第一章 线性规划及单纯形法1．用X j （j=1.2…5）分别代表5中饲料的采购数，线性规划模型：12345123412341234min 0.20.70.40.30.8.3267000.50.2300.20.8100(1,2,3,4,5,6)0j z x x x x x st x x x x x x x x x x x x x x x x j =+++++++≥+++≥+++≥=≥555 +18 +2 0.5+2 2.解：设123456x x x x x x x 表示在第i 个时期初开始工作的护士人数，z 表示所需的总人数，则123456161223344556min .607060502030(1,2.3.4.5.6)0i z x x x x x x st x x x x x x x x x x x x x i =++++++≥+≥+≥+≥+≥+≥=≥ 3．解：设用i=1，2，3分别表示商品A ，B ，C ，j=1，2，3分别代表前，中，后舱，Xij 表示装于j 舱的i 种商品的数量，Z 表示总运费收入则：111213212223313233111213212223313233112131122232132333112131max 1000()700()600().6001000800105740010575400105715008652000z x x x x x x x x x st x x x x x x x x x x x x x x x x x x x x x =++++++++++≤++≤++≤++≤++≤++≤++≤ 122232132333112131122232132333122232112131132333865300086515008650.158658650.158658650.18650(1,2.3.1,2,3)ij 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 i j ++≤++≤++≤++++≤++++≤++≥== 5. （1）Z = 4（2）12121212max .6101207051038z x x st x x x x x x =++≤+≥≤≥≤≥ 解：如图：由图可得： **(10,6)16T x Z ==　；　即该问题具有唯一最优解*(10,6)Tx =（3）无可行解(4)12121212max 56.22232,0z x x st x x x x x x =+-≥-+≤≥ 如图：由图知，该问题具有无界解。

6（1）''"1234456'"12344'"123445'"123446'"'1234456max 3425500.22221436z x x x x x x x st x x x x x x x x x x x x x x x x x x x x x x x x =-+-++++-+-=+-+-=++-+=≥　-2 + -2- ，，，，，，0（2）'''"12334''"1233''"12334'"12334max 22330.46z x x x x x st x x x x x x x x x x x x x x =+-++++-=+-+=≥ 2+ ，，，，07．1）系数矩阵A ：364)120C ⎛⎫⎪- ⎪ ⎪-⎝⎭=12345612363008102 0＝（p p p p p p 30000种组合1123112368145403B P P P B ==-=-≠1 ；可构成基。

求B 的基本解，∴（B ，b ）=040⎛⎫⎛⎫⎪ ⎪- ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭123691008110＝0116/33001-7/6∴ y 1=（0，16/3，-7/6，0，0，0）T同理y 2=（0，10，0，-7，0，0）T y 3=（0， 3，0，0，7/2，0）T y 4=（7/4，-4，0，0，0，21/4）T y 5=（0，0，-5/2，8，0，0）Ty 6=（0，0，3/2，0，8，0）T y 7=（1，0，-1/2，0，0，3）T y 8=（0，0，0，3，5，0）T y 9=（5/4，0，0，-2，0，15/4）Ty 10=（0， 3，-7/6，0，0，0）T y 11=（0，0，-5/2，8，0，0）Ty 12=（0，0，-5/2，3，5，0）T y 13=（4/3，0，0，0，2，3/4）Ty 14=（0，10，0，-7，0，0）T y 15=（0， 3，0，0，7/3，0）Ty 16=（0，0，3/2，0，8，0）T基可行解：（每个x 值都大于0），（y 3，y 6，y 8，y 12，y 13，y 15，y 16） 最优解：（y 3，y 6， y 15，y 16） Z max =3[p 2 p 3 p 4]，[p 2 p 3 p 5]，[p 3 p 4 p 5]，[p 2 p 4 p 5]为奇异，∴只有16个基。

