《運籌學第3版熊偉編著習題答案.doc》由會員分享，可在線閱讀，更多相關《運籌學第3版熊偉編著習題答案.doc（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、138運籌學(第3版) 習題答案運籌學（第3版）習題答案第1章 線性規(guī)劃 P36第2章 線性規(guī)劃的對偶理論 P74第3章 整數(shù)規(guī)劃 P88第4章 目標規(guī)劃 P105第5章 運輸與指派問題P142第6章 網(wǎng)絡模型 P173第7章 網(wǎng)絡計劃 P195第8章 動態(tài)規(guī)劃 P218第9章 排隊論 P248第10章 存儲論P277第11章 決策論P304第12章 多屬性決策品P343第13章 博弈論P371全書420頁第1章 線性規(guī)劃1.1 工廠每月生產(chǎn)A、B、C三種產(chǎn)品 ,單件產(chǎn)品的原材料消耗量、設備臺時的消耗量、資源限量及單件產(chǎn)品利潤如表123所示表123產(chǎn)品資源ABC資源限量材料(kg)1.51.2

2、42500設備(臺時)31.61.21400利潤(元/件)101412 根據(jù)市場需求,預測三種產(chǎn)品最低月需求量分別是150、260和120,最高月需求是250、310和130.試建立該問題的數(shù)學模型,使每月利潤最大【解】設x1、x2、x3分別為產(chǎn)品A、B、C的產(chǎn)量，則數(shù)學模型為1.2 建筑公司需要用5m長的塑鋼材料制作A、B兩種型號的窗架兩種窗架所需材料規(guī)格及數(shù)量如表124所示：表124 窗架所需材料規(guī)格及數(shù)量型號A型號B每套窗架需要材料長度（m）數(shù)量(根)長度(m)數(shù)量(根)A1：22B1：2.52A2：1.53B2：23需要量（套）300400問怎樣下料使得（1）用料最少；（2）余料最少【

3、解】 第一步：求下料方案，見下表。方案一二三四五六七八九十需要量B12.52111000000800B2201002110001200A120010010210600A21.50001002023900余料(m)00.50.51110100.5第二步：建立線性規(guī)劃數(shù)學模型設xj（j=1,2,，10）為第j種方案使用原材料的根數(shù)，則（1）用料最少數(shù)學模型為（2）余料最少數(shù)學模型為1.3某企業(yè)需要制定16月份產(chǎn)品A的生產(chǎn)與銷售計劃。已知產(chǎn)品A每月底交貨，市場需求沒有限制，由于倉庫容量有限，倉庫最多庫存產(chǎn)品A1000件，1月初倉庫庫存200件。16月份產(chǎn)品A的單件成本與售價如表125所示。表125月

4、份1 2 3 4 5 6產(chǎn)品成本(元/件)銷售價格(元/件)300 330 320 360 360 300350 340 350 420 410 340（1）16月份產(chǎn)品A各生產(chǎn)與銷售多少總利潤最大，建立數(shù)學模型；（2）當1月初庫存量為零并且要求6月底需要庫存200件時，模型如何變化?！窘狻吭Oxj、yj（j1，2，6）分別為16月份的生產(chǎn)量和銷售量，則數(shù)學模型為（1）（2）目標函數(shù)不變，前6個約束右端常數(shù)800改為1000，第711個約束右端常數(shù)200改為0，第12個約束“200”改為“200”。1.4 某投資人現(xiàn)有下列四種投資機會, 三年內(nèi)每年年初都有3萬元（不計利息）可供投資：方案一：在三

5、年內(nèi)投資人應在每年年初投資，一年結算一次，年收益率是20，下一年可繼續(xù)將本息投入獲利；方案二：在三年內(nèi)投資人應在第一年年初投資，兩年結算一次，收益率是50，下一年可繼續(xù)將本息投入獲利，這種投資最多不超過2萬元；方案三：在三年內(nèi)投資人應在第二年年初投資，兩年結算一次，收益率是60，這種投資最多不超過1.5萬元；方案四：在三年內(nèi)投資人應在第三年年初投資，一年結算一次，年收益率是30，這種投資最多不超過1萬元投資人應采用怎樣的投資決策使三年的總收益最大，建立數(shù)學模型.【解】是設xij為第i年投入第j項目的資金數(shù)，變量表如下項目一項目二項目三項目四第1年第2年第3年x11x21x31x12x23x34

