运筹学思考练习题答案.doc

1、第一章 L.P 及单纯形法练习题答案一、判断下列说法是否正确1. 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。()2. 线性规划问题的每一个基解对应可行域的一个顶点。()3. 如线性规划问题存在某个最优解，则该最优解一定对应可行域边界上的一个点。()4. 单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个基可行解中至少有一个基变量的值为负。()5. 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。()6. 若 、 分别是某一线性规划问题的最优解，则 也是该线性规划1X2 12X问题

2、的最优解，其中 、 为正的实数。()127. 线性规划用两阶段法求解时，第一阶段的目标函数通常写为 (xai 为人工aiMinZ变量) ，但也可写为 ，只要所有 ki 均为大于零的常数。()iaMinZkx8. 对一个有 n 个变量、m 个约束的标准型的线性规划问题，其可行域的顶点恰好为个。()nC9. 线性规划问题的可行解如为最优解，则该可行解一定是基可行解。()10. 若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解。()二、求得 L.P 问题 1231425jMaxZx8416x0;,的解如下：X =(0,3,2,16,0)T; X =(4,3,-2,0

3、,0)T; X =(3.5,2,0.5,2,4)T;X =(8,0,0,-16,12)T; =(4.5,2,-0.5,-2,4)T; X =(3,2,1,4,4)T; X =(4,2,0,0,4)T。要求：分别指出其中的基解、可行解、基可行解、非基可行解。答案：2基解：X 、X 、X 、X ，可行解：X 、X 、X 、X ，基可行解：X 、X ，非基可行解：X 、X (或非基可行解：X 、X 、X 、X 、X )。三、求解下列线性规划问题： 1212MinZ5x46s.t3x,0答案：化为标准型：12312453MaZx6s.tx,x0得初始单纯形表并求解： jc5 4 0 0 0BCXb 1

4、x23x45xi0 3x6 1 2 1 0 0 60 44 2 -1 0 1 0 20 515 5 3 0 0 1 3jjjcz0 54 0 0 00 3x4 0 5/2 1 -1/2 0 8/55 12 1 -1/2 0 1/2 0 0 55 0 11/2 0 -5/2 1 10/11jjjcz-10 0 13/20 -5/2 00 3x19/11 0 0 1 7/11 -5/11 19/75 127/11 1 0 0 3/11 1/11 94 210/11 0 1 0 -5/11 2/11 jjjcz-175/11 0 0 0 5/11-13/110 4x19/7 0 0 11/7 1 -

