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

數(shù)學(xué)建模組合優(yōu)化模型第一頁(yè)，共五十二頁(yè)，2022年，8月28日優(yōu)化問(wèn)題建模優(yōu)化問(wèn)題概述數(shù)學(xué)規(guī)劃模型組合優(yōu)化模型優(yōu)化算法介紹評(píng)價(jià)方法第二頁(yè)，共五十二頁(yè)，2022年，8月28日優(yōu)化問(wèn)題建模組合優(yōu)化問(wèn)題概述網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)流量安排問(wèn)題路線選擇問(wèn)題第三頁(yè)，共五十二頁(yè)，2022年，8月28日組合優(yōu)化問(wèn)題概述組合優(yōu)化問(wèn)題常見(jiàn)的組合優(yōu)化問(wèn)題組合優(yōu)化問(wèn)題建模步驟第四頁(yè)，共五十二頁(yè)，2022年，8月28日組合優(yōu)化問(wèn)題有限個(gè)可行方案中選擇最優(yōu)方案最優(yōu)解一定存在可行方案的個(gè)數(shù)非常多，枚舉法不可行，往往是NP-hard問(wèn)題第五頁(yè)，共五十二頁(yè)，2022年，8月28日組合優(yōu)化問(wèn)題組合計(jì)數(shù)問(wèn)題最小費(fèi)用最大流問(wèn)題最短路問(wèn)題網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題最優(yōu)匹配問(wèn)題裝箱問(wèn)題旅游售貨員問(wèn)題車輛路徑問(wèn)題第六頁(yè)，共五十二頁(yè)，2022年，8月28日網(wǎng)絡(luò)設(shè)計(jì)常見(jiàn)網(wǎng)絡(luò)設(shè)計(jì)管線網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、關(guān)系網(wǎng)絡(luò)等設(shè)計(jì)內(nèi)容設(shè)置多少點(diǎn)？設(shè)在什么地方？--選址問(wèn)題點(diǎn)之間如何鏈接？--網(wǎng)路優(yōu)化設(shè)計(jì)要求實(shí)現(xiàn)基本功能成本最小第七頁(yè)，共五十二頁(yè)，2022年，8月28日網(wǎng)絡(luò)連接方式最少用多少邊可把下列點(diǎn)連起來(lái)？第八頁(yè)，共五十二頁(yè)，2022年，8月28日網(wǎng)絡(luò)連接方式聯(lián)通不含回路第九頁(yè)，共五十二頁(yè)，2022年，8月28日第十頁(yè)，共五十二頁(yè)，2022年，8月28日最小支撐樹(shù)第十一頁(yè)，共五十二頁(yè)，2022年，8月28日算法步驟

第十二頁(yè)，共五十二頁(yè)，2022年，8月28日算例

1452312432214第十三頁(yè)，共五十二頁(yè)，2022年，8月28日迭代過(guò)程

1452312432214145231243221414523124322141452312432214第十四頁(yè)，共五十二頁(yè)，2022年，8月28日流量安排問(wèn)題最大流問(wèn)題最小費(fèi)用流問(wèn)題運(yùn)輸問(wèn)題第十五頁(yè)，共五十二頁(yè)，2022年，8月28日最大流問(wèn)題1234565233242617第十六頁(yè)，共五十二頁(yè)，2022年，8月28日第十七頁(yè)，共五十二頁(yè)，2022年，8月28日數(shù)學(xué)規(guī)劃模型第十八頁(yè)，共五十二頁(yè)，2022年，8月28日算法步驟

第十九頁(yè)，共五十二頁(yè)，2022年，8月28日第二十頁(yè)，共五十二頁(yè)，2022年，8月28日算例

1234565233242617第二十一頁(yè)，共五十二頁(yè)，2022年，8月28日迭代過(guò)程

1234565,22,23,23,22,2426,21712345632,2112,2426,217-∞+1,3+2,1+1,1第二十二頁(yè)，共五十二頁(yè)，2022年，8月28日第二十三頁(yè)，共五十二頁(yè)，2022年，8月28日結(jié)果第二十四頁(yè)，共五十二頁(yè)，2022年，8月28日最小費(fèi)用流問(wèn)題stdcba2,32,13,21,33,11,24,25,21,2第二十五頁(yè)，共五十二頁(yè)，2022年，8月28日stdcba2,32,13,21,33,11,24,25,21,2stdcba2,32,13,21,33,11,24,25,21,22222222223211V=4，費(fèi)用為32V=4，費(fèi)用為25第二十六頁(yè)，共五十二頁(yè)，2022年，8月28日線性規(guī)劃形式第二十七頁(yè)，共五十二頁(yè)，2022年，8月28日Scilab實(shí)現(xiàn)用Scilab語(yǔ)言求解以上算例所示網(wǎng)絡(luò)的最小費(fèi)用流Scilab語(yǔ)句：cleartail=[11223];head=[23344];

g=make_graph('g',1,4,tail,head);

cost=[13131];

max_cap=[21242];第二十八頁(yè)，共五十二頁(yè)，2022年，8月28日續(xù)g('edge_cost')=cost;

g('edge_max_cap')=max_cap;

demd=[-3,0,0,3];

g('node_demand')=demd;

[c,phi,flag]=min_lcost_flow2(g)第二十九頁(yè)，共五十二頁(yè)，2022年，8月28日結(jié)果flag=

