運(yùn)籌學(xué)暑期培訓(xùn)什么是最優(yōu)化？西北大學(xué)數(shù)學(xué)系決策變量目標(biāo)函數(shù)約束條件西北大學(xué)數(shù)學(xué)系優(yōu)化問題是工程技術(shù)、經(jīng)濟(jì)管理、科學(xué)研究等領(lǐng)域最常遇到的一類問題。它研究在有限或無限種可行方案中挑選最優(yōu)方案，構(gòu)造尋求最優(yōu)解的計(jì)算方法。

到達(dá)最優(yōu)目標(biāo)的方案，稱為最優(yōu)方案，搜索最優(yōu)方案的方法，稱為最優(yōu)化方法。建立的尋求最優(yōu)的數(shù)學(xué)表達(dá)式，稱為最優(yōu)化模型。西北大學(xué)數(shù)學(xué)系一、優(yōu)化問題的根本形式及分類形式：分類：〔1〕約束優(yōu)化和無約束優(yōu)化；〔2〕線性規(guī)劃、非線性規(guī)劃、二次規(guī)劃等。解法：枚舉法，搜索法，啟發(fā)式算法。西北大學(xué)數(shù)學(xué)系二、線性規(guī)劃及求解標(biāo)準(zhǔn)型：其它形式化為標(biāo)準(zhǔn)型的方法：解法：?jiǎn)渭冃畏ǎ瑢?duì)偶單純形法，兩階段法等。西北大學(xué)數(shù)學(xué)系Matlab中的標(biāo)準(zhǔn)型：或求解命令：x=linprog(c,A,b)%返回的值x就是優(yōu)化問題的最優(yōu)解。西北大學(xué)數(shù)學(xué)系化標(biāo)準(zhǔn)型的方法：目標(biāo)函數(shù)：max--------min只需令：那么目標(biāo)變?yōu)椋杭s束條件：：不等式兩端同乘-1“=〞:利用兩個(gè)不同方向的不等式約束代替變量范圍約束：每一個(gè)變量的范圍約束看作獨(dú)立的約束條件西北大學(xué)數(shù)學(xué)系例：s.t.標(biāo)準(zhǔn)型：從而x=linprog(c,A,b)執(zhí)行命令：西北大學(xué)數(shù)學(xué)系其它命令：[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB)說明：該命令可將不等式約束與等式約束以及變量的范圍限制分別輸入。A,b:不等式約束的系數(shù)矩陣和右端項(xiàng)；Aeq,beq：等式約束的系數(shù)矩陣和右端項(xiàng)；LB,UB：變量的范圍限制；x,fval：分別返回最優(yōu)解和最優(yōu)值。注意：linprog()還有其它形式的用法，具體可在Matlab指令窗運(yùn)行helplinprog，就能看到所有的函數(shù)調(diào)用形式。西北大學(xué)數(shù)學(xué)系例：利用上述方法處理后，可令

，，執(zhí)行命令：[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB)西北大學(xué)數(shù)學(xué)系三、整數(shù)規(guī)劃及求解規(guī)劃中的變量〔局部或全部〕限制為整數(shù)時(shí)，稱為整數(shù)規(guī)劃。分類：整數(shù)規(guī)劃混合整數(shù)規(guī)劃0-1整數(shù)規(guī)劃西北大學(xué)數(shù)學(xué)系理論解法：整數(shù)規(guī)劃和混合整數(shù)規(guī)劃：分枝定界法割平面法0-1整數(shù)規(guī)劃：完全枚舉法，隱枚舉法

指派問題：匈牙利算法所有整數(shù)規(guī)劃問題：蒙特卡洛算法

軟件求解：

①針對(duì)理論解法編程求解；

②某些特殊問題可用Matlab命令求解；

