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

第二章線性規(guī)劃的對偶問題習題(1)maxz=10x1+x2+2x3st.x1+x2+2X3WIO4x1+x2+x3^20x.NO(j=1,2,3)(3)minz=3x1+2x2_(1)maxz=10x1+x2+2x3st.x1+x2+2X3WIO4x1+x2+x3^20x.NO(j=1,2,3)(3)minz=3x1+2x2_3x3+4x4st.x~2x+3x+4xW31234x2+3x3+4x4N—52x1~3x2~7x3—4x4=2=x1N0,x4W0,x2,x3無約束2.2已知線性規(guī)劃問題maxz=CX,x1,x3N0,x2,x4無約束(4)minz=—5x1—6x2—7x3st.—x1+5x2—3x3N15—5x1—6x2+10x3W20x1—x2—x3=—5x1W0,x2N0,x3無約束AX=b,XN0。分別說明發(fā)生下列情況時，其對偶問題的解的變化：問題的第k個約束條件乘上常數(shù)久。乏0)；將第k個約束條件乘上常數(shù)久。乏0)后加到第r個約束條件上;目標函數(shù)改變?yōu)閙axz=XCX(A^0);(4)模型中全部x1用3x'i代換。2.3已知線性規(guī)劃問題minz=8x1+6x2+3x3+6x4st.x1+2x2+x4N33x+x+x+xN61234x3+x4=2TOC\o"1-5"\h\zx1+x3N2x.N0(j=1,2,3,4)寫出其對偶問題；7已知原問題最優(yōu)解為x*=(1,1,2,0)，試根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解。2.4已知線性規(guī)劃問題minz=2x1+x2+5x3+6x4對偶變量st.2x1+x3+x4W8y12x1+2x2+x3+2x4^12y^x.N0(j=1,2,3,4)其對偶問題的最優(yōu)解y1*=4；y；=1，試根據(jù)對偶問題的性質(zhì)，求出原問題的最優(yōu)解。2.5考慮線性規(guī)劃問題maxz=2x1+4x2+3x3st.3x1+4x2+2x3W602x1+x2+2x3^40x+3x+2xW80123x.N0(j=1,2,3)寫出其對偶問題用單純形法求解原問題，列出每步迭代計算得到的原問題的解與互補的對偶問題的解；用對偶單純形法求解其對偶問題，并列出每步迭代計算得到的對偶問題解及與其互補的對偶問題的解；比較(2)和(3)計算結(jié)果。

2.6已知線性規(guī)劃問題maxz=10x1^5x2s3jc+4^5x,~h2xnW812x.^0(j，=1,2)用單純形法求得最終表如下表所示：x1x2x3x4bx201-14x110-712*00-尋2514試用靈敏度分析的方法分別判斷:目標函數(shù)系數(shù)C1或c2分別在什么范圍內(nèi)變動，上述最優(yōu)解不變；約束條件右端項b,b2,當一個保持不變時，另一個在什么范圍內(nèi)變化，上述最優(yōu)基保持不變；問題的目標函數(shù)變?yōu)閙axz=12x1^4x2時上述最優(yōu)解的變化；(4)約束條件右端項由變?yōu)?4)約束條件右端項由變?yōu)閒11］時上述最優(yōu)解的變化。2.7線性規(guī)劃問題如下：maxz=—5x1+5x2+13x3S~x1+x2+3x^20①12x1+4x2+10x3^90②先用單純形法求解，然后分析下列各種條件下，’最優(yōu)解分別有什么變化?約束條件①的右端常數(shù)由20變?yōu)?0；約束條件②的右端常數(shù)由90變?yōu)?0；目標函數(shù)中x3的系數(shù)由13變?yōu)?；x的系數(shù)列向量由(一1，12)t變?yōu)?0，5)t；增加一個約束條件③：2x+3x+5x<50；將原約束條件②改變?yōu)椋?0x+5x+10x<100。一……1232.8用單純形法求解某線性規(guī)劃問題得到最終單純形表如下：cj基變量50401060Sx1x2xxAac0116bd102400efg給出a，b，c，d，e，f，g的值或表達式；指出原問題是求目標函數(shù)的最大值還是最小值；用a+?a，b+2b分別代替a和b，仍然保持上表是最優(yōu)單純形表，求?a，?b滿足的范圍。2.9某文教用品廠用原材料白坯紙生產(chǎn)原稿紙、日記本和練習本三種產(chǎn)品。該廠現(xiàn)有工人100人，每月白坯紙供應量為30000千克。已知工人的勞動生產(chǎn)率為：每人每月可生產(chǎn)原稿紙30捆，或日記本104030打，或練習本30箱。已知原材料消耗為：每捆原稿紙用白坯紙y千克，每打日記本用白坯紙耳千80一一克，每箱練習本用白坯紙?zhí)澢Э?。又知每生產(chǎn)一捆原稿紙可獲利2元，生產(chǎn)一打日記本獲利3元，生產(chǎn)一箱練習本獲利1元。試確定：（1）現(xiàn)有生產(chǎn)條件下獲利最大的方案；（2）如白坯紙的供應數(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ù)學模型使該廠利潤最大，并求解。（2）原料A、B的影子價格各為多少。（3）現(xiàn)有新產(chǎn)品丙，每件消耗3千克原料A和4千克原料B，問該產(chǎn)品的銷售價格至少為多少時才值得投產(chǎn)。（4）工廠可在市場上買到原料AoX廠是否應該購買該原料以擴大生產(chǎn)？在保持原問題最優(yōu)基的不變的情況下，最多應購入多少？可增加多少利潤？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）如果生產(chǎn)中除原料和工時外，尚考慮水的用量，設兩A，B產(chǎn)品的單位產(chǎn)品分別需要水4噸和2噸，水的總用量限制在400噸以內(nèi)，又應如何安排生產(chǎn)？復習思考題2.12試從經(jīng)濟上解釋對偶問題及對偶變量的含義。2.13根據(jù)原問題同對偶問題之間的對應關(guān)系，分別找出兩個問題變量之間、解以及檢驗數(shù)之間的對應關(guān)系。2.14什么是資源的影子價格，同相應的市場價格之間有何區(qū)別，以及研究影子價格的意義。2.15試述對偶單純形法的計算步驟，它的優(yōu)點及應用上的局限性。2.16將氣.，b，c的變化分別直接反映到最終單純形表中，表中原問題和對偶問題的解各自將會出現(xiàn)什么變化，有多少種不同情況以及如何去處理。2.17判斷下列說法是否正確（a）任何線性規(guī)劃問題存在并具有唯一的對偶問題；（b）對偶問題的對偶問題一定是原問題；（c）根據(jù)對偶問題的性質(zhì)，當原問題為無界解時，其對偶問題無可行解，反之，當對偶問題無可行解時，其原問題具有無界解；（d）若某種資源的影子價格等于k，在其它條件不變的情況下，當該種資源增加5個單位時，相應的目標函數(shù)值將增大5k；（e）應用對偶單純形法計算時，若單純形表中某一基變量x.<0，又x.所在行的元素全部大于或等于零，則可以判斷其對偶問題具有無界解；11（f）若線性規(guī)劃問題中