運(yùn)籌學(xué)習(xí)題及答案

1、運(yùn)籌學(xué)習(xí)題答案第一章（39頁(yè)）1.1用圖解法求解下列線性規(guī)劃問題，并指出問題是具有唯一最優(yōu)解、無(wú)窮多最 優(yōu)解、無(wú)界解還是無(wú)可行解。（1）max z =論 x25x1 +10x2 <50x1 +x2 _ 1x2 _4為，X2 _0（2）min z=x1+1.5x2x-i +3x2 _3x-i + x2 丄 2x-i， x2 亠 0（3）max z=2x1 +2 x2x-1 -x2 _-1-0.5x-i + x2 -2x-i， x2 -0（4）max z=xj + x2x-i -x2 -03Xr_X2 _3x1， x2 -0解：（1）（圖略）有唯一可行解，max z=14（2）（圖略）有唯一

2、可行解，min z=9/4（3）（圖略）無(wú)界解（4）（圖略）無(wú)可行解1.2將下列線性規(guī)劃問題變換成標(biāo)準(zhǔn)型，并列出初始單純形表。(1) min 2=-3捲+4乂2-2乂3+5乂44 Xi - X2 +2 X3 - X4 =-2x-i + x2 +3 x3 -< 14 -2 x-i +3 x2 - x3 +2 x4 亠 2x- ,X2 ,X3 _0,X4無(wú)約束n mJ 二、'aikxiki =1 k 4m為-Xk = -1( =1,n)k 4xik 丄0(i=1 n; k=1,m)(1)解：設(shè) z=-z ,X4 = X5-X6, X5,X6 _0標(biāo)準(zhǔn)型：Max z =3 x1 -4

3、x2 +2 x3 -5( x5 - x6 )+0 x7 +0 x8 -M x9-M x10s. t .-4 x1 + x2 -2 x3 + x5 - x6 + x10 =2x-i + x2 +3 x3 - x5 + x6 + x7 =14-2 x-i +3 x2 - x3 +2 x5 -2 x6 - x8 + x9 =2-0X ,X2, X3 , X5 , X6 , X7, X8 , X9 , X10初始單純形表：Cj T3-42-5500-M-MeCBXbbXX2X3X5X6X7X8X9X10-MX102-41-21-1000120X714113-11100014-MX92-23-12-20

4、-1102/3r -z4M3-6M4M-42-3M3M-55-3M0-M00(2)解：加入人工變量Xi , X2 , X3 ,Xn，得:n mMax s=(1/pk)二 二 ik xik -M x1 -M x2-.-M xn i=17s.t.mx + 遲 Xik =1(i=1,2,3,n)k=4xk 蘭0, Xj 20,(i=1,2,3n; k=1,2.,m)M是任意正整數(shù) 初始單純形表：CjM-MM如/ Pka12/ PkH rn/ Pkan1/Pkan2/ / Pkamn0iCBXbbX1X2XnX11X12X1mXn1Xn2Xnm-MX1110011000-MX210100000-MXn

5、1001000111-snM000%枷%+M陥/-+M/ 4%+M%+M7和1.3在下面的線性規(guī)劃問題中找出滿足約束條件的所有基解。指出哪些是基可行 解，并代入目標(biāo)函數(shù)，確定最優(yōu)解。(1) max z=2x4+3x2+4x3+7x42x4 +3x2 -x3-4 x4 =8X1 -2 X2 +6x3-7 X4 =-3max z=5x1 -2 x2 +3 x3 -6 x4X1, X2 ,X3 , X4 -0x1 +2 x2 +3 x3 +4 X4 =72 x1 + x2 + x3 +2 X4 =3x1 x2 x3 x4 _0(1) 解：系數(shù)矩陣A是：2 3-1*_267 一令 A=(R , P2,

6、巳,P4)P與卩2線形無(wú)關(guān)，以(R , P2)為基，捲,X2為基變量。有2 X! +3 x2 =8+ x3 +4 x4x-i -2 x2 =-3-6 x3 +7 x4令非基變量X3， X4 =0解得：捲=1; x2 =2基解X(1)=( 1, 2, 0, 0)T為可行解乙=8同理，以(P，巳)為基，基解X=(45/13, 0,-14/13, 0)T是非可行解； 以(P , R )為基，基解 X(3)=(34/5, 0, 0, 7/5)t 是可行解，Z3=117/5； 以(F2,巳)為基，基解 X=(0, 45/16, 7/16, 0)T 是可行解，Z4 =163/16； 以(P2, P4)為基

