數(shù)學(xué)規(guī)劃模型PPT精選文檔

1、課程內(nèi)容和目的： 了解數(shù)學(xué)規(guī)劃模型的一般理論，介紹一些典型的規(guī)劃模型，如生產(chǎn)計(jì)劃安排問(wèn)題、資源配置問(wèn)題、運(yùn)輸問(wèn)題、下料問(wèn)題、指派問(wèn)題、選址問(wèn)題等。能通過(guò)分析建立一些實(shí)際問(wèn)題的數(shù)學(xué)規(guī)劃模型，會(huì)用工具軟件熟練求解線性規(guī)劃，整數(shù)規(guī)劃，非線性規(guī)劃等問(wèn)題。教學(xué)難點(diǎn)和重點(diǎn)： 重點(diǎn)掌握規(guī)劃模型的三要素，建立規(guī)劃模型的方法以及工具求解。難點(diǎn)是模型求解算法的理解和如何將實(shí)際問(wèn)題逐步轉(zhuǎn)換成規(guī)劃問(wèn)題。課程學(xué)時(shí)：10學(xué)時(shí)第四章第四章 數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 實(shí)際問(wèn)題中實(shí)際問(wèn)題中的優(yōu)化模型的優(yōu)化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決

2、策變量決策變量f(x)目標(biāo)函數(shù)目標(biāo)函數(shù)gi(x) 0約束條件約束條件多元函數(shù)多元函數(shù)條件極值條件極值 決策變量個(gè)數(shù)決策變量個(gè)數(shù)n和和約束條件個(gè)數(shù)約束條件個(gè)數(shù)m較大較大 最優(yōu)解在可行域最優(yōu)解在可行域的邊界上取得的邊界上取得 數(shù)數(shù)學(xué)學(xué)規(guī)規(guī)劃劃線性規(guī)劃線性規(guī)劃非線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃重點(diǎn)在模型的建立和結(jié)果的分析重點(diǎn)在模型的建立和結(jié)果的分析4.1 4.1 線性規(guī)劃模型線性規(guī)劃模型 線性規(guī)劃(LP)研究的實(shí)際問(wèn)題多種多樣的，它在工農(nóng)業(yè)生產(chǎn)、經(jīng)濟(jì)管理、優(yōu)化設(shè)計(jì)與控制等領(lǐng)域都有廣泛應(yīng)用。如資源分配問(wèn)題、生產(chǎn)計(jì)劃問(wèn)題、物資運(yùn)輸問(wèn)題、合理下料問(wèn)題、庫(kù)存問(wèn)題、勞動(dòng)力安排問(wèn)題、最優(yōu)設(shè)計(jì)問(wèn)題等等。線性規(guī)劃

3、模型的求解方法目前仍以單純形法為主要方法，該方法于1947年由美國(guó)數(shù)學(xué)家丹齊齊格（G.B.Dantzig）提出，經(jīng)過(guò)60多年的發(fā)展完善，已經(jīng)形成比較成熟的算法，同時(shí)配合計(jì)算機(jī)技術(shù)的廣泛應(yīng)用使得該方法得到空前的普及應(yīng)用。目前，大多數(shù)數(shù)學(xué)軟件都可以求解一般線性規(guī)劃模型，這一節(jié)主要采用Matlab和Lingo軟件。 問(wèn)題提出 : 加工廠用牛奶生產(chǎn)A1、A2兩種奶制品，1桶牛奶可以在設(shè)備甲上用12小時(shí)加工成3公斤A1，或者在設(shè)備乙上用8小時(shí)加工成4公斤A2。根據(jù)市場(chǎng)需求，生產(chǎn)的A1、A2能全部售出，且每公斤A1獲利24元，每公斤A2獲利16元。現(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動(dòng)

4、時(shí)間為480小時(shí)，并且設(shè)備甲每天至多能加工100公斤A1，設(shè)備乙的加工能力沒(méi)有限制。試為該廠制定一個(gè)生產(chǎn)計(jì)劃，使每天獲利最大，并進(jìn)一步討論以下3個(gè)附加問(wèn)題： 1）若用35元可以額外購(gòu)買(mǎi)到1桶牛奶，是否作這項(xiàng)投資？若投資，每天最多購(gòu)買(mǎi)多少桶牛奶？ 2）若可以聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，付給臨時(shí)工人的工資最多是每小時(shí)幾元？ 3）由于市場(chǎng)需求變化，每公斤A1的獲利增加到30元，應(yīng)否改變生產(chǎn)計(jì)劃？案例1：奶制品的生產(chǎn)與銷(xiāo)售 案例分析案例分析1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A

5、1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買(mǎi)到元可買(mǎi)到1桶牛奶，買(mǎi)嗎？若買(mǎi)，每天最多買(mǎi)多少桶牛奶，買(mǎi)嗎？若買(mǎi)，每天最多買(mǎi)多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：每天：1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶桶牛奶生產(chǎn)牛奶生產(chǎn)A1 x2桶桶牛奶生產(chǎn)牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)間勞動(dòng)時(shí)間 4808

6、1221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天5021 xx48081221 xx10031x0,21xx直線直線AB下方下方直線直線BC下方下方直線直線CD左側(cè)左側(cè)平面左上角平面左上角約約束束條條件件216472maxxxz目標(biāo)目標(biāo)函數(shù)函數(shù) 在在B(20,30)點(diǎn)得到最優(yōu)解點(diǎn)得到最優(yōu)解z=c (常數(shù)常數(shù)) 等值線等值線最大利潤(rùn)為最大利潤(rùn)為72*20+64*3

