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

1、第四章 數(shù)學(xué)規(guī)劃模型 4.1 奶制品的生產(chǎn)與銷售4.2 自來(lái)水輸送與貨機(jī)裝運(yùn)4.3 汽車生產(chǎn)與原油采購(gòu)4.5 飲料廠的生產(chǎn)與檢修4.6 鋼管和易拉罐下料y數(shù)學(xué)規(guī)劃模型 實(shí)際問(wèn)題中的優(yōu)化模型x決策變量f(x)目標(biāo)函數(shù)gi(x)0約束條件多元函數(shù)條件極值 決策變量個(gè)數(shù)n和約束條件個(gè)數(shù)m較大 最優(yōu)解在可行域的邊界上取得 數(shù)學(xué)規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃重點(diǎn)在模型的建立和結(jié)果的分析企業(yè)生產(chǎn)計(jì)劃4.1 奶制品的生產(chǎn)與銷售 空間層次工廠級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤(rùn)為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；車間級(jí)：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃。時(shí)

2、間層次若短時(shí)間內(nèi)外部需求和內(nèi)部資源等不隨時(shí)間變化，可制訂單階段生產(chǎn)計(jì)劃，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃。本節(jié)課題例1 加工奶制品的生產(chǎn)計(jì)劃1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶 時(shí)間480小時(shí) 至多加工100公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到1桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)A2 獲利 24

3、3x1 獲利 164 x2 原料供應(yīng) 勞動(dòng)時(shí)間 加工能力 決策變量 目標(biāo)函數(shù) 每天獲利約束條件非負(fù)約束 線性規(guī)劃模型(LP)時(shí)間480小時(shí) 至多加工100公斤A1 50桶牛奶 每天模型分析與假設(shè) 比例性 可加性 連續(xù)性 xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比 xi對(duì)約束條件的“貢獻(xiàn)”與xi取值成正比 xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無(wú)關(guān) xi對(duì)約束條件的“貢獻(xiàn)”與xj取值無(wú)關(guān) xi取值連續(xù) A1,A2每公斤的獲利是與各自產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與各自產(chǎn)量無(wú)關(guān)的常數(shù)A1,A2每公斤的獲利是與相互產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與相互產(chǎn)量無(wú)關(guān)的常

4、數(shù)加工A1,A2的牛奶桶數(shù)是實(shí)數(shù) 線性規(guī)劃模型模型求解 圖解法 x1x20ABCDl1l2l3l4l5約束條件目標(biāo)函數(shù) Z=0Z=2400Z=3600z=c (常數(shù)) 等值線c在B(20,30)點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù) 可行域?yàn)橹本€段圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。 模型求解 軟件實(shí)現(xiàn) LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1

5、 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤(rùn)3360元。 結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.0000

6、00 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料無(wú)剩余時(shí)間無(wú)剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三種資源“資源” 剩余為零的約束為緊約束（有效約束） 結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE R

7、EDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量 原料增加1單位, 利潤(rùn)增長(zhǎng)48 時(shí)間增加1單位, 利潤(rùn)增長(zhǎng)2 加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格 35元可買到1桶牛奶，要買嗎？35 48, 應(yīng)該買！ 聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？ 2元！RANGES IN

8、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.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.

9、333332 80.000000 4 100.000000 INFINITY 40.000000最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系數(shù)范圍(64,96) x2系數(shù)范圍(48,72) A1獲利增加到 30元/千克，應(yīng)否改變生產(chǎn)計(jì)劃 x1系數(shù)由24 3=72增加為303=90，在允許范圍內(nèi) 不變！(約束條件不變)結(jié)果解釋 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE C

10、OEF INCREASE DECREASE X1 72.000000 24.000000 8.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影子價(jià)格有意義時(shí)約束右端的允許變化范圍 原料最多增加10 時(shí)間最多增加53 35元可買

11、到1桶牛奶，每天最多買多少？最多買10桶!(目標(biāo)函數(shù)不變)例2 奶制品的生產(chǎn)銷售計(jì)劃 在例1基礎(chǔ)上深加工1桶牛奶 3千克A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 0.8千克B12小時(shí),3元1千克獲利44元/千克 0.75千克B22小時(shí),3元1千克獲利32元/千克 制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大 30元可增加1桶牛奶，3元可增加1小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？50桶牛奶, 480小時(shí) 至多100公斤A1 B1，B2的獲利經(jīng)常有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響？1桶牛奶 3千克 A1 12小時(shí) 8小時(shí) 4千克 A2 或獲利24元/千克 獲利16元/kg