6、數(shù)學模型為最優(yōu)解X=(30000，0，66000，0，109200，0)；Z847201.5 煉油廠計劃生產(chǎn)三種成品油，不同的成品油由半成品油混合而成，例如高級汽油可以由中石腦油、重整汽油和裂化汽油混合，辛烷值不低于94，每桶利潤5元，見表126。表126成品油高級汽油一般汽油航空煤油一般煤油半成品油中石腦油重整汽油裂化汽油中石腦油重整汽油裂化汽油輕油、裂化油、重油、殘油輕油、裂化油、重油、殘油按10:4:3:1調合而成辛烷值9484蒸汽壓：公斤平方厘米1利潤(元/桶)54.231.5半成品油的辛烷值、氣壓、及每天可供應數(shù)量見表127。表127半成品油1中石腦油2重整汽油3裂化汽油4輕油5裂化

7、油6重油7殘油辛烷值80115105蒸汽壓：公斤平方厘米1.01.50.60.05每天供應數(shù)量(桶)200010001500120010001000800問煉油廠每天生產(chǎn)多少桶成品油利潤最大，建立數(shù)學模型。解 設xij為第i（i1,2,3,4）種成品油配第j(j=1,2,7)種半成品油的數(shù)量（桶）?？偫麧櫍焊呒壠秃鸵话闫偷男镣橹导s束航空煤油蒸氣壓約束一般煤油比例約束即半成品油供應量約束整理后得到1.6 圖解下列線性規(guī)劃并指出解的形式：(1) 【解】最優(yōu)解X（3，2）；最優(yōu)值Z=19 (2) 【解】有多重解。最優(yōu)解X（1）（0，5/4）；X（2）（3，1/2）最優(yōu)值Z=5(3) 【解】最優(yōu)解

8、X（4，1）；最優(yōu)值Z=10，有唯一最優(yōu)解(4) 【解】最優(yōu)解X（2，3）；最優(yōu)值Z=26，有唯一最優(yōu)解(5) 【解】無界解。 (6)【解】無可行解。1.7 將下列線性規(guī)劃化為標準形式 (1) 【解】（1）令為松馳變量 ，則標準形式為 (2) 【解】（2）將絕對值化為兩個不等式，則標準形式為 (3) 【解】方法1：方法2：令則標準型為(4) 【解】令，線性規(guī)劃模型變?yōu)闃藴市蜑?.8 設線性規(guī)劃取基分別指出對應的基變量和非基變量，求出基本解，并說明是不是可行基【解】B1：x1、x3為基變量，x2、x4為非基變量,基本解為X=（15，0，10，0）T，B1是可行基。B2：x2、x4是基變量，x1、

9、x3為非基變量，基本解X=（0，20，0，100）T，B2是可行基。1.9分別用圖解法和單純形法求解下列線性規(guī)劃，指出單純形法迭代的每一步的基可行解對應于圖形上的那一個極點 (1)【解】圖解法單純形法：C(j)1300bRatioC(i)BasisX1X2X3X40X3-2110220X42301124C(j)-Z(j)130003X2-21102M0X480-3160.75C(j)-Z(j)70-3063X2010.250.257/21X110-0.3750.1253/4C(j)-Z(j)00-0.375-0.87545/4對應的頂點：基可行解可行域的頂點X(1)=（0，0，2，12）、X(

10、2)=（0，2，0，6，）、X(3)=（、（0，0）（0，2）最優(yōu)解 (2) 【解】圖解法單純形法：C(j)-3-5000bRatioBasisC(i)X1X2X3X4X5X301210063X4014010102.5X501100144C(j)-Z(j)-3-50000X300.501-0.5012X2-50.25100.2502.510X500.7500-0.2511.52C(j)-Z(j)-1.75001.250-12.5X1-3102-102MX2-501-0.50.5024X5000-1.50.5100C(j)-Z(j)003.5-0.50-16X1-310-1022X2-50110

