《《运筹学(I)》课程试卷A》由会员分享，可在线阅读，更多相关《《运筹学(I)》课程试卷A（11页珍藏版）》请在金锄头文库上搜索。
1、20052006 学年第二学期考试试卷运筹学（I） 课程试卷 A（本卷考试时间 120 分钟）一、辨析题（注：请详细说明理由） 。 （每小题 3 分，本题共 15 分）1.一个极小化线性规划的某轮表格中有 r=(-1，-2 ，0，0， 0)，请问是否可以选择 1x作为进基变量？为什么？2.线性规划原问题 minTCXAb，和对偶问题ax0TbUA，都有可行解，则原问题的目标函数值一定不小于对偶问题的目标函数值？为什么？3.有一个线性规划，它有 8 个变量、4 个独立的约束。请问 X(1，2，3，4，5，0，0，0)T是否可以是它的一个基本可行解？为什么？4. m 个发点，n 个收点的产销平衡运
2、输问题数学模型约束条件中，独立约束条件有多少个？为什么？ 5.一个赋权图的最小生成树是否唯一？为什么？二、求极小化线性规划问题的一个单纯形表如下表。问 a1、a 2、a 3、a 4、a 5 、a 6 分别为何值时：（本题共 13 分） BX1x2 3 4x 5b32x4-3 0 1 0 -1a1 1 0 0 2a2 0 0 1 a32a44ra5 0 0 0 a6 (1) 表中给出线性规划是唯一解；(2)表中给出线性规划有无穷多解；(3)表中给出线性规划的可行解无界；(4)表中给出线性规划 1x为换入变量， 4x为换出变量； 三、给出线性规划：（本题共 10 分）max3216xfts. 14
3、30x2 0x（1）写出对偶问题；（2）已知 41x， 62， 3x，是上述线性规划的最优解，用互补松弛定理求对偶问题的最优解。四、已知线性规划：（本题共 12 分） max32107xfts. 21x300标准化后的初始表和最优表如下（ f）CjCB XB7 12 10 0 0X1 X2 X3 X4 X5b0 X40 X51 1 1 1 02 2 1 0 12030r7 12 10 0 0 10 X312 X20 0 1 2 11 1 0 1 11010r5 0 0 8 2 （1）求对偶问题的最优解。（2）若该 LP 问题原目标函数中 X1 的系数由 7 变为 9，问最优解有什么变化？（3）
4、 若右端常数21b由 30变为 4，问最优解有什么变化？ 五、若发点 1A， 2及收点 1B， 2， 3的有关数据如下表所示。假定 1A， 2处允许物资存储，问怎样调配以使总的支付费用最少？试建立运输模型再进行求解。（本题共 10 分）1 2 3B供应量 存储费1A24 6 86 2 420020054需求量 50 100 100 六、用分支定界法求解整数规划问题：（本题共 10 分）max 123zxs.t. 712x0,1,2iii为 整 数 ，七、已知 4 个人做 4 件事情的收益如下表，问如何分配任务使得收益最大化。（本题共 10 分）1B 2 3B 41A234A11 8 9 126
5、 7 8 1014 12 10 77 5 8 62v2vS八、用 Dijkstra 法求 1到各顶点的最短路。 （本题共 10 分）九、下图中弧旁的数字（ ijC， ijf） （ ij表示容量， ijf流量）：（本题共 10 分）（1）验证图中的流是可行流； （2）求网络的最大流；（3）证明（2）中求出的流是最大流。20052006 学年第二学期考试试卷运筹学（I） 课程试卷 A 参考答案（本卷考试时间 120 分钟）一、辨析题（本题共 5 小题，每小题 3 分，共 15 分）1.答：可以。 （1 分）因为 1x所对应的检验数为“-1” ，把 1x作为进基变量，仍然可以改进目标函数值。 （2
6、分）2.答：对。 （1 分）因为原问题和对偶问题都有可行解，则两问题必有最优解，则依照对偶问题的性质可知，原问题的目标函数值一定大于等于对偶问题的目标函数值。 （2 分）3.答：不可以。 （1 分）（5，1）（6，1）tv（1，0）（4，1）（1，0）（6，1）4v（2，1）（2，1）因为该线性规划只有 4 个独立约束，则相应基变量只有 4 个，则 X的解中最多只有 4 个是非零。 （2 分）4.答：独立约束条件有 m+n-1 个。 （1 分）因为，该运输问题数学模型中虽然有 m+n 个约束条件，但其中一个是沉余项，约束条件中实际只有 m+n-1 个条件是独立的。 （2 分）5.答：不是唯一。
7、 （1 分）因为赋权图中边的所赋权可能是相同的，在这种情况下得到的最小生成树就不唯一的。 （2 分）二、解：(1) 40a, 50， 60a。(3 分)(2) 10、 20 4, 5=0， 60。(3 分)(3) 4， 50， 10， 20。(3 分)(4) 4a， 50， 1a0， 20, 6a0 且421a或 0， 5a0， 10,20。(4 分)三、解：(1)其对偶问题如下：min 124zuts. 61 243u10， 。(3 分)(2)使用互补松弛定理，得到如下结果：( 其中 i为 U取最优解时约束条件不等号左右两边的差值， 1,23.i)min 124zuts. 6 1x(=4)=
8、01 2 (=6)=0243u 3 (=0)=010， 。 （2 分）由此得到：1=0， 2=0。 （2 分）所以： 126u得到：12u（2 分）则对偶问题的最优解为 (,)TU。 （1 分）四、解：(1)根据对偶问题最优解与原问题最优表的联系，可以直接得到对偶问题的最优解为：(8,2)TU。 （3 分）(2)由题意可知： 1C，1523r，因此可知：该最优表中的最优基不变，所以：最优解不发生变化。 （3 分）(3)由最优表中的信息可得：12B， （1 分）则 1 4053b， （2 分）将50代替最优表中的，采用对偶单纯形法继续求解得到最终最优表为：CB XB X1 X2 X3 X4 X5
9、 b10 X30 X42 2 1 0 11 1 0 1 13010r13 8 0 0 10 （2 分）由此可知：最优解产生了变化，且最优解为 *(,31,)TX。 （1 分）五、解：该运输问题为产销的问题，虚拟销地 4B，形成新的问题： 1B 2 3B 4供应量1A24 6 8 56 2 4 4200200需求量 50 100 100 150 （2 分）设 iA jB的运输量为 ijx，则由新的运输问题可以得到：mn 121342123446856f xxx21234113240.68055xxst 0ijx， ,.i,34.j （2 分）使用最小元素法得到初始解：1B 2 3B 4供应量1A
10、250 100 50100 100200200需求量 50 100 100 150 （2 分）使用位势法，得到检验数为：1B 2 3B 4iu 1A20 3 0 03 0 -3 00-1jv4 3 8 5 增加 2A 3B的运输量，得到新的解为： 1B 2 3B 4供应量1A250 0 150100 100200200需求量 50 100 100 150 （2 分）使用位势法，得到检验数为：1B 2 3B 4iu 1A20 0 0 06 0 0 30-4jv4 6 8 5 因此可知：1B 2 3B 4供应量1A250 0 150100 100200200需求量 50 100 100 150 为
11、该运输问题的最优解。 （2 分）六、解：采用分支定界法进行求解，其求解枚举树图如下：A0()K9（2，3/2 ） （2 分）21x 2xA1()K8 A2()K17/24v3（2，1） （3/2 ，2） （2 分）1x12xA3()K7 A4()K（1，2） （2 分） 无可行解 （2 分）由分支定界法求解过程可知，最优解为 *(2,1)TX，其对应的最优值为：*8f。 （2 分）七、解：注意到本题要求求解收益最大化，因此按照极大化问题转化为极小化问题的原则，并按照匈牙利方法计算如下： 18912670445681430270123047（2 分） （2 分）130472012348（2 分）
12、 （2 分）从而得到本题的最优分配方案 I： 1A B， 2 4， 3A 2B， 4 3；最优分配方案 II： 1 4， 2 ， 3 1， 。最大收益为 41。 （2 分）八、解：使用 Dijkstra 法得到最优解为：2v1v3vS2vSv1v3v530 6 95 7 （10 分）九、用标号法求最大流，并给与证明。 （本题共分）解：(1)对于任何一个边上的流量 ijf都满足：0ijijfC且在该运输网络中间顶点都满足流量守恒条件，所以，该图中的流为可行流。 （3 分）(2) 上图即为最大流。 （3 分）(3)由上图中的 f中不存在 f的增流链，因此上图中的流 f即为最大流。 （2 分）S=VS,V1,V2 S*=V3,V4,Vt
