運籌學復習資料一、問答題（5選1）：1、運籌學的主要內容有哪些？運籌學為什么在美國被稱為管理科學，此名稱合理嗎？答：運籌學是應用分析、試驗、量化的方法，對經濟管理系統(tǒng)中的人、財、物等有限資源進行統(tǒng)籌安排，為決策者提供有決策依據的最優(yōu)方案，以實現最有效的管理。運籌學的研究內容包括規(guī)劃論、圖與網絡分析、存貯論、排隊論、對策論、決策論。規(guī)劃論主要解決兩大問題：如何有效利用現有的人力、物力去完成更多的任務；對于給定的任務或者目標。用最少的人力或物力如何去完成。圖與網絡分析主要解決生產組織、計劃管理以及工程施工中的工序安排、工期控制、資源合理調配問題。決策論研究決策過程中方案的選擇、度量和概率值選取問題。最終獲得最優(yōu)策略、最優(yōu)方案。定量分析技術作為管理工具，在美國的許多企業(yè)得到廣泛的應用，量化管理或者精確管理是美國企業(yè)管理的重點，運籌學在美國被稱為管理科學。此名稱合理。2、運籌學解決實際問題的過程可分為哪幾個階段?答：運籌學解決實際問題的過程可分為5個階段：（1）提出并形成問題。要解問題，首先需要提出問題，明確問題的實質及關鍵所在，這就要求對系統(tǒng)進行深入的調查和分析，確定問題的界限，選準問題的目標。（2）建立模型。運籌學模型是一個能有效地達到一定目標（或多個目標）行動的系統(tǒng)，因此，目標一經認定，就要用數學語言描述問題，建立目標函數，分析問題所處的環(huán)境，確定約束條件，探求與問題有關的決策變量等，并選用合適的方法，建立運籌學模型。（3）分析并求解模型。根據所建模型的性質及其數學特征，選擇適當的求解方法。（4）檢驗并評價模型。模型分析和計算得到結果以后，尚需按照它能否解決實際問題，主要考慮達成目標的情況，選擇合適的標準，并通過一定的方法對模型結構和一些基本參數進行評價，以檢驗它們是否準確無誤，否則就要考慮改換或修正模型，增減計算過程中所用到的資料或數據。（5）應用或實施模型的解。經過反復檢查以后，最終應用或實施模型的解，就是供給決策者一套有科學依據的并為解決問題所需要的數據、信息或方案，以輔助決策者在處理問題時作出正確的決策和行動方案。3、試述線性規(guī)劃模型建模的基本步驟及線性規(guī)劃模型的構成要素的特征。答：①建模基本步驟：確定決策變量、確定目標函數、確定約束條件。②線性規(guī)劃模型的構成要素及特征：決策變量，是規(guī)劃問題中要確定的未知量,用來表示規(guī)劃問題中用數量表示的方案\措施，可以由決策者決定和控制。目標函數，是決策變量的函數，反映決策者對于規(guī)劃規(guī)劃問題結果的要求。約束條件，指決策變量取值時受到的各種資源條件的限制,通常表達為含決策變量的等式或者不等式。4、試述線性規(guī)劃與對偶規(guī)劃之間存在的關系。答：線性規(guī)劃問題具有對偶性，即任何一個求極大值的線性規(guī)劃問題，都有一個求極小值的線性規(guī)劃問題與之對應，反之亦然。如果把其中一個叫做原問題，則另一個就叫做它的對偶問題，并稱這互相聯(lián)系的兩個問題為一對對偶問題。根據對偶理論，在解原問題的同時，也可以得到對偶問題的解，并且還可以提供影子價格等有價值的信息。5、什么是資源的影子價格，它同相應的市場價格之間有何區(qū)別？答：在一對對偶問題（P）和（D）中，若（P）的某個約束條件的右端常數bi增加1個單位時，所引起的目標函數最優(yōu)值Z﹡的改變量yi﹡成為第i個約束條件的影子價格。如果原規(guī)劃模型屬于在一定資源約束條件下，按一定的生產消耗生產一組產品并尋求總體效益（如利潤）目標函數最大化問題，那么其對偶模型屬于對本問題中每一資源以某種方式進行估價以便得出與最優(yōu)生產計劃相一致的一個企業(yè)的最低總價值。該對偶模型中資源的估價表現為相應的資源的影子價格。影子價格不是市場價格，它是根據企業(yè)本身的資源情況bi、消耗系數aij和產品的利潤cj計算出來的一種價格，是新增資源所創(chuàng)造的價值，是邊際價格。不同的企業(yè)，即使是相同的資源，其影子價格也不一定相同。就是同一個企業(yè)，在不同的生產周期，資源的影子價格也不完全一樣。企業(yè)決策者可以將企業(yè)資源的影子價格與市場價格相比較，買賣這種資源，使企業(yè)獲利或降低成本，此時該資源的影子價格也將發(fā)生變化，直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。影子價格是一種機會成本。二、建模題（只要求建立模型）1、資源的合理利用問題。P7一般提法：某廠計劃在下一生產周期內生產B1,B2,…Bn種產品，要消耗A1,A2,…Am種資源，已知每件產品所消耗的資源數、每種資源的數量限制以及每件產品可獲得的利潤如表所示，問如何安排生產計劃，才能充分利用現有的資源，使獲得的總利潤最大？設決策變量xj表示下一個周期產品Bj(j=1,2,…n)的產量，則此問題的數學模型可歸結為：求xj，使得2、生產組織與計劃問題。P8一般提法：某工廠用機床A1,A2,…Am加工B1,B2,…Bn種零件。在一個周期內，各機床可能工作的機時（臺時），工廠必須完成各種零件的數量、各機床加工每個零件的時間（機時/個）和加工每個零件的成本（元/個）如表所示，問如何安排各機床的生產任務，才能完成加工任務，又使總成本最低？3、合理配料問題。P11一般提法：某飼養(yǎng)場用n種飼料B1,B2,…Bn配置成含有m種營養(yǎng)成分A1,A2,…Am的混合飼料，其余資料如表所示。問應如何配料，才能既滿足需要，又使混合飼料的總成本最低？4、運輸問題。P175設xij表示由產地Ai運往銷地Bj(i=1,2,…m;j=1,2,….n)的運量，則當產銷平衡時，其模型如下：當產大于銷時，其模型是：當產小于銷時，其模型是：5、合理下料問題。P247一般提法：設用某型號的圓鋼下零件A1,A2,…,Am的毛坯。在一根圓鋼上下料的方式有B1,B2,…Bn種，每種下料方式可以得到各種零件的毛坯數以及每種零件的需要量，如表所示。問怎樣安排下料方式，使得即滿足需要，所用的原材料又最少？設：xj

