優(yōu)化模型與AMPL概述

優(yōu)化模型與AMPL

最優(yōu)化是工程技術(shù)、經(jīng)濟(jì)管理、科學(xué)研究、社會(huì)生活中經(jīng)常遇到的問(wèn)題,如:優(yōu)化模型和算法的重要意義結(jié)構(gòu)設(shè)計(jì)資源分配生產(chǎn)計(jì)劃運(yùn)輸方案解決優(yōu)化問(wèn)題的手段

經(jīng)驗(yàn)積累，主觀判斷

作試驗(yàn)，比優(yōu)劣

建立數(shù)學(xué)模型，求解最優(yōu)策略最優(yōu)化:在一定條件下，尋求使目標(biāo)最大(小)的決策

優(yōu)化問(wèn)題三要素：決策變量；目標(biāo)函數(shù)；約束條件約束條件決策變量?jī)?yōu)化問(wèn)題的一般形式

無(wú)約束優(yōu)化(沒(méi)有約束)與約束優(yōu)化(有約束)

可行解（只滿(mǎn)足約束）與最優(yōu)解(取到最優(yōu)值)目標(biāo)函數(shù)局部最優(yōu)解與整體最優(yōu)解

局部最優(yōu)解(LocalOptimalSolution,如x1)

整體最優(yōu)解(GlobalOptimalSolution,如x2)x*f(x)x1x2o優(yōu)化模型的簡(jiǎn)單分類(lèi)

線(xiàn)性規(guī)劃(LP)

目標(biāo)和約束均為線(xiàn)性函數(shù)

非線(xiàn)性規(guī)劃(NLP)

目標(biāo)或約束中存在非線(xiàn)性函數(shù)

二次規(guī)劃(QP)

目標(biāo)為二次函數(shù)、約束為線(xiàn)性

整數(shù)規(guī)劃(IP)

決策變量(全部或部分)為整數(shù)整數(shù)線(xiàn)性規(guī)劃(ILP)，整數(shù)非線(xiàn)性規(guī)劃(INLP)

純整數(shù)規(guī)劃(PIP),混合整數(shù)規(guī)劃(MIP)

一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃連續(xù)優(yōu)化離散優(yōu)化數(shù)學(xué)規(guī)劃優(yōu)化模型的簡(jiǎn)單分類(lèi)和求解難度優(yōu)化線(xiàn)性規(guī)劃非線(xiàn)性規(guī)劃二次規(guī)劃連續(xù)優(yōu)化整數(shù)規(guī)劃問(wèn)題求解的難度增加

常用優(yōu)化軟件1.LINDO/LINGO軟件2.MATLAB優(yōu)化工具箱/Mathematic的優(yōu)化功能3.SAS(統(tǒng)計(jì)分析)軟件的優(yōu)化功能4.EXCEL軟件的優(yōu)化功能5.AMPL/MINOS,CPLEXMATLAB優(yōu)化工具箱能求解的優(yōu)化模型優(yōu)化工具箱3.0(MATLAB7.0R14)連續(xù)優(yōu)化離散優(yōu)化無(wú)約束優(yōu)化非線(xiàn)性極小fminunc非光滑(不可微)優(yōu)化fminsearch非線(xiàn)性方程(組)fzerofsolve全局優(yōu)化暫缺非線(xiàn)性最小二乘lsqnonlinlsqcurvefit線(xiàn)性規(guī)劃linprog純0-1規(guī)劃bintprog一般IP(暫缺)非線(xiàn)性規(guī)劃fminconfminimaxfgoalattainfseminf上下界約束fminbndfminconlsqnonlinlsqcurvefit約束線(xiàn)性最小二乘lsqnonneglsqlin約束優(yōu)化二次規(guī)劃quadprog1桶牛奶3公斤A1

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

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

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

可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？每天：線(xiàn)性規(guī)劃模型－例:奶制品生產(chǎn)計(jì)劃

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ù)約束

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

50桶牛奶每天AMPL程序模型文件,用文本編輯器編輯,保存為milk.modsetPordered;#產(chǎn)品集合param

T{iinP}>0;#加工時(shí)間param

Q{iinP}>0;#單位產(chǎn)量param

L{iinP}>0;#單位利潤(rùn)var

x{iinP}>=0;#生產(chǎn)計(jì)劃maximizeprofit:sum{iinP}L[i]*Q[i]*x[i];subjecttoraw:sum{iinP}x[i]<=50;subjecttotime:sum{iinP}T[i]*x[i]<=480;subjecttocapacity:Q[first(P)]*x[first(P)]<=100;數(shù)據(jù)文件文件,用文本編輯器編輯,保存為milk.datsetP:=A1A2;paramT:=A112A28;paramQ:=A13A24;paramL:=A124A216;批處理文件,用文本編輯器編輯,保存為milk.runmodelmilk.mod;datamilk.dat;optionsolvercplexamp;solve;運(yùn)行求解AMPL:milk.runCPLEX11.0.0:optimalsolution;objective33602dualsimplexiterations(1inphaseI)x[*]:=A120A230;靈敏度分析AMPL:displayx.rc,x.down,x.up;

