第1章線性規(guī)劃與單純形法

1、一、選擇填空1.2. 3. 4. 5. 6. 7. 8. 9. 10.二、判斷正誤1.2. 3. 4. 5. 6. 7. 8. 9. 10.三、將下列問題化為標(biāo)準(zhǔn)型Max Zst2X1X1，X32為 x2 3x3 x4X2 X3 X473x2 5x380,x20,x4符號不限令X2X2，X4X4 X5，在約束1中引入非負(fù)的松弛變量X6，約束2兩邊同乘以-1。整理得:MaxZ3X3(X4X5)s.tX2 X32X1 3( X2)IIX1,X2,X3,X4,X5,X6X1(X4X5) X675x3 80即:MaxZ2x1 x2 3x3 x4X2 X3 X4 X5 X62x1 3x2 5x3 8st

2、X1,X2,X3,X4,X5,X602. Min Z=-x 1+5x 2-2x3S.tYX1 +X2 - X 3<X57j2x1 - X2 +3x 3 > 5X1 + X 2= 10X1 > 0, X2 < 0, X3符號不限解首先，令對變量X3進(jìn)行處理，令X3 = X3- X4；再令X ' 2 = - X 2。然后對目標(biāo)函數(shù)和約束條件進(jìn)行標(biāo)準(zhǔn)化。Max Z=x i+5x 2+2x 3-2x 4s.tYxi - X2 - X3+X4+X5j2x 1 + X 2 +3x 3 - 3x 4-X6 = 5=10X1 - X 2X1, X2, X3, X4, X5, X