7、0=3360元元20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1,30桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2模型求解模型求解-圖解法圖解法x1x20l1l2l3l4l5問(wèn)問(wèn)1：35元可買(mǎi)到元可買(mǎi)到1桶牛奶，買(mǎi)嗎？桶牛奶，買(mǎi)嗎？最大利潤(rùn)為最大利潤(rùn)為72*20+64*30=3360元元最大利潤(rùn)為最大利潤(rùn)為72*18+64*33=3408元元增加增加1桶牛奶，利潤(rùn)增加桶牛奶，利潤(rùn)增加48元。元。 4835買(mǎi)！買(mǎi)！1250 xx1251xx35元可買(mǎi)到元可買(mǎi)到1桶牛奶，若買(mǎi)，每天最多買(mǎi)多少桶牛奶，若買(mǎi)，每天最多買(mǎi)多少? 10桶當(dāng)直線當(dāng)直線AB向上平移到向上平移到x1+x2=60的位置時(shí)，可行域?qū)⒉辉僮兓?。的位置時(shí)，可行域?qū)⒉辉僮兓?。?/p>

8、增加牛奶供應(yīng)時(shí)，因加工時(shí)間有限（超過(guò)了藍(lán)色線），無(wú)法再增加牛奶供應(yīng)時(shí)，因加工時(shí)間有限（超過(guò)了藍(lán)色線），無(wú)法得到加工。得到加工。1250 xx1260 xx問(wèn)問(wèn)2：可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? 12128480 xx12128481xx最大利潤(rùn)為最大利潤(rùn)為3360元元最大利潤(rùn)為最大利潤(rùn)為3362元元增加增加1小時(shí)的工作時(shí)間，利潤(rùn)增加小時(shí)的工作時(shí)間，利潤(rùn)增加2元元。2元元問(wèn)問(wèn)3： A1的獲利增加到的獲利增加到 30元元/kg，應(yīng)否改變生產(chǎn)計(jì)劃？，應(yīng)否改變生產(chǎn)計(jì)劃？ 不改變不改變獲利的改變，引起等值獲利的改變，引起等值線線z=c傾斜程度的改變

9、，傾斜程度的改變，只要傾斜程度介于只要傾斜程度介于AB和和BC的傾斜程度之間，則的傾斜程度之間，則生產(chǎn)計(jì)劃不變。生產(chǎn)計(jì)劃不變。12max24 316 4zxx A2獲利固定，獲利固定，A1獲利允許的變化范圍為獲利允許的變化范圍為64/3, 32。A1獲利固定，獲利固定，A2獲利允許的變化范圍為獲利允許的變化范圍為12, 18。12max30 316 4zxx 注：模型求解模型求解 軟件實(shí)現(xiàn)軟件實(shí)現(xiàn) LINGO 9.0 max =72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; Global optimal solution found. Objective

10、value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost （變量（變量) (取值）取值） （檢驗(yàn)系數(shù)）（檢驗(yàn)系數(shù)） X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price （行（行) (松弛或剩余變量取值）松弛或剩余變量取值） (對(duì)偶或影子價(jià)格）對(duì)偶或影子價(jià)格） 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000D

11、O RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)，利潤(rùn)3360元。元。 結(jié)果解釋結(jié)果解釋 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost （變量（變量) (取值）取值） （檢驗(yàn)系數(shù)）（檢驗(yàn)系數(shù)） X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price （

12、行（行) (松弛或剩余變量取值）松弛或剩余變量取值） (對(duì)偶或影子價(jià)格）對(duì)偶或影子價(jià)格） 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000原料無(wú)剩余原料無(wú)剩余時(shí)間無(wú)剩余時(shí)間無(wú)剩余加工能力剩余加工能力剩余40三三種種資資源源“資源資源” 剩余為零的約束為剩余為零的約束為緊約束緊約束（有效約束）（有效約束） max =72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;結(jié)果解釋結(jié)果解釋 Global optimal solution found. Objec

13、tive value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時(shí)單位時(shí)“效益效益”的增的增量量 原料增加原料增加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)48 時(shí)間增加時(shí)間增

14、加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)2 加工能力增長(zhǎng)不影響利潤(rùn)加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格影子價(jià)格 35元可買(mǎi)到元可買(mǎi)到1桶牛奶，要買(mǎi)嗎？桶牛奶，要買(mǎi)嗎？35 120095.7x1+93x2+89.7x3+95.2x4+90.6x5+74.2x6+88.5x7+92.9x81750781x1+2106x2+5100 x3+93x4+8x6+278x8245040 x1+9x2+4x3+4x4+183.6x5+6x6+0.2x7+21x842240 x1+460 x2+290 x3+90 x4+190 x5+240 x6+280 x7+210 x82101.8x1+2.4x2+2.6x3+0.9x

15、4+1.7x5+4.6x6+3.9x7+1.2x817.5x1+x2+x3+x4+x5+x6+x7+x8=150 x120 x510 x335x230 x430 x630 x730 x830end: 模模型型求求解解 在Lindo6.1中輸入如下程序語(yǔ)句 LP OPTIMUM FOUND AT STEP 22 OBJECTIVE FUNCTION VALUE 1) 635.0000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 X3 35.000000 0.000000 X4 30.000000

16、0.000000 X5 5.000000 0.000000 X6 0.000000 1.000000 X7 0.000000 6.000000 X8 30.000000 0.000000運(yùn)行后得到如下結(jié)果：可見(jiàn)最佳的食物搭配方案為一周安排20千克小白菜，30千克菠菜，35千克胡蘿卜，30千克小黃瓜，5千克豆芽和30千克蕃茄，方案最小費(fèi)用為635元。小白菜菠菜胡蘿卜小黃瓜豆芽玉米香菇蕃茄結(jié)結(jié)果果分分析析生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大；怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大；運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題(Trans

17、portation Problem)各種類(lèi)型的貨物裝箱，由于受體積、重量等限制，各種類(lèi)型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。案例3：自來(lái)水輸送與貨機(jī)裝運(yùn)問(wèn)題其他費(fèi)用其他費(fèi)用: :450元元/千噸千噸 應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？ 若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？ 元元/千噸千噸甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理費(fèi)引水管理費(fèi)例例1 自來(lái)水輸

