數(shù)學(xué)規(guī)劃模型課件

1、第四章第四章 數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 4.1 奶制品的生產(chǎn)與銷售奶制品的生產(chǎn)與銷售4.2 自來水輸送與貨機(jī)裝運(yùn)自來水輸送與貨機(jī)裝運(yùn)4.3 汽車生產(chǎn)與原油采購汽車生產(chǎn)與原油采購4.4 接力隊(duì)選拔和選課策略接力隊(duì)選拔和選課策略4.5 飲料廠的生產(chǎn)與檢修飲料廠的生產(chǎn)與檢修4.6 鋼管和易拉罐下料鋼管和易拉罐下料y數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 實(shí)際問題中實(shí)際問題中的優(yōu)化模型的優(yōu)化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決策變量決策變量f(x)目標(biāo)函數(shù)目標(biāo)函數(shù)gi(x) 0約束條件約束條件多元函數(shù)多元函數(shù)條件極值條件極值 決策變量個數(shù)決策變量個數(shù)n

2、和和約束條件個數(shù)約束條件個數(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é)果的分析企業(yè)生產(chǎn)計(jì)劃企業(yè)生產(chǎn)計(jì)劃4.1 奶制品的生產(chǎn)與銷售奶制品的生產(chǎn)與銷售 空間層次空間層次工廠級：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等工廠級：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；條件，以最大利潤為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；車間級：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)車間級：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)

3、劃。用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃。時間層次時間層次若短時間內(nèi)外部需求和內(nèi)部資源等不隨時間變化，可若短時間內(nèi)外部需求和內(nèi)部資源等不隨時間變化，可制訂制訂單階段生產(chǎn)計(jì)劃單階段生產(chǎn)計(jì)劃，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃。，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃。本節(jié)課題本節(jié)課題例例1 加工奶制品的生產(chǎn)計(jì)劃加工奶制品的生產(chǎn)計(jì)劃1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時間時間480小時小時 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶桶牛

4、奶，買嗎？若買，每天最多買多少桶? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：每天：1桶牛奶 3公斤A1 12小時 8小時 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勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax每天獲利每天獲利

5、約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時間時間480小時小時 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型求解模型求解 圖解法圖解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl64647264721221zxxxxzMax即目標(biāo)目標(biāo)函數(shù)函數(shù) Z=0Z=2400Z=3600斜率為斜率為-72/64等值線等值線在在B(20,30)點(diǎn)得到最優(yōu)解點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是

6、線性函數(shù)目標(biāo)函數(shù)和約束條件是線性函數(shù) 可行域?yàn)橹本€段圍成的凸多邊形可行域?yàn)橹本€段圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊最優(yōu)解一定在凸多邊形的某個頂點(diǎn)取得。形的某個頂點(diǎn)取得。 模型求解模型求解 軟件實(shí)現(xiàn)軟件實(shí)現(xiàn) LINGO 9.0model:max=72*x1+64*x2;x1+x250; 12*x1+8*x2480;3*x1100; end Global optimal solution found at iteration: 2 Objective value: 3360.000Variable Value Reduced Cost X1 20.00

7、000 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.000000DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤，利潤3360元。元。 結(jié)果解釋結(jié)果解釋 Objective value: 3360.000Total solver iterations: 2Variable Value Redu

8、ced 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原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40model:max=72*x1+64*x2;x1+x250; 12*x1+8*x2480;3*x1100; end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約

9、束） 結(jié)果解釋結(jié)果解釋 Objective value: 3360.000 Total solver iterations: 2Variable 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單位時單位時“效益效益”的增的增量量 原料增加原料增加1單位單位, 利潤

10、增長利潤增長48 時間增加時間增加1單位單位, 利潤增長利潤增長2 加工能力增長不影響利潤加工能力增長不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 48, 應(yīng)該買！應(yīng)該買！ 聘用臨時工人付出的工資最多每小時幾元？聘用臨時工人付出的工資最多每小時幾元？ 2元！元！RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.