3、6> 0四、用圖解法求解下列線性規(guī)1. min Z= - X i+2x 2S.t.YX1 - X 2 > -2X1 +2x 2 < 6X1 , X2 > 08x1根據(jù)上圖，最優(yōu)解為X*= (xi, X2)T = (6, 0 ) T，最優(yōu)值為-6。2.Max Z= - x 1+2x2s.t.YX1 - x 2> -2xi +2x 2xi, X2 > 08xi根據(jù)上圖，最優(yōu)解為X(x|,X2)T ( , 8/，最優(yōu)值為一03 33五、用單純形法求解下列線性規(guī)劃1. Max Z=3x 1+5x2s.tY12X2 < 123x1 +2x2 <18X1,

4、X2 > 0解首先，標(biāo)準(zhǔn)化后線性規(guī)劃如下:(1) Max Z=3x 1+5x 2+Ox 3+Ox 4+Ox 5X1 + x 3 = 4S.tY2X2 + x 4 = 123x1 +2x 2 + X 5 = 18X1, X2, X3, X4, X5, x6> 0再用表格單純形法求解如下:、按照第一個正檢驗數(shù)對應(yīng)非基變量進(jìn)基的方法）CbXBbXj30000jX15X20X30X40X50X34101004/10X412020100X5183200118/3-Z0350003X14101000X4120201012/20X5602-3016/2-Z-1205-3003X14101004/

5、10X460031-16/35X2301-3/201/2-Z-27009/20-5/23X12100-1/31/30X320011/3-1/35X260101/20-Z-36000-3/2-1(二、按照最大正檢驗數(shù)對應(yīng)非基變量進(jìn)基的方法)CbXBbXj0c0000j0X15X20X30X40X50X34101000X4120201012/20X5183200118/2-Z0350000X34101004/15X260101/200X56300-116/3-Z-12300-5/200X320011/3-1/35X260101/203X12100-1/31/3-Z-3600-3-3/2-1因此，最

6、優(yōu)解為X* =(2, 6, 2, 0, 0)T,最優(yōu)值為Zmax=36 。2. Max Z=2x i- X2+X33xi+X2+X3 < 60S.t.VXi-X2+2x 3 < 10X1 +X 2-X 3< 20X1, X2, X3 > 0解首先，標(biāo)準(zhǔn)化后線性規(guī)劃如下:(1) Max Z=2x 1-X2+X33Xi+X2+X 3+X4 = 60X1-X2+2x 3+X5 = 10X1 +X 2-X3 +X 6 = 20X1, X2, X3, X4, X5, X6 > 0CbXBwbXjod*1ccc0jJX1X21X3uX4uX5X60X46031110060/3

7、0X5101-1201010/10X62011-100120/1-Z02-110000X43004-51-3030/42X1101-120100X61002-30-1110/2-Z-2001-30-200X4100011-1-2再用表格單純形法求解如下:2X115101/201/2-1X251/201-3/20-1/21/2-Z-2500-3/20-3/2-1/2因此，最優(yōu)解為X* =( 15, 5, 0, 10, 0, 0)T,最優(yōu)值為Zmax =25 。六、表格單純形法計算題1. (2)初始線性規(guī)劃模型如下:Max Z=5x 1+20x 2+25x3s.t.Y2xi+x 22X2+X 33

8、x1 -1/2x 3X1, X2, X3 >(3)用單純形法求出最優(yōu)解及相應(yīng)的最優(yōu)值。解(按照最大檢驗數(shù)對應(yīng)非基變量進(jìn)基的方法)CbXbwbxj20250000j-5xi20X225X30X40X50X60X4402101000X53002101030/10X61530-1/2001-Z0520250000X44021010040/225X3300210100X63031001/2130/3-Z-7505-3000-2500X42001/301-1/325X330-2/35xi1002101011/3001/61/3-Z-8000-95/300 -155/6-5/3七、用大M法和兩階段法

9、求解下列線性規(guī)劃1. min Z= x i+2x 2S.t.N-x 1 +2x 2 > 2X1 , X2 > 0解標(biāo)準(zhǔn)化并引入人工變量X5后，線性規(guī)劃模型如下:Max Z ' =-x i-2x 2-Mx 5-X 1 +2x 2 -X3+X5 = 2s.t.Y+X4= 3xi , X2, X3, X4, x5 > 0用大M法求解如下:CbXbwbXjAcrrIV /I0jX1-JX2CX3CX4=TV1X5-MX52-12-1012/20X4310010-Z '2M-1-M-2+M-M00-2X21-1/21-1/201/20X4310010-Z '2-

10、20-101-M從表中可以看出，最優(yōu)解X* = (0, 1,0, 3 ) T,最優(yōu)值為Zmax=-2。因此，原問題最優(yōu)解X* = ( 0, 1, 0, 3 ) T，最優(yōu)值為Zmin =2 。用兩階段法求解如下: 第一階段:標(biāo)準(zhǔn)化并引入人工變量X5，對人工變量進(jìn)行優(yōu)化線性規(guī)劃模型如下:Max W=-x 5-X 1 +2x 2 -X3+X5 = 2s.tYX1+X4= 3X1, X2, X3, X4, X5 > 0CbXBbXjnnnn 40j0X10X20X3cX4X5-1X52-12-1012/20X4310010-W2-12-1000X21-1/21-1/201/20X4310010-

11、Z '00000-1由于人工變量X5=0，故可以劃去該列，以X2, X4為基變量進(jìn)行第二階段的計算。第二階段:Max Z =-x 1-2x2-1/2X 1+X 2 -1/2x 3= 1s.t.%X1+X4= 3X1, X2, X3, X4 > 0由于上表中所有非基變量的檢驗數(shù)小于等于 0，因此，原問題已經(jīng)達(dá)到最優(yōu)解,即X* = (0,1,0, 3 ) T，最優(yōu)值為Zmin =2 。2. Max Z=x i+2x2+3x3-X4xi+2x 2+3x 3 = 15S.t.V2xi+X2+5x 3 = 20X1 +2x 2+X 3+X4 = 10X1, X2, X3, X4 >

12、0解首先，標(biāo)準(zhǔn)化并引入人工變量X5, X6后，線性規(guī)劃如下:(1) Max Z=x i+2x 2+3x 3-x4-Mx5-Mx 6X1+2x 2+3x 3+X5 = 15s.tY2xi+X2+5x 3+X 6 = 20X1 +2x 2+X 3+X4 = 10Xi, X2, X3, X4 > 02/3-Z-15000-1-M-1-M從表中可以看出，最優(yōu)解 X* = (5/2, 5/2, 5/2, 0, 0, 0) T，最優(yōu)值為Zmax=15 。用兩階段法求解如下:Min W=x 5+x 60X415/73/70 10-1/715/62/76/70 01-9/74/7-W000 0 011從

13、表中可以看出，第一階段的最優(yōu)解X* = (0, 15/7, 25/7,15/7, 0, 0) T，最優(yōu)3. Max Z=3x i- X2-X3st < X1-2X2+X3 < 11< -4x i+x 2+2x 3 > 3CbXbwbXj一OO-10jX1JX2X3X42X215/7-1/71003X325/73/701025/3-1X415/76/700115/6-Z-90/76/70002X25/20101/63X35/2001-1/21X15/21007/6-Z-15000-1值為Wmin=0。轉(zhuǎn)入第二階段求解如下:-2X1 +X 3= 1X1, X2, X3 &g

14、t; 0解首先，標(biāo)準(zhǔn)化并引入人工變量X6, X7后，線性規(guī)劃如下:Max Z=3x 1-X2-X 3-Mx 6-Mx 7xi-2x 2+X 3 +x 4 = 11-4xi+x 2+2x3 -X5+X6 = 3-2x 1 +X3+X 7= 1X1, X2, X3, X4, X5, X6, X7> 0用大M法求解如下:0-1-M-Z-1-1-Z-1-1-ZX2X7X4X2X3X1X2X3-4-2-13/21/13+M12-2-1-2M0M+10-11-M-2-5-1-2-2-11-M-1-M1/3-2/32/3-5/3-1-22/3-4/34/3-7/30-1/3-1/31/3-M12/32

15、/3-M從表中可以看出，最優(yōu)解 X* = (4, 1,9, 0, 0, 0, 0 ) T，最優(yōu)值為Zmax=2 。Wmin =0。轉(zhuǎn)入第二階段求解如下:CbXbwbXj0j3X1=nX2=nX3DX4DX50X4123001-212/3-1X210100-1-1X31-20100-Z-41000-13X141001/3-2/3-1X210100-1-1X390012/3-4/3-Z-2000-1/3-1/3從表中可以看出，最優(yōu)解 X* = ( 4, 1,9, 0, 0, 0, 0)T，最優(yōu)值為Zmax=2。八、線性規(guī)劃建模1.某商店制定一種商品的712月進(jìn)貨與銷售計劃。由于商店倉庫容量的限制，

16、存貨不能超過500件。6月底已存貨100件，以后每月1日進(jìn)貨一次。假設(shè)各月份該種商品買進(jìn)及銷售單價如下表所示， 問各月應(yīng)進(jìn)貨、銷售各多少，才能是總收入最多？試列出線性規(guī)劃模型。月份7月8月9月10月11月12月買進(jìn)單價/元282425272323銷售單價/元292426282225解設(shè)7-12月份進(jìn)貨量分別為X11, X21, X31, X41, X51, X61；銷售量分別為X12, X22,X32, X42, X52, X62。則最大化目標(biāo)函數(shù)可以表示為各個月的銷售總收入與各個月進(jìn)貨總成本的差額。而約束條件包括兩方面：月初庫存量、月末庫存量約束，庫存要求介于0，500區(qū)間，因此，模型構(gòu)造如

17、下:Max Z = (29x12+24x 22+26x 32+28x 42+22x 52+25x 62)-(28x 11 +24x 21 +25x 31 +27x 41 +23x 51 +23x 61)廠 X11 W 500-100(或者 400)100+x11-X12 > 0 (或者 X12 < 100+ X 11)X21 <500- (100+x 11-X12)100+X11-X 12+X 21 -X 22 > 0500- (100+X 11-X 12+X 21 -X 22)100+X11-X 12+X 21-X 22 +X 31 -X 32 > 0500-(

18、 100+x 11-X 12+X 21-X22+X 31-X32 )100+X11-X 12+X 21 -X 22 +X 31 -X 32 +X 41 -X420500-( 100+X 11-X 12+X 21-X 22 +X 31 -X 32 +X 41 -X 42 )100+X11-X 12+X 21-X 22 +X 31-X 32+X 41 -X42+X 51 -X 52 > 0500- ( 100+X 11-X 12+X 21-X 22 +X 31 -X 32 +X 41 -X 42 +X 51 -X 52 )100+X11-X 12+X 21 -X22+X 31 -X32+X

19、41 -X42+X 51 -X52+X 61 -X62 > 0X11 , X21 , X31 , X41 , X51 , X61 , X12, X22, X32, X42, X52 , X62 > 03.某廠生產(chǎn)A、B、C三種產(chǎn)品，每種產(chǎn)品都要經(jīng)過甲、乙兩道工序。設(shè)該廠有兩種規(guī)格的設(shè)備，甲1和甲2可以完成甲工序；有3種規(guī)格的設(shè)備乙1、乙2、乙3能完成乙工序。每種設(shè)備完成每個產(chǎn)品的加工工時、 每小時的費用以及每件產(chǎn)品的原料費用和銷售價格如表1.12所示，其中空缺位置表示該設(shè)備不能加工工序設(shè)備產(chǎn)品設(shè)備有設(shè)備加工ABC效臺時費（元/小時）該種產(chǎn)品，要求安排最優(yōu)生產(chǎn)計劃，使該廠利潤最大。甲

20、甲148050000.1甲2379110000.05乙乙106230000.08乙250560000.12乙363040000.07原料費（元/件）0.30.50.8單價（元/件）1.52.54flJa解:Q fl a fl（1 ）決策變量：設(shè)A產(chǎn)品經(jīng)過甲乙兩道工序B產(chǎn)品經(jīng)過甲乙兩道工序（C產(chǎn)品經(jīng)過甲乙兩道工序（5種規(guī)格）加工的產(chǎn)品數(shù)分別為Xii,X21,X31,X41,X51 ；5種規(guī)格）加工的產(chǎn)品數(shù)分別為Xi2,X22,X32,X42,X52 ；5種規(guī)格）加工的產(chǎn)品數(shù)分別為Xi3,X23,X33,X43,X53 ；2 )目標(biāo)函數(shù)：總利潤=收益工時成本C1 材料成本 C2收益=A產(chǎn)品數(shù)X單價