③主要采用Lingo編程求解西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系Lingo程序：設(shè)n=8，c，a，B應(yīng)給出具體值。Max=c1*x1+c2*x2+c3*x3+c4*x4+c5*x5+c6*x6+c7*x7+c8*x8;-1*x1+x2>=0;x3+x4>=1;x5+x6+x7=2;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);bin(x7);bin(x8);西北大學(xué)數(shù)學(xué)系四、非線性規(guī)劃及求解西北大學(xué)數(shù)學(xué)系定義：目標(biāo)函數(shù)或約束條件中至少有一個(gè)非線性函數(shù)，這類問題稱之為非線性規(guī)劃問題，簡(jiǎn)記為〔NP〕。分類：約束優(yōu)化和無約束優(yōu)化

西北大學(xué)數(shù)學(xué)系理論解法：無約束優(yōu)化：梯度法，牛頓法，共軛方向法等；約束優(yōu)化：障礙函數(shù)法，懲罰函數(shù)法等。軟件求解：①針對(duì)理論解法編程求解；②Matlab命令求解；③Lingo編程求解。西北大學(xué)數(shù)學(xué)系x=fmincon(fun,x0,A,B,Aeq,Beq,lb,ub,nonlcon,options)西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系無約束優(yōu)化問題的Matlab求解標(biāo)準(zhǔn)形式：命令：[X,FVAL]=fminbnd(fun,x1,x2,options)標(biāo)準(zhǔn)形式：命令：[X,FVAL]=fminunc(fun,x0,options)西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系二次規(guī)劃標(biāo)準(zhǔn)型：Matlab命令：

[X,FVAL]=quadprog(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)西北大學(xué)數(shù)學(xué)系五、多目標(biāo)規(guī)劃及求解西北大學(xué)數(shù)學(xué)系多目標(biāo)的處理：決策值和目標(biāo)值：決策變量的值給定后，上面每一個(gè)不等式左端的值稱為決策值，右端的數(shù)稱為標(biāo)值。正負(fù)偏差量：決策值和目標(biāo)值之間的差異。注意：引入偏差量的目的是可將目標(biāo)函數(shù)借助于偏差量表示為等式。