7、，基解X=(0, 68/29, 0, -7/29)T是非可行解；以(P4,巳)為基，基解X(6)=(0, 0, -68/31, -45/31 )T是非可行解；最大值為 Z3=117/5;最優(yōu)解 X=(34/5, 0, 0, 7/5)T。(2) 解：系數(shù)矩陣A是：12 3 4$112-令 A=（R , P2,巳,P4）R , P2線性無(wú)關(guān)，以(Pi , P2)為基，有: x-i +2x2=7-3 x3-4 x42 x1 + x2 =3- x3 -2 x4令 X3 , X4 =0 得x-i =-1/3, x2=11/3基解 X(1)= (-1/3,11/3, 0, 0)T 為非可行解；同理，以(P

8、 , Pj)為基，基解 X(2) = (2/5, 0, 11/5, 0)T 是可行解 Z2=43/5;以(P , R )為基，基解X=(-1/3, 0, 0, 11/6)t是非可行解；以(P2, Pj)為基，基解X=(0, 2, 1, 0)T是可行解，Z4=-1；以(P4, Pj)為基，基解 X(6)=(0, 0, 1, 1)T 是 z6=-3；最大值為Z2 =43/5;最優(yōu)解為X=(2/5, 0, 11/5, 0)T。1.4分別用圖解法和單純形法求解下列線性規(guī)劃問題，并指出單純形迭代每一步相當(dāng)于圖形的哪一點(diǎn)。（1）max z=2x1 + x23x1 +5x2 乞 156x1 +2x2 蟲24

9、x1 , x2 -0（2）max z=2x1+5 x2x<42x2 遼 12x-i ,x2 -03 x1 +2 x 18解：（圖略）（1）max z=33/4 最優(yōu)解是（15/4,3/4） 單純形法：標(biāo)準(zhǔn)型是 max z=2 為 + x2 +0 x3 +0 x4s.t. 3x! +5x2 + x3 =156捲 +2x2 + x4=24Xi , X2, X3 ,滄0單純形表計(jì)算：Cj21004CBXbbX1X2X3X40X315351050X42462014-z021000X33041-1/23/42X1411/301/612-z-801/30-1/31X23/4011/4-1/82X11

10、5/410-1/125/24-z-33/400-1/12-7/24解為：（15/4, 3/4, 0, 0 ）TMax z=33/4迭代第一步表示原點(diǎn)；第二步代表 C點(diǎn)（4, 0，3，0）T ；第三步代表B點(diǎn)（15/4，3/4，0，0 ）T。（2）解：（圖略）Max z=34 此時(shí)坐標(biāo)點(diǎn)為（2，6）單純形法，標(biāo)準(zhǔn)型是：s.t.x1 + x3 =42x2 + x4=123x-i +2x2 + X5 =18Xi , X2, X3 , X4,Xs -0俵略)最優(yōu)解 X= (2, 6, 2, 0, 0 )TMax z=34迭代第一步得X(1)= (0, 0, 4, 12, 18)t表示原點(diǎn)，迭代第二步得

11、X=(0, 6,4, 0, 6)t，第三步迭代得到最優(yōu)解的點(diǎn)。1.5以1.4題(1)為例，具體說(shuō)明當(dāng)目標(biāo)函數(shù)中變量的系數(shù)怎樣變動(dòng)時(shí)，滿足約 束條件的可行域的每一個(gè)頂點(diǎn)，都可能使得目標(biāo)函數(shù)值達(dá)到最優(yōu)。解：目標(biāo)函數(shù)： max z=C| x1 +c2 x2(1) 當(dāng) C2 =0 時(shí)x2 =- ( &/c2) x1 +z/c2其中，k=_G/c2kAB =-3/5 , kBc =-3kkBc 時(shí)，c1, 9 同號(hào)。當(dāng)C2、0時(shí)，目標(biāo)函數(shù)在C點(diǎn)有最大值當(dāng)cr 0時(shí)，目標(biāo)函數(shù)在原點(diǎn)最大值。kBC - k- kAB 時(shí)，c1, $ 同號(hào)。當(dāng)C2 0,目標(biāo)函數(shù)在B點(diǎn)有最大值；當(dāng)cr 0, 目標(biāo)函數(shù)在原

12、點(diǎn)最大值。kAB - k - 0 時(shí)，c1, c2 同號(hào)。當(dāng)c 0時(shí)，目標(biāo)函數(shù)在A點(diǎn)有最大值當(dāng)c2 0時(shí)，目標(biāo)函數(shù)在原點(diǎn)最大值。k -0時(shí)，Cl , °異號(hào)。當(dāng)C2, 0, Cl - 0時(shí)，目標(biāo)函數(shù)在A點(diǎn)有最大值；當(dāng)C2 0, Cl0時(shí)，目標(biāo)函數(shù)在C點(diǎn)最大值。k= kAB 時(shí)，q, C2 同號(hào)當(dāng)C2、0時(shí)，目標(biāo)函數(shù)在AB線斷上任一點(diǎn)有最大值當(dāng)C2 - 0,目標(biāo)函數(shù)在原點(diǎn)最大值。k= kBC 時(shí)，Cl， C2 同號(hào)。當(dāng)C2-0時(shí)，目標(biāo)函數(shù)在BC線斷上任一點(diǎn)有最大值當(dāng)C2 - 0時(shí)，目標(biāo)函數(shù)在原點(diǎn)最大值。k=0 時(shí)，Cl=0當(dāng)C2、0時(shí)，目標(biāo)函數(shù)在A點(diǎn)有最大值當(dāng)C2 0，目標(biāo)函數(shù)在OC線