11、000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最優(yōu)解不變最優(yōu)解不變時目標(biāo)函時目標(biāo)函數(shù)系數(shù)允許變化范圍數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系數(shù)范圍系數(shù)范圍(64,96)

12、x2系數(shù)范圍系數(shù)范圍(48,72) A1獲利增加到獲利增加到 30元元/千克，應(yīng)否改變生產(chǎn)計(jì)劃千克，應(yīng)否改變生產(chǎn)計(jì)劃 x1系數(shù)由系數(shù)由24 3=72增加增加為為30 3=90，在在允許范圍內(nèi)允許范圍內(nèi) 不變！不變！(約束條件不變約束條件不變)結(jié)果解釋結(jié)果解釋 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.

13、000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子價格有意義時約束右端的允許變化范圍影子價格有意義時約束右端的允許變化范圍 原料最多增加原料最多增加10 時間最多增加時間最多增加53 35元可買到元可買到1桶牛奶，每天最多買多少？桶牛奶，每天最多買多少？最多買最多買10

14、桶桶!(目標(biāo)函數(shù)不變目標(biāo)函數(shù)不變)4.2 自來水輸送與貨機(jī)裝運(yùn)自來水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤最大；怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤最大；運(yùn)輸問題運(yùn)輸問題各種類型的貨物裝箱，由于受體積、重量等限制，各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。其他費(fèi)用其他費(fèi)用: :450元元/千噸千噸 應(yīng)如何分配水庫供水量，公司才能獲利最多？應(yīng)如何分配水庫供水量，公司才能獲利最多？ 若水庫供水量都提高一倍，公司利潤可增

15、加到多少？若水庫供水量都提高一倍，公司利潤可增加到多少？ 元元/千噸千噸甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理費(fèi)引水管理費(fèi)例例1 自來水輸送自來水輸送收入：收入：900元元/千噸千噸 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：?。?0；40水庫供水量水庫供水量(千噸千噸)小區(qū)基本用水量小區(qū)基本用水量(千噸千噸)小區(qū)額外用水量小區(qū)額外用水量(千噸千噸)（以天計(jì)）（以天計(jì)）總供水量：總供水量：160確定送水方案確定送水方案使利潤最大使利潤最大問題問題分析分析A：50B：60C：50甲：甲：3

16、0；50乙：乙：70；70丙：丙：10；20?。憾。?0；40 總需求量總需求量(300)每個水庫最大供水量都提高一倍每個水庫最大供水量都提高一倍利潤利潤 = 收入收入(900) 其它費(fèi)用其它費(fèi)用( (450) 引水管理費(fèi)引水管理費(fèi)利潤利潤(元元/千噸千噸)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxZMax供應(yīng)供應(yīng)限制限制B, C 類似處理類似處理50:A14131211xxxx10014131211xxxx問題討

17、論問題討論 確定送水方案確定送水方案使利潤最大使利潤最大需求約束可以不變需求約束可以不變求解求解 OBJECTIVE FUNCTION VALUE 1) 88700.00 VARIABLE VALUE 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 X

18、31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 這類問題一般稱為這類問題一般稱為“運(yùn)輸問題運(yùn)輸問題”(Transportation Problem)總利潤總利潤 88700（元）（元） A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030如何如何裝運(yùn)，裝運(yùn)，使本次飛行使本次飛行獲利最大？獲利最大？ 三個貨艙三個貨艙最大最大載載重重( (噸噸),),最大容積最大容積( (米米3 3) ) 例例2 貨機(jī)裝運(yùn)貨機(jī)裝運(yùn) 重量（噸）重量