18、送自來(lái)水輸送收入：收入：900元元/千噸千噸 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20?。憾。?0；40水庫(kù)供水量水庫(kù)供水量(千噸千噸)小區(qū)基本用水量小區(qū)基本用水量(千噸千噸)小區(qū)額外用水量小區(qū)額外用水量(千噸千噸)（以天計(jì)）（以天計(jì)）總供水量：總供水量：160確定送水方案確定送水方案使利潤(rùn)最大使利潤(rùn)最大問(wèn)題問(wèn)題分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20?。憾。?0；40 總需求量總需求量(300)每個(gè)水庫(kù)最大供水量都提高一每個(gè)水庫(kù)最大供水量都提高一倍倍利潤(rùn)利潤(rùn) = 收入收入(900) 其它費(fèi)用其它費(fèi)用(

19、 (450) 引水管理費(fèi)引水管理費(fèi)利潤(rùn)利潤(rùn)(元元/千噸千噸)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxZMax供應(yīng)供應(yīng)限制限制B, C 類(lèi)似處理類(lèi)似處理50:A14131211xxxx10014131211xxxx問(wèn)題討論問(wèn)題討論 確定送水方案確定送水方案使利潤(rùn)最大使利潤(rùn)最大需求約束可以不變需求約束可以不變求解求解 OBJECTIVE FUNCTION VALUE 1) 88700.00 VARIABLE VALU

20、E REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 總利潤(rùn)總利潤(rùn) 88700（元）（元） A(100)B(120)

21、C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030如何如何裝運(yùn)，裝運(yùn)，使本次飛行使本次飛行獲利最大？獲利最大？ 三個(gè)貨艙三個(gè)貨艙最大最大載載重重( (噸噸),),最大容積最大容積( (米米3 3) ) 例例2 貨機(jī)裝運(yùn)貨機(jī)裝運(yùn) 重量（噸）重量（噸）空間空間( 米米3/噸）噸）利潤(rùn)（元利潤(rùn)（元/噸）噸）貨物貨物1184803100貨物貨物2156503800貨物貨物3235803500貨物貨物4123902850三個(gè)貨艙中實(shí)際載重必須與其最大三個(gè)貨艙中實(shí)際載重必須與其最大載載重成比例重成比例 前倉(cāng)：前倉(cāng)：10；6800中倉(cāng)：中倉(cāng)：16；

22、8700后倉(cāng)：后倉(cāng)：8；5300飛機(jī)平衡飛機(jī)平衡決策決策變量變量 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量( (噸）噸）i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉(cāng)分別代表前、中、后倉(cāng))模型假設(shè)模型假設(shè) 每種貨物可以分割到任意??；每種貨物可以分割到任意?。回洐C(jī)裝運(yùn)貨機(jī)裝運(yùn)每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 模型建立模型建立 貨艙貨艙容積容積 目標(biāo)目標(biāo)函數(shù)函數(shù)( (利潤(rùn)利潤(rùn))約束約束條件條件 )(2850)(3500)(3800)(3100

23、434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312111xxxx870039058065048042322212xxxx530039058065048043332313xxxx貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型建立模型建立 貨艙貨艙重量重量 1041312111xxxx1642322212xxxx843332313xxxx10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量約束約束條件條件平衡平衡要求要求 81610433323134232221241312111xxxxxxxx

24、xxxx貨物貨物供應(yīng)供應(yīng) 18131211xxx15232221xxx23333231xxx12434241xxx貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型建立模型建立 10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量 OBJECTIVE FUNCTION VALUE 1) 121515.8 VARIABLE VALUE REDUCED COST X11 0.000000 400.000000 X12 0.000000 57.894737 X13 0.000000 400.000000 X21 10.000000 0.000000 X22 0.00000

25、0 239.473679 X23 5.000000 0.000000 X31 0.000000 0.000000 X32 12.947369 0.000000 X33 3.000000 0.000000 X41 0.000000 650.000000 X42 3.052632 0.000000 X43 0.000000 650.000000 貨物貨物2：前倉(cāng)：前倉(cāng)10, ,后倉(cāng)后倉(cāng)5； 貨物貨物3: : 中倉(cāng)中倉(cāng)13, 后倉(cāng)后倉(cāng)3；貨物貨物4: : 中倉(cāng)中倉(cāng)3。貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型求解模型求解 最大利潤(rùn)約最大利潤(rùn)約121516元元貨物貨物供應(yīng)點(diǎn)供應(yīng)點(diǎn)貨艙貨艙需求點(diǎn)需求點(diǎn)平衡要求平衡要求運(yùn)輸運(yùn)輸

26、問(wèn)題問(wèn)題運(yùn)輸問(wèn)題的擴(kuò)展運(yùn)輸問(wèn)題的擴(kuò)展4.2 4.2 整數(shù)規(guī)劃模型整數(shù)規(guī)劃模型 實(shí)際問(wèn)題中經(jīng)常遇到貨物是不可分割的，如人，動(dòng)物，整體裝配的設(shè)備等，這時(shí)候除了題目本身的約束外，還要加上決策變量的整數(shù)約束，這就是這節(jié)要介紹的整數(shù)規(guī)劃問(wèn)題（Integer Programing ）。 整數(shù)規(guī)劃又可分為線性整數(shù)規(guī)劃和非線性整數(shù)規(guī)劃，這一節(jié)只介紹線性整數(shù)規(guī)劃。整數(shù)線性規(guī)劃中如果所有決策變量都是整數(shù)，則稱(chēng)為純整數(shù)規(guī)劃；若只有部分變量為整數(shù)，則稱(chēng)為混合整數(shù)規(guī)劃；若決策變量只能取0或1，則稱(chēng)為0-1規(guī)劃。 求解整數(shù)規(guī)劃的算法主要是分枝定界法和割平面法，這兩種方法都是以求解線性規(guī)劃的方法為基礎(chǔ)。而0-1規(guī)劃的求解使

27、用隱枚舉法，它不需要用單純形法先求解線性規(guī)劃，而是依次檢查變量等于0或1的某種組合，以便使目前最好的可行解不斷加以改進(jìn)，最終獲得最優(yōu)解。 整數(shù)規(guī)劃的求解主要使用Lindo和Lingo軟件。 如果生產(chǎn)某一類(lèi)型汽車(chē)，則至少要生產(chǎn)如果生產(chǎn)某一類(lèi)型汽車(chē)，則至少要生產(chǎn)8080輛，輛， 那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？汽車(chē)廠生產(chǎn)三種類(lèi)型的汽車(chē)，已知各類(lèi)型每輛車(chē)對(duì)鋼汽車(chē)廠生產(chǎn)三種類(lèi)型的汽車(chē)，已知各類(lèi)型每輛車(chē)對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量。材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量。 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材（噸）鋼材（噸） 1.5 3 5 6

28、00勞動(dòng)時(shí)間（小時(shí)）勞動(dòng)時(shí)間（小時(shí)） 280 250 400 60000利潤(rùn)（萬(wàn)元）利潤(rùn)（萬(wàn)元） 2 3 4 制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大。制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大。案例4：汽車(chē)生產(chǎn)計(jì)劃制定設(shè)每月生產(chǎn)小、中、大型設(shè)每月生產(chǎn)小、中、大型汽車(chē)的數(shù)量分別為汽車(chē)的數(shù)量分別為x1, x2, x3321432xxxzMax600535 . 1.321xxxts60000400250280321xxx0,321xxx汽車(chē)廠生產(chǎn)計(jì)劃汽車(chē)廠生產(chǎn)計(jì)劃 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材鋼材 1.5 3 5 600時(shí)間時(shí)間 280 250 400 60000利潤(rùn)利潤(rùn) 2 3 4 線性線性規(guī)劃

29、規(guī)劃模型模型(LP)模型建立模型建立3） 模型中增加條件：模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解。均為整數(shù)，重新求解。 OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.731183 3) 0.000000 0.003226結(jié)果為小數(shù)，結(jié)果為小數(shù)，怎么辦？怎么辦？1）舍去小數(shù)：

30、?。┥崛バ?shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值，算出目標(biāo)函數(shù)值z(mì)=629，與，與LP最優(yōu)值最優(yōu)值632.2581相差不大。相差不大。2）試探：如取）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)等，計(jì)算函數(shù)值值z(mì)，通過(guò)比較可能得到更優(yōu)的解。，通過(guò)比較可能得到更優(yōu)的解。 但必須檢驗(yàn)它們是否滿(mǎn)足約束條件。為什么？但必須檢驗(yàn)它們是否滿(mǎn)足約束條件。為什么？模模型型求求解解IP可用可用LINDO直接求解直接求解整數(shù)規(guī)劃整數(shù)規(guī)劃( (Integer Programming, ,簡(jiǎn)記簡(jiǎn)記IP) )“gin 3”表示表示“前前3個(gè)變量個(gè)變量為整數(shù)為整數(shù)”，等價(jià)于：，等價(jià)于：