5、5/75 112/7 1 0 -3/7 0 2/74 215/7 0 1 5/7 0 -1/7jjjcz-120/7 0 0 -5/7 0 -6/7所有检验数 ，已得最优解： ， 。j0 T*59X,712MinZ734第二章 对偶理论与灵敏度分析练习题答案1判断下列说法是否正确：(1) 任何线性规划问题存在并具有惟一的对偶问题；()(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；()(3) 设 ， 分别为标准形式的原问题与对偶问题的可行解， ， 分别为其最优解，则恒jxiy *jxiy有 ；()nnm*jjii1111cby

6、(4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；()(5) 已知 为线性规划的对偶问题的最优解，若 ，说明在最优生产计划中第 i 种资源*iy *iy0已完全耗尽；()(6) 已知 为线性规划的对偶问题的最优解，若 ，说明在最优生产计划中第 i 种资源*i *i一定有剩余；()(7) 若某种资源的影子价格等于 k，在其他条件不变的情况下，当该种资源增加 5 个单位时，相应的目标函数值将增大 5k；()(8) 应用对偶单纯形法计算时，若单纯形表中某一基变量 ，又 xi 所在行的元素全部大i0于或等于零，则可以判断其对偶问题具有无界解；()(9) 若线性规划问题中的

7、bi，c j 值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；()(10)在线性规划问题的最优解中，如某一变量 xj 为非基变量，则在原来问题中，无论改变它在目标函数中的系数 cj 或在各约束中的相应系数 aij，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。()2下表是某一约束条件用“”连接的线性规划问题最优单纯形表格，其中 x4、x 5 为松弛变量。XB x1 x2 x3 x4 x5x3 5/2 0 1/2 1 1/2 0x1 5/2 1 -1/2 0 -1/6 1/3j 0 -4 0 -4 -2要求：(1)写出原线性规划问题及其对

8、偶问题的数学模型；(2)直接由表写出对偶问题的最优解； (3)其它条件不变时，约束条件右端项 b1 在何范围内变化，上述最优基不变。 (4)若以单价 2.5 购入第一种资源是否值得，为什么？若有人愿意购买第二种资源应要价多少，为什么？5答案：(1)注：该问题得解法非唯一，以下解法只是其中一种（各解法原理相同） 。由题意已知原线性规划问题目标函数为 Max（因 j0 为最优） ，且 c4、c 5 为 0（松弛变量目标函数系数为 0） 。根据 知： ，得：1jjBjcCP2311cc406c23123c60根据 ，得：5112221 6300A|b 125A|b301则原线性规划问题的数学模型为：

9、 123312MaxZ6x05s.t,其对偶问题的数学模型为： 1212Min5y36s.t0y,(2)直接由表写出对偶问题得最优解为： *Y4,(3)令原解 ，得 br 的变化范围为：()-1iBiixXb，其中： 。则：iriririi iMab/|0Mn/a|01iriraB，即 ，则()1551xi22615b10b2(4)以单价 2.5 购入第一种资源是值得的，因其小于该资源“影子价格” （即 2.54） ，可盈利；第二种资源应要价至少为 2（影子价格） ，否则不如自己组织生产。6第三章运输问题、第四章目标规划练习题答案一、判断下列说法是否正确1表上作业法实质上就是求运输问题的单纯形

10、法。()2在运输问题中，只要任意给出一组含(m+n-1)个非零的 xij，且满足 ，n1jiiax，就可以作为一个初始可行解。()m1ijjbx3建立目标规划模型时，正偏差变量应取正值，负偏差变量应取负值。()4线性规划问题是目标规划问题的一种特殊形式。()二、用表上作业法求解下表最小运费方案销地产地 甲 乙 丙 丁 产量1 18 14 17 12 1002 5 8 13 15 1003 17 7 12 9 150销量 50 70 60 80答案：因该问题为产销不平衡问题，总产量 350 (100+100+150)大于总销量 260 (50+70+60+80)，故假想一销地“戊” ，其销量为

11、90 (350-260)，形成产销平衡问题，并用Vogel 法求得初始解：销地产地 甲 乙 丙 丁 戊 产量 差额18 14 17 12 01 10 90 10010 12 12 2 2 5 125 8 13 15 02 50 50 10050,0 5 8 5 17 7 12 9 03 20 60 70 150130,70 7 7 2 2 3 9销量 50，0 70,20,0 60,0 80 90，012 1 1 3 0 1 1 3 0 1 1 3 7 5 3 5 3 差额 3 用位势法求空格检验数：甲 乙 丙 丁 戊 ui18 14 17 12 01 11 4 2 10 90 35 8 13

12、 15 02 50 50 0 5 2 13 13 17 20 7 60 12 70 9 3 0 07vj 4 7 12 9 -3所有空格检验数 ij0，表中已得最优解： ， (就地贮存)， ，14x015921x50， ， ， ，其余 ；最小运费： 。2x50323x6340ij *Z6但考虑非基变量 的检验数 23=0，该问题有无穷多最优解，用闭回路法调整得另一最2优解： ， (就地贮存)， ， ， ， ， ，其14159021x523032x731034x7余 。(见下表)ijx0甲 乙 丙 丁 戊 ui18 14 17 12 01 10 90 35 8 13 15 02 50 50 11

13、7 7 12 9 03 70 10 70 0vj 4 7 12 9 -3三、针对目标规划模型： 12321122312iMinZPddx48x,0;d,i1,3 (1)用图解法求出问题的满意解。(2)若将目标函数改为： 1233MinZPdd满意解会如何变化。答案：(1) 满意解为图中 A(4,0)、B(6,1)、C(2,3)所围成的区域。x1x2 12x4123x12x4281d2d23d3A(4,0)B(6,1)C(2,3)O8(2) 满意解为 B(6,1)、C(2,3)线。9第五章整数规划练习题答案一. 判断下列说法是否正确1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整

14、数解的目标函数值是该问题目标函数值的下界。()2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。()3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。()4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。()二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问应如何分配这五项工作，并求得最大产值。工作工人 A B C D E甲 9 4 6 8 5乙 8 5 9 10 6丙 9 7 3 5 8丁 4 8 6 9 5戊 10 5 3 6 3答案：设原矩阵为 A，因求极大问题，令 B=M-

15、aij，其中 M=Maxaij=10，则：1642510140210253B376540354074061 m4n5l213213454566 0312406035m=5=n，得最优解。解矩阵 。31243563*1X001即，甲D，乙 C，丙E，丁B，戊 A，最大产值=10+8+9+8+8=43。10三. 对整数规划 1212MaxZ85x36,0,整 数解得其松弛问题最优表如下：cj 8 5 0 0CB XB b x1 x2 x3 x4 5 x2 3/2 0 1 1/4 -1/48 x1 15/4 1 0 1/8 3/8 j 75/2 0 0 -9/4 -7/4要求：用割平面法完成求解过程

16、。答案：(1) 产生高莫雷约束：根据 Maxfi，应选取 x1 所在行为源行： ，即，134xx81343x08产生高莫雷约束为： 。341x08(2) 将高莫雷约束加入松弛变量 x5，写入原表最后一行形成下表并用对偶单纯形法求解：cj 8 5 0 0 0CB XB b x1 x2 x3 x4 x5 5 x2 3/2 0 1 1/4 -1/4 08 x1 15/4 1 0 1/8 3/8 00 x5 -3/4 0 0 -1/8 -3/8 1 j 75/2 0 0 -9/4 -7/4 0cj 8 5 0 0 0CB XB b x1 x2 x3 x4 x5 5 x2 2 0 1 1/3 0 -2/38 x1 3 1 0 0 0 10 x4 2 0 0 1/3 1 -8/3 j 34 0 0 -5/3 0 -14/3b 列均为整数，所有 j 均非负，已得最优整数解：X *=(3, 2)T，Z *=34。