表示用Bj(j=1.2…n)種方式下料的圓鋼根數，則這一問題的數學模型為：求xj，使得：6、0-1整數規(guī)劃問題。P267例1一般模型nmaxZ=∑cixi；i=1n∑aijxj≤bi（i=1，2，…，m）；j=1s.t.xj=0,1（j=1，2，…，n）。7、目標規(guī)劃P228例2課件：例三一般形式課本例二：已知一個生產計劃的線性規(guī)劃模型為：其中目標函數為總利潤，x1,x2為產品A、B產量?，F有下列目標：1、要求總利潤必須超過2500元；2、考慮產品受市場影響，為避免積壓，A、B的生產量不超過60件和100件；3、由于甲資源供應比較緊張，不要超過現有量140。試建立目標規(guī)劃模型，并用圖解法求解。解：以產品A、B的單件利潤比2.5：1為權系數，模型如下：三、計算題：1、單純形法。P51例1。例1：將線性規(guī)劃問題化為典式,并列初始單純形表解：先引入松馳變量x1、x2、x3，將問題化為典式取初始可行基

此時問題已是關于基的典式，故可直接作初始單純形表，由表Ⅰ可知，初始基可行解（0，0，170，100，150），初始目標函數值再進行第二步迭代，由表Ⅱ可知，新的基可行解（0，30，110,10,0），相應的目標函數再進行第三步迭代，由表Ⅲ可知，檢驗數已全部非正，于是判定已求得最優(yōu)解（50/7，200/7，540/7，0,,0），相應的目標函數最優(yōu)值序號1018000Ⅰ000170100150521002301015001Z01018000Ⅱ0018110103023/5010-2/57/5001-3/51/51001/5Z-54032/5000-18/5Ⅲ01018540/750/7200/7001-23/711/71005/7-3/7010-1/72/7Z-4100/7000-32/7-6/72、某廠準備生產A、B、C三種產品，它們都要消耗勞動力和原材料，已知有關數據如下表：ABC資源限制勞動力63545原材料34530單件利潤（元）415(1)

