CAN-File-10-10-08-13-線性規(guī)教學(xué)講解課件

第04章線性規(guī)劃：網(wǎng)絡(luò)流及整數(shù)規(guī)劃

LinearProgramming:NetworkFlowandintegerprogramming最小費用流問題網(wǎng)絡(luò)單純形法

－生成樹與基－原始網(wǎng)絡(luò)單純形法－對偶網(wǎng)絡(luò)單純形法網(wǎng)絡(luò)流問題的應(yīng)用

－運輸問題和指派問題－最短路問題－最大流問題最小費用流問題網(wǎng)絡(luò)基本元素：節(jié)點集(nodes)，設(shè)頂點的個數(shù)為m

有向弧集(directedarcs)

是所有可能弧集的子集弧是有方向的：網(wǎng)絡(luò)流的數(shù)據(jù)注：將供給重新表示為負(fù)需求,節(jié)點i

的需求量

,沿著弧(i,j)運輸1單位物品的費用假定I：供需平衡問題網(wǎng)絡(luò)流問題決策變量：目標(biāo)：,沿著弧(i,j)運輸?shù)臄?shù)量網(wǎng)絡(luò)流問題－續(xù)約束：

質(zhì)量守恒(massconservation)inflow(k)–outflow(k)=demand(k)=-supply(k),

非負(fù)性假定II：弧沒有容量限制矩陣記號A是點弧關(guān)聯(lián)矩陣(node-arcincidencematrix)

通常A的維數(shù)很大，并且是稀疏的注其中：對偶問題對偶變量對偶松弛變量用網(wǎng)絡(luò)記號：互補(bǔ)松弛關(guān)系(ComplementarityRelations)

原變量必須是非負(fù)的因此與之相聯(lián)系的對偶約束是不等式對偶松弛變量與原變量是互補(bǔ)的：

原始約束是等式因此他們沒有松弛變量對應(yīng)的對偶變量，，是自由變量對于他們互補(bǔ)條件是自然成立的網(wǎng)絡(luò)單純形法定義：子網(wǎng)絡(luò)(Subnetwork)網(wǎng)絡(luò)子網(wǎng)絡(luò)定義：連通vs.不連通(Connectedvs.Disconnected)連通不連通定義：圈vs.非圈(Cyclicvs.Acyclic)圈非圈定義：樹(Trees)樹＝連通的+非圈非樹定義：生成樹(SpanningTrees)生成樹－觸及到每個頂點的樹樹解的計算?樹解(treesolution)滿足流平衡約束給定生成樹且對,樹解－原始流

固定一個根節(jié)點，比如e樹解的計算：從葉子節(jié)點開始，逆向依次解流平衡方程葉子節(jié)點：僅有一條弧相連接的節(jié)點樹解－對偶變量與對偶松弛變量

利用計算非樹弧上的對偶松弛變量

從根節(jié)點開始，沿著樹弧利用向外遞歸計算，可得到頂點處的對偶變量樹解與基本可行解的關(guān)系引理.

A的秩是m-1；

在生成樹中，選擇一個節(jié)點，刪除與之對應(yīng)的流平衡約束，并稱之為根節(jié)點(rootnode);對應(yīng)的關(guān)聯(lián)矩陣和供需向量定理

的m-1階子方陣是最小費用流問題的基當(dāng)且僅當(dāng)其列對應(yīng)的弧恰好搭建成網(wǎng)絡(luò)的一個生成樹.定理’一個流向量是基本解當(dāng)且僅當(dāng)它是一個樹解.

樹解基本解；對偶變量單純形乘子；對偶松弛變量相對費用系數(shù).原始網(wǎng)絡(luò)單純形法假設(shè)樹解是原始可行的，即滿足非負(fù)條件：入弧選取規(guī)則：選取弧(i,j)使得對偶松弛變量zij<0出弧選取規(guī)則：

在圈中，與入弧的方向相反；且在所有這樣可能的弧中流最小.原始流的更新(*****)：與出弧同方向的減去出弧上的流；與出弧反方向的加上出弧上的流.入弧為(d,e);出弧為(d,c).(用于無容量限制網(wǎng)絡(luò)的)網(wǎng)絡(luò)單純形法：Step1.從一個可行的樹解開始，假設(shè)第n