11、-12X4000-3120C(j)-Z(j)00201-16對應的頂點：基可行解可行域的頂點X(1)=（0，0，6，10，4）、X(2)=（0，2.5，1，0，1.5，）、X(3)=（2，2，0，0，0）X(4)=（2，2，0，0，0）（0，0）（0，2.5）(2，2)（2，2）最優(yōu)解：X=（2，2，0，0，0）；最優(yōu)值Z16該題是退化基本可行解，5個基本可行解對應4個極點。1.10用單純形法求解下列線性規(guī)劃(1)【解】單純形表：C(j)34100R. H. S.RatioBasisC(i)X1X2X3X4X5X402311044/3X501220133/2C(j)-Z(j)341000X24

12、2/311/31/30 4/32X50-1/304/3-2/311/3MC(j)-Z(j)1/30-1/3-4/3016/3X1313/21/21/202X5001/23/2-1/211C(j)-Z(j)0-1/2-1/2-3/20-6最優(yōu)解：X=（2，0，0，0，1）；最優(yōu)值Z6 (2) 【解】單純形表：C(j)21-35000R. H. S.RatioBasisC(i)X1X2X3X4X5X6X7X50153-710030MX603-1110101010X702-6-14001205C(j)-Z(j)21-35000X509/2-11/25/40107/465MX605/21/25/400

13、1-1/4510X451/2-3/2-1/41001/45MC(j)-Z(j)-1/217/2-7/4000-5/4X50320150111-1120MX21515/2002-1/21010X45807/2103-1/220MC(j)-Z(j)-430-2300-173因為730并且ai70,原問題無可行解。兩階段法第一階段：數(shù)學模型為C(j)000001R. H. S.RatioBasisC(i)X1X2X3X4X5X6X3053100091.8X40-56010015MX612100-1152.5C(j)-Z(j)-2-10010514X1013/51/50009/5X4009110024

14、X610-1/5-2/50-117/5C(j)-Z(j)01/52/5010因為X60,原問題無可行解。圖解法如下： (4) 【解】大M法。X7是人工變量，數(shù)學模型為Cj425000MR.H.S.RatioCBXBX1X2X3X4X5X6X70X46-141100X53-3-518MX7121112010C(j)-Z(j)425* Big MM2MM10X413/29/21-1/21/2200X59/2-7/21-3/23/2382X21/211/2-1/21/210C(j)-Z(j)341-1* Big M-15X313/912/9-1/91/940/90X586/97/91-17/917/

15、9482/92X2-2/91-1/9-4/94/970/9C(j)-Z(j)-25/9-8/913/9-13/9* Big M-1無界解。兩階段法。第一階段：Cj0001R.H.S.RatioCBXBX1X2X3X4X5X6X70X46-141100X53-3-5181X7121112010C(j)-Z(j)12110X413/29/21-1/21/2200X59/2-7/21-3/23/2382X21/211/2-1/21/210C(j)-Z(j)1第二階段：Cj425000R.H.S.RatioCBXBX1X2X3X4X5X60X413/29/21-1/2200X59/2-7/21-3/2

16、381X21/211/2-1/210C(j)-Z(j)7/29/21/20X313/912/9-1/940/90X586/97/91-17/9482/92X2-2/91-1/9-4/970/9C(j)-Z(j)-3-11原問題無界解。1.12 在第1.9題中，對于基求所有變量的檢驗數(shù),并判斷B是不是最優(yōu)基【解】, B不是最優(yōu)基，可以證明B是可行基。1.13已知線性規(guī)劃的最優(yōu)基為，試用矩陣公式求（1）最優(yōu)解；(2)單純形乘子；(3)(4)【解】則(1)(2)(3)(4)注：該題有多重解：X(1)=(0，5，0，5/2)X(2)=(0，10/3，10/3，0)X(3)=(10，0，0，0)，x2是