13、斷上任一點(diǎn)有最大值（2）當(dāng) C2=0 時(shí)，max z= Cl xic1 -0時(shí)，目標(biāo)函數(shù)在C點(diǎn)有最大值Cl0時(shí)，目標(biāo)函數(shù)在OA線斷上任一點(diǎn)有最大值Cl=0時(shí)，在可行域任何一點(diǎn)取最大值。并指出屬于哪類1.6分別用單純形法中的大 M法和兩階段法求解下列線性問題, 解。（1）max z=2x1+3 x2-5 x3x1 + x2 + x - 152 x1-5 x2 + x< 24x1 , x2 亠0(2) min z=2 x1 +3 x2 + x3X +4 x2 +2 X3 _ 83 禺 +2 x2 - 6Xi , X , X3 - 0(3) max z=10x1+15x2+12x35 x1 +

14、3 x2 + X3 - 9-5x-i +6x2+15x3 _ 152 x1 + x2 + x 5X1 , X2, X3 -0(4) max z=2x1-x2+2 x3x-i + x2 + x3 丄 6-2 x-i + x3 亠 22x2-x3 _0X1 , X2, X3 -0解：(1)解法一：大M法化為標(biāo)準(zhǔn)型：Max z=2 x1 +3 x2-5 x3-M x4 +0x5-M x6s.t. x-i + x2 + x3 + x4=72 x-i -5 x2 + x3 - x5 + x6=10x1 ,x2, x3, x4 ,x0 M 是任意大整數(shù)。單純形表：Cj23-5-M0-M0iCBXbbx-X

15、2X3X4X5X6-MX471111007-MX6102-510-115-z17M3M+23-4M2M-50-M0-MX4207/21/211/2-1/24/72Xi51-5/21/20-1/21/2-z2M-100(7/2)M+80.5M-600.5M+1-1.5M-13X24/7011/72/71/7-1/72Xi45/7106/75/7-1/71/7-z-102/700-50/7-M-16/7-1/7-M+1/7最優(yōu)解是：X= (45/7, 4/7, 0, 0, 0 )T目標(biāo)函數(shù)最優(yōu)值max z=102/7有唯一最優(yōu)解。解法二：第一階段數(shù)學(xué)模型為 min w= x4+ x6S.t. %

16、+ x2+ x3+ x4=72 x-i -5 x2+ x3 - x5+ x6=10X!,X2,X3,X4， x5,x6 -0(單純形表略) 最優(yōu)解X=(45/7，4/7，0，0，0 )T目標(biāo)函數(shù)最優(yōu)值 min w=0 第二階段單純形表為：Cj23-50qCbXbbX1X2X3X53X24/7011/71/72X145/7106/7-1/7-z-102/700-50/7-1/7最優(yōu)解是X= (45/7, 4/7, 0, 0, 0 )TMax z=102/7(2) 解法一：大M法z =-z 有 max z =-min (- z ) =-min z化成標(biāo)準(zhǔn)形：Max z =-2 x-i-3x2-x3

17、+0x4+0 %5-M x6-M x7S.T.捲 +4 x2 +2 x3 - x4 + x6 =43 x- +2 X2 - X5 + x =6X!,X2,X3,X4 , X5,xe , X7 0(單純性表計(jì)算略)線性規(guī)劃最優(yōu)解X=(4/5, 9/5, 0, 0, 0 , 0)T目標(biāo)函數(shù)最優(yōu)值min z=7非基變量X3的檢驗(yàn)數(shù)-3=0,所以有無(wú)窮多最優(yōu)解。兩階段法：第一階段最優(yōu)解X=(4/5, 9/5, 0, 0, 0, 0 )T是基本可行解,min w=0第二階段最優(yōu)解(4/5, 9/5, 0, 0, 0, 0 )T min z=7非基變量x3的檢驗(yàn)數(shù)二3=0,所以有無(wú)窮多最優(yōu)解（3）解：大M

18、法加入人工變量，化成標(biāo)準(zhǔn)型：Max z=10 X! +15 x2+12 x3 +0 x4+0 x5 +0 x6-M x7s.t. 5 x- +3 X2 + X3 + X4=9-5 捲+6 x2 +15 x3 + x5=152x2+ x3 - x6+ x7 =5Xi, X2, X3 , X4 ,X5, X6 , X7 0單純形表計(jì)算略當(dāng)所有非基變量為負(fù)數(shù)，人工變量 x7=0.5,所以原問題無(wú)可行解兩階段法（略）（4）解法一：大M法單純形法，（表略）非基變量X4的檢驗(yàn)數(shù)大于零，此線性規(guī)劃問題有無(wú)界解兩階段法略1.7求下述線性規(guī)劃問題目標(biāo)函數(shù) z的上界和下界;Max z= g% + c2x2ax-i

19、a12x2 - bia2i X1 822X2 b2其中：1_g 3,4_g _6,8_0 _12 ,10_b2_14 , -1 _a13,2_a12_5 ,2 _ a21 _ 4 , 4 _ a22 _ 6 解：求Z的上界Max z=3 x-i +6x2s.t.-論 +2 x2 _ 122 為 +4 x2 _ 14加入松弛變量，化成標(biāo)準(zhǔn)型，用單純形法解的，最優(yōu)解X=(0, 7/2, 5, 0 )T目標(biāo)函數(shù)上界為z=21存在非基變量檢驗(yàn)數(shù)等于零，所以有無(wú)窮多最優(yōu)解 求z的下界線性規(guī)劃模型：Max Z= x-i +4 x2s.t. 3x1+5 x2 豈 84x1+6x10x2 , x0加入松弛變量

