运筹学(第五版)习题答案.docx

《运筹学(第五版)习题答案.docx》由会员分享，可在线阅读，更多相关《运筹学(第五版)习题答案.docx（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学习题答案第一章(39页)L1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷 多最优解、无界解还是无可行解。(1) max50+10S050S4-a0 ia 4S00(2) min z=+1.5初始单纯形表:0-M-M ss s0sabaa 00a s -Maii0 011 00 0-Mai0i 00 00 0 -Mai00 1000 11 1-snM00 0目3臼 EE 回1. 3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基 可行解，并代入目标函数，确定最优解。1 1) max z=20+3S +4S +7S20 +3SS-4二80-2S +6S-7S

2、=-3Sssa0 o(2)max z=50-2a+3s-6SS +2S +3S +4二7+a4-a +2S =3S a a a o(1)解：系数矩阵A是：EH令A二(09sss)线形无关，以（hS ）为基，SS 为基变量。有 2+3S=8+a +4as-2s =-3-6S +7S令非基变量ss =0解得:=1;=2基解区=（1, 2, 0, 0a 为可行解s=8同理，以（0S）为基，基解3=（45/13, 0, -14/13, 00是非可行解；以（0S）为基，基解=（34/5, 0, 0, 7/50是可行解，0=117/5；）为基，基解a二(0, 45/16, 7/16, 00是可行解，S =

3、163/16；以(as)为基，基解a=(0, 68/29, 0, -7/290是非可行解；以(SS)为基，基解a=(0, 0, -68/31, -45/310是非可行解；最大值为0=117/5；最优解3=(34/5, 0, 0, 7/5S(2)解:系数矩阵A是:目令A二(0SSS)S9S线性无关，以(0a)为基，有：+2a=7-3S-4S20二3-2S令ss 二0得0 =-1/3,S=11/3基解a=(-1/3, 11/3, 0, 0S 为非可行解；同理，以(0S)为基，基解3=(2/5, 0, 11/5, 0S 是可行解S =43/5；）为基，基解a二（-1/3, 0, 0, 11/6S 是

4、非可行解；以（a，s）为基，基解3二（0, 2, 1, 0S 是可行解，S 二T;以（SS ）为基，基解a=（0, 0, 1, 1S 是S二一3；最大值为S =43/5；最优解为3=(2/5, 0, 11/5, 0L 4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每 一步相当于图形的哪-点。曰平纯加迭代母 max z=20 +03LS+5S15060 +2a243aa0amax z=2LH+5ah+3S03S+a02S00max z=20 +2Ssa0-i-0. 50 +001230+2Sa18aa0解：(图略)(1) max z=33/4 最优解是(15/4, 3/4)单纯形

5、法：标准型是max z=204-a+os+oss. t.+5+a =1560 +2s+a=24sssao单纯形表计算:02100aabas000s15351050s2462014-z021000s3041-1/23/42a411/301/612z-801/30-1/31s3/4011/4-1/82a15/410-1/125/24-z-33/400-1/12-7/24解为:（15/4, 3/4, 0, 0SMax z=33/4迭代第一步表示原点；第二步代表C点（4, 0, 3, 0S第三步代表B点（15/4, 3/4, 0, 0S（2）解:（图略）Max z=34 此时坐标点为（2, 6）单纯形

6、法，标准型是：Max z=20 +5S +0s +0s4-0s. t.+a=42a+a 二123a+2a+a 二18Ssssa o（表略） 最优解 X= （2, 6, 2, 0, 0Max z=34迭代第一步得a二（0, 0, 4, 12, 18S表示原点，迭代第二步得3二（0, 6, 4, 0, 60,第三步迭代得到最优解的点。15以1.4题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满 足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。解：目标函数：max z=0W4-sa当0a0时a二-（0/0）0Iz/其中，k二-0a =-3/5,a=-3ka 时，同号。当0a0

7、时，目标函数在C点有最大值当00时，目标函数在原点最大值。 k时，同号。当00,目标函数在B点有最大值；当00,目标函数在原点最大值。 k 0时，同号。0时，目标函数在A点有最大值当00时，目标函数在原点最大值。 k 0时，异号。当0a0, 0时，目标函数在A点有最大值；当00, 0时，目标函数在C点最大值。 k二时，同号当0a0时，目标函数在AB线断上任一点有最大值当00,目标函数在原点最大值。 k二时，同号。当a0时，目标函数在BC线断上任一点有最大值当00时，目标函数在原点最大值。 k=0 时，=0当0a0时，目标函数在A点有最大值当0,目标函数在0C线断上任一点有最大值(2)当0=0

8、时，max z二000时，目标函数在C点有最大值0时，目标函数在0A线断上任一点有最大值 =0时，在可行域任何一点取最大值。1. 6分别用单纯形法中的大M法和两阶段法求解下列线性问题，并指出属于 哪类解。(1) max z=2+3a-5SS 4-a +a01520-5S +a 24SSa 0min z=20+3a+4+28+26990+15+12+3+9asaSSSSSmax z=100SSaa-5a0omax z=0+asa0o30a0-3Ss00解：(1)(图略)有唯一可行解,max z=14(2)(图略)有唯一可行解，min z=9/4 （3）（图略）无界解+6S +15S a 1520

9、 +a +aa 5SSa omax z=20a +2as +a +a-20+a22Saa0ssa0解：(1)解法一：大M法化为标准型：Max z=20+3S-5S-Mss. t.0 +a4-a +a =720-5S +aa +a =10sssssa0 M是任意大整数。单纯形表:023-50-M0ab00SSsS-Ms71111007-Ms102-510-115-z17M3M+23-4M2M-500-Ms207/21/211/2-1/24/72a51-5/21/20-1/21/2-z2M-100（7/2）M+80. 5M-600. 5M+1-1. 5M-13s4/7011/72/71/7-1/7

10、2a45/7106/75/7-1/71/7-z-102/700-50/7-M-16/7-1/7-M+l/7最优解是：X=（45/7, 4/7, 0, 0, 0S目标函数最优值 max z=102/7有唯一最优解。解法二： 第一阶段数学模型为min w二s. t.0 +a +a4-a =720-5S4-aa+a =10ssssss（单纯形表略）最优解X二（45/7, 4/7, 0, 0, 0S目标函数最优值min w=0第二阶段单纯形表为：023-500sabaS0a3a4/7011/71/72a45/7i06/7-1/7-z-102/700-50/7-1/7最优解是X=(45/7, 4/7,

11、0, 0, 0SMax z=102/7(2)解法一：大M法=-z 有 max=-min (-)=-min z化成标准形:Max =-2S-3Sa+0a+os-MS - MSS. T.S +4S+2Sa+a 二430+24-s=6Ssssass00（单纯性表计算略）线性规划最优解X=（4/5, 9/5, 0, 0, 0 , 0S目标函数最优值min z=7非基变量S的检验数S=0,所以有无穷多最优解。两阶段法： 第一阶段最优解烂（4/5, 9/5, 0, 0, 0, 0是基本可行解,min w=0第二阶段最优解(4/5, 9/5, 0, 0, 0, 00 min z=7非基变量a的检验数回 巾，

12、所以有无穷多最优解。(3)解:大M法加入人工变量，化成标准型：Max z=100 +15S +12S+0S+0S+0s-Mss. t. 50+3+a 二9-5h+6S +15S +a =152h+a +aa+a 二5Ssss（4）（图略）无可行解1. 2将下列线性规划问题变换成标准型，并列出初始单纯形表。（1） min z=-30+4S-2S+540a+2Sa=-24-a+3sa014-2+3a0o单纯形表计算略当所有非基变量为负数，人工变量0 =0.5,所以原问题无可行解。两阶段法（略）（4）解法一：大M法单纯形法，（表略）非基变量S的检验数大于零，此线性规划问题有无界解。两阶段法略1. 7

13、求下述线性规划问题目标函数z的上界和下界;Max z=4-其中:x_ a aaw a0S解：求z的上界Max z=3+6t. 一+2122+414ha0加入松弛变量，化成标准型，用单纯形法解的，最优解X= (0, 7/2, 5, 00目标函数上界为z=21存在非基变量检验数等于零，所以有无穷多最优解。求z的下界线性规划模型：Max Z=0+4Ss. t. 30+5Sa840+6a10ha0加入松弛变量，化成标准型，解得：最优解为X二（0, 8/5, 0, 1/5a目标函数下界是z=32/51. 8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工变 量，0aa,d,09a为待定常数

14、，试说明这些常数分别取何值时，以下结论成立。（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为0,换出变量为基b0aaaaasd4i0a0S2-1-30i-i0S30-500-4ia0a00-30解:（1）有唯一最优解时，da 0,0w 0,0w 0（2）存在无穷多最优解时，d0 0,00 0,0 二0或d00,0 =0,0a0.(3)有无界解时，d0,0,0,(4)此时，有d0并且d/4无约束(2) max解:设z0SSassa0标准型：Max =30-4a+2S-5(SS )+0s+0sa-Ms. t .-40-2+aa 4-a =2S+a+3aa 4-a+a =14-20+3Sa +2S-2Sa4-=2s ss s as a 0初始单纯形表:0a3-42-5500回ab0S0SSSass2-41-21-1000120s14113-11100014-Ms2-23-12-20-1102/304M3-6M4M-42-3M3M-55-3M0-M00(2)解：加入人工变量s s,得：Max s= (1/S)aasa0-MS 一.-MSs. t.目(i= 1,2, 3,n)a00,000,(i=l, 2, 3n; k=l, 2.，m)M是任意正整数