運籌學課后習題答案

1、第一章線性規(guī)劃1、由圖可得：最優(yōu)解為2、用圖解法求解線性規(guī)劃:Min z=2x1+X2-x1 +4x2 <24 x1 +x2 之 85 Mxi <10x2 -0解:由圖可得：最優(yōu)解 x=1.6,y=6.41+6x22x1 -x2 >2一2x1 +3x2 <2x1 ,x2 >0解:2xi-x2=O0-1z=5x：+6x2-2由圖可得：最優(yōu)解 Max z=5x 1+6x2, Max z= + 二5xi < 15j 6xi+2x22M 24x1 +x2 M 5x1, x2 >05.maxZ = 2x1 3x2x1 +2x2 <84x1 <164x

2、2 <12xj 1,j =1,2如圖所示，maxZ在（4, 2）這一點達到最大值為2.6將線性規(guī)劃模型化成標準形式：Min z=x1-2x 2+3x3x1 +x2 +x3 <7產(chǎn)x2 +x3 >2-3x1 +x2 +2x3 = -5x1 >0, x2>0,&無約束解：令 Z' =-Z,引進松弛變量x4之0,引入剩余變量x5之0,并令 x3=x3' -x3' ，其中x3 之0,x 3' '0 0Max z' =-x i+2x2-3x 3' +3x3''x1 +x2 +x3'x3&

3、#39;'+x4 =7產(chǎn)-x2 +x3'-x3''-% =2-3x1 +x2 +2x3 = -5x1 之 0,x2 >0, x3'>0,x3''>0,x4 >0,x5 之 07將線性規(guī)劃模型化為標準形式Min Z =xi+2x2+3x3-2x1 + x2 + x3 < 9j 3x1 +x2 +2x3 >44x1 -2x2 -3x3 = -6x1 <0, x2之0,x3無約束 J解：令Z' = -z ,引進松弛變量x40,引進剩余變量x5之0,得到一下等價的標準形式。-2x1 + x2 +

