一、優(yōu)化問題基本概念
1.1 優(yōu)化問題
優(yōu)化問題：在一系列客觀或主觀限制條件下,尋求使所關(guān)注的某個或多個指標達到最大(或最小)的決策
- 結(jié)構(gòu)設(shè)計、資源分配、生產(chǎn)計劃、運輸方案中經(jīng)?？梢?/li>
通常的解決手段：
- 經(jīng)驗積累、主觀判斷
- 做試驗、比優(yōu)劣
- 建立數(shù)學(xué)模型，求解最優(yōu)策略
解決優(yōu)化問題的數(shù)學(xué)方法：
- 數(shù)學(xué)規(guī)劃
- 圖論
解決優(yōu)化問題的數(shù)學(xué)軟件：
- matlab
- lingo
當決策變量約束條件比較少是可以使用matlab軟件，當涉及的決策變量約束條件比較多時可以考慮更為專業(yè)的lingo軟件
1.2 優(yōu)化模型的簡單分類
優(yōu)化模型可以根據(jù)目標、參數(shù)、變量、約束等劃分成不同的類別
比較常用的一種劃分依據(jù)按照決策變量是否連續(xù)劃分為連續(xù)優(yōu)化與離散優(yōu)化
連續(xù)優(yōu)化：
1. 線性規(guī)劃(LP) ：目標和約束均為線性函數(shù)
2. 非線性規(guī)劃(NLP) ：目標或約束中存在非線性函數(shù)
3. 二次規(guī)劃(QP) ：目標為二次函數(shù)、約束為線性(NLP特例)
離散優(yōu)化：
整數(shù)規(guī)劃(IP) ： 決策變量(全部或部分)為整數(shù)
1. 整數(shù)線性規(guī)劃(ILP)
2. 整數(shù)非線性規(guī)劃(INLP)
3. 純整數(shù)規(guī)劃(PIP),
4. 混合整數(shù)規(guī)劃(MIP)
5. 一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃
說明：
由于不同類型的優(yōu)化問題的求解難度和求解方法是有很大差異的,因此在解決我們所面臨的問題時,弄清問題的類型是很有必要的。
例如,只能對于連續(xù)線性規(guī)劃或某些特定的二次規(guī)劃(如凸二次規(guī)劃)問題,可以比較容易地求到整體最優(yōu)解，或判斷原問題無解;而對于一般的非線性規(guī)劃和整數(shù)規(guī)劃,當問題的規(guī)模比較大時,在可以接受的計算時間內(nèi)找到整體最優(yōu)解是非常困難的,因此通常只能求局部最優(yōu)解。
一般來說,離散優(yōu)化問題比連續(xù)優(yōu)化問題難以求解,非線性規(guī)劃問題比線性規(guī)劃問題難以求解,非光滑優(yōu)化比光滑優(yōu)化難以求解。
1.3 國賽中的優(yōu)化問題
| 2000-2021 |
|---|
| ? 2000B 鋼管訂購和運輸問題 |
| ? 2001B 公交車優(yōu)化調(diào)度 |
| ? 2001C 基金使用的最優(yōu)策略 |
| ? 2002B 彩票中的數(shù)學(xué) |
| ? 2003B 露天礦生產(chǎn)的車輛安排問題 |
| ? 2004B 奧運會臨時超市網(wǎng)點設(shè)計問題 |
| ? 2004D 公務(wù)員招聘工作中錄用方案 |
| ? 2005B DVD在線租賃 |
| ? 2006B 出版社的資源配置問題 |
| ? 2007B 乘公交，看奧運 |
| ? 2008B 高等教育學(xué)費探討 |
| ? 2009B 眼科病床的合理安排 |
| ? 2011B 交巡警服務(wù)平臺設(shè)置與調(diào)度 |
| ? 2012B 太陽能小屋設(shè)計 |
| ? 2013B 碎紙片的拼接 |
| ? 2014B 創(chuàng)意折疊桌設(shè)計 |
| ? 2015B “互聯(lián)網(wǎng)+”時代的出租車資源配置 |
| ? 2016B 小區(qū)開放對道路通行的影響 |
| ? 2017B “拍照賺錢”任務(wù)定價 |
| ? 2018B 智能RGV的動態(tài)調(diào)度策略 |
| ? 2019B “同心協(xié)力”策略研究 |
| ? 2020B 穿越沙漠 |
| ? 2021C 生產(chǎn)企業(yè)原材料的訂購與運輸 |
二、數(shù)學(xué)規(guī)劃
求解各種優(yōu)化問題的關(guān)鍵就是找優(yōu)化問題的三要素的過程即：
- 決策變量
- 目標函數(shù)
- 約束條件
2.1 線性規(guī)劃（LP）
2.1.1 LP問題
例1
解
最后的模型
matlab求解
% 化成matlab求線性規(guī)劃的標準形式
f = [-7 -12]'; % 目標函數(shù)的系數(shù)向量
A=[9 4;4 5;3 10]; % 不等式約束
b=[360 200 300]';
lb=[0 0]';
[x,val]=linprog(f,A,b,[],[],lb)
val=-val
運行結(jié)果：
此處也可以使用lindo求解
max 7x1+12x2
st
9x1+4x2<=360
4x1+5x2<=200
3x1+10x2<=300
x1>=0
x2>=0
結(jié)果
對于這樣的數(shù)學(xué)模型，我們一般有如下的名稱。特別是價格系數(shù)、技術(shù)系數(shù)
2.1.2 LP模型的表示形式
（1）一般形式
（2）矩陣形式
主要用于在matlab中求解，用matlab求解時需要將涉及到的矩陣全部列出。策變量、約束條件比較少的時候完全可以使用。而當決策變量、約束條件成百上千時，寫出其矩陣變得不太現(xiàn)實，這就需要用lingo求解
例如在上個例題中就需要列出以下矩陣
（3）和式形式
這種形式主要適用于lingo中，可以根據(jù)和式形式比較容易的編寫出相應(yīng)的程序
2.1.3 求解通用算法
- 單純形算法
二維空間線性規(guī)劃的最優(yōu)解必然在凸多邊形的頂點
三維空間線性規(guī)劃的最優(yōu)解必然在凸多邊體的頂點
2.1.4 靈敏性分析
意義:現(xiàn)實問題中價格、技術(shù)、資源系數(shù)可能會變化（發(fā)生微小變動），生產(chǎn)方案也會受到影響
給定一個波動范圍使得結(jié)果還是最優(yōu)解不變
2.2 整數(shù)規(guī)劃（IP）
整數(shù)規(guī)劃求解整數(shù)規(guī)劃一般為分支定界法或割平面法
線性規(guī)劃求解一般為單純形法
非線性規(guī)劃一般求迭代解梯度下降
整數(shù)規(guī)劃與線性規(guī)劃建模區(qū)別在變量變?yōu)檎麛?shù)，其余步驟一樣
2.3 0-1規(guī)劃規(guī)劃
2.3.1 選址問題
題目：
解決：
代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-456382.html
sets:
site/1..7/:x,b,c;
endsets
data:
q=?;
enddata
max=@sum(site(i):c(i)*x(i));
@sum(site(i):b(i)*x(i))<q;
x(1)+x(2)+x(3)<=2;
x(4)+x(5)>=1;
x(6)+x(7)>=1;
!@sum(site(i)|i#le#3:x(i))<=2;
!@sum(site(i)|i#ge#6:x(i))>=1;
@for(site(i):@bin(x(i)));
2.3.2 指派問題
題目：
解決：
代碼：
sets:
set1/1..4/:y;
set2/1..4/:z;
set3(set1,set2):c,x;
endsets
min=@sum(set3(i,j):c*x);
@for(set1(i):@sum(set2(j):x(i,j))=1);
@for(set2(j):@sum(set1(i):x(i,j))=1);
@for(set3(i,j):@bin(x(i,j)));
2.3.3 固定費用問題
題目：
解決：
代碼：
sets:
way/1..3/:x,y;
endsets
min=13*x(1)+12*x(2)+10*x(3)+120*y(1)+150*y(2)+180*y(3);
@sum(way(i):x)=500;
1.5*x(1)+1.7*x(2)+1.8*x(3)<=1500;
1.3*x(1)+1.5*x(2)+1.6*x(3)<=1000;
4*x(1)+4.5*x(2)+1.5*x(3)<=3500;
2.8*x(1)+3.8*x(2)+4.2*x(3)<=2800;
@for(way:0.01*y<=x);
@for(way:x<=1000*y);
@for(way:@bin(y));
2.3.4 0-1變量的其他用處
- 把相互約束的排斥條件轉(zhuǎn)化為普通的約束條件
- 表示分段函數(shù)
2.4 多目標規(guī)劃
多目標無法直接求解，需要轉(zhuǎn)化為單目標規(guī)劃文章來源地址http://www.zghlxwxcb.cn/news/detail-456382.html
2.4.1解決方法
- 主要目標法：只保留一個主要目標，將其他的轉(zhuǎn)化為約束條件
- 線性加權(quán)法（前提要保證兩者的量綱一致） 將所有目標轉(zhuǎn) 化為同時求最大或是同時求最小 若量綱不一致需消除量綱的影響（映射到01區(qū)間）
到了這里，關(guān)于數(shù)學(xué)建模 優(yōu)化問題——數(shù)學(xué)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