個節(jié)點是根節(jié)點.Step2.計算對偶向量(單純形乘子)：從根節(jié)點向葉子節(jié)點，依次求解方程組Step3.計算對偶松弛向量(相對費用系數(shù)/既約費用系數(shù))：(i,j)使得，稱之為入弧.如果他們?nèi)秦?fù)，當(dāng)前樹解是最優(yōu)的；否則，選取弧Step4.確定出?。喝牖『蜆浠”匦纬梢粋€圈.如果圈中的所有弧和入弧同向，則最優(yōu)費用是-∞，終止算法.否則，在與入弧反向的樹弧中選一個最小的流作為出弧.Step5.轉(zhuǎn)軸：在當(dāng)前樹解中用入弧代替出弧，更新原始流，得新的樹解.轉(zhuǎn)Step2.對偶變量的更新

從新的生成樹中刪除入弧，得到網(wǎng)絡(luò)的兩個子樹；一個子樹含根節(jié)點(T0)，另一個不含根節(jié)點(T1).子樹T0上的節(jié)點對應(yīng)的對偶變量不變；子樹T1上的節(jié)點對應(yīng)的對偶變量的更新準(zhǔn)則：入弧由T0指向T1時，對偶變量統(tǒng)一加上入弧的對偶松弛變量入弧由T1指向T0時，對偶變量統(tǒng)一減去入弧的對偶松弛變量對偶松弛變量的更新對偶松弛變量的更新策略：非橋接弧保持不變；與入弧同向橋接兩個子樹，對偶松弛變量

減去入弧上的原有對偶松弛變量；與入弧反向橋接兩個子樹，對偶松弛變量

加上入弧上的原有對偶松弛變量；對偶網(wǎng)絡(luò)單純形法假設(shè)樹解是對偶可行的，即確定的對偶變量和對偶松弛變量滿足對偶問題的約束條件(即基本解是對偶可行的)：出弧選取規(guī)則：選取樹弧(i,j)使得對應(yīng)流xij<0去掉出弧，生成樹變成兩個子樹；入弧必須橋接兩個子樹！出弧(c,a)入弧選取規(guī)則：

必須是橋接兩個子樹的非樹弧，

且與出弧反方向；在可選的中間選取對偶松弛最小的.入弧(d,e)出弧(c,a)入弧(d,e)最優(yōu)解！

找一個樹解

法1

改變原問題的費用向量使得所給樹解是對偶可行的；利用對偶網(wǎng)絡(luò)單純形法求解新問題，得到最優(yōu)解；新問題的最優(yōu)解是原問題的可行樹解；從此樹解出發(fā)，利用原始網(wǎng)絡(luò)單純形法求解所給問題.

法2

改變原問題的供給向量使得所給樹解是原始可行的；利用原始網(wǎng)絡(luò)單純形法求解新問題，得到最優(yōu)解；新問題的最優(yōu)解是原問題的對偶可行樹解；從此樹解出發(fā)，利用對偶網(wǎng)絡(luò)單純形法求解所給問題.求解一般的最小費用流問題：整性定理(IntegralityTheorem)整性定理.考慮無容量限制的網(wǎng)絡(luò)流問題.i)如果供給量bi是整數(shù)，則每個基本可行解的分量是整數(shù).ii)如果費用系數(shù)

cij

是整數(shù)，則每個對偶基本解的分量是整數(shù).整數(shù)線性規(guī)劃通常不易求解；但是具有整性數(shù)據(jù)的最小費用流問題可用網(wǎng)絡(luò)單純形法求解！網(wǎng)絡(luò)流：應(yīng)用運輸問題(TransportationProblem)每個頂點是兩種類型之一：

發(fā)(源/供給)點收(目的/需求)點每條弧滿足：

起點在發(fā)點終點在收點二部/分圖(bipartite)供給節(jié)點需求節(jié)點運輸問題的表上作業(yè)法數(shù)據(jù)表運輸表7個頂點8條??！有6個基變量，2個非基變量對偶變量

需求量供給量102315756*1184318*9*12*36指派問題(AssignmentProblem)

給定m個人和m項任務(wù)，第i個人完成任務(wù)j的費用是cij

指派每個人去做且只做一項任務(wù)每項任務(wù)只由一個人去完成

忽略整數(shù)要求，由整性定理，利用網(wǎng)絡(luò)單純形法可得到指派問題的解！問題是嚴(yán)重退化的，有2m個約束，但基本解只有m個非零元素！相對于二次指派問題，稱這里的問題為線性指派問題！最短路問題(ShortestPathsProblem)給定：