4、x3 + x4 = 9_3%1 + x2 + 2x3 - 乂5 = 44x1 -2x2 -3x3 = -6X1 < 0, x2, x4, x5 >0,x2 = -x 2x3=x3 -x 3Z' = -min Z = -x 1-2x 2- 3x3-2x1-x2x3- x3x4* -3x1 -x2 +2（x3 -x3 ）x5 =4'.一一''' L_4x1 2x2 -3 x3 - x3 - -68.maxZ=3x 1 3x2 4x33x14x2 5x3 x4 =406x1 4x2 3x3 x5 =66Xj 之0, j =1,2,3,4,5Cj33

5、4000 iCBXBbx1x2x3x4x50X4403451080X5606430120bj334004x383/54/511/5040/30x54221/58/50-3/5160/7bj3/5-1/50-4/504x3204/714/35-1/73x11018/2101/75/21bj0-3/70-31/35-1/7二最優(yōu)解為(10,0,2,0,0),目標函數(shù)maxZ=389用單純形法求解線性規(guī)劃問題：Max Z =70xi+120X29xi +4x2 <360Mx1 +6x2 <2003x1 +10x2 <300解:Max Z =70xi+120X29xi +4x2 +X

6、3 =3604xi 6x2 X4 = 2003x1 10x2 x5 =300單純形表如下Cclc2cBkEbxlx2x3工4x50x3360941000k4300460100x5300310001Oj0701200x32407. 8010-0. 402022001-0. 6120x2300. 31000. 1Oj360034000-120x3169. 09001-1.60. 9970xl9. 091000. 45-0. 28120x227.27010-0. 140. 18Uj2903. 7000-14.1-1410.max Z = 4x1 3x2 2% +2x2 <3000 j5x1 +

7、2.5x2 <4000 x1 <500 x1,x2 >0解：引入松弛變量x3,x4,x5(x3,x4,x5 , 0) 2為 +2x2 +x3 =3000j 5x1 +2.5x2+x4 =4000 x1 +% =500xj 之0, j =1,2,3,4,5Cj430000 iCBXBbx1x2x3x4x50X330002210015000X4400052.50108000X550010001500Cj-Zj43000二 1 =g =4 -(0 2 0 5 0 1) =4二2 =c2 -z2 =3-(0 2+0 2.5+0 0) =3:檢驗數(shù)>0,max(cr1 ,o2)=

8、max(4,3) =4,.對應的x1為換入變量.陋，空舞】=500.x5為換出變量.(251 .Cj430000 iCBXBbx1x2x3x4x50X320000210-20X4150002.501-50X150010001Cj-Zj0000-4丁非基變量檢驗數(shù) W0,二得到最優(yōu)解：x1 =500*2 =0*3 = 2000？4 =1500,% =0, 二目標函數(shù)的 maxZ=41 =q 4 =4 (0父2+0父 5 + 0父1) = 4父 500 + 3父 0= 2000.max Z=10Xi+6X2+4%X1+X2+X3+X=100v 10 Xi+4»+5X3+X5=600、2

9、X1+2X+6X3+%=300X,X 2,X3,X 4,X5,X6>0得到初始單純形表:C1064000CBXbbXiX2X3X4X5X600X41001111001000X6001045010600X300226001150C-Zj1064000(2)其中 p1 =C1-Z1=10- (0X1+0X 10+0X2) =10,同理求得其他根據(jù)p max =max10,6,4=10,對應的X為換入變量，計算。得到，0 min =min100/1,600/10,300/2=60,X5為換出變量，進行旋轉(zhuǎn)運算。(3)重復(2)過程得到如下迭代過程C1064000CBXbbXiX2X3X4X5X

10、600X44003/51/21-1/100200/310Xi6012/51/201/1001500X618006/5501/51150C-Zj02-10-106X2200/3015/65/3-1/60200/310Xi100/3101/6-2/31/601500X100004-201150C-Zj00-8/3-10/3-2/30P j <0,迭代已得到最優(yōu)解，X*= (100/3, 200/3, 0, 0, 0, 100)Z* =10 X 100/3+6 X 200/3+4 X 0 =2200/3 。max Z=2Xi+X25X2+X3=156 6X1+2X2+ X4=24、X+2X2+

11、 X5=5X,X 2,X3,X 4,X5>0得到初始單純形表:C21000CBXbbX1X2X3X4X500X31505100-0X4246201040X55110015c-Zj21000(2)其中 pi =Ci-Zi=2- (0X1+0X10+0X2) =2,同理求得其他 根據(jù)P max =max2,1,0=2,對應的X為換入變量，計算。得到， 0 min =min-,24/6,5/1=4, X4為換出變量，進行旋轉(zhuǎn)運算。(3)重復(2)過程得到如下迭代過程C106400CBXbbX1X2X3X4X500X3150510032X1411/301/60120X5102/30-1/613/

12、2C-Zj01/30-1/300X315/20015/4-15/22X117/21001/4-1/21X23/2010-1/43/2C-Zj000-1/4-1/2P j <0,迭代已得到最優(yōu)解，X*= (7/2 , 3/2 , 0, 0, 0)Z* =2 X 7/2+3/2 =17/2 。13解：引入松弛變量 X3、X4,約束條件化成等式，將原問題進行標準化，得：Max Z=2.5Xi+Xz3X1+5X2+X3 =15* 1 + 2X2 +X 4=10X1,X2,X3,X4>0(1)確定初始可行基為單位矩陣I = P3,P4,基變量為X3,X4,X5,非基變量為X1,X2,則有:M

13、ax Z=2.5X 1+3X2X - 3=15-3X1-5X2s.t X4=10-5X1-2X2Xi >0, j=1 , 2, 3, 4Cj2.5100CBXbbXx2x3x4a0X315351050x41052012cj -zj2.5100將題求解過程列成單純形表格形式，表1由上述可得，將x1替換為X4表2,單純形迭代過程Cj2.5100CBXbb乂2乂3x400x39019/51-3/545/192.5x1212/501/55c zcjzj0000.5由表2可得，將X2替換為X3Cj2.5100CbXbbxi乂2x3x4Qd451x2219c u202.5x.19530 1w-w25

14、1 01919cj -zj0001-2表3最終單純形表一、一 ，1r 一,*2045*非基變量檢驗數(shù) 仃3=0,。4 =-萬，得到該線性規(guī)劃另一最優(yōu)解，x =(言，,0,0 ) , z =5,該線性規(guī)劃具有無窮多個解14.用單純形法求解線性規(guī)劃問題：max z = 2xi X2 5x2 <156x1+ 2x2 <24s.t.|x1x2 - 5x1 - 0, x2 - 0解:(1)將原問題轉(zhuǎn)化為標準形式，得max z = 2xi X2 0x3 0x4 0x55x2 + X3=156x1 +2x2+x4=24s.t.xix2x5 = 5xi _ 0, x2 _ 0, x3 _ 0, x

15、4 _ 0, x5 _ 0(2)建立單純性，并進行迭代運算C210000C8XbXXX3X4X50X31505100一0X4246101040X55110015C-Zj210000X3150510032X411/601/60240X5105/60-1/616/5CZ02/30-1/300X390011-62X19/51001/5-1/51Xa6/5010-1/56/5C-Zj000-1/5-4/5得到最優(yōu)解代甫,59,。,。) T, z*=4415.用單純形法求解線性規(guī)劃問題:maxz = XiX2Xi -2x2 m 2,_ 2xi + X2 < 2st.-XiX2 <4Xi _

16、0, X2 _ 0解：(i)將原問題轉(zhuǎn)化為標準形式，得maXZ = Xi X20X30x40x5Xi 2X2 + X3=2,_ 2Xi 十 X2+ x，=2st.-XiX2X5= 4Xi _ 0, X2 _ 0, X3 _ 0, X4 _ 0, X5 _ 0(2)建立單純性，并進行迭代運算C2i0000C8XbbXiX2X3X4X50X2ii2i0020X42-2i0i0-0X54-ii00i-CZii000iX2i-2i000X460-32i00X560-ii0iC-Zj03-i00本例第二個單純形表中，非基變量 X對應的檢驗數(shù)b > 0,并且對應的變量系數(shù) ai,2<0(i=i

17、 ,2, 3),根據(jù)無界解判定定理，該線性規(guī)劃問題有無界解(或無最優(yōu)解)。如果從方程角度看，第二個表格還原線性方程maxz u 3xi - X22Xi - 2x2 + X3 = 2st .<_ 3x2 十 2X3 + x，= 6-X2+x3+x5=6也即：Xi = 22X2 - X3.«X4 = 3x2 - 2X3+6X5 = x2 - x3 + 6令X3 =0,則Xi = 2 + 2X2.4 X 4 =3X2+6X5 = x 2 +6此時，若X2進基，則Xi, X4, X5會和基變量X2同時增加，同時目標函數(shù)值無限增 長，所以本題無解。16解：（1）引入松弛變量 X3, X4

18、, X5將原問題標準化，得 max Z=2Xi+4X2+0X3+0X+0X5廠 X+2X2+X3=8=X+X4=4一 X2+X5=3X,X 2,X3,X 4,X5>0(i)得到初始單純形表:C24000CBXbbXiX2X3X4X500X381210040X44i0010-0X53010013C-Zj24000(2)重復(1)過程得到如下迭代過程C106400CBXbbXiXX3X4X500X321010020X441001044X2301001-Cj-Zj2000-42X12101000X4200-1104X2301001Cj-Zj00-200因此有無窮多解，其中一個解為p5 = 0

19、, p 3 < 0 ,X1=2X2=3max Z = 1617、Maxz=3x1+5x2Max z=3x1+5x2x x1+ x3=4x1<4標準化并且引入松弛變量2x2+ x4=122x2 <12I 3x1+2x2 <18L 3x1+2x2+ x5=18x1 , x2, x3, x4, x5> 0x1 >0 x2 >0Cj35000CbXbbX1X2X3X4X500X3410100/0X4120【2】01060X518320019bj350000X34101005X260101/200X56300-11bj000-5/20非基變量oj W0,得到最優(yōu)

20、解，其中 x1=0, x2=6, x3=4.x4=0 , x5=6最優(yōu)解 Max Z=3*0+5*6=30其中，有非基變量（T 1=0,所以有無窮多個解18、解：化為標準形式：MaxZ' =-5X1-2X2-4X33X1+X2+2X3-X4=46X1+3X2+5X3-X5=10X1,x2,x3,x4,x5>=0增加人工變量x6,x7,得到：MaxZ' =-5X1-2X2-4X3-MX6-MX73X1+X2+2X3-X4+X6=46X1+3X2+5X3-X5+X7=10X1,x2,x3,x4,x5>=0大M法求解過程如下：cj-5-2-400-M-M0 iCBXBbX

21、1X2X3X4X5X6X7-MX64312-10104/3-MX7106350-1015/3cj-zj-5+9M-2+4M-4+7M-M-M00-5X14/311/32/3-1/301/30-MX720112-1-211cj-zj0-1/3+M-2/3+M-5/3+2M-M5/3-3M0-5X15/311/25/60-1/601/610/30X4101/21/21-1/2-11/22cj-zj01/21/60-5/6-M5/6-M-5X12/3101/3-11/31-1/3-2X220112-1-21cj-zj00-1/3-1-1/31-M1/3-M最優(yōu)解為 X1*=2/3,X2*=2,X3*

22、=0最優(yōu)目標函數(shù)值 minZ=22/319、解：化為標準形式：maxZ=-540x1-450x2-720x33x1+5x2+9x3-x4=709x1+5x2+3x3-x5=30X1,x2,x3,x4,x5>=0增加人工變量x6,x7,得到：maxZ=-540x1-450x2-720x3-Mx6-Mx73x1+5x2+9x3-x4+x6=709x1+5x2+3x3-x5+x7=30X1,x2,x3,x4,x5>=0大M法求解過程如下：cj-540-450-72000-M-M0 iCBXBbX1X2X3X4X5X6X7-M-MX6X770303(9)5593-100-1100170/3

23、30/9cj-zj12M-54010M-45012M-720-M-M00-M-540X6X16010/30110/35/9(8)1/3-101/3-1/910-1/31/92.510cj-zj0-150+10M/38M-540MM/3-600-M/3+60-720-540X3X115/25/6015/12(5/12)10-1/81/241/24-1/81/8-1/24-1/241/8182cj-zj01250135/2-475/12135/2-M75/2-M-720-450X3X220/32-112/501101/61/101/6-3/101/6-1/10-1/63/10-5700-360-1

24、80-4500-720075-7515-15-7575-M-1515-M最優(yōu)解為 X*=(0220/3,0,0)最優(yōu)目標函數(shù)值 minZ=570020解：先將其化成標準形式，有max z =-3 x1 +x3+0 X4 +0x5-2x1 + x2 + x3+x4=4(a)x1+ x2- x3x5=1(b)x2 +x3二9(c)這種情況可以添加兩列單位向量P6,f-1P6, P7是人為添加上去的,x5P7,連同約束條件中的向量P4構成單位矩陣它相當于在上述問題的約束條件(b)中添加變量x6,約束條件(c)中添加變量x7 ,這兩個變量相應稱為人工變量。由于約束條件(b) (c)在添加人工變量前已是

25、等式，為使這些等式得到滿足，因此在最優(yōu)解中人工變量取值必須為零。為此，令目標函數(shù)中人工變量的系數(shù)為任意大的負數(shù)，用“ -M”代表。添加人工變量后數(shù)學模型變?yōu)閙ax z = -3x+x3+0 M+0x5 - M% - Mx7x1 + x2 + x3 + x4=4-2X1 + X2- X3X5 + X6 =1X2 + X3+X7 =9得到初始可行解 X(°)= (0,0,0,4,0,1 ,9),并列出初始單純形表。在單純形法迭代運算中,可當作一個數(shù)學符號一起參加運算。檢驗數(shù)中含 M符號的，當M的系數(shù)為正時，該檢驗數(shù)為正;當M的系數(shù)為負時，該檢驗數(shù)為負。求解過程見下表c j-30100 -

26、M -MCb基 bXX 2X 3 X 4X5X6X70X441 111000-MX61-M X79-21 -10-1100310001Cj-Zj-2M-3 4M 10 -M 000X4330211-100X21-21-10-110-M X7660403-31Cj-Zj6M-30 4M+10 3M -4M00X400001-1/2-1/2-1/20X23-3X11011/30001/3102/301/2-1/21/6Cj-Zj00303/2 -M-3/2 -M+1/20X400001-1/21/2-1/20X25/2-1/2100-1/4 1/41/41X33/23/20103/4 -3/41/

27、4Cj-Zj-9/2000-3/4 -M+3/4 -M-1/4最優(yōu)解為(0, 5/2 , 3/2 )21、解：將原問題轉(zhuǎn)化為標準型Maxz=3x1+2x22x1+x2+x3=2s.t. 3x1+4x2-x4=12Xi>0, i=1,2,3,4然后添加人工變量x5,將原線性規(guī)劃問題變?yōu)镸axz=3x1+2x2-Mx52x1+x2+x3=2s.t. 4x1+4x2-x4+x5=12Xi >0, i=1,2,3,4,5取基變量為x3,x5,建立單純形表，迭代過程如下:Cj3200-M0 iCbXbBX1X2X3X4X50X32211002-MX512340-113Cj-zj3+3M2+4

28、M0-M0Cj3200-M0 iCbXbBX1X2X3X4X50X2221100-MX54-50-4-11Cj-zj3-5M0-4M-M0在單純形表中，非基變量的檢驗值都是小于0,而人工變量仍不為 0,則該線性規(guī)劃無最優(yōu)解。22、解：假設甲、乙倆種產(chǎn)品產(chǎn)量分別為x1、x2,產(chǎn)品售后的最大利潤為z,則根據(jù)題意可建立以下線性規(guī)劃模型:Max=70x1+120x29x1+4x2<360s.t. (x1+6x2<2003x1 + 10x2<300Xi >0, i=1,223 .解：設甲、乙產(chǎn)品的生產(chǎn)數(shù)量應為x1、x2,則x1、x220,設z是產(chǎn)品售后的總利潤，則maxz =70

29、x1 120x2s.t9x1 +4x2 <3604x1 +6x2 <2003x1 +10x2 <300x1,x2 之 024 .解：設甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量為x1, x2,設z為產(chǎn)品售后總'禾1J潤，則 max z=4x1+3x2s.t.'2x1 +2x2 <30005刈 +2.5x2 <4000x1 三 500x1,x2 -025.設x1、x2、x3分別為產(chǎn)品 A、B、C的產(chǎn)量，則數(shù)學模型為 max Z =10x1 14x2 12x31.5x1 +1.2x2+ 4x3 w 25003xi+1.6x2+1.2x31400150 <xi &l

30、t;250260 < x2 <310120 <x3 <130X1, x2, x3 之 026設xi，x2分別為產(chǎn)品A B的產(chǎn)量，x3為副產(chǎn)品C的銷售量，x4為副產(chǎn)品C的銷毀量, 有X3+X4 = 2x2,Z為總利潤，則數(shù)學模型為maxZ =3xi 7x2 2x3-x41 +2x2 <112xi + 3x2 <17I-2x2 X3 X4 . 0X3 <13xj -0,j =123,427.設生產(chǎn)四種產(chǎn)品分別為X1,X2,X3X4，則應滿足的目標函數(shù)為max=2X+3Xa+X+K滿足的約束條件為0 0.5X 1+3X2+X3+0.5X4W 18002X1+

31、X2+X3+ X4W28000.5X1+0.5X2+X3+X4W 18003X1+X2+2X+3X4<18001 >10002600X3>500X4> 40028.設X1=A出售的數(shù)量，X2=A在第二車間加工后的出售數(shù)量,X 3=B的出售數(shù)量，X4=B在第三車間加工后的出售數(shù)量，X 5=第一車間所用的原料數(shù)量目標函數(shù)為 maxZ=8X+9.5X2+7%+8X42.75X5滿足的約束條件為儀5< 1000003X2+2X+1.5X5 < 200000X1+X23X5=0X13+ X4 -2X5=01,X2,X3,X4>029,解：現(xiàn)在我們對本問題定義三種

32、不同形式的決策變量，從而從不同的途徑來構建模型(1)設工廠第j季度生產(chǎn)產(chǎn)品xj噸首先，考慮約束條件：第一季度末工廠需交貨20噸，故應有x1>=20;第一季度末交貨后積余(x1-20 )噸；第二季度末工廠需交貨20噸，故應有 x1-20+x2>=20 ;類似地，應有XI +X2 -40 + x3230 ；第四季度末供貨后工廠不能積壓產(chǎn)品，故應有 x1 +x2 +x3 70 + x4 =10；又考慮到工廠每個季度的生產(chǎn)能力，故應有 0Exj Eaj .其次，考慮目標函數(shù)：第一季度工廠的生產(chǎn)費用為15.0 x1,第二季度工廠生產(chǎn)的費用包括生產(chǎn)費用14x2及積壓產(chǎn)品的存貯費 0.2(2-2

33、0)；類似地，第三季度費用為15.3x3 +0.2(x1 +x2 -40),第四季度費用為 14.8m +0.2(x1 + x2 + x3 -70).工廠一年的費 用即為這四個季度費用之和.整理后，得下列線性規(guī)劃模型：min z =15.6x1 14.4x2 15.5x3 14.8x4-26s.t.x1 x2- 40x1 +x2 +x370* x1 +x2 +x3 +x4 =80、20 Mx1M30, 0Mx2 M40, 0Mx3 M 20 , 0Mx4 M 10.(2)設第j季度工廠生產(chǎn)的產(chǎn)品為 xj噸，第j季度初存貯的產(chǎn)品為yj噸(顯然，y1 = 0).因為每季度初的存貯量為上季度存貯量、

34、生產(chǎn)量之和與上季度的需求量之差，又考慮到第四季度末存貯量為零，故有：x 20 = y2,V2 +x2 -20 = y3,y3 +x3 -30 = y4 ,y4+x4=10；同時，每季度的生產(chǎn)量不能超過生產(chǎn)能力：xj <aj ；而工廠四個季度的總費用由每季的生產(chǎn)費用與存貯費用組成，于是得線性規(guī)劃：min z =15.0x1 0.2y2 14x2 0.2y3 15.3x3 0.2y4 14.8x4s.t.x1 - y2 = 20y2 +x2 - y3 =20y3 + x3 - y4 = 30yy4 +x4 =100 <Xi <300<x2 400<x3 <200

35、Mx4 M10L yj 至0 , j =2, 3, 4.(3)設第i季度生產(chǎn)而用于第j季度末交貨的產(chǎn)品數(shù)量為x j噸.根據(jù)合同要求，必須有：x11 =20,x12+x22=20,x13 * x23+ x33= 30 , x14*x24* x34 + x44= 10.又每季度生產(chǎn)而用于當季和以后各季交貨的產(chǎn)品數(shù)不可能超過該季工廠的生產(chǎn)能力, 故應有：x x1 +x2 +x3 +x4 <30 ,+ x22 + x23 + x24 40 ,、x33 +乂34 <20,x44 <10.第i季度生產(chǎn)的用于第j季度交貨的每噸產(chǎn)品的費用cij =di +0.2(j i),于劃模型：有線性規(guī)

36、min z =15.0Xii 15.2xi2 15.4xi3 15.6xi414x22 14.2x23 14.4x2415.3X33 15.5X34 14.8X44s.t.，x11 =20x12 + x22 = 20x13 + x23 + x33 = 30x14 +乂24 +乂34 +44 =10x11 +x2 +x3 +x4 <30x22 + x23 + x24 « 40x33 + x34 20 x44 - 10k xij 之0 i =1, , , 4; j =1, , , 4, j >i30,解 設xj為i #型飛機被派遣去j#工廠執(zhí)行任務的架數(shù).甲方的目標是希望事件

37、“至少摧毀一個工廠”的概率最大 廠”的概率f最小.我們有：這相當于希望事件“不摧毀任何工f = (1 一 0.10)。(1 一 0.20)x12(1 0.15)x13 (1 0.08)x21 (1 - 0.16)x22 (1 - 0.12)x23它不是線性的，為此將上式改寫為z = log f = x11 log 0.9 x12 log0.8 x13 log 0.85 x2110g 0.92 x22 1og0.84 x23 log 0.88于是，模型的目標函數(shù)為z =0.0457x11 0.0969x12 0.0704x130.0362x21 0.0656x22 0.0554x23關于燃料的約

38、束條件為：2 4502 480xii -x12222 5702 4502 480x13-x21 x222332 570323x23 100V 工i 1 j=1xj <48000經(jīng)過整理，即為550x11 580x12 670x13 400x21 420x22 480x23 < 48000.飛機數(shù)量約束：33Z x1j <40 ,工 x2j <28j 1j 1綜上所述，本問題的線性規(guī)劃模型為：max z =0.0457x110.0969x12 0.0704x13 0.0362x21 0.0656x22 0.0554x23s.t.5 550x11 +580x12 +670x

39、13 +400x21 +420x22 +480x23 <48000J x11 "*"x12 + x13 40x21 + +x23 28、xij " , i =1 , 2; j =1, 2, 3.第二章線性規(guī)劃1.對偶問題和對偶變量的經(jīng)濟意義是什么?從經(jīng)濟學的角度來說，對偶變量反映的是對應的原變量的邊際效應，即每增加一單位的原變量使目標函數(shù)變化的值，當原變量在目標函數(shù)取得最優(yōu)解時沒有用完的情況下，原變量的增加不會改變目標函數(shù)的值，此時原變量的邊際效應為0,即對偶變量為0,這就是強對偶理論。2 .簡述對偶單純形法的計算步驟。它與單純形法的異同之處是什么?計算步驟

40、見書P-42單純形法對偶單純形法原理保證原問題是可行解的情況卜向?qū)ε紗栴}可行的方向迭代保證對偶問題是可行解的情況卜.向原問題可行的方向迭代最優(yōu)解判斷看非基變量的檢驗數(shù)是否都小于等于零看對偶單純形表的B-1b是否都大于等于零迭代原則最大一最小比值原則最大：檢驗數(shù)最大的那個非基變量為換入變量；最?。築-1b/aik最小的那個對應的基變量為換出變量最小一最小比值原則最?。築-1b列數(shù)字最小(負數(shù))的那個對應的基變量為換出變量；最?。?cj-zi)/alj最小的那個對應的非基變量為換入變量3 .什么是資源的影子價格？他和相應的市場價格之間有什么區(qū)別？對偶變量yi的意義代表在資源最優(yōu)利用條件下對第i種資

41、源的估價，這是根據(jù)資源在生產(chǎn)作用中做出的貢獻而得到的估價，稱為影子價格。市場價格是指實際發(fā)生的市場交易價格，它是計量財務支出和收入的直接依據(jù)；機會成本或支付意愿就是經(jīng)濟分析中的影子價格。4 .如何根據(jù)原問題和對偶問題之間的對應關系，找出兩個問題變量之間、解及檢驗數(shù)之間的關系？(1)對偶(min型)變量的最優(yōu)解等于原問題松弛變量檢驗數(shù)的絕對值(2)對偶問題最優(yōu)解的剩余變量解值等于原問題對應變量的檢驗數(shù)的絕對值(3)由于原問題和對偶問題是相互對偶的，因此對偶問題的檢驗數(shù)與原問題的解也有類似上述關系。（4）更一般地講，不管原問題是否標準，在最優(yōu)解的單純型表中，都有原問題虛變量（松弛或剩余）的檢驗數(shù)對

42、應其對偶問題實變量 （對偶變量）的最優(yōu)解，原問題實變量（決策變量）的 檢驗數(shù)對應其對偶問題虛變量（松弛或剩余變量）的最優(yōu)解。5 .（1） min w=30yi+80y2（2） max w=30yi+80y2+50火yi+4y2 v 2 3yi+2y2>2 3yi+4y2 及4 yi,y2>0yi-y2+4y3)23yi+5y2+2y30 8.-3yi+4y2-4y3=-4yi>Oa無限制，y3<06 .解：max z' -4x=-2x2-6x3-2xi -4x2-8x3+x4=-24s.t. -4xi-x2-4x3+x5=-8為0,j=i,2,3,4,5Cj-4

43、-2-600CBXbbxiX2X3X4X50x4-24-2-4-8i00X5-8-4-i-40iq-z-4-2-6-2X26i/2ii/2-i/400X5-2-7/20-72-i/4iCj-z-30-5-i/20-4Xi4/7i0ii/i4-Z7-2X240/70i0-Z7i/7Cj-z00-2-Z7-67所以：x*=(4/7,40/7,0,0,0), z*=96 /7.7 .max z=xi+2x2+3x3+4x4xi+2x2+2x3+3x4+x5=20 2xi+x2+3x3+2x4+x6=20 xj>0,j=i,2,3,4,5,6對偶問題：min w=20yi+20y2yi+2y2 o 1yi+y2-y3=l2yi+y2> 22yi+y2-y4=22yi+3y2>32yi+3y2-y5=33yi+2y2>43yi+2y2-y6=4yi,y2>0已知對偶問題最優(yōu)解為：.Y*XS=(yi ,y2)(x5,x6)T=0yi>0,i=i,.,6yi*=6/5,y2*=i/5.代入,得：y3=35,y4=35,y5=