運籌學實驗指導書

1、運籌學實 驗 指 導 書適用專業(yè)： 工業(yè)工程 東北大學秦皇島分?？刂乒こ虒W院工業(yè)工程專業(yè)2014年3月前 言對于工業(yè)工程專業(yè)來說，運籌學是一門公共基礎課，是應用性很強的課程。它是利用現代數學研究各種資源的運用、籌劃和相關決策等問題的一門重要學科，主要研究如何在一定條件下科學、合理地分配人力、物力、財力等資源，使實際系統有效運行。它可以用來預測發(fā)展趨勢，制定行動規(guī)劃或優(yōu)選方案，從而為行政管理人員和決策者在決策時提供科學的依據。運籌學的實際運用包括如下六個步驟：問題分析；模型構造；模型求解；模型驗證；解的有效控制；方案實施。隨著計算機軟件的發(fā)展，許多復雜的運籌學計算可以由計算機軟件來完成，如mat

2、lab、mathematica、lingo、excel等。本實驗課程以lingo軟件為工具，使學生在學習了運籌學基本原理的基礎上，進一步掌握使用軟件工具解決運籌學實際問題的方法。本實驗課程共8學時，內容如下：1、軟件編程基礎及其在運籌學中的應用（2學時）2、單純形法的計算機實現（2學時）3、解運輸問題（2學時）4、解目標規(guī)劃、整數規(guī)劃問題和指派問題（2學時）實驗一 軟件編程基礎及其在運籌學中的應用（2學時）一、實驗目的1、 熟悉lingo的操作環(huán)境。2、 學會用lingo編程的方法來求解運籌學問題并讀取結果。二、實驗素材例題1、（利潤最大化問題）某工廠生產甲、乙兩種產品。每生產一個單位的甲產品

3、需要使用A設備1小時，工人勞動時間1小時，可贏利20元；生產一個單位的乙產品需要使用B設備1小時，工人勞動時間2小時，可贏利30元。受工廠條件限制，每天的總勞動時間不能超過120小時，A設備的總使用時間不能超過60小時，B設備的總使用時間不能超過50小時。試建立線性規(guī)劃模型，每天生產多少甲、乙產品，可使利潤最大？解：建立線性規(guī)劃模型。設x1為每天生產甲產品的數量，x2為每天生產乙產品的數量。由此得到線性規(guī)劃模型：max=20*x1+30*x2;x1+2*x2<=120;x1<=60;x2<=50;x1>=0;x2>=0;將程序輸入lingo軟件，不需輸入最后兩行（

4、變量的非負約束），點擊solve按鈕，得到求解結果如下： Global optimal solution found. -（已找到全局最優(yōu)解） Objective value: 2100.000 -（最優(yōu)目標函數值） Infeasibilities: 0.000000 -（找到的解違反了幾個約束條件） Total solver iterations: 1 -（迭代次數） Variable Value Reduced Cost X1 60.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 2100.000

5、1.000000 2 0.000000 15.00000 3 0.000000 5.000000 4 20.00000 0.000000由上述結果得到，每天生產甲產品60個單位，乙產品30個單位，每天可獲得的最大利潤是2100元。（注：大家在“help”中查找“solver status”，即可查詢到solver status box的詳細解釋。關于lingo軟件的使用問題都可以通過查詢help文件得到答案）習題1、max=6*x7+7*x2;7*x1+5*x2<=3500;5*x1+8*x2<=4000;2*x1+5*x2<=2000;習題2、min=x1+x2;x1-x2

6、<=-1;x1+x2<=-1;習題3、（裝船問題）設有甲、乙、丙三種貨物需要裝船。它們的積載因數分別為1.5、2和1（m3/kg），艙時量（裝船速度）分別為50、100和40（kg/h），總裝貨量為1000kg，貨物總容積不能超過1400m3。問該船應各裝甲、乙、丙貨物多少千克，才能使裝貨時間最短？習題4、（最高性價比問題）某飼養(yǎng)場飼養(yǎng)動物出售。設每頭動物每天至少需要700g蛋白質、30g礦物質、100mg維生素?，F有五種飼料可供選用，其每千克的營養(yǎng)成分含量及價格如下表所示。要求確定既滿足動物需要、又使費用最低的飼料選擇方案。飼料蛋白質（g）礦物質（g）維生素（mg）價格（元/千克