19、（噸）空間空間( 米米3/噸）噸）利潤（元利潤（元/噸）噸）貨物貨物1184803100貨物貨物2156503800貨物貨物3235803500貨物貨物4123902850三個貨艙中實(shí)際載重必須與其最大三個貨艙中實(shí)際載重必須與其最大載載重成比例重成比例 前倉：前倉：10；6800中倉：中倉：16；8700后倉：后倉：8；5300飛機(jī)平衡飛機(jī)平衡決策決策變量變量 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量( (噸）噸）i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉分別代表前、中、后倉)模型假設(shè)模型假設(shè) 每種貨物可以分割到任意小；每種貨物可以分割到任意??；貨

20、機(jī)裝運(yùn)貨機(jī)裝運(yùn)每種貨物可以在一個或多個貨艙中任意分布；每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 模型建立模型建立 貨艙貨艙容積容積 目標(biāo)目標(biāo)函數(shù)函數(shù)( (利潤利潤)約束約束條件條件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312111xxxx870039058065048042322212xxxx530039058065048043332313xxxx貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型建立模型建立 貨艙貨艙重量重量 1

21、041312111xxxx1642322212xxxx843332313xxxx10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量約束約束條件條件平衡平衡要求要求 81610433323134232221241312111xxxxxxxxxxxx貨物貨物供應(yīng)供應(yīng) 18131211xxx15232221xxx23333231xxx12434241xxx貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型建立模型建立 10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量 OBJECTIVE FUNCTION VA

22、LUE 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.000000 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

23、 0.000000 650.000000 貨物貨物2：前倉：前倉10, ,后倉后倉5； 貨物貨物3: : 中倉中倉13, 后倉后倉3；貨物貨物4: : 中倉中倉3。貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型求解模型求解 最大利潤約最大利潤約121516元元貨物貨物供應(yīng)點(diǎn)供應(yīng)點(diǎn)貨艙貨艙需求點(diǎn)需求點(diǎn)平衡要求平衡要求運(yùn)輸運(yùn)輸問題問題運(yùn)輸問題的擴(kuò)展運(yùn)輸問題的擴(kuò)展練習(xí)題（一） 某銀行經(jīng)理計(jì)劃用一筆資金進(jìn)行有價證券的投資，可供購進(jìn)的某銀行經(jīng)理計(jì)劃用一筆資金進(jìn)行有價證券的投資，可供購進(jìn)的證券以及信用等級、到期年限、收益如下表所示。按照規(guī)定，證券以及信用等級、到期年限、收益如下表所示。按照規(guī)定，市政證券的收益可以免稅，其他證券的收

24、益需按市政證券的收益可以免稅，其他證券的收益需按50%的稅率的稅率納稅。此外還有以下限制：納稅。此外還有以下限制：（1）政府及代辦機(jī)構(gòu)的證券總共至少要夠進(jìn)）政府及代辦機(jī)構(gòu)的證券總共至少要夠進(jìn)400萬元；萬元；（2）所購證券的平均信用等級不超過）所購證券的平均信用等級不超過1.4（信用等級數(shù)字越小，（信用等級數(shù)字越小，信用程度越高）；信用程度越高）；（3）所購證券的平均年限不超過）所購證券的平均年限不超過5年；年；問題：問題：(1)若該經(jīng)理擁有若該經(jīng)理擁有1000萬元資金，應(yīng)如何投資？萬元資金，應(yīng)如何投資？(2)如果能夠以如果能夠以2.75%的利率借到不超過的利率借到不超過100萬元資金，該經(jīng)理

25、應(yīng)萬元資金，該經(jīng)理應(yīng)如何操作？如何操作？(3)在在1000萬元資金情況下，若證券萬元資金情況下，若證券A的稅前收益增加為的稅前收益增加為4.5%，投資應(yīng)否改變？若證券投資應(yīng)否改變？若證券C的稅前收益減少為的稅前收益減少為4.8%，投資應(yīng)否，投資應(yīng)否改變？改變？證券以及信用等級、到期年限、收益表 證卷名稱 證卷種類 信用等級 到期年限稅前收益A市政294.3B代辦機(jī)構(gòu)2155.4C政府145.0D政府134.4E市政524.5 如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)8080輛，輛， 那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？例例1 汽車廠生產(chǎn)計(jì)劃汽

26、車廠生產(chǎn)計(jì)劃 汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量。材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量。 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材（噸）鋼材（噸） 1.5 3 5 600勞動時間（小時）勞動時間（小時） 280 250 400 60000利潤（萬元）利潤（萬元） 2 3 4 制訂月生產(chǎn)計(jì)劃，使工廠的利潤最大。制訂月生產(chǎn)計(jì)劃，使工廠的利潤最大。4.3 汽車生產(chǎn)與原油采購汽車生產(chǎn)與原油采購設(shè)每月生產(chǎn)小、中、大型設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為汽車的數(shù)量分別為x1, x2, x332

27、1432xxxzMax600535 . 1.321xxxts60000400250280321xxx0,321xxx汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 模型建立模型建立 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材鋼材 1.5 3 5 600時間時間 280 250 400 60000利潤利潤 2 3 4 線性線性規(guī)劃規(guī)劃模型模型(LP)模型模型求解求解 3） 模型中增加條件：模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解。均為整數(shù)，重新求解。 OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE VALUE REDUCED COST X1 64.51

28、6129 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ù)：?。┥崛バ?shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值，算出目標(biāo)函數(shù)值z=629，與，與LP最優(yōu)值最優(yōu)值632.2581相差不大。相差不大。2）試探：如?。┰囂剑喝缛1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)等，計(jì)算函數(shù)值值z，通過比較可能得到更優(yōu)的解。，通過

