2016年武汉轻工大学数学与计算机学院运筹学复试笔试最后押题五套卷
● 摘要
一、计算题
1． 某运输问题的一个运输方案如表所示。格子右上角的黑体数字为相应供需方之间的运价，右下角的斜体数字为相应的运输量。
（l ）该方案是不是最优运输方案? 为什么? （2）用闭合回路法进行进一步的调整。
【答案】（l ）用位势法计算各空格的检验数。令μ=0，计算结果如表所示:
在非基变量的检验数中，（A 2，B 3）的检验数为-l<0。所以该方案不是最优运输方案。
（2）从上述表格中的空格（A 2，B 3）出发点作一闭回路，并对闭回路上的点进行正负编号，如表所示。
得到新的运输方案为:
2． 用Gomory 切割法解以下问题。
【答案】（1）在该线性规划问题的约束条件中分别加入松弛变量x3，x4，化为标准型
先不考虑上述模型中的整数约束，利用单纯形法进行求解，如表所示。
表
此时的最优解为最优目标值。
由表中最终单纯形表可得变量间的关系式：
将系数和常数项都分解成整数和非负数真分数之和，移项，则以上两式变为
要求x 1，x 2，x 3，x 4为非负整数，从上述两式看来，等式左边是整数，等式右边括号内是正数，所以等式右边必须是负数，则上述第二个等式的右端可由下式代替：
即
加入松弛变量x 5，即得到切割方程:
表
将该约束条件加入到上表的最终单纯形表中，并进行进一步求解，如下表所示。
由于x l ，x 2己为整数，所以最优解为
（2）在该线性规划问题的约束条件中分别加入松弛变量x 3，x 4，x 6及人工变量x 5，化为标准型
先不考虑模型中的整数约束，利用单纯形法进行求解，如表所示。
表
相关内容
相关标签