網(wǎng)絡(luò)：

費用=旅行時間：根節(jié)點(homeorroot)：問題：找從N中每一個節(jié)點出發(fā)到根節(jié)點的最短路(有向的)根節(jié)點5：

1→3→5：5

2→5：53→5：14→3→5：3

1

4

2

3

5

7

4

5

1

2

5

1

4

網(wǎng)絡(luò)流表述

令vi=從節(jié)點i

到根節(jié)點r

的最短時間

在網(wǎng)絡(luò)文獻(xiàn)中稱為標(biāo)號(label);

在動態(tài)規(guī)劃的文獻(xiàn)中稱為值(value).以下算法中使用的記號：

令

求解最小費用網(wǎng)絡(luò)流問題從i

到r

的最短路：由最優(yōu)樹弧得到最短路的長度(時間)=標(biāo)號校正算法(LabelCorrectingAlgorithm)動態(tài)規(guī)劃(DynamicProgramming)Bellman方程組、動態(tài)規(guī)劃原理不必是一個樹！

逐次逼近法(MethodofsuccessiveApproximation)－初始化：－迭代：－終止：當(dāng)某次迭代沒有一個vi改變時，終止算法.標(biāo)號校正算法的復(fù)雜度

vi(k)=從節(jié)點i

到根節(jié)點

r

且有k

條弧或者更少的最短路的長度

最多要求m-1次迭代每次迭代作n

次加/比較運算總共需要mn

次運算標(biāo)號設(shè)置算法(LabelSettingAlgorithm)Dijkstra算法，1959年記號：

F=已完成的節(jié)點集(標(biāo)號被設(shè)定)

=在i

之后要訪問的節(jié)點(終點)Dijkstra算法：

初始化：

迭代：－當(dāng)還有未完成的節(jié)點時，選擇vi

最小的節(jié)點,記為j.

將j

添加到已完成節(jié)點集－對每個未完成的節(jié)點i

，且有弧(i,j)將i

和j

連接起來：Dijkstra最短路算法的流程根節(jié)點5：

1→3→5：5

2→5：53→5：14→3→5：3Dijkstra算法的復(fù)雜度

每次迭代完成一個節(jié)點：m

次迭代

每次迭代的計算量：－選擇一個未完成的節(jié)點：*普通的需要m

次比較*使用合適的數(shù)據(jù)結(jié)構(gòu)，需要logm次比較－更新鄰接弧總共：mlog

m+n最大流問題(MaximumFlowProblem)給定：問題：求從s

到t

的最大流量(將盡可能多的流從s

推向t)

網(wǎng)絡(luò)：,A

是點弧關(guān)聯(lián)矩陣

弧上流量的上界：發(fā)點，收點Ford-Fulkerson算法最大流－最小割定理網(wǎng)絡(luò)流表述

令

添加人工弧(t,s)：割及割的容量

s-t

割(cut)：包含發(fā)點s

但不包含收點t

的節(jié)點集合C

割的容量(capacity)：流平衡方程：最大流－最小割定理(Max-FlowMin-CutTheorem)定理.在任一網(wǎng)絡(luò)中，最大流的流量等于最小割的容量.

由Ford與Fulkerson于1956年提出來的，是圖論和網(wǎng)絡(luò)流中的最重要結(jié)論之一!設(shè)是最大流問題的解xts

*設(shè)是對偶問題的解證明線性整數(shù)規(guī)劃

整數(shù)線性規(guī)劃

－調(diào)度問題－旅行商問題－實用的建模技術(shù)分支定界法

調(diào)度問題(SchedulingProblems)

設(shè)備調(diào)度(equipmentscheduling)

人員調(diào)度(crewscheduling)Airlinescheduling：

Route-identificationRouteOptimization(√)設(shè)備調(diào)度問題

可能的航線(route)集{1,2,……,n}

，對應(yīng)的費用cjm

個航段(leg)集{1,2,……,m}

航線和航段的關(guān)系：問題：選取航線使得每個航段恰被覆蓋一次，且總費用最小把航段合理的安排到不同的航線上！機(jī)組人員調(diào)度問題

可能的航線(route)集{1,2,……,n}

，對應(yīng)的費用cjm