31、gin x1gin x2gin x3 IP 的最優(yōu)解的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值，最優(yōu)值z(mì)=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VALUE 1) 632.0000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000 321432xxxzMax600535 . 1.321xxxts6000040

32、0250280321xxx為非負(fù)整數(shù)321,xxxIP 結(jié)果輸出結(jié)果輸出模型求解模型求解其中其中3個(gè)個(gè)子模型應(yīng)子模型應(yīng)去掉，然后去掉，然后逐一求解，比較目標(biāo)函數(shù)值，逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：再加上整數(shù)約束，得最優(yōu)解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0,321xxx方法方法1：分解為：分解為8個(gè)個(gè)LP子模型子模型 汽車(chē)廠生產(chǎn)計(jì)劃汽車(chē)廠生產(chǎn)計(jì)劃 若生產(chǎn)某類(lèi)汽車(chē)，則至少生產(chǎn)若生產(chǎn)某類(lèi)汽車(chē)，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)

33、劃。輛，求生產(chǎn)計(jì)劃。321432xxxzMax600535 . 1.321xxxts60000400250280321xxxx1, ,x2, x3=0 或或 80 x1=80，x2= 150，x3=0，最優(yōu)值，最優(yōu)值z(mì)=610LINDO中對(duì)中對(duì)0-1變量的限定：變量的限定：int y1int y2int y3 方法方法2：引入引入0-1變量，化為整數(shù)規(guī)劃變量，化為整數(shù)規(guī)劃 M為大的正數(shù)，為大的正數(shù)，可取可取1000 OBJECTIVE FUNCTION VALUE 1) 610.0000VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2

34、150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000 若生產(chǎn)某類(lèi)汽車(chē)，則至少生產(chǎn)若生產(chǎn)某類(lèi)汽車(chē)，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃。輛，求生產(chǎn)計(jì)劃。x1=0 或 80 x2=0 或 80 x3=0 或 801 , 0,80,11111yyxMyx1 , 0,80,22222yyxMyx1 , 0,80,33333yyxMyx最優(yōu)解同前最優(yōu)解同前 案例5：鐵路平板車(chē)裝貨問(wèn)題 有有七七種規(guī)格的包裝箱要裝到種規(guī)格的包裝箱要裝到兩輛兩輛鐵路平板車(chē)上

