习题参考答案习题一1．设选用第1种、第2种、第3种、第4种、第5种饲料的量分别为12345,,,,x x x x x 。

Min 543218.03.07.04.02.0x x x x x Z ++++=12345123451234512345326187000.50.220.530..0.50.220.8100,,,,0x x x x x x x x x x s t x x x x x x x x x x ++++≥⎧⎪++++≥⎪⎨++++≥⎪⎪≥⎩2．设x ij 为生产第i 种食品所使用的第j 种原料数，i ＝1，2，3分别代表甲、乙、丙，j ＝1，2，3分别代表A 、B 、C 。

其数学模型为：Max Z =)(0.1)(5.1)(2)(95.1)(45.2)(9.2332313322212312111333231232221131211x x x x x x x x x x x x x x x x x x ++⨯-++⨯-++⨯-++⨯+++⨯+++⨯s.t. )3,2,1,3,2,1(,05.06.015.02.06.01200250020003332313323222123232221211312111313121111332313322212312111==≥≤++≤++≥++≤++≥++≤++≤++≤++j i x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ij3．将下列线性规划问题化为标准形式（1）引入剩余变量1s ，松弛变量2sMax 32142x x x Z ++=123112321231231225623215..327,,0,,0x x x s x x x s s t x x x x x x s s +--=⎧⎪+++=⎪⎨--+=⎪⎪≥≥⎩ （2）令'22x x =-，'''333x x x =-，引入松弛变量1sMax 33217785x x x x Z ''-'+'--= ⎪⎩⎪⎨⎧≥''''=''-'+'+=+''+'-'-0,,,,152245106..13321332113321s x x x x x x x x s x x x x t s4.（1）唯一最优解 1x =1.7143，2x ＝2.1429，Max Z =9.8571；（2）无可行解； （3）无界解；（4）无可行解；（5）多重最优解，Max Z=66，其中一个解为1x =4，2x ＝6； （6）唯一最优解，为1x =6.6667，2x ＝2.6667，Max Z =30.6667。

5．可行解：(A), (C), (E), (F) ；基本解：(A), (B), (F) ；基本可行解：(A), (F)6.（1）标准型为：Max 2195x x Z +=⎪⎪⎩⎪⎪⎨⎧≥=-+=++=++0,,,,65.01085.0..32121321221121s s s x x s x x s x x s x x t s （2）至少有2个变量的值取零，因为有3个基本变量、2个非基本变量，非基本变量的取值为零。

（3）在这个线性规划问题中，共有10种基本解。

（4）最优解X =（4，6，0，0，1）T，Max Z=74。

7．单纯形法求解下列线性规划问题（1）（2）8．（1）a=7，b=-6，c=0，d=1，e=0，f=1/3，g=0； （2）表中给出最优解X *＝（0 0 7 0 5 0）T。

9．用大M 法求解结果：（1）无可行解；（2）最优解X *=（4 4）T，最优值为28； （3）有无界解；（4）最优解为X *=（4，0，0）T，最优值为8。

习题二1.（1）原问题的对偶问题为212010y y MinW +=s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧，11112y y y y 2y +++04222≥y y y 2110≥≥≥（2）原问题的对偶问题为321253y y y MaxW +-=s.t.⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧-1111432y y y y 1y +++，043222≤y y y 2y ---+，047323333≥y y y y 无约束34323y ≥-==≤（3）原问题的对偶问题为32152015y y y MaxW -+=s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧--11135y y y 1y +--，01065222≥y y y 2y --+，0333≤y y y 无约束3765y -=-≤-≥2．由教材表3-4与表3-5的对应关系，如图可知B=（x 4，x 1，x 2）列，B 1-=（x 4，x 5，x 6）列,故B= ⎝⎛001，，，113，，，⎪⎪⎪⎪⎭⎫-111，B -1=⎝⎛001，，，2/12/11--，，，⎪⎪⎪⎪⎭⎫-2/12/12因最终单纯形表中非基变量的系数为B 1-N ，所以，(x 1*，x 2*，x 3*，b *)=B1-（N ，b ）=B -1(x 1，x 2，x 3，b)=⎝⎛001，，，2/12/11--，，，⎪⎪⎪⎪⎭⎫-2/12/12 ⎝⎛113，，，111-，，，121-，，，⎪⎪⎪⎪⎭⎫201060=⎝⎛010，，，100，，，2/32/11-，，，⎪⎪⎪⎪⎭⎫51510检验数j C =c j -C B P j =(0,0,-3/2,0,-3/2,-1/2)3．原问题的对偶问题为2134y y MaxZ += s.t.⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧≥≥≤+≤+≤+≤-≤+0,0332532322212121212121y y y y y y y y y y y y由松弛互补性质可知，在最优性条件下，*j v *j x =0和*i y *i u =0，这里*i u （i=1,2），*j v （j=1,2,3,4,5）分别为原问题的剩余变量及对偶问题的松弛变量。

由*1y =4/5>0,*2y =3/5>0,利用互补松弛定理*1y *1u =*2y *2u =0，得到*1u =*2u =0,即原问题的两个约束条件为等式约束条件。

将*1y =4/5,*2y =3/5代入对偶问题的约束条件，得到（2）式y 1*-y 2*=1/5<3，（3）式2y 1*+3y 2*=17/5<5，（4）式y 1*+y 2*=7/5<2，（2）、（3）、（4）三式为严格不等式，所以*2v >0，*3v >0，*4v >0，再利用一次互补松弛定理*2v *2x =*3v *3x =*4v *4x =0，得到*2x =*3x =*4x =0。

根据上述结果，原约束可以转化成二元一次线性方程组：⎪⎩⎪⎨⎧=+=+****32435151x x x x 解方程组得x 1*=x 5*=1综上所得，原问题的最优解为X *=(1,0,0,0,1)，相应的目标函数最优值为*Z =*W =5。

4.（1）将原问题化为标准形式为321432x x x MaxW ---=s.t.⎪⎪⎩⎪⎪⎨⎧=≥-=+-+--=+---5,2,1,04323253214321 i x x x x x x x x x i建立这个问题的单纯形表并运算，具体见下表：表中b 列数字全为非负，检验数全为非正，故问题的最优解为*X =(11/5,2/5,0,0,0)若对应两个约束条件的对偶变量分别为y 1和y 2，则对偶问题的最优解为*Y =(8/5,1/5,0,0,9/5)（2）将原问题化为标准形式为：32123x x x MaxW ---=s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥-=++--=++-=+++62103466325314321，，，， i x x x x x x x x x x x i建立这个问题的单纯形表并计算，过程见下表:由上述表格可以看出基变量x 4行系数全为正，而其限定向量b 却存在负值，在x i ≥0,i=621，，， 的情况下不可能成立，故此题无解。

原问题的对偶规划如下：321346y y y Z Max ++='s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧1111y y y y ，0≤-+，222y y y 3y -+033≥y y 123≤≤≤显然，（0，0，0）为该对偶问题的可行解，则对偶问题为无界解。

5.（1）线性规划原问题的最优解X *=（0，0，8，0，6）T最优值*Z =b B C B 1-=（12，0）⨯⎪⎪⎭⎫⎝⎛68=96最优基B=⎝⎛33，，⎪⎪⎭⎫10 逆B -1=⎝⎛-13/1，，⎪⎪⎭⎫10 （2）原问题的对偶问题为：213024y y MinW +=s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥+≥+≥+0,123326624321212121y y y y y y y y y ，对偶问题的最优解Y *=（4，0，10，2，0）。

（3）若最优解不变，c 3变化Δc 3，则变化后的最终单纯形表为：由上表可以看出，在最优解不变的情况下，需满足下列不等式：⎪⎪⎩⎪⎪⎨⎧≤∆--≤∆--≤∆--03/1403/1203/410333c c c ⇒⎪⎪⎩⎪⎪⎨⎧-≥∆-≥∆-≥∆1262/15333c c c 得到3c ∆6-≥ 因此c 3=12+3c ∆≥6。

（4）由最终单纯形表可知1-B =⎪⎪⎭⎫ ⎝⎛-1,10,3/1，而b ∆=⎪⎭⎫ ⎝⎛∆20b ， 易见1-B b+1-Bb ∆=⎪⎪⎭⎫ ⎝⎛68+⎪⎭⎫ ⎝⎛∆20b =⎪⎭⎫ ⎝⎛∆+268b 。

因最优基变量不变,知6+2b ∆0≥,故2b ∆≥-6,而b 2*=b 2+2b ∆=30+2b ∆≥24，因此，当b 2*≥24时最优基变量不变。

（5）在原线性规划的约束条件上，增加下面的约束条件x 1+2x 2+2x 312≤,原问题变为：3211226x x x MaxZ ++=s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤++≤++≤++3,2,1,01222303622434321321321j x x x x x x x x x x j原最终单纯形表新增一行和一列，见表。

此时原最终单纯形表中的x 3和x 5的系数不再是单位向量了，所以继续进行行变换，保持原基变量不变。

在行变换后得到的新单纯形表中，检验数均小于等于零，但右端项出现负值，所以可用对偶单纯形法继续运算。

最后得最优解X *=(12/5,0,24/5,0,54/5,0)T，最优值Z *=72。

6.（1）设y 的系数增加了∆y ，变化后的最优单纯形表为：因为保持最优生产计划不改变，所以，需满足下列不等式：⎪⎩⎪⎨⎧≤∆+-≤∆--02/1104/32/1y y ⇒⎪⎩⎪⎨⎧≤∆-≥∆23/2y y ， 故2≥∆y 3/2-≥，所以，y 的系数的变化范围为∆y+2=（4/3，4）。