試建立線性規(guī)劃模型，求使該廠獲利最大的生產計劃。(2)

原材料增加1個單位,能夠使最優(yōu)目標函數值增加或減少多少?解：（1）設決策變量分別表示A、B、C三種產品的產量，則此問題的數學模型為:引入松馳變量將問題化為標準型選初始可行基。令非基變量得初始基可行解。列單純形表序號C41500CBXBbx1x2x3x4x5Ⅰ00x4x5453063510345*00Z04

1

500Ⅱ05x4x31563*-101-13/54/5101/5Z-301-300-1Ⅲ45x1x3531-1/301/3-1/3011-1/52/5Z-350-8/30-1/3-2/3由上表知，最優(yōu)解為X*=（5，0，3，0，0）T，目標函數最優(yōu)值Z*=35。即最優(yōu)生產計劃為：A產品生產5單位，C產品生產3單位，B產品生產0單位。（2）寫出此問題線性規(guī)劃的對偶規(guī)劃，由上表可知對偶規(guī)劃的最優(yōu)解為Y*=（1/3，2/3）。根據對偶理論，對偶規(guī)劃的最優(yōu)解就是原規(guī)劃中變量的影子價格，勞動力和原材料的影子價格分別為1/3，2/3。因此，原材料增加1個單位，按最優(yōu)生產計劃安排生產可以多獲利2/3個單位。3、某公司在計劃期內要安排生產A、B兩種產品（假設市場銷路很好）。生產單位產品的利潤以及所需的勞動力、設備臺時以及原材料的消耗資料由下表給出。產品A產品B資源限制勞動力設備原材料9434510360（工時）200（臺時）300（千克）單位產品利潤70120⑴

試求使該公司獲利最大的生產方案。⑵

設備增加1臺時，能夠使最優(yōu)目標函數增加或減少多少？解：⑴設A、B兩種產品的產量分別是X1、X2，此生產問題的線性規(guī)劃模型是：用單純形法求解，首先引入松馳變量x3、x4、x5，將線性規(guī)劃化成標準型，取松馳變量x3、x4、x5為基變量，求得初始基可行解X=（0，0，360，200，300）。列出單純形表，根據規(guī)則在表中求解。序號C70120000CBXBbX1X2X3X4X5Ⅰ000X3X4X53602003009410045010310001Z070120000Ⅱ00120X3X4X224050307.8010-0.42.5011-0.50.31000.1Z-360034000-12Ⅲ070120X3X1X284202400

-2.12

-3.121.1610

0.4

0.4-0.201-0.12