12、 0.8千克 B12小時(shí),3元1千克獲利44元/千克 0.75千克 B22小時(shí),3元1千克獲利32元/千克 出售x1 千克 A1, x2 千克 A2， X3千克 B1, x4千克 B2原料供應(yīng) 勞動(dòng)時(shí)間 加工能力 決策變量 目標(biāo)函數(shù) 利潤(rùn)約束條件非負(fù)約束 x5千克 A1加工B1， x6千克 A2加工B2附加約束 模型求解 軟件實(shí)現(xiàn) LINDO 6.1 OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0

13、.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No OBJECTIVE FUNCTION VALUE 1) 3460.80

14、0 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000

15、NO. ITERATIONS= 2結(jié)果解釋每天銷售168 千克A2和19.2 千克B1， 利潤(rùn)3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，將得到的24千克A1全部加工成B1 除加工能力外均為緊約束結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.5

16、20000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000增加1桶牛奶使利潤(rùn)增長(zhǎng)3.1612=37.92增加1小時(shí)時(shí)間使利潤(rùn)增長(zhǎng)3.26 30元可增加1桶牛奶，3元可增加1小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？投資150元增加5桶牛奶，可賺回189.6元。（大于增加時(shí)間的利潤(rùn)增長(zhǎng)）結(jié)果解釋B1,B2的獲利有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響 RANGES IN

17、WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY

18、 DO RANGE (SENSITIVITY) ANALYSIS? YesB1獲利下降10%，超出X3 系數(shù)允許范圍B2獲利上升10%，超出X4 系數(shù)允許范圍波動(dòng)對(duì)計(jì)劃有影響生產(chǎn)計(jì)劃應(yīng)重新制訂：如將x3的系數(shù)改為39.6計(jì)算，會(huì)發(fā)現(xiàn)結(jié)果有很大變化。 4.2 自來(lái)水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大；運(yùn)輸問(wèn)題各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。其他費(fèi)用:450元/千噸 應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？ 若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？ 元/千噸甲乙丙丁A16013

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

20、制B, C 類似處理問(wèn)題討論 確定送水方案使利潤(rùn)最大需求約束可以不變求解 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 X31 50.000000

