運(yùn)籌學(xué)報(bào)告2014年

全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽

ChinaUndergraduateMathematicalContestinModeling(CUMCM)

http://

國(guó)際大學(xué)生數(shù)學(xué)建模競(jìng)賽TheMathematicalContestinModeling(MCM)9/25/20231廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝往年數(shù)模試題1993年A題非線性交調(diào)的頻率設(shè)計(jì)

1993年B題球隊(duì)排名問(wèn)題1994年A題逢山開(kāi)路

1994年B題鎖具裝箱1995年A題一個(gè)飛行管理模型

1995年B題天車與冶煉爐的作業(yè)調(diào)度1996年A題最優(yōu)捕魚(yú)策略

1996年B題節(jié)水洗衣機(jī)1997年A題零件的參數(shù)設(shè)計(jì)

1997年B題截?cái)嗲懈?998年A題投資的收益和風(fēng)險(xiǎn)

1998年B題災(zāi)情巡視路線1999年A題自動(dòng)化車床管理

1999年B題鉆井布局2000年A題DNA序列分類

2000年B題鋼管定購(gòu)和運(yùn)輸2001年A題血管的三維重建

2001年B題公交車調(diào)度2002年A題車燈線光源的優(yōu)化設(shè)計(jì)

2002年B題彩票中的數(shù)學(xué)2003年A題SARS的傳播

2003年B題露天礦生產(chǎn)的車輛安排2004年A題奧運(yùn)會(huì)臨時(shí)超市網(wǎng)點(diǎn)設(shè)計(jì)

2004年B題電力市場(chǎng)的輸電阻塞管理2005年A題長(zhǎng)江水質(zhì)的評(píng)價(jià)和預(yù)測(cè)

2005年B題DVD在線租賃2006年A題出版社的資源配置

2006年B題艾滋病療法評(píng)價(jià)及療效預(yù)測(cè)2007年A題人口預(yù)測(cè)

2007年B題乘公交

看奧運(yùn)2008年A題高校學(xué)費(fèi)標(biāo)準(zhǔn)

2008年B題電子眼定位2009年A題

制動(dòng)器試驗(yàn)臺(tái)的控制方法分析

2009年B題眼科病床的合理安排

9/25/20232廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝數(shù)學(xué)建模步驟示意圖

模型準(zhǔn)備

模型假設(shè)

模型檢驗(yàn)

模型應(yīng)用

模型分析

模型求解

模型構(gòu)成

9/25/20233廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝運(yùn)籌學(xué)中的優(yōu)化模型

及輔助軟件求解主講人：付輝Emial：lindafh819@126.com9/25/20234廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝優(yōu)化模型

實(shí)際問(wèn)題中的優(yōu)化模型x~決策變量f(x)~目標(biāo)函數(shù)gi(x)0~約束條件數(shù)學(xué)規(guī)劃線性規(guī)劃(LP)二次規(guī)劃(QP)非線性規(guī)劃(NLP)純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃(MIP)整數(shù)規(guī)劃(IP)0-1整數(shù)規(guī)劃一般整數(shù)規(guī)劃連續(xù)規(guī)劃9/25/20235廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝優(yōu)化問(wèn)題與規(guī)劃模型解決最優(yōu)化問(wèn)題的數(shù)學(xué)方法：運(yùn)籌學(xué)運(yùn)籌學(xué)主要分支：線性規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、圖與網(wǎng)絡(luò)分析、存貯論、排隊(duì)倫、對(duì)策論、決策論。它們的特點(diǎn)就是：在若干可能的方案中尋求某種意義下的最優(yōu)方案。數(shù)學(xué)上稱為最優(yōu)化問(wèn)題,而研究處理這種問(wèn)題的方法叫最優(yōu)化的方法。9/25/20236廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝優(yōu)化模型是一類既重要又特殊的數(shù)學(xué)模型，而優(yōu)化建模方法是也一種特殊的數(shù)學(xué)建模方法。優(yōu)化模型一般有下面三個(gè)要素：（1）

決策變量，它通常是該問(wèn)題要求解的那些未知量。（2）目標(biāo)函數(shù)，通常是該問(wèn)題要優(yōu)化（最大或最?。┑哪莻€(gè)目標(biāo)的數(shù)學(xué)表達(dá)式，它是決策變量的函數(shù)。（3）約束條件，由該問(wèn)題對(duì)決策變量的限制條件給出。9/25/20237廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝主要內(nèi)容：1.優(yōu)化引例及輔助軟件求解；2.運(yùn)籌學(xué)中一些基本模型；3.建模實(shí)例；9/25/20238廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝實(shí)例：家具生產(chǎn)的安排

家具公司生產(chǎn)桌子和椅子，用于生產(chǎn)的勞力共計(jì)450個(gè)工時(shí)，木材共有4立方米,每張桌子要使用15個(gè)工時(shí)、0.2立方木材，售價(jià)80元。每張椅子使用10個(gè)工時(shí)、0.05立方木材，售價(jià)45元。問(wèn)為達(dá)到最大的收益，應(yīng)如何安排生產(chǎn)？

分析：

1.求什么？

生產(chǎn)多少桌子？x1

生產(chǎn)多少椅子？x2

2.優(yōu)化什么？

收益最大Maxf=80x1+45x2

3.限制條件？

原料總量0.2x1+0.05x2≤4

勞力總數(shù)

15x1+10x2≤4509/25/20239廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝模型：以產(chǎn)值為目標(biāo)取得最大收益.

設(shè)：生產(chǎn)桌子x1張,椅子x2張,(決策變量)

將目標(biāo)優(yōu)化為：maxf=80x1+45x2

對(duì)決策變量的約束：

0.2x1+0.05x2≤4（Ⅰ）

15x1+10x2≤450,（Ⅱ）

x1≥0,x2≥0,9/25/202310廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝模型求解：

（1）圖解法（用于決策變量是二維）15x1+10x2=450x1x20.2x1+0.05x2=49/25/202311廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)(關(guān)于不同的目標(biāo)值是一族平行直線)目標(biāo)值的大小描述了直線離原點(diǎn)的遠(yuǎn)近,并且最優(yōu)解一定在可行解集的某個(gè)極點(diǎn)上達(dá)到

(穿過(guò)可行域的目標(biāo)直線組中最遠(yuǎn)離(或接近)原點(diǎn)的直線所穿過(guò)的凸多邊形的頂點(diǎn)).9/25/202312廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝（2）用EXCEL—Solver實(shí)現(xiàn)