17、基變量，X(3)是退化基本可行解Z501.14 已知某線性規(guī)劃的單純形表128, 求價值系數(shù)向量C及目標函數(shù)值Z表128Cjc1c2c3c4c5c6c7bCBXBx1x2x3x4x5x6x73x4012130244x1101020100 x601404123/2j0110102【解】由有c21（31400（1）2c31（324（1）04）1c51（3（3）420（4）0c7-2（324(1)02）0則C(4,2,1,3,0,0,0,)，Z=CBXB=12 1.15 已知線性規(guī)劃的最優(yōu)單純形表如表129所示，求原線性規(guī)劃矩陣C、A、及b，最優(yōu)基B及表129Cjc1c2c3c4c5bCBXBx1x

18、2x3x4x5c1x11041/61/156c2x201301/52j00123【解】由c4c50，由公式得由 得 由 得 1.16思考與簡答（1）在例1.2中，如果設xj(j=1，2，7)為工作了5天后星期一到星期日開始休息的營業(yè)員，該模型如何變化。（2）在例1.3中，能否將約束條件改為等式；如果要求余料最少，數(shù)學模型如何變化；簡述板材下料的思路。（3）在例1.4中，若允許含有少量雜質，但雜質含量不超過1，模型如何變化。（4）在例1.6中，假定同種設備的加工時間均勻分配到各臺設備上，要求一種設備每臺每天的加工時間不超過另一種設備任一臺加工時間1小時，模型如何變化。(5)在單純形法中，為什么說

19、當時線性規(guī)劃具有無界解。(6)選擇出基變量為什么要遵循最小比值規(guī)則，如果不遵循最小比值規(guī)則會是什么結果。（7）簡述大M法計算的基本思路，說明在什么情形下線性規(guī)劃無可行解。（8）設X(1)、X(2)、X(3)是線性規(guī)劃的3個最優(yōu)解，試說明也是線性規(guī)劃的最優(yōu)解。（9）什么是基本解、可行解、基本可行解、基本最優(yōu)解，這四個解之間有何關系。（10）簡述線性規(guī)劃問題檢驗數(shù)的定義及其經(jīng)濟含義。返回頂部第2章 線性規(guī)劃的對偶理論2.1某人根據(jù)醫(yī)囑，每天需補充A、B、C三種營養(yǎng)，A不少于80單位，B不少于150單位，C不少于180單位此人準備每天從六種食物中攝取這三種營養(yǎng)成分已知六種食物每百克的營養(yǎng)成分含量及食

20、物價格如表2-22所示（1）試建立此人在滿足健康需要的基礎上花費最少的數(shù)學模型；（2）假定有一個廠商計劃生產(chǎn)一中藥丸，售給此人服用，藥丸中包含有A，B，C三種營養(yǎng)成分試為廠商制定一個藥丸的合理價格，既使此人愿意購買，又使廠商能獲得最大利益，建立數(shù)學模型表2-22含量 食物營養(yǎng)成分一二三四五六需要量A1325144081180B24930251215150C1872134100180食物單價（元/100g）0.50.40.80.90.30.2【解】（1）設xj為每天第j種食物的用量，數(shù)學模型為（2）設yi為第i種單位營養(yǎng)的價格，則數(shù)學模型為2.2寫出下列線性規(guī)劃的對偶問題（1） 【解】（2） 【

21、解】（3） 【解】（4） 【解】對偶問題為： 2.3考慮線性規(guī)劃(1)說明原問題與對偶問題都有最優(yōu)解；(2)通過解對偶問題由最優(yōu)表中觀察出原問題的最優(yōu)解；(3)利用公式CBB1求原問題的最優(yōu)解；(4)利用互補松弛條件求原問題的最優(yōu)解【解】(1)原問題的對偶問題為容易看出原問題和對偶問題都有可行解，如X(2，1)、Y(1，0，1)，由定理2.4知都有最優(yōu)解。(2)對偶問題最優(yōu)單純形表為C(j)42700R. H. S.BasisC(i)y1y2y3y4y5y370-1/514/5-1/528/5y1417/50-3/52/54/5C(j)-Z(j)0-11/50-16/5-1/5w=42.4對偶