246C =8.基的定义10621350314B ==-≠ ∴X 1 X 2 X 3所对应的列向量可以构成基B 由 X 1 X 2 X 3 列向量构成 = 106213314⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦ N 由 非基变量对应的向量构成 =354120⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦（B ，b ）= 106102131314⎡⎤⎡⎤⎢⎥⎢⎥→⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦１0-13/5　４　00 37/5２0013/5 ∴B 对应的基解：（-13/5，37/5，0，0，3/5）9．解：（1）由图知：**(1,3/2)35/2;T x Z ==； 单纯形法：化为标准形如下： 12123124max 105.349528i z x x st x x x x x x =+++=++= C 10 5 0 0b C B X B X 1 X 2 X 3 X R 0 X 3 3 4 1 0 9 0 X R 5 2 0 1 8 检验数 10 5 0 0 0 0 X 3 0 14/5 1 -3/5 21/5 10 X 1 1 2/5 0 -1/5 8/5 检验数 0 1 0 -2 -16 5 X 2 0 1 5/14 -3/14 3/2 10 X 1 1 0 -1/7 3/7 0 检验数 0 0 -5/14-25/14-35/2所以：**(1,3/2)35/2;T x Z ==； 其中：(0,0)(8/5,0)(1,3/2)A B C −−−→−−−→−−−→对应T 对应T 对应T （0,0,9,8)（8/5,0,21/5,0)（1,3/2,0,0)9.2）∴A 点最大 Z= 8123412312max 200.3515224(1,2,3,4)0i z x x x x st x x x x x x x i =-++++=++==≥4 6 0点（0，0，15，24）A 点（4，0，3，0） Zmax=810.解1）要使A （0，0）成为最优解则需C ≤0且d ≤0；2）要使B （8/5，0）成为最优解则C ≥0且d=0或C>0且d<0或C/d ≥5/2且Cd>0； 3）要使C （1，3/2）成为最优解则-5/2≤-C/d ≤-3/4且Cd>0；即5/2≥C/d ≥3/4且Cd>0；4）要使D （0，9/4）成为最优解则C<0且d>0或C=0，d>011.(1)化为标准型：1231234123123max 2.36021020(1,2,3,4,5,6)0z x x x st x x x x x x x x x x x x x i =-++++=-++=+-+==≥56 **(,);T x Z ==155，0；　25（2）123456712341231323max 235.223122286164312(1,2,3...7)0i z x x x x x x x st x x x x x x x x x x x x x x x i =+++++++++=+++=++=++==≥5670000 4 **(1,3/2)33/2;T x Z ==，1，1，0，0；　（3）标准型： 12313212max 35.4212218z x x st x x x x x x x =++=+=++=45 3 **();T x Z ==2，6；　36 （4）标准型''"'"'"12344556678910'"'"144667'"123668'"'"135********'"'123445max 0.93422222264312z x x x x x x x x x x Mx Mx x st 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 =+--+-+-+---++-+-+=+-+-+=+-++-+=++= ，，，，，，"'"56678910x x x x x x ≥，，，，，，0（5）12341234123123max 62108.564420328252310(1,2,3,4)0j z x x x x st x x x x x x x x x x x x x j =++++--≤-++≤-++≤=≥44 5 4 解：标准化：12341234512361237max 62108.564420328252310(1,2,3,4,5,6,7)0j z x x x x st x x x x x x x x x x x x x x x x j =++++--+=-+++=-+++==≥44 5 4 由表可得， 70k p σ>0≤且因此问题的解无界。