20、，化成標(biāo)準(zhǔn)型，解得:最優(yōu)解為X= （0, 8/5, 0, 1/5 ）T目標(biāo)函數(shù)下界是z=32/51.8表1-6是某求極大化線性規(guī)劃問題計(jì)算得到的單純形表。表中無(wú)人工變 量，a1，a2，a3，d，C1，02為待定常數(shù)，試說(shuō)明這些常數(shù)分別取何值時(shí)，以下 結(jié)論成立。（1）表中解為唯一最優(yōu)解；（2）表中解為最優(yōu)解，但存在無(wú)窮多最優(yōu)解；（3）該線性規(guī)劃問題具有無(wú)界解；（4）表中解非最優(yōu)，對(duì)解改進(jìn)，換入變量為為，換出變量為x6基bX1X2X3X4XX6X3d4a10a20x42-1-301-10X 3a3-500-41Cj _ZjC1C200-30解：（1） 有唯一最優(yōu)解時(shí)，dO, c0, c< 0

21、（2） 存在無(wú)窮多最優(yōu)解時(shí)，d_0, g _0, C2=0或d_0, C1 =0, C2_0.（3）有無(wú)界解時(shí)，d_0, c$0, q、0且a$0（4）此時(shí)，有 d 丄0, c< 0 并且 & _ c2, a3 > 0 , 3/a3 “ d/41.9某晝夜服務(wù)的公交線路每天個(gè)時(shí)間段內(nèi)所需司機(jī)和乘務(wù)員人數(shù)如下:班次時(shí)間所需人數(shù)16點(diǎn)到10點(diǎn)60210點(diǎn)到14點(diǎn)70314點(diǎn)到18點(diǎn)：60418點(diǎn)到22點(diǎn)50522點(diǎn)到2點(diǎn)”062點(diǎn)到6點(diǎn)30設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間區(qū)段一開始時(shí)上班，并連續(xù)上班8小時(shí)，問該公 交線路至少配備多少司機(jī)和乘務(wù)人員。列出線型規(guī)劃模型。解：設(shè)Xk （k

22、=1 , 2, 3, 4, 5, 6）為Xk個(gè)司機(jī)和乘務(wù)人員第k班次開始上班建立模型：Min z= x-i + x2 + x3 + x4 + x5 + x6s.t. x-i + x _ 60Xi + x2 亠 70x2+ x3 亠 60x3+ x4 _50x4+ x5 _20x5+ x6 _30Xl,X2,X3,x4,X5,X6-01.10某糖果公司廠用原料 A、B、C加工成三種不同牌號(hào)的糖果甲乙丙，已知各 種糖果中ABC含量，原料成本，各種原料的每月限制用量，三種牌號(hào)糖果的單 位加工費(fèi)用及售價(jià)如表所示：原料甲乙丙原料 成本（元/ 千克）每月 限制用量 （千克）A>60%>15%I

23、 22000B11.52500C<20%<60%<50%11200加工費(fèi)0.50.40.3售價(jià)3.42.852.25問該廠每月應(yīng)當(dāng)生產(chǎn)這三種牌號(hào)糖果各多少千克，使得獲利最大？建立數(shù)學(xué)模 型。解：解：設(shè)Xi，X2，X3是甲糖果中的A，B，C成分，X4，x，X6是乙糖果的A，B，C成分，X7，X8，X9是丙糖果的A，B，C成分。線性規(guī)劃模型：Max z=0.9 Xi +1.4 X2+I.9 X3 +0.45x4 +0.95 x +1.45 冷-0.05%7 +0.45 X +0.95%9s.t.-0.4x1+0.6x2+0.6x3 0-0.2 x-i -0.2 x2 +0.8x3

24、 _0-0.85 滄+0.15x5+0.15xe _0-O.6x4-O.6x5+0.4x6 _0-0.7X7-0.5x +0.5X9 豈0x1 + x4 + x? <2000x2 + x5 + x8 <2500x3+x6 + x)< 1200x7 x8 xgXi,X2,X3,X4,X5,X6,7,8 ,-01.11某廠生產(chǎn)三種產(chǎn)品I、丨【、III。每種產(chǎn)品經(jīng)過AB兩道加工程序，該廠 有兩種設(shè)備能完成A工序，他們以A,A2表示；有三種設(shè)備完成B工序，分別為，B2，B3;產(chǎn)品I可以在AB任何一種設(shè)備上加工，產(chǎn)品丨【可以在任何規(guī)格 的A設(shè)備上加工，但完成B工序時(shí)，只能在B1設(shè)備上加

25、工；產(chǎn)品III只能在A，B2上加工。已知條件如下表，要求安排最優(yōu)生產(chǎn)計(jì)劃，使該廠利潤(rùn)最大化設(shè)備產(chǎn)品設(shè)備有效臺(tái) 時(shí)滿負(fù)荷時(shí)的 設(shè)備費(fèi)用IIIIIIA5106000300A2791210000321Bi684000250B24117000783B374000200原料費(fèi)0.250.350.5單價(jià)1.252.002.8解：產(chǎn)品1,設(shè)A1, A2完成A工序的產(chǎn)品X1，X2件；B工序時(shí)，B1,B2，B3完成B工序的X3 , X4, X5件，產(chǎn)品丨【，設(shè)Ai,A2完成A工序的產(chǎn)品X6 , X7件；B工 序時(shí)，B1完成B的產(chǎn)品為X8件；產(chǎn)品111,A2完成A工序的X9件，B2完成B工序的X9件；X1 + X