-0.120.16Z-4280000-13.6-5.2由于最終表中所有的檢驗數都已經成為負數或者零,于是得到最優(yōu)解:目標函數最優(yōu)值（2）寫出此問題的線性規(guī)劃的對偶規(guī)劃，求出對偶規(guī)劃的最優(yōu)解，根據對偶理論，對偶規(guī)劃的最優(yōu)解就是原規(guī)劃中變量的影子價格，勞動工時、設備臺時和原材料的影子價格分別為0，13.6，5.2。因此，設備每增加1臺時，按最優(yōu)計劃安排生產可以多獲利13.6元。4、對偶問題。作業(yè)P136（9）（10）（11）（9）已知線性規(guī)劃問題.①寫出其對偶問題；②已知原問題的最優(yōu)解為3，2，0，試根據互補松弛定理，直接求出對偶問題的最優(yōu)解；（3）如果上述規(guī)劃中的第一個約束為資源約束，寫出這種資源的影子價格。解：①原問題的對偶問題為②由于＞0，＞0，由互補松馳定理得其對應的對偶問題的約束條件為0，即所以對偶問題的最優(yōu)解為③，第一種資源的影子價格為4（10）已知線性規(guī)劃問題其對偶問題的最優(yōu)解為，試根據對偶理論求出原問題的最優(yōu)解。解：此LP問題的對偶問題為將代入對偶問題的約束條件（1）（2）為嚴格不等式，由互補松馳定理推知，。又因。故原問題的兩個約束條件應取等式，有解得，故原問題的最優(yōu)解為（0，0，4，4），目標函數最優(yōu)值為（11）已知線性規(guī)劃問題①寫出其對偶問題；②已知原問題的最優(yōu)解為1，1，2，0試根據對偶理論，直接求出對偶問題的最優(yōu)解。解：①對偶規(guī)劃為②將X*=（1，1，2，0）T代入原方程的約束條件則最后一個約束為松約束，所以又由于，，，由互補松馳定理知，其對偶問題的約束方程必為等式，即所以有即對偶問題的最優(yōu)解為（2，2，1，0）5、運輸問題。P177例1。作業(yè)P213。2（1）⑴P177例1。⑵作業(yè)P213。2（1）已知運輸問題的產銷平衡表與單位運價表如表所示，試用表上作業(yè)法分別求最優(yōu)解（表中M代表充分大的正數）。銷地產地B1B2B3B4產量A137645A224322A343853銷量3322解：單位運價銷地B1B2B3B4產量產地A1①◎②②5，4，2，03764A2②×××2，02432A3×③××3，04385銷量3，1，03，02，02，0（x22,x12,x11,x21）為一個閉回路，σ22=（4+3）-（7+2）=-2＜0（x23,x13,x11,x21）為一個閉回路，σ23=（3+3）-（6+2）=-2＜0（x24,x14,x11,x21）為一個閉回路，σ24=（2+3）-（4+2）=-1＜0（x31,x11,x12,x32）為一個閉回路，σ31=（4+7）-（3+3）=5＞0（x33,x13,x12,x32）為一個閉回路，σ33=（8+7）-（6+3）=7＞0（x34,x14,x12,x32）為一個閉回路，σ34=（5+7）-（4+3）=5＞0單位運價銷地B1B2B3B4產量產地A1③◎◎②53764A2◎×②×22432A3×③××34385銷量3322X11*=3,X12*=0,X13*=0,X14*=2,X21*=0,X23*=2,X32*=3,其余Xij*=0，目標函數的最優(yōu)值為Z*=3×3+0×7+0×6+2×4+0×2+2×3+3×3=32.6、用匈牙利法求解分配問題。P285、7（1）（2）（1）已知效益矩陣為79101213121617（cij）=1516141511121516解：791012－702350234（cij）=13121617－121045104415161415－141201120011121516－1101450144－1◎234√◎1231◎442◎0042◎?3〈422◎??1442√?033√◎134√01012◎44√202222◎?3〈44400??33√0011√√?1◎12◎2244?◎◎?11此時，獨立零元素的個數m＝4。于是已求得最優(yōu)解X13=X22*=X34*=X41*=1，其余Xij*=0。目標函數最優(yōu)值Z﹡＝10×1+12×1+15×1+11×1＝48(2)已知效益矩陣為38210387297（cij）=64275842359106910解：382103－2160810407087297－26507553064（cij）=64275－2420533004284235－262013500029106910－63403422023－1－2－1－1◎4?7?0427053◎64√310423◎?42302425??◎25020222?23√00001√?427◎31◎423◎2425?2◎2◎???1此時，獨立零元素的個數m＝5。于是已求得最優(yōu)解X15*=X23*=X32*=X44*=X51*=1，其余Xij*=0。目標函數最優(yōu)值Z﹡＝3×1+2×1+4×1+3×1+9×1＝217、最短路徑問題。解：整個計算過程分三個階段，從最后一個階段開始，第一階段（C

→D）：

C

有三條路線到終點Df1

(C1

)=1；

f1(C2

)=3；

f1

(C3

)=4第二階段（B

→C）：

B

到C

有六條路線。d(

B1,C1

)+

f1

(C1

)3+14f2

(

B1

)=mind(

B1,C2

)+

f1

(C2

)=min3+3=min6=4d(

B1,C3

)+

f1

(C3

)1+45最短路線為B1→C1

→D路長4d(

B2,C1

)+

f1

(C1

)2+13f2

(

B2

)=mind(

B2,C2

)+

f1

(C2

)=min3+3=min6=3d(

B2,C3

)+

f1

(C3

)1+45最短路線為B2→C1

→D路長3第三階段（

A

→

B

）：

A

到B

有二條路線。d(A,

B1

)＋

f2

(

B1

)2+4f3

(A)=min=min=min｛6,7｝=6d(A,

B2

)＋

f2

(

B2

)4+3所以：最短路線為A→B1→C1

→D。路長6解：整個計算過程分四個階段，從最后一個階段開始，第一階段（D

→E）：

D

有兩條路線到終點E。顯然有

f1

(D1

)=5；

f1(D2

)=2第二階段（C

→D）：

C

到D有三條路線。d(

C1,D1

)+

f1

(D1

)3+58f2

(

C1

)=mind(

C1,D2

)+

f1

(D2

)=min9+2=min11=8d(