同济运筹学2005到2006期末试卷A

1、20052006运筹学（I）课程试卷A一、辨析题（详细说明理由）。（每小题3分，本题共15分）1.一个极小化线性规划的某轮表格中有=(-1，-2，0，0，0)，请问是否可以选择作为进基变量？为什么？2.线性规划原问题和对偶问题都有可行解，则原问题的目标函数值一定不小于对偶问题的目标函数值？为什么？3.有一个线性规划，它有8个变量、4个独立的约束。请问(1，2，3，4，5，0，0，0)是否可以是它的一个基本可行解？为什么？4. m个发点，n个收点的产销平衡运输问题数学模型约束条件中，独立约束条件有多少个？为什么？5.一个赋权图的最小生成树是否唯一？为什么？二、求极小化线性规划问题的一个单纯形表如

2、下表。问a1、a2、a3、a4、a5 、a6分别为何值时：（本题共13分） -3 0 1 0 -1a1 1 0 0 2a2 0 0 1 a32a44 a5 0 0 0 a6(1) (1) 表中给出线性规划是唯一解；(2)表中给出线性规划有无穷多解； (3)表中给出线性规划的可行解无界； (4)表中给出线性规划为换入变量，为换出变量； 三、给出线性规划：（本题共10分） （1）写出对偶问题；（2）已知，是上述线性规划的最优解，用互补松弛定理求对偶问题的最优解。四、已知线性规划：（本题共12分） 标准化后的初始表和最优表如下（）CjCB XB7 12 10 0 0X1 X2 X3 X4 X5b0

3、X40 X5 1 1 1 1 0 2 2 1 0 120307 12 10 0 010 X312 X2 0 0 1 2 11 1 0 1 1 10 10 5 0 0 8 2（1）求对偶问题的最优解。（2）若该LP问题原目标函数中X1 的系数由7变为9，问最优解有什么变化？（3） 若右端常数由变为，问最优解有什么变化？ 五、若发点，及收点，的有关数据如下表所示。假定，处允许物资存储，问怎样调配以使总的支付费用最少？试建立运输模型再进行求解。（本题共10分） 供应量存储费4 6 86 2 420020054需求量50 100 100六、用分支定界法求解整数规划问题：（本题共10分） s.t. 七、

4、已知4个人做4件事情的收益如下表，问如何分配任务使得收益最大化。（本题共10分） 11 8 9 12 6 7 8 10 14 12 10 7 7 5 8 6八、用Dijkstra法求到各顶点的最短路。（本题共10分） 九、下图中弧旁的数字（，）（表示容量，表示流量）：（本题共10分）（1）验证图中的流是可行流； （2）求网络的最大流；（3）证明（2）中求出的流是最大流。20052006运筹学（I）课程试卷A参考答案一、辨析题（本题共5小题，每小题3分，共15分）1.答：可以。（1分）因为所对应的检验数为“-1”，把作为进基变量，仍然可以改进目标函数值。（2分）2.答：对。（1分）因为原问题和对

5、偶问题都有可行解，则两问题必有最优解，则依照对偶问题的性质可知，原问题的目标函数值一定大于等于对偶问题的目标函数值。（2分）3.答：不可以。（1分）因为该线性规划只有4个独立约束，则相应基变量只有4个，则的解中最多只有4个是非零。（2分）4.答：独立约束条件有m+n-1个。（1分）因为，该运输问题数学模型中虽然有m+n个约束条件，但其中一个是沉余项，约束条件中实际只有m+n-1个条件是独立的。（2分）5.答：不是唯一。（1分）因为赋权图中边的所赋权可能是相同的，在这种情况下得到的最小生成树就不唯一的。（2分）二、解：(1) , 0，。(3分)(2) 0、0 , =0，0。(3分) (3) ，0

6、，0，0。(3分) (4) ，0，0，0, 0且或，0，0,0。(4分)三、解：(1)其对偶问题如下： ，。(3分) (2)使用互补松弛定理，得到如下结果：(其中为取最优解时约束条件不等号左右两边的差值，) (=4)=0 (=6)=0 (=0)=0 ，。 （2分） 由此得到：=0，=0。 （2分） 所以： 得到： （2分） 则对偶问题的最优解为。（1分）四、解：(1)根据对偶问题最优解与原问题最优表的联系，可以直接得到对偶问题的最优解为： 。 （3分） (2)由题意可知：， 因此可知：该最优表中的最优基不变， 所以：最优解不发生变化。 （3分） (3)由最优表中的信息可得： ，（1分） 则 ，

7、（2分）将代替最优表中的，采用对偶单纯形法继续求解得到最终最优表为：CB XBX1 X2 X3 X4 X5b10 X30 X4 2 2 1 0 1 1 1 0 1 1 30 10 13 8 0 0 10 （2分）由此可知：最优解产生了变化，且最优解为。（1分）五、解：该运输问题为产销的问题，虚拟销地，形成新的问题： 供应量4 6 8 56 2 4 4200200需求量50 100 100 150 （2分）设的运输量为，则由新的运输问题可以得到： ， （2分）使用最小元素法得到初始解： 供应量50 100 50 100 100200200需求量50 100 100 150 （2分）使用位势法，得

8、到检验数为： 0 3 0 03 0 -3 00-14 3 8 5增加的运输量，得到新的解为： 供应量50 0 150 100 100200200需求量50 100 100 150 （2分）使用位势法，得到检验数为： 0 0 0 06 0 0 30-44 6 8 5因此可知： 供应量50 0 150 100 100200200需求量50 100 100 150为该运输问题的最优解。（2分）六、解：采用分支定界法进行求解，其求解枚举树图如下： 9 （2，3/2） （2分） 8 17/2 （2，1） （3/2，2） （2分） 7 （1，2） （2分） 无可行解 （2分）由分支定界法求解过程可知，最优解为，其对应的最优值为：。（2分）七、解：注意到本题要求求解收益最大化，因此按照极大化问题转化为极小化问题的原则，并按照匈牙利方法计算如下： （2分） （2分） （2分）