補充線性規(guī)劃問習題練習題解答

1、補充線性規(guī)劃問題習題及解答1某銅廠軋制的薄銅板每卷寬度為100cm，現(xiàn)在要在寬度上進行切割以完成下列訂貨任務(wù)：24cm寬的75卷，40cm寬的50卷和32cm寬的110卷，長度是一樣的，試將這個要解決的切割方案問題列成線性規(guī)劃模型，使切余的邊料最少。答：有下面八種切法方案出品數(shù)（卷）規(guī)格一二三四五六七八需要數(shù)量（卷）24cm40cm32cm4000200031111022102010117550110余料4204412122028設(shè)x1，x2，x3，x4，x5，x6 ，x7，x8分別表示八種下料方案切割的銅卷數(shù)，求解x1，x2，x3，x4，x5，x6，x7，x8使?jié)M足條件：并使余料總數(shù)：Z=

2、4x1+20x2+4x3+4x4+12x5+12x6 +20x7 +28x8 取得最小值。近似最優(yōu)解x1=25/4,x3=20,x4=50 其他為0，最優(yōu)值z*=305。（不是整數(shù)解）2某養(yǎng)雞場養(yǎng)雞10000只，用大豆和谷物飼料混合喂養(yǎng)，每天每只平均吃混合飼料，其中應(yīng)至少含有蛋白質(zhì)和鈣。已知大豆中含50%蛋白質(zhì)和%的鈣，價格是元/kg，谷物中含有10%的蛋白質(zhì)和%的鈣，價格是元/kg，糧食部門每周只保證供應(yīng)谷物飼料25000kg，大豆供應(yīng)量不限，問應(yīng)如何搭配兩種飼料，才能使喂養(yǎng)成本最低，建立該問題的數(shù)學模型。50%x1 +10%x2×7×10000=7000 蛋白質(zhì)%x1+

3、%x2×7×10000=140 鈣 x1 +x2×7×10000=35000 總量 x225000 谷物限量x10,x20min z=x1+解：設(shè)每周用大豆x1公斤，谷物x2公斤,數(shù)學模型為 圖解最優(yōu)解x1= , x2=,最小值z*=。3一家晝夜服務(wù)的飯店，24小時內(nèi)需要服務(wù)員的人數(shù)如下每個服務(wù)員每天連續(xù)工作8小時，且在表中時段開始上班，試求要求滿足以上要求的最少上班人數(shù)，建立該問題的數(shù)學模型。解：設(shè)在j鐘點上班的人數(shù)為xj(j=1,2,6)，上班之后連續(xù)工作8小時，下班離開，每班中間不允許交接班離開。故有4人8人10人7人12人4人 26時 x1610

4、時 x21014時 x31418時 x41822時 x5222時 x6據(jù)題意有26時 x1 +x6 4 610時 x1+x2+ 81014時 x2+x3 101418時 x3+x4 71822時 x4+x5 12222時 x5+x6 4 min z=x1+x2+x3+x4+x5+x6最優(yōu)解x1=4 , x2=10 , x4=8 , x5=4 , 其他xj=0, 最優(yōu)值min z=26（人）4設(shè)有四個投資機會：甲：在三年內(nèi)，投資人應(yīng)在每年年初投資，每年每元可獲利息元，每年取息后可重新將本息投入生息。乙：在三年內(nèi)，投資人應(yīng)在第一年年初投資，每兩年每元可獲得利息元，兩年后取息，可重新將本息投入生息。

5、丙：在三年內(nèi)，投資人應(yīng)在第二年年初投資，兩年后每元可獲得利息元，這種投資最多不得超過15000元。?。和顿Y人應(yīng)在第三年年初投資，一年內(nèi)每元投資可獲利息元，這種投資不得超過10000元。假定在這三年為期的投資中，開始時有30000元可供投資，投資人應(yīng)怎樣決定投資，才能在第三年底獲得最高的收益，試建立其數(shù)學模型。解：設(shè)xij為第i年初投放到j(luò)項目的資金數(shù)，其數(shù)學模型為：max z=+x11+x1230000x21+x23x31+x34+x2315000x3410000xij0 ,(i=1,2,3 ,j=1,2,3,4)最優(yōu)解x11=12500, x12=17500, x23=15000, x31=