21、 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 這類問(wèn)題一般稱為“運(yùn)輸問(wèn)題”(Transportation Problem)總利潤(rùn) 88700（元） A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030如何裝運(yùn)，使本次飛行獲利最大？ 三個(gè)貨艙最大載重(噸),最大容積(米3) 例2 貨機(jī)裝運(yùn)重量（噸）空間( 米3/噸）利潤(rùn)（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850三個(gè)貨艙中實(shí)際載重必須與其最大載重

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

23、 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.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

24、 3.052632 0.000000 X43 0.000000 650.000000 貨物2：前倉(cāng)10,后倉(cāng)5； 貨物3: 中倉(cāng)13, 后倉(cāng)3；貨物4: 中倉(cāng)3。貨機(jī)裝運(yùn)模型求解 最大利潤(rùn)約121516元貨物供應(yīng)點(diǎn)貨艙需求點(diǎn)平衡要求運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題的擴(kuò)展 如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛， 那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？例1 汽車廠生產(chǎn)計(jì)劃 汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量。 小型 中型 大型 現(xiàn)有量鋼材（噸） 1.5 3 5 600勞動(dòng)時(shí)間（小時(shí)） 280 250 400 60000利潤(rùn)（萬(wàn)元） 2 3 4 制訂月生產(chǎn)計(jì)劃，使工

25、廠的利潤(rùn)最大。4.3 汽車生產(chǎn)與原油采購(gòu)設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1, x2, x3汽車廠生產(chǎn)計(jì)劃 模型建立 小型 中型 大型 現(xiàn)有量鋼材 1.5 3 5 600時(shí)間 280 250 400 60000利潤(rùn) 2 3 4 線性規(guī)劃模型(LP)模型求解 3） 模型中增加條件：x1, x2, x3 均為整數(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 S

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

27、x1=64，x2=168，x3=0，最優(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 模型求解 IP 結(jié)果輸出其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個(gè)LP子模型 汽車廠生產(chǎn)計(jì)劃

28、 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1,x2, x3=0 或 80 x1=80，x2= 150，x3=0，最優(yōu)值z(mì)=610LINDO中對(duì)0-1變量的限定：int y1int y2int y3 方法2：引入0-1變量，化為整數(shù)規(guī)劃 M為大的正數(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.00000

29、0 0.000000 Y3 0.000000 0.000000 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1=0 或 80 x2=0 或 80 x3=0 或 80最優(yōu)解同前 NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO, MATLAB)，但是其結(jié)果常依賴于初值的選擇。 方法3：化為非線性規(guī)劃 非線性規(guī)劃（Non- Linear Programming，簡(jiǎn)記NLP） 實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時(shí)，才能得到正確的結(jié)果。 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。 x1=0 或 80 x2=0 或 80 x3=0 或 80應(yīng)如何安排原油的采購(gòu)和加工 ？ 例2 原油

30、采購(gòu)與加工 市場(chǎng)上可買到不超過(guò)1500噸的原油A： 購(gòu)買量不超過(guò)500噸時(shí)的單價(jià)為10000元/噸； 購(gòu)買量超過(guò)500噸但不超過(guò)1000噸時(shí)，超過(guò)500噸的 部分8000元/噸； 購(gòu)買量超過(guò)1000噸時(shí)，超過(guò)1000噸的部分6000元/噸。 售價(jià)4800元/噸 售價(jià)5600元/噸庫(kù)存500噸 庫(kù)存1000噸 汽油甲(A50%) 原油A 原油B 汽油乙 (A60%) 決策變量 目標(biāo)函數(shù)問(wèn)題分析 利潤(rùn)：銷售汽油的收入 - 購(gòu)買原油A的支出 難點(diǎn)：原油A的購(gòu)價(jià)與購(gòu)買量的關(guān)系較復(fù)雜甲(A50%) A B 乙(A60%) 購(gòu)買xx11x12x21x224.8千元/噸 5.6千元/噸原油A的購(gòu)買量,原油A

31、, B生產(chǎn)汽油甲,乙的數(shù)量c(x) 購(gòu)買原油A的支出利潤(rùn)(千元)c(x)如何表述？原油供應(yīng) 約束條件 x 500噸單價(jià)為10千元/噸； 500噸 x 1000噸，超過(guò)500噸的8千元/噸；1000噸 x 1500噸，超過(guò)1000噸的6千元/噸。 目標(biāo)函數(shù)購(gòu)買xA B x11x12x21x22庫(kù)存500噸 庫(kù)存1000噸 目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃； 對(duì)于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解； 想辦法將模型化簡(jiǎn)，用現(xiàn)成的軟件求解。 汽油含原油A的比例限制 約束條件甲(A50%) A B 乙(A60%) x11x12x21x22x1 , x2 , x3

32、以價(jià)格10, 8, 6(千元/噸)采購(gòu)A的噸數(shù)目標(biāo)函數(shù) 只有當(dāng)以10千元/噸的價(jià)格購(gòu)買x1=500(噸)時(shí)，才能以8千元/噸的價(jià)格購(gòu)買x2方法1 非線性規(guī)劃模型，可以用LINGO求解模型求解x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 500噸 x 1000噸，超過(guò)500噸的8千元/噸增加約束x= 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;

33、 2*x12 - 3*x22 0;x=x1+x2+x3; (x1 - 500) * x2=0; (x2 - 500) * x3=0; 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

34、.1021405E-13 10.00000 X2 0.0000000E+00 8.000000 X3 0.0000000E+00 6.000000 X 0.0000000E+00 0.0000000E+00 LINGO得到的是局部最優(yōu)解，還能得到更好的解嗎？ 用庫(kù)存的500噸原油A、500噸原油B生產(chǎn)汽油甲，不購(gòu)買新的原油A，利潤(rùn)為4,800千元。 y1, y2 , y3=1 以價(jià)格10, 8, 6(千元/噸)采購(gòu)A增加約束方法2 0-1線性規(guī)劃模型，可用LINDO求解y1,y2,y3 =0或1 OBJECTIVE FUNCTION VALUE 1) 5000.000 VARIABLE VAL

35、UE 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 1000.000000 0.000000 購(gòu)買1000噸原油A，與庫(kù)存的500噸原油A和1000噸原油B

36、一起，生產(chǎn)汽油乙，利潤(rùn)為5,000千元 。x1 , x2 , x3 以價(jià)格10, 8, 6(千元/噸)采購(gòu)A的噸數(shù)y=0 x=0 x0 y=1優(yōu)于方法1的結(jié)果b1 b2 b3 b4方法3 b1 xb2，x= z1b1+z2b2，z1+z2=1，z1, z20, c(x)= z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2 x b3，x= 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)+z

37、4c(b4). 直接處理處理分段線性函數(shù)c(x) IP模型，LINDO求解，得到的結(jié)果與方法2相同.處理分段線性函數(shù)，方法3更具一般性bkxbk+1yk=1,否則,yk=0方法3 bkxbk+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對(duì)于k=1,2,34.5 飲料廠的生產(chǎn)與檢修單階段生產(chǎn)計(jì)劃多階段生產(chǎn)計(jì)劃 生產(chǎn)批量問(wèn)題 企業(yè)生產(chǎn)計(jì)劃考慮與產(chǎn)量無(wú)關(guān)的固定費(fèi)用給優(yōu)化模型求解帶來(lái)新的困難外部需求和內(nèi)部資源隨時(shí)間變化 安

38、排生產(chǎn)計(jì)劃, 滿足每周的需求, 使4周總費(fèi)用最小。存貯費(fèi):每周每千箱飲料 0.2千元。 例1 飲料廠的生產(chǎn)與檢修計(jì)劃 在4周內(nèi)安排一次設(shè)備檢修，占用當(dāng)周15千箱生產(chǎn)能力，能使檢修后每周增產(chǎn)5千箱，檢修應(yīng)排在哪一周? 周次需求量(千箱)生產(chǎn)能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合計(jì)100135某種飲料4周的需求量、生產(chǎn)能力和成本問(wèn)題分析 除第4周外每周的生產(chǎn)能力超過(guò)每周的需求； 生產(chǎn)成本逐周上升；前幾周應(yīng)多生產(chǎn)一些。 周次需求能力11530225403354542520合計(jì)100135成本5.05.15.45.5 飲料廠在第1周開始時(shí)沒(méi)有庫(kù)

39、存； 從費(fèi)用最小考慮, 第4周末不能有庫(kù)存； 周末有庫(kù)存時(shí)需支出一周的存貯費(fèi)； 每周末的庫(kù)存量等于下周初的庫(kù)存量。 模型假設(shè) 目標(biāo)函數(shù)約束條件產(chǎn)量、庫(kù)存與需求平衡 決策變量 能力限制 非負(fù)限制 模型建立x1 x4：第14周的生產(chǎn)量y1 y3：第13周末庫(kù)存量周次需求能力11530225403354542520成本5.05.15.45.5存貯費(fèi):0.2 (千元/周千箱) 模型求解 4周生產(chǎn)計(jì)劃的總費(fèi)用為528 (千元) 最優(yōu)解： x1 x4：15，40，25，20； y1 y3： 0，15，5 .周次需求能力11530225403354542520成本5.05.15.45.5產(chǎn)量15402520

40、庫(kù)存01550LINDO求解檢修計(jì)劃0-1變量wt ：wt=1 檢修安排在第t周(t=1,2,3,4） 在4周內(nèi)安排一次設(shè)備檢修，占用當(dāng)周15千箱生產(chǎn)能力，能使檢修后每周增產(chǎn)5千箱，檢修應(yīng)排在哪一周? 檢修安排在任一周均可周次需求能力11530225403354542520成本5.05.15.45.5約束條件能力限制 產(chǎn)量、庫(kù)存與需求平衡條件不變 增加約束條件：檢修1次檢修計(jì)劃目標(biāo)函數(shù)不變0-1變量wt ：wt=1 檢修安排在第t周(t=1,2,3,4）LINDO求解總費(fèi)用由528千元降為527千元檢修所導(dǎo)致的生產(chǎn)能力提高的作用, 需要更長(zhǎng)的時(shí)間才能得到充分體現(xiàn)。 最優(yōu)解： w1=1, w2

41、, w3, w4=0; x1 x4：15,45,15,25； y1 y3：0,20,0 .例2 飲料的生產(chǎn)批量問(wèn)題 安排生產(chǎn)計(jì)劃, 滿足每周的需求, 使4周總費(fèi)用最小。存貯費(fèi):每周每千箱飲料 0.2千元。 飲料廠使用同一條生產(chǎn)線輪流生產(chǎn)多種飲料。若某周開工生產(chǎn)某種飲料, 需支出生產(chǎn)準(zhǔn)備費(fèi)8千元。 某種飲料4周的需求量、生產(chǎn)能力和成本周次需求量(千箱)生產(chǎn)能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合計(jì)100135生產(chǎn)批量問(wèn)題的一般提法ct 時(shí)段t 生產(chǎn)費(fèi)用(元/件)；ht 時(shí)段t (末)庫(kù)存費(fèi)(元/件)；st 時(shí)段t 生產(chǎn)準(zhǔn)備費(fèi)(元)；dt 時(shí)

42、段t 市場(chǎng)需求(件)；Mt 時(shí)段t 生產(chǎn)能力(件)。假設(shè)初始庫(kù)存為0制訂生產(chǎn)計(jì)劃, 滿足需求,并使T個(gè)時(shí)段的總費(fèi)用最小。決策變量 xt 時(shí)段t 生產(chǎn)量；yt 時(shí)段t (末)庫(kù)存量；wt =1 時(shí)段t 開工生產(chǎn) (wt =0 不開工)。目標(biāo)約束混合0-1規(guī)劃模型 最優(yōu)解：x1 x4：15，40，45，0；總費(fèi)用：554.0(千元) 生產(chǎn)批量問(wèn)題的一般提法將所給參數(shù)代入模型，用LINDO求解生產(chǎn)中通過(guò)切割、剪裁、沖壓等手段，將原材料加工成所需大小6 鋼管和易拉罐下料原料下料問(wèn)題按照工藝要求，確定下料方案，使所用材料最省，或利潤(rùn)最大問(wèn)題1. 如何下料最節(jié)省 ? 例1 鋼管下料 問(wèn)題2. 客戶增加需求

43、：原料鋼管:每根19米 4米50根 6米20根 8米15根 客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多，會(huì)增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過(guò)3種。如何下料最節(jié)省？5米10根 按照客戶需要在一根原料鋼管上安排切割的一種組合。 切割模式余料1米 4米1根 6米1根 8米1根 余料3米 4米1根 6米1根 6米1根 合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸余料3米 8米1根 8米1根 鋼管下料 為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。亢侠砬懈钅Ｊ?. 所用原料鋼管總根數(shù)最少 模式4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米/p>

44、201341203511116030170023鋼管下料問(wèn)題1 兩種標(biāo)準(zhǔn)1. 原料鋼管剩余總余量最小xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,7) 約束滿足需求 決策變量 目標(biāo)1（總余量）按模式2切割12根,按模式5切割15根，余料27米 模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015最優(yōu)解：x2=12, x5=15, 其余為0；最優(yōu)值：27。整數(shù)約束： xi 為整數(shù)當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo) 目標(biāo)2（總根數(shù)）鋼管下料問(wèn)題1 約束條件不變 最優(yōu)解：x2=15, x5=5, x7=5, 其余為0；最優(yōu)

45、值：25。xi 為整數(shù)按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米 雖余料增加8米，但減少了2根 與目標(biāo)1的結(jié)果“共切割27根，余料27米” 相比 鋼管下料問(wèn)題2對(duì)大規(guī)模問(wèn)題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過(guò)3種。現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過(guò)于復(fù)雜。決策變量 xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,3) r1i, r2i, r3i, r4i 第i 種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長(zhǎng)的鋼管的數(shù)量滿足需求模式合理：每根余料不超過(guò)3米整數(shù)非

46、線性規(guī)劃模型鋼管下料問(wèn)題2目標(biāo)函數(shù)（總根數(shù)）約束條件整數(shù)約束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)為整數(shù)增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界： 特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：13+10+8=31 模式排列順序可任定 鋼管下料問(wèn)題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長(zhǎng)19米LINGO求解整數(shù)非線性規(guī)劃模型Local optimal solution found at iteration: 12211 Objective value: 28.00000Variable V