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

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

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

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

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

如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計劃應(yīng)作何改變？例1汽車廠生產(chǎn)計劃汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量.

小型中型大型現(xiàn)有量鋼材（噸）1.535600勞動時間（小時）28025040060000利潤（萬元）234

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

小型中型大型現(xiàn)有量鋼材1.535600時間28025040060000利潤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=629，與LP最優(yōu)值632.2581相差不大.2）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數(shù)值z，通過比較可能得到更優(yōu)的解.

但必須檢驗它們是否滿足約束條件.為什么？IP可用LINGO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡記IP)IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z=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個子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個LP子模型汽車廠生產(chǎn)計劃

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃.x1,x2,,x3=0或80x1=80，x2=150，x3=0，最優(yōu)值z=610LINGO中對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)計劃.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，簡記NLP）

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

80x2=0或

80x3=0或

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

例2加工奶制品的生產(chǎn)計劃1桶牛奶

3公斤A1

12小時

8小時

4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時間480小時至多加工100公斤A1

制訂生產(chǎn)計劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?

可聘用臨時工人，付出的工資最多是每小時幾元?A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計劃？每天：問題1桶牛奶3公斤A1

12小時8小時4公斤A2

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

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

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動時間

加工能力

決策變量

目標(biāo)函數(shù)

每天獲利約束條件非負(fù)約束

線性規(guī)劃模型(LP)時間480小時至多加工100公斤A1

50桶牛奶每天基本模型模型分析與假設(shè)

比例性可加性連續(xù)性xi對目標(biāo)函數(shù)的“貢獻”與xi取值成正比xi對約束條件的“貢獻”與xi取值成正比xi對目標(biāo)函數(shù)的“貢獻”與xj取值無關(guān)xi對約束條件的“貢獻”與xj取值無關(guān)xi取值連續(xù)A1,A2每公斤的獲利是與各自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工A1,A2的數(shù)量,時間是與各自產(chǎn)量無關(guān)的常數(shù)A1,A2每公斤的獲利是與相互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工A1,A2的數(shù)量,時間是與相互產(chǎn)量無關(guān)的常數(shù)加工A1,A2的牛奶桶數(shù)是實數(shù)線性規(guī)劃模型模型求解

圖解法

x1x20ABCDl1l2l3l4l5約束條件目標(biāo)函數(shù)

Z=0Z=2400Z=3600z=c(常數(shù))~等值線c在B(20,30)點得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù)可行域為直線段圍成的凸多邊形目標(biāo)函數(shù)的等值線為直線最優(yōu)解一定在凸多邊形的某個頂點取得。模型求解

軟件實現(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，利潤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三種資源“資源”剩余為零的約束為緊約束（有效約束）原料無剩余時間無剩余加工能力剩余40結(jié)果解釋

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

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

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

(“LINGO|Ranges”)

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

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

A1獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計劃?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影子價格有意義時約束右端的允許變化范圍原料最多增加10時間最多增加5335元可買到1桶牛奶,每天最多買多少?最多買10桶!(目標(biāo)函數(shù)不變)充分條件!

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

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

若水庫供水量都提高一倍，公司利潤可增加到多少？元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費例3運輸問題---自來水輸送收入：900元/千噸

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

其他費用:450元/千噸

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

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

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

模型建立確定3個水庫向4個小區(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利潤=總收入-其它費用-引水管理費=144000-