26、2 = X3+ X4 + x5x7X8X6+7=8建立數(shù)學(xué)模型：Max z=(1.25-0.25)*(人 + x? )+(2-0.35)*(滄 + X7 )+(2.8-0.5) X9 -(5 洛+10 Xe )300/6000-(7 x2 +9 X7 +12 X9 )321/10000-(6 x3 +8 滄)250/4000-(4 x4 +11 X9 )783/7000-7 x5*200/4000s.t5 x1 +10 x6 三60007 X2+9 X7+12 X9 乞 100006 X3+8 X8 <40004 X4+11 X9 < 70007 x5 <4000X1 + X

27、2 = X3+ X4 + x5x7 x8X6+7=8X7 X X9“人兀皿兇必風(fēng)，,-0最優(yōu)解為 X= （1200，230，0，859，571，0，500，500，324 ）T 最優(yōu)值1147.試題：1. （2005年華南理工大學(xué)）設(shè)某種動(dòng)物每天至少需要 700克蛋白質(zhì)、30克礦物質(zhì)、100毫克維生素?，F(xiàn)有5種飼料可供選擇，每種飼料每公斤營(yíng)養(yǎng)成分的含量及單價(jià) 如下表所示：試建立既滿足動(dòng)物生長(zhǎng)需要，又使費(fèi)用最省的選用飼料方案的線性規(guī)劃模表11飼料蛋白質(zhì)（克）礦物質(zhì)（克）維生素（毫克）價(jià)格（元/公 斤）1310.50.2220.510.7310.20.20.446220.35180.50.80.8

28、解題分析：這是一道較簡(jiǎn)單的數(shù)學(xué)規(guī)劃模型問題，根據(jù)題意寫出約束即可解題過程：min z = 0.2x0.7x2 0.4x3 0.3x 0.8x53% + 2x2 + x3 +6x4 + 18x5 K 700x, +0.5x2 +0.2x3 +2x4 +0.5卷 X 30 s.t彳0.5x, +x2 +0.2x3 +2x4 +0.8x5 蘭 100X,X2,X3,x4,X5 X0第二章（67頁(yè)）2.1用改進(jìn)單純形法求解以下線性規(guī)劃問題。（1）Max z= 6x1-2 x2+3 x32 x1- x2+3 x3 二2為+4x3乞4人，X2， X3 0（2）min z=2 x1 + x23 x1 + x

29、2 =34xj+3x2 _6x-i +2x2 -3x-i, x2 -0解：（1）先化成標(biāo)準(zhǔn)型：Max z=6 x1 -2 x2 +3 x3 +0x4 +0x5 s.t. 2 x1- x2 +2 x3 + x4 =2x-i +4 x3 + x5 =4Xl,X2,X3,X4,X5_0令 Bo= ( P4 , P5)=No=(P，P2，P3)=2J-1010非基變量的檢驗(yàn)數(shù)口 _CN°CB0耳二 N0 ='-N。-=CN° =(6,-2,3)，B0=0、h2、4Xb°= ( X4,X5 )T ,CBo=(O,O)，XN0=( X!，X2，X3 )T，b0=l4

30、丿cN0 =(6,-2,3)因?yàn)閄i的檢驗(yàn)數(shù)等于6,是最大值，所以，Xi為換入變量,012、b° =I4；B 0Pi =BA0由二規(guī)則得:-=1X4為換出變量Bl =( P4 , P5)='201,Xb-= ( Xi,X5)T , Cb, =(6,0).Ni=(R,P2,P3),XNi=( X4，X2，X3)TCNi =(0 ,-2,3),Bi0.50-0.5 b,bi =非基變量的檢驗(yàn)數(shù)叫=(-3，1，-3)因?yàn)閤2的檢驗(yàn)數(shù)為1,是正的最大數(shù)。所以X2為換入變量;-0.50.5由二規(guī)則得：=6B A0 P2 =所以X5是換出變量B2=(R , P2)=-10,X B2 =

31、( x1, x2 ) , CB2 =(6,-2).n2=(F4,P5 , P3),xn2= ( X4 , x , X3 )T1Cn2=(0, 0, 3)，B2-0 1-12,b2 =I6非基變量的檢驗(yàn)數(shù)；邛2= (-2, -2,-9)非基變量的檢驗(yàn)數(shù)均為負(fù)數(shù)，愿問題已達(dá)最優(yōu)解。最優(yōu)解X=廣4、0即：X= (4,6,0)t目標(biāo)函數(shù)最優(yōu)值 max z=12（2）解：Min z=2x2+0 x3+M x4+M x5 +0x6S.T.3 捲 + x2 + x4 =34 捲+3 x2- X3 + X5 =6x-i +2 x2 + x6 =3X6 - 0M是任意大的正數(shù)。（非基變量檢驗(yàn)數(shù)計(jì)算省略）原問題最

