第五章 整数规划练习题答案.pdf

《第五章 整数规划练习题答案.pdf》由会员分享，可在线阅读，更多相关《第五章 整数规划练习题答案.pdf（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章整数规划练习题答案一.判断下列说法是否正确1.用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是该问题目标函数值的下界。（）2.用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解.(）3.用割平面法求解纯整数规划时,要求包括松弛变量在内的全部变量必须取整数值。(）4.指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。（）二.设有五项工作要分派给五个工人，每人的作业产值如下表所示,为了使总产值最大，问应如何分配这五项工作，并求得最大产值。工作工人甲乙丙丁戊答案：答案：设原矩阵为 A，因求极大问题,令 B=Maij，其中 M=

2、Maxaij=10，则：12B 16025A989410B45785C69363D810596E5685365325425105104257521 0241515105747125261443 33625316371441414004241 004547012526144333642134003154002034646441403m4n5 1lm4603102400315400203353531634131525432 00300m=5=n，得最优解。解矩阵X*003011051010100001。000000即,甲D，乙C,丙E,丁B，戊A，最大产值=10+8+9+8+8=43.三.对整数规

3、划MaxZ 8x15x22x13x212x x 612x,x 0,整数12解得其松弛问题最优表如下：CB58cjXBx2x1b3/215/475/28x10105x21000 x31/41/80 x4-1/43/8j9/47/4要求：用割平面法完成求解过程。答案：(1)产生高莫雷约束：根据 Maxfi，应选取 x1所在行为源行:x1313产生高莫雷约束为：x3x40.488313313x3x4 3,即，x10 x30 x43488488(2)将高莫雷约束加入松弛变量 x5，写入原表最后一行形成下表并用对偶单纯形法求解：CB580cjXBbx23/2x115/4x58x101008x101005x210005x210000 x31/41/8-1/80 x41/43/8-3/80 x500103/475/2jCB580cjXBx2x1x49/4-7/40 x31/301/30 x40010b232340 x52/318/314/3b 列均为整数，所有j均非负，已得最优整数解：X=(3,2)T,Z*=34。j5/32