運籌學試題及答案

1、一、填空題：每空格2分，共16分1、 線性規(guī)劃的解有唯一最優(yōu)解、無窮多最優(yōu)解、無界解和無可行解四種。2、 在求運費最少的調度運輸問題中，如果某一非基變量的檢驗數(shù)為4,則說明如果在該空格中增加一個運量運費將增加 4。3、 “如果線性規(guī)劃的原問題存在可行解，則其對偶問題一定存在可行解”，這句話對還是錯？錯4、如果某一整數(shù)規(guī)劃：MaxZ=X i +X2X1+9/14X2W 51/14-2X1+X2W 1/3X1,X2> 0且均為整數(shù)所對應的線性規(guī)劃松弛問題的最優(yōu)解為X仁3/2, X2=10/3，MaxZ=6/29，我們現(xiàn)在要對X1進行分枝，應該分為X1W 1和 X12。5. 在用逆向解法求動態(tài)

2、規(guī)劃時，fk(sk)的含義是：從第k個階段到第n個階段 的最優(yōu)解 。6. 假設某線性規(guī)劃的可行解的集合為D,而其所對應的整數(shù)規(guī)劃的可行解集合為B,那么D和B的關系為 D包含B7. 已知下表是制訂生產(chǎn)計劃問題的一張 LP最優(yōu)單純形表極大化問題，約束條 件均為“W”型不等式其中 X3,X4,X5為松馳變量。XbbX茨X4X5X4300-21P 3X14/310-1/302/3X2 :101 :00:-1Cj-Zj00-50-23213問：1寫出B-1 =1/3.02/3001對偶問題的最優(yōu)解:Y=5， 0， 23， 0， 08. 線性規(guī)劃問題如果有無窮多最優(yōu)解，則單純形計算表的終表中必然有某一個非

3、基變量的檢驗數(shù)為0;9. 極大化的線性規(guī)劃問題為無界解時，則對偶問題 無解;10. 假設整數(shù)規(guī)劃的松馳問題的最優(yōu)解不符合整數(shù)要求，假設 X=b不符合整數(shù) 要求，INTb是不超過bi的最大整數(shù)，則構造兩個約束條件： Xi >INTbi+ 1 和Xi < INTbi，分別將其并入上述松馳問題中，形成兩個分支，即兩個后繼問題。丫 二(4,0,9,0,0,0)問：（1）對偶問題的最優(yōu)解: 2寫出 B-1 2 3 4 =11. 知下表是制訂生產(chǎn)計劃問題的一張 LP最優(yōu)單純形表極大化問題，約束條 件均為“W”型不等式其中 X4,X5,X6為松馳變量。XbbX關X4X5X6X21P 10201X