32、優(yōu)解是X= （0.6，1.2，0）目標(biāo)函數(shù)最優(yōu)值：z=12/52.2已知某線性規(guī)劃問題，用單純形法計(jì)算得到的中間某兩步的加算表見表，試將空白處數(shù)字填上。Cj354000CBXbbX1X2X3X4X5X65X28/32/3101/3000X514/3-4/305-2/3100X620/35/304-2/301Cj-Zj-1/304-5/300.X215/418/41-10/41X3-6/415/414/41Xi-2/41-12/4115/41Cj-Zj解:Cj354000CBXbbX1X2X3X4X5X65X28/30X514/30X620/3Cj-Zj5X280/4101015/414X350

33、/41001-6/413X144/41100-2/41Cj-Zj000-45/412.3寫出下列線性規(guī)劃問題的對(duì)偶問題。(1) min z= 2 x1 +2 x2+4 x32 論+3 x2+5 x3 _23 x1 + x2 +7 x3 遼3x-i +4 x2 +6 x3 < 5Xi 必，X30(1)解：對(duì)偶問題是：Max w=2 y-i -3 y2-5 y3s.t.2yi -3 y2- y -23 yi - y2 -4 y 2 5%-7 y2-6 y3 -4yi, y2,y3 -0(2) max z= x-i +2 x2+3 x3 +4 x4-x-i + x2 - x3 -3 x4 =5

34、6 xi +7 x2 +3 x3 -5 x4 _ 812 x-i -9 x2 -9 x3 +9 x 20Xi , X2 一 0； X3 -0； X4 無(wú)約束解：對(duì)偶問題：Min w=5 y-i +8 y3 +20 y4S.t. -yi +6 y3+i2y4 -i yi+7y3-9y4 -2 -yi+3 y3-9* 乞 3 -3 yi-5 y3 +9 *=4mm n(3) min z二二二 qxjil j 4n' Xij =4i=1,mj 4m' Xij =bj j=1,ni 4Xij -0解：mn對(duì)偶冋題:max w= aiyi +送bjym岀s.t. yi'+y；卅蘭

35、q'' ''y,ym j 無(wú)約束 i=1,2,.m; j=1,2,.nnMax z=二 cjxjjmn' a/ _ b , i=1,.,g _ m j呂n- aijxj二 bi ,j三i= m11,m1 - 2,., mXj -0,當(dāng) j=1 ,.,m乩Xj無(wú)約束，當(dāng)j= n1,., n解：mMin w八 bj yi TIIs.t.m' a* - Cji ±j=1,2,3- n1、aj y； - cj j=ni+1, 口+2,.ni 4yi -0i=1,2 .mny 無(wú)約束，)=+1, E+2.m2.4判斷下列說(shuō)法是否正確，并說(shuō)明為什么

36、.(1)如線性規(guī)劃問題的原文題存在可行解，則其對(duì)偶問題也一定存在可行解。(2) 如線性規(guī)劃的對(duì)偶問題無(wú)可行解，則原問題也一定無(wú)可行解。(3) 如果線性規(guī)劃問題的原問題和對(duì)偶問題都具有可行解，則該線性規(guī)劃 問題一定有有限最優(yōu)解。(1) 錯(cuò)誤，原問題有可行解，對(duì)偶問題可能存在可行解，也可能不存在；(2) 錯(cuò)誤，對(duì)偶問題沒有可行解，原問題可能有可行解也可能有無(wú)界解；(3) 錯(cuò)誤，原問題和對(duì)偶問題都有可行解，則可能有有限最優(yōu)解也可能 有無(wú)界解；2.5設(shè)線性規(guī)劃問題1是：nMax z1 =二 Cj 為j旦，i=1，2，mxj -0, j =1,2., n(y1,., ym )是其對(duì)偶冋題的最優(yōu)解 又設(shè)線

37、性規(guī)劃問題2是nMax Z2 =' Cj Xjjmn' ajXj 蟲b + ki ， i=1，2，m j毘xj -0, j = 1,2., n其中ki是給定的常數(shù)，求證：mmax z2 _ max 乙 + ' ki yii =1解：證明：把原問題用矩陣表示：Max z-i =CX s.t. AX _bX _0b= ( D ,b2.bm )T設(shè) 可行解為Xi,對(duì)偶問題的最優(yōu)解Y1= ( yi , yym )已知。Max z2=CXs.t. AX mb+kX -0k= ( ki,k2.km )T設(shè)可行解為X2，對(duì)偶問題最優(yōu)解是丫2,對(duì)偶問題是，Min w=Y(b+k)S.t

38、. YA -CY -0因?yàn)槭亲顑?yōu)解，所以丫2 (b+k)乞丫1 (b+k)X2是目標(biāo)函數(shù)Z2的可行解，AX2乞b+k ； A%2豈丫2 (b+k)豈Yb+Yk 原問題和對(duì)偶問題的最優(yōu)函數(shù)值相等，所以不等式成立，證畢。2.6已知線性規(guī)劃問題Max z= C|X-| c2x2 c3x3Xj - 0, j _ 1，.，5用單純形法求解，得到最終單純形表如表所示，要求：(1) 求 aii，ai2，ai3， a2i， a22，a23，bi，b2的值;(2)求 Ci,C2,C3 的值;XbbXiX2X3X4X5X33/21011/2-1/2x21/210-12Cj Zj-3000-4解：(1) 初始單純形

