線性規(guī)劃的對偶問題

1、第二章 線性規(guī)劃的對偶問題習題2.1 寫出下列線性規(guī)劃問題的對偶問題=2xi + x 2+ 3x3 + x 4(1) max z = 10xi+ X2+ 2x3(2) max zst. x1+ X2+ X3 + X 4 W52x1 x 2+ 3x34x1x3+ x4>1x1, x3> 0, x2,X4無約束=一 5 x 1 6x2 7x3st. x 1+ x 2+ 2 x3< 104xi + X2+ x3< 20Xj >0(j = 1,2,3 )(3) min z= 3x1 + 2 x 2 3x3 + 4x4 (4) min zst. x1+ 5x2 3x3 &g

2、t; 155x1 6x2 +10x3 < 20x1 x 2 x 3 5x 1<0, x2>0, X3 無約束AX=b, X> 0。分別說明發(fā)生下列情況時,其入(入工0);(入工0)后加到第r個約束條件上；st. x 1 2x2 + 3x3 + 4x4 3x2 + 3x3 + 4x4 A 52x 1 3x2 7x3 4x4 2=x1 >0, X4W 0, X2, X3 無約束2.2 已知線性規(guī)劃問題 maxz CX，對偶問題的解的變化：( 1)問題的第 k 個約束條件乘上常數(shù)(2) 將第k個約束條件乘上常數(shù) 入入CX (入工0);。min z 8x1+ 6x2+ 3

3、x3+ 6x4(3) 目標函數(shù)改變?yōu)?max z( 4)模型中全部 x1 用 3 x'1 代換2.3 已知線性規(guī)劃問題st. x 1+ 2x2+ x 4> 33x1+ x 2+ x 3+ x 4> 6x3 + x 4 2xi+ X3>2X >0 (j =123,4 )(1) 寫出其對偶問題；(2) 已知原問題最優(yōu)解為 x*=( 1 ， 1 ，2， 0 ) ，試根據(jù)對偶理論，直接求出對 偶問題的最優(yōu)解。2.4 已知線性規(guī)劃問題 min z = 2x1+ x2+ 5x3+ 6x4對偶變量st. 2x i+X3+ x 4< 8y i2xi + 2x2+X3 +

4、2x4< 12y 2xj>0(j =1,2,3,4 )其對偶問題的最優(yōu)解yi*=4； y2*=1,試根據(jù)對偶問題的性質(zhì)，求出原問題的最優(yōu) 解。2.5 考慮線性規(guī)劃問題max z=2x1+ 4x2+3x3st. 3x 1 + 4x2 + 2x3602xi + x 2+ 2x3 w 40Xi + 3x2 + 2x3 w 80xj>0 (j =1,2,3 )(1) 寫出其對偶問題(2) 用單純形法求解原問題，列出每步迭代計算得到的原問題的解與互補的對偶問題的解；(3) 用對偶單純形法求解其對偶問題，并列出每步迭代計算得到的對偶問題 解及與其互補的對偶問題的解；(4) 比較( 2)和

5、( 3)計算結(jié)果。2.6 已知線性規(guī)劃問題max z=10x1+ 5x2st. 3x 1+ 4x2w 95xi + 2x2< 8Xj >0 (j = 1,2 )用單純形法求得最終表如下表所示:X1X2X3X4bX201314X110171CTj =Cj -Zj005142514試用靈敏度分析的方法分別判斷：(1) 目標函數(shù)系數(shù)C1或C2分別在什么范圍內(nèi)變動，上述最優(yōu)解不變；(2) 約束條件右端項bi，b,當一個保持不變時，另一個在什么范圍內(nèi)變化, 上述最優(yōu)基保持不變；(3) 問題的目標函數(shù)變?yōu)?max z = 12xi + 4x2時上述最優(yōu)解的變化；(4) 約束條件右端項由9變?yōu)?

6、1時上述最優(yōu)解的變化。18 丿119 J2.7線性規(guī)劃問題如下：max z = 5x1 + 5x2 + 13x3st.X1+X2+3x3< 2012X1 + 4X2 + 10x3<90Xj >0 (j = 1,2,3 )先用單純形法求解，然后分析下列各種條件下，最優(yōu)解分別有什么變化?(1)約束條件的右端常數(shù)由20變?yōu)?0；(2)約束條件的右端常數(shù)由90變?yōu)?0；(3)目標函數(shù)中X3的系數(shù)由13變?yōu)?；(4)X1的系數(shù)列向量由(一1，12) T變?yōu)?0，(5)增加一個約束條件：2x1 + 3x2 + 5x3 W 505) T；（6）將原約束條件改變?yōu)?10Xi + 5x2 +