①模型中的數(shù)據(jù)直接輸入EXCEL工作表中。其中決策變量初始的值可以任意給出，它們是可變的，軟件最后將給出最優(yōu)解的值。SUMPRODUCT是EXCEL的一個(gè)內(nèi)置函數(shù)，表示兩個(gè)向量或矩陣對(duì)應(yīng)元素乘積的和。9/25/202313廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝9/25/202314廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝9/25/202315廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝引用工具——規(guī)劃求解（需要工具—加載宏安裝）9/25/202316廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝9/25/202317廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝9/25/202318廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝混合線性規(guī)劃的EXCEL求解

9/25/202319廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝求解模型步驟：打開(kāi)MicrosoftExcel的一個(gè)工作表；把模型的目標(biāo)函數(shù)系數(shù)矩陣置于A1至E4區(qū)域，約束常數(shù)25000、30000和21000分別置于G6、G7和G8單元格；選擇A6至E9范圍作可變單元，并輸入初值1。其中A6至E8區(qū)域?qū)?yīng)變量xij(i=1,2,3;j=0,1,2,3,4)，而B(niǎo)9至E9則分別對(duì)應(yīng)變量y1,y2,y3,和y4,A9則恒為1；在F6、F7、F8和F9處分別輸入“=SUM（A6：E6）”、“=SUM（A7：E7）”、“=SUM（A8：E8）”、“=SUM（B9：E9）”,再在A10至E10處分別輸入“=A6+A7+A8”、“=B6+B7+B8-41000*B9”、“=C6+C7+C8-41000*C9”、“=D6+D7+D8-41000*D9”、“=E6+E7+E8-41000*E9”表示約束等式的左邊；選擇單元格A11,輸入“=A1*A6”,再把其引用至單元格E14;即用鼠標(biāo)按著單元格A11的右下角，先拖至A14,再拖至E14;以單元格F14作目標(biāo)單元格，輸入“=SUM(A11:E14)”9/25/202320廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝結(jié)果如圖所示：9/25/202321廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝進(jìn)入“規(guī)劃求解”界面?！霸O(shè)置目標(biāo)單元格”處輸入“F14”,然后選“最小值”，再在“可變單元格”處輸入“A6:E9”,在“約束”處添加12個(gè)約束：⑴“A6：E8>=0”、⑵“A9=1”、⑶“B9：E9＝二進(jìn)制”、⑷“A10=35000”、⑸“B10=0”、⑹“C10=0”、⑺“D10=0”、⑻“E10=0”、⑼“F6=G6”、⑽“F7=G7”、⑾“F8=G8”、⑿“F9=1”。最后，規(guī)劃求解參數(shù)界面如圖8。再在“選項(xiàng)”中選擇“采用線性模型”。9/25/202322廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝單擊求解，即可得到此問(wèn)題的解。9/25/202323廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝結(jié)果：目錄9/25/202324廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝（3）用Matlab實(shí)現(xiàn)-------lp

線性優(yōu)化函數(shù)

線性優(yōu)化問(wèn)題即目標(biāo)函數(shù)和約束條件均為線性函數(shù)的問(wèn)題。其標(biāo)準(zhǔn)形式為：9/25/202325廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝

化為9/25/202326廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝程序如下：

c=[-2，-1,1];A=[1，4，-1；2，-2，1];b=[4,12];

Aeq=[1，1，2];beq=6;

LB＝[0,0,-inf];UB=[inf,inf,5];

[x,z]=linprog(c,A,b,Aeq,beq,LB,UB)

運(yùn)行結(jié)果：

x=

4.6667

0.0000

0.6667

z=

-8.6667

說(shuō)明：x解為最優(yōu)解，目標(biāo)最大為8.6667。9/25/202327廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝MATLAB優(yōu)化工具箱能求解的優(yōu)化模型優(yōu)化工具箱3.0(MATLAB7.0R14)連續(xù)優(yōu)化離散優(yōu)化無(wú)約束優(yōu)化非線性極小fminunc非光滑(不可微)優(yōu)化fminsearch非線性方程(組)fzerofsolve全局優(yōu)化暫缺非線性最小二乘lsqnonlinlsqcurvefit線性規(guī)劃linprog0-1規(guī)劃bitprog一般ＩＰ(暫缺)非線性規(guī)劃fminconfminimaxfgoalattainfseminf上下界約束fminbndfminconlsqnonlinlsqcurvefit約束線性最小二乘lsqnonneglsqlin約束優(yōu)化二次規(guī)劃quadprog9/25/202328廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝（4）用LINDO/LINGO實(shí)現(xiàn)

我們可以直接在下面的窗口輸入LP模型輸入后，用鼠標(biāo)單擊LINDO軟件工具欄中的圖標(biāo)，或從菜單中選擇Solve│Solve(Ctrsl+S)命令，則LINDO開(kāi)始編譯這個(gè)模型，編譯沒(méi)錯(cuò)誤馬上開(kāi)始求解，求解時(shí)會(huì)顯示如圖（4）—2所示LINDO求解器運(yùn)行狀態(tài)窗口（里面的“Objective”就是最優(yōu)解，即：2200）。9/25/202329廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝

圖（4）—29/25/202330廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝

“LPOPTIMUMFOUNDATSTEP2”表示單純形法在兩次迭代后得到最優(yōu)解?！癘BJECTIVEFUNCTIONVALUE1)2200.000”表示最優(yōu)目標(biāo)值為2200.000（在LINDO中目標(biāo)函數(shù)所在的行總是被認(rèn)為是第1行，這就是這里“1）”的含義）。9/25/202331廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝（5）LINDO和LINGO軟件能求解的優(yōu)化模型

LINGO

LINDO優(yōu)化模型線性規(guī)劃(LP)非線性規(guī)劃(NLP)二次規(guī)劃(QP)連續(xù)優(yōu)化整數(shù)規(guī)劃(IP)9/25/202332廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝

LPQPNLPIP全局優(yōu)化(選)

ILPIQPINLP

LINDO/LINGO軟件的求解過(guò)程LINDO/LINGO預(yù)處理程序線性優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序1.確定常數(shù)2.識(shí)別類型1.單純形算法2.內(nèi)點(diǎn)算法(選)1、順序線性規(guī)劃法(SLP)2、廣義既約梯度法(GRG)(選)