組人員(flightcrews){1,2,……,m}

－可以理解為每組為一個航段服務(wù)航線和機(jī)組人員的關(guān)系：問題：選取航線使每組人員至少為一個航線服務(wù)，且總費用最小把機(jī)組人員合理地安排到航線上！

旅行商問題(TravelingSalesmanProblem,TSP)旅行商從城市0出發(fā)，周游城市1,2,……，n-1；每個城市只經(jīng)過一次，最后回到城市0；城市兩兩之間的距離為cij問題：安排周游使總路程最短.周游=所有城市的排列可能的周游數(shù)目：(n-1)!

頂點約束原有問題的松弛該問題的解可能會含幾個有向子圈，也稱子周游.指派約束！想辦法排除子圈！

子周游表述(SubtourFormulation)添加一族子周游(消去)約束一開始不必把所有的子周游消去約束都放進(jìn)去；可以邊算邊放！有指數(shù)多個約束！NN0,ti∈{1,2,…,n-1},i≥1

MTZ(Miller-Tucker-Zemlin)表述引入新變量ti

－表示進(jìn)入城市i

之前經(jīng)過的城市數(shù)目弧約束0規(guī)模??！可處理有偏好的周游！

實用建模技術(shù)或約束：引入0-1變量y其中M是充分大的正數(shù)帶固定成本的目標(biāo)函數(shù)：進(jìn)一步假設(shè)+非線性目標(biāo)函數(shù)－二次多項式

其中yij

滿足

其中zij

滿足假設(shè)分成3段，即k=3非線性目標(biāo)函數(shù)－連續(xù)的逐段線性函數(shù)非線性目標(biāo)函數(shù)－連續(xù)的非線性函數(shù)連續(xù)非線性函數(shù)的逐段線性函數(shù)近似!整數(shù)線性規(guī)劃的線性規(guī)劃松弛(LP-relaxation)x*=(0,1),z*=1.9舍入到最近的整數(shù)(1,0)不可行！(2,0)，(1,1),(2,2)可行但非最優(yōu)!線性規(guī)劃松弛：x=(1.5,0),=1.5分支定界法分支第一次分支當(dāng)前最好解(best-so-far)第二次分支枚舉樹(enumerationtree)線性規(guī)劃松弛：x=(1.5,0),=1.5剪枝、廣探法與深探法剪枝(pruning)廣探法(breadth-first-search)深探法(depth-firstsearch)假如P1的最優(yōu)值為2.1深探法與線性整數(shù)規(guī)劃探測到整數(shù)解的好處：一個可行解對應(yīng)一種可行設(shè)計或者可行決策！找到可行解就有可能更新當(dāng)前最好解，這可以幫助剪枝深探法的優(yōu)勢：整數(shù)解通常位于枚舉樹的底層深探法的程序編寫較容易可應(yīng)用對偶單純形法求解下一層的子問題應(yīng)用對偶單純形法求解子問題P1=P0+“x1≤1”P2=P0+“x1≥2”用單純形法求解P0，之后用對偶單純形法求解

P1和P2分支定界法的原理節(jié)點對應(yīng)著一個連續(xù)優(yōu)化問題，其中根節(jié)點對應(yīng)的是松弛問題P0；節(jié)點分三類：父節(jié)點、無可行解的葉子節(jié)點和解是整數(shù)的葉子節(jié)點；節(jié)點之間由分支連接起來分支定界法中枚舉樹的結(jié)構(gòu)分支定界法的動機(jī)：通過探測枚舉樹來尋找解是整數(shù)的葉子節(jié)點，從而找到目標(biāo)值最小的一個。在一個父節(jié)點，連續(xù)優(yōu)化問題的解可能有多個分量違反整性約束。因此有多種方式來選取分支變量。從而枚舉樹不是惟一確定的。分支定界法的原理II下一次應(yīng)該求解哪個節(jié)點對應(yīng)的問題

；應(yīng)該對哪個變量進(jìn)行分支；為當(dāng)前節(jié)點對應(yīng)的子問題確定一個下界.2.從已經(jīng)探測到的整性葉子節(jié)點中，找到目前最好的整數(shù)可行解及目標(biāo)值；部分搜索策略中需要確定：1.保持一個未解決問題棧，且每個問題有一個最優(yōu)值的下界；棧(stack)方法：分支定界法IIIInitially,theco