35、去。包裝箱的鐵路平板車(chē)上去。包裝箱的寬和高寬和高是一樣的，但是一樣的，但厚度厚度(t，以厘米計(jì)，以厘米計(jì))及重量及重量(w，以公斤計(jì)，以公斤計(jì))是是不同的。下表給出了每種包裝箱的厚度、重量以及數(shù)量。下圖不同的。下表給出了每種包裝箱的厚度、重量以及數(shù)量。下圖中每輛平板車(chē)有中每輛平板車(chē)有10.2米長(zhǎng)的地方可用來(lái)裝包裝箱（象面包片那米長(zhǎng)的地方可用來(lái)裝包裝箱（象面包片那樣樣)，載重為，載重為40噸。由于當(dāng)?shù)刎涍\(yùn)的限制，對(duì)噸。由于當(dāng)?shù)刎涍\(yùn)的限制，對(duì)C5,C6,C7類(lèi)的包裝類(lèi)的包裝箱的總數(shù)有一定的限制：這類(lèi)箱子所占的空間箱的總數(shù)有一定的限制：這類(lèi)箱子所占的空間(厚度厚度)不能超過(guò)不能超過(guò)302.7厘米。試

36、把包裝箱裝到平板車(chē)上去使得厘米。試把包裝箱裝到平板車(chē)上去使得浪費(fèi)的空間最小浪費(fèi)的空間最小。問(wèn)問(wèn)題題描描述述七種規(guī)格的包裝箱參數(shù)p 所有包裝箱的總重量為89噸，大于兩輛平板車(chē)的總載重量80，所以只能選擇性的裝載貨物. p 浪費(fèi)空間是指平板車(chē)可裝車(chē)長(zhǎng)度10.2m與每輛車(chē)所有包裝箱厚度總和的差值，可以等效的把浪費(fèi)空間最小轉(zhuǎn)化成兩輛車(chē)裝車(chē)總量最大. p 包裝箱的重量和厚度受到平板車(chē)裝載條件的限制以及貨物總量的限制. 問(wèn)題分析問(wèn)題分析p 貨物是不可拆分的，所以這是一個(gè)典型的整數(shù)線性規(guī)劃問(wèn)題.p 兩輛平板車(chē)之間存在相互的制約關(guān)系，在考慮一輛平板車(chē)時(shí)，必須同時(shí)考慮第二輛平板車(chē). 問(wèn)題分析問(wèn)題分析p 對(duì)題目中

37、“由于當(dāng)?shù)刎涍\(yùn)的限制，對(duì)C5,C6,C7類(lèi)的包裝箱的總數(shù)有一定的限制：這類(lèi)箱子所占的空間(厚度)不能超過(guò)302.7厘米?！笨梢岳斫獬擅枯v車(chē)這三類(lèi)貨物的裝車(chē)總數(shù)不超過(guò)302.7厘米，也可以是兩輛車(chē)裝載三類(lèi)貨物的總量不超過(guò)302.7厘米. 模型假設(shè)模型假設(shè)1.各個(gè)貨物之間排列時(shí)靠在一起,包裝箱之間的空隙不計(jì)；2.裝載的過(guò)程中不考慮貨物在車(chē)上的排列次序及各個(gè)貨物的重量分布，排除因局部過(guò)重而造成平板車(chē)失衡的情況；3.鐵路平板車(chē)只能放置一列(排)包裝箱；4.兩輛平板車(chē)裝載C5,C6,C7三類(lèi)包裝箱的總厚度不超過(guò)302.7厘米。 模型建立模型建立決策變量設(shè)xij表示第i輛平板車(chē)裝載Cj包裝箱的件數(shù),i=1

38、,2;j=1,2,7. jjjnwt,分別表示包裝箱的厚度、單個(gè)重量和可供裝車(chē)的件數(shù).參數(shù)變量裝車(chē)總厚度記為T(mén)，則目標(biāo)函數(shù)可表示為： 目標(biāo)函數(shù)2171maxijijjxtT約束條件各種包裝箱可供裝車(chē)數(shù)量的限制：7 , 1,21jnxijij平板車(chē)載重限制：2 , 1,4071ixwjijj厚度限制：2 , 1, 2 .1071ixtjijj模型建立模型建立約束條件兩輛車(chē)對(duì)包裝箱C5,C6,C7的特殊限制：027. 32175ijijjxt所有決策變量都是整數(shù)變量: Zijx模型求解模型求解 該整數(shù)規(guī)劃模型可以利用Lindo和Lingo求解。求解之前注意到20.4-3.027=17.373m，而

39、前4類(lèi)貨物的總長(zhǎng)度恰為17.373m。因此在滿(mǎn)足約束條件的情況下，應(yīng)盡量將C1C4四類(lèi)箱子裝完，以保證兩輛車(chē)?yán)速M(fèi)的空間最小。所以在求解時(shí)將前四類(lèi)箱子的數(shù)量約束改成等式。max 0.487x11+0.52x12+0.613x13+0.72x14+0.487x15+0.52x16+0.64x17 +0.487x21+0.52x22+0.613x23+0.72x24+0.487x25+0.52x26+0.64x27st x11+x21=8 x12+x22=7 x13+x23=9 x14+x24=6 x15+x256 x16+x264 x17+x278 2x11+3x12+x13+0.5x14+4x1

