數(shù)學(xué)建模中的優(yōu)化模型

簡(jiǎn)要提綱1.優(yōu)化模型簡(jiǎn)介2.簡(jiǎn)單的優(yōu)化模型3.數(shù)學(xué)規(guī)劃模型4.圖論，動(dòng)態(tài)規(guī)劃(選講)5.建模與求解實(shí)例1.優(yōu)化模型簡(jiǎn)介優(yōu)化問(wèn)題的一般形式無(wú)約束優(yōu)化:最優(yōu)解的分類和條件約束優(yōu)化的簡(jiǎn)單分類優(yōu)化建模如何創(chuàng)新？?方法1：大膽創(chuàng)新，別出心裁----采用有特色的目標(biāo)函數(shù)、約束條件等----你用非線性規(guī)劃，我用線性規(guī)劃----你用整數(shù)/離散規(guī)劃，我用連續(xù)規(guī)劃/網(wǎng)絡(luò)優(yōu)化----……?方法2：細(xì)致入微，滴水不漏----對(duì)目標(biāo)函數(shù)、約束條件處理特別細(xì)致----有算法設(shè)計(jì)和分析，不僅僅是簡(jiǎn)單套用軟件----敏感性分析詳細(xì)/全面----……建模時(shí)需要注意的幾個(gè)基本問(wèn)題1、盡量使用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個(gè)數(shù)如：盡量少使用絕對(duì)值、符號(hào)函數(shù)、多個(gè)變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個(gè)數(shù)（如x/y<5改為x<5y）4、合理設(shè)定變量上下界，盡可能給出變量初始值5、模型中使用的參數(shù)數(shù)量級(jí)要適當(dāng)(如小于103)常用優(yōu)化軟件1.LINGO軟件2.MATLAB優(yōu)化工具箱3.EXCEL軟件的優(yōu)化功能4.SAS(統(tǒng)計(jì)分析)軟件的優(yōu)化功能5.其他2.簡(jiǎn)單的優(yōu)化模型——生豬的出售時(shí)機(jī)飼養(yǎng)場(chǎng)每天投入4元資金，用于飼料、人力、設(shè)備，估計(jì)可使80千克重的生豬體重增加2公斤。問(wèn)題市場(chǎng)價(jià)格目前為每千克8元，但是預(yù)測(cè)每天會(huì)降低0.1元，問(wèn)生豬應(yīng)何時(shí)出售。如果估計(jì)和預(yù)測(cè)有誤差，對(duì)結(jié)果有何影響。分析投入資金使生豬體重隨時(shí)間增加，出售單價(jià)隨時(shí)間減少，故存在最佳出售時(shí)機(jī)，使利潤(rùn)最大求t使Q(t)最大10天后出售，可多得利潤(rùn)20元建模及求解生豬體重w=80+rt出售價(jià)格p=8-gt銷售收入R=pw資金投入C=4t利潤(rùn)Q=R-C=pw-C估計(jì)r=2，若當(dāng)前出售，利潤(rùn)為80×8=640（元）t天出售=10Q(10)=660>640g=0.1敏感性分析研究r,g變化時(shí)對(duì)模型結(jié)果的影響估計(jì)r=2，g=0.1

設(shè)g=0.1不變t對(duì)r的（相對(duì)）敏感度生豬每天體重增加量r增加1%，出售時(shí)間推遲3%。rt敏感性分析估計(jì)r=2，g=0.1研究r,g變化時(shí)對(duì)模型結(jié)果的影響

設(shè)r=2不變t對(duì)g的（相對(duì)）敏感度生豬價(jià)格每天的降低量g增加1%，出售時(shí)間提前3%。gt強(qiáng)健性分析保留生豬直到利潤(rùn)的增值等于每天的費(fèi)用時(shí)出售由S(t,r)=3建議過(guò)一周后(t=7)重新估計(jì),再作計(jì)算。研究r,g不是常數(shù)時(shí)對(duì)模型結(jié)果的影響w=80+rtw=w(t)p=8-gtp=p(t)若(10%),則（30%）每天利潤(rùn)的增值每天投入的資金3.

