運(yùn)籌學(xué)作業(yè)王程130404026

1、運(yùn)籌學(xué)作業(yè)王程信管1302130404026目錄運(yùn)籌學(xué)作業(yè)1第一章 線性規(guī)劃及單純形法3第二章 線性規(guī)劃的對偶理論與靈敏度分析24第三章 運(yùn)輸問題53第四章 目標(biāo)規(guī)劃63第五章 整數(shù)規(guī)劃72第六章 非線性規(guī)劃84第七章 動態(tài)規(guī)劃93第八章 圖與網(wǎng)絡(luò)分析96第九章 網(wǎng)絡(luò)計劃98第一章 線性規(guī)劃及單純形法1.1分別用圖解法和單純形法求下列線性規(guī)劃問題，指出問題具有唯一最優(yōu)解、無窮多最優(yōu)解、無界解還是無可行解；當(dāng)具有限最優(yōu)解時，指出單純形表中的各基可行解對應(yīng)圖解法中可行域的哪一頂點(diǎn)。 解：圖解法： 當(dāng)經(jīng)過點(diǎn)時，最小，且有無窮多個最優(yōu)解。 圖解法： 該問題無可行解。 圖解法： 當(dāng)經(jīng)過點(diǎn)時，取得唯一最優(yōu)

2、解。 單純形法： 在上述問題的約束條件中分別加入松弛變量， 化為標(biāo)準(zhǔn)型： 由線性規(guī)劃問題的標(biāo)準(zhǔn)型可列出單純初始形表逐步迭代，計算結(jié)果如下表所示： 圖解法： 當(dāng)經(jīng)過點(diǎn)時，取得唯一最優(yōu)解。1.2將下述線性規(guī)劃問題化成標(biāo)準(zhǔn)形式。 1.3 對下述線性規(guī)劃問題找出所有基解，指出哪些是基可行解，并確定最優(yōu)解。解：（1）該線性規(guī)劃問題的全部基解見下表中的，打者為基可行解，注*者為最優(yōu)解，z* =36。（2）該線性規(guī)劃問題的標(biāo)準(zhǔn)形式為： 其全部基解見下表中的，打者為基可行解，注*者為最優(yōu)解，z*=5。 1.4 題1.1（3）中，若目標(biāo)函數(shù)變?yōu)椋懻摰闹等绾巫兓?，使該問題可行域的每個頂點(diǎn)依次使目標(biāo)函數(shù)達(dá)到最優(yōu)。

3、解：由目標(biāo)函數(shù)可得： ，其中 。當(dāng) 時，可行域的頂點(diǎn)a使目標(biāo)函數(shù)達(dá)到最優(yōu)；當(dāng) 時，可行域的頂點(diǎn)b使目標(biāo)函數(shù)達(dá)到最優(yōu)；當(dāng) 時，可行域的頂點(diǎn)c使目標(biāo)函數(shù)達(dá)到最優(yōu)；當(dāng)或時，最優(yōu)解為o點(diǎn) 。 1.6 分別用單純形法中的大m法和兩階段法求解下列線性規(guī)劃問題，并指出屬哪一類解。 其中m是一個任意大的正數(shù)，據(jù)此可列出初始單純形表如下： cj23100mmicbxbbx1x2x3x4x5x6x7mmx6x786134220-100-1100123cj-zj2-4m3-6m1-2mmm003mx2x7221/45/2101/2-1-1/41/20-11/4-1/20184/5cj-zj32x2x19/54/50

4、1103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5cj-zj0001/21/2m-1/2m-1/2由單純形表的計算結(jié)果得：最優(yōu)解 ,目標(biāo)函數(shù)最優(yōu)值 x存在非基變量檢驗數(shù)，故該線性規(guī)劃問題有無窮多最優(yōu)解。 據(jù)此可列出單純初始形表如下：cj0000011icbxbbx1x2x3x4x5x6x711x6x786134220-100-1100123cj-zj-4-6-2110001x2x7221/45/2101/2-1-1/41/20-11/4-1/20184/5cj-zj00x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-

5、1/102/5cj-zj0000011第一階段求得的最優(yōu)解，目標(biāo)函數(shù)的最優(yōu)值，因人工變量，所以是原線性規(guī)劃問題的基可行解。于是可以進(jìn)行第二階段計算，將第一階段的最終表中的人工變量取消，并填入原問題的目標(biāo)函數(shù)的系數(shù)，如下表：cj23100icbxbbx1x2x3x4x532x2x19/54/501103/5-2/5-3/101/51/10-2/5 cj-zj0001/21/2由表中計算可知，原線性規(guī)劃問題的最優(yōu)解，目標(biāo)函數(shù)的最優(yōu)值，由于存在非基變量檢驗數(shù)，故該線性規(guī)劃問題有無窮多最優(yōu)解。 其中m是一個任意大的正數(shù)，據(jù)此可列出單純形表如下：cj101512000-micbxbbx1x2x3x4x5

6、x6x700-mx4x5x791555-52361115110001000-10019/5-5/2cj-zj10+2m15+m12+m00-m0100-mx1x5x79/5247/51003/59-1/51/5163/51/51-2/501000-100193/27/3cj-zj1012-mx1x3x73/23/21/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001cj-zj0 由單純性表的最終表可以看出，所有非基變量檢驗數(shù) ，且存在人工變量 ，故原線性規(guī)劃問題無可行解。據(jù)此可列出單純初始形表如下：cj0000001icbxbbx

7、1x2x3x4x5x6x7001x4x5x791555-52361115110001000-10019/5-5/2cj-zj-2-1-100101001x1x5x79/5247/51003/59-1/51/5163/51/51-2/501000-100193/27/3cj-zj-1/53/5-2/51001x1x3x73/23/21/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001cj-zj0 7/163/801 第一階段求得最優(yōu)解，因人工變量 ，且非基變量檢驗數(shù)，所以原線性規(guī)劃問題無可行解。1.5 考慮下述線性規(guī)劃問題： 解：（