6、16250, x34=10000,其他為0；最優(yōu)值z*=575005某一求目標函數(shù)最大值的線性規(guī)劃問題，用單純形法求解時得到的某一步的單純形表如下：問a1，a2，a3，c，d各為何值及變量xj屬于那一類性質(zhì)的變量時：（1）現(xiàn)有解為唯一最優(yōu)解。（2）現(xiàn)有解為最優(yōu)，但最優(yōu)解有無窮多個。（3）存在可行解，但目標函數(shù)無界。（4）此問題無可行解。答：0, d0, x3, x4 ,x5都不是人工變量；=0, d0 , a1，a2至少一個大于零，x3,x4,x5都不是人工變量；0 , d 0 , a10，a20，x3,x4,x5都不是人工變量； 0 , d0 且x3,x4,x5 至少一個是人工變量。6. 某

7、線性規(guī)劃問題的初始單純形表及迭代后的表格如下：求a，b，k，l各個值。答：a=3, b=2, c=4, d=-2, e=2, f=3,g=1, h=0, i=5, j=5, k=-3/2, l=07. 寫出下列線性規(guī)劃問題的對偶問題：（1） 答:（2）答:8用對偶單純形法求解下列線性規(guī)劃問題:（1） 解:化成標準形式，列對偶單純形表 cj -1 -1 0 0 bCBXB x1 x2 x3 x4 0 0x3x4 -2 -1 1 0 -1 -7 0 1 -4 -7j=cj-zj -1 -1 0 0 0采用對偶單純形迭代規(guī)則得最優(yōu)表：-1-1x1x2 1 0 7/13 1/13 0 1 1/13 -

8、2/13 21/1310/13j=cj-zj 0 0 -6/13 -1/13 31/13最優(yōu)解X=(21/13,10/13,0,0) ,最優(yōu)值minZ= 31/13(maxZ=-31/13) 。（2）解: 化成標準形式，列對偶單純形表cj -4 -12 -18 0 0 bCBXB x1 x2 x3 x4 x5 0 0X4X5 -1 0 -3 1 0 0 (-2) -2 0 1 -3 -5j=cj-zj -4 -12 -18 0 0 0-12X4X2 -1 0 (-3) 1 0 0 1 1 0 -1/2 -3 5/2j=cj-zj -4 0 -6 0 -6 -18-12X3X2 1/3 0 1

9、-1/3 0 1/3 1 0 0 -1/2 1 3/2j=cj-zj -2 0 0 -2 -6 最優(yōu)解X=(0,3/2,1,0,0) ,最優(yōu)值minZ=36(maxZ=0-(3/2)×12-1×18=-36) 。9設(shè) （1）寫出其對偶問題。（2）求解對偶問題。（3）從對偶解中求出原問題的解。答：（1）對偶模型 （2）求解對偶問題，圖解法。得Y=(-3,1) ,w*=-15 。（3）利用互補松弛性求原問題解，由y1,y2異于0，知原約束均為等式；又由對偶約束1，2，4式為嚴格不等式，故可得x1,x2,x4等于0。代入原約束方程組，解得x3=3，x5=3, 即X*=(0,0,3

10、,0,3)T ,最優(yōu)值z*=-1×3-4×3=-15=w*。10從下面最優(yōu)單純形表中（最大化問題，約束條件均為“”連接）-5Z=-5（1）寫出原問題與對偶問題的最優(yōu)解。（2）求，并解釋這兩個數(shù)值的含義。（3）如果以代價增添第一種資源一個單位，是否值得（4）若有人原向你購買第三種資源，應(yīng)要價多少才合算（5）是否有其它最優(yōu)解，如果沒有，說明為什么如果有，則求出另一個最優(yōu)解。解：(1)原問題最優(yōu)解X*=(2,0,3/2,0,1,0)T ,對偶問題最優(yōu)解Y*=(4,0,9,0,0,0)。 (2)在最優(yōu)表上可以得到最優(yōu)基的逆B-1,根據(jù)最優(yōu)表上Pj=B-1Pj ,可解得Pj=BPj,

