運籌學_第1章_線性規(guī)劃習題.doc

第一章 線性規(guī)劃習題1.1 （生產(chǎn)計劃問題）某企業(yè)利用A、B、C三種資源，在計劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品資源的消耗、單位產(chǎn)品利潤等數(shù)據(jù)如下表，問如何安排生產(chǎn)計劃使企業(yè)利潤最大？表11 產(chǎn) 品 單耗資 源甲乙資源限制ABC120111300kg400kg250kg單位產(chǎn)品利潤（元/件）50100解：設(shè)x1、x2分別代表甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量（件），z表示公司總利潤。依題意，問題可轉(zhuǎn)換成求變量x1、x2的值，使總利潤最大，即max z=50x1+100x2且稱z=50x1+100x2為目標函數(shù)。同時滿足甲、乙兩種產(chǎn)品所消耗的A、B、C三種資源的數(shù)量不能超過它們的限量，即可分別表示為 x1 + x23002x1 + x2400x2250且稱上述三式為約束條件。此外，一般實際問題都要滿足非負條件，即x10、x20。這樣有max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20工廠1工廠2200萬m3500萬m3圖11習題1.2 靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天500萬m3，在兩個工廠之間有一條流量為200萬m3的支流。兩化工廠每天排放某種有害物質(zhì)的工業(yè)污水分別為2萬m3和1.4萬m3。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有20%可以自然凈化。環(huán)保要求河流中工業(yè)污水含量不能大于0.2%。兩化工廠處理工業(yè)污水的成本分別為1000元/萬m3和800元/萬m3?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個工廠處理工業(yè)污水的總費用最小。解：設(shè)x1、x2分別代表工廠1和工廠2處理污水的數(shù)量(萬m3)。則問題的目標可描述為min z=1000x1+800x2約束條件有第一段河流（工廠1工廠2之間）環(huán)保要求 (2x1)/500 0.2%第二段河流（工廠2以下河段）環(huán)保要求0.8(2x1) +(1.4x2)/7000.2%此外有x12； x21.4化簡得到min z=1000x1+800x2x1 10.8x1 + x2 1.6x1 2x21.4x1、x20x2z*=50x1+100x2=27500x1 + x2300x1x22502x1 + x2400z1=50x1+100x2=0BOACD圖12z2=14000習題1.3 max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20用圖解法求解。解：如圖12中的B點，即問題的最優(yōu)解為x1*=50；x2*=250，相應(yīng)的最優(yōu)值為z*=27500，且該問題有唯一最優(yōu)解。111z=42z=6OA圖13習題1.4 max z=2x1+2x2x1x2 1x1 + 2x2 0x1、x2 0用圖解法求解。解：圖13中陰影部分就是該問題的可行域，顯然該問題的可行域是無界的。兩條虛線為目標函數(shù)等值線，它們對應(yīng)的目標值分別為2和4，可以看出，目標函數(shù)等值線向右移動，問題的目標值會增大。但由于可行域無界，目標函數(shù)可以增大到無窮。稱這種情況為無界解或無最優(yōu)解。習題1.5 化下列線性規(guī)劃為標準形 max z=2x1+2x24x3x1 + 3x23x3 30x1 + 2x24x380x1、x20，x3無限制解：按照上述方法處理，得該線性規(guī)劃問題的標準形為 max z=2x1+2x24x31+4x32x1 + 3x23x31 + 3x32x4 = 30x1 + 2x24x31 + 4x32 + x5 = 80x1、x2，x31，x32，x4，x5 0例1.6 用單純形法求解max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20解：首先將問題化為標準形式，然后將整個計算過程列在一個表中（表19）。 表19Cj50100000b CBXB x1 x2x3x4x5 0x311100300 0x421010400 0x501001250z501000000 0x31010-150 0x42001-1150 100x201001250z50000-10025000 50x11010-150 0x400-21150 100x201001250z00-500-5027500由于j0（j=1，5），故X*=（50，250，0，50，0）T， Z*=27500例1.7 用單純形法求解max z=2x1+x2x1 + x252x15x210x1、x20解：用單純形表實現(xiàn)如表110 表110Cj2100b CBXB x1x2x3x4 0x3-11105 0x42-5011010/4(min)z21000 0x30-3/211/210 2x11-5/201/25z060-1102=6 0，且p20，故該線性規(guī)劃有無界解（無最優(yōu)解）。例1.8 用單純形法（大M法）求解下列線性規(guī)劃 max z=3x12x2x3x12x2 + x3 114x1 + x2 + 2x3 32x1 + x3 = 1x1、x2、x30解：化為標準形式 max z=3x12x2x3x12x2 + x3 + x4 = 114x1 + x2 +2x3 x5 = 32x1 +x3 = 1x1、x2、x3 、x4、x50顯然上述標準形式的線性規(guī)劃問題沒有現(xiàn)成的初始可行基。觀察可知，需要在第二、三個約束方程中分別加入人工變量x6、x7，構(gòu)造如下線性規(guī)劃問題 max z=3x12x2x3Mx6Mx7x12x2 + x3 + x4 = 114x1 + x2 +2x3 x5 + x6 = 32x1 + x3 +x7 = 1x1、x2、x3、x4、x5、x6、x70用單純形進行計算，計算過程見表111。 表111Cj3-1-100-M-Mb CBXB x1 x2x3x4x5x6x70x41-21100011-Mx6-4120-1103-Mx7-20100011z3-6M-1+M-1+3M0-M004M0x43-20100-110-Mx60100-11-21-1x3-20100011z1-1+M00-M0-3M+1M+10x43001-22-512-1x20100-11-21-1x3-20100011z1000-1-M+1-M-123x11001/3-2/32/3-5/34-1x20100-1121-1x30012/3-4/34/3-7/39z000-1/3-1/3-M+1/3-M+2/32由于j0（j=1，7），且基變量中不含人工變量，故X*=（4，1，9）T， z*=2例1.9 用單純形法（大M法）求解下列線性規(guī)劃 max z=3x1+2x22x1+ x2 23x1 +4 x2 12x1、x20解: 化為標準形式后引入人工變量x5得到 max z=3x1+2x2Mx52x1+ x2 +x3 = 23x1 +4 x2 x4+x5 =12x1、x50用單純形法計算，過程列于表112中。從表中可以看出，雖