40、5+2x16+x1740 2x21+3x22+x23+0.5x24+4x25+2x26+x2740 0.487x11+0.52x12+0.613x13+0.72x14+0.487x15+0.52x16+0.64x1710.2 0.487x21+0.52x22+0.613x23+0.72x24+0.487x25+0.52x26+0.64x2710.2 0.487x15+0.52x16+0.64x17+0.487x25+0.52x26+0.64x2750;x1+x260;x2+x350;x3+x440;x4+x520;x5+x630;gin(x1);gin(x2);gin(x3);gin(x4);

41、gin(x5);gin(x6);end Global optimal solution found. Objective value: 130.0000 Extended solver steps: 0 Total solver iterations: 7Variable Value Reduced Cost X1 50.00000 1.000000 X2 10.00000 1.000000 X3 40.00000 1.000000 X4 0.000000 1.000000 X5 30.00000 1.000000 X6 0.000000 1.000000計(jì)算結(jié)果：Lingo程序(方式一):

42、Global optimal solution found. Objective value: 130.0000 Extended solver steps: 0 Total solver iterations: 6 Variable Value Reduced CostREQUIRED( 1) 60.00000 0.000000REQUIRED( 2) 50.00000 0.000000REQUIRED( 3) 40.00000 0.000000REQUIRED( 4) 20.00000 0.000000REQUIRED( 5) 30.00000 0.000000REQUIRED( 6) 5

43、0.00000 0.000000DRIVER( 1) 50.00000 1.000000DRIVER( 2) 10.00000 1.000000DRIVER( 3) 40.00000 1.000000DRIVER( 4) 0.000000 1.000000DRIVER( 5) 30.00000 1.000000DRIVER( 6) 0.000000 1.000000求求解解結(jié)結(jié)果果即6個(gè)班次依次需要的司乘人員數(shù)量分別為：x1=50；x2=10；x3=40；x4=0；x5=30；x6=0。共計(jì)至少需要130名司乘人員。 生產(chǎn)中通過(guò)切割、剪裁、沖壓等生產(chǎn)中通過(guò)切割、剪裁、沖壓等手段，將原材料加工成

44、所需大小手段，將原材料加工成所需大小原料下料問(wèn)題原料下料問(wèn)題按照工藝要求，確定下料方案，按照工藝要求，確定下料方案，使所用材料最省，或利潤(rùn)最大使所用材料最省，或利潤(rùn)最大案例7：下料問(wèn)題 I 問(wèn)題問(wèn)題. 如何下料最節(jié)省如何下料最節(jié)省 ? 例例1 鋼管下料鋼管下料 原料鋼管原料鋼管: :每根每根19米米 4米米50根根 6米米20根根 8米米15根根 工地需求工地需求節(jié)省的標(biāo)準(zhǔn)是什么？節(jié)省的標(biāo)準(zhǔn)是什么？問(wèn)問(wèn)題題描描述述 某建筑工地需要一批不同型號(hào)的鋼管，其中4m的50根，6m的20根，8m的15根。現(xiàn)在從鋼管廠進(jìn)貨的原料都是19m的，需要對(duì)這些原料進(jìn)行合理的切割。問(wèn)怎樣切割使得既滿(mǎn)足工地需求，又使

45、浪費(fèi)材料最??？按照客戶(hù)需要在一根原料鋼管上安排切割的一些組合按照客戶(hù)需要在一根原料鋼管上安排切割的一些組合: : 切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料應(yīng)小于客戶(hù)需要鋼管的最小尺寸。的余料應(yīng)小于客戶(hù)需要鋼管的最小尺寸。余料余料3米米 8米米1根根 8米米1根根 鋼管下料鋼管下料 為滿(mǎn)足客戶(hù)需要，按照哪些種合理模式，每種模式為滿(mǎn)足客戶(hù)需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)??？切割多少根原料鋼管，最為節(jié)??？合理切割模式合理切割模式2. 所用原料鋼管總

46、根數(shù)最少所用原料鋼管總根數(shù)最少 模式模式 4米鋼管根數(shù)米鋼管根數(shù)6米鋼管根數(shù)米鋼管根數(shù)8米鋼管根數(shù)米鋼管根數(shù)余料余料(米米)14003231013201341203511116030170023鋼管下料問(wèn)題鋼管下料問(wèn)題兩種兩種標(biāo)準(zhǔn)標(biāo)準(zhǔn)1. 原料鋼管剩余總余量最小原料鋼管剩余總余量最小xi 按第按第i 種模式切割的原料鋼管根數(shù)種模式切割的原料鋼管根數(shù)( (i= =1,2,7) ) 約束約束滿(mǎn)足需求滿(mǎn)足需求 決策決策變量變量 目標(biāo)目標(biāo)1（總余量）（總余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx按模式按模式2切割切割12

47、根根, ,按模式按模式5切割切割15根，余料根，余料27米米 模模式式4米米根數(shù)根數(shù)6米米根數(shù)根數(shù)8米米根數(shù)根數(shù)余余料料14003231013201341203511116030170023需需求求502015最優(yōu)解：最優(yōu)解：x2=12, x5=15, 其余為其余為0；最優(yōu)值：最優(yōu)值：27。整數(shù)約束：整數(shù)約束： xi 為整數(shù)為整數(shù)model:sets:pattern/1.7/:residu,number;type/1.3/:required;link(pattern,type):aa;endsetsdata:residu=3 1 3 3 1 1 3;required=50 20 15;aa=4