21、+B產(chǎn)品數(shù)X單價+ C產(chǎn)品數(shù)X單價=1.5 (xiiX21)2.5 (x12 x22) 4 x23C1 = 0.10 (4x11 8x12) + 0.05 (3x21 7x229X23)+ 0.08 (6X32 2X33)+ 0.12 (5X41 5X43)+ 0.07 (6X51 3X52)C2 = 0.3 (x11x21)0.5 (x12x22)(3) 工時約束：4x118x1250003x217x229x23 110006x322x3330005x415x4360006x513x5240000.8 X23甲工序加工的產(chǎn)品數(shù)=乙工序加工的產(chǎn)品數(shù)(A、B、C)x11 x21x41x51x12

22、 x22x32x52x23x33x43則線性規(guī)劃模型為：4 )工序流程約束：MaxZ 0.8x11 1.2x12 1.05x21 1.65x220.48x32 0.16x33 0.6x41 0.6x434x118x1250003x217x229x23 110006x322x3330005x415x436000s.t. 6x513x524000x11x21x41x51x12x22x32x52x23x33x43X11,X21,X41,X51,X12,X22,X32,X52,X23,X33,X4302.75x230.42x51 0.21x52九、研究討論題第 1 章 常見錯誤總結(jié)：1）表格單純形法簡便易行，但卻不習(xí)慣用。雖然思路十分明確，但還是不方便。單純形表格可以求最優(yōu)解， 也可以進(jìn)行敏感性分析。 最優(yōu)表中有許多有用的 信息。(2)求解結(jié)果的表達(dá)：X *=(,，)T Zmax =? Z min =? MaX Z =?大 寫 X 表示向量（通常是列向量）（3）單純形表格不連續(xù)，自己寫上第一次迭代，第二次迭代;4）在添加人工變量時，系數(shù)矩陣中已經(jīng)有現(xiàn)成的列向量，卻不用。結(jié)果發(fā)現(xiàn)在單位陣中多出了單位列向量， 有些人的單位