8、1）上界對應(yīng)的模型如下（c，b取大，a取小） 最優(yōu)值（上界）為：21；（2）下界對應(yīng)的模型如下（c，b取小，a取大） 最優(yōu)值（下界）為：6.4。1.7 已知某線性規(guī)劃問題的初始單純形表和用單純形法迭代后得到表1-21，試求括弧中未知數(shù)的值。 1.8 若x,x(2)均為某線性規(guī)劃問題的最優(yōu)解，證明在這兩點(diǎn)連線上的所有點(diǎn)也是該問題的最優(yōu)解。 1.9 考慮線性規(guī)劃問題 模型中為參數(shù)，要求： 組成兩個新的約束，根據(jù)式和式，以為基變量，列出初始單純形表；解： 在表中，假定 ，則 為何值時，為問題的最優(yōu)基； 在表中，假定 ，則 為何值時，為問題的最優(yōu)基。 1.10 試述線性規(guī)劃模型中“線性”二字的含義，并

9、用實例說明什么情況下線性的假設(shè)將被違背。答：線性的含義：一是嚴(yán)格的比例性，如生產(chǎn)某產(chǎn)品對資源的消耗量和可獲取的利潤，同其生產(chǎn)數(shù)量嚴(yán)格成比例；二是可疊加性，如生產(chǎn)多種產(chǎn)品時，可獲取的總利潤使各項產(chǎn)品的利潤之和，對某項資源的消耗量應(yīng)等于各產(chǎn)品對該資源的消耗量之和；三是可分性，即模型中的變量可以取值為小數(shù)、分?jǐn)?shù)或某一實數(shù)；四是確定性，指模型中的參數(shù)cj,aij,bi 均為確定的常數(shù)。 很多實際問題往往不符合上述條件，例如每件產(chǎn)品售價3元，但成批購買就可以得到折扣優(yōu)惠。1.11 判斷下列說法是否正確，為什么？ 含n個變量m個約束的標(biāo)準(zhǔn)型的線性規(guī)劃問題，基解數(shù)恰好為個； 答：錯誤。基本解的個數(shù)=基的個數(shù)

10、 線性規(guī)劃問題的可行解如為最優(yōu)解，則該可行解一定為基可行解； 答：錯誤。當(dāng)有唯一最優(yōu)解時，最優(yōu)解是可行域頂點(diǎn)，對應(yīng)基本可行解；當(dāng)有無窮多最優(yōu)解時，除了其中的可行域頂點(diǎn)對應(yīng)基本可行解外，其余最優(yōu)解不是基本可行解。 如線性規(guī)劃問題存在可行域，則可行域一定包含坐標(biāo)的原點(diǎn)； 答：錯誤。如果約束條件中有一個約束所對應(yīng)的區(qū)域不包含坐標(biāo)的原點(diǎn)，則即使有可行域，也不包含坐標(biāo)的原點(diǎn)。 單純形法迭代計算中，必須選取同最大檢驗數(shù)對應(yīng)的變量作為換入基的變量。答：錯誤。若此時最大檢驗數(shù)，可是 ，則問題是無界解，計算結(jié)束。1.12 線性規(guī)劃問題,如是該問題的最優(yōu)解，又為某一常數(shù)，分別討論下列情況時最優(yōu)解的變化。 目標(biāo)函數(shù)

11、變?yōu)椋?目標(biāo)函數(shù)變?yōu)椋?目標(biāo)函數(shù)變?yōu)椋s束條件變?yōu)?。解： 最優(yōu)解不變； c為常數(shù)時最優(yōu)解不變，否則可能發(fā)生變化； 最優(yōu)解變?yōu)椋簒/。1.13 某飼養(yǎng)場飼養(yǎng)動物出售，設(shè)每頭動物每天至少需要700g蛋白質(zhì)、30g礦物質(zhì)、100mg維生素?，F(xiàn)有五種飼料可供選用，各種飼料每kg營養(yǎng)成分含量及單價如表1-22所示。要求確定既滿足動物生長的營養(yǎng)需要，又使費(fèi)用最省的選用飼料的方案。 最優(yōu)解為 1.14 遼源街郵局從周一到周日每天所需的職員人數(shù)如下表1-23所示。職員分別安排在周內(nèi)某一天開始上班，并連續(xù)工作5天，休息2天。要求確定： 該郵局至少應(yīng)配備多少職員，才能滿足值班需要； 因從周一開始上班的，雙休日都

12、能休息；周二或周日開始上班的，雙休日內(nèi)只能有一天得到休息；其他時間開始上班的，兩個雙休日都得不到休息，很不合理。因此郵局準(zhǔn)備對每周上班的起始日進(jìn)行輪換（但從起始日開始連續(xù)上5天班的規(guī)定不變），問如何安排輪換，才能做到在一個星期內(nèi)每名職工享受到同等的雙休日的休假天數(shù)； 該郵局職員中有一名領(lǐng)班，一名副領(lǐng)班。為便于領(lǐng)導(dǎo)，規(guī)定領(lǐng)班于每周一、三、四、五、六上班，副領(lǐng)班于一、二、三、五、日這5天上班。據(jù)此試重新對上述要求和建模和求解。 對這23名職工分別編號， ，以23周為一個周期，這23名職工上班安排見下表。 此時只需在每天人數(shù)中減去領(lǐng)班和副領(lǐng)班兩人即可，重現(xiàn)建模如下：1.15 一艘貨輪分前、中、后三個

13、艙位，它們的容積與最大允許載重量如表1-24所示?，F(xiàn)有三種貨物待運(yùn)，已知有關(guān)數(shù)據(jù)列于表1-25。 又為了艙運(yùn)安全，前、中、后艙的實際載重量大體積保持各艙最大允許載重量的比例關(guān)系。具體要求：前、后艙分別與中艙之間載重量比例的偏差不超過15%，前、后艙之間不超過10%。問該貨輪應(yīng)裝載a、b、c各多少件運(yùn)費(fèi)收入為最大？試建立這個問題的線性規(guī)劃模型。1.16 長城通信公司擬對新推出的一款手機(jī)收費(fèi)套餐服務(wù)進(jìn)行調(diào)查，以便進(jìn)一步設(shè)計改進(jìn)。調(diào)查對象設(shè)定為商界人士及大學(xué)生，要求：總共調(diào)查600人，其中大學(xué)生不少于250人；方式分電話調(diào)查和問卷調(diào)查，其中問卷調(diào)查人數(shù)不少于30%；對大學(xué)生電話調(diào)查80%以上應(yīng)安排在