7、）1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8注：粗看起來，目標函數與約束條件是有顯著區(qū)別的，但細致分析，就可以發(fā)現他們之間沒有本質上的區(qū)別。例如，一個企業(yè)增加生產量，創(chuàng)造高的經濟收入顯然是目標。這個企業(yè)擁有的資金、設備是限制條件，把擁有的資金和設備說成是目標是不妥的，但若要求一個企業(yè)“以最少的資金創(chuàng)造最高的經濟收入”，這里的資金就有目標的含義。所以給目標加上某一限制，就成了約束條件。習題5、（人力資源分配問題）某晝夜服務的公交線路每天各時間段內所需要的工作人員人數如下表所示。設工作人員在各時間段一開始時上班，并連續(xù)工作8小時。問該公交線

8、路該如何安排工作人員，才能既滿足工作需要，又可以配備最少的工作人員？班次時間段所需人數16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030習題6、（投資計劃問題）某地區(qū)在今后3年內有4種投資機會：第一種是在3年內每年年初投資，年底可獲利潤20%，并可將本金收回。該投資機會每年都有，投資者可自行決定到底是每年都這樣投資，還是只選擇其中的一、兩年進行這種投資。第二種是在第一年年初投資，第二年年底可獲利50%，并可將本金收回，但該項投資金額不超過200萬元。請注意只有第一年年初有這樣的投資機會，第二年年初

9、就沒有了。第三種是在第二年年初投資，第三年年底收回本金，并獲利潤60%，但該項投資金額不超過150萬元。請注意只有第二年年初有這樣的投資機會。第四種是在第三年年初投資，當年底收回本金，并獲利潤40%，但該項投資金額不超過100萬元。現在該地區(qū)準備了300萬元資金，如何制定投資方案，使到第三年年末本利的和最大？例題2、（lingo程序的通用形式）在書寫數據量較大的程序時，使用通用形式更加簡便。請大家對比以下兩個程序，它們的功能相同，但書寫形式不同：直接求解的程序：max=2*x1+5*x2;x1+x3=4;x2+x4=3;x1+2*x2+x5=8;通用形式的程序：sets:var_num/1.5