4、32/3001104X5 :10:-20116 1Cj-Zj000-40-9T二、計算題60分1、已知線性規(guī)劃20分MaxZ=3X 1+4X2 01+X2W 52X1+4X2W 123X1+2X2W 8X1,X2> 0其最優(yōu)解為:基變量X1X2X3X4X5X33/2001-1/8-1/4X25/20103/8-1/4X11100-1/41/2c j000-3/4-1/2(T 4=-9/8(T 5=-1/4由于非基變量的檢驗數(shù)仍然都是小于0的，所以最優(yōu)解不變。3當假設b2的量從12上升到15X =9/8 '29/81/4 “由于基變量的值仍然都是大于0的，所以最優(yōu)解的基變量不會發(fā)生

5、變化 4如果增加一種新的產(chǎn)品，則P6 =(11/8,7/8 , - 1/4) Tt 6=3/8>0所以對最優(yōu)解有影響，該種產(chǎn)品應該生產(chǎn)2、已知運輸問題的調運和運價表如下，求最優(yōu)調運方案和最小總費用。共15分。銷地產(chǎn)地B1B2B3產(chǎn)量A159215A231711A362820銷量181216解：初始解為B1B2B3產(chǎn)量/tA1515A21111A181120銷量/t181216計算檢驗數(shù)B1b2B3產(chǎn)量/tA513015A-20011A00020銷量/t181216由于存在非基變量的檢驗數(shù)小于 0,所以不是最優(yōu)解，需調整 調整為：B1B2B3產(chǎn)量/tA1515A1111A712120銷量/

6、t181216重新計算檢驗數(shù)B1B2B3產(chǎn)量/tA513015A02211A00020銷量/t181216所有的檢驗數(shù)都大于等于 0，所以得到最優(yōu)解3、某公司要把4個有關能源工程項目承包給 4個互不相關的外商投標者，規(guī)定 每個承包商只能且必須承包一個項目，試在總費用最小的條件下確定各個項目的 承包者，總費用為多少？各承包商對工程的報價如表 2所示：15 分目投標者'ABCD甲l15182124乙19232218丙26171619丁19212317答最優(yōu)解為：X= 0 11 0 00 0 10 0 0總費用為504. 考慮如下線性規(guī)劃問題24分Max z=-5x1+5x2+13x3S.t

7、.-X1+X2+3X3< 20v 12x1+4x2+10x3= 90X1 , X2, X3> 0 答復以下問題： 1求最優(yōu)解 2求對偶問題的最優(yōu)解 3當b1由20變?yōu)?5,最優(yōu)解是否發(fā)生變化。 4求新解增加一個變量X6, C6=10, a16=3, a26=5,對最優(yōu)解是否有影響 5C2有5變?yōu)?,是否影響最優(yōu)解。答：最優(yōu)解為1)C-5513009CBXbbX,X2X3X4X50X420-1131020/30X59012410019C-Zj-55130013X320/3-1/31/311/30200X570/3 146/322/30-10/3170/22Cj-Zj-2/32/30-