西北大學(xué)數(shù)學(xué)系數(shù)學(xué)模型：解法：〔1〕利用針對(duì)多目標(biāo)規(guī)劃的單純形法求解，這種情況下甚至不需要給出p的值；〔2〕將p的值給定，直接利用線性規(guī)劃方法求解。西北大學(xué)數(shù)學(xué)系賽題選講西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系圖論模型災(zāi)情巡視路線西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系問題分析題目給出了某縣的公路網(wǎng)絡(luò)圖，要求在不同條件下設(shè)計(jì)出最優(yōu)的災(zāi)情巡視路線。將每個(gè)鄉(xiāng)(鎮(zhèn))或村看作一個(gè)圖的頂點(diǎn)，各鄉(xiāng)鎮(zhèn)、村之間的公路看作對(duì)應(yīng)頂點(diǎn)的邊，各條公路的長(zhǎng)度(或行駛時(shí)間)看作對(duì)應(yīng)邊上的權(quán)，使得公路網(wǎng)絡(luò)圖轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題轉(zhuǎn)化為圖論中的分組旅行員推銷問題(TSP)，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)O出發(fā)，行遍所有頂點(diǎn)至少一次后又回到點(diǎn)O，使得總權(quán)最小。由于圖中各點(diǎn)之間的連接關(guān)系比較復(fù)雜，顯然，在巡視過程中，有些路線是不需要經(jīng)過的。因此，考慮對(duì)圖中的連接關(guān)系進(jìn)行簡(jiǎn)化，對(duì)于任何一個(gè)點(diǎn)，都要考慮從縣政府出發(fā)，能夠經(jīng)過盡可能短的路線到達(dá)該點(diǎn)。圖中數(shù)據(jù)較多，如果考慮用計(jì)算機(jī)處理，首先需要解決以下問題：〔1〕圖在計(jì)算機(jī)中是如何存儲(chǔ)的？〔2〕如何化簡(jiǎn)所給圖？〔3〕如何給出巡視路線？返回西北大學(xué)數(shù)學(xué)系圖的計(jì)算機(jī)表示：一般情況下，當(dāng)利用計(jì)算機(jī)處理圖的問題時(shí)，通常將圖的拓?fù)浣Y(jié)構(gòu)利用關(guān)聯(lián)矩陣或鄰接矩陣來表示。關(guān)聯(lián)矩陣鄰接矩陣西北大學(xué)數(shù)學(xué)系圖論常用問題及算法一、最短線路問題兩個(gè)指定頂點(diǎn)之間的最短路徑-----Dijkstra算法假設(shè)從v1到某個(gè)頂點(diǎn)vi的最短路是{v1,v2,…,vi-1,vi},那么{v1,v2,…,vi-1,vi}必然是vi到vi-1的最短路，所以要求v1過vi-1到vi的最短路，必須先求出v1到vi-1的最短通路.如果用L1,k表示vi到vk點(diǎn)的最短通路的長(zhǎng)，那么L1,k=min{L1,k-1+wk-1,k}西北大學(xué)數(shù)學(xué)系例v1,v2,…,v8,v9九個(gè)城市間的公路網(wǎng)如下圖，假定有一批貨物需要用卡車由v1分別運(yùn)到v9，問各走哪條路最短？ｖ１ｖ２ｖ３ｖ４ｖ５ｖ６ｖ７ｖ８ｖ９１２３３４２３３４５２３３2.5３西北大學(xué)數(shù)學(xué)系ｖ１ｖ２ｖ３ｖ４ｖ５ｖ６ｖ７ｖ８ｖ９１２３３４２３３４５２３３2.5３（0）34西北大學(xué)數(shù)學(xué)系重復(fù)〔２〕中的步驟，直到圖上全部沒有T標(biāo)號(hào)為止。西北大學(xué)數(shù)學(xué)系任意頂點(diǎn)之間的最短路徑-----Floyd算法西北大學(xué)數(shù)學(xué)系二、最小樹西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系最小樹西北大學(xué)數(shù)學(xué)系三、最大流問題如果把有向網(wǎng)絡(luò)看作一個(gè)交通網(wǎng)，其中點(diǎn)表示車站，弧表示道路，那么弧權(quán)就表示兩個(gè)車站間道路的通過能力。于是，給定一個(gè)有向網(wǎng)絡(luò)，需求指定兩點(diǎn)間的最大流量，即最大流問題。西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系最大流算法：根本思想：從一個(gè)可行流開始，尋找關(guān)于這個(gè)可行流的增廣鏈，假設(shè)存在，那么可以經(jīng)過調(diào)整，得到一個(gè)新的可行流，其流量比原來的可行流要大，重復(fù)這個(gè)過程，直到不存在關(guān)于該流的可增廣鏈為止。西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系西北大學(xué)數(shù)學(xué)系四、歐拉回路與中國(guó)郵遞員問題西北大學(xué)數(shù)學(xué)系歐拉回路的應(yīng)用-----中國(guó)郵遞員問題：一個(gè)郵遞員，負(fù)責(zé)某一地區(qū)的信件投遞，他每天要從郵局出發(fā)，走遍該地區(qū)所有街道在返回郵局，問應(yīng)如何安排送信的路線可以使所走的總路程最短？圖論問題：給定一個(gè)賦權(quán)連通圖，要求一條回路經(jīng)過每邊至少一次，且滿足總權(quán)最小。歐拉回路的存在性：無向連通圖是歐拉圖，當(dāng)且僅當(dāng)圖中無奇點(diǎn)。西北大學(xué)數(shù)學(xué)系中國(guó)郵遞員問題的分析：〔1〕如果圖中沒有奇點(diǎn)，那么是一個(gè)歐拉圖，那么歐拉回路就給出問題的解；〔2〕如果圖中有奇點(diǎn)，那么必然有些邊不止走過一次，這相當(dāng)于對(duì)圖中某些邊增加一些重復(fù)邊，使所得到的新圖沒有奇點(diǎn)且總路程最短。西北大學(xué)數(shù)學(xué)系ｖ１ｖ２ｖ３ｖ４ｖ５ｖ６ｖ７ｖ８ｖ９19231156789101314172021例在城市的點(diǎn)有一郵局，某郵遞員所負(fù)責(zé)的街道如圖所示〔街道旁的數(shù)字為街長(zhǎng)〕。問郵遞員從郵局出發(fā)，應(yīng)該走那條路線才能以最短路程走過每條街道至少一次，并最后回到郵局。西北大學(xué)數(shù)學(xué)系具體步驟：第一步：確定一個(gè)初始方案。1.先將街道圖中所有奇點(diǎn)配對(duì)。本例中有4個(gè)奇點(diǎn)：，將其中配對(duì)，配對(duì)。2.在每對(duì)奇點(diǎn)之間找一條鏈，并給該鏈的所有邊加一條重復(fù)邊〔權(quán)數(shù)與原邊相同〕在之間選一條鏈加重復(fù)邊。在之間選加重復(fù)邊。如下圖．ｖ１ｖ２ｖ３ｖ４ｖ５ｖ６ｖ７ｖ８ｖ９192345678910113131431317192021212重復(fù)邊總長(zhǎng)為69.西北大學(xué)數(shù)學(xué)系第二步：檢查是否是最優(yōu)方案，如果不是那么進(jìn)行調(diào)整。檢查標(biāo)準(zhǔn):(1)每條邊上最多只有一個(gè)重復(fù)邊；(2)每個(gè)圈上重復(fù)邊的總權(quán)數(shù)不大于該圈最大權(quán)數(shù)的一半。顯然在之間條件〔1〕不滿足，故不是最優(yōu)方案。調(diào)整：假設(shè)兩點(diǎn)間有兩條以上的重復(fù)邊，可從中去掉兩條，這樣所得新圖仍無奇點(diǎn)，仍可確定一個(gè)方案，該方案與原方案比較減少了重復(fù)邊數(shù)，方案得到了改進(jìn)。如下圖。ｖ１ｖ２ｖ３ｖ４ｖ５ｖ６ｖ７ｖ８ｖ９1923115678910112131215131519162121重復(fù)邊總長(zhǎng)為63.西北大學(xué)數(shù)學(xué)系對(duì)于條件(2)中，重復(fù)邊總長(zhǎng)超過圈長(zhǎng)一半，故需要調(diào)整。調(diào)整：去掉原重復(fù)邊，在之間添加一個(gè)重復(fù)邊，如下圖。ｖ１ｖ２ｖ３ｖ４ｖ５ｖ６ｖ７ｖ８ｖ９192311891011127111361515142121重復(fù)邊總長(zhǎng)為47.西北大學(xué)數(shù)學(xué)系對(duì)于條件(2)中，重復(fù)邊總長(zhǎng)超過圈長(zhǎng)一半，故需要調(diào)整。調(diào)整：去掉原重復(fù)邊，在之間經(jīng)添加一個(gè)重復(fù)邊，如下圖。ｖ１ｖ２ｖ３ｖ４ｖ５ｖ６ｖ７ｖ８ｖ９19231189101112711136151421重復(fù)邊總長(zhǎng)為34.至此，兩個(gè)條件都得到滿足那么圖中所給加邊方案最優(yōu)，在此圖中尋找歐拉回路，即得中國(guó)郵遞員問題的解。西北大學(xué)數(shù)學(xué)系五、Hamilton回路與旅行商問題Hamilton回路：在一個(gè)賦權(quán)圖中，經(jīng)過所有的頂點(diǎn)一次且僅一次，再回到出發(fā)點(diǎn)的回路。目前，關(guān)于Ha