1.phi=

!2.1.1.1.2.!c=

11.第三十頁(yè)，共五十二頁(yè)，2022年，8月28日運(yùn)輸問(wèn)題運(yùn)出地(n個(gè))運(yùn)入地(m個(gè))可運(yùn)出量需運(yùn)入量單位運(yùn)量的運(yùn)輸費(fèi)用第三十一頁(yè)，共五十二頁(yè)，2022年，8月28日運(yùn)輸方案確定每個(gè)運(yùn)出地向個(gè)運(yùn)入地運(yùn)輸貨物的數(shù)量，要求滿足：1、運(yùn)出貨物總量不得超過(guò)可運(yùn)貨物總量；2、運(yùn)入貨物總量不得低于需運(yùn)貨物總量；3、運(yùn)輸總費(fèi)用最小第三十二頁(yè)，共五十二頁(yè)，2022年，8月28日線性規(guī)劃模型第三十三頁(yè)，共五十二頁(yè)，2022年，8月28日對(duì)偶規(guī)劃網(wǎng)絡(luò)分析第三十四頁(yè)，共五十二頁(yè)，2022年，8月28日算法步驟運(yùn)籌學(xué)課件網(wǎng)絡(luò)分析第三十五頁(yè)，共五十二頁(yè)，2022年，8月28日算例

運(yùn)籌學(xué)課件網(wǎng)絡(luò)分析求如圖所示運(yùn)輸問(wèn)題的最優(yōu)解1231234-45-20-30-30355040

8

699912137149165第三十六頁(yè)，共五十二頁(yè)，2022年，8月28日模型第三十七頁(yè)，共五十二頁(yè)，2022年，8月28日計(jì)算model:min=8*x11+6*x12+9*x13+9*x14+9*x21+12*x22+13*x23+7*x24+14*x31+9*x32+16*x33+5*x34;x11+x12+x13+x14<=35;x21+x22+x23+x24<=50;x31+x32+x33+x34<=40;x11+x21+x31>=45;x12+x22+x32>=20;x13+x23+x33>=30;x14+x24+x34>=30;end第三十八頁(yè)，共五十二頁(yè)，2022年，8月28日路線選擇問(wèn)題最短路問(wèn)題—兩點(diǎn)之間路線選擇旅游售貨員問(wèn)題—環(huán)線選擇車輛路徑問(wèn)題—多個(gè)環(huán)線選擇第三十九頁(yè)，共五十二頁(yè)，2022年，8月28日最短有向路問(wèn)題12345652332426179第四十頁(yè)，共五十二頁(yè)，2022年，8月28日數(shù)學(xué)規(guī)劃模型第四十一頁(yè)，共五十二頁(yè)，2022年，8月28日算法步驟

第四十二頁(yè)，共五十二頁(yè)，2022年，8月28日算例

12345652332426179第四十三頁(yè)，共五十二頁(yè)，2022年，8月28日計(jì)算的迭代過(guò)程

123456523324261705∞9∞312345652332426170510953991234565233242617056953912345652332426170568539第四十四頁(yè)，共五十二頁(yè)，2022年，8月28日12345652332426170568539第四十五頁(yè)，共五十二頁(yè)，2022年，8月28日旅游售貨員問(wèn)題旅行售貨員問(wèn)題是圖論中一個(gè)著名問(wèn)題，就是在網(wǎng)絡(luò)N上找一條從v0點(diǎn)出發(fā)，經(jīng)過(guò)v1,v2,…,vn各一次最后返回v0的最短路線和最短路程。第四十六頁(yè)，共五十二頁(yè)，2022年，8月28日動(dòng)態(tài)規(guī)劃方法現(xiàn)把它看成一個(gè)多階段決策問(wèn)題。從v0出發(fā)，經(jīng)過(guò)n個(gè)階段，每個(gè)階段的決策是選擇下一個(gè)點(diǎn)。如果用所在的位置來(lái)表示狀態(tài)，那么狀態(tài)與階段數(shù)就不能完全決定決策集合了，因?yàn)樽哌^(guò)的點(diǎn)不需要再走，所以決策集合與以前選的決策有關(guān)。用（vi,V）表示狀態(tài)，vi是所處的點(diǎn)，V是還沒(méi)有經(jīng)過(guò)的點(diǎn)集合。在狀態(tài)（vi,V）的決策集合中，取決策vjV，獲得的效益是vi到vj的距離dij，轉(zhuǎn)入下一個(gè)狀態(tài)（vj,V\{vj}），現(xiàn)在用最優(yōu)化原理來(lái)找遞推公式。第四十七頁(yè)，共五十二頁(yè)，2022年，8月28日續(xù)(1)用fk(vi,V)表示從vi點(diǎn)出發(fā)，經(jīng)過(guò)V中的點(diǎn)各一次，最后回到v0點(diǎn)的最短路程，V是一個(gè)頂點(diǎn)集合，|V|=k，dij是vi到vj的弧長(zhǎng)，則第四十八頁(yè)，共五十二頁(yè)，2022年，8月28日問(wèn)題描述車輛路徑問(wèn)題是指一定數(shù)量的顧客，各自有不同數(shù)量的貨物需求，配送中心向顧客提供貨物，由一個(gè)車隊(duì)負(fù)責(zé)分送貨