3、多點(diǎn)搜索(Multistart)(選)9/25/202333廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝（6）建模時(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)9/25/202334廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝一般模型的建立某機(jī)器廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，需在A、B、C三中不同的設(shè)備上加工。具體耗時(shí)如下表：?jiǎn)枺喝绾紊a(chǎn)使得利潤(rùn)最大？ABC利潤(rùn)Ⅰ產(chǎn)品2h402Ⅱ產(chǎn)品2053能力時(shí)限1216159/25/202335廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝建立模型模型假設(shè)：設(shè)和分別表示?、П兩種產(chǎn)品在計(jì)劃期內(nèi)的產(chǎn)量，利潤(rùn)收入為。模型建立：目標(biāo)函數(shù)：約束條件：

目標(biāo)規(guī)劃9/25/202336廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝線性規(guī)劃問(wèn)題的一般模型：s.t.9/25/202337廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝例某部門有資金200萬(wàn)元，今后5年內(nèi)考慮給以下的項(xiàng)目投資。已知項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年年末可收回本利110％；項(xiàng)目B：從第一年到第四年年初都可投資，次年末可收回本利125％，投資額30萬(wàn)；項(xiàng)目C：第三年初投資，第五年末能收回本利140％，投資額80萬(wàn)；項(xiàng)目D：第二年初投資，第五年末能收回本利155％，投資額100萬(wàn)；問(wèn)：如何投資使得第五年末資金額最大？9/25/202338廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝1.模型假設(shè)設(shè)為第i年年初投入第j種方案的資金數(shù)。2.模型分析i年初12345本利限量ABCD110%125%140%155%30801009/25/202339廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝3.模型建立目標(biāo)函數(shù)：約束條件：第一年年初：第二年年初：第三年年初：第四年年初：第五年年初：各變量都要大于等于零，且在各方案投資限量范圍內(nèi)。目標(biāo)函數(shù)其實(shí)就是第五年的收益。9/25/202340廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝求解方法方法：圖解法（只能求解兩個(gè)變量的問(wèn)題）單純形法大M法兩階段法結(jié)合對(duì)偶單純形法可以對(duì)線性規(guī)劃問(wèn)題進(jìn)行靈敏度分析及參數(shù)規(guī)劃。9/25/202341廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝運(yùn)輸問(wèn)題某糖果公司下面設(shè)有三個(gè)分工廠，每天的糖果生產(chǎn)量分別為：A1－7t，A2－4t，A3－9t。該公司把這些糖果分別運(yùn)往四個(gè)地區(qū)的門市部銷售，各地區(qū)每天的銷售量為：B1－3t，B2－6t，B3－5t，B4－6t。已知從每個(gè)加工廠到各銷售門市部每噸糖果的運(yùn)價(jià)如下表所示，問(wèn)該食品公司應(yīng)如何調(diào)運(yùn)，在滿足各門市部銷售需要的情況下，使總的運(yùn)費(fèi)支出為最少。9/25/202342廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3311310192874105749銷量36569/25/202343廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝模型假設(shè)：設(shè)代表從第i個(gè)產(chǎn)地調(diào)運(yùn)給第j個(gè)銷地的物資的單位數(shù)量。模型建立：目標(biāo)函數(shù)約束條件s.t.9/25/202344廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝一般模型方法：表上作業(yè)法（找初始解：最小元素法、Vogel法;調(diào)整：閉回路法、位勢(shì)法）s.t.9/25/202345廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝整數(shù)規(guī)劃特點(diǎn)：在線性規(guī)劃問(wèn)題中加一個(gè)約束——變量取整數(shù)解。求解的方法有：匈牙利法、分枝定界法、割平面法指派問(wèn)題：

N個(gè)人完成N項(xiàng)任務(wù)，每人一項(xiàng)。由于每個(gè)人的特點(diǎn)不同，不同人完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)（效益）不同。如何分配工作方案可以使總回報(bào)（效益）最大？

9/25/202346廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝動(dòng)態(tài)規(guī)劃模型的分類以“時(shí)間”角度可分成：

離散型和連續(xù)型。從信息確定與否可分成：

確定型和隨機(jī)型。從目標(biāo)函數(shù)的個(gè)數(shù)可分成：

單目標(biāo)型和多目標(biāo)型。動(dòng)態(tài)規(guī)劃9/25/202347廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝動(dòng)態(tài)規(guī)劃的基本原理多階段決策過(guò)程最優(yōu)化多階段決策過(guò)程是指這樣一類特殊的活動(dòng)過(guò)程，他們可以按時(shí)間順序分解成若干相互聯(lián)系的階段，在每個(gè)階段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列，所以多階段決策問(wèn)題也稱為序貫決策問(wèn)題。9/25/202348廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝例（一定階段最短路問(wèn)題）

W先生每天駕車去公司上班。如圖，W先生的住所位于A，公司位于F，圖中的直線段代表公路，交叉點(diǎn)代表路口，直線段上的數(shù)字代表兩路口之間的平均行駛時(shí)間。現(xiàn)在W先生的問(wèn)題是要確定一條最省時(shí)的上班路線。9/25/202349廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝A3B14C13D14532B22C23D2E11234C34D35E22F9/25/202350廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF9/25/202351廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝1階段（Stage）

將所給問(wèn)題的過(guò)程，按時(shí)間或空間特征分解成若干個(gè)相互聯(lián)系的階段，以便按次序去求每階段的解，常用k表示階段變量。我們把從A到F看成一個(gè)五階段問(wèn)題。9/25/202352廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝2狀態(tài)（State）

各階段開(kāi)始時(shí)的客觀條件叫做狀態(tài)。描述各階段狀態(tài)的變量稱為狀態(tài)變量，常用sk表示第k階段的狀態(tài)變量，狀態(tài)變量的取值集合稱為狀態(tài)集合，用Sk表示。

9/25/202353廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝動(dòng)態(tài)規(guī)劃中的狀態(tài)具有如下性質(zhì)：

當(dāng)某階段狀態(tài)給定以后，在這階段以后的過(guò)程的發(fā)展不受這段以前各段狀態(tài)的影響。即：過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前狀態(tài)去影響它未來(lái)的發(fā)展，這稱為無(wú)后效性。如果所選定的變量不具備無(wú)后效性，就不能作為狀態(tài)變量來(lái)構(gòu)造動(dòng)態(tài)規(guī)劃模型。9/25/202354廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝3決策和策略（DecisionandPolicy）

當(dāng)各段的狀態(tài)確定以后，就可以做出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。決策變量用dk(Sk)表示，允許決策集合用Dk(Sk)表示。9/25/202355廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝

各個(gè)階段決策確定后，整個(gè)問(wèn)題的決策序列就構(gòu)成一個(gè)策略，用p1,n(d1,d2,…dn)表示。對(duì)每個(gè)實(shí)際問(wèn)題，可供選擇的策略有一定的范圍，稱為允許策略集合，用P表示。使整個(gè)問(wèn)題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。9/25/202356廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝4狀態(tài)轉(zhuǎn)移方程

動(dòng)態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段的決策結(jié)果。如果給定了第k段的狀態(tài)Sk

，本階段決策為dk(Sk)

，則第k+1段的狀態(tài)Sk+1由公式：Sk+1=Tk（

Sk，dk）確定，稱為狀態(tài)轉(zhuǎn)移方程。9/25/202357廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝5指標(biāo)函數(shù)

用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)稱為指標(biāo)函數(shù)。最優(yōu)指標(biāo)函數(shù)記為fk(Sk)。

9/25/202358廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝動(dòng)態(tài)規(guī)劃的基本思想：

從過(guò)程的最后一段開(kāi)始，用逆序遞推方法求解，逐步求出各段各點(diǎn)到終點(diǎn)E最短路線，最后求出A點(diǎn)到E點(diǎn)的最短路線。9/25/202359廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝動(dòng)態(tài)規(guī)劃的函數(shù)方程（DP）

建立DP函數(shù)方程是指確定過(guò)程的階段及階段數(shù)，規(guī)定狀態(tài)變量和決策變量的取法，給出各階段的狀態(tài)集合，允許決策集合，狀態(tài)轉(zhuǎn)移方程和指標(biāo)函數(shù)等。9/25/202360廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝在上面的計(jì)算過(guò)程中，利用了第k階段與第k+1階段的關(guān)系：fk(Sk)=Minr(Sk,dk(Sk))+fk+1(Sk+1)

dk(Sk)k=1,2,3,4,5f6(S6)=0

這種遞推關(guān)系，稱為動(dòng)態(tài)規(guī)劃的函數(shù)基本方程。9/25/202361廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝貝爾曼(Ballman)最優(yōu)化原理

作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)，即無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。這就是說(shuō)，不管引導(dǎo)到這個(gè)現(xiàn)時(shí)狀態(tài)的頭一個(gè)狀態(tài)和決策是什么，所有的未來(lái)決策應(yīng)是最優(yōu)的。9/25/202362廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：可把一個(gè)N維優(yōu)化問(wèn)題化成N個(gè)一維優(yōu)化問(wèn)題求解。DP方程中附加某些約束條件，可使求解更加容易。求得最優(yōu)解以后，可得所有子問(wèn)題的最優(yōu)解。9/25/202363廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝動(dòng)態(tài)規(guī)劃的缺點(diǎn)：“一個(gè)”問(wèn)題，“一個(gè)”模型，“一個(gè)”求解方法。且求解技巧要求比較高，沒(méi)有統(tǒng)一處理方法。狀態(tài)變量維數(shù)不能太高，一般要求小于6。9/25/202364廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝層次分析法在管理中，人們常常需要對(duì)一些情況作出決策：例如企業(yè)的決策者要決定購(gòu)置哪種設(shè)備，上馬什么產(chǎn)品；經(jīng)理要從若干求職者中決定錄用哪些人員；地區(qū)、部門官員要對(duì)人口、交通、經(jīng)濟(jì)、環(huán)境等領(lǐng)域的發(fā)展規(guī)劃作出決策。在日常生活中也常會(huì)遇到，在多種類不同特征的商品中選購(gòu)。報(bào)考學(xué)校選擇志愿。畢業(yè)時(shí)選擇工作崗位等。9/25/202365廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝AHP法的特征：定性與定量相結(jié)合，把人們的思維過(guò)程層次化，數(shù)量化。運(yùn)用AHP法進(jìn)行決策時(shí)，可以分4個(gè)步驟：（1）分析系統(tǒng)中各個(gè)因素的關(guān)系，建立系統(tǒng)的遞階層次結(jié)構(gòu)；（2）對(duì)同一層次的各元素關(guān)于上一層次中某一準(zhǔn)則的重要性進(jìn)行兩兩比較，構(gòu)造兩兩比較判斷矩陣；（3）由判斷矩陣計(jì)算被比較元素對(duì)于該準(zhǔn)則的相對(duì)權(quán)重；（4）

計(jì)算各層元素對(duì)系統(tǒng)目標(biāo)的合成權(quán)重，并進(jìn)行排序。9/25/202366廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝建立層次分析的結(jié)構(gòu)模型用AHP分析問(wèn)題，首先要把問(wèn)題條理化、層次化，構(gòu)造層次分析的結(jié)構(gòu)模型。這些層次大體可分3類：1、最高層：在這一層次中只有一個(gè)元素，一般是分析問(wèn)題的預(yù)定目標(biāo)或理想結(jié)果，因此又稱目標(biāo)層；2、中間層：這一層次包括了為實(shí)現(xiàn)目標(biāo)所涉及的中間環(huán)節(jié)，它可由若干個(gè)層次組成，包括所需要考慮的準(zhǔn)則，子準(zhǔn)則，因此又稱為準(zhǔn)則層；3、最底層：表示為實(shí)現(xiàn)目標(biāo)可供選擇的各種措施、決策、方案等，因此又稱為措施層或方案層。9/25/202367廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝決策目標(biāo)準(zhǔn)則1方案1準(zhǔn)則m1準(zhǔn)則2子準(zhǔn)則1方案2子準(zhǔn)則2方案mr子準(zhǔn)則m2…………………方案層準(zhǔn)則層目標(biāo)層層次分析結(jié)構(gòu)圖9/25/202368廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝目標(biāo)層：準(zhǔn)則層：方案層：例1、某顧客選購(gòu)電冰箱時(shí)，對(duì)市場(chǎng)上正在出售的四種電冰箱考慮6項(xiàng)準(zhǔn)則作為評(píng)價(jià)依據(jù)，得到如下層次分析模型：9/25/202369廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝例2設(shè)某港務(wù)局要改善一條河道的過(guò)河運(yùn)輸條件，為此需要確定是否要建立橋梁或隧道以代替現(xiàn)有輪渡。此問(wèn)題中過(guò)河方式的確定取決于過(guò)河方式的效益與代價(jià)（即成本）。通常我們用費(fèi)效比（效益/代價(jià)）作為選擇方案的標(biāo)準(zhǔn)。為此構(gòu)造以下兩個(gè)層次分析的結(jié)構(gòu)模型。9/25/202370廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝準(zhǔn)則層過(guò)河的效益A經(jīng)濟(jì)效益B1社會(huì)效益B2環(huán)境效益B3橋梁D1隧道D2渡船D3收入