7、IOX3W 100o2.8用單純形法求解某線性規(guī)劃問題得到最終單純形表如下:Cj基變量50401060SX1X2X3X4ac0116bd1024<5j =Cj-Zj00efg（1）給出a，b, c, d, e，f，g的值或表達式；（2）指出原問題是求目標函數(shù)的最大值還是最小值；（3） 用a+ a，b+ b分別代替a和b,仍然保持上表是最優(yōu)單純形表，求a， b滿足的范圍。2.9某文教用品廠用原材料白坯紙生產(chǎn)原稿紙、日記本和練習本三種產(chǎn)品。該 廠現(xiàn)有工人100人，每月白坯紙供應(yīng)量為 30000千克。已知工人的勞動生產(chǎn)率為： 每人每月可生產(chǎn)原稿紙 30捆，或日記本30打，或練習本30箱。已知原

8、材料消耗 為：每捆原稿紙用白坯紙 10千克，每打日記本用白坯紙 40千克，每箱練習本用白33坯紙80千克。又知每生產(chǎn)一捆原稿紙可獲利2元，生產(chǎn)一打日記本獲利 3元，生產(chǎn)3一箱練習本獲利1元。試確定：（1）現(xiàn)有生產(chǎn)條件下獲利最大的方案；（2）如白坯紙的供應(yīng)數(shù)量不變，當工人數(shù)不足時可招收臨時工，臨時工工資支出為每人每月40元，則該廠要不要招收臨時工？如要的話，招多少臨時工最合適？2.10某廠生產(chǎn)甲、乙兩種產(chǎn)品，需要A、B兩種原料，生產(chǎn)消耗等參數(shù)如下表（表中的消耗系數(shù)為千克/件）產(chǎn)品原料甲乙可用量（千克）原料成本（兀/千克）A241601.0B321802.0銷售價1316（元）（1）請構(gòu)造數(shù)學模型

9、使該廠利潤最大，并求解。（2）原料A B的影子價格各為多少。（3） 現(xiàn)有新產(chǎn)品丙，每件消耗 3千克原料A和4千克原料B，問該產(chǎn)品的銷售 價格至少為多少時才值得投產(chǎn)。（4）工廠可在市場上買到原料 A。工廠是否應(yīng)該購買該原料以擴大生產(chǎn)？在保 持原問題最優(yōu)基的不變的情況下，最多應(yīng)購入多少？可增加多少利潤？2.11某廠生產(chǎn)A、B兩種產(chǎn)品需要同種原料，所需原料、工時和利潤等參數(shù)如 下表：單位產(chǎn)品AB可用量（千克）原料（千克）12200工時（小時）21300利潤（萬元）43（1）請構(gòu)造一數(shù)學模型使該廠總利潤最大，并求解。（2） 如果原料和工時的限制分別為300公斤和900小時，又如何安排生產(chǎn)？（3） 如果

10、生產(chǎn)中除原料和工時外，尚考慮水的用量，設(shè)兩A, B產(chǎn)品的單位產(chǎn)品分別需要水4噸和2噸，水的總用量限制在 400噸以內(nèi)，又應(yīng)如何安排生產(chǎn)？復(fù)習思考題2.12 試從經(jīng)濟上解釋對偶問題及對偶變量的含義。2.13 根據(jù)原問題同對偶問題之間的對應(yīng)關(guān)系，分別找出兩個問題變量之間、解以 及檢驗數(shù)之間的對應(yīng)關(guān)系。2.14 什么是資源的影子價格，同相應(yīng)的市場價格之間有何區(qū)別，以及研究影子價 格的意義。2.15 試述對偶單純形法的計算步驟，它的優(yōu)點及應(yīng)用上的局限性。2.16 將 aij， b， c 的變化分別直接反映到最終單純形表中，表中原問題和對偶問題 的解各自將會出現(xiàn)什么變化，有多少種不同情況以及如何去處理。2.17 判斷下列說法是否正確(a) 任何線性規(guī)劃問題存在并具有唯一的對偶問題；(b) 對偶問題的對偶問題一定是原問題；(c) 根據(jù)對偶問題的性質(zhì)，當原問題為無界解時，其對偶問題無可行解，反之，當 對偶問題無可行解時，其原問題具有無界解；(d) 若某種資源的影子價格等于 k，在其它條件不變的情況下，當該種資源增加5個單位時，相應(yīng)的目標函數(shù)值將增大 5k；(e) 應(yīng)用對偶單純形法計算時，若單純形表中某一基變量Xi<0，又Xi所在行的元素全部大于或等于零，則可以判斷其對偶問題具有無界解；(