11、從而得A,對偶解-單純形因子再由檢驗數(shù) ,可得 解得C=(1,1,2,0,0,0) ，最優(yōu)值z*=1×2+0+2×(3/2)=5。在最優(yōu)方案時，有 ,因為b1影子價格大于0,是稀缺資源，故在一定范圍內(nèi)每增加一個單位該種資源就會增加4個單位總收入（影子價格或邊際收入為4）。對 ，x6表示第三種資源剩余數(shù)量，該偏導數(shù)值表示資源剩余量對總收入的影響率。在初始方案時其值為0，在最佳方案時其值為-9，從另外角度說明引入該資源有利于減少短缺造成的損失或增加收入（影子價格為9）。(3) 如果以代價增添第一種資源一個單位, 會增加4個單位總收入，值得。 (4) 若有人愿向你購買第三種資源，

12、要價不低于其影子價格9才合算。 (5) 在最優(yōu)表上,非基變量x2的檢驗數(shù)為0，故最優(yōu)解不唯一。令x2進基，x1出基，換基迭代得新最優(yōu)解X*=(0,2,3/2,0,5)T ,最優(yōu)值z*=0+1×2+2(3/2)=5 。11設(shè) 先用單純形法求出最優(yōu)解，再分析在下列各條件單獨變化的情況下最優(yōu)解的變化。（1）約束條件（2）右端常數(shù)由90變?yōu)?0。（2）目標函數(shù)中x3的系數(shù)由13變?yōu)?。（3）增加一個約束條件：解: 先用單純形法求出最優(yōu)解MAX:-5X1 +5X2 +13X3 ST: 1 -1X1 +1X2 +3X3 +1X4 = 20 2 12X1 +4X2 +10X3 +1X5 = 90得

13、到了第一個可行基用最大檢驗數(shù)法- I BA C -5 5 13 0 0 b X1 X2 X3 X4 X5- 1 X2 5 20 -1 1 3 1 0 2 X5 0 10 16 0 -2 -4 1- Cj-Zj -100 0 0 -2 -5 0迭代次數(shù) = 2最優(yōu)解MAX Z= 100變量名 取值 檢驗數(shù) X1 0 X2 20 X3 0 X4 0 X5 10 約束標號 對偶價格( 1) ( 2) 在最優(yōu)基不變的條件下, 變量在目標函數(shù)中的系數(shù)的取值區(qū)間變量名 現(xiàn)系數(shù) 系數(shù)取值區(qū)間 X1 ( - , ) X2 ( , ) X3 ( - , ) X4 ( - , ) X5 ( , )在最優(yōu)基不變的條

14、件下, 右端常數(shù)項的取值區(qū)間約束序號 現(xiàn)常數(shù) 常數(shù)取值區(qū)間( 1) ( , )( 2) ( , )-(1) 約束條件（2）右端常數(shù)由90變?yōu)?0,不影響最優(yōu)基,只須驗證可行性。由最優(yōu)表找到最優(yōu)基的逆, x5不可行,采用對偶單純形迭代，x5出基，x3進基， - I BA C -5 5 13 0 0 b X1 X2 X3 X4 X5- 1 X3 13 5 -8 0 1 2 -1/2 2 X2 5 5 23 1 0 -5 3/2- Cj-Zj -90 -16 0 0 -1 -1-最優(yōu)解變量名 取值 檢驗數(shù) X1 0 X2 5 X3 5 X4 0 X5 0 MAX Z= 90(2) 目標函數(shù)中非基變量