14、周六或周日，對商界人士電話調(diào)查80%以上應(yīng)安排在周一至周五；問卷調(diào)查時間不限。已知有關(guān)調(diào)查費(fèi)用如表1-26所示，問該公司應(yīng)如何安排調(diào)查，使總的費(fèi)用為最省。1.17 生產(chǎn)存儲問題。某廠簽訂了5種產(chǎn)品（i=1，5）上半年的交貨合同。已知各產(chǎn)品在第j月（j=1，6）的合同交貨量dij ，該月售價sij 、成本價cij 及生產(chǎn)1件時所需工時aij 。該廠第j月的正常生產(chǎn)工時為tj，但必要時可加班生產(chǎn)，第j月允許的最多加班工時不超過tj，并且加班時間內(nèi)生產(chǎn)出來的產(chǎn)品每件成本增加額外費(fèi)用cij元。若生產(chǎn)出來的產(chǎn)品當(dāng)月不交貨，每件庫存1個月交存儲費(fèi)pi元。試為該廠設(shè)計一個保證完成合同交貨，又使上半年預(yù)期盈利

15、總額為最大的生產(chǎn)計劃安排。1.18 宏銀公司承諾為某建設(shè)項目從2003年起的4年中每年年初分別提供以下數(shù)額貸款：2003年100萬元，2004年150萬元，2005年120萬元，2006年110萬元。以上貸款資金均需于2002年年底前籌集齊。但為了充分發(fā)揮這筆資金的作用，在滿足每年貸款額情況下，可將多余資金分別用于下列投資項目： 于2003年年初購買a種債券，期限3年，到期后本息合計為投資額的140%，但限購60萬元； 于2003年年初購買b種債券，期限2年，到期后本息合計為投資額的125%，且限購90萬元； 于2004年年初購買c種債券，期限2年，到期后本息合計為投資額的130%，但限購50

16、萬元； 于每年年初將任意數(shù)額的資金存放于銀行，年息4%，于每年年底取出。求宏銀公司應(yīng)如何運(yùn)用好這筆籌集到的資金，使2002年年底需籌集到的資金數(shù)額為最少。1.19 紅豆服裝廠新推出一款時裝，據(jù)經(jīng)驗和市場調(diào)查，預(yù)測今后6個月對該款時裝的需求為：1月3000件，2月3600件，3月4000件，4月4600件，5月4800件，6月5000件。生產(chǎn)每件需熟練工人工作4h，耗用原材料150元，售價為240元/件。該廠1月初有熟練工80人，每人每月工作160h。為適應(yīng)生產(chǎn)需要，該廠可招收新工人培訓(xùn)，但培訓(xùn)一名新工人需占用熟練工人50h用于指導(dǎo)操作，培訓(xùn)期為一個月，結(jié)束后即可上崗。熟練工人每月工資2000元

17、，新工人培訓(xùn)期間給予生活補(bǔ)貼800元，轉(zhuǎn)正后工資與生產(chǎn)效率同熟練工人。又熟練工人（含轉(zhuǎn)正一個月后的新工人）每月初有2%因各種原因離職。已知該廠年初已加工出400件該款時裝作為庫存，要求6月末存庫1000件。又每月生產(chǎn)出來時裝如不在當(dāng)月交貨，庫存費(fèi)用為每件每月10元。試為該廠設(shè)計一個滿足各月及6月末庫存要求，又使16月總收入為最大的勞動力安排方案。第二章 線性規(guī)劃的對偶理論與靈敏度分析2.1 寫出下列線性規(guī)劃問題的對偶問題，并以對偶問題為原問題，再寫出對偶的對偶問題。 2.2 判斷下列說法是否正確，并說明為什么。如果線性規(guī)劃的原問題存在可行解，則其對偶問題也一定存在可行解；答：錯誤。如果原問題是

18、無界解，則對偶問題無可行解。如果線性規(guī)劃的對偶問題無可行解，則原問題也一定無可行解；答：錯誤。如果對偶問題無可行解，也可能是因為原問題是無界解。在互為對偶的一對原問題與對偶問題中，不管原問題是求極大或極小，原問題可行解的目標(biāo)函數(shù)值一定不超過其對偶問題可行解的目標(biāo)函數(shù)值；答：錯誤。如果原問題是求極小，則結(jié)論相反。任何線性規(guī)劃問題具有唯一的對偶問題。答：正確。2.5 已知某求極大線性規(guī)劃問題用單純形法求解時的初始單純形表及最終單純形表如表2-30所示，求表中各括號內(nèi)未知數(shù)(a)(l)的值。解：l=1，k=0，a=2，c=3，h=-1/2，b=10，e=5/4，f=-1/2，d=1/4，g=-3/4

19、，i=-1/4，j=-1/4.2.6 給出線性規(guī)劃問題 寫出其對偶問題；用圖解法求解對偶問題；利用的結(jié)果及根據(jù)對偶問題性質(zhì)寫出原問題最優(yōu)解。解：其對偶問題為： 圖解法求解： （3）根據(jù)互補(bǔ)松弛型性質(zhì)可以得到最優(yōu)解 2.7 給出線性規(guī)劃問題 寫出其對偶問題；利用對偶問題性質(zhì)證明原問題目標(biāo)函數(shù)值 。解：其對偶問題為： 易得 是對偶問題的一個可行解，帶入目標(biāo)函數(shù)得 ，故原問題的目標(biāo)函數(shù)值。2.8 已知線性規(guī)劃問題 試根據(jù)對偶問題性質(zhì)證明上述線性規(guī)劃問題目標(biāo)函數(shù)值無界。 2.9 給出線性規(guī)劃問題 要求：寫出其對偶問題；已知原問題最優(yōu)解為,試根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解。 解：其對偶問題為：