c2岸間商業(yè)

c3節(jié)省時(shí)間c1當(dāng)?shù)厣虡I(yè)c4建筑就業(yè)c5安全可靠c6交往溝通c7自豪感c8舒適c9進(jìn)出方便c10美化c11層次分析方案層目標(biāo)層9/25/202371廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝過(guò)河的代價(jià)A經(jīng)濟(jì)代價(jià)B1社會(huì)代價(jià)B2環(huán)境代價(jià)B3橋梁D1投入資金c1操作維護(hù)c2沖擊渡船業(yè)c3沖擊生活方式c4交通擁擠c5居民搬遷

c6汽車排廢物c7對(duì)水的污染c8對(duì)生態(tài)的破壞c9隧道D2渡船D3層次分析目標(biāo)層準(zhǔn)則層方案層9/25/202372廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝層次分析法的優(yōu)點(diǎn)

系統(tǒng)性——將對(duì)象視作系統(tǒng)，按照分解、比較、判斷、綜合的思維方式進(jìn)行決策——系統(tǒng)分析（與機(jī)理分析、測(cè)試分析并列）；

實(shí)用性——定性與定量相結(jié)合，能處理傳統(tǒng)的優(yōu)化方法不能解決的問(wèn)題；

簡(jiǎn)潔性——計(jì)算簡(jiǎn)便，結(jié)果明確，便于決策者直接了解和掌握。層次分析法的局限

囿舊——只能從原方案中選優(yōu)，不能產(chǎn)生新方案；

粗略——定性化為定量，結(jié)果粗糙；主觀——主觀因素作用大，結(jié)果可能難以服人。9/25/202373廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝多目標(biāo)規(guī)劃MOP(multi-objectiveprogramming)同時(shí)考慮多個(gè)決策目標(biāo)時(shí)，稱為多目標(biāo)規(guī)劃問(wèn)題。為了求得多目標(biāo)規(guī)劃問(wèn)題的非劣解，常常需要將多目標(biāo)規(guī)劃問(wèn)題轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題去處理。實(shí)現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法：效用最優(yōu)化模型罰款模型約束模型目標(biāo)達(dá)到法目標(biāo)規(guī)劃模型9/25/202374廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝求解多目標(biāo)規(guī)劃的方法一種是化多為少的方法，即把多目標(biāo)化為比較容易求解的單目標(biāo)或雙目標(biāo)，如主要目標(biāo)法、線性加權(quán)法、理想點(diǎn)法等；另一種叫分層序列法，即把目標(biāo)按其重要性會(huì)出一個(gè)序列，每次都在前一目標(biāo)最優(yōu)解集內(nèi)求下一個(gè)目標(biāo)最優(yōu)解，直到求出共同的最優(yōu)解。9/25/202375廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝線性加權(quán)和目標(biāo)規(guī)劃在上述目標(biāo)規(guī)劃中，假定f1(X),f2(X),…,fp(X)具有相同的量綱,按照一定的規(guī)則分別給fi賦予相同的權(quán)系數(shù)ωi，作線性加權(quán)和評(píng)價(jià)函數(shù)則多目標(biāo)問(wèn)題化為如下的單目標(biāo)問(wèn)題9/25/202376廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝分層序列法：1.基本步驟：把(VP)中的p個(gè)目標(biāo)按其重要程度排序。依次求單目標(biāo)規(guī)劃的最優(yōu)解。2.過(guò)程：無(wú)妨設(shè)其次序?yàn)橄惹蠼獾米顑?yōu)值，記再解得最優(yōu)值，依次進(jìn)行，直到得最優(yōu)值則是在分層序列意義下的最優(yōu)解集合。9/25/202377廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝目標(biāo)規(guī)劃問(wèn)題仍為例1，但企業(yè)的經(jīng)營(yíng)目標(biāo)不僅僅是利潤(rùn)，而是考慮多個(gè)方面，如：（1）力求使利潤(rùn)指標(biāo)不低于15元；（2）考慮到市場(chǎng)需求，?、П兩種產(chǎn)品的生產(chǎn)量需保持2:1的比例；（3）A為貴重設(shè)備，嚴(yán)格禁止超時(shí)使用；（4）設(shè)備C可以適當(dāng)加班，但要控制；（5）設(shè)備B既要充分利用，又盡可能不加班；（6）重要性上設(shè)備B是C的3倍。9/25/202378廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝具體做法：⒈設(shè)置偏差變量。用來(lái)表明實(shí)際值同目標(biāo)值之間的差異，偏差變量用下列符號(hào)表示：：超出目標(biāo)的差值，稱正偏差變量：未達(dá)到目標(biāo)的差值，稱負(fù)偏差變量與有下面幾種取值情況：9/25/202379廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝⒉統(tǒng)一處理目標(biāo)和約束。只對(duì)資源使用上有嚴(yán)格限制的建立系統(tǒng)約束，數(shù)學(xué)形式上為嚴(yán)格的等式或不等式，同線性規(guī)劃中的約束條件。因正負(fù)偏差不可能同時(shí)出現(xiàn)，故總有若要求：?的2倍產(chǎn)量不低于П的產(chǎn)量，即不希望上式中，用目標(biāo)約束可表示為：9/25/202380廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝若要求：?的2倍產(chǎn)量低于П的產(chǎn)量，即不希望上式中，用目標(biāo)約束可表示為：若要求：?的2倍產(chǎn)量恰好等于П的產(chǎn)量，即不希望上式中，又不希望出現(xiàn)用目標(biāo)約束可表示為：9/25/202381廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝⒊目標(biāo)的優(yōu)先級(jí)與權(quán)系數(shù)。權(quán)系數(shù)：在一個(gè)目標(biāo)規(guī)劃的模型中，如果兩個(gè)不同目標(biāo)重要程度相差懸殊，為達(dá)到某一目標(biāo)可犧牲其他一些目標(biāo)，稱這些目標(biāo)是屬于不同層次的優(yōu)先級(jí)。權(quán)系數(shù)：對(duì)屬于同一層次優(yōu)先級(jí)的不同目標(biāo)，按其重要程度可分別乘上不同的系數(shù)，這個(gè)系數(shù)稱為權(quán)系數(shù)。9/25/202382廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝建立模型目標(biāo)函數(shù)：約束條件：9/25/202383廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝一般模型s.t.9/25/202384廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝求解方法圖解法單純形法層次算法9/25/202385廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝數(shù)學(xué)規(guī)劃模型的一般形式：非線性規(guī)劃模型9/25/202386廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝無(wú)約束一維搜索方法t為實(shí)數(shù)一維搜索問(wèn)題指目標(biāo)函數(shù)為單變量的非線性規(guī)劃問(wèn)題。又稱線性搜索問(wèn)題。其模型為：什么叫一維搜索問(wèn)題？或一般一維搜索問(wèn)題有效一維搜索問(wèn)題9/25/202387廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝一維搜索問(wèn)題的算法分類：