8、13/3013X3185/33-34/33012/11-1/225X235/11 n23/1110-5/113/22-68/3300-1/11-1/11最優(yōu)解為 Xi=185/33, X 3=35/112) 對偶問題最優(yōu)解為Y= 1/22,1/11,68/33,0,03)當b仁45時X= 45/11 r-jj/90由于X2的值小于一0,所以最優(yōu)解將發(fā)生變化4P6 =(3/11,-3/4) T(T 6=217/20>0所以對最優(yōu)解有影響。5當 C2=6(T 1=-137/33(T 4=4/11(T 5=-17/22由于C 4大于0所以對最優(yōu)解有影響5.求如下圖的網(wǎng)絡的最大流和最小截集(割集

9、)，每弧旁的數(shù)字是Cj , f j。 15 分V2Vs(4,4)(4,1)(9,7)(8,8)VtV3(6,6)6.考慮如下線性規(guī)劃問題20分Max z=3xi+X2+4x3s.t.6xi+3x2+5x3< 9v 3xi+4x2+5x3< 8j X1, X2, X3> 0 答復以下問題：1丨求最優(yōu)解；2直接寫出上述問題的對偶問題及其最優(yōu)解；3假設問題中X2列的系數(shù)變?yōu)?, 2T,問最優(yōu)解是否有變化; 4C2由1變?yōu)?,是否影響最優(yōu)解，如有影響，將新的解求出。Cj31400CbXbbX1X2X3X4X50X49635100X5834501Cj-Zj314000X413-101-

10、14X38/5:3/54/5101/5:Cj-Zj3/5-11/500-4/53X11/31-1/301/3-1/34X37/5 T011-1/52/5Cj-Zj0-20-1/5-3/5最優(yōu)解為 X1=1/3,X3=7/5,Z=33/52)對偶問題為Min w=9y1+8y261+3y2>3J 3y1+4y2> 1 5y1+5y2> 4y1,y2> 0對偶問題最優(yōu)解為y1=1/5,y2=3/53) 假設問題中X2列的系數(shù)變?yōu)?, 2T則 P2 =(1/3,1/5) T(T 2=-4/5 v 0所以對最優(yōu)解沒有影響4C2由1變?yōu)?(T 2=-1 V 0所以對最優(yōu)解沒有影響

11、In設備能力（臺.h）A111100B1045600C226300單位產(chǎn)品利潤（元）10648.某廠I、所需的設備臺時,n、川三種產(chǎn)品分別經(jīng)過A B、C三種設備加工。已知生產(chǎn)單位各種產(chǎn)品設備的現(xiàn)有加工能力及每件產(chǎn)品的預期利潤見表：1）建立線性規(guī)劃模型，求獲利最大的產(chǎn)品生產(chǎn)計劃。（15分）Cij , f ij 解:Vt2）產(chǎn)品川每件的利潤到多大時才值得安排生產(chǎn)？如產(chǎn)品川每件利潤增加到50/6元，求最優(yōu)計劃的變化。（4分）3）產(chǎn)品I的利潤在多大范圍內變化時，原最優(yōu)計劃保持不變。（2分）4）設備A的能力在什么范圍內變化時，最優(yōu)基變量不變。（3分）5）如有一種新產(chǎn)品，加工一件需設備A、B、C的臺時各為

12、1、4、3h，預期每件為8元，是否值得生產(chǎn)。（3分）6) 如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品川，試確定最優(yōu)計劃的變化。(3分)解：1建立線性規(guī)劃模型為：MaxZ=10x1+6x2+4x3x1+x2+x 3 w 10010x1+4x2+5x 3< 6002x1+2x2+6x3 w 300xj > 0,j=1,2,3獲利最大的產(chǎn)品生產(chǎn)計劃為：X*=(x1,x2,x3,x4,x5,x6) '(100/3,200/3,0,0,0,100)' Z*=2200/32產(chǎn)品川每件利潤到 20/3才值得生產(chǎn)。如果產(chǎn)品川每件利潤增加到50/6元，最優(yōu)計劃的變化為：X*=(x1,x2,x3

13、,x4,x5,x6) '(175/6,275/6,25,0,0,0) ' Z*=7753產(chǎn)品I的利潤在6,15變化時，原最優(yōu)計劃保持不變。4設備A的能力在60,150變化時，最優(yōu)基變量不變。5新產(chǎn)品值得生產(chǎn)。6最優(yōu)計劃的變化為：X*=(x1,x2,x3,x4,x5,x6) '(190/6,350/6,10,0,0,60 )'9. 給出成性規(guī)劃問題：(15分)Min z=2x 1 +3x 2+6x 3X1+2X 2+x 3 >2-2x 1+x 2+3x 3 W-3Xj >0j=1,，4要求：(1) 寫出其對偶問題。(5分)(2) 利用圖解法求解對偶問題

14、。(5分)(3) 利用(2)的結果，根據(jù)對偶問題性質寫出原問題最優(yōu)解。(5分)解：1該問題的LD為：MaxW=2y1-3y2y1-2y2 w 22y1+y2 w 3y1+3y2 w 6y1 > 0, y2 w 02) 用圖解法求得 LD 的最優(yōu)解為：Y*=(y1,y2)' =(8/5,-1/5)'W*=19/53) 由互補松弛定理：原問題的最優(yōu)解為：X*=(x1,x2,x3) '(8/5,1/5,0)'10. 某部門有3個生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地），生產(chǎn)的產(chǎn)品由4個銷售點（銷地）出售,產(chǎn)各銷售點的銷售量（單位.t）以及各工廠到各銷售點的單位運價（元/t）示于下表中，要求研究產(chǎn)品如何調運才能使總運量最??？（10分）B1B2B3B4產(chǎn)量A141241132A22103920A38511644銷量1628282496 96解：最優(yōu)調運方案為：A1-B3 和 B4 28t 和 4tA2-B1 和 B4 16t 和 4tA3-B2 和 B4 28t 和 16t最小總運費為：460元11. 求解以下0-1規(guī)劃問題 maxz=3x 1+2x 2-5x 3-2x 4+3x 5x 1+X 2 +x 3 +2x 4+x 5 <4F7x 1 +3x 3-4x 4+3x 5 <811x 1-6x 2+3x 4-3x 5 >3LXj=0 或