20、已知原問題最優(yōu)解為，帶入原問題，第4個約束不等式成立，故。又由于大于0，上面對偶問題前3個約束取等號，故得到最優(yōu)解：。2.10 已知線性規(guī)劃問題a和b如下： 試分別寫出同間的關(guān)系式。解： .2.11 用對偶單純形法求解下列線性規(guī)劃問題。 解：先將問題改寫為： 列出單純形表，用對偶單純形法求解步驟進(jìn)行計算過程如下：由上表可得原問題最優(yōu)解為，代入目標(biāo)函數(shù)得 。先將問題改寫為： 列出單純形表，用對偶單純形法求解步驟進(jìn)行計算過程如下：由上表可得原問題最優(yōu)解為，代入目標(biāo)函數(shù)得 。2.12 考慮如下線性規(guī)劃問題： 要求：寫出其對偶問題；用對偶單純形法求解原問題；用單純形法求解其對偶問題；對比與中每步計算得

21、到的結(jié)果。解：其對偶問題為： 先將問題改寫為 列出單純形表，用對偶單純形法求解步驟進(jìn)行計算過程如下：由上表可得原問題最優(yōu)解為，代入目標(biāo)函數(shù)得 。 用單純形法求解其對偶問題：由上表可得對偶問題最優(yōu)解為，代如目標(biāo)函數(shù)。2.13 已知線性規(guī)劃問題：先用單純形法求出最優(yōu)解，再分析在下列條件單獨(dú)變化的情況下最優(yōu)解的變化。 目標(biāo)函數(shù)變?yōu)? 約束右端項由變?yōu)椋?增添一個新的約束條件。解：先用單純形法計算如下： 由上表可得最優(yōu)解為 當(dāng)目標(biāo)函數(shù)變?yōu)闀r，反映到最終單純形表上如下表所示：因變量x2 的檢驗數(shù)大于零，故需繼續(xù)用單純形法迭代計算得下表：由上表可得最優(yōu)解變?yōu)?因有 將其反映到最終單純形表中如下表所示：由表

22、可得最優(yōu)解為先將原問題的最優(yōu)解帶入新增約束條件中，因故原問題最優(yōu)解發(fā)生改變。給新增約束條件中加入松弛變量并規(guī)范化得： 以x6 為基變量，將上式反映到最終單純形表中得下表：因上表中x1列不是單位向量，故需進(jìn)行變換，得下表：因上表中對偶問題為可行解，原問題為非可行解，故用對偶單純性法迭代計算得下表：由上表可得最優(yōu)解為2.14 給出線性規(guī)劃問題當(dāng)時用單純形法求解得最終單純形表見表2-31。試分析 當(dāng)時，范圍內(nèi)變化時的變化； 當(dāng)時，范圍內(nèi)變化時的變化。解：將反映到最終單純形表中得下表：在上表中，當(dāng)時，表中解為最優(yōu)，且當(dāng)時，變量的檢驗數(shù)0，用單純形法迭代計算得下表：在上表中，當(dāng)時，表中解為最優(yōu)，且在第一

23、個表中，當(dāng)時，變量的檢驗數(shù)0，用單純形法迭代計算得下表：在上表中，當(dāng)時，表中解為最優(yōu)，且因有 將其反映到最終單純形表中得下表：在上表中，當(dāng)時，表中解為最優(yōu)，且當(dāng)時，表中基變量，這時可用對偶單純形法繼續(xù)迭代計算得下表：在上表中，當(dāng)時，表中解為最優(yōu)，且在第一個表中，當(dāng)時，表中基變量，這時可用對偶單純形法繼續(xù)迭代計算得下表：在上表中，當(dāng)時，表中解為最優(yōu)，且2.15 分析下列線性規(guī)劃問題中，當(dāng)變化時最優(yōu)解的變化，并畫出對的變化關(guān)系圖。 解：先令求得最優(yōu)解，并將反映到最終單純形表中，得下表：上表中，當(dāng)時，表中解為最優(yōu)，且，當(dāng)時，變量的檢驗數(shù)0，用單純形法迭代計算得下表：上表中，當(dāng)時，表中解為最優(yōu)，且，當(dāng)

24、時，變量的檢驗數(shù)0，用單純形法迭代計算得下表：上表中，當(dāng)時，表中解為最優(yōu)，且；下圖表明了目標(biāo)函數(shù)值隨值變化的情況：先令求得最優(yōu)解，并將反映到最終單純形表中，得下表：上表中，當(dāng)時，表中解為最優(yōu)，且，當(dāng)時，變量的檢驗數(shù)0，用單純形法迭代計算得下表：上表中，當(dāng)時，表中解為最優(yōu)，且，當(dāng)時，變量的檢驗數(shù)0，用單純形法迭代計算得下表：上表中，當(dāng)時，表中解為最優(yōu)，且；下圖表明了目標(biāo)函數(shù)值隨值變化的情況：令求解得最終單純形表，又因有 將其反映到最終單純形表中，得下表：上表中當(dāng)時，解為最優(yōu)解且，當(dāng)時，表中基變量將小于零，這時用對偶單純形法繼續(xù)求解得下表： 表中當(dāng)時為最優(yōu)解，且，當(dāng)時，原問題無可行解。 下圖表明了

25、目標(biāo)函數(shù)值隨值變化的情況： 令求解得最終單純形表，又因有 將其反映到最終單純形表中，得下表： 上表中當(dāng)時，解為最優(yōu)解且，當(dāng)時，表中基變量將小于零，這時用對偶單純形法繼續(xù)求解得下表： 表中當(dāng)時為最優(yōu)解，且，當(dāng)時，表中基變量將小于零，這時用對偶單純形法繼續(xù)求解得下表： 表中當(dāng)時為最優(yōu)解，且下圖表明了目標(biāo)函數(shù)值隨值變化的情況： 2.16 某廠生產(chǎn)a、b、c三種產(chǎn)品，其所需勞動力、材料等有關(guān)數(shù)據(jù)見表2-32。要求：確定獲利最大的產(chǎn)品生產(chǎn)計劃；產(chǎn)品a的利潤在什么范圍內(nèi)變動時，上述最優(yōu)計劃不變；如果設(shè)計一種新產(chǎn)品d，單件勞動力消耗為8h，材料消耗為2kg，每件可獲利30元，問該種產(chǎn)品是否值得生產(chǎn)？如果原材