精確一維搜索（最優(yōu)一維搜索）

非精確一維搜索（可接受一維搜索）具體方法：

兩種精確一維搜索方法：0.618法（近似黃金分割法），Newton法。

兩種非精確一維搜索方法：Goldstein法,Armijo法。9/25/202388廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝無(wú)約束最優(yōu)化方法n元函數(shù)的無(wú)約束非線性規(guī)劃問(wèn)題：求解此類模型(UMP)的方法稱為無(wú)約束最優(yōu)化方法。無(wú)約束最優(yōu)化方法通常有兩類：解析法：要使用導(dǎo)數(shù)的方法；直接法：無(wú)須考慮函數(shù)是否可導(dǎo)，直接使用函數(shù)值。方法：最速下降法或梯度法（一種解析法）9/25/202389廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝約束最優(yōu)化方法約束非線性規(guī)劃問(wèn)題MP其中,x=(x1,x2,…

xn)T，f(x),gi(x),hj(x)為x的實(shí)值函數(shù)求解此類模型(MP)的方法稱為約束最優(yōu)化方法。具體方法

懲罰函數(shù)法：罰函數(shù)法（外部懲罰法），障礙函數(shù)法（內(nèi)部懲罰法）9/25/202390廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝能用最簡(jiǎn)淺的數(shù)學(xué)方法解決別人用高深理論才能解決的答卷是更優(yōu)秀的答卷

目錄9/25/202391廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝應(yīng)用實(shí)例：供應(yīng)與選址

某公司有6個(gè)建筑工地要開(kāi)工，每個(gè)工地的位置（用平面坐標(biāo)系a，b表示，距離單位：千米）及水泥日用量d(噸)由下表給出。目前有兩個(gè)臨時(shí)料場(chǎng)位于A(5,1)，B(2,7)，日儲(chǔ)量各有20噸。假設(shè)從料場(chǎng)到工地之間均有直線道路相連。（1）試制定每天的供應(yīng)計(jì)劃，即從A，B兩料場(chǎng)分別向各工地運(yùn)送多少噸水泥，使總的噸千米數(shù)最小。（2）為了進(jìn)一步減少噸千米數(shù)，打算舍棄兩個(gè)臨時(shí)料場(chǎng)，改建兩個(gè)新的，日儲(chǔ)量各為20噸，問(wèn)應(yīng)建在何處，節(jié)省的噸千米數(shù)有多大？9/25/202392廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝（一）、建立模型

記工地的位置為(ai，bi)，水泥日用量為di，i=1,…,6;料場(chǎng)位置為(xj，yj)，日儲(chǔ)量為ej，j=1,2；從料場(chǎng)j向工地i的運(yùn)送量為Xij。當(dāng)用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，當(dāng)不用臨時(shí)料場(chǎng)時(shí)決策變量為：Xij，xj，yj。9/25/202393廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝（二）使用臨時(shí)料場(chǎng)的情形

使用兩個(gè)臨時(shí)料場(chǎng)A(5,1)，B(2,7).求從料場(chǎng)j向工地i的運(yùn)送量為Xij，在各工地用量必須滿足和各料場(chǎng)運(yùn)送量不超過(guò)日儲(chǔ)量的條件下，使總的噸千米數(shù)最小，這是線性規(guī)劃問(wèn)題.線性規(guī)劃模型為：設(shè)X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X

129/25/202394廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝計(jì)算結(jié)果為：x=[3.00005.00000.00007.00000.00001.00000.00000.00004.00000.00006.000010.0000]’fval=136.22759/25/202395廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝（三）改建兩個(gè)新料場(chǎng)的情形

改建兩個(gè)新料場(chǎng),要同時(shí)確定料場(chǎng)的位置(xj,yj)和運(yùn)送量Xij，在同樣條件下使總噸千米數(shù)最小.這是非線性規(guī)劃問(wèn)題。非線性規(guī)劃模型為：9/25/202396廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝設(shè)X11=X1,X21=X2,,X31=X3,X41=X4,X51=X5,,X61=X6X12=X7,X22=X8,,X32=X9,X42=X10,X52=X11,,X62=X12

x1=X13,y1=X14,x2=X15,y2=X16

（1）先編寫M文件liaoch.m定義目標(biāo)函數(shù)。(2)取初值為線性規(guī)劃的計(jì)算結(jié)果及臨時(shí)料場(chǎng)的坐標(biāo):x0=[35070100406105127]';編寫主程序gying2.m.9/25/202397廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝(3)計(jì)算結(jié)果為：x=[3.00005.00000.07077.000000.9293003.929306.000010.07076.38754.39435.75117.1867]’fval=105.4626exitflag=19/25/202398廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝(4)若修改主程序gying2.m,取初值為上面的計(jì)算結(jié)果:x0=[3.00005.00000.07077.000000.9293003.929306.000010.07076.38754.39435.75117.1867]’得結(jié)果為:x=[3.00005.00000.30947.00000.01080.6798003.690605.989210.32025.53694.91945.82917.2852]’fval=103.4760exitflag=1總的噸千米數(shù)比上面結(jié)果略優(yōu).(5)若再取剛得出的結(jié)果為初值,卻計(jì)算不出最優(yōu)解.9/25/202399廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝(6)若取初值為:x0=[35471000005115.63484.86877.24797.7499]',則計(jì)算結(jié)果為:x=[3.00005.00004.00007.00001.0000000005.000011.00005.69594.92857.25007.7500]’fval=89.8835exitflag=1總的噸千米數(shù)89.8835比上面結(jié)果更好.通過(guò)此例可看出fmincon函數(shù)在選取初值上的重要性.9/25/2023100廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝鋼管訂購(gòu)及運(yùn)輸優(yōu)化模型2000年“網(wǎng)易杯”全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題9/25/2023101廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝符號(hào)說(shuō)明：9/25/2023102廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝1、鋪設(shè)總費(fèi)用：2、成本及運(yùn)輸總費(fèi)用：總費(fèi)用=鋪設(shè)總費(fèi)用+成本及運(yùn)輸總費(fèi)用=C+W模型的分析與建立9/25/2023103廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝建立模型9/25/2023104廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝模型求解利用MATLAB軟件包求解得：9/25/2023105廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝訂購(gòu)和運(yùn)輸方案表9/25/2023106廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝建模實(shí)例與求解下料問(wèn)題露天礦的運(yùn)輸問(wèn)題（2003年B題）鋼管運(yùn)輸問(wèn)題（2000年B題）飛行管理問(wèn)題（1995年A題）9/25/2023107廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝問(wèn)題1.如何下料最節(jié)省?例