29、比較可能得到更優(yōu)的解。 但必須檢驗(yàn)它們是否滿足約束條件。為什么？但必須檢驗(yàn)它們是否滿足約束條件。為什么？IP可用可用LINDO直接求解直接求解整數(shù)規(guī)劃整數(shù)規(guī)劃( (Integer Programming, ,簡記簡記IP) )“gin 3”表示表示“前前3個變量個變量為整數(shù)為整數(shù)”，等價于：，等價于：gin x1gin x2gin x3 IP 的最優(yōu)解的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值，最優(yōu)值z=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VA

30、LUE 1) 632.0000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000 321432xxxzMax600535 . 1.321xxxts60000400250280321xxx為非負(fù)整數(shù)321,xxx模型求解模型求解 IP 結(jié)果輸出結(jié)果輸出其中其中3個個子模型應(yīng)子模型應(yīng)去掉，然后去掉，然后逐一求解，比較目標(biāo)函數(shù)值，逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：再加上整數(shù)約束，得最優(yōu)解：80, 0, 0321xxx0,80, 0321xxx

31、80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0,321xxx方法方法1：分解為：分解為8個個LP子模型子模型 汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 若生產(chǎn)某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃。輛，求生產(chǎn)計(jì)劃。321432xxxzMax600535 . 1.321xxxts60000400250280321xxxx1, ,x2, x3=0 或或 80 x1=80，x2= 150，x3=0，最優(yōu)值，最優(yōu)值z=610LINDO中對中對0-1變量的限定：變量的限定：int y1int y

32、2int 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 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)某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃。輛，求生

33、產(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)解同前 NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解雖然可用現(xiàn)成的數(shù)學(xué)軟件求解( (如如LINGO, , MATLAB) )，但是其結(jié)果常依賴于初值的選擇。，但是其結(jié)果常依賴于初值的選擇。 方法方法3：化為非線性規(guī)劃化為非線性規(guī)劃 非線性規(guī)劃（非線性規(guī)劃（Non- Linear Programming，簡記，簡記NLP） 實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出的最