26、料數(shù)量不增，勞動力不足時可以從市場購買，為1.8元/h。問：該廠要不要招收勞動力擴(kuò)大生產(chǎn)，以購多少為宜？解：用x1，x2，x3分別表示該廠生產(chǎn)的三種產(chǎn)品a、b、c的數(shù)量，則對該問題建模如下： 解得最優(yōu)生產(chǎn)計劃為：；設(shè)產(chǎn)品a的利潤為元，反映到最終單純形表上如下：為使上表中的解仍為最優(yōu)解，應(yīng)有 解得 即產(chǎn)品a的利潤在內(nèi)變動時，生產(chǎn)計劃不變。設(shè)該公司生產(chǎn)x6 件產(chǎn)品d，有c6 =30，p6=（8,2）t 。 將其反映到最終單純形表中得下表：因，故用單純形法繼續(xù)迭代計算得下表： 由上表可知產(chǎn)品d值得投入生產(chǎn)，最優(yōu)解為。由可知勞動力的價格是2元，大于市場價格。故應(yīng)該招收勞動力擴(kuò)大生產(chǎn)。當(dāng)招收勞動力為15

27、0h時，利潤達(dá)到最大值3600元。2.17 已知線性規(guī)劃問題： 當(dāng)時求解得最終單純形表見表2-33。確定和的值；當(dāng)時，在什么范圍內(nèi)變化上述最優(yōu)解不變；當(dāng)時，在什么范圍內(nèi)變化上述最優(yōu)基不變。解：由題給可得： 將目標(biāo)函數(shù)的系數(shù)變化直接反映到最終單純形表中，得下表：為使上表中的解仍為最優(yōu)解，應(yīng)有 解得 因有 將其反映到最終單純形表中，其b列數(shù)字為 當(dāng)時問題的最優(yōu)基不變，解得2.18 某文教用品廠利用原材料白坯紙生產(chǎn)原稿紙、日記本和練習(xí)本三種產(chǎn)品。該廠現(xiàn)有工人100人，每天白坯紙的供應(yīng)量為30 000kg。如單獨(dú)生產(chǎn)各種產(chǎn)品時，每個工人每天可生產(chǎn)原稿紙30捆，或日記本30打，或練習(xí)本30箱。已知原材料

28、消耗為：每捆原稿紙用白坯紙10/3kg，每打日記本用白坯紙40/3kg，每箱練習(xí)本用白坯紙80/3kg。已知生產(chǎn)各種產(chǎn)品的贏利為：每捆原稿紙1元，每打日記本2元，每箱練習(xí)本3元。試決定：在現(xiàn)有生產(chǎn)條件下使該廠盈利最大的方案；如白坯紙供應(yīng)量不變，而工人數(shù)量不足時可以從市場上招收臨時工，臨時工費(fèi)用為每人每天40元。問：該廠應(yīng)否招臨時工及招收多少人為宜？解：設(shè)該廠每天生產(chǎn)x1捆原稿紙，x2打日記本，x3箱練習(xí)本，則對該問題建模如下： 用單純形表法計算如下所示： 解得最優(yōu)生產(chǎn)計劃為：.設(shè)應(yīng)招收臨時工人，因有 將其反映到最終單純形表中，其b列數(shù)字為 當(dāng)時問題的最優(yōu)基不變，解得 故該廠應(yīng)從市場招收臨時工2

29、00人/天，新計劃只生產(chǎn)原稿紙9000捆。第三章 運(yùn)輸問題3.1 與一般線性規(guī)劃的數(shù)學(xué)模型相比，運(yùn)輸問題的數(shù)學(xué)模型具有什么特征？答： 運(yùn)輸問題一定有有限最優(yōu)解； 約束條件系數(shù)矩陣的元素只取0或1； 約束條件系數(shù)矩陣的每列有兩個1，而且只有兩個1.前m行中有一個1，后n行中有一個1；對于產(chǎn)銷平衡的運(yùn)輸問題，所有的約束都取等式。3.2 運(yùn)輸問題的基可行解應(yīng)滿足什么條件？是判斷表3-26和表3-27中給出的調(diào)運(yùn)方案可否作為表上作業(yè)迭代法時的基可行解？為什么？答：運(yùn)輸問題基可行解的要求是基變量的個數(shù)等于m+n-1。、表3-26和3-27中給出的方案都不是基可行解，因為數(shù)字格的數(shù)量不等于m+n-1。3.

30、3 試對給出運(yùn)輸問題初始基可行解的最小元素法和vogel法進(jìn)行比較，分析給出的解之質(zhì)量不同的原因。答：最小元素法從最小的價格入手，一開始效果很好，但是到了最后因選擇余地較少效果不好；vogel法從產(chǎn)地和銷地運(yùn)價的級差來考慮問題，總體效果很好，但是方法較復(fù)雜。3.5 用表上作業(yè)法求解運(yùn)輸問題時，在什么情況下會出現(xiàn)退化解？當(dāng)出現(xiàn)退化解釋應(yīng)如何處理？答：當(dāng)數(shù)字格的數(shù)量小于m+n-1時，相應(yīng)的解就是退化解。如果出現(xiàn)了退化解，首先找到同時劃去的行和列，然后在同時劃去的行和列中的某個空格中填入數(shù)字0，只要數(shù)字格的數(shù)量保持在m+n-1個的水平即可。3.6 一般線性規(guī)劃問題具備什么特征才能將其轉(zhuǎn)化為運(yùn)輸問題求

31、解，請舉例說明。答：如果線性規(guī)劃問題有“供”和“需”的關(guān)系，并且有相應(yīng)的“費(fèi)用”，就可以考慮將線性規(guī)劃問題轉(zhuǎn)成運(yùn)輸問題求解。例如，生產(chǎn)滿足需求的問題。3.4 簡要說明用位勢法（對偶變量法）求檢驗數(shù)的原理。解：原問題的檢驗數(shù)也可以利用對偶變量來計算： 其中，ui和vj 就是原問題約束條件對應(yīng)的對偶變量。由于原問題的基變量的個數(shù)等于m+n-1，所以相應(yīng)的檢驗數(shù)就等于0。即有： 由于方程有m+n-1個，而變量有m+n個。所以上面的方程有無窮多個解。任意確定一個變量的值都可以通過方程求出一個解，然后再利用這個解就可以求出非基變量的檢驗數(shù)了。3.7 表3-28和表3-29分別給出了各產(chǎn)地和各銷地的產(chǎn)量和

