數(shù)學(xué)建模第03章_數(shù)學(xué)規(guī)劃模型

1、第三章第三章 數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 1 奶制品的生產(chǎn)與銷售奶制品的生產(chǎn)與銷售 2 食譜問題食譜問題 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ù)條件極值條件極值 決策變量個(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)在模型的建

2、立和結(jié)果的分析不能用微分法求解不能用微分法求解。企業(yè)生產(chǎn)計(jì)劃企業(yè)生產(chǎn)計(jì)劃4.1 奶制品的生產(chǎn)與銷售奶制品的生產(chǎn)與銷售 空間層次空間層次工廠級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等工廠級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤(rùn)為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；條件，以最大利潤(rùn)為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；車間級(jí)：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)車間級(jí)：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃。用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃。時(shí)間層次時(shí)間層次若短時(shí)間內(nèi)外部需求和內(nèi)部資源等不隨時(shí)間變化，可若短時(shí)間內(nèi)外部需求和內(nèi)部資源等不隨時(shí)間變化，可制訂制訂單階段

3、生產(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小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否

4、改變生產(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í)間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型分析與

5、假設(shè)模型分析與假設(shè) 比比例例性性 可可加加性性 連續(xù)性連續(xù)性 xi對(duì)目標(biāo)函數(shù)的對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)貢獻(xiàn)”與與xi取值取值成正比成正比 xi對(duì)約束條件的對(duì)約束條件的“貢獻(xiàn)貢獻(xiàn)”與與xi取值取值成正比成正比 xi對(duì)目標(biāo)函數(shù)的對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)貢獻(xiàn)”與與xj取值取值無關(guān)無關(guān) xi對(duì)約束條件的對(duì)約束條件的“貢獻(xiàn)貢獻(xiàn)”與與xj取值取值無關(guān)無關(guān) xi取值連續(xù)取值連續(xù) A1,A2每公斤的獲利是與各每公斤的獲利是與各自產(chǎn)量無關(guān)的常數(shù)自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量和的數(shù)量和時(shí)間是與各自產(chǎn)量無關(guān)的常數(shù)時(shí)間是與各自產(chǎn)量無關(guān)的常數(shù)A1,A2每公斤的獲利是與相每公斤的獲利是與相互產(chǎn)量無關(guān)的常

6、數(shù)互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量和的數(shù)量和時(shí)間是與相互產(chǎn)量無關(guān)的常數(shù)時(shí)間是與相互產(chǎn)量無關(guān)的常數(shù)加工加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)的牛奶桶數(shù)是實(shí)數(shù) 線性規(guī)劃模型線性規(guī)劃模型模型求解模型求解 圖解法圖解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目標(biāo)目標(biāo)函數(shù)函數(shù) Z=0Z=2400Z=3600z=c (常數(shù)常數(shù)) 等值線等值線c在在B(20,30)點(diǎn)得到最優(yōu)解點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)

7、和約束條件是線性函數(shù)目標(biāo)函數(shù)和約束條件是線性函數(shù) 可行域?yàn)橹本€段圍成的凸多邊形可行域?yàn)橹本€段圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。形的某個(gè)頂點(diǎn)取得。 模型求解模型求解 軟件實(shí)現(xià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 20.000000 0.000000 X2 30.000000 0.000000

8、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)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)，利潤(rùn)3360元。元。 結(jié)果解釋結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000

9、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原料無剩余原料無剩余時(shí)間無剩余時(shí)間無剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結(jié)果解釋結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.00

10、0 VARIABLE VALUE REDUCED 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)解下最優(yōu)解下“資源資源”增加增加1單位時(shí)單位時(shí)“效益效益”的增的增量量 原料增加原料增加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)48 時(shí)間增加時(shí)間增加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)2 加工能力增長(zhǎng)不影響利潤(rùn)加工能力增長(zhǎng)不影響利潤(rùn)

11、影子價(jià)格影子價(jià)格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 48, 應(yīng)該買！應(yīng)該買！ 聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？ 2元！元！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.000000 16.000000 RIGHTHAND SIDE RA

12、NGES 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)解不變時(shí)目標(biāo)函最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系數(shù)范圍系數(shù)范圍(64,96) x2系數(shù)范圍系數(shù)范圍(48,72) A1獲利增加到獲利增加到 30元元/千克，應(yīng)否改變生產(chǎn)計(jì)劃千克，應(yīng)否改變生產(chǎn)

13、計(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.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOW

14、ABLE 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í)約束右端的允許變化范圍影子價(jià)格有意義時(shí)約束右端的允許變化范圍 原料最多增加原料最多增加10 時(shí)間最多增加時(shí)間最多增加53 35元可買到元可買到1桶牛奶，每天最多買多少？桶牛奶，每天最多買多少？最多買最多買10桶桶!(目標(biāo)函數(shù)不變目標(biāo)函數(shù)不變)例例2 奶制品的生產(chǎn)銷售計(jì)劃奶制品的生產(chǎn)銷售計(jì)劃 在例在例1基礎(chǔ)上深加工基礎(chǔ)上

15、深加工1桶桶牛奶牛奶 3千克千克A1 12小時(shí)小時(shí) 8小時(shí)小時(shí) 4公斤公斤A2 或或獲利獲利24元元/公斤公斤 獲利獲利16元元/公斤公斤 0.8千克千克B12小時(shí)小時(shí),3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克B22小時(shí)小時(shí),3元元1千克千克獲利獲利32元元/千克千克 制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時(shí)時(shí)間，應(yīng)否投小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資資？現(xiàn)投資150元，可賺回多少？元，可賺回多少？50桶牛奶桶牛奶, 480小時(shí)小時(shí) 至多至多100公斤公斤A1 B1，B2的獲利經(jīng)常有的獲利經(jīng)常有1

16、0%的波動(dòng)，對(duì)計(jì)劃有無影響？的波動(dòng)，對(duì)計(jì)劃有無影響？1桶桶牛奶牛奶 3千克千克 A1 12小時(shí)小時(shí) 8小時(shí)小時(shí) 4千克千克 A2 或或獲利獲利24元元/千克千克 獲利獲利16元元/kg 0.8千克千克 B12小時(shí)小時(shí),3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克 B22小時(shí)小時(shí),3元元1千克千克獲利獲利32元元/千克千克 出售出售x1 千克千克 A1, x2 千克千克 A2， x3千克千克 B1, x4千克千克 B2原料原料供應(yīng)供應(yīng) 勞動(dòng)勞動(dòng)時(shí)間時(shí)間 加工能力加工能力 決策決策變量變量 目標(biāo)目標(biāo)函數(shù)函數(shù) 利潤(rùn)利潤(rùn)約束約束條件條件非負(fù)約束非負(fù)約束 0,61xx x5千克千克 A1

17、加工加工B1， x6千克千克 A2加工加工B26543213332441624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加約束附加約束 5380 x.x64750 x.x 模型求解模型求解 軟件實(shí)現(xiàn)軟件實(shí)現(xiàn) LINDO 6.1 5043) 26251xxxx48022)(2)(4)3656251xxxxxx OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3

18、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 NO. ITERATIONS= 2600334) 26521xxxx44804624) 36521xxxxDO RANGE (SENSITIVITY) A

19、NALYSIS? No 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.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.0000

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

21、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增加增加1桶牛奶使利潤(rùn)增桶牛奶使利潤(rùn)增長(zhǎng)長(zhǎng)3.1612=37.925043)26251xxxx600334) 26521xxxx4增加增加1小時(shí)時(shí)間