运筹学第17讲复习分配问题与匈牙利法

《运筹学第17讲复习分配问题与匈牙利法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章   整数规划与分配问题整数规划的特点及作用分枝定界法割平面法分配问题与匈牙利法应用举例IntegerProgramming,简称IP有纯整数规划、混合整数规划与0-1整数规划等类型。我们只研究线性整数规划。整数规划是研究决策变量只能取正整数的一类规划问题。整数规划的特点（1）可行解域为离散点集（2）不能用舍入取整法（3）目标函数值的最优值不会优于其松弛问题的最优值整数规划的特点整数规划的求解分枝定界法割平面法共同点：通过增加附加约束，使整数最优解最终成为线性规划可行域的一个顶点，从而使问题可利用单纯形法求

2、出这个整数最优解；不同点：附加约束条件的选取原则及方法不同。实质：在保留原问题全部整数可行解的前提下，将原问题分枝为若干容易求解的子问题，并利用子问题的整数解的目标值来判定分枝的界限<定界>。分枝定界法分枝边界解：设应购进甲、乙机床台数分别为x1和x2，数学模型为：1、去掉变量为整数约束，可用图解法求得最优解；x1x20123456789654321x1=3.25非整数，进行分枝(2)4x1+2x2=18(1)2x1+3x2=14(3.25,2.5)TX(0)=(x1,x2)T=(3.25,2.5)TZ(0)=1

3、4.75【例】某厂拟购进甲、乙两类机床生产新产品。已知两类机床进价分别为2万元和3万元，安装占地面积分别为4m2和2m2，投产后的收益分别为3百元/日和2百元/日。厂方仅有资金14万元，安装面积18m2，为使收益最大，厂方应购进甲、乙机床各多少台？x1=3.25非整数，进行分枝2、得两个子问题的数学模型:子问题(1)子问题(2)分别用图解法求得最优解X(1)=(3,2.67)T,Z(1)=14.33X(2)=(4,1)T,Z(2)=14子问题1x1x20123456789654321(2)(1)子问题2(4,1)

4、Z(1)＞Z(2)=14子问题2停止分枝，其整数解作为界；子问题1对x2=2.67进行分枝子问题(3)子问题(4)x1x20123456789654321(3)(0)子问题3子问题4(1)(2)(4)子问题(1)Z(1)

5、分枝，其整数解作为界；子问题1对x2=2.67进行分枝分别用图解法求得最优解X(3)=(3,2)T,Z(3)=13X(4)=(2.5,3)T,Z(4)=13.5Z(3)

6、3添加x2≤2添加x1≥4√分枝问题解可能出现的情况表情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6中问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况4或5割平面法割平面法的基础仍然是用解线性规划的方法去解整数规划问题：首先不考虑变量为整数这一条件，但增加线性约束条件（Gomory约束，称为割平面），使得原可行解域中切掉一部分，这部分只包含非整数解，但没切割掉任何整数可行解，切除的结果使整数解可能成为顶点。分枝定解法是对原问题可行解域进行了切割，切割方法是对取非

7、整数解相邻的整数作附加约束，约束方程简单，但子问题由于分枝的增多而成指数增长。割平面法割平面法的基础仍然是用解线性规划的方法去解整数规划问题：首先不考虑变量为整数这一条件，但增加线性约束条件（Gomory约束，称为割平面），使得原可行解域中切掉一部分，这部分只包含非整数解，但没切割掉任何整数可行解，切除的结果使整数解可能成为顶点。关键：如何找到割平面约束方程，使切割后最终得到这样的可行域——它的一个整数坐标的顶点恰好是问题的最优解。割平面法的步骤求松弛问题的最优基可行解判断是否为整数解否在单纯形表中加入一行利用对

8、偶单纯形算法求最优解是停止得到最优解附加约束利用具有最大分数部分的非整基变量例题：用割平面法求解下列整数规划maxz=3x1+2x2s.t.x1+0.5x2≤4.52x1+3x2≤14x1,x2≥0,且均取整数值第1步.去掉整数约束找出松弛问题，若约束条件系数和右边常数不是整数，则必须化为整数（保证所添加的松弛变量均为整数）；maxz=3x1+2x2s.t.2x1+x2≤