32、銷量，以及各產(chǎn)地至各銷地的單位運(yùn)價，試用表上作業(yè)法求最優(yōu)解。解：（1）由最小元素法求得初始基可行解為，如下表：閉回路法求檢驗數(shù)，如下表：由于（a2，b4）的檢驗數(shù)小于0，故初始基可行解不是最優(yōu)解。故改進(jìn)解，直到各非基變量的檢驗數(shù)大于0，得最優(yōu)解表為：（2）由于總產(chǎn)量13大于總銷量10，需增加一假想銷地b5，使其銷量為3，如下表，此時產(chǎn)銷平衡。由最小元素法求得初始基可行解為，再進(jìn)行多次迭代運(yùn)算求得最優(yōu)解如下表：3.8 某企業(yè)和用戶簽訂設(shè)備交貨合同，已知該企業(yè)各季度的生產(chǎn)能力、每臺設(shè)備的生產(chǎn)成本和每季度末的交貨量（見表3-30），若生產(chǎn)出的設(shè)備當(dāng)季度不交貨，每臺設(shè)備每年度需支付保管維護(hù)費(fèi)0.1萬元

33、，試問在遵守合同的條件下，企業(yè)應(yīng)如何安排生產(chǎn)計劃，才能使年消耗費(fèi)用最低？解：設(shè)xij為第i季度生產(chǎn)而于第j季度交貨的設(shè)備數(shù)量，可列出該運(yùn)輸問題的如下產(chǎn)銷平衡表和單位運(yùn)價表合一的表。表中d為虛設(shè)的需求地，m為任意大的正數(shù)，表明不允許后面季度的產(chǎn)量用于前面季度交貨。表中小方格內(nèi)的單位運(yùn)價為i季度生產(chǎn)于j季度交貨的每臺設(shè)備消耗的費(fèi)用，為生產(chǎn)成本和保管費(fèi)用之和。用最小元素法得出初始運(yùn)輸方案，如下表所示： 再經(jīng)過迭代得最優(yōu)解見下表： 即最優(yōu)分配計劃為：x11 =15，x22 =20，x23=15，x33=10，x34=20，總的消耗費(fèi)用z*=913.5。3.9 某市有三個面粉廠，它們供給三個面食加工廠所

34、需的面粉。各面粉廠的產(chǎn)量、各面食加工廠加工面粉的能力、各面食加工廠和各面粉廠之間的單位運(yùn)價，均示于表3-31中。假定在第1、2和3面食加工廠制作單位面粉食品的利潤分別為12、16和11，試確定使總效益最大的面粉分配計劃（假定面粉廠和面食加工廠都屬于同一個主管單位）。解：根據(jù)表3-31，用最小元素法得出初始運(yùn)輸方案，再經(jīng)過迭代得最優(yōu)解如下表所示：即最優(yōu)分配計劃為：x1 =0，x3 =20，x1=15，x2=5，x2=20，總收益z*=425。因面粉廠的總產(chǎn)量大于食品廠的總需量，故面粉廠的產(chǎn)量中有10個單位面粉滯留。3.10 表3-32示出一個運(yùn)輸問題及它的一個解，試問：表中給出的解是否為最優(yōu)解？

35、請用位勢法進(jìn)行檢驗。若價值系數(shù)c24 由1變?yōu)?，所給的解是否仍為最優(yōu)解？若不是，請求出最優(yōu)解。若所有價值系數(shù)均增加1，最優(yōu)解是否改變？為什么？若所有價值系數(shù)均乘以2，最優(yōu)解是否改變？為什么？寫出該運(yùn)輸問題的對偶問題，并說明二者最優(yōu)解的關(guān)系。解：用位勢法檢驗后算出各空格的檢驗數(shù)于下表：因為所有的檢驗數(shù)0，故表中給出的解即為最優(yōu)解。若價值系數(shù)c24 由1變?yōu)?，用位勢法求得檢驗數(shù)于下表所示：由于，故知表中解不再是最優(yōu)解，且以為換入變量，它對應(yīng)的閉合回路于下表所示：該閉合回路的偶數(shù)頂點(diǎn)位于格（a1，b2）、（a3，b3）和（a2，b4），由于 故應(yīng)對解作如下調(diào)整： 得到新的基可行解是：，其它為非基

36、變量，這時的最優(yōu)解。現(xiàn)再用位勢法求這個新解各非基變量的檢驗數(shù)，結(jié)果示于下表：由于所有非基變量的檢驗數(shù)全為非負(fù)，故這個解為最優(yōu)解。最優(yōu)解不變，因為這樣做不改變非基變量檢驗數(shù)的值。最優(yōu)解不變，就如同將單位運(yùn)價由元/500g變?yōu)樵?kg，價格增加為原2倍一樣，這樣做不會改變非基變量檢驗數(shù)的符號。對偶問題如下： 其最優(yōu)解是： 3.11 1、2、3三個城市每年需分別供應(yīng)電力320個單位、250個單位和350個單位，由、兩個電站提供，它們的最大可供電量分別為400個單位和450個單位，單位費(fèi)用如表3-33所示。由于需要量大于可供量，決定城市1的供應(yīng)量可減少030個單位，城市2的供應(yīng)量不變，城市3的供應(yīng)量不

37、能少于270個單位，試求總費(fèi)用最低的分配方案（將可供電量用完）。解：根據(jù)表3-33與已知，解得總費(fèi)用最低的分配方案如下表所示：即最優(yōu)分配方案為：電站供給城市1150單位，城市2250單位；電站供給城市1140單位，城市3310單位。第四章 目標(biāo)規(guī)劃4.1 若用以下表達(dá)式作為目標(biāo)規(guī)劃的目標(biāo)函數(shù)，其邏輯是否正確？為什么？ 答： 不正確，邏輯不合理； 正確，表示未達(dá)到的目標(biāo)值越大越好； 正確，表示離目標(biāo)值正負(fù)偏差之和最?。?正確，表示超過目標(biāo)值越大越好。4.2 用圖解法解下列目標(biāo)規(guī)劃問題： 解：解題過程見圖4-1。求出的區(qū)域沒有公共部分，則取兩個最接近的點(diǎn)a、b?？梢越獬鯽的坐標(biāo)為（40,70）b坐