15、x3的系數(shù)c3由13變?yōu)?。檢查檢驗數(shù)3=c3-CBB-1P3=8-(5,0)(3,10)T=8-15=-7<0,最優(yōu)解，最優(yōu)值不變。(3) 增加一個約束條件：,引進松弛變量x6作為一個基變量，在最優(yōu)表添加一行，迭代出單位矩陣和檢驗數(shù)形式，判斷是否最優(yōu)解。- I BA C -5 5 13 0 0 0 b X1 X2 X3 X4 X5 X6- 1 X2 5 20 -1 1 3 1 0 0 2 X5 0 10 16 0 -2 -4 1 0 3 X6 0 50 2 3 5 0 0 1- Cj-Zj -100 0 0 -2 -5 0 0- I BA C -5 5 13 0 0 0 b X1 X2

16、 X3 X4 X5 X6- 1 X2 5 20 -1 1 3 1 0 0 2 X5 0 10 16 0 -2 -4 1 0 3 X6 0 -10 5 0 (-4) -3 0 1- Cj-Zj -100 0 0 -2 -5 0 0采用對偶單純形迭代，x6出基，x3進基，- I BA C -5 5 13 0 0 0 b X1 X2 X3 X4 X5 X6- 1 X2 5 25/2 11/4 1 0 -5/4 0 3/4 2 X5 0 15 27/2 0 0 -5/2 1 -1/2 3 X3 13 5/2 -5/4 0 1 3/4 0 -1/4 - Cj-Zj -95 -5/2 0 0 -7/2 0

17、 -1/2最優(yōu)解MAX Z= 95變量名 取值 檢驗數(shù) X1 0 X2 25/2 X3 5/2 X4 0 X5 15 X6 0 約束標號 對偶價格( 1) ( 2) ( 3) 在最優(yōu)基不變的條件下, 變量在目標函數(shù)中的系數(shù)的取值區(qū)間變量名 現(xiàn)系數(shù) 系數(shù)取值區(qū)間 X1 ( - , ) X2 ( , ) X3 ( , ) X4 ( - , ) X5 ( , ) X6 ( - , )在最優(yōu)基不變的條件下, 右端常數(shù)項的取值區(qū)間約束序號 現(xiàn)常數(shù) 常數(shù)取值區(qū)間( 1) ( , )( 2) ( , )( 3) ( , )12設(shè) （1）求在不影響最優(yōu)基的條件下各個cj的允許變化的范圍。（2）求在不影響最優(yōu)基

18、的條件下各個bi的允許變化的范圍。解：列單純形表求解得最優(yōu)表，利用最優(yōu)基不變時求解各系數(shù)區(qū)間MAX: 2X1 +5X2 +8X3 ST: 1 3X1 +2X2 -1X3 +1X4 =610 2 -1X1 +6X2 +3X3 +1X5 =125 3 -1X1 +1X2+1/2X3 +1X6 =420MAX: 2X1 +5X2 +8X3 ST: 1 3X1 +2X2 -1X3 +1X4 =610 2 -1X1 +6X2 +3X3 +1X5 =125 3 -1X1 +1X2+1/2X3 +1X6 =420得到了第一個可行基用最大檢驗數(shù)法- I BA C 2 5 8 0 0 0 b X1 X2 X3 X4 X5 X6 - 1 X4 0 610 3 2 -1 1 0 0 2 X5 0 125 -1 6 3 0 1 0 125/3 3 X6 0 420 -1 1 1/2 0 0 1 840- Cj-Zj 0 2 5 8 0 0 0 -旋轉(zhuǎn)元是 A23用最大檢驗數(shù)法- I BA C 2 5 8 0 0 0 b X1 X2 X3 X4 X5 X6 - 1 X4 0 1955/3 8/3 4 0 1 1/3 0 1955/8 2 X3 8 125/3 -1/3 2 1 0 1/3 0 3 X6 0 2395/6 -5/6