鋼管下料問(wèn)題2.客戶增加需求：原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多，會(huì)增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過(guò)3種。如何下料最節(jié)??？5米10根9/25/2023108廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝按照客戶需要在一根原料鋼管上安排切割的一種組合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根鋼管下料9/25/2023109廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)省？合理切割模式2.所用原料鋼管總根數(shù)最少模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問(wèn)題1兩種標(biāo)準(zhǔn)1.原料鋼管剩余總余量最小9/25/2023110廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)約束滿足需求決策變量

目標(biāo)1（總余量）按模式2切割12根,按模式5切割15根，余料27米

模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015最優(yōu)解：x2=12,x5=15,

其余為0；最優(yōu)值：27整數(shù)約束：xi為整數(shù)9/25/2023111廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）鋼管下料問(wèn)題1約束條件不變最優(yōu)解：x2=15,x5=5,x7=5,其余為0；最優(yōu)值：25。xi為整數(shù)按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米雖余料增加8米，但減少了2根與目標(biāo)1的結(jié)果“共切割27根，余料27米”相比9/25/2023112廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝鋼管下料問(wèn)題2對(duì)大規(guī)模問(wèn)題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過(guò)3種?，F(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過(guò)于復(fù)雜。決策變量

xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,3)r1i,r2i,r3i,r4i~第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長(zhǎng)的鋼管的數(shù)量9/25/2023113廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝滿足需求模式合理：每根余料不超過(guò)3米整數(shù)非線性規(guī)劃模型鋼管下料問(wèn)題2目標(biāo)函數(shù)（總根數(shù)）約束條件整數(shù)約束：xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數(shù)9/25/2023114廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界：

特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：31模式排列順序可任定

鋼管下料問(wèn)題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長(zhǎng)19米9/25/2023115廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝LINGO求解整數(shù)非線性規(guī)劃模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數(shù)為28根。9/25/2023116廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝板材規(guī)格2：長(zhǎng)方形，32

28cm，2萬(wàn)張。易拉罐下料每周工作40小時(shí)，每只易拉罐利潤(rùn)0.10元，原料余料損失0.001元/cm2（不能裝配的罐身、蓋、底也是余料）模式1：1.5秒模式2：2秒模式3：1秒模式4：3秒上蓋下底罐身罐身高10cm，上蓋、下底直徑均5cm。

板材規(guī)格1：正方形，邊長(zhǎng)24cm，5萬(wàn)張。如何安排每周生產(chǎn)？

9/25/2023117廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝

罐身個(gè)數(shù)底、蓋個(gè)數(shù)余料損失（cm2）沖壓時(shí)間（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53模式1:正方形邊長(zhǎng)24cm問(wèn)題分析計(jì)算各種模式下的余料損失上、下底直徑d=5cm，罐身高h(yuǎn)=10cm。模式1余料損失242-10

d2/4-dh=222.6cm29/25/2023118廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝問(wèn)題分析目標(biāo):易拉罐利潤(rùn)扣除原料余料損失后的凈利潤(rùn)最大

約束：每周工作時(shí)間不超過(guò)40小時(shí)；原料數(shù)量：規(guī)格1（模式1~3）5萬(wàn)張，規(guī)格2（模式4）2萬(wàn)張；罐身和底、蓋的配套組裝。注意：不能裝配的罐身、上下底也是余料決策變量

xi~按照第i種模式的生產(chǎn)張數(shù)(i=1,2,3,4)；y1~一周生產(chǎn)的易拉罐個(gè)數(shù)；y2~不配套的罐身個(gè)數(shù)；y3~不配套的底、蓋個(gè)數(shù)。模型建立9/25/2023119廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝目標(biāo)

約束條件

時(shí)間約束原料約束產(chǎn)量余料時(shí)間x1222.61.5x2183.32x3261.81x4169.53模型建立y1~易拉罐個(gè)數(shù)；y2~不配套的罐身；y3~不配套的底、蓋。每只易拉罐利潤(rùn)0.10元，余料損失0.001元/cm2罐身面積

dh=157.1cm2

底蓋面積

d2/4=19.6cm2(40小時(shí))9/25/2023120廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝約束條件

配套約束y1~易拉罐個(gè)數(shù)；y2~不配套的罐身；y3~不配套的底、蓋。罐身底、蓋1102401645產(chǎn)量x1x2x3x4雖然xi和y1，y2，y3應(yīng)是整數(shù)，但是因生產(chǎn)量很大，可以把它們看成實(shí)數(shù)，從而用線性規(guī)劃模型處理。9/25/2023121廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝將所有決策變量擴(kuò)大10000倍（xi~萬(wàn)張，yi

~萬(wàn)件）

LINDO發(fā)出警告信息：“數(shù)據(jù)之間的數(shù)量級(jí)差別太大，建議進(jìn)行預(yù)處理，縮小數(shù)據(jù)之間的差別”模式2生產(chǎn)40125張，模式3生產(chǎn)3750張，模式4生產(chǎn)20000張，共產(chǎn)易拉罐160250個(gè)(罐身和底、蓋無(wú)剩余)，凈利潤(rùn)為4298元

模型求解