38、標(biāo)為（55,40）?？傻胊處，b處，比較找出小者為點(diǎn)b。所以，問題的滿意解為解題過程見圖4-2：求出的區(qū)域沒有公共部分，則取兩個最接近的點(diǎn)a、b?？梢越獬鯽的坐標(biāo)為（25,15）b坐標(biāo)為(30,70)?？傻胋處，a處，比較找出小者為點(diǎn)a。所以，問題的滿意解為4.3 用單純形法解下列目標(biāo)規(guī)劃問題： 解：解題過程的單純形表見下表4-3： 解題過程的單純形表見下表4-3：4.4 某成品酒有三種商標(biāo)（紅、黃、藍(lán)），都是由三種原料酒（等級、）兌制而成。三種等級的原料酒的日供應(yīng)量和成本見表4-13，三種商標(biāo)的成本酒的兌制要求和售價見表4-14。決策者規(guī)定：首先是必須嚴(yán)格按規(guī)定比例兌制各商標(biāo)的酒；其次是獲利

39、最大；最后是紅商標(biāo)的酒每天至少生產(chǎn)2000kg。試列出該問題的數(shù)學(xué)模型。解：設(shè)i=1,2,3表示原料酒、等級，j=1,2,3表紅、黃、藍(lán)酒，xij為j酒中使用第i種原料酒的數(shù)量，目標(biāo)規(guī)劃模型為： 4.5 公司決定使用1000萬元新產(chǎn)品開發(fā)基金開發(fā)a、b、c三種新產(chǎn)品。經(jīng)預(yù)測估計，開發(fā)a、b、c三種新產(chǎn)品的投資利潤率分別為5%、7%、10%。由于新開發(fā)產(chǎn)品有一定風(fēng)險，公司研究后確定了下列優(yōu)先順序目標(biāo)：第一，a產(chǎn)品至少投資300萬元；第二，為分散投資風(fēng)險，任何一種新產(chǎn)品的開發(fā)投資不超過開發(fā)基金總額的35%；第三，應(yīng)至少留有10%的開發(fā)基金，以備急用；第四，使總的投資利潤最大。試建立投資分配方案的目

40、標(biāo)規(guī)劃模型。解：設(shè)對a、b、c三種新產(chǎn)品分別開發(fā)投資x1,x2,x3萬元，則目標(biāo)規(guī)劃模型為： 4.6 已知單位牛奶、牛肉、雞蛋中的維生素及膽固醇含量等有關(guān)數(shù)據(jù)見表4-15.如果只考慮這三種食物，并且設(shè)立了下列三個目標(biāo)：第一，滿足三種維生素的每日最小需求量；第二，使每日攝入的膽固醇最少；第三，使每日購買食品的費(fèi)用最少。要求建立問題的目標(biāo)規(guī)劃模型。 4.7 金源公司生產(chǎn)三種產(chǎn)品，其整個計劃期分為三個階段?，F(xiàn)需編制生產(chǎn)計劃，確定各個階段各種產(chǎn)品的生產(chǎn)數(shù)量。計劃受市場需求、設(shè)備臺時、財務(wù)資金等方面條件的約束，有關(guān)數(shù)據(jù)如表4-16和表4-17所示。假設(shè)計劃期初及期末各種產(chǎn)品的庫存量皆為零。公司設(shè)定以下三

41、個優(yōu)先等級的目標(biāo)：p1：及時供貨，保證需求，盡量減少缺貨，并且第三種產(chǎn)品及時供貨的重要性相當(dāng)于第一種、第二種產(chǎn)品的2倍；p2：盡量使各階段加工設(shè)備不超負(fù)荷；p3：流動資金占用量不超過限額。要求建立目標(biāo)規(guī)劃的模型。第五章 整數(shù)規(guī)劃5.1要在長度為l的一根圓鋼上截取不同長度的零件毛坯，毛坯長度有n種，分別為aj（1,2, ，n）。問每種毛坯應(yīng)當(dāng)各截取多少根，才能使圓鋼殘料最少，試建立本問題的數(shù)學(xué)模型。 5.2 籃球隊需要選擇5名隊員組成出場陣容參加比賽。8名隊員的身高及擅長位置見表5-11。出場陣容應(yīng)滿足以下條件：必須且只有一名中鋒上場；至少有一名后衛(wèi)；如1號或4號上場，則6號不出場，反之如6號上

42、場，則1號和4號均不出場；2號和8號至少有一個不出場。問應(yīng)當(dāng)選擇哪5名隊員上場，才能使出場隊員平均身高最高，試建立數(shù)學(xué)模型。 5.3 一個旅行者要在其背包里裝一些最有用的旅行物品。背包容積為a，攜帶物品總重量最多為b?，F(xiàn)有物品m件，第i件物品體積為ai，重量為bi（i=1,2，m）。為了比較物品的有用程度，假設(shè)第i件物品的價值為ci（i=1,2，m）。若每件物品只能整件攜帶，每件物品都能放入背包中，并且不考慮物品放入背包后相互的間隙。問旅行者應(yīng)當(dāng)攜帶哪幾件物品，才能使攜帶物品的總價值最大，要求建立本問題的數(shù)學(xué)模型。 5.4 分別用割平面法和用分支定界法解下列整數(shù)規(guī)劃： 解：割平面法：引入松弛變

43、量，將問題化為標(biāo)準(zhǔn)形式，用單純形法解其松弛問題，得最優(yōu)單純形表，見表1。由于b列各分?jǐn)?shù)中 有最大小數(shù)部分3/4，故從表2中第三行產(chǎn)生割平面約束。割平面約束為 引入松弛變量，得割平面方程 將上式并入表1，然后利用對偶單純形法求解，得表2。類似地，從表2中最后一個單純形表的第二行產(chǎn)生割平面約束引入松弛變量，得割平面方程將上式并入表2中最后一個單純形表，然后用對偶單純形法解之，得表3。表3給出的最優(yōu)解已滿足整數(shù)要求，因而，原整數(shù)規(guī)劃問題的最優(yōu)解為分支定界法：根據(jù)最終單純形表可以得到，此時最優(yōu)解為選x2進(jìn)行分支，可以得到兩個約束條件第一個約束條件： 最終化為標(biāo)準(zhǔn)式，相當(dāng)于增加了一個約束條件和變量x6z