39、表的增廣矩陣是:Ci =ai31_a2ia?300 bi1 b2最終單純形表的增廣矩陣為C2 =1 00.5 11 0.5-0.5 1.52 2C2是C1作初等變換得來(lái)的，將C2作初等變換，使得C2的第四列和第五列 的矩陣成為C2的單位矩陣。有：an=9/2；印2=1;盹=4;a21 =5/2；a22=1；a23 =2；b =9； b2=5由檢驗(yàn)計(jì)算得：C| =-3； C2 = C3 =02.7已知線性規(guī)劃問題Max z=2 x1 + x2 +5 x3 +6 x4s.t. 2x1 + x3+ x4 空 82 x1 +2 x2 + x3 +2 x - 12Xj -0, j=1,4對(duì)偶變量y1,

40、y2，其對(duì)偶問題的最優(yōu)解是y；=4, y； =1，試應(yīng)用對(duì)偶問題 的性質(zhì)，求原問題的最優(yōu)解。解：對(duì)偶問題是：Min w=8 y1 +12 y2s.t. 2y1 +2 y2 丄22y2 -1yi + y2 -5 %+2y2 - 6yi, y2 - o互補(bǔ)松弛性可知，如 卞,Y是原問題和對(duì)偶問題的可行解，那么，Y?Xs=0和YS X?=0，當(dāng)且僅當(dāng)X，Y?是最優(yōu)解。設(shè)X,Y是原問題和對(duì)偶問題的可行解，Ys=（y3，y4，y，y）有：XY S=0;且 YSX=0X5=X6=0，原問題約束條件取等號(hào)，X3=4； X4=4最優(yōu)解 X=（0, 0, 4, 4）t目標(biāo)函數(shù)最優(yōu)值為44。2.8試用對(duì)偶單純形法

41、求解下列線性規(guī)劃問題。（1）min z= x1 + x22 為 + x2 _ 4x1 +7 x2 _ 7Xi, X2 0（2）min z=3 捲 +2 x2 + x3 +4 x42 x1 +4 x2 +5 x3 + x4 - 03x1- x2 +7x3-2x4 -25x1 +2 x2 + x3+10x4 -15為，X2, X3, &-0解：（1）取w=-z，標(biāo)準(zhǔn)形式：Max w=- x-i -x2+0 x3+0 x4s.t.-2 X- - X2 + X3 =-4-X- -7 X2 + X4 =-7Xi , X2 , X3 , X4 一 U單純形法求解(略)： 最優(yōu)解：X= (21/13

42、, 10/13, U, U)T目標(biāo)函數(shù)最優(yōu)值為31/13。(2) 令：w=-z,轉(zhuǎn)化為標(biāo)準(zhǔn)形式：Max w=-3 x1 -2 x2- x3 -4 x4 +0 x5 +0x6 +0x7s.t.-2 X1 -4 X2 -5 X3 - X4 + X5 =0-3 x-i + x2 -7 x3 +2 x4 + x6 =-2-5 x-i -2 x2- x3-6 x4 + x7 =-15X1，X2， X3，X4，X5，X6，X7 .單純形法略 原問題最優(yōu)解：X=（3，0，0，0，6，7，0）T目標(biāo)函數(shù)最優(yōu)值為9。2.9現(xiàn)有線性規(guī)劃問題max z=- 5x1 +5x2 +13 x3-x-i + x2 +3 x

43、3 - 2012 x-i +4 x2 +10 x3 - 90X1， X2，X3-0先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最優(yōu)解分別有什么變化？（1）約束條件1的右端常數(shù)20變?yōu)?0(2) 約束條件2的右端常數(shù)90變?yōu)?0(3) 目標(biāo)函數(shù)中x3的系數(shù)變?yōu)?(4) xi的系數(shù)向量變?yōu)?J2丿(5) 增加一個(gè)約束條件2 Xi+3 « +5怡乞50(6) 將約束條件2變?yōu)?0+5x2+10x3空100解：把原問題化成標(biāo)準(zhǔn)型的：Max z=-5 x1 +5 x2+13 X3 +0 x4 +0 xs.t-x-i + x2 +3 x3 + xg =2012 x-i +4 x2+10 x

44、3+ xg =90%， x， X3， x4，X5 - 0單純形法解得：最優(yōu)解：X= (0，20，0，0，10)T目標(biāo)函數(shù)最優(yōu)值為100。非基變量x-i的檢驗(yàn)數(shù)等于0，原線性問題有無(wú)窮多最優(yōu)解(1) 約束條件二的右端常數(shù)變?yōu)?0有：BJ b因此b =bb單純形法解得：最優(yōu)解：X= (0，0，9，3，0)T目標(biāo)函數(shù)最優(yōu)值為117。(2) 約束條件Q右端常數(shù)變?yōu)?0有 b=B：b因此b =b 比單純形法解得，最優(yōu)解：X= (0，5，5，0，0)T目標(biāo)函數(shù)最優(yōu)值為90。(3) X3的系數(shù)變成8, X3是非基變量，檢驗(yàn)數(shù)小于0,所以最優(yōu)解不變(4) xi的系數(shù)向量變?yōu)閤i是非基變量，檢驗(yàn)數(shù)等于-5,所以