22、問題的最優(yōu)解Y(4/5,0,28/5)，由定理2.6，原問題的最優(yōu)解為X=(16/5，1/5)，Z42.4（3）CB=(7,4), (4)由y1、y3不等于零知原問題第一、三個約束是緊的，解等式得到原問題的最優(yōu)解為X=(16/5，1/5)。2.4證明下列線性規(guī)劃問題無最優(yōu)解證明：首先看到該問題存在可行解，例如x=(2,1,1)，而上述問題的對偶問題為由約束條件知y10，由約束條件當y20知y11，對偶問題無可行解，因此原問題也無最優(yōu)解(無界解)。2.5已知線性規(guī)劃的最優(yōu)解，求對偶問題的最優(yōu)解【解】其對偶問題是：由原問題的最優(yōu)解知，原問題約束的松弛變量不等于零()，x1、x3不等于零，則對偶問題

23、的約束、約束為等式，又由于知y30；解方程得到對偶問題的最優(yōu)解Y=(5/2,5/2,0)；w55/227.52.6用對偶單純形法求解下列線性規(guī)劃 【解】將模型化為對偶單純形表：cj34600CBXBX1X2X3X4X5b00X4X512223110011012C(j)-Z(j)34600003X4X101115/21/2101/21/246C(j)-Z(j)019/203/21853X2X101105/22111/2142C(j)-Z(j)0021122b列全為非負，最優(yōu)解為x(2，4，0)；Z22 【解】將模型化為5400 b XB CB X1 X2 X3 X4 X30-1-110-6 X4

24、021012CjZj3400 X1311-106 X400-121-10CjZj0130 X131011-4 X2401-2-110CjZj0051出基行系數(shù)全部非負，最小比值失效，原問題無可行解。【解】將模型化為 cj24000 b XBCB X1 X2 X3 X4 X5 X302310024 X40-1-2010-10 X50-1-3001-18CjZj24000 X30101016 X40-1/3001 2/32 X241/3100 1/36CjZj2/30004/3最優(yōu)解X=(0，6)；Z24【解】將模型化為Cj235600 b XB CB X1 X2 X3 X4 X5 X6 X50-

25、1-2-3-410-2 X60-21-1301-3CjZj235600 X231/213/22-1/201 X60-5/20-5/211/21-4CjZj1/201/203/20 X23-11013/5-1/53/5-7/5 X35101-2/5-1/5-2/58/5CjZj0001/58/51/5 X121-10-13/51/5-3/57/5 X3501111/5-2/51/51/5CjZj0001/58/51/5 X12101-2/5-1/5-2/58/5 X2301111/5-2/51/51/5CjZj0001/58/51/5原問題有多重解：X(1)(7/5，0，1/5，)；最優(yōu)解X(2

26、)(8/5，1/5，0)；Z19/5如果第一張表X6出基，則有Cj235600 b XB CB X1 X2 X3 X4 X5 X6 X50 -1-2-3-410-2 X60 -21-1301-3 CjZj235600 X500-5/2-5/2-11/21-1/2-1/2 X121-1/21/2-3/20-1/23/2CjZj044901 X2301111/5-2/51/51/5 X12101-7/5-1/5-2/58/5CjZj0001/58/51/527某工廠利用原材料甲、乙、丙生產(chǎn)產(chǎn)品A、B、C，有關資料見表2-23表2-23產(chǎn)品材料消耗材料 產(chǎn)品材料消耗原材料ABC每月可供原材料（Kg）

27、甲乙丙211200123500221600每件產(chǎn)品利潤413（1）怎樣安排生產(chǎn)，使利潤最大（2）若增加1kg原材料甲，總利潤增加多少（3）設原材料乙的市場價格為1.2元/Kg，若要轉賣原材料乙，工廠應至少叫價多少，為什么？（4）單位產(chǎn)品利潤分別在什么范圍內(nèi)變化時，原生產(chǎn)計劃不變（5）原材料分別單獨在什么范圍內(nèi)波動時，仍只生產(chǎn)A和C兩種產(chǎn)品（6）由于市場的變化，產(chǎn)品B、C的單件利潤變?yōu)?元和2元，這時應如何調整生產(chǎn)計劃（7）工廠計劃生產(chǎn)新產(chǎn)品D，每件產(chǎn)品D消耗原材料甲、乙、丙分別為2kg，2kg及1kg，每件產(chǎn)品D應獲利多少時才有利于投產(chǎn)【解】（1）設 x1、x2、x3分別為產(chǎn)品A、B、C的月生