44、0000-1/4-1/3x220100-1/41x45/600013/2-4/3x18/310001/41/3x31/600100-2/3x1x2x3x4x5x6第二個約束條件：最終化為標(biāo)準(zhǔn)式，相當(dāng)于增加了一個約束條件和變量x6z00-200-1x2 301000-1x4 -1001101/2x1 2102001x5 300-601-4x1x2x3x4x5x6無可行解繼續(xù)對第一個分支解：引入松弛變量，將問題化為標(biāo)準(zhǔn)形式，用單純形法解其松弛問題，得最優(yōu)單純形表，見表4。表4給出的最優(yōu)解已滿足整數(shù)要求，因而，原整數(shù)規(guī)劃問題的最優(yōu)解為 5.5 用隱枚舉法解下列0-1型整數(shù)規(guī)劃： 解：在列出所有可能情

45、況以后沒有滿足約束條件的解，所以沒有可行解。解：求解過程可以列表表示（見表6）。所以，最優(yōu)解 5.6 某城市可劃分為11個防火區(qū)，已設(shè)有4個消防站，如圖5-8所示。圖5-8中，虛線表示該消防站可以在消防允許時間內(nèi)到達(dá)該防火區(qū)進(jìn)行有效的消防滅火。問能否關(guān)閉若干消防站，但仍不影響任何一個防火區(qū)的消防救災(zāi)工作（提示：對每一個消防站建立一個表示是否將關(guān)閉的0-1變量）。 5.7 現(xiàn)有p個約束條件需要從中選擇q個約束條件，試借助0-1變量列出表達(dá)式。 5.8 解下列系數(shù)矩陣的最小化指派問題： 解：先對各行元素分別減去本行的最小元素，然后對各列也如此，即 此時，中各行各列都已出現(xiàn)零元素。為了確定中的獨(dú)立零

46、元素，對加*，即 由于只有4個獨(dú)立零元素，少于系數(shù)矩陣階數(shù)n=5，故需要確定能覆蓋所有零元素的最少直線數(shù)目的集合。結(jié)果如下：為了使中未被直線覆蓋的元素中出現(xiàn)零元素，將第二行和第三行中各元素都減去未被直線覆蓋的元素中的最小元素1，但這樣一來，第一列出現(xiàn)了負(fù)元素。為了消除負(fù)元素，再對第一列各元素分別加上1，即回到步驟2，對加*：中已有5個獨(dú)立零元素，故可確定指派問題的最優(yōu)指派方案。即最優(yōu)解為 解：先對各行元素分別減去本行的最小元素，然后對各列也如此，即 此時，中各行各列都已出現(xiàn)零元素。為了確定中的獨(dú)立零元素，對加*，即中已有6個獨(dú)立零元素，故可確定指派問題的最優(yōu)指派方案。即最優(yōu)解為 5.9 需要分

47、派5人去做5項工作，每人做各項工作的能力評分見表5-11。應(yīng)如何分派，才能使總的得分最大？試分別用匈牙利法和表上作業(yè)法求解。解：匈牙利法：先對各行元素分別減去本行的最小元素，然后對各列也如此，即 此時，中各行各列都已出現(xiàn)零元素。為了確定中的獨(dú)立零元素，對加*，即 由于只有3個獨(dú)立零元素，少于系數(shù)矩陣階數(shù)n=5，故需要確定能覆蓋所有零元素的最少直線數(shù)目的集合。結(jié)果如下：為了使中未被直線覆蓋的元素中出現(xiàn)零元素，將第四、五行中各元素都減去未被直線覆蓋的元素中的最小元素0.1，但這樣一來，第五列出現(xiàn)了負(fù)元素。為了消除負(fù)元素，再對第五列各元素分別加上0.1，即回到步驟2，對加*：中已有5個獨(dú)立零元素，故

48、可確定最優(yōu)解為 表上作業(yè)法：用最小元素法求最優(yōu)解，可以把人員看成產(chǎn)地，業(yè)務(wù)看成銷地，各地產(chǎn)量和銷地均為1，于是轉(zhuǎn)化為運(yùn)輸問題。5.10 上題的指派問題也可用分支定界法求解，試說明解題思路。答：用分支定界法時，先根據(jù)表列出線性規(guī)劃模型：例如先不考慮每人完成一項任務(wù)的約束，按照誰完成的多進(jìn)行分配。當(dāng)不滿足問題要求時，按a1， a5中指定1人完成b1，其余 4人再按得分多的進(jìn)行分配，這樣得5個分支。如5個分支均非可行解時，可選一個邊界值最大分支，并指定剩下4人中的1人完成任務(wù)b2，繼續(xù)分支，依次進(jìn)行。5.11 考慮下列問題： 式中，為整數(shù)值，且的值只能等于0、1、4和6.請用一等價的整數(shù)規(guī)劃模型來表

49、達(dá)這個問題。 如果在目標(biāo)函數(shù)中，用來代替，請相應(yīng)地修改的答案。5.12 卡車送貨問題（覆蓋問題）。龍運(yùn)公司目前必須向5家用戶送貨，需在用戶a處卸下1個單位重量的貨物，在用戶b處卸下2個單位重量的貨物，在用戶c處卸下3個單位重量的貨物，在用戶d處卸下4個單位重量的貨物，在用戶e處卸下8個單位重量的貨物。公司有各種卡車四輛：1號車載重量能力為2個單位，2號車載重能力為6個單位，3號車載重能力為8個單位，4號車載重能力為11個單位。每輛車只運(yùn)貨一次，卡車j的一次運(yùn)費(fèi)為cj。假定一輛卡車不能同時給用戶a和c二者送貨；同樣，也不能同時給用戶b和d二者送貨。請列出一個整數(shù)規(guī)劃模型表達(dá)式，以確定裝運(yùn)全部貨物應(yīng)如何配置卡車，使其運(yùn)費(fèi)為最小。如果卡車j只要給用戶i運(yùn)貨時需收附加費(fèi)kij（同卸貨量無關(guān)），試述應(yīng)如何修改這一