（6）化为:标准形：Z ‘=-Z12314624634max .425233265(1,2,3,4,5,6)0i z xx x x st x x x x x x x x x x x x i =----=++=++==≥‘556　- + - 44017207/244722/3x x x x x x x -==⎧⎧⎪⎪-=⇒=⎨⎨⎪⎪-=-=-⎩⎩如图：1. 1. X ≥7/2 时，检验数≤0 ，∴最优解：（5，3，5，0，0）T2. 2. 1≤X<7/2时，4-4X<0,-2X+7>0C-x -1 -10 0 0 bC B X B X 1 X 2 X 3 X 4 X 5 X 6 -X X 1 1 0 1/3 -10/3 -5/3 0 20/3 -1 X 2 0 1 -1/6 5/3 -13/6 0 13/6 0X 6 00 1/61/3-5/615/6 检验数 0X/3-7/6 -10X/3+5/3 -5X/3-13/6 020X/3+13/6 **(20/313/60005/6)20/313/6;T x Z X ==+，，，，，； 3. X <-3/2时 4-4X>-2X+7>0 C-x -1-1 0 0 0 bC B X B X 1 X 2 X 3 X 4 X 5X 6 -X X 1 1 2 0 0 -6 0 11 -1 X 2 0 1/2 0 1 -3/2 1/2 3/2-1X 3 0-110 -252 检验数 02x-2 0 0-6X-2 511X+24.-3/2≤X <1； -2X+7>4-4X>0 C-x -1 -10 0 0 bC B X B X 1 X 2 X 3 X 4 X 5 X 6 -X X 1 1 0 0 -10/3 -5/3 0 20/3 -1 X 2 0 1 0 5/3 -13/6 0 13/6 -1X 6 00 11/3-5/615/6 检验数X/3-7/6 -10X/3+5/3 -5X/3-13/620X/3+13/610/35/301/25/313/6013/1010/35/35/313/6 2.3x x x x x x x -+==⎧⎧⎪⎪--=⇒=-⎨⎨⎪⎪-+=--=⎩⎩1)1/2≤X < 1 ，所有检验数 <0∴**(20/3,13/6,0,0,0,5/6)20/313/6;T x Z X ==+；　（1/2≤X< 2）-1.3≤X <1/2时 C -x -1 -1 0 0 0 bC B X B X 1 X 2 X 3 X 4 X 5X 6-X X 1 1 2 0 0 -6 00 11 0 X 4 0 3/5 -1/10 1 -13/10 00 13/10X 6 0-1/51/50 -2/5 11 2/5 检验数 02X-1 -1-6X11X1 0≤X <1/2时， 检验数<0∴**(11,0,0,13/10,0,2/5)11;T x Z X ==；　（0≤X ≤1/2） 2-1.3≤X <0时， -6X >0又 X 5列的系数< 0 ，所以解无界 3） -1.5≤X<-1.3时，同表（A ）-6X >0 ，又 X 5的列的系数<0，所以解无界（7）123123123123123max 64.221320217123z x x x st x x x x x x x x x x x x =++-++≤-+≤++≤≥≥≥ 4 ，，解：化为标准形：123101112123412351236171028113912max 64.221320217123i z x x x Mx Mx Mx st x x x x x x x x x x x x x x x x x x x x x x =++----+++=-++=+++=-+=++=++= 4 0(1,2,3...11)i ≥=即：**(/,/);T x Z ==72214，3；　47 为最优解，但该问题具有无穷多最优解（8）12335673562316367max 33.3621006(1,2,...7)0j z x x x x x x x st x x x x x x x x x x x x i =-+-+--++=+-=-+=++==≥4 解：化为标准形：123356711356231636711max 33.3621006(1,2,...)0z x x x x x x x x x x x st x x x x x x x x x x x x x x x x i =-+-+------+++=+-+=-++=+++==≥８910８4910M M M M 11**(0,2,6,0,12,0,0))4;T x Z =-=； 12．（1）解： 标准形： 112378912347138236max 22.620(1,2,3...9)0z x x x Mx Mx Mx st x x x x x x x x x x x x x x i =-+---++-+=-+-+=--+==≥59 2 2得一辅助问题：78912347138236max .620(1,2,3...9)0j w Mx Mx Mx st x x x x x x x x x x x x x x i =---++-+=-+-+=--+==≥59 2 *********56/5,16/5,8/5,0;0;(6/5,16/5,8/5,0,0,0)Tx x x x x x x x w x ==========1234789其最优解为其原问题的初始基本解可行解（2）大M 法，先化为标准形：Z ‘=-Z123141212max 400.24336z x x x x Mx Mx st x x x x x x x x x x =--++--++=++=++=‘4564536 4　- 二阶段法：引入人工变量 X 5 X 6 得原问题的一个辅助问题：141212max .24336w x x st x x x x x x x x x x =--++=++=++=564536 4　- *******52,1,5,0;0;(2,1,5,0,0,0)Tx x x x x x w x ========12346其最优解为其原问题的初始基本解可行解（3）12312312min 23.42826(1,2,3)0j z x x x st x x x x x x j =-+++≥+≥=≥ 3 标准形：'12378123471258min 23.42826(1,2,3...8)0j z x x x Mx Mx st x x x x x x x x x x j =-+---++-+=+-+==≥ 3 （6）两阶段法：78123471258max .42826(1,2,3...8)0z x x st x x x x x x x x x x j =--++-+=+-+==≥ 3 ********4/5,9/5,0;0;x x x x x x x w =======8其最优解为由表知此题为解无界； （4）123123123123max 101512.5395615155(1,2,3)0j z x x x st x x x x x x x x x x i =++++≤-++≤++≥=≥ 2 化为标准形：12371234123512367max 101512.5395615155(1,2,3...7)0z x x x Mx st x x x x x x x x x x x x x x i =++-+++=-+++=++-+==≥ 2 13．（1）100b σ≤≠ ； （2）100,0σαα≤<<12　， （3）0,0,0,0d ααα≥<<≥11216.13,5[0051]0[025]1020[01/551]50[0150]03[005]14/5x x b b a a g g f f e e ∴-⨯+⨯==⎧⎧⎪⎪-⨯+⨯=-=⎪⎪⎪⎪-⨯+⨯=⇒=-⎨⎨⎪⎪-⨯+⨯==⎪⎪-⨯+⨯=-=⎪⎪⎩⎩是基，c=0,d=117.解：由表知：（1） d=1，e=0，b=-6，f=1/3，g=0，a=7； （2）由表知所有70,σ≤所以表中给出的是最优解。