28、產(chǎn)量，數(shù)學模型為最優(yōu)單純形表：C(j)413000R.H.S.Ratio XB CBX1X2X3X4X5X6X1411/503/5-1/5020X3303/51-1/52/50160X60000-101400C(j)-Z(j)0-8/50-9/5-2/50Z=560最優(yōu)解X=（20，0，160），Z=560。工廠應生產(chǎn)產(chǎn)品A20件，產(chǎn)品C160種，總利潤為560元。（2）由最優(yōu)表可知，影子價格為,故增加利潤1.8元。（3）因為y2=0.4，所以叫價應不少于1.6元。（4）依據(jù)最優(yōu)表計算得（5）依據(jù)最優(yōu)表計算得（6）變化后的檢驗數(shù)為2=1,4=-2,5=0。故x2進基x1出基,得到最最優(yōu)解X=(

29、0,200,0)，即只生產(chǎn)產(chǎn)品B 200件,總利潤為600元。C(j)432000R.H.S.Ratio XB CBX1X2X3X4X5X6X1411/503/5-1/5020100X3203/51-1/52/50160800/3X60000-101400MC(j)-Z(j)010-200560X225103-10100MX33-301-210100100X60000-101400MC(j)-Z(j)-500-510X22211100200X40-301-210100X60000-101400C(j)-Z(j)-20-1-300(7)設產(chǎn)品D的產(chǎn)量為x7, 單件產(chǎn)品利潤為c7，只有當時才有利于

30、投產(chǎn)。則當單位產(chǎn)品D的利潤超過4.4元時才有利于投產(chǎn)。28對下列線性規(guī)劃作參數(shù)分析（1） 【解】0時最優(yōu)解X=(4,3,0)；最優(yōu)表：C(j)35000R. H. S.BasisC(i)X1X2X3X4X5X13101004X250100.503X5000-3-110C(j)-Z(j)00-3-2.5027將參數(shù)引入到上表：C(j)325000R.H.S.BasisC(i)X1X2X3X4X5X132101004X250100.503X5000-3-110C(j)-Z(j)0032-2.50.5027當320及-2.50.50時最優(yōu)基不變，有1.55。當5時X4進基X2出基，用單純形法計算。參

31、數(shù)變化與目標值變化的關系如下表所示。FromToFromTo LeavingEnteringRange(Vector)(Vector)OBJ ValueOBJ ValueSlopeVariableVariable10527525X2X425M52M830-1.52719.55X1X34-1.5-M19.5M-3目標值變化如下圖所示。0(-1.5,Z=19.5)(5,Z=52)(0,Z=27)（2）【解】0時最優(yōu)解X=(4,3,0)，Z27；最優(yōu)表：C(j)35000R. H. S.BasisC(i)X1X2X3X4X5X13101004X250100.503X5000-3-110C(j)-Z(

32、j)00-3-2.5027替換最優(yōu)表的右端常數(shù)，得到下表。C(j)35000R.H.S.BasisC(i)X1X2X3X4X5X13101004X250100.503X5000-3-115C(j)-Z(j)00-3-2.504時問題不可行，40時X5出基X3進基得到下表：C(j)35000R.H.S.BasisC(i)X1X2X3X4X5X13100-1/31/34-2/3X250101/203X300011/3-1/35/3C(j)-Z(j)000-3/2-106時為最優(yōu)解。6時Z15。6時X1出基X4進基得到下表：C(j)35000R.H.S.BasisC(i)X1X2X3X4X5X40-3001-1-12+2X253/21001/29-X30101004+C(j)-Z(j)9時最優(yōu)解X=(0，0，13，6，0)，Z=0；9時無可行解。綜合分析如下表所示。FromToFromTo LeavingEnteringR