第五章-整数规划练习题答案教程文件.doc

第五章 整数规划练习题答案精品资料第五章 整数规划练习题答案一. 判断下列说法是否正确1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是该问题目标函数值的下界。(P)2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。(O)3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。(P)4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。(P)二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问应如何分配这五项工作，并求得最大产值。工作工人ABCDE甲 946 85乙 859106丙 973 58丁 486 95戊1053 63答案：设原矩阵为A，因求极大问题，令B=M-aij，其中M=Maxaij=10，则： m=5=n，得最优解。解矩阵。即，甲D，乙C，丙E，丁B，戊A，最大产值=10+8+9+8+8=43。三. 对整数规划解得其松弛问题最优表如下：cj8500CBXBbx1x2x3x45x23/2011/4-1/48x115/4101/83/8j75/200-9/4-7/4要求：用割平面法完成求解过程。答案：(1) 产生高莫雷约束：根据Maxfi，应选取x1所在行为源行：，即，产生高莫雷约束为：。(2) 将高莫雷约束加入松弛变量x5，写入原表最后一行形成下表并用对偶单纯形法求解：cj85000CBXBbx1x2x3x4x55x23/2011/4-1/408x115/4101/83/800x5-3/400-1/8-3/81j75/200-9/4-7/40cj85000CBXBbx1x2x3x4x55x22011/30-2/38x13100010x42001/31-8/3j3400-5/30-14/3b列均为整数，所有j均非负，已得最优整数解：X*=(3, 2)T，Z*=34。仅供学习与交流，如有侵权请联系网站删除 谢谢3