34、優(yōu)解時，才能得到正確的結(jié)果。的最優(yōu)解時，才能得到正確的結(jié)果。 若生產(chǎn)某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃。輛，求生產(chǎn)計(jì)劃。 x1=0 或 80 x2=0 或 80 x3=0 或 800)80(11xx0)80(22xx0)80(33xx應(yīng)如何安排原油的采購和加工應(yīng)如何安排原油的采購和加工 ？ 例例2 原油采購與加工原油采購與加工 市場上可買到不超過市場上可買到不超過1500噸的原油噸的原油A： 購買量不超過購買量不超過500噸時的單價為噸時的單價為10000元元/ /噸；噸； 購買量超過購買量超過500噸但不超過噸但不超過1000噸時，超過噸時，超過500噸的噸

35、的 部分部分8000元元/ /噸；噸； 購買量超過購買量超過1000噸時，超過噸時，超過1000噸的部分噸的部分6000元元/ /噸。噸。 售價售價4800元元/噸噸 售價售價5600元元/噸噸庫存庫存500噸噸 庫存庫存1000噸噸 汽油甲汽油甲(A 50%) 原油原油A 原油原油B 汽油乙汽油乙 (A 60%) 決策決策變量變量 目標(biāo)目標(biāo)函數(shù)函數(shù)問題問題分析分析 利潤：銷售汽油的收入利潤：銷售汽油的收入 - - 購買原油購買原油A的支出的支出 難點(diǎn)：原油難點(diǎn)：原油A的購價與購買量的關(guān)系較復(fù)雜的購價與購買量的關(guān)系較復(fù)雜)()(6 . 5)( 8 . 422122111xcxxxxzMax甲甲

36、(A 50%) A B 乙乙(A 60%) 購買購買xx11x12x21x224.8千元千元/噸噸 5.6千元千元/噸噸原油原油A的購買量的購買量, ,原油原油A, B生產(chǎn)生產(chǎn)汽油汽油甲甲,乙的數(shù)量乙的數(shù)量c(x) 購買原油購買原油A的支出的支出利潤利潤(千元千元)c(x)如何表述？如何表述？原油供應(yīng)原油供應(yīng) 約束約束條件條件xxx500121110002221 xx1500 x500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc x 500噸單價為噸單價為10千千元元/ /噸；噸； 500噸噸 x 1000噸，超過噸，超過500噸的噸的8千千

37、元元/ /噸；噸；1000噸噸 x 1500噸，超過噸，超過1000噸的噸的6千千元元/ /噸。噸。 目標(biāo)目標(biāo)函數(shù)函數(shù)購買購買x A B x11x12x21x22庫存庫存500噸噸 庫存庫存1000噸噸 目標(biāo)函數(shù)中目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃；不是線性函數(shù)，是非線性規(guī)劃； 對于用分段函數(shù)定義的對于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟，一般的非線性規(guī)劃軟件也難以輸入和求解；件也難以輸入和求解； 想辦法將模型化簡，用現(xiàn)成的軟件求解。想辦法將模型化簡，用現(xiàn)成的軟件求解。 汽油含原油汽油含原油A的比例限制的比例限制 5 . 0211111 xxx6 . 0221212 xxx2

38、111xx 221232xx 約束約束條件條件甲甲(A 50%) A B 乙乙(A 60%) x11x12x21x22x1 , x2 , x3 以價格以價格10, 8, 6(千元千元/ /噸噸) )采購采購A的噸數(shù)的噸數(shù)目標(biāo)目標(biāo)函數(shù)函數(shù) 只有當(dāng)以只有當(dāng)以10千元千元/噸的價格購買噸的價格購買x1=500( (噸噸) )時，才能以時，才能以8千元千元/噸的價格購買噸的價格購買x2方法方法1 )6810()( 6 . 5)( 8 . 432122122111xxxxxxxzMax0)500(32xx500,0321xxx非線性規(guī)劃模型非線性規(guī)劃模型，可以用，可以用LINGO求解求解模型求解模型求解

39、x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 500噸噸 x 1000噸，超過噸，超過500噸的噸的8千千元元/ /噸噸增加約束增加約束0)500(21xxx= x1+x2+x3, c(x) = 10 x1+8x2+6x3 方法方法1：LINGO求解求解Model:Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3;x11+x12 x + 500;x21+x22 0; 2*x12 - 3*x22 0;x=x1+x2+x3; (x1 - 500) * x2=0; (x2 - 500) * x3=0

40、; x1 500;x2 500;x3 0;x11 0;x12 0;x21 0;x22 0;x1 0;x2 0;x3 0;end Objective value: 4800.000Variable Value Reduced CostX11 500.0000 0.0000000E+00X21 500.0000 0.0000000E+00X12 0.0000000E+00 0.0000000E+00X22 0.0000000E+00 0.0000000E+00 X1 0.1021405E-13 10.00000 X2 0.0000000E+00 8.000000 X3 0.0000000E+00

41、6.000000 X 0.0000000E+00 0.0000000E+00 LINGO得到的是局部最優(yōu)解，還得到的是局部最優(yōu)解，還能得到更好的解嗎？能得到更好的解嗎？ 用庫存的用庫存的500噸原油噸原油A、500噸原油噸原油B生產(chǎn)汽油甲，不購買新的原油生產(chǎn)汽油甲，不購買新的原油A，利潤為利潤為4,800千千元。元。 y1, y2 , y3=1 以價格以價格10, 8, 6(千元千元/ /噸噸) )采購采購A增增加加約約束束方法方法2 0-1線性規(guī)劃模型線性規(guī)劃模型，可，可用用LINDO求解求解112500500yxy223500500yxy33500yx y1, ,y2, ,y3 =0或或1