45、最優(yōu)解不變。(5) 解：加入約束條件03用對(duì)偶單純形表計(jì)算得：X= (0, 25/2, 5/2, 0, 15, 0)T目標(biāo)函數(shù)最優(yōu)值為95。(6) 改變約束條件，巳,巳,P5沒有變化, 線性規(guī)劃問題的最優(yōu)解不變。2.10已知某工廠計(jì)劃生產(chǎn)1,1111三種產(chǎn)品，各產(chǎn)品在ABC設(shè)備上加工，數(shù) 據(jù)如下表，設(shè)備代號(hào)IIIIII每月設(shè)備 有效臺(tái)時(shí)A8210300B1058400C21310420單位產(chǎn)品利潤(rùn)/千兀322.9(1)如何充分發(fā)揮設(shè)備能力，使生產(chǎn)盈利最大?(2) 如果為了增加產(chǎn)量，可借用其他工廠的設(shè)備B，每月可借用60臺(tái)時(shí)， 租金為1.8萬(wàn)元，問借用是否合算？(3) 若另有兩種新產(chǎn)品IV,V

46、,其中IV為10臺(tái)時(shí)，單位產(chǎn)品利潤(rùn)2.1千元； 新產(chǎn)品V需用設(shè)備A為4臺(tái)時(shí)，B為4臺(tái)時(shí)，C為12臺(tái)時(shí)，單位產(chǎn)品盈利1.87 千元。如A,B,C設(shè)備臺(tái)時(shí)不增加，分別回答這兩種新產(chǎn)品投產(chǎn)在經(jīng)濟(jì)上是否劃 算？(4) 對(duì)產(chǎn)品工藝重新進(jìn)行設(shè)計(jì)，改進(jìn)結(jié)構(gòu)，改進(jìn)后生產(chǎn)每件產(chǎn)品I，需要 設(shè)備A為9臺(tái)時(shí)，設(shè)備B為12臺(tái)時(shí)，設(shè)備C為4臺(tái)時(shí)，單位產(chǎn)品利潤(rùn)4.5千元， 問這對(duì)原計(jì)劃有何影響？解：(1) 設(shè)：產(chǎn)品三種產(chǎn)品的產(chǎn)量分別為，X1 , X2 , X3，建立數(shù)學(xué)模型：s.t.Max z=3 x1 +2 x2+2.9 X38x4+2x2+10x3 乞30010 x1 +5 x2 +8 x3 - 4002+13x2+

47、10x3-420Xi,X2,X3 一0把上述問題化為標(biāo)準(zhǔn)型，用單純形法解得：最優(yōu)解：X=（ 338/15, 116/5, 22/3，0，0，0）T目標(biāo)函數(shù)最優(yōu)值為2029/15。（2）0.3千兀每臺(tái)時(shí)。設(shè)備B的影子價(jià)格為4/15千元/臺(tái)時(shí)，借用設(shè)備的租金為 所以，借用B設(shè)備不合算。（3）設(shè)備V,V生產(chǎn)的產(chǎn)量為x，X8，系數(shù)向量分別為：P7 =（12,5,10）丁P8 =（4,4,12）丁檢驗(yàn)數(shù)二7 =-0.06,所以生產(chǎn) V不合算，6=37/300,生產(chǎn)V合算。單純形法計(jì)算得：最優(yōu)解：X=（ 107/4，31/2，0，0，0，0，55/4）T目標(biāo)函數(shù)最優(yōu)值為10957/80。（4）改進(jìn)后，檢驗(yàn)

48、數(shù)二1=253/300，大于零。所以，改進(jìn)技術(shù)可以帶來(lái)更好的效益。2.11分析下列參數(shù)規(guī)劃中當(dāng)t變化時(shí)最優(yōu)解的變化情況（1）Max z（t）=（3-6t）捲+（2-20 X2+（5-5t） X3 （t_0）s.t.3 X1 +2 X3 - 460x-i +2 x2 +x3 - 430x-i +4 x2 - 420xi , X2, X3 _ 0(2) Max z(t)=(7+2t) x1 +(12+t) x2 +(10-t) x3 (t 亠 0)s.t.x-i + x2 + x3- 202 x1 +2 x2 + x3 - 30Xi , x, X3 一0(3) Max Z(t) =2x1 + x2

49、 (0 t 乞25)s.t.X1- 10+2tx-i + x2 - 25-tx2- 10+2tx-i , x2 -0(4) Max z(t) =21 x-i +12x2+18 x3 +15 x4 (0 -1 - 59)s.t.6 x1 +3 x2 +6 x3 +3 & - 30+t6*3x2+12x3+6x4 - 78-t9 x1 +3 x2 -6 x3 +9 x4135-2t人,X2, X3, x4 -0解：(1)化成標(biāo)準(zhǔn)形式：Max Z(t) =(3-6t) X1 +(2-2t) x? +(5-5t) X3 +0 X4 +0 X5 +0 Xs (t - 0)s.t.3 x1 +2 x3 + x5 =460x-i +2x2 +x3 + X4 =43