實(shí)用管理運(yùn)籌學(xué)陳剛課后參考答案

第2章線性規(guī)劃練線性規(guī)劃的三要素是什么？答：“決策變量”、“目標(biāo)函數(shù)”和“約束條件”是線性規(guī)劃模型必備的三個(gè)要素。線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式有哪些特征？答：線性規(guī)劃的標(biāo)準(zhǔn)形式就有以下四個(gè)特征：①目標(biāo)函數(shù)只有最大化一種形式；②約束條件全部為等式；③決策變量均非負(fù)；④約束條件右端項(xiàng)均非負(fù)。簡(jiǎn)述圖解法的一般步驟。答：圖解法的步驟如下：步驟1：分別以線性規(guī)劃模型中的兩個(gè)變量為橫軸和縱軸建立平面直角坐標(biāo)系(一般以為橫軸，為縱軸)。步驟2：在所建立的平面坐標(biāo)系中畫出約束條件所圍成的區(qū)域圖形，即可行域，并將其用陰影表示出來。步驟3：畫出目標(biāo)函數(shù)的等值線，通常以目標(biāo)函數(shù)值等于0時(shí)為基準(zhǔn)，將等值線沿其法線方向向右上方移動(dòng)直到可行域的邊界點(diǎn)，并根據(jù)目標(biāo)函數(shù)是求最大值還是最小值，判斷是移動(dòng)到上邊界點(diǎn)還是下邊界點(diǎn)為止。4.用圖解法求解下列線性規(guī)劃問題，并判別其解的類型。(1)答：用圖解法求得（1）的最優(yōu)解（0，10）為唯一最優(yōu)解，如圖所示。此時(shí)，目標(biāo)函數(shù)求得其最大值為。(2)答：用圖解法求得（2）的最優(yōu)解（1/5，3/5）為唯一最優(yōu)解，如圖所示。此時(shí)，目標(biāo)函數(shù)求得其最小值為。(3)答：用圖解法求得（3）的可行域無界，如圖所示。此時(shí)，該目標(biāo)函數(shù)解為無界解。(4)答：用圖解法求得（4）有無窮多最優(yōu)解，如圖所示。此時(shí)，目標(biāo)函數(shù)求得其最大值為。(5)答：用圖解法求得（5）的最優(yōu)解（20/3，8/3）為唯一最優(yōu)解，如圖所示。此時(shí)，目標(biāo)函數(shù)求得其最大值為。5.將下述線性規(guī)劃問題轉(zhuǎn)化成標(biāo)準(zhǔn)形式。(1)答：令，得到（1）標(biāo)準(zhǔn)形式為：(2)答：令，得到（2）標(biāo)準(zhǔn)形式為：(3)答：令，得到（3）標(biāo)準(zhǔn)形式為：6.用圖解法求解下列線性規(guī)劃問題，寫出其標(biāo)準(zhǔn)形式，并求出兩個(gè)松弛變量的值。答：用圖解法求得最優(yōu)解（1，3/2）為唯一最優(yōu)解，如圖所示。此時(shí)，目標(biāo)函數(shù)求得其最大值為，標(biāo)準(zhǔn)形式如下，兩個(gè)松弛變量均為0。7.用圖解法求解下列線性規(guī)劃問題，寫出其標(biāo)準(zhǔn)形式，并求出三個(gè)剩余變量的值。答：用圖解法求得最優(yōu)解（1，5）為唯一最優(yōu)解，如圖所示。此時(shí)，目標(biāo)函數(shù)求得其最小值為，令，標(biāo)準(zhǔn)形式如下，剩余變量的值。對(duì)第6和第7題的線性規(guī)劃目標(biāo)函數(shù)系數(shù)進(jìn)行靈敏度分析，即假定其中一個(gè)系數(shù)不變情況下，求出使最優(yōu)解不變的另一個(gè)系數(shù)的變化范圍。答：（1）第6題目標(biāo)函數(shù)等值線的斜率為，如圖，當(dāng)目標(biāo)函數(shù)等值線的斜率在直線的斜率-3/4和直線的斜率-5/2之間變動(dòng)時(shí)，原最優(yōu)解A(1,3/2)仍是最優(yōu)解。，當(dāng)時(shí)，原問題的最優(yōu)解將保持不變。假設(shè)不變，代入不等式中得或；同理，假設(shè)不變，代入不等式中得。（2）第7題目標(biāo)函數(shù)等值線的斜率為，如圖，當(dāng)目標(biāo)函數(shù)等值線的斜率在直線的斜率-5和直線的斜率-1之間變動(dòng)時(shí)，原最優(yōu)解A(1,5)仍是最優(yōu)解。，當(dāng)時(shí)，原問題的最優(yōu)解將保持不變。假設(shè)不變，代入不等式中得或；同理，假設(shè)不變，代入不等式中得。9.某化工廠能夠生產(chǎn)A，B兩種產(chǎn)品，各產(chǎn)品都需要經(jīng)過3道工序進(jìn)行加工完成，生產(chǎn)產(chǎn)品A，B每噸的利潤(rùn)分別為2萬元，3萬元，生產(chǎn)各產(chǎn)品1噸所需工時(shí)數(shù)及各工序可用總工時(shí)數(shù)如下表所示。如何安排生產(chǎn)，使化工廠的總利潤(rùn)最大。建立數(shù)學(xué)模型，并用LINGO求解。表2-1單位產(chǎn)品所需工時(shí)數(shù)及各工序可用總工時(shí)數(shù)工序單位產(chǎn)品所需工時(shí)數(shù)可用總工時(shí)數(shù)產(chǎn)品A產(chǎn)品B工序1810350工序2105450工序325400答：設(shè)安排生產(chǎn)A產(chǎn)品x1，生產(chǎn)B產(chǎn)品x2，化工廠的總利潤(rùn)為z，則該生產(chǎn)計(jì)劃問題可用以下數(shù)學(xué)模型表示：用LINGO求解如下圖，最優(yōu)解為(0,35)，此時(shí)，最大利潤(rùn)為。10.假設(shè)你有1萬元閑錢打算用來購買基金，目前看上兩種基金，其價(jià)格、收益以及風(fēng)險(xiǎn)系數(shù)如下表所示，試求一種投資方案，使得總風(fēng)險(xiǎn)不高于300且總收益最大。建立數(shù)學(xué)模型，并用LINGO求解。表2-2基金相關(guān)信息基金價(jià)格/元收益(元/年)風(fēng)險(xiǎn)系數(shù)A2540.7B4550.4答：設(shè)投資A基金x1元，投資B基金x2元，總收益為z，則問題可用以下數(shù)學(xué)模型表示：用LINGO求解如下圖，最優(yōu)解為(400,0)，此時(shí)，最大利潤(rùn)為。某混凝土公司可生產(chǎn)甲、乙兩種混凝土產(chǎn)品，其車間的生產(chǎn)能力為25噸/小時(shí)，每天工作8小時(shí)，現(xiàn)有兩個(gè)施工現(xiàn)場(chǎng)每天分別需要甲產(chǎn)品120噸，乙產(chǎn)品100噸，甲產(chǎn)品水泥和沙的配比是4:6，利潤(rùn)是150元/噸;乙產(chǎn)品水泥和沙的配比是5:5，利潤(rùn)時(shí)100元/噸。該公司每天可供使用的水泥為155噸、沙為145噸。該公司給兩個(gè)施工現(xiàn)場(chǎng)的供給量不能超過其需求量，不足部分由其他公司供給，問該公司每天應(yīng)生產(chǎn)甲、乙兩種產(chǎn)品各多少噸，使得利潤(rùn)最大建立數(shù)學(xué)模型，并用LINGO求解。答：設(shè)生產(chǎn)甲x1噸，生產(chǎn)甲x2噸，總收益為z，則問題可用以下數(shù)學(xué)模型表示：用LINGO求解如下圖，最優(yōu)解為(120,80)，此時(shí)，最大利潤(rùn)為。12.某集裝箱卡車的最大載重為140噸，最大容積為1365立方英尺?，F(xiàn)有A、B兩種貨物想要托運(yùn)：A貨物重量為4噸/件，體積為19立方英尺/件，托運(yùn)費(fèi)為2萬元/件；B貨物重量為8噸，體積為27立方英尺/件，托運(yùn)費(fèi)為3萬元/件。問卡車司機(jī)應(yīng)該各托運(yùn)A、B兩種貨物多少件，使得收入最大。建立數(shù)學(xué)模型，并用LINGO求解。答：設(shè)托運(yùn)A貨物x1噸，托運(yùn)B貨物x2噸，總收入為z，則問題可用以下數(shù)學(xué)模型表示：用LINGO求解如下圖，最優(yōu)解為(35,0)，此時(shí)，最大利潤(rùn)為。13.某公司生產(chǎn)2種產(chǎn)品，2種產(chǎn)品都需要經(jīng)過車加工、銑加工、鉆加工、磨加工四個(gè)工藝流程，由于工藝略有差異，2種產(chǎn)品每個(gè)工序的時(shí)間有所不同，如下表所示，此外，表中還說明了每種產(chǎn)品的單位利潤(rùn)以及四個(gè)工序的可用總工時(shí)是多少。如何安排生產(chǎn)，使得總利潤(rùn)最大。建立數(shù)學(xué)模型，并用LINGO求解。表2-3第13題數(shù)據(jù)表項(xiàng)目工藝消耗時(shí)間(小時(shí)/件)利潤(rùn)(萬元/件)車加工銑加工鉆加工磨加工產(chǎn)品1951065產(chǎn)品2107964可用工時(shí)(小時(shí))8000700090006000答：設(shè)生產(chǎn)產(chǎn)品1x1，產(chǎn)品2x2，總利潤(rùn)為z，則問題可用以下數(shù)學(xué)模型表示：用LINGO求解如下圖，最優(yōu)解為(888.8889,0)，此時(shí)，最大利潤(rùn)為。14.某企業(yè)可制造A、B、C、D四種產(chǎn)品，單位產(chǎn)品所需消耗原材料、勞動(dòng)力、設(shè)備工時(shí)及利潤(rùn)如下表所示?？晒┦褂玫脑牧嫌?000kg，勞動(dòng)力6000工時(shí)，設(shè)備7000工時(shí)。問該公司應(yīng)該如何制定生產(chǎn)計(jì)劃，使得利潤(rùn)最大。建立數(shù)學(xué)模型，并用LINGO求解。表2-4第14題數(shù)據(jù)表項(xiàng)目產(chǎn)品A產(chǎn)品B產(chǎn)品C產(chǎn)品D原材料(kg/件)10141913勞動(dòng)力(工時(shí)/件)811127設(shè)備(工時(shí)/件)1819614利潤(rùn)(萬元/件)6987答：設(shè)生產(chǎn)產(chǎn)品Ax1，產(chǎn)品Bx2，產(chǎn)品Cx3，產(chǎn)品Dx4，總利潤(rùn)為z，則問題可用以下數(shù)學(xué)模型表示：用LINGO求解如下圖，最優(yōu)解為(0.4285714，0，4.214286，1.357143)，此時(shí)，最大利潤(rùn)為。第3章單純形法與對(duì)偶理論練1.簡(jiǎn)述單純形法的基本思路和原理。答：（1）單純形法的基本思路是：先找出可行域的一個(gè)頂點(diǎn)，根據(jù)一定規(guī)則判斷其是否最優(yōu)；若否，則轉(zhuǎn)換到與之相鄰的另一頂點(diǎn)，并使目標(biāo)函數(shù)值更優(yōu)；如此下去，直到找到某最優(yōu)解為止。（2）單純形法的基本原理是：首先，找出一個(gè)初始基本可行解；其次，根據(jù)最優(yōu)性檢驗(yàn)判斷找到的基本可行解是否是最優(yōu)解，若為最優(yōu)解，則得出結(jié)果，反之，則需進(jìn)行基變換，具體做法是更換可行基中的一個(gè)列向量，得到新的可行基，求出新的基本可行解使目標(biāo)函數(shù)值更優(yōu)；最后再根據(jù)最優(yōu)性檢驗(yàn)判斷新的基本可行解是否是最優(yōu)解，如此下去，直到找到最優(yōu)解為止。2.簡(jiǎn)述用單純形法求解線性規(guī)劃時(shí)無界解、無可行解、多重最優(yōu)解、唯一最優(yōu)解的判別條件是什么。答：（1）無界解：存在某個(gè)檢驗(yàn)數(shù)大于0，且其對(duì)應(yīng)系數(shù)列向量的每個(gè)元素都小于等于0。（2）無可行解：所有檢驗(yàn)數(shù)小于等于0，且基變量中含有非0人工變量。（3）多重最優(yōu)解：所有檢驗(yàn)數(shù)小于等于0，且基變量中不存在非0人工變量，且存在非基變量的檢驗(yàn)數(shù)為0。（4）唯一最優(yōu)解：所有檢驗(yàn)數(shù)小于等于0，且基變量中不存在非0人工變量，且不存在非基變量的檢驗(yàn)數(shù)為0。3.哪些情況下考慮對(duì)偶問題有助于求解原問題。答：(1)原問題約束多、變量少時(shí)，求解對(duì)偶問題能夠降低計(jì)算時(shí)間。因?yàn)樵瓎栴}約束多變量少，轉(zhuǎn)換成對(duì)偶問題就是約束少變量多。使用單純形法時(shí)，約束越少，基變量就越少，理論上來說，所需的迭代次數(shù)就越少，因此能夠有效降低計(jì)算時(shí)間。(2)幫助證明原問題無解。要證明原問題有解，只需要找出一個(gè)滿足約束的解，但要證明原問題無解，卻不能通過遍歷所有的解來證明原問題無解。(3)便于進(jìn)行敏感性分析。很多時(shí)候我們對(duì)原問題的好奇心并不僅限于得到最優(yōu)解，而是還關(guān)注“如果某些已知條件發(fā)生變化，對(duì)最優(yōu)解的影響程度如何”，這就是敏感性分析。對(duì)偶問題和敏感性分析息息相關(guān)：一是增加敏感性分析的直觀程度，例如對(duì)偶問題的最優(yōu)解就是原問題約束的影子價(jià)格；二是在改變某些條件導(dǎo)致原問題無可行解時(shí)，可以借助仍然有可行解的對(duì)偶問題來分析。4.簡(jiǎn)述對(duì)偶規(guī)劃的基本性質(zhì)。答：（1）對(duì)稱性：對(duì)偶問題的對(duì)偶是原問題。（2）弱對(duì)偶性：對(duì)于原問題和對(duì)偶問題的可行解，都有。（3）最優(yōu)性：若原問題和對(duì)偶問題的可行解分別為，且，則分別是原問題和對(duì)偶問題的最優(yōu)解。（4）強(qiáng)對(duì)偶性：如果原問題和對(duì)偶問題都有可行解，則兩者都有最優(yōu)解，且兩者最優(yōu)值相等。（5）互補(bǔ)松弛性：線性規(guī)劃取最優(yōu)解時(shí)，若某一約束條件對(duì)應(yīng)的對(duì)偶變量“≠0”，則該約束嚴(yán)格取“=”；若約束條件取嚴(yán)格不等式，其對(duì)應(yīng)的對(duì)偶變量一定“=0”。5.簡(jiǎn)述對(duì)偶問題與原問題的關(guān)系。答：表3-1原問題與對(duì)偶問題的關(guān)系原問題對(duì)偶問題目標(biāo)函數(shù)max目標(biāo)函數(shù)min變量個(gè)個(gè)約束條件00無約束=約束條件個(gè)個(gè)變量00=無約束約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)6.簡(jiǎn)述影子價(jià)格的經(jīng)濟(jì)意義。答：(1)影子價(jià)格反映了資源對(duì)目標(biāo)函數(shù)的邊際貢獻(xiàn)及資源轉(zhuǎn)化成效益的效率。影子價(jià)格越大，則資源對(duì)目標(biāo)函數(shù)的邊際貢獻(xiàn)越大，資源轉(zhuǎn)化成效益的效率越大。(2)影子價(jià)格反映了資源的稀缺程度。當(dāng)某種資源的影子價(jià)格大于0時(shí)，表示這種資源稀缺，且影子價(jià)格越大，資源越稀缺；當(dāng)某種資源的影子價(jià)格等于0時(shí)，說明這種資源有剩余或供大于求。(3)影子價(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用。影子價(jià)格不同于市場(chǎng)價(jià)格，是在特定問題中資源使用者賦予資源的一個(gè)估價(jià)，而資源的市場(chǎng)價(jià)格是其價(jià)值的客觀體現(xiàn)，隨供求關(guān)系的變化，價(jià)格圍繞價(jià)值波動(dòng)。在完成市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，就買進(jìn)資源；當(dāng)市場(chǎng)價(jià)格高于影子價(jià)格時(shí)，就賣出資源。7.簡(jiǎn)述對(duì)偶單純形法的步驟。答：對(duì)偶單純形法的步驟如下：步驟1：根據(jù)線性規(guī)劃問題列出初始單純形表。步驟2：檢查常數(shù)列，如果常數(shù)列的所有分量都，且檢驗(yàn)數(shù)均，則已經(jīng)得到最優(yōu)解，停止計(jì)算。如果常數(shù)列中至少還有一個(gè)負(fù)分量，且檢驗(yàn)數(shù)均，則進(jìn)行以下計(jì)算。步驟3：確定出基變量：在常數(shù)列中找到一個(gè)最小的負(fù)分量，即，則這個(gè)負(fù)分量所在行的基變量為出基變量。步驟4：確定入基變量：檢查出基變量所在行的各系數(shù)，如果所有的都，則無可行解，停止計(jì)算。如果存在為負(fù)數(shù)，則計(jì)算所有為負(fù)數(shù)的與其對(duì)應(yīng)的檢驗(yàn)數(shù)的比值，找出其中的最小值，即，則其對(duì)應(yīng)的非基變量為入基變量。步驟5：以為主元，按原單純形法在表中進(jìn)行迭代，得到新的單純形表，重復(fù)步驟2~4。8.用單純形法、大M法或兩階段法求解下列線性規(guī)劃問題，并判斷問題的解屬于哪一類。(1)解：在約束條件中加入松弛變量，得將參數(shù)填入單純形表計(jì)算，如表所示。表3-2單純形表迭代次數(shù)基變量410000121088/10[4]2011111/40000041001003/21-1/421/4411/201/411/44201110-10-1迭代到第2次，所有檢驗(yàn)數(shù)都小于等于0，且基變量中不存在非0人工變量，且不存在非基變量檢驗(yàn)數(shù)為0，說明已經(jīng)求得唯一最優(yōu)解，唯一最優(yōu)解為，最優(yōu)值為11。（2）解：在約束條件中加入松弛變量，，，得將參數(shù)填入單純形表計(jì)算，如表所示。表3-3單純形表迭代次數(shù)基變量1063000003211002020/301110101010/10[12]410015050/200000001063000100[1]3/410-1/415/215/2002/311/1201-1/1235/635/41011/31/12001/1225/625/21010/35/6005/6125/308/313/600-5/626013/410-1/415/210/1000[5/12]-2/311/125/62/11010-1/6-1/301/65/3—10617/68/301/6185/3001/6-8/30-1/63601011/5-9/5-2/563001-8/512/51/5210100-3/52/51/52106312/52/51/562000-12/5-2/5-1/5迭代到第4次，所有檢驗(yàn)數(shù)都小于等于0，且基變量中不存在非0人工變量，且不存在非基變量檢驗(yàn)數(shù)為0，說明已經(jīng)求得唯一最優(yōu)解，唯一最優(yōu)解為，最優(yōu)值為62。(3)解：在約束條件中加入松弛變量，，，得將參數(shù)填入單純形表計(jì)算，如表所示。表3-4單純形表迭代次數(shù)基變量-2-310000022-11004—01-2[3]01099/3011100155/10000000-2-31000107/34/3011/30711/3-2/3101/30302/35/300-1/3121/3-2/3101/303-7/3-7/300-1/30迭代到第2次，所有檢驗(yàn)數(shù)都小于等于0，且基變量中不存在非0人工變量，且不存在非基變量檢驗(yàn)數(shù)為0，說明已經(jīng)求得唯一最優(yōu)解，唯一最優(yōu)解為，最優(yōu)值為=-=-3。(4)解：在約束條件中加入松弛變量，剩余變量，人工變量，得將參數(shù)填入單純形表計(jì)算，如表所示。表3-5單純形表迭代次數(shù)基變量51300-M0-M1[4]20-111010/401-2110015—-M-4M-2M0M-M-10M5+M1+4M3+2M0-M011[1/4]11/20-1/41/45/210/103/2021-1/21/22040/31/411/20-1/41/45/219/405/201/4-M-1/4251420-221000-6-11-5/2-5/25520100-1010500-19-7010-M-10在以上的單純形表中，若進(jìn)行第4次迭代，選為入基變量，但由于=-2，=，找不到大于0的來確定出基變量，此時(shí)該線性規(guī)劃問題無界的。（5）解：在約束條件中加入松弛變量，剩余變量，人工變量，得將參數(shù)填入單純形表計(jì)算，如表所示。表3-6單純形表迭代次數(shù)基變量1400-M002[2]1001111/2-M-110-1188/1M-M0M-M-8M1-M4+M0-M014111/20011/2-M-20-1/2-115/24+2M42+1/2MM-M22-5/2M-3-2M0-2-1/2M-M0迭代到第2次，所有檢驗(yàn)數(shù)都小于等于0，說明已經(jīng)求得最優(yōu)解，但人工變量=0，可知該線性規(guī)劃問題無可行解的。（6）解：在約束條件中加入剩余變量，，，人工變量，，，得將參數(shù)填入單純形表計(jì)算，如表所示。表3-7單純形表迭代次數(shù)基變量23000-M-M-M0-M43-1001001212/3-M1[2]0-1001044/2-M0100-100155/1-5M-5MMMM-M-M-M-21M2+5M3+5M-M-M-M0001-M5/20-1[3/2]01-3/2064/131/210-1/2001/202—-M-1/2001/2-10-1/2136/13/2-2M3M-3/2-2MM-M3/2+2M-M6-9M1/2+2M0-M3/2+2M-M0-3/2-3M0205/30-2/3102/3-104—34/31-1/3001/3004—-M-4/30[1/3]0-1-1/30113/14+4/3M3-1-1/3M0M1+1/3M0-M12-M-2-4/3M01+1/3M0-M-1-4/3M-M030-1001-20-12630100-100150-4010-3-10330300-30031520003-M-M-M-3在以上的單純形表中，若進(jìn)行第4次迭代，選為入基變量，但由于=-2，=-1，=-3，找不到大于0的來確定出基變量，此時(shí)該線性規(guī)劃問題無界的。（7）解：在約束條件中加入松弛變量，，剩余變量，人工變量，得將參數(shù)填入單純形表計(jì)算，如表所示。表3-8單純形表迭代次數(shù)基變量211000-M0-M[2]11-100144/2012001001010/10241001088/2-2M-M-MM00M-4M2+2M1+M1+M-M00-2M1211/21/2-1/2001/22—003/2-1/21/210-1/2816/10020[1]01-144/1211-10014000100-M-12213/21/2001/204001/2-1/201-1/20600201012000-1-M迭代到第3次，所有檢驗(yàn)數(shù)都小于等于0，說明已經(jīng)求得最優(yōu)解，此時(shí)非基變量檢驗(yàn)數(shù)等于0，則該線性規(guī)劃問題有多重最優(yōu)解，其中一個(gè)最優(yōu)解為，最優(yōu)值為8。9.對(duì)第8題(1)、(2)小題中線性規(guī)劃的目標(biāo)函數(shù)中變量系數(shù)及約束方程中常數(shù)項(xiàng)進(jìn)行靈敏度分析，即目標(biāo)函數(shù)中變量系數(shù)在什么范圍內(nèi)變化時(shí)線性規(guī)劃的最優(yōu)解不變，約束方程中常數(shù)項(xiàng)在什么范圍內(nèi)變化時(shí)，其對(duì)應(yīng)的對(duì)偶價(jià)格不變。答：（1）表3-98（1）的最終單純形表迭代次數(shù)基變量41001003/21-1/421/4411/201/411/44201110-10-1例如非基變量和基變量在目標(biāo)函數(shù)中變量系數(shù)在什么范圍內(nèi)變化時(shí)線性規(guī)劃的最優(yōu)解不變，約束方程中常數(shù)項(xiàng)在什么范圍內(nèi)變化時(shí)，其對(duì)應(yīng)的對(duì)偶價(jià)格不變。由于是非基變量，因此，當(dāng)1，即當(dāng)2時(shí)，線性規(guī)劃的最優(yōu)解不變。由于是基變量，因此，即4，時(shí)，線性規(guī)劃的最優(yōu)解不變。對(duì)應(yīng)的松弛變量是，因此，即+=8-=時(shí)，其對(duì)應(yīng)的對(duì)偶價(jià)格不變。（2）表3-108（2）的最終單純形表迭代次數(shù)基變量10630003601011/5-9/5-2/563001-8/512/51/5210100-3/52/51/52106312/52/51/562000-12/5-2/5-1/5例如非基變量和基變量在目標(biāo)函數(shù)中變量系數(shù)在什么范圍內(nèi)變化時(shí)線性規(guī)劃的最優(yōu)解不變，約束方程中常數(shù)項(xiàng)在什么范圍內(nèi)變化時(shí)，其對(duì)應(yīng)的對(duì)偶價(jià)格不變。由于是非基變量，因此，當(dāng)，即當(dāng)時(shí)，線性規(guī)劃的最優(yōu)解不變。由于是基變量，因此，即，時(shí)，線性規(guī)劃的最優(yōu)解不變。對(duì)應(yīng)的松弛變量是，因此，即，時(shí)，其對(duì)應(yīng)的對(duì)偶價(jià)格不變。10.寫出下列線性規(guī)劃的對(duì)偶問題。(1)該線性規(guī)劃的對(duì)偶問題為：(2)該線性規(guī)劃的對(duì)偶問題為：(3)該線性規(guī)劃的對(duì)偶問題為：11.寫出下列線性規(guī)劃的對(duì)偶問題，考慮用哪一種形式求解相應(yīng)線性規(guī)劃問題更簡(jiǎn)單，并選擇合適的方法求解。(1)解：該線性規(guī)劃的對(duì)偶問題為：求解該線性規(guī)劃的對(duì)偶問題更簡(jiǎn)單，因?yàn)椴恍枰肴斯ぷ兞?，所以在約束條件中加入松弛變量，，，，，得將參數(shù)填入對(duì)偶單純形表計(jì)算，如表所示。表3-10對(duì)偶單純形表迭代次數(shù)基變量67891000000001000[1]0000011/1011000000101—001100001001—000110000101—0000110000111/1000000000006789100000011010001100001—011000010001—001100001001—0001100001011/10-100[1]0-1000100/1100001010000010-47890-10000021010001100001—011000010001—001[1]000010011/10101001001-111/19-10010-100010—100910100091057800-1000-9310100011000011/10110000100011/1801100001001—0[1]-100010-11-100/19-10010-100010—18891010809185-1000-10-80-941001001001-1111/100[2]000-111-1111/28011000010011/161-100010-11-10—90-101000-1100—638910603541804000-60-3-5-4510000011/2-1/21/2-1/21/21/2701000-1/21/21/2-1/21/21/28001001/2-1/21/21/2-1/21/26100001/21/2-1/21/2-1/21/2900010-1/21/2-1/21/21/21/2678910425362000000-4-2-5-3-6迭代到第6次，所有檢驗(yàn)數(shù)都小于等于0，說明已經(jīng)求出對(duì)偶問題最優(yōu)解，最優(yōu)解為，從最終單純形表中可以看出，原線性規(guī)劃問題最優(yōu)解為，最優(yōu)值為20。(2)解：該線性規(guī)劃的對(duì)偶問題為：求解該線性規(guī)劃的對(duì)偶問題更簡(jiǎn)單，因?yàn)椴恍枰肴斯ぷ兞?，所以在約束條件中加入松弛變量，，，得將參數(shù)填入對(duì)偶單純形表計(jì)算，如表所示。表3-11對(duì)偶單純形表迭代次數(shù)基變量412000002110022/103101033/101[4]00166/40000041200010[7/4]010-1/41/22/7011/4001-1/43/26/11121/41001/43/26/1312003181000-324104/70-1/72/7000-11/711/75/71201-1/702/710/74124/7020/7128/700-4/70-20/7迭代到第3次，所有檢驗(yàn)數(shù)都小于等于0，說明已經(jīng)求出對(duì)偶問題最優(yōu)解，最優(yōu)解為，從最終單純形表中可以看出，原線性規(guī)劃問題最優(yōu)解為，最優(yōu)值為。(3)解：該線性規(guī)劃的對(duì)偶問題為：求解該線性規(guī)劃的對(duì)偶問題更簡(jiǎn)單，因?yàn)橹恍枰胍粋€(gè)人工變量，所以在約束條件中加入松弛變量，，剩余變量，人工變量得將參數(shù)填入對(duì)偶單純形表計(jì)算，如表所示。表3-12對(duì)偶單純形表迭代次數(shù)基變量236000--M-3[1]-400-1111/10511010055/13M-M4M00M-M-M2-3M3+M6-4M00-M010-70-1110-334—3-31-400-111—080[5]011-144/5-93-1200-33311018003-32053/700111/5-4/54/564/5317/51004/5-1/51/521/568/50101/51/5-1/54/599/536018/53/5-3/587/5-89/5000-18/5-3/5-M+3/5迭代到第3次，所有檢驗(yàn)數(shù)都小于等于0，說明已經(jīng)求出對(duì)偶問題最優(yōu)解，最優(yōu)解為，從最終單純形表中可以看出，原線性規(guī)劃問題最優(yōu)解為，最優(yōu)值為。12.用對(duì)偶單純形法求解下列線性規(guī)劃問題。解：先將線性規(guī)劃轉(zhuǎn)化為下列形式，以使用對(duì)偶單純形法求解求解過程如表所示。表3-13對(duì)偶單純形表迭代次數(shù)基變量-2-3-500000[-1]1-1100-40112010800-11001-20000000-2-3-50002—5———1-21-11-10040021110400[-1]1001-2-22-2200-80-5-3-200—5————2-2100-10-1600031120-301-100-12-2-33005-1800-800-5迭代到第3次，所有檢驗(yàn)數(shù)都小于等于0，常數(shù)列所有分量都非負(fù)，說明已經(jīng)求出優(yōu)解，最優(yōu)解=6，=2，=0，=0，=0，=0，最優(yōu)目標(biāo)函數(shù)值為=-=18。13.某化工廠能夠生產(chǎn)3種產(chǎn)品，各產(chǎn)品都需要經(jīng)過3道工序進(jìn)行加工完成，生產(chǎn)產(chǎn)品A，B，C每噸的利潤(rùn)分別為2.5萬元，2萬元，3萬元，生產(chǎn)各產(chǎn)品1噸所需工時(shí)數(shù)及各工序可用總工時(shí)數(shù)如下表所示。表3-21單位產(chǎn)品所需工時(shí)數(shù)及各工序可用總工時(shí)數(shù)工序單位產(chǎn)品所需工時(shí)數(shù)可用總工時(shí)數(shù)產(chǎn)品A產(chǎn)品B產(chǎn)品C工序181610350工序21055450工序32135400(1)如何安排生產(chǎn)，使化工廠的總利潤(rùn)最大。(2)為了擴(kuò)大生產(chǎn)，化工廠通過各種手段增加工時(shí)數(shù)，如果工序1每增加1工時(shí)數(shù)，需要消耗成本1萬元，那么這樣做是否劃算。(3)若由于技術(shù)進(jìn)步，生產(chǎn)每噸產(chǎn)品B工序1減少了2工時(shí)，工序2減少了1工時(shí)，工序3減少了2工時(shí)，那么這時(shí)的最優(yōu)生產(chǎn)方案是否發(fā)生變化。(4)若由于市場(chǎng)變化，產(chǎn)品B每噸的利潤(rùn)變?yōu)?萬元，那么這時(shí)的最優(yōu)生產(chǎn)方案是否發(fā)生變化。解：（1）設(shè)為產(chǎn)品A的計(jì)劃產(chǎn)量，為產(chǎn)品B的計(jì)劃產(chǎn)量，為產(chǎn)品C的計(jì)劃產(chǎn)量，建立數(shù)學(xué)模型在約束條件中，添加松弛變量，將模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式，并利用單純形法求出問題的最優(yōu)解與最優(yōu)值，如下表所示。表3-14對(duì)偶單純形表迭代次數(shù)基變量2.52300000816[10]100350350/1001055010450450/502135001400400/500000002.52300013[4/5]8/511/100035175/406-30-1/210275275/60-250-1/201225—12/524/533/10001051/10-14/50-3/100022.5125/41/800175/400-15-24/5-5/41050/40098/5-1/401625/22.5525/85/1600875/80-3-1/8-5/1600根據(jù)上表可知，=，=0，=0，=0，=，=，最優(yōu)目標(biāo)函數(shù)值=，所以應(yīng)生產(chǎn)產(chǎn)品A萬噸，使化工廠的總利潤(rùn)最大。（2）工序1的對(duì)偶價(jià)格為萬元，每增加1工時(shí)數(shù)可以多獲利萬元，但是消耗成本1萬元，所以這樣做不劃算。（3）仍不生產(chǎn)產(chǎn)品B，最大利潤(rùn)不變。（4）由于是非基變量，因此，當(dāng)3，即當(dāng)5時(shí)，=3，此時(shí)線性規(guī)劃的最優(yōu)解不變，所以這時(shí)的最優(yōu)生產(chǎn)方案不變。14.已知線性規(guī)劃問題其對(duì)偶問題的最優(yōu)解為，最優(yōu)值為，試用互補(bǔ)松弛定理求出原問題的最優(yōu)解。解：首先寫出其對(duì)偶問題將代入約束不等式，其，式等號(hào)成立，，式等號(hào)不成立，即對(duì)應(yīng)的松弛變量不為0。由互補(bǔ)松弛定理有==0.又由于>0，>0，由互補(bǔ)松弛定理可知原問題的兩個(gè)約束條件應(yīng)該取“=”，將==0代入原問題的約束條件，得解得=4，=4，可知原問題的最優(yōu)解為==0，=4，=4，對(duì)應(yīng)的目標(biāo)函數(shù)最大值為28。第4章運(yùn)輸問題練簡(jiǎn)述表上作業(yè)法的基本步驟和每個(gè)步驟的方法。答：表上作業(yè)法的四個(gè)步驟為：確定初始基本可行解，包括西北法，最小元素法，伏格爾法；最優(yōu)解的判別，包括閉回路法，位勢(shì)法；運(yùn)輸方案的改進(jìn)，包括閉回路調(diào)整法；多重最優(yōu)解的判別。表上作業(yè)多重最優(yōu)解的判別條件是什么。答：某個(gè)非基變量(空格)的檢驗(yàn)數(shù)為0時(shí)，該問題有多重最優(yōu)解。3.表上作業(yè)法的退化現(xiàn)象是指什么。答：表上作業(yè)法的退化有兩種情況：（1）0在確定初始基本可行解時(shí)，有可能出現(xiàn)下面這種情況：當(dāng)在某個(gè)單元格填入數(shù)字后，該單元格對(duì)應(yīng)的行和列的剩余量都變成0。這時(shí)就要同時(shí)劃去行和列，但為了保證基變量的個(gè)數(shù)為m+n-1個(gè)，就需要在該單元格對(duì)應(yīng)的行和列的任一空格處填入0，表示該單元格為基變量。（2）在用閉回路調(diào)整時(shí)，有可能出現(xiàn)兩個(gè)或兩個(gè)以上的偶數(shù)順序頂點(diǎn)有相同的最小值。這時(shí)只能選擇其中一個(gè)作為出基變量，經(jīng)調(diào)整后，得到退化解。退化解中有相同最小值的其他單元格必須填入0，表明它們是基變量。4.判斷下列說法的對(duì)錯(cuò)，如果是錯(cuò)的，請(qǐng)寫出正確說法。(1)在運(yùn)輸問題的單位運(yùn)價(jià)表的某一行或某一列分別加上一個(gè)常數(shù)，最優(yōu)解不會(huì)變。答:正確(2)產(chǎn)銷平衡問題是指產(chǎn)地?cái)?shù)和銷地?cái)?shù)相等。答：錯(cuò)誤，產(chǎn)銷平衡是指總產(chǎn)量和總銷量相等。(3)運(yùn)輸問題最優(yōu)解中不為0的變量的個(gè)數(shù)最多為m+n個(gè)。答：錯(cuò)誤，運(yùn)輸問題最優(yōu)解中不為0的變量的個(gè)數(shù)最多為m+n-1 個(gè)(4)運(yùn)輸問題一定有最優(yōu)解。答：正確(5)用表上作業(yè)法求解最小化運(yùn)輸問題時(shí)，當(dāng)所有非基變量的檢驗(yàn)數(shù)均小于等于0，說明已求出最優(yōu)解。答:錯(cuò)誤，當(dāng)所有非基變量的檢驗(yàn)數(shù)都大于等于0時(shí)，說明已求出最優(yōu)解。(6)用表上作業(yè)法求解產(chǎn)大于銷的運(yùn)輸問題時(shí)，需要虛擬一個(gè)銷地。答：正確5.某同學(xué)在做運(yùn)輸問題時(shí)得到下面三個(gè)初始解，如表4-42至4-44所示，問哪些解不可能是通過表上作業(yè)法得出的？答：初始解2和初始解3不可能是通過表上作業(yè)法得出的，表上作業(yè)法得到的基變量數(shù)為m+n-1個(gè)，初始解2和初始解3都不符合。表4-42初始解1銷地產(chǎn)地1234產(chǎn)量11010214620334815銷量1314108表4-43初始解2銷地產(chǎn)地1234產(chǎn)量11010214620313215銷量1314108表4-44初始解3銷地產(chǎn)地1234產(chǎn)量155102105520334815銷量13141086.某建筑公司目前在全市有四個(gè)工地，對(duì)水泥的需求量分別為300噸、300噸、200噸和200噸，某水泥供應(yīng)商在該市有三個(gè)工廠，分別可供應(yīng)500噸、200噸和400噸。由于距離原因，相應(yīng)的單位運(yùn)價(jià)如表4-45所示。建筑公司采購水泥后，由供應(yīng)商負(fù)責(zé)運(yùn)輸，問供應(yīng)商應(yīng)該如何制定調(diào)運(yùn)方案可使總運(yùn)輸費(fèi)用最小。表4-45單位運(yùn)價(jià)表(單位：元/噸)建筑公司供應(yīng)商工地1工地2工地3工地4工廠13764工廠22432工廠34385解：由題意可知，某建筑公司工地水泥需求量為300+300+200+200=1000噸，工廠可供應(yīng)水泥500+200+400=1100噸，本題目為產(chǎn)銷不平衡問題，產(chǎn)大于銷，需要虛擬一個(gè)銷地為工地5，運(yùn)輸單價(jià)為0，需求量為100。如表4-46數(shù)據(jù)表所示。表4-46數(shù)據(jù)表建筑公司供應(yīng)商工地1工地2工地3工地4虛擬工地5供應(yīng)量工廠137640500工廠224320200工廠343850400需求量3003002002001001100設(shè)表示從工廠i（i=1,2,3）提供到工地j（j=1,2,3,4）的產(chǎn)品數(shù)量，建立數(shù)學(xué)模型如下：對(duì)應(yīng)的LINGO程序如下：min=3*x11+7*x12+6*x13+4*x14+2*x21+4*x22+3*x23+2*x24+4*x31+3*x32+8*x33+5*x34;x11+x12+x13+x14<500;x21+x22+x23+x24<200;x31+x32+x33+x34<400;x11+x21+x31=300;x12+x22+x32=300;x13+x23+x33=200;x14+x24+x34=200;圖4-14LINGO求解結(jié)果表4-47運(yùn)輸表建筑公司供應(yīng)商工地1工地2工地3工地4供應(yīng)量工廠1300200500工廠2200200工廠3300300需求量3003002002001000由以上計(jì)算可知，本問題有最優(yōu)解，最優(yōu)解為：x11=300噸，x14=200噸，x23=200噸，x32=300噸，其最優(yōu)值為3200元。工廠1運(yùn)輸?shù)焦さ?為300噸，運(yùn)輸?shù)焦さ?為200噸；工廠2運(yùn)輸?shù)焦さ?為200噸；工廠3運(yùn)輸?shù)焦さ?為300噸；其最優(yōu)值為3200元。7.某企業(yè)在不同的地方有三個(gè)分公司，生產(chǎn)同一種產(chǎn)品，每月的產(chǎn)量分別是300臺(tái)、400臺(tái)和500臺(tái)，目前主要的銷售地有4個(gè)，需求量分別是200臺(tái)、250臺(tái)、350臺(tái)和400臺(tái)。單位運(yùn)價(jià)如表4-48所示。表4-48單位運(yùn)價(jià)表(單位：元/臺(tái))銷地產(chǎn)地銷地1銷地2銷地3銷地4分公司110153019分公司221172325分公司323212022應(yīng)該如何安排運(yùn)輸方案，使得總運(yùn)輸費(fèi)用最小？解：由題意可知，產(chǎn)地的產(chǎn)量之和為300+400+500=1200臺(tái)，銷地的需求量之和為200+250+350+400=1200臺(tái)，總產(chǎn)量等于總銷量，是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題。因此，把產(chǎn)地的產(chǎn)量全部分配給銷地，正好滿足這四個(gè)銷地的需求。如表4-49數(shù)據(jù)表所示。表4-49數(shù)據(jù)表銷地產(chǎn)地銷地1銷地2銷地3銷地4總產(chǎn)量分公司110153019300分公司221172325400分公司323212022500總銷量2002503504001200設(shè)表示從產(chǎn)地i（i=1,2,3）運(yùn)輸?shù)戒N地j（j=1,2,3,4）的產(chǎn)品數(shù)量，寫出此問題的數(shù)學(xué)模型：對(duì)應(yīng)的LINGO程序如下：min=10*x11+15*x12+30*x13+19*x14+21*x21+17*x22+23*x23+25*x24+23*x31+21*x32+20*x33+22*x34;x11+x12+x13+x14=300;x21+x22+x23+x24=400;x31+x32+x33+x34=500;x11+x21+x31=200;x12+x22+x32=250;x13+x23+x33=350;x14+x24+x34=400;、圖4-15LINGO求解結(jié)果表4-50運(yùn)輸表銷地產(chǎn)地銷地1銷地2銷地3銷地4總產(chǎn)量分公司1200100300分公司2250150400分公司3200300500總銷量2002503504001200由以上計(jì)算可知，本問題有最優(yōu)解，最優(yōu)解為：x11=200臺(tái)，x14=100臺(tái)，x22=250臺(tái)，x23=150臺(tái)，x33=200臺(tái)，x34=300臺(tái)，其最優(yōu)值為22200元。分公司1運(yùn)輸?shù)戒N地1為200臺(tái)，運(yùn)輸?shù)戒N地4為100臺(tái)；分公司2運(yùn)輸?shù)戒N地2為250臺(tái)，運(yùn)輸?shù)戒N地3為150臺(tái)；分公司3運(yùn)輸?shù)戒N地3為200臺(tái)，運(yùn)輸?shù)戒N地4為500臺(tái)；其最優(yōu)值為22200元。假設(shè)由于技術(shù)改進(jìn)，分公司2的產(chǎn)量提高到600臺(tái)，問應(yīng)如何安排運(yùn)輸方案，使得總運(yùn)輸費(fèi)用最小？解:由題意可知，產(chǎn)地的產(chǎn)量之和為300+600+500=1400臺(tái)，銷地的需求量之和為200+250+350+400=1200臺(tái)，為產(chǎn)銷不平衡問題，產(chǎn)大于銷，需要虛擬一個(gè)銷地，運(yùn)輸單價(jià)為0，銷售量為200，如表4-51數(shù)據(jù)表所示。表4-51數(shù)據(jù)表銷地產(chǎn)地銷地1銷地2銷地3銷地4虛擬銷地總產(chǎn)量分公司1101530190300分公司2211723250600分公司3232120220500總銷量2002503504002001400設(shè)表示從產(chǎn)地i（i=1,2,3）運(yùn)輸?shù)戒N地j（j=1,2,3,4,5）的產(chǎn)品數(shù)量，建立數(shù)學(xué)模型如下：對(duì)應(yīng)的LINGO程序如下：min=10*x11+15*x12+30*x13+19*14+21*x21+17*x22+23*x23+25*x24+23*x31+21*x32+20*x33+22*x34;x11+x12+x13+x14<300;x21+x22+x23+x24<600;x31+x32+x33+x34<500;x11+x21+x31=200;x12+x22+x32=250;x13+x23+x33=350;x14+x24+x34=400;圖4-16LINGO求解結(jié)果由以上計(jì)算可知，本問題有最優(yōu)解，最優(yōu)解為：x11=200臺(tái)，x14=100臺(tái)，x22=250臺(tái)，x23=150臺(tái)，x33=200臺(tái)，x34=300臺(tái)，其最優(yōu)值為22200元。分公司1運(yùn)輸?shù)戒N地1為200臺(tái)，運(yùn)輸?shù)戒N地4為100臺(tái)；分公司2運(yùn)輸?shù)戒N地2為250臺(tái)，運(yùn)輸?shù)戒N地3為150臺(tái)；分公司3運(yùn)輸?shù)戒N地3為200臺(tái)，運(yùn)輸?shù)戒N地4為500臺(tái)；其最優(yōu)值為22200元。假設(shè)由于產(chǎn)品質(zhì)量過硬，銷地1的銷量提高到400臺(tái)，其他條件與(1)相同，且為了保持各地之間的銷量平衡，要求最低供應(yīng)量不能低于需求量的80%，問應(yīng)如何安排運(yùn)輸方案，使得總運(yùn)輸費(fèi)用最?。拷?由題意知，銷地1的銷量提高到400臺(tái)，總產(chǎn)量等于總銷量，產(chǎn)銷平衡。為了保持各地之間的銷量平衡，要求最低供應(yīng)量不能低于需求量的80%，所以將銷地1分成兩部分產(chǎn)地到，銷地1的320臺(tái)必須滿足，所以虛擬產(chǎn)地到銷地1的運(yùn)價(jià)定為M，虛擬銷地（1）的運(yùn)輸量為80臺(tái)，單位運(yùn)價(jià)為0，其他銷地按照同樣方式進(jìn)行分解，如表4-52數(shù)據(jù)表所示。表4-52數(shù)據(jù)表銷地產(chǎn)地銷地1銷地（1）銷地2銷地（2）銷地3銷地（3）銷地4銷地（4）總產(chǎn)量分公司11010151530301919300分公司22121171723232525400分公司32323212120202222500虛擬產(chǎn)地M0M0M0M0200總銷量320802005028070320801400建立數(shù)學(xué)模型如下：對(duì)應(yīng)的LINGO程序如下：min=10*x11+10*x12+15*x13+15*x14+30*x15+30*x16+19*x17+19*x18+21*x21+21*x22+17*x23+17*x24+23*x25+23*x26+25*x27+25*x28+23*x31+23*x32+21*x33+21*x34+20*x35+20*x36+22*x37+22*x38+M*x41+M*x43+M*x45+M*x47;x11+x12+x13+x14+x15+x16+x17+x18=300;x21+x22+x23+x24+x25+x26+x27+x28=400;x31+x32+x33+x34+x35+x36+x37+x38=500;x41+x42+x43+x44+x45+x46+x47+x48=200;x11+x21+x31+x41=320;x12+x22+x32+x42=80;x13+x23+x33+x43=200;x14+x24+x34+x44=50;x15+x25+x35+x45=280;x16+x26+x36+x46=70;x17+x27+x37+x47=320;x18+x28+x38+x48=80;圖4-17LINGO求解結(jié)果由以上計(jì)算可知，本問題有最優(yōu)解，最優(yōu)解為：x11=270臺(tái)，x12=30臺(tái)，x21=50臺(tái)，x23=200臺(tái)，x24=50臺(tái)，x25=100臺(tái)，x35=180臺(tái)，x37=320臺(tái)，x42=50臺(tái)，x46=70臺(tái)，x48=80臺(tái)，其最優(yōu)值為21240元。分公司1運(yùn)輸?shù)戒N地1為300臺(tái)；分公司2運(yùn)輸?shù)戒N地1為50臺(tái)，運(yùn)輸?shù)戒N地2為250臺(tái)，運(yùn)輸?shù)戒N地3為100臺(tái)；分公司3運(yùn)輸?shù)戒N地3為180臺(tái)，運(yùn)輸?shù)戒N地4為320臺(tái)；其最優(yōu)值為21240元。8.有三個(gè)儲(chǔ)煤基地負(fù)責(zé)供應(yīng)五個(gè)地區(qū)冬天的煤炭需求，五個(gè)地區(qū)的需求量不確定，但根據(jù)以往歷史數(shù)據(jù)，可以估計(jì)其最低需求和最高需求，儲(chǔ)煤基地的儲(chǔ)煤量，各地區(qū)的需求以及單位運(yùn)價(jià)(單位：元/噸)如表4-53所示。試求盡量滿足各地區(qū)的用煤需求，且運(yùn)輸總費(fèi)用最小的調(diào)運(yùn)方案表4-53數(shù)據(jù)表銷地單位運(yùn)價(jià)產(chǎn)地地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)5供應(yīng)量/噸儲(chǔ)煤基地163895550儲(chǔ)煤基地285462500儲(chǔ)煤基地3119748450最低需求/噸250350200300150最高需求/噸350500250350250解:由題可知，煤炭的供應(yīng)量為550+500+450=1500噸，各地區(qū)煤炭需求量最高為350+500+250+350+250=1700噸，最低為250+350+200+300+150=1250噸，我們可以設(shè)置一個(gè)虛擬基地4，因?yàn)樽畹偷男枨罅勘仨殱M足，因此不能從虛擬基地調(diào)運(yùn)煤炭給它，這時(shí)可假設(shè)虛擬基地到地區(qū)1的單位運(yùn)價(jià)為M(一個(gè)很大的數(shù))，就可防止虛擬基地給地區(qū)1調(diào)運(yùn)煤炭，因?yàn)槿绻摂M基地給地區(qū)1調(diào)運(yùn)了煤，那么總運(yùn)費(fèi)也將是一個(gè)很大的數(shù)，不符合題目求最小值的目標(biāo)；剩下為100噸，為了區(qū)別我們稱其為地區(qū)（1），這部分的需求量可由虛擬基地供應(yīng)(相當(dāng)于缺貨)，也可由其他儲(chǔ)煤基地供應(yīng)，這時(shí)假設(shè)虛擬基地到地區(qū)（1）的的單位運(yùn)價(jià)為0。同理，地區(qū)2、地區(qū)3、地區(qū)4和地區(qū)5的需求量也分為兩部分，如表4-54數(shù)據(jù)表所示。表4-54數(shù)據(jù)表銷地單位運(yùn)價(jià)產(chǎn)地地區(qū)1地區(qū)（1）地區(qū)2地區(qū)（2）地區(qū)3地區(qū)（3）地區(qū)4地區(qū)(4)地區(qū)5地區(qū)(5)供應(yīng)量/噸儲(chǔ)煤基地16633889955550儲(chǔ)煤基地28855446622500儲(chǔ)煤基地3111199774488450虛擬基地4M0M0M0M0M0200需求/噸25010035015020050300501501001700建立數(shù)學(xué)模型如下：對(duì)應(yīng)的LINGO程序如下：min=6*x11+6*x12+3*x13+3*x14+8*x15+8*x16+9*x17+9*x18+5*x19+5*110+8*x21+8*x22+5*x23+5*x24+4*x25+4*x26+6*x27+6*x28+2*x29+2*x210+11*x31+11*x32+9*x33+9*x34+7*x35+7*x36+4*x37+4*x38+8*x39+8*x310+M*x41+M*x43+M*x45+M*x47+M*x49;x11+x12+x13+x14+x15+x16+x17+x18+x19+x110=550;x21+x22+x23+x24+x25+x26+x27+x28+x29+x210=500;x31+x32+x33+x34+x35+x36+x37+x38+x39+x310=450;x41+x42+x43+x44+x45+x46+x47+x48+x49+x410=200;x11+x21+x31+x41=250;x12+x22+x32+x42=100;x13+x23+x33+x43=350;x14+x24+x34+x44=150;x15+x25+x35+x45=200;x16+x26+x36+x46=50;x17+x27+x37+x47=300;x18+x28+x38+x48=50;x19+x29+x39+x49=150;x110+x210+x310+x410=100;圖4-18LINGO求解結(jié)果由以上計(jì)算可知，本問題有最優(yōu)解，最優(yōu)解為：x11=150噸，x13=250噸，x14=50噸，x23=100噸，x25=200噸，x26=50噸，x29=150噸，x31=100噸，x37=300噸，x38=50噸，x110=100噸，x42=100噸，x44=100噸，其最優(yōu)值為6650元。儲(chǔ)煤基地1運(yùn)輸?shù)降貐^(qū)1為150噸，運(yùn)輸?shù)降貐^(qū)2為300噸，運(yùn)輸?shù)降貐^(qū)5為100噸；儲(chǔ)煤基地2運(yùn)輸?shù)降貐^(qū)2為100噸，運(yùn)輸?shù)降貐^(qū)3為250噸，運(yùn)輸?shù)降貐^(qū)5為150噸；儲(chǔ)煤基地3運(yùn)輸?shù)降貐^(qū)1為100噸，運(yùn)輸?shù)降貐^(qū)4為350噸；儲(chǔ)煤基地4運(yùn)輸?shù)降貐^(qū)1為100噸，運(yùn)輸?shù)降貐^(qū)2為100噸。其最優(yōu)值為6650元。9.某化肥廠有四個(gè)分廠生產(chǎn)同一種化肥，產(chǎn)量分別是300噸、500噸、400噸和200噸，負(fù)責(zé)供應(yīng)六個(gè)地區(qū)的客戶，各地區(qū)的需求量分別是280噸、250噸、320噸、350噸、370噸和340噸。由于工廠生產(chǎn)工藝的差別，各廠的單位生產(chǎn)成本分別是1.3萬元/噸，1.4萬元/噸，1.35萬元/噸和1.45萬元/噸。又由于市場(chǎng)行情不同，各地區(qū)的銷售價(jià)格分別是3.2萬元/噸，3.1萬元/噸，2.9萬元/噸，2.8萬元/噸，3.3萬元/噸和3.0萬元/噸。各地之間的單位運(yùn)價(jià)如表4-55所示。由于供小于求，必然會(huì)有某些地區(qū)缺貨，根據(jù)各地區(qū)的市場(chǎng)評(píng)估，銷售部門要求地區(qū)1和地區(qū)2至少供應(yīng)150噸且不超過其需求量，地區(qū)3和地區(qū)4要求必須滿足需求量，地區(qū)5和地區(qū)6只要不超過其需求量即可。請(qǐng)制定使總利潤(rùn)最大的運(yùn)輸方案。表4-55單位運(yùn)價(jià)表(單位：萬元/噸)銷地產(chǎn)地地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)5地區(qū)6分廠10.30.20.40.70.80.8分廠20.80.40.70.20.10.1分廠30.70.10.20.50.50.6分廠40.10.40.30.30.40.4解:由題可知，產(chǎn)地化肥的產(chǎn)量為300+500+400+200=1400噸，需求量為280+250+320+350+370+340=1910噸，產(chǎn)銷不平衡，產(chǎn)小于銷，所以我們?cè)O(shè)置一個(gè)虛擬產(chǎn)地5，又由于地區(qū)1和地區(qū)2至少供應(yīng)150噸且不超過其需求量，因此需將地區(qū)1和地區(qū)2的需求量分為兩部分：一部分為150噸，這部分的需求量必須滿足，因此不能從虛擬產(chǎn)地調(diào)運(yùn)化肥給它，這時(shí)可假設(shè)虛擬產(chǎn)地到地區(qū)1和地區(qū)2的單位運(yùn)價(jià)為M(一個(gè)很大的數(shù))，就可防止虛擬產(chǎn)地給地區(qū)1和地區(qū)2調(diào)運(yùn)化肥，因?yàn)槿绻摂M產(chǎn)地給地區(qū)1或地區(qū)2調(diào)運(yùn)了化肥，那么總運(yùn)費(fèi)也將是一個(gè)很大的數(shù)，不符合題目求最小值的目標(biāo)；另一部分分別為130噸和100噸，為了區(qū)別我們稱其為地區(qū)（1）和地區(qū)（2），這部分的需求量可由虛擬產(chǎn)地供應(yīng)(相當(dāng)于缺貨)，也可由其他分廠供應(yīng)，這時(shí)假設(shè)虛擬產(chǎn)地到項(xiàng)目（1）和項(xiàng)目（2）的單位運(yùn)價(jià)為0。如表4-56數(shù)據(jù)表所示。表4-56數(shù)據(jù)表銷地產(chǎn)地地區(qū)1地區(qū)（1）地區(qū)2地區(qū)（2）地區(qū)3地區(qū)4地區(qū)5地區(qū)6總產(chǎn)量分廠10.30.30.20.20.40.70.80.8300分廠20.80.80.40.40.70.20.10.1500分廠30.70.70.10.10.20.50.50.6400分廠40.10.10.40.40.30.30.40.4200虛擬產(chǎn)地M0M0MM00510總銷量1501301501003203503703401910建立數(shù)學(xué)模型如下：對(duì)應(yīng)的LINGO程序如下：max=3.2*(x11+x21+x31+x41)+3.1*(x12+x22+x32+x42)+2.9*(x13+x23+x33+x43)+2.8*(x14+x24+x34+x44)+3.3*(x15+x25+x35+x45)+3.0*(x16+x26+x36+x46)-1.3*(x11+x12+x13+x14+x15+x16+x17+x18)-1.4*(x21+x22+x23+x24+x25+x26+x27+x28)-1.35*(x31+x32+x33+x34+x35+x36+x37+x38)-1.45*(x41+x42+x43+x44+x45+x46+x47+x48)-(0.3*x11+0.3*x12+0.2*x13+0.2*x14+0.4*x15+0.7*x16+0.8*x17+0.1*x18+0.8*x21+0.8*x22+0.4*x23+0.4*x24+0.7*x25+0.2*x26+0.1*x27+0.1*x28+0.7*x31+0.7*x32+0.1*x33+0.1*x34+0.2*x35+0.5*x36+0.5*x37+0.6*x38+0.1*x41+0.1*x42+0.4*x43+0.4*x44+0.3*x45+0.3*x46+0.4*x47+0.4*x48+M*x51+M*x53+M*x55+M*x56);x11+x12+x13+x14+x15+x16+x17+x18=300;x21+x22+x23+x24+x25+x26+x27+x28=500;x31+x32+x33+x34+x35+x36+x37+x38=400;x41+x42+x43+x44+x45+x46+x47+x48=200;x51+x52+x53+x54+x55+x56+x57+x58=510;x11+x21+x31+x41+x51=150;x12+x22+x32+x42+x52=130;x13+x23+x33+x43+x53=150;x14+x24+x34+x44+x54=100;x15+x25+x35+x45+x55=320;x16+x26+x36+x46+x56=350;x17+x27+x37+x47+x57=370;x18+x28+x38+x48+x58=340;圖4-19LINGO求解結(jié)果由以上計(jì)算可知，本問題有最優(yōu)解，最優(yōu)解為：x41=150，x12=80，x42=50，x13=150，x14=20，x34=80，x35=320，x26=350，x18=50，x27=150，x57=220，x58=290，其最優(yōu)值為1544萬元。分廠1運(yùn)輸?shù)降貐^(qū)1為80噸，運(yùn)輸?shù)降貐^(qū)2為170噸，運(yùn)輸?shù)降貐^(qū)6為50噸；分廠2運(yùn)輸?shù)降貐^(qū)4為350噸，運(yùn)輸?shù)降貐^(qū)5為150噸；分廠3運(yùn)輸?shù)降貐^(qū)2為80噸，運(yùn)輸?shù)降貐^(qū)3為320噸；分廠4運(yùn)輸?shù)降貐^(qū)1為190噸；其最優(yōu)值為1544萬元。10.某公司目前有2個(gè)工廠，5個(gè)銷售地。由于市場(chǎng)前景好，產(chǎn)品供不應(yīng)求，因此公司決定再建一個(gè)工廠，初步有3個(gè)備選方案，原工廠以及各備選方案到銷售地的單位運(yùn)價(jià)(單位：元/噸)、工廠的產(chǎn)量及銷量如表4-57數(shù)據(jù)表所示。請(qǐng)問選哪個(gè)方案更加合理？表4-57數(shù)據(jù)表銷地單位運(yùn)價(jià)產(chǎn)地銷地1銷地2銷地3銷地4銷地5供應(yīng)量/噸工廠116751616400工廠2718955300備選方案11613101918300備選方案27513127300備選方案32076199300需求量/噸19022026015018010001000解:該問題是一個(gè)設(shè)施選址問題，我們可以將其轉(zhuǎn)化為三個(gè)運(yùn)輸問題，分別計(jì)算其最小的總運(yùn)輸費(fèi)用，選取較小的方案為新建工廠的地址。利用表上作業(yè)法或LINGO軟件分別求解三個(gè)運(yùn)輸問題，這里省略求解過程，結(jié)果如下：表4-58數(shù)據(jù)表銷地單位運(yùn)價(jià)產(chǎn)地銷地1銷地2銷地3銷地4銷地5供應(yīng)量/噸工廠116751616400工廠2718955300備選方案11613101918300需求量/噸19022026015018010001000備選方案1建立數(shù)學(xué)模型如下所示：對(duì)應(yīng)的LINGO程序如下：min=16*x11+7*x12+5*x13+16*x14+16*x15+7*x21+18*x22+9*x23+5*x24+5*x25+16*x31+13*x32+10*x33+19*x14+18*x35;x11+x12+x13+x14+x15=400;x21+x22+x23+x24+x25=300;x31+32+x33+x34+x35=300;x11+x21+x31=190;x12+x22+x32=220;x13+x23+x33=260;x14+x24+x34=150;x15+x25+x35=180；圖4-20LINGO求解結(jié)果由以上計(jì)算可知，備選方案1最優(yōu)解為：x12=220，x13=180，x21=120，x25=180，x31=70，x33=80，x34=150，其最優(yōu)值為6100元。表4-59數(shù)據(jù)表銷地單位運(yùn)價(jià)產(chǎn)地銷地1銷地2銷地3銷地4銷地5供應(yīng)量/噸工廠116751616400工廠2718955300備選方案27513127300需求量/噸19022026015018010001000備選方案2建立數(shù)學(xué)模型如下所示：對(duì)應(yīng)的LINGO程序如下：min=16*x11+7*x12+5*x13+16*x14+16*x15+7*x21+18*x22+9*x23+5*x24+5*x25+7*x31+5*x32+13*x33+12*x14+7*x35;x11+x12+x13+x14+x15=400;x21+x22+x23+x24+x25=300;x31+x32+x33+x34+x35=300;x11+x21+x31=190;x12+x22+x32=220;x13+x23+x33=260;x14+x24+x34=150;x15+x25+x35=180;圖4-21LINGO求解結(jié)果由以上計(jì)算可知，備選方案2最優(yōu)解為：x12=140，x13=260，x21=120，x25=180，x31=70，x32=80，x34=150，其最優(yōu)值為4910元。表4-60數(shù)據(jù)表銷地單位運(yùn)價(jià)產(chǎn)地銷地1銷地2銷地3銷地4銷地5供應(yīng)量/噸工廠116751616400工廠2718955300備選方案32076199300需求量/噸19022026015018010001000備選方案3建立數(shù)學(xué)模型如下所示：對(duì)應(yīng)的LINGO程序如下：min=16*x11+7*x12+5*x13+16*x14+16*x15+7*x21+18*x22+9*x23+5*x24+5*x25+20*x31+7*x32+6*x33+19*x14+9*x35;x11+x12+x13+x14+x15=400;x21+x22+x23+x24+x25=300;x31+x32+x33+x34+x35=300;x11+x21+x31=190;x12+x22+x32=220;x13+x23+x33=260;x14+x24+x34=150;x15+x25+x35=180;圖4-22LINGO求解結(jié)果由以上計(jì)算可知，備選方案3最優(yōu)解為：x12=140，x13=260，x21=190，x25=110，x32=80，x34=150，x35=70，其最優(yōu)值為5350元。綜上所述，備選方案2為最佳方案，其最優(yōu)值為4910元。11.某產(chǎn)品的供應(yīng)鏈上有3個(gè)制造商(A、B、C)，2個(gè)分銷商(D、E)和4個(gè)銷售商(F、G、H、I)，制造商的產(chǎn)品只能通過分銷商轉(zhuǎn)運(yùn)到銷售商。每個(gè)制造商的年產(chǎn)量(單位：萬件)，每個(gè)銷售商的年需求量(單位：萬件)，以及各地之間的單位運(yùn)價(jià)(單位：元/件)如圖4-23所示。圖4-23運(yùn)輸網(wǎng)絡(luò)示意圖求使得運(yùn)輸費(fèi)用最小的調(diào)運(yùn)方案。表4-61數(shù)據(jù)表分銷商制造商銷售商ABCFGHID68789710E56411796解：中轉(zhuǎn)問題仍然可以用表上作業(yè)法求解，首先仍然是要寫出產(chǎn)銷平衡表，由于分銷中心既要接收物資，又要發(fā)出物資，因此分銷中心既要看成產(chǎn)地又要看成銷地。又由于分銷中心只是起到中轉(zhuǎn)的作用，收到多少物資就要運(yùn)出多少物資，因此其產(chǎn)量等于銷量，且產(chǎn)量與銷量的值取分銷中心的最大轉(zhuǎn)運(yùn)量。又由于生產(chǎn)廠與銷地之間，以及分銷中心與分銷中心之間不能相互運(yùn)輸，因此他們的單位運(yùn)價(jià)取為M。分銷中心自己與自己的單位運(yùn)價(jià)取為0，其對(duì)應(yīng)決策變量實(shí)際含義為(最大轉(zhuǎn)運(yùn)量-實(shí)際轉(zhuǎn)運(yùn)量)，如果題目規(guī)定了分銷中心的最大轉(zhuǎn)運(yùn)能力，則該值就是剩余可用的能力。根據(jù)以上描述，構(gòu)造本題的產(chǎn)銷平衡表，如表4-62所示。表4-62產(chǎn)銷平衡表銷地運(yùn)價(jià)產(chǎn)地DEFGHI供應(yīng)量/臺(tái)A65MMMM16B86MMMM24C74MMMM20D0M8971060EM01179660需求量/臺(tái)606015122211120120建立數(shù)學(xué)模型如下：對(duì)應(yīng)的LINGO程序如下：min=6*x11+5*x12+8*x21+6*x22+7*x31+4*x32+8*y11+9*y12+7*y13+10*y14+11*y21+7*y22+9*y23+6*y24;x11+x12=16;x21+x22=24;x31+x32=20;x11+x21+x31-(y11+y12+y13+y14)=0;x12+x22+x32-(y21+y22+y23+y24)=0;y11+y21=15;y12+y22=12;y13+y23=22;y14+y24=11;圖4-24LINGO求解結(jié)果由以上計(jì)算可知，本問題有最優(yōu)解，最優(yōu)解為：x11=16，x22=24，x32=20，y11=15，y13=1，y22=12，y23=21，y24=11，其最優(yōu)值為786萬元。由A運(yùn)輸?shù)紻為16萬件，由B運(yùn)輸?shù)紼為24萬件，由C運(yùn)輸?shù)紼為20萬件；由D運(yùn)輸?shù)紽為15萬件，由D運(yùn)輸?shù)紿為1萬件，由E運(yùn)輸?shù)紾為12萬件，由E運(yùn)輸?shù)紿為21萬件，由E運(yùn)輸?shù)絀為11萬件；其最優(yōu)值為786萬元。如果分銷商每年的最大處理能力為40萬件，求此時(shí)的最小運(yùn)輸費(fèi)用調(diào)運(yùn)方案。表4-63產(chǎn)銷平衡表銷地運(yùn)價(jià)產(chǎn)地DEFGHI供應(yīng)量/臺(tái)A65MMMM16B86MMMM24C74MMMM20D0M8971040EM01179640需求量/臺(tái)404015122211100100建立數(shù)學(xué)模型如下：對(duì)應(yīng)的LINGO程序如下：min=6*x11+5*x12+8*x21+6*x22+7*x31+4*x32+8*y11+9*y12+7*y13+10*y14+11*y21+7*y22+9*y23+6*y24;x11+x12=16;x21+x22=24;x31+x32=20;x11+x21+x31<40;x12+x22+x32<40;x11+x21+x31-(y11+y12+y13+y14)=0;x12+x22+x32-(y21+y22+y23+y24)=0;y11+y21=15;y12+y22=12;y13+y23=22;y14+y24=11;圖4-25LINGO求解結(jié)果由以上計(jì)算可知，本問題有最優(yōu)解，最優(yōu)解為：x11=16，x21=4，x22=20，x32=20，y11=15，y13=5，y22=12，y23=17，y24=11，其最優(yōu)值為786萬元。由A運(yùn)輸?shù)紻為16萬件，由B運(yùn)輸?shù)紻為4萬件，由B運(yùn)輸?shù)紼為20萬件；由C運(yùn)輸?shù)紼為20萬件；由D運(yùn)輸?shù)紽為15萬件，由D運(yùn)輸?shù)紿為5萬件，由E運(yùn)輸?shù)紾為12萬件，由E運(yùn)輸?shù)紿為17萬件，由E運(yùn)輸?shù)絀為11萬件；其最優(yōu)值為786萬元。12.某工廠實(shí)行的是按訂單生產(chǎn)的生產(chǎn)模式，已知明年四個(gè)季度的訂單分別是208、256、354、307臺(tái)，訂單統(tǒng)一季度末交貨。由于原材料價(jià)格及供應(yīng)變動(dòng)等原因，每季度的生產(chǎn)能力和單位生產(chǎn)成本也不同，生產(chǎn)能力分別是350、450、400、200臺(tái)，單位成本分別是4.4、4.3、4.6、4.9萬元/臺(tái)。又如果生產(chǎn)出來的產(chǎn)品當(dāng)季度不交貨，那么每臺(tái)產(chǎn)品每季度的儲(chǔ)存、維護(hù)等費(fèi)用為0.15萬元。問如何在按時(shí)交貨的前提下，制定使總成本最小的生產(chǎn)與儲(chǔ)存計(jì)劃。解：由于當(dāng)月生產(chǎn)出的產(chǎn)品不一定當(dāng)月交貨，因此該問題的決策變量可以假設(shè)為第i季度生產(chǎn)的產(chǎn)品在第季度交貨的數(shù)量，不妨用xij表示。又由于第i季度生產(chǎn)的產(chǎn)品在第j季度交貨的單位成本應(yīng)該是生產(chǎn)成本和儲(chǔ)存、維護(hù)等成本之和，如在1季度生產(chǎn)的發(fā)動(dòng)機(jī)在2季度交貨，其單位成本=4.4+0.15=4.55萬元，以此類推。又由于時(shí)間不可倒流，即下一季度生產(chǎn)出的產(chǎn)品不可能用于前面季度的訂單交貨，我們可以假設(shè)其相應(yīng)的單位成本為M(一個(gè)非常大的數(shù))來強(qiáng)迫決策變量為0。此外，由于產(chǎn)大于銷，我們還需假設(shè)一個(gè)銷地，如表4-64產(chǎn)銷平衡表所示。表4-64產(chǎn)銷平衡表銷地單位運(yùn)價(jià)產(chǎn)地一季度二季度三季度四季度虛擬銷地供應(yīng)量/臺(tái)一季度4.44.554.74.850350二季度M4.34.454.60450三季度MM4.64.750400四季度MMM4.90200需求量/臺(tái)20825635430727514001400建立數(shù)學(xué)模型如下所示：其對(duì)應(yīng)的LINGO程序?yàn)椋簃in=4.4*x11+4.55*x12+4.7*x13+4.85*x14+4.3*x22+4.45*x23+4.6*x24+4.6*x33+4.75*x34+4.9*x44;x11+x12+x13+x14<350;x22+x23+x24<450;x33+x34<400;x44<200;x11=208;x12+x22=256;x13+x23+x33=354;x14+x24+x34+x44=307;圖4-26LINGO求解結(jié)果由以上計(jì)算可知，本問題有最優(yōu)解，最優(yōu)解為x11=208臺(tái)，x14=67臺(tái)，x22=256臺(tái)，x24=194臺(tái)，x33=354臺(tái)，x34=46臺(tái)，其最優(yōu)值為5080.25萬元。第一季度生產(chǎn)275臺(tái)，在第一季度交付208臺(tái)，在第四季度交付67臺(tái)；第二季度生產(chǎn)450臺(tái)，在第二季度交付256臺(tái)，在第四季度交付194臺(tái)；第三季度生產(chǎn)400臺(tái)，在第三季度交付354臺(tái)，在第四季度交付46臺(tái)。其最優(yōu)值為5080.25萬元。第5章整數(shù)規(guī)劃練簡(jiǎn)述整數(shù)規(guī)劃的三個(gè)分類。純整數(shù)規(guī)劃、0-1規(guī)劃、混合整數(shù)規(guī)劃簡(jiǎn)述分支定界法的基本步驟。步驟1：將原整數(shù)規(guī)劃問題去掉決策變量取整約束，轉(zhuǎn)化為相應(yīng)的線性規(guī)劃問題并用單純形法求解，如果無可行解，則原整數(shù)規(guī)劃問題也無可行解；如有可行解，則求出線性規(guī)劃的最優(yōu)解。步驟2：判斷解是否為整數(shù)，且目標(biāo)函數(shù)值的上界是否等于下界，如果是，則結(jié)束計(jì)算，輸出最優(yōu)解；如果否，則轉(zhuǎn)到第3步。步驟3：將線性規(guī)劃進(jìn)行分支，選擇一個(gè)有整數(shù)約束但目前不是整數(shù)的決策變量，假設(shè)，則分別將和增加到上一步線性規(guī)劃的約束條件中，得到兩個(gè)新的線性規(guī)劃并用單純形法求解，轉(zhuǎn)到第2步。簡(jiǎn)述求解0-1規(guī)劃的隱枚舉法的步驟。步驟1：將目標(biāo)函數(shù)中決策變量按照其前面的系數(shù)從大到小排列。步驟2：如果是求最大值，決策變量的取值按照(1,1,…,1,1)、(1,1,…,1,0)、(1,1,…,0,1)、(1,1,…,0,0)…的順序排列(即按照目標(biāo)函數(shù)取值從大到小排列)；如果是求最小值，決策變量的取值按照(0,0,…,0,0)、(0,0,…,0,1)、(0,0,…,1,0)、(0,0,…,1,1)…的順序排列(即按照目標(biāo)函數(shù)取值從小到大排列)。步驟3：依次計(jì)算各解是否可行，直到找到第一個(gè)可行解，即為最優(yōu)解。簡(jiǎn)述匈牙利法的步驟。步驟1：從系數(shù)矩陣的每行元素中減去該行的最小元素，得到新系數(shù)矩陣。步驟2：從新系數(shù)矩陣的每列元素中減去該列的最小元素，得到另一個(gè)新系數(shù)矩陣。步驟3：用總數(shù)最少的橫線或縱線覆蓋新系數(shù)矩陣中所有的0，如果橫線和縱線的數(shù)量之和等于系數(shù)矩陣的行數(shù)，則得到最優(yōu)系數(shù)矩陣，轉(zhuǎn)到步驟5；否則，轉(zhuǎn)到步驟4。步驟4：把系數(shù)矩陣中所有未被覆蓋的數(shù)減去其中的最小數(shù)，并將這個(gè)最小數(shù)加到橫線與縱線交叉點(diǎn)上的數(shù)上，被覆蓋的其他非交叉點(diǎn)上的數(shù)不變，得到新的系數(shù)矩陣，轉(zhuǎn)到步驟3。步驟5：從只有一個(gè)0的行或列開始，這個(gè)0所對(duì)應(yīng)的行與列就給出了一個(gè)分配方案，把這個(gè)0所對(duì)應(yīng)的行和列劃去。重復(fù)這一步驟，直到全部任務(wù)分配完畢。5．某集裝箱卡車的最大載重為140噸，最大容積為1365立方英尺?，F(xiàn)有A、B兩種貨物想要托運(yùn)：A貨物重量為4噸/件，體積為195立方英尺/件，托運(yùn)費(fèi)為2萬元/件；B貨物重量為40噸，體積為273立方英尺/件，托運(yùn)費(fèi)為3萬元/件。問卡車司機(jī)應(yīng)該各托運(yùn)A、B兩種貨物多少件，才能使獲利最大。建立數(shù)學(xué)模型并用分枝定界法求解(其中分支的線性規(guī)劃可用軟件求解)。解：為司機(jī)運(yùn)送i貨物的數(shù)量。解出該題LINGO程序求解如下：max=2*xA+3*xB;4*xA+40*xB<140;195*xA+273*xB<1365;@gin(xA);@gin(xB);6.用隱枚舉法求解下列0-1規(guī)劃。(1)(2)（1）X3X1X2約束條件目標(biāo)函數(shù)值111×12110√9（2）X1X2X3約束條件目標(biāo)函數(shù)值000√×0001√√×1010√√×3100√√√57．某公司有五個(gè)工程隊(duì)，現(xiàn)在剛好有五項(xiàng)工程任務(wù)，由于每個(gè)工程隊(duì)的特長(zhǎng)不同，其完成各項(xiàng)任務(wù)的成本也各不相同，每個(gè)工程隊(duì)完成每項(xiàng)任務(wù)的成本如表5-8所示，要求確定工程隊(duì)和任務(wù)之間一一對(duì)應(yīng)的指派方案，使總成本最少。請(qǐng)用匈牙利法求解。表5-8花費(fèi)成本表(單位：萬元)任務(wù)1任務(wù)2任務(wù)3任務(wù)4任務(wù)5工程隊(duì)110514514工程隊(duì)2141481111工程隊(duì)371251211工程隊(duì)4119131112工程隊(duì)51271169所有行減去其最小元素5090966033270762042361503所有列減去其最小元素3090646030070730042041500第1個(gè)解：3090646030070730042041500第2個(gè)解：3090646030070730042041500第3個(gè)解：30906460300707300420415008．某公司生產(chǎn)3種產(chǎn)品，3種產(chǎn)品都需要經(jīng)過車加工、銑加工、鉆加工、磨加工四個(gè)工藝流程，由于工藝略有差異，3種產(chǎn)品每個(gè)1工4序的時(shí)間有所不同，如表5-9所示，此外，表中還說明了每種產(chǎn)品的單位利潤(rùn)以及四個(gè)工序的可用總工時(shí)是多少。問該公司應(yīng)如何制定本周期的生產(chǎn)計(jì)劃，使總利潤(rùn)最大。表5-9第8題數(shù)據(jù)表項(xiàng)目工藝消耗時(shí)間(小時(shí)/件)利潤(rùn)(萬元/件)車加工銑加工鉆加工磨加工產(chǎn)品1951065產(chǎn)品2107964產(chǎn)品359653可用工時(shí)(小時(shí))8000700090006000解：設(shè)xi為第i種產(chǎn)品生產(chǎn)的數(shù)量。解得 該題LINGO程序求解如下max=5*x1+4*x2+3*x3;9*x1+10*x2+5*x3<8000;5*x1+7*x2+9*x3<7000;10*x1+9*x2+6*x3<9000;6*x1+6*x2+5*x3<6000;@gin(x1);@gin(x2);@gin(x3);9．某制造企業(yè)可以生產(chǎn)甲、乙、丙種產(chǎn)品，每種產(chǎn)品都需要經(jīng)過A、B兩道工序。該企業(yè)有三種規(guī)格的設(shè)備可以完成工序A，記為A1、A2、A3；有四種規(guī)格的設(shè)備可以完成工序B，記為B1、B2、B3、B4。產(chǎn)品甲可以在工序A、B的任何規(guī)格的設(shè)備上進(jìn)行加工；產(chǎn)品乙的工序B只能在B1、B2上加工；產(chǎn)品丙的工序A只能在A2上加工，工序B只能在B1、B4上加工。已知各種設(shè)備加工各種產(chǎn)品的單件工時(shí)、設(shè)備的有效臺(tái)時(shí)、每設(shè)備臺(tái)時(shí)的成本、各種產(chǎn)品的單價(jià)以及原材料單價(jià)等信息，如表5-10所示。問應(yīng)該如何安排生產(chǎn)，使總利潤(rùn)最大。表5-10第9題數(shù)據(jù)表項(xiàng)目產(chǎn)品單件工時(shí)(小時(shí)/件)設(shè)備臺(tái)時(shí)(小時(shí))