x.rc

x.down

x.up:=A106496A204872;x.rc最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量;x.down,x.up最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍AMPL:displayraw,time,capacity;aw=48time=2capacity=0原料增加1單位,利潤(rùn)增長(zhǎng)48;時(shí)間增加1單位,利潤(rùn)增長(zhǎng)2;加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格AMPL:displayraw.down,raw.up,raw.current,raw.slack;raw.down=43.3333raw.up=60raw.current=50raw.slack=0影子價(jià)格有意義時(shí)約束右端的允許變化范圍;原料最少到43.3,最大到60,slack=0意為原料用完.模型求解

圖解法

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

Z=0Z=2400Z=3360z=c(常數(shù))~等值線(xiàn)c在B(20,30)點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線(xiàn)性函數(shù)可行域?yàn)橹本€(xiàn)段圍成的凸多邊形目標(biāo)函數(shù)的等值線(xiàn)為直線(xiàn)最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。求解LP的基本思想思路：從可行域的某一頂點(diǎn)開(kāi)始，只需在有限多個(gè)頂點(diǎn)中一個(gè)一個(gè)找下去，一定能得到最優(yōu)解。LP的約束和目標(biāo)函數(shù)均為線(xiàn)性函數(shù)2維可行域

線(xiàn)段組成的凸多邊形目標(biāo)函數(shù)等值線(xiàn)為直線(xiàn)最優(yōu)解凸多邊形的某個(gè)頂點(diǎn)n維超平面組成的凸多面體等值線(xiàn)是超平面凸多面體的某個(gè)頂點(diǎn)LP的通常解法是單純形法(G.B.Dantzig,1947)線(xiàn)性規(guī)劃模型的解的幾種情況線(xiàn)性規(guī)劃問(wèn)題有可行解(Feasible)無(wú)可行解（Infeasible）有最優(yōu)解（Optimal）無(wú)最優(yōu)解(Unbounded)非線(xiàn)性規(guī)劃模型－例：選址問(wèn)題某公司有6個(gè)建筑工地，位置坐標(biāo)為(ai,bi)(單位：公里),水泥日用量di

(單位：噸）假設(shè)：料場(chǎng)和工地之間有直線(xiàn)道路用例中數(shù)據(jù)計(jì)算，最優(yōu)解為總噸公里數(shù)為136.2線(xiàn)性規(guī)劃模型(LP)決策變量：cij(料場(chǎng)j到工地i的運(yùn)量）~12維選址問(wèn)題：NLP2）改建兩個(gè)新料場(chǎng)，需要確定新料場(chǎng)位置(xj,yj)和運(yùn)量cij

，在其它條件不變下使總噸公里數(shù)最小。決策變量：cij，(xj,yj)~16維非線(xiàn)性規(guī)劃模型(NLP)整數(shù)規(guī)劃-例:聘用方案決策變量：周一至周日每天(新)聘用人數(shù)x1,x2,x7目標(biāo)函數(shù)：7天(新)聘用人數(shù)之和約束條件：周一至周日每天需要人數(shù)連續(xù)工作5天周一工作的應(yīng)是(上)周四至周一聘用的設(shè)系統(tǒng)已進(jìn)入穩(wěn)態(tài)（不是開(kāi)始的幾周）聘用方案整數(shù)規(guī)劃模型(IP)丁的蛙泳成績(jī)退步到1’15”2；戊的自由泳成績(jī)進(jìn)步到57”5,組成接力隊(duì)的方案是否應(yīng)該調(diào)整？如何選拔隊(duì)員組成4100米混合泳接力隊(duì)?0-1規(guī)劃－混合泳接力隊(duì)的選拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候選人的百米成績(jī)窮舉法：組成接力隊(duì)的方案共有5!=120種。目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(秒)~隊(duì)員i

第j種泳姿的百米成績(jī)約束條件每人最多入選泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人0-1規(guī)劃:

整數(shù)規(guī)劃的特例整數(shù)規(guī)劃問(wèn)題一般形式

整數(shù)線(xiàn)性規(guī)劃(ILP)

目標(biāo)和約束均為線(xiàn)性函數(shù)整數(shù)非線(xiàn)性規(guī)劃(NLP)

目標(biāo)或約束中存在非線(xiàn)性函數(shù)整數(shù)規(guī)劃問(wèn)題的分類(lèi)

純(全)整數(shù)規(guī)劃(PIP)

決策變量均為整數(shù)混合整數(shù)規(guī)劃(MIP)

決策變量有整數(shù)，也有實(shí)數(shù)0-1規(guī)劃

決策變量只取0或1取消整數(shù)規(guī)劃中決策變量為整數(shù)的限制（松弛），對(duì)應(yīng)的連續(xù)優(yōu)化問(wèn)題稱(chēng)為原問(wèn)題的松弛問(wèn)題整數(shù)規(guī)