數(shù)學(xué)規(guī)劃模型例1汽車廠生產(chǎn)計(jì)劃例2加工奶制品的生產(chǎn)計(jì)劃例3運(yùn)輸問(wèn)題

如果生產(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.535600勞動(dòng)時(shí)間（小時(shí)）28025040060000利潤(rùn)（萬(wàn)元）234

制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大.設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3汽車廠生產(chǎn)計(jì)劃模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間28025040060000利潤(rùn)234線性規(guī)劃模型(LP)模型求解

3）模型中增加條件：x1,x2,x3

均為整數(shù)，重新求解.

ObjectiveValue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.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可用LINGO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡(jiǎn)記IP)IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;@gin(x1);@gin(x2);@gin(x3);

Globaloptimalsolutionfound.

Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCost

X164.00000-2.000000

X2168.0000-3.000000

X30.000000-4.000000模型求解

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

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃.x1,x2,,x3=0或80x1=80，x2=150，x3=0，最優(yōu)值z(mì)=610LINGO中對(duì)0-1變量的限定：@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1變量，化為整數(shù)規(guī)劃

M為大的正數(shù),本例可取1000ObjectiveValue:610.0000VariableValueReducedCost

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃.x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;x1*(x1-80)>0;x2*(x2-80)>0;x3*(x3-80)>0;@gin(x1);@gin(x2);@gin(x3);方法3：化為非線性規(guī)劃

非線性規(guī)劃（Non-LinearProgramming，簡(jiǎn)記NLP）

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃.x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前.一般地，整數(shù)規(guī)劃和非線性規(guī)劃的求解比線性規(guī)劃困難得多，特別是問(wèn)題規(guī)模較大或者要求得到全局最優(yōu)解時(shí).

例2加工奶制品的生產(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ì)劃？每天：?jiǎn)栴}1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(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)的常數(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)

LINGOmodel:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2

VariableValueReducedCost

X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤(rùn)3360元。結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000

MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

model:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end三種資源“資源”剩余為零的約束為緊約束（有效約束）原料無(wú)剩余時(shí)間無(wú)剩余加工能力剩余40結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量影子價(jià)格35元可買到1桶牛奶，要買嗎?35<48,應(yīng)該買！

聘用臨時(shí)工人付出的工資最多每小時(shí)幾元?2元！原料增加1單位,利潤(rùn)增長(zhǎng)48時(shí)間增加1單位,利潤(rùn)增長(zhǎng)2加工能力增長(zhǎng)不影響利潤(rùn)Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000

最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍敏感性分析

(“LINGO|Ranges”)

x1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)

A1獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃?x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)結(jié)果解釋

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000影子價(jià)格有意義時(shí)約束右端的允許變化范圍原料最多增加10時(shí)間最多增加5335元可買到1桶牛奶,每天最多買多少?最多買10桶!(目標(biāo)函數(shù)不變)充分條件!

生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大。例3運(yùn)輸問(wèn)題其他費(fèi)用:450元/千噸

應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？

若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費(fèi)例3運(yùn)輸問(wèn)題---自來(lái)水輸送收入：900元/千噸

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40水庫(kù)供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)（以天計(jì)）總供水量：160確定送水方案使利潤(rùn)最大問(wèn)題分析A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40<總需求量：120+180=300總收入900160=144,000(元)收入：900元/千噸

其他費(fèi)用:450元/千噸

支出引水管理費(fèi)其他支出450160=72,000(元)使引水管理費(fèi)最小供應(yīng)限制約束條件需求限制

線性規(guī)劃模型(LP)目標(biāo)函數(shù)

水庫(kù)i向j區(qū)的日供水量為xij（x34=0）決策變量

模型建立確定3個(gè)水庫(kù)向4個(gè)小區(qū)的供水量模型求解

部分結(jié)果：ObjectiveValue:24400.00VariableValueReducedCostX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000

X22

50.0000000.000000X230.00000020.000000X24

10.0000000.000000X31

40.0000000.000000X320.00000010.000000X33

10.0000000.000000利潤(rùn)=總收入-其它費(fèi)用-引水管理費(fèi)=144000-