48、 0 0 3 1 0 2 0 1 1 2 0 1 1 1 0 3 0 0 0 2; enddata!目標(biāo)函數(shù)(總余量最小)min=sum(pattern:residu*number);!工地需求;for(type(i): sum(pattern(j): aa(j,i)*number(j)required(i);!各變量整數(shù)約束;for(pattern:gin(number);end鋼管切割問(wèn)題的Lingo程序當(dāng)余料沒(méi)有用處時(shí)，當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo)通常以總根數(shù)最少為目標(biāo) 76543212xxxxxxxZMin目標(biāo)目標(biāo)2（總根數(shù)）（總根數(shù)）鋼管下料問(wèn)題鋼管下料問(wèn)題1 1 約束條

49、約束條件不變件不變 最優(yōu)解：最優(yōu)解：x2=15, x5=5, x7=5, 其余為其余為0；最優(yōu)值：最優(yōu)值：25。5023454321xxxxx20326542xxxx152753xxxxi 為整數(shù)按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米 雖余料增加雖余料增加8米，但減少了米，但減少了2根根 與與目標(biāo)目標(biāo)1的結(jié)果的結(jié)果“共切割共切割27根，余料根，余料27米米” 相比相比 板材板材規(guī)格規(guī)格2：長(zhǎng)方形，長(zhǎng)方形，32 28cm，2萬(wàn)張。萬(wàn)張。例例2 易拉罐下料易拉罐下料每周工作每周工作40小時(shí)，每只易拉罐利潤(rùn)小

50、時(shí)，每只易拉罐利潤(rùn)0.10元，原料余料損失元，原料余料損失0.001元元 / cm2（不能裝配的罐身、蓋、底也是余料）（不能裝配的罐身、蓋、底也是余料） 模式模式1：1.5秒秒模式模式2：2秒秒模式模式3：1秒秒上蓋上蓋下底下底罐罐身身罐身高罐身高10cm，上上蓋蓋、下底直、下底直徑均徑均5cm。 板材規(guī)格板材規(guī)格1：正方形，邊長(zhǎng)正方形，邊長(zhǎng)24cm，5萬(wàn)張。萬(wàn)張。如何安排每周生產(chǎn)？如何安排每周生產(chǎn)？ 1015.7模式模式4：3秒秒1015.7 罐身個(gè)數(shù)罐身個(gè)數(shù)底、蓋底、蓋個(gè)數(shù)個(gè)數(shù)余料損失余料損失（cm2）沖壓時(shí)間沖壓時(shí)間（秒）（秒）模式模式1110222.61.5模式模式224183.32模

51、式模式3016261.81模式模式446169.53模式模式1: 正方形正方形邊長(zhǎng)邊長(zhǎng)24cm 問(wèn)題分析問(wèn)題分析計(jì)算各種模式下的余料損失計(jì)算各種模式下的余料損失 上、下底直徑上、下底直徑d=5cm，罐身高罐身高h(yuǎn)=10cm。 模式模式1 余料損失余料損失 242-10 d2/4 - dh=222.6 cm2問(wèn)題分析問(wèn)題分析目標(biāo)目標(biāo): :易拉罐利潤(rùn)扣除原料余料損失后的凈利潤(rùn)最大易拉罐利潤(rùn)扣除原料余料損失后的凈利潤(rùn)最大 約束：約束：每周工作時(shí)間不超過(guò)每周工作時(shí)間不超過(guò)40小時(shí)；小時(shí)； 原料數(shù)量：原料數(shù)量：規(guī)格規(guī)格1（模式（模式1 3）5萬(wàn)張，萬(wàn)張， 規(guī)格規(guī)格2（模式（模式4）2萬(wàn)張；萬(wàn)張； 罐身和

52、底、蓋的配套組裝罐身和底、蓋的配套組裝 。注意注意：不能裝配的罐身、上下底也是余料：不能裝配的罐身、上下底也是余料決策決策變量變量 xi 按照第按照第i 種模式生產(chǎn)的張數(shù)種模式生產(chǎn)的張數(shù)( (i= =1,2,3,4) )；y1 一周生產(chǎn)的易拉罐個(gè)數(shù)；一周生產(chǎn)的易拉罐個(gè)數(shù)；y2 不配套的罐身個(gè)數(shù)；不配套的罐身個(gè)數(shù)；y3 不配套的底、蓋個(gè)數(shù)。不配套的底、蓋個(gè)數(shù)。 模型建立模型建立目標(biāo)目標(biāo) 約束約束條件條件 )6 .191 .1575 .1698 .2613 .1836 .222(001. 01 . 03243211yyxxxxyMax時(shí)間約束時(shí)間約束 144000325 . 14321xxxx原料

53、約束原料約束 ,50000321xxx200004x產(chǎn)量產(chǎn)量余料余料時(shí)間時(shí)間x1222.61.5x2183.32x3261.81x4169.53模型建立模型建立y1 易拉罐個(gè)數(shù)；易拉罐個(gè)數(shù)；y2 不配套的罐身；不配套的罐身；y3 不配套的底、蓋。不配套的底、蓋。每只易拉罐利潤(rùn)每只易拉罐利潤(rùn)0.10元，元，余料損失余料損失0.001元元 / cm2罐身罐身面積面積 dh=157.1 cm2 底蓋底蓋面積面積 d2/4=19.6 cm2(40小時(shí)小時(shí))約束約束條件條件 配套約束配套約束 2/ )516410(,42min43214211xxxxxxxy1421242yxxx/p>

54、10yxxxxy,424211xxxy2/ )516410(43211xxxxyy1 易拉罐個(gè)數(shù)；易拉罐個(gè)數(shù)；y2 不配套的罐身；不配套的罐身；y3 不配套的底、蓋。不配套的底、蓋。罐身罐身底、蓋底、蓋1102401645產(chǎn)量產(chǎn)量x1x2x3x4雖然雖然xi和和y1，y2，y3應(yīng)是整數(shù)，但是因生產(chǎn)量很大，應(yīng)是整數(shù)，但是因生產(chǎn)量很大，可以把它們看成實(shí)數(shù)，從而用線性規(guī)劃模型處理可以把它們看成實(shí)數(shù)，從而用線性規(guī)劃模型處理 。將所有決策變量擴(kuò)大將所有決策變量擴(kuò)大10000倍（倍（xi 萬(wàn)張，萬(wàn)張，yi 萬(wàn)件）萬(wàn)件） LINDO發(fā)出警告信息：發(fā)出警告信息：“數(shù)據(jù)之間的數(shù)量級(jí)差別太大，數(shù)據(jù)之間的數(shù)量級(jí)差別

55、太大，建議進(jìn)行預(yù)處理，縮小數(shù)據(jù)之間的差別建議進(jìn)行預(yù)處理，縮小數(shù)據(jù)之間的差別”模式模式2生產(chǎn)生產(chǎn)40125張，張，模式模式3生產(chǎn)生產(chǎn)3750張，張，模式模式4生產(chǎn)生產(chǎn)20000張，張，共產(chǎn)易拉罐共產(chǎn)易拉罐160250個(gè)個(gè)( (罐身和底、蓋無(wú)剩余罐身和底、蓋無(wú)剩余) )，凈利潤(rùn)為凈利潤(rùn)為4298元元 , 5321xxx24x模型求解模型求解 OBJECTIVE FUNCTION VALUE 1) 0.4298337VARIABLE VALUE REDUCED COST Y1 16.025000 0.000000 X1 0.000000 0.000050 X2 4.012500 0.000000 X

56、3 0.375000 0.000000 X4 2.000000 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484 , 4 .14325 . 14321xxxx下料問(wèn)題的建模總結(jié)下料問(wèn)題的建?？偨Y(jié) 確定下料模式確定下料模式 構(gòu)造優(yōu)化模型構(gòu)造優(yōu)化模型 規(guī)格不太多，可枚舉下料模式，建立整數(shù)線性規(guī)劃模型，規(guī)格不太多，可枚舉下料模式，建立整數(shù)線性規(guī)劃模型，否則要構(gòu)造整數(shù)非線性規(guī)劃模型，求解困難，可用否則要構(gòu)造整數(shù)非線性規(guī)劃模型，求解困難，可用縮小縮小可行域可行域的方法進(jìn)行化簡(jiǎn)，但要保證最優(yōu)解的存在。的方法進(jìn)行化簡(jiǎn)，但要保證最優(yōu)解的存在。一維問(wèn)題（如鋼管

57、下料）一維問(wèn)題（如鋼管下料）二維問(wèn)題（如易拉罐下料）二維問(wèn)題（如易拉罐下料）具體問(wèn)題具體分析（比較復(fù)雜具體問(wèn)題具體分析（比較復(fù)雜 ）分派問(wèn)題分派問(wèn)題若干項(xiàng)任務(wù)分給一些候選人來(lái)完成，每人的專(zhuān)長(zhǎng)不同，若干項(xiàng)任務(wù)分給一些候選人來(lái)完成，每人的專(zhuān)長(zhǎng)不同，完成每項(xiàng)任務(wù)取得的效益或需要的資源就不同，如何分完成每項(xiàng)任務(wù)取得的效益或需要的資源就不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少。派任務(wù)使獲得的總效益最大，或付出的總資源最少。若干種策略供選擇，不同的策略得到的收益或付出的若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個(gè)策略之間有成本不同，各個(gè)策略之間有相互制約關(guān)系相互制約關(guān)系，如

58、何在滿(mǎn)，如何在滿(mǎn)足一定條件下作出決擇，使得收益最大或成本最小。足一定條件下作出決擇，使得收益最大或成本最小。案例8：接力隊(duì)選拔和選課策略0-1規(guī)劃模型規(guī)劃模型 丁的蛙泳成績(jī)退步到丁的蛙泳成績(jī)退步到115”2；戊的自由泳成績(jī)進(jìn)；戊的自由泳成績(jī)進(jìn)步到步到57”5, 組成接力隊(duì)的方案是否應(yīng)該調(diào)整組成接力隊(duì)的方案是否應(yīng)該調(diào)整？如何選拔隊(duì)員組成如何選拔隊(duì)員組成4 4 100100米混合泳接力隊(duì)米混合泳接力隊(duì)? ?例例1 混合泳接力隊(duì)的選拔混合泳接力隊(duì)的選拔 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106

59、”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候選人的名候選人的百米成績(jī)百米成績(jī)窮舉法窮舉法：組成接力隊(duì)的方案共有組成接力隊(duì)的方案共有5!=120種種。目標(biāo)目標(biāo)函數(shù)函數(shù)若選擇隊(duì)員若選擇隊(duì)員i參加泳姿參加泳姿j 的比賽，記的比賽，記xij=1, , 否則記否則記xij=0 0-1規(guī)劃模型規(guī)劃模型 cij( (秒秒) )隊(duì)員隊(duì)員i 第第j 種泳姿的百米成績(jī)種泳姿的百米成績(jī)約束約束條件條件每人每人最多最多入選泳姿之一入選泳姿之一 ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.

60、484.669.683.8j=458.65359.457.262.44151jiijijxcZMin每種泳姿每種泳姿有且只有有且只有1 1人人 5, 1, 141ixjij4, 1, 151jxiij模型求解模型求解 最優(yōu)解：最優(yōu)解：x14 = x21 = x32 = x43 = 1, 其它變量為其它變量為0;成績(jī)?yōu)槌煽?jī)?yōu)?53.2( (秒秒) )=413”2 MIN 66.8x11+75.6x12+87x13+58.6x14 + +67.4x51+71 x52+83.8x53+62.4x54SUBJECT TO x11+x12+x13+x14 =1 x41+x42+x43+x44 =1 x1