運籌學復習題及 答案

1、運籌學復習題及答案一、一個毛紡廠用羊毛和滌綸生產(chǎn)A、B、C混紡毛料，生產(chǎn)1單位A、B、C分別需要羊毛和滌綸3、 2； 1、 1； 4、4單位，三種產(chǎn)品的單位利潤分別為4、1、5。每月購進的原料限額羊毛為8000單位，滌綸為3000單位，問此毛紡廠如何安排生產(chǎn)能獲得最大利潤？（要求：建立該問題的數(shù)學模型）解：設 生產(chǎn)混紡毛料ABC各x1、x2、x3單位max zx1+x2+5x33x1+x2+4x380002x1+x2+4x33000x1,x2,x30二、寫出下述線性規(guī)劃問題的對偶問題max s=2x1+3x2-5x3+x4x1+x2-3x3+x452x1 +2x3-x44x2 +x3+x4=6

2、 x1,x2,x30；x4無約束解：先將原問題標準化為：max s=2x1+3x2-5x3+x4-x1-x2+3x3-x4-52x1 +2x3-x44x2 +x3+x4=6x1,x2,x30；x4無約束則對偶問題為：min z=-5y1+4y2+6y3-y1+2y22-y1+ y233y1+ 2y2+y3-5-y1-y2+y3=1y1,y20,y3無約束三、求下述線性規(guī)劃問題min S =2x13x25x3x1x23x3 52x1 2x3 4 x1，x2，x30解：引入松弛變量x4，x5，原問題化為標準型：max Z=-S =-2x1-3x2+5x3x1x23x3 x4=52x1 2x3 +x

3、5=4 x1，x2，x3, x4,x50對應基B0（P2,P5）的單純形表為T(B0)=51 1 -3 -1 042 0 2 0 1151 0 -4 -3 0x1的檢驗數(shù)為正，x1進基，由min5/1,4/2=4/2知，x5出基，迭代得新基B1=(P2,P1),對應的單純形表為T(B1)=30 1 -4 -1 -1/221 0 1 0 1/2130 0 -5 -3 -1/2至此，檢驗數(shù)全為非正，已為最優(yōu)單純形表。對應的最優(yōu)解為：x1=2,x2=3,x3=x4=x5=0,max z=-13,故原問題的最優(yōu)解為：x1=2,x2=3,x3 =0,min s=13。四、利用大M法求解下面線性規(guī)劃問題:

4、 解：引入松弛變量x4和人工變量x5，構造如下規(guī)劃：對應基B0（P4,P5）的單純形表為T(B0)=42 1 1 1 061 2 0 0 16M-1+M 2+2M 1 0 0x1的檢驗數(shù)為-1+ M0，x1進基，由min6/1=6/1知，x5出基，迭代得新基B1=(P4,P1),對應的單純形表為T(B1)=160 5 1 1 261 2 0 0 160 4 1 0 1-Mx3的檢驗數(shù)為10，x3進基，由min16/1=16/1知，x4出基，迭代得新基B2=(P3,P1),對應的單純形表為T(B2)=160 5 1 1 261 2 0 0 1-100 -1 0 -1 -1-M至此，檢驗數(shù)全為非正

5、，已為最優(yōu)單純形表。對應的最優(yōu)解為：x1=6,x2=0,x3=16,x4=x5=0,最優(yōu)值max z=10。五、已知線性規(guī)劃問題(L):(1) 寫出該問題的對偶表,從而給出其對偶問題(D).(2)用對偶單純形法求解問題.解：(1)該問題的對偶表,x1x2x3MinMax其對偶問題(D)為max Z=6y1+8y22y1+ y21 y1+3y222y1+2y23 y1,y20123cb2126y11328y2(2)用對偶單純形法求解問題. 引入松弛變量x4、x5，構造如下規(guī)劃：對應基B0（P4,P5）的單純形表為T(B0)=6-2 -1 -2 1 08-1 -3 -2 0 10-1 -2 -3

6、0 0檢驗數(shù)全為非正，基變量x46，x4出基,利用偶單純形法，由min1/2，2/-1,-3/-2=1/2知，x1進基，迭代得新基B1=(P1,P5),對應的單純形表為T(B1)=31 1/2 1 -1/2 050 -5/2 -1 -1/2 130 -3/2 -2 -1/2 0基變量x55，x5出基,利用偶單純形法知，x2進基，迭代得新基B2=(P1,P2),對應的單純形表為T(B2)=21 0 4/5 -3/5 1/520 1 2/5 1/5 -2/560 0 -7/5 -1/5 -3/5至此,得到最優(yōu)解:x1=x2=2,x3=x4=x5=0,最優(yōu)值maxZ=-6,故原問題的最優(yōu)解為: x1