42、 OBJECTIVE FUNCTION VALUE 1) 5000.000 VARIABLE VALUE REDUCED COST Y1 1.000000 0.000000 Y2 1.000000 2200.000000 Y3 1.000000 1200.000000 X11 0.000000 0.800000 X21 0.000000 0.800000 X12 1500.000000 0.000000 X22 1000.000000 0.000000 X1 500.000000 0.000000 X2 500.000000 0.000000 X3 0.000000 0.400000 X 10

43、00.000000 0.000000 購買購買1000噸原油噸原油A，與，與庫存的庫存的500噸原油噸原油A和和1000噸原油噸原油B一起，生一起，生產(chǎn)汽油乙，利潤為產(chǎn)汽油乙，利潤為5,000千元千元 。x1 , x2 , x3 以價格以價格10, 8, 6(千元千元/ /噸噸) )采購采購A的噸數(shù)的噸數(shù)y=0 x=0 x0 y=1優(yōu)于方法優(yōu)于方法1的結(jié)果的結(jié)果b1 b2 b3 b4方法方法3 b1 x b2，x= z1b1+z2b2，z1+z2=1，z1, z2 0, c(x)= z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2 x b3，x=

44、 z2b2+z3b3， z2+z3=1，z2, z3 0, c(x)= z2c(b2)+z3c(b3). b3 x b4，x= z3b3+z4b4，z3+z4=1，z3, z4 0, c(x)= z3c(b3)+z4c(b4). 500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc 直接處理處理分段線性函數(shù)直接處理處理分段線性函數(shù)c(x) IP模型，模型，LINDO求求解，得到的結(jié)果與解，得到的結(jié)果與方法方法2相同相同. .處理分段線性函數(shù)，方法處理分段線性函數(shù)，方法3更具一般性更具一般性44332211bzbzbzbzx)()()()()(4

45、4332211bczbczbczbczxcbk x bk+1yk=1, ,否則否則, ,yk=03432321211,yzyyzyyzyz)4 , 3 , 2 , 1(0, 14321kzzzzzk10, 1321321或yyyyyy方法方法3 bk x bk+1 , ,x= zkbk+z k+1 bk+1zk+zk+1 =1，zk, zk+1 0, c(x)= zkc(bk)+zk+1 c(bk+1 ).c(x)x1200090005000050010001500b1 b2 b3 b4對于對于k=1,2,3分（指）派問題分（指）派問題4.4 接力隊(duì)選拔和選課策略接力隊(duì)選拔和選課策略若干項(xiàng)任務(wù)

46、分給一些候選人來完成，每人的專長不同，若干項(xiàng)任務(wù)分給一些候選人來完成，每人的專長不同，完成每項(xiàng)任務(wù)取得的效益或需要的資源就不同，如何分完成每項(xiàng)任務(wù)取得的效益或需要的資源就不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少。派任務(wù)使獲得的總效益最大，或付出的總資源最少。若干種策略供選擇，不同的策略得到的收益或付出的若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個策略之間有相互制約關(guān)系，如何在滿成本不同，各個策略之間有相互制約關(guān)系，如何在滿足一定條件下作出決擇，使得收益最大或成本最小。足一定條件下作出決擇，使得收益最大或成本最小。丁的蛙泳成績退步到丁的蛙泳成績退步到115”2；戊

47、的自由泳成績進(jìn)；戊的自由泳成績進(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”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候選人的名候選人的百米成績百米成績窮舉法窮舉法：組成接力隊(duì)的方案共有組成接力隊(duì)的方案共有5!=120種種。目標(biāo)目標(biāo)函數(shù)函

48、數(shù)若選擇隊(duì)員若選擇隊(duì)員i參加泳姿參加泳姿j 的比賽，記的比賽，記xij=1, , 否則記否則記xij=0 0-1規(guī)劃模型規(guī)劃模型 cij( (秒秒) )隊(duì)員隊(duì)員i 第第j 種泳姿的百米成績種泳姿的百米成績約束約束條件條件每人最多入選泳姿之一每人最多入選泳姿之一 ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.44151jiijijxcZMin每種泳姿有且只有每種泳姿有且只有1 1人人 5, 1, 141ixjij4, 1, 151jxiij模型求解模

49、型求解 最優(yōu)解：最優(yōu)解：x14 = x21 = x32 = x43 = 1, 其它變量為其它變量為0;成績?yōu)槌煽優(yōu)?53.2( (秒秒) )=413”2 model:MIN=66.8*x11+75.6*x12+87*x13+ 83.8*x53+62.4*x54;x11+x12+x13+x14 =1; x41+x42+x43+x44 = 50;x2 + 2*x4 + x5 + 3*x6= 20;x3 + x5+ 2*x7 = 15;gin(x1); gin(x2); gin(x3); gin(x4); gin(x5);gin(x6); gin(x7);end求解可以得到最優(yōu)解如下：求解可以得到最

50、優(yōu)解如下： OBJECTIVE FUNCTION VALUE: 27.00000 VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 最優(yōu)解：最優(yōu)解：x2=12, x5=15, 其余為其余為0；最優(yōu)值：最優(yōu)值：27。按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余料根，余料27

51、米米 當(dāng)余料沒有用處時，當(dāng)余料沒有用處時，通常以總根數(shù)最少為目標(biāo)通常以總根數(shù)最少為目標(biāo) 76543212xxxxxxxZMin目標(biāo)目標(biāo)2（總根數(shù)）（總根數(shù)）鋼管下料問題鋼管下料問題1 1 約束條約束條件不變件不變 最優(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é)

52、果“共切割共切割27根，余料根，余料27米米” 相比相比 鋼管下料問題鋼管下料問題2對大規(guī)模問題，用模型的約束條件界定合理模式對大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：增加一種需求：5米米10根；切割根；切割模式不超過模式不超過3種。種。現(xiàn)有現(xiàn)有4種種需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚舉法確定合理切割模式，過于復(fù)雜。根，用枚舉法確定合理切割模式，過于復(fù)雜。決策變量決策變量 xi 按第按第i 種模式切割的原料鋼管根數(shù)種模式切割的原料鋼管根數(shù)( (i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 種切割模式下，每

53、根原料鋼管種切割模式下，每根原料鋼管生產(chǎn)生產(chǎn)4米、米、5米、米、6米和米和8米長的鋼管的數(shù)量米長的鋼管的數(shù)量滿足需求滿足需求50313212111xrxrxr10323222121xrxrxr20333232131xrxrxrxrxr模式合理：每根模式合理：每根余料不超過余料不超過3米米1986541641312111rrrr1986541642322212rrrr1986541643332313rrrr整數(shù)非線性規(guī)劃模型整數(shù)非線性規(guī)劃模型鋼管下料問題鋼管下料問題2目標(biāo)函數(shù)（目標(biāo)函數(shù)（總根數(shù)）總根數(shù)）321xxxMin約束約束條件條件整數(shù)約束：整數(shù)約束： xi ,r1

54、i, r2i, r3i, r4i ( (i= =1,2,3) )為整數(shù)為整數(shù)增加約束，縮小可行域，便于求解增加約束，縮小可行域，便于求解321xxx原料鋼管總根數(shù)下界：原料鋼管總根數(shù)下界： 2619158206105504特殊生產(chǎn)計(jì)劃：對每根原料鋼管特殊生產(chǎn)計(jì)劃：對每根原料鋼管模式模式1：切割成：切割成4根根4米鋼管，需米鋼管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米鋼管，需米鋼管，需10根；根；模式模式3：切割成：切割成2根根8米鋼管，需米鋼管，需8根。根。原料鋼管總根數(shù)上界：原料鋼管總根數(shù)上界：13+10+8=31 3126321xxx模式排列順序可任定模式排列順

55、序可任定 鋼管下料問題鋼管下料問題2需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料鋼管長每根原料鋼管長19米米將（37）（46）構(gòu)成的模型輸入LINGO如下：model:Title 鋼管下料鋼管下料 - 最小化鋼管根數(shù)的最小化鋼管根數(shù)的LINGO模型模型;min=x1+x2+x3;x1*r11+x2*r12+x3*r13 =50;x1*r21+x2*r22+x3*r23 =10;x1*r31+x2*r32+x3*r33 =20;x1*r41+x2*r42+x3*r43 =15;4*r11+5*r21+6*r31+8*r41 =19;4*r12+5*r2

56、2+6*r32+8*r42 =19;4*r13+5*r23+6*r33+8*r43 =16;4*r12+5*r22+6*r32+8*r42 =16;4*r13+5*r23+6*r33+8*r43 =16;x1+x2+x3 = 26;x1+x2+x3 =x2;x2=x3;gin(x1); gin(x2); gin(x3);gin(r11);gin(r12);gin(r13);gin(r21);gin(r22);gin(r23);gin(r31);gin(r32);gin(r33);gin(r41);gin(r42);gin(r43);end LINGO求解整數(shù)非線性規(guī)劃模型求解整數(shù)非線性規(guī)劃模型

57、Local optimal solution found at iteration: 12211 Objective value: 28.00000Variable Value Reduced CostX1 10.00000 0.000000X2 10.00000 2.000000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.00000

58、0 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000 模式模式1：每根原料鋼管切割成：每根原料鋼管切割成3根根4米和米和1根根6米鋼管，共米鋼管，共10根；根；模式模式2：每根原料鋼管切割成：每根原料鋼管切割成2根根4米、米、1根根5米和米和1根根6米鋼管，米鋼管，共共10根；根；模式模式3：每根原料鋼管切割成：每根原料鋼管切割成2根根8米鋼管，共米鋼管，共8根。根。原料鋼管總根數(shù)為原料鋼管總根數(shù)為28根。根。板材板材規(guī)格規(guī)