OBJECTIVEFUNCTIONVALUE1)0.4298337VARIABLEVALUEREDUCEDCOSTY116.0250000.000000X10.0000000.000050X24.0125000.000000X30.3750000.000000X42.0000000.000000Y20.0000000.223331Y30.0000000.0364849/25/2023122廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝下料問(wèn)題的建模確定下料模式構(gòu)造優(yōu)化模型規(guī)格不太多，可枚舉下料模式，建立整數(shù)線性規(guī)劃模型，否則要構(gòu)造整數(shù)非線性規(guī)劃模型，求解困難，可用縮小可行域的方法進(jìn)行化簡(jiǎn)，但要保證最優(yōu)解的存在。一維問(wèn)題（如鋼管下料）二維問(wèn)題（如易拉罐下料）具體問(wèn)題具體分析（比較復(fù)雜）9/25/2023123廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝露天礦里鏟位已分成礦石和巖石:平均鐵含量不低于25%的為礦石，否則為巖石。每個(gè)鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個(gè)鏟位至多安置一臺(tái)電鏟，電鏟平均裝車時(shí)間5分鐘卡車在等待時(shí)所耗費(fèi)的能量也是相當(dāng)可觀的，原則上在安排時(shí)不應(yīng)發(fā)生卡車等待的情況。露天礦生產(chǎn)的車輛安排(CUMCM-2003B)

礦石卸點(diǎn)需要的鐵含量要求都為29.5%

1%(品位限制），搭配量在一個(gè)班次（8小時(shí)）內(nèi)滿足品位限制即可。卸點(diǎn)在一個(gè)班次內(nèi)不變?？ㄜ囕d重量為154噸，平均時(shí)速28km,平均卸車時(shí)間為3分鐘。問(wèn)題：出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；出動(dòng)幾輛卡車，分別在哪些路線上各運(yùn)輸多少次?9/25/2023124廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝平面示意圖9/25/2023125廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝問(wèn)題數(shù)據(jù)距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝Ⅰ1.900.991.901.131.272.251.482.043.093.51巖場(chǎng)5.895.615.614.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝Ⅱ4.423.863.723.162.252.810.781.621.270.50鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量0．951．051．001．051．101．251．051．301．351．25巖石量1．251．101．351．051．151．351．051．151．351．25鐵含量30%28%29%32%31%33%32%31%33%31%9/25/2023126廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝問(wèn)題分析與典型的運(yùn)輸問(wèn)題明顯有以下不同：這是運(yùn)輸?shù)V石與巖石兩種物資的問(wèn)題；屬于產(chǎn)量大于銷量的不平衡運(yùn)輸問(wèn)題；為了完成品位約束，礦石要搭配運(yùn)輸；產(chǎn)地、銷地均有單位時(shí)間的流量限制；運(yùn)輸車輛只有一種，每次滿載運(yùn)輸，154噸/車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個(gè)產(chǎn)地作為最后結(jié)果中的產(chǎn)地；最后求出各條路線上的派出車輛數(shù)及安排。近似處理：先求出產(chǎn)位、卸點(diǎn)每條線路上的運(yùn)輸量(MIP模型)然后求出各條路線上的派出車輛數(shù)及安排9/25/2023127廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝模型假設(shè)卡車在一個(gè)班次中不應(yīng)發(fā)生等待或熄火后再啟動(dòng)的情況；在鏟位或卸點(diǎn)處由兩條路線以上造成的沖突問(wèn)題面前，我們認(rèn)為只要平均時(shí)間能完成任務(wù)，就認(rèn)為不沖突。我們不排時(shí)地進(jìn)行討論；空載與重載的速度都是28km/h，耗油相差很大；卡車可提前退出系統(tǒng)，等等。如理解為嚴(yán)格不等待，難以用數(shù)學(xué)規(guī)劃模型來(lái)解個(gè)別參數(shù)隊(duì)找到了可行解（略）9/25/2023128廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝符號(hào)xij

：從i鏟位到j(luò)號(hào)卸點(diǎn)的石料運(yùn)量（車）單位：噸；cij

：從i號(hào)鏟位到j(luò)號(hào)卸點(diǎn)的距離公里；Tij:從i號(hào)鏟位到號(hào)j卸點(diǎn)路線上運(yùn)行一個(gè)周期平均時(shí)間分；Aij

：從號(hào)鏟位到號(hào)卸點(diǎn)最多能同時(shí)運(yùn)行的卡車數(shù)輛；Bij

：從號(hào)鏟位到號(hào)卸點(diǎn)路線上一輛車最多可運(yùn)行的次數(shù)次；pi：i號(hào)鏟位的礦石鐵含量p=(30,28,29,32,31,33,32,31,33,31)%qj:j號(hào)卸點(diǎn)任務(wù)需求，q=(1.2,1.3,1.3,1.9,1.3)*10000噸cki

：i號(hào)鏟位的鐵礦石儲(chǔ)量萬(wàn)噸cyi

：i號(hào)鏟位的巖石儲(chǔ)量萬(wàn)噸fi:描述第i號(hào)鏟位是否使用的0-1變量，取1為使用；0為關(guān)閉。(近似)9/25/2023129廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝優(yōu)化模型（1）道路能力(卡車數(shù))約束（2）電鏟能力約束（3）卸點(diǎn)能力約束（4）鏟位儲(chǔ)量約束（5）產(chǎn)量任務(wù)約束（6）鐵含量約束（7）電鏟數(shù)量約束（8）整數(shù)約束

.xij為非負(fù)整數(shù)fi

為0-1整數(shù)9/25/2023130廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝計(jì)算結(jié)果（LINGO軟件）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦漏135411倒Ⅰ4243巖場(chǎng)7015巖漏8143倒Ⅱ13270鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏0.8671.8620.314倒場(chǎng)Ⅰ1.0771.162巖場(chǎng)1.8920.326巖石漏1.8411.229倒場(chǎng)Ⅱ0.6840.11.4899/25/2023131廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝計(jì)算結(jié)果（派車）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏1(29)倒場(chǎng)Ⅰ1(39)1(37)巖場(chǎng)1(37)巖石漏1(44)1(35)倒場(chǎng)Ⅱ1(47)結(jié)論：鏟位1、2、3、4、8、9、10處各放置一臺(tái)電鏟。一共使用了13輛卡車；總運(yùn)量為85628.62噸公里；巖石產(chǎn)量為32186噸；礦石產(chǎn)量為38192噸。此外：6輛聯(lián)合派車（方案略）9/25/2023132廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝最大化產(chǎn)量結(jié)論：（略）目標(biāo)函數(shù)變化此外：車輛數(shù)量（20輛）限制（其實(shí)上面的模型也應(yīng)該有）9/25/2023133廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7鐵路運(yùn)價(jià)表里程≤300301～350351～400401～450451～500…運(yùn)價(jià)2023262932…

鋼管運(yùn)輸問(wèn)題（CUMCM-2000B)9/25/2023134廣東技術(shù)師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院付輝常用解法:二次規(guī)劃先計(jì)算