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

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

設g=0.1不變t對r的〔相對〕敏感度生豬每天體重增加量r增加1%，出售時間推遲3%。rt11.敏感性分析估計r=2，g=0.1研究r,g變化時對模型結果的影響

設r=2不變t對g的〔相對〕敏感度生豬價格每天的降低量g增加1%，出售時間提前3%。gt12.強健性分析保存生豬直到利潤的增值等于每天的費用時出售由S(t,r)=3建議過一周后(t=7)重新估計,再作計算。研究r,g不是常數(shù)時對模型結果的影響w=80+rt

w=w(t)p=8-gt

p=p(t)若(10%),則（30%）每天利潤的增值每天投入的資金13.3.

數(shù)學規(guī)劃模型例1汽車廠生產(chǎn)方案例2加工奶制品的生產(chǎn)方案例3運輸問題14.如果生產(chǎn)某一類型汽車，那么至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)方案應作何改變？例1汽車廠生產(chǎn)方案汽車廠生產(chǎn)三種類型的汽車，各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量.

小型中型大型現(xiàn)有量鋼材（噸）1.535600勞動時間（小時）28025040060000利潤（萬元）234制訂月生產(chǎn)方案，使工廠的利潤最大.15.設每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3汽車廠生產(chǎn)方案模型建立

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

3〕模型中增加條件：x1,x2,x3均為整數(shù)，重新求解.ObjectiveValue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.003226結果為小數(shù)，怎么辦？1〕舍去小數(shù)：取x1=64，x2=167，算出目標函數(shù)值z=629，與LP最優(yōu)值632.2581相差不大.2〕試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數(shù)值z，通過比較可能得到更優(yōu)的解.

但必須檢驗它們是否滿足約束條件.為什么？17.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結果輸出18.其中3個子模型應去掉，然后逐一求解，比較目標函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個LP子模型汽車廠生產(chǎn)方案假設生產(chǎn)某類汽車，那么至少生產(chǎn)80輛，求生產(chǎn)方案.x1,x2,,x3=0或

80

x1=80，x2=150，x3=0，最優(yōu)值z=61019.LINGO中對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)解同前

20.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)解時.

21.例2加工奶制品的生產(chǎn)方案1桶牛奶

3公斤A1

12小時

8小時

4公斤A2

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

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

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

12小時8小時4公斤A2

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

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

獲利24×3x1

獲利16×4x2

原料供給勞動時間

加工能力

決策變量

目標函數(shù)

每天獲利約束條件非負約束

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

50桶牛奶每天根本模型23.模型分析與假設

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

圖解法

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

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

軟件實現(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元。26.結果解釋

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三種資源“資源〞剩余為零的約束為緊約束〔有效約束〕原料無剩余時間無剩余加工能力剩余4027.結果解釋

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

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

最優(yōu)解不變時目標函數(shù)系數(shù)允許變化范圍敏感性分析(“LINGO|Ranges〞)x1系數(shù)范圍(64,96)

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

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

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000影子價格有意義時約束右端的允許變化范圍原料最多增加10時間最多增加5335元可買到1桶牛奶,每天最多買多少?最多買10桶!(目標函數(shù)不變)充分條件!30.生產(chǎn)、生活物資從假設干供給點運送到一些需求點，怎樣安排輸送方案使運費最小，或利潤最大。例3運輸問題31.其他費用:450元/千噸

應如何分配水庫供水量，公司才能獲利最多？

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

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

其他費用:450元/千噸

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

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

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

模型建立確定3個水庫向4個小區(qū)的供水量34.模型求解

局部結果：ObjectiveValue:24400.00VariableValueReducedCostX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000X2250.0000000.000000X230.00000020.000000X2410.0000000.000000X3140.0000000.000000X320.00000010.000000X3310.0000000.000000利潤=總收入-其它費用-引水管理費=144000-7