《管理运筹学第8章整数规划汇总》由会员分享，可在线阅读，更多相关《管理运筹学第8章整数规划汇总（12页珍藏版）》请在金锄头文库上搜索。
1、 1幣数规划的图解法2幣数规划的计算机求解3整数规划的应用4整数规划的分枝定界法求整数解的线性规划问题，不是用四舍五入法或去 尾法对线性规划的非整数解加以处理都能解决的， 而要用整数规划的方法加以解决。在整数规划中，如果所有的变量都为非负整数，则 称为纯整数规划问题;如果有一部分变量为负整数, 则称之为混介整数规划问题。在整数规划中，如果 变量的取值只限于0和1,这样的变量我们称之为()- 1变量。在纯整数规划和混合整数规划问题中，如 果所有的变量都为0-1变量，则称之为01规划。*12例1.某公司拟用集装箱托运卬.乙两种货物，这两种货物每件的体积、重帚.可获利润以及托运所受限制如农所示。货物
2、每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲19542乙273403托运限制1365140甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最人。 解：设X】、X2分别为甲.乙两种货物托运的件数，建立模型目标函数：Max z = 2x）+3 x2约束条彳牛：s.t.195X） + 273 x2 13654x. + 40 x； 140Xj 0为整数。如果去掉最后一个约束，就是一个线性规划问题。利用图解法，得到线性规划的垠优解为x,=2.44, X2=326,目标函数值为14.66。 由图表可看出，整数规划的故优解为x,=4, x2=2,目标函数值为14。性质1:任何求最大丨1
3、标函数值的纯整数规划或混合梏数规划的最大II 标函数值小于或等于相应的线性规划的最大口标函数值；任何求最小口翕 #标函数值的纯整数规划或混合整数规划的最小II标函数值人于或等于相N的线性规划的最小H标函数值。 2数规划的计算机求解例2：例3:Max z = 3召+也+ 3西Max z = 3x1 + x2 + 3x3s. t.s. t.-xx + 2x2 十西 W 4-X + 2x2 + X3 W 44x2 3x3 W2 x x2=3. 30线性规划3：Max 2x3x2s. t. 195+273x2 13654*i+ 40 乜 W140 xj W43ATp X2 0解得z3=14. 58,
4、x产3, x2=2. 8618 4建数规划的分枝定界法（四）修改整数规划的垠优冃标函数的上下界。经分析，将上界z = 14.66修改为J=14.58, z=13o线性规划2和线性规划3中选样.个I:界最人的线件规划，即线性规划3,进 行分枝。线性规划3分解为线性规划4和线性规划5,如卜：线件规划4： Max 2冯十3乜s. t. 195场+273乜W13654码+ 40*2140町W4X0 3x2 W2X, x2 0线性规划5：解得乙产14, X=4, x2=2Max 2x3x2无可行解s. t 195场+273也01365 4曲+ 40 助 W140 x& 3 *2$ 3ATX . *2$
5、0 4 建数规划的分枝定界法（六）进-步修改整数规划最优目标函数值Z*的上下界。从线性规划2, 4, 5中修改上下界。分析后，可得2 =14,空=14。都 取线性规划2, 4, 5中的整数町行解的H标函数值的最大值。性质2：当整数规划的最优日标函数值/的上界？等于其下界乙 时，该整数规划的最优解己经被求出。这个整数的最优解即 为其目标函数值取此卜界的对应线性规划的整数可行解。用图8-2表示例9的求解过程与求解结果图8-2从以上解题过程可得用分枝泄界法求解目标函数值最大的整数规划的 步骤，我们将求解的整数规划问题称为A,将与其和对应的线性规划问题 称为B：第一步：求解问题B,可得以下情况之一：1
6、. B没有可行解，则A也没有可行解，求無过程停止。2. B仃故优解，且符合问题A的整数条件，贝IJB的故优解即为A的最优 解，求解过程停止。3. B有故优解，但不符合A的整数条件，记其目标函数值为可。第二步：确定A的最优II标函数值z*的上下界，其上界即为z仁勺，再 用观察法找到A的一个整数口J行解，求其冃标函数值作为z*的下界，记为 Z_o第三步：判断，是否等于Z。若相等，则整数规划最优解即为其I标 函数值等于Z的A的那个整数可行解：否则进行第四步。 4 建数规划的分枝定界法第四步：在B的最优解中选一个最远离密数要求的变量，不妨设此变量 为勺以叩表示小于J的晟大整数.构造以卜一两个约朿条件.并加入问题B 得劲B的吋个分枝$和B?。Xj Wbj和 Xj 2 bjJ+1第五步：求解B詡IB?。修