10、/:c,x;const_num/1.3/:b;matrix(const_num,var_num):A;endsetsmax=sum(var_num:c*x);for(const_num(i):sum(var_num(j):A(I,j)*x(j)=b(i);data:c=2,5,0,0,0;b=4,3,8;A=1,0,1,0,0, 0,1,0,1,0, 1,2,0,0,1;enddata三、實驗內容及步驟1、 打開lingo軟件文件夾，雙擊“Lingo11.exe”,打開軟件。2、 實踐例題1，初步學會讀report。請注意如下幾點：（1） 程序第一行的max表示求極大，min表示求極小；（2）

11、 注意每個語句后面加上分號；（3） Lingo軟件保持著單純形法的特點，默認為所有變量都是非負限制的，因此不需把變量非負限制的約束條件寫入模型；3、 實踐習題1、2，觀察report有何不同。4、 解習題3、4的運籌學問題。習題5、6為附加題，可依個人能力選做。5、 實踐例題2。四、實驗結果本部分由學生填寫。請仿照例題1的解題步驟，將實驗步驟3、4的結果寫在實驗報告中。五、實驗儀器及工具Lingo軟件。實驗二 單純形法的計算機實現（2學時）一、 實驗目的1、 進一步練習運用lingo軟件去解決線性規(guī)劃、對偶等實際問題。2、 理解lingo report中slack or surplus以及du

12、al price的經濟含義。3、 學會使用lingo進行靈敏度分析。二、 實驗素材例題1、同實驗一的例題1。（利潤最大化問題）某工廠生產甲、乙兩種產品。每生產一個單位的甲產品需要使用A設備1小時，工人勞動時間1小時，可贏利20元；生產一個單位的乙產品需要使用B設備1小時，工人勞動時間2小時，可贏利30元。受工廠條件限制，每天的總勞動時間不能超過120小時，A設備的總使用時間不能超過60小時，B設備的總使用時間不能超過50小時。試建立線性規(guī)劃模型，每天生產多少甲、乙產品，可使利潤最大？解：建立線性規(guī)劃模型。設x1為每天生產甲產品的數量，x2為每天生產乙產品的數量。由此得到線性規(guī)劃模型：max=2

13、0*x1+30*x2;x1+2*x2<=120;x1<=60;x2<=50;將程序輸入lingo軟件，不需輸入最后兩行（變量的非負約束），點擊solve按鈕，得到求解結果如下： Global optimal solution found. -（已找到全局最優(yōu)解） Objective value: 2100.000 -（最優(yōu)目標函數值） Infeasibilities: 0.000000 Total solver iterations: 1 Variable Value Reduced Cost X1 60.00000 0.000000 X2 30.00000 0.000000

14、 Row Slack or Surplus Dual Price 1 2100.000 1.000000 2 0.000000 15.00000 3 0.000000 5.000000 4 20.00000 0.000000由上述結果得到，每天生產甲產品60個單位，乙產品30個單位，每天可獲得的最大利潤是2100元。A、 report的含義：B、 Reduced cost：檢驗數取負。slack or surplus：表示在線性規(guī)劃中在最優(yōu)解處，松弛變量或剩余變量的值。如果這個值為0，則表示此約束為緊約束，也就是說，改動此時約束的值會影響到最優(yōu)解的值。如果不為0，則表示此約束為松約束，也就是說

15、，在一定的范圍內改動約束的值，并不影響最優(yōu)解的值。那么，當緊約束的值改變時，最優(yōu)解改變多少呢？dual price會告訴我們。Dual price：對偶價格（影子價格），表示在最優(yōu)解下，資源增加1單位時，效益的增量（即資源增加1單位對效益的貢獻）。它與原問題的約束條件相聯系，而不與變量相聯系。例如在本題中，例如在本題中，總勞動時間每增加1小時，將會使利潤增加15元；增加B設備的生產能力（可使用時間），對利潤沒有影響；B設備的生產能力由50小時一直減小到30小時，都對利潤沒有影響，如果再接著往下減，就會有影響了。從dual price中我們可以看出，增加某些資源會對效益有提升，那么，資源是不是能

16、夠無限制增加呢？靈敏度分析會告訴我們。C、 靈敏度分析：在作靈敏度分析之前，需要對lingo軟件中的參數進行調整，其方法如下圖所示： 然后在完成程序計算后，在程序運行狀態(tài)窗口下，單擊LINGO下的Range按鈕，則軟件會彈出靈敏度分析報告。例如，每增加1小時的勞動時間，利潤可增加15元，但最多只能增加40小時，達到160小時，再增加勞動時間就可能達不到增加利潤的效果了。同樣，A設備的生產能力也只能增加60小時，達到120小時。習題1、某公司有甲乙兩個工廠生產A、B兩種產品，產品分別由甲乙兩個工廠中的加工車間和裝配車間來完成，有關這兩個工廠中各車間的生產成本、工時定額和可利用工時限額的資料如下表

17、所示。這兩種產品運到南北兩個地區(qū)去出售，有關最大的市場銷售量、售價、銷售費用和運輸費用如下表所示?，F公司希望采取一些措施來提高經濟效益，為此要弄清應關注哪些問題。是擴大銷售量呢？還是改善工廠的生產能力？若擴大銷售量呢，是首先擴大南方市場還是北方市場？是先擴大產品A的銷售量還是擴大B的銷售量？如果要增加工廠中的有效工時，那么首先關注哪一家工廠及哪一個車間？資料出售到南方出售到北方產品A產品B產品A產品B最大銷售量（件）90001200075006000每件售價（元）12171318銷售費用（元/件）4534運輸費用（元/件）工廠甲1122工廠乙2212資料工廠甲工廠乙產品A產品B產品A產品B單件

18、生產成本5645工時定額（小時）加工車間1.5212裝配車間122.51.5可利用工時定額（小時）加工車間1200016000800022000裝配車間共30000共40000習題2、某工廠生產A、B、C三種產品，其所需勞動力、材料等有關數據如下表所示。要求：（1）確定獲利最大的生產方案；（2）產品A、B、C的利潤分別在什么范圍內變動時，上述最優(yōu)方案不變；（3）如果生產一種新產品D，每件消耗勞動力8個單位，消耗材料2個單位，每件可獲利3元，該種產品是否值得生產？（4）如果勞動力數量不增，材料不足時可從市場購買，每單位0.4元，問該廠要不要購進原材料擴大生產，若需購進，以購多少為宜？資源產品可用

19、量（單位）ABC勞動力63545材料34530產品利潤（元/件）314三、 實驗內容及步驟1、 打開lingo軟件文件夾，雙擊“Lingo11.exe”,打開軟件。2、 實踐例題1。3、 針對上次實驗中的習題3、4，分析report中影子價格的經濟含義。4、 解本實驗的習題1、2。四、實驗結果本部分由學生填寫。將實驗步驟3、4的結果寫在實驗報告中。五、實驗儀器及工具Lingo軟件。實驗三 解運輸問題（2學時）一、實驗目的1、 學會使用lingo進行運輸問題的求解。二、實驗素材習題1、（產銷平衡問題）將貨物從兩個產地A、B運往三個銷售地1、2和3。各產地供應數量、各銷售地需求數量及運費如下圖所示

20、。問如何組織運輸，才能使總運輸費用最少。習題2、（供過于求問題）有三個產地的產品需要運往四個銷地，各產地供應數量、各銷售地需求數量及運費如下表所示。如何調運使總運費最少？B1B2B3B4產量A1626730A2495325A3881521銷量15172212習題3、（供不應求問題）有三個產地的產品需要運往四個銷地，各產地供應數量、各銷售地需求數量及運費如下表所示。如何調運使總運費最少？B1B2B3B4產量A13116107A219978A375889銷量7867習題4、（轉運問題）對于習題1，假設貨物可以在產地與產地間、銷地與銷地間轉運，如下圖所示。（1）問如何組織運輸，才能使總運輸費用最少。

21、（2）對比本結果與習題1的計算結果，你能得出什么結論？習題5、（運輸問題悖論）有四個產地的產品需要運往五個銷地，各產地供應數量、各銷售地需求數量及運費如下表所示。（1）如何調運使總運費最少？（2）如果A1、A3多產5個單位，B2多銷10個單位，那么最優(yōu)運輸方案是什么？總運費又是多少？（3）從本實驗結果中，你能發(fā)現些什么嗎？請盡量深入地寫出你的結論、想法等。B1B2B3B4B5產量A11415613147A216922131618A38511456A41241891015銷量41112811三、實驗內容及步驟1、 打開lingo軟件。2、 解習題14。習題5為選做。四、實驗結果本部分由學生填寫。

22、將習題15的結果寫在實驗報告中。五、實驗儀器及工具Lingo軟件。實驗四 解目標規(guī)劃、整數規(guī)劃問題和指派問題（2學時）一、實驗目的1、 學會使用lingo進行整數規(guī)劃、指派問題和目標規(guī)劃問題的求解。二、實驗素材習題1、（整數規(guī)劃問題-排產問題）某工廠生產A1和A2兩種產品，需要經過B1、B2、B3三道工序，單位工時和利潤及各工序每周工時限額如下表所示。問：工廠應如何安排生產，才能使總利潤最大？產品工序單位利潤B1B2B3A10.30.20.325A20.70.10.540工時限額（小時/周）250100200提示：為滿足條件“變量x取整數”，只需加上一個限制函數gin（x）。習題2、（0-1型

23、整數規(guī)劃問題-投資項目的選擇問題）某地區(qū)有5個可考慮的投資項目，其期望純收益與所需投資額如下表所示。這5個項目中，在項目、和之間必須且只能選擇一項；項目和之間至少選擇一項；和兩個項目是密切相關的，以的實施為前提。該地區(qū)共籌集到資金15萬元，究竟應該選擇哪些項目才能使其期望純收益最大呢？工程項目期望純收益（萬元）所需投資（萬元）10.06.08.04.07.02.06.04.09.05.0提示：1、為滿足條件“變量x取0或1”，只需加上一個限制函數bin（x）。2、期望純收益指已經扣除投資之后的收益。3、該模型涉及一類選擇問題。習題3、（整數規(guī)劃問題與0-1型整數規(guī)劃問題-選址問題）某市計劃在新

24、建的5個居民小區(qū)中的2個內各設立一所小學。下表給出了各小區(qū)內及各小區(qū)間的平均步行時間（分鐘）及各居民小區(qū)的小學生人數。該市教委希望：兩所小學的招生人數基本持平，學生總的上學步行時間最短。請向該市教委提供決策建議：兩所小學分別建于哪兩個小區(qū)，以及各居民小區(qū)學生應分配到哪所小學上學？小區(qū)如果在該小區(qū)建立小學小學生人數1234515201525102002204201525180315206251530042515254121605102515125350習題4、（指派問題-游泳隊員選拔問題）某高校準備從5名游泳隊員中選擇4人組成接力隊，參加市里的4*100m混合泳接力比賽。5名隊員4種泳姿的百米平

25、均成績如下表所示，問應如何選拔隊員組成接力隊？隊員蝶泳仰泳蛙泳自由泳甲66.875.68758.6乙57.26666.453丙7867.884.659.4丁7074.269.657.2戊67.47183.862.4例題1、（目標規(guī)劃問題-工廠排產問題）某工廠生產A、B兩種產品，需要用不銹鋼、銅材和鋁材三種主要原料。各種材料的庫存量、單位產品材料消耗定額及利潤等數值如下表所示。（1）若該廠生產的產品都能銷售出去，問該廠的決策者應如何安排A、B兩種產品的產量，使工廠的利潤最大？（2）若以利潤達到3000元或以上作為主要目標，恰好用完鋁材作為第二目標，則應該如何安排A、B兩種產品的產量？每件材料消耗

26、產品材料庫存千克/件ABKg材料不銹鋼23120銅材2180鋁材-130利潤6070解：（1） 顯然，這一問題可以用線性規(guī)劃模型來描述。設x1、x2分別表示A、B兩種產品的產量，則問題的數學模型為：max=60*x1+70*x2;2*x1+3*x2<=120;2*x1+x2<=80;x2<=30;用lingo求解上述線性規(guī)劃問題，得到最優(yōu)解x1=30，x2=20，最大利潤為3200元。注：從線性規(guī)劃角度上看，提出的問題似乎已經得到了圓滿的解決。但是，如果從工廠計劃人員的立場上對此進行評價，問題就沒有這么簡單。在實際計劃工作中，工廠計劃部門通常是預先制定一個利潤指標，然后按照指

27、標來進行材料準備和排產；而且計劃人員追求的目標往往不止一個，而這些目標在本質上又經常是不可比較和相互矛盾的，例如“以最少的資金創(chuàng)造最高的產量”，因此需要在若干目標之間進行權衡折中。在這種時候，目標規(guī)劃就非常有用。目標規(guī)劃是一種數學方法，它是在企業(yè)決策者規(guī)定了若干指標值及實現這些指標的先后順序后，在給定的有限資源條件下，求出總的偏離指標值最小的方案，稱這個方案為滿意方案。因此，目標規(guī)劃被認為是一種較線性規(guī)劃更接近實際決策過程的決策工具。（2）A、建立目標規(guī)劃模型。設d1p和d1m是主要目標（利潤>=3000元）的偏差變量，d2p和d2m是次要目標（恰好用完鋁材）的偏差變量，p1和p2分別為

28、主要目標和次要目標的優(yōu)先因子。則主要目標的目標函數可表示為：min=p1*d1m，次要目標的目標函數可表示為：min=p2*(d2p+d2m)。于是總的目標函數為：min=p1*d1m+p2*(d2p+d2m)。故本題的數學模型為：min=p1*d1m+p2*(d2p+d2m); - 目標函數60*x1+70*x2+d1m-d1p=3000; - 目標約束1x2+d2m-d2p=30; - 目標約束22*x1+3*x2<=120; - 系統（絕對）約束12*x1+x2<=80; - 系統（絕對）約束2B、使用lingo對本模型進行求解。使用序貫式算法。（根據優(yōu)先級的先后次序，將目標

29、規(guī)劃問題分解成一系列的單目標規(guī)劃問題，依次求解）先求第一級目標（主要目標）：min=d1m;60*x1+70*x2+d1m-d1p=3000;x2+d2m-d2p=30;2*x1+3*x2<=120;2*x1+x2<=80;運行結果為： Global optimal solution found. Objective value: 0.000000 Infeasibilities: 0.000000 Total solver iterations: 2 Variable Value Reduced Cost D1M 0.000000 1.000000 X1 15.00000 0.000000 X2 30.00000 0.000000 D1P 0.000000 0.000000 D2M 0.000000 0.000000 D2P 0.000000 0.000000 Row Slack or Surplus Dual Price 1 0.000000 -1.000000 2 0.000000 0.000000 3 0.000000 0