7、=x2=2,x3=0, 最優(yōu)值minS=6.六、某運輸問題的產(chǎn)銷平衡表和運價表如下，試用表上作業(yè)法求最優(yōu)調運方案。 銷地產(chǎn)地B1B2B3產(chǎn)量A1A2A310324162571211銷量10101030解：由最小元素法得初始運輸方案B1B2B3產(chǎn)量A1A2A3101072171211銷量10101030總運費S=010110672251=61經(jīng)計算11（60）（21）30,調整量=min（7,10）7，經(jīng)調整，得新運輸方案：B1B2B3產(chǎn)量A1A2A37310 9171211銷量10101030總運費S=613740至此，所有檢驗數(shù)均以非正，該運輸方案已為最優(yōu)。即：A1運到B1 7個單位；A2運

8、到B1 3個單位；A2運到B3 9個單位A3運到B2 10個單位；A3運到B3 1個單位；總運費S40個單位七、某極大化整數(shù)規(guī)劃對應的線性規(guī)劃的最優(yōu)單純形表如下：5/20 1 1/2 -1/213/41 0 -1/4 3/4-69/40 0 -3/4 -3/4試建立割平面方程并求原整數(shù)規(guī)劃的最優(yōu)解。解：由x2=5/2為非整數(shù)，對應方程為：5/2=x2+1/2x3-1/2x4即：x2x4-2=1/2-(1/2x3+1/2x4),得Gomery割平面：1/2-(1/2x3+1/2x4)0引入松弛變量x5,添加約束： -1/2x3-1/2x4 x5=1/2,由表5/20 1 1/2 -1/2 013

9、/41 0 -1/4 3/4 0-1/20 0 -1/2 -1/2 1-69/40 0 -3/4 -3/4 0利用對偶單純形法迭代得到新單純形表：20 1 0 -1 17/21 0 0 1 -1/210 0 1 1 -2-33/20 0 0 0 -3/2由7/2=x1+x4-1/2x5,得Gomery割平面：1/2-1/2x5+0-2/3 1/384/3故最優(yōu)基不變，最優(yōu)解改變?yōu)椋簒14/3,x2=10/3,對應的最優(yōu)值為16/3。（4）設c2的攝動量為，最優(yōu)基不變。此時，C=(-1,2+,0,0),CB=(2+,-1),由C -CBB-1A0,得4010因此1，即c22+1，故當c2在1,+

10、)變化時,最優(yōu)基不變,生產(chǎn)計劃不變.九、某物資的產(chǎn)銷平衡表及運價表如下，求總運費最省的調運方案。 平衡表運價表(百元/噸) 銷地產(chǎn)地B1 B2 B3 B4產(chǎn)量(噸)B1 B2 B3 B4A1A2A33572 5 9 81 9 2 67 5 4 3銷量(噸)6 3 2 415解:利用最小元素法得到初始可行解(運輸方案) 銷地產(chǎn)地B1 B2 B3 B4產(chǎn)量(噸)A1A2A31 25 1 2 4357銷量(噸)6 3 2 415對應的總運費s0=12+2551152443=42(百元)利用位勢法計算檢驗數(shù)ij=cij-(ui+vj),如下: B1 B2 B3 B4uiA1A2A3 5 5 5 -1

11、450-10vj2 5 4 3檢驗數(shù)23=c23-(u2+v3)=2-(4-1)=-1,表中不是最優(yōu)運輸方案,需調整,調整量為=min=2,2,5=2,新運輸方案為: 銷地產(chǎn)地B1 B2 B3 B4產(chǎn)量(噸)A1A2A33 03 2 3 4357銷量(噸)6 3 2 415對應的總運費s1=32+0531352243=40(百元)或s1=s0+23=42-12=40(百元)利用位勢法計算檢驗數(shù)ij=cij-(ui+vj),如下: B1 B2 B3 B4uiA1A2A3 5 5 5 45 20-10vj2 5 3 3此時,檢驗數(shù)全為非負, 表中已是最優(yōu)運輸方案, 總運費為40百元.十、利用割平面法,求下面問題:解：引入松弛變量x3，x4，構造輔助LP：對應基B0（P3P4）的單純形表T(B0)=61 1 1 031 4 0 102 1 0 0迭代得到新基B1（P3P1）,對應的單純形表為：T(B1)=30 5 1 131 4 0 160 9 0 2迭代得到新基B2（P2P1）,對應的單純形表為：T(B2)=3/50 1 1/5 1/527/51 0 4/5 1/557/50 0 -9/5 1/5檢驗數(shù)已經(jīng)全為非正，得到輔助LP的最優(yōu)單純形表，由于解不是整數(shù)，所以不是原整數(shù)規(guī)劃問題的解.對應第二個方程的Gomery割平面：2/5（4/5x31/5x5）0引入松弛變量x5,添加約