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

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

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

LinearProg最小費(fèi)用流問題網(wǎng)絡(luò)單純形法

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

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

有向弧集(directedarcs)

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

的需求量

,沿著弧(i,j)運(yùn)輸1單位物品的費(fèi)用假定I：供需平衡問題網(wǎng)絡(luò)流的數(shù)據(jù)注：將供給重新表示為負(fù)需求網(wǎng)絡(luò)流問題決策變量：目標(biāo)：,沿著弧(i,j)運(yùn)輸?shù)臄?shù)量網(wǎng)絡(luò)流問題決策變量：目標(biāo)：網(wǎng)絡(luò)流問題－續(xù)約束：

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

非負(fù)性假定II：弧沒有容量限制網(wǎng)絡(luò)流問題－續(xù)約束：質(zhì)量守恒(massconservat矩陣記號(hào)A是點(diǎn)弧關(guān)聯(lián)矩陣(node-arcincidencematrix)

通常A的維數(shù)很大，并且是稀疏的注其中：矩陣記號(hào)A是點(diǎn)弧關(guān)聯(lián)矩陣(node-arcinciden對(duì)偶問題對(duì)偶變量對(duì)偶松弛變量用網(wǎng)絡(luò)記號(hào)：對(duì)偶問題對(duì)偶變量對(duì)偶松弛變量用網(wǎng)絡(luò)記號(hào)：互補(bǔ)松弛關(guān)系(ComplementarityRelations)

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

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

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

利用計(jì)算非樹弧上的對(duì)偶松弛變量

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

A的秩是m-1；

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

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

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

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

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

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

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

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

必須是橋接兩個(gè)子樹的非樹弧，

且與出弧反方向；在可選的中間選取對(duì)偶松弛最小的.入弧(d,e)對(duì)偶網(wǎng)絡(luò)單純形法假設(shè)樹解是對(duì)偶可行的，即確定的對(duì)偶變量和對(duì)偶出弧(c,a)入弧(d,e)最優(yōu)解！出弧(c,a)入弧(d,e)最優(yōu)解！

找一個(gè)樹解

法1

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

法2

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

cij

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

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

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

需求量供給量102315756*1184318*9*12*36運(yùn)輸問題的表上作業(yè)法數(shù)據(jù)表運(yùn)輸表7個(gè)頂點(diǎn)8條?。∮?指派問題(AssignmentProblem)

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

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

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

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

費(fèi)用=旅行時(shí)間：根節(jié)點(diǎn)(homeorroot)：?jiǎn)栴}：找從N中每一個(gè)節(jié)點(diǎn)出發(fā)到根節(jié)點(diǎn)的最短路(有向的)根節(jié)點(diǎn)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

最短路問題(ShortestPathsProblem)給網(wǎng)絡(luò)流表述

令vi=從節(jié)點(diǎn)i

到根節(jié)點(diǎn)r

的最短時(shí)間

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

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

令

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

到r

的最短路：由最優(yōu)樹弧得到最短路的長度(時(shí)間)=網(wǎng)絡(luò)流表述令vi=從節(jié)點(diǎn)i到根節(jié)點(diǎn)r的最短時(shí)間標(biāo)號(hào)校正算法(LabelCorrectingAlgorithm)動(dòng)態(tài)規(guī)劃(DynamicProgramming)Bellman方程組、動(dòng)態(tài)規(guī)劃原理不必是一個(gè)樹！

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

vi(k)=從節(jié)點(diǎn)i

到根節(jié)點(diǎn)

r

且有k

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

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

次加/比較運(yùn)算總共需要mn次運(yùn)算標(biāo)號(hào)校正算法的復(fù)雜度vi(k)=從節(jié)點(diǎn)i到根節(jié)點(diǎn)r標(biāo)號(hào)設(shè)置算法(LabelSettingAlgorithm)Dijkstra算法，1959年記號(hào)：

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

=在i

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

初始化：

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

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

將j

添加到已完成節(jié)點(diǎn)集－對(duì)每個(gè)未完成的節(jié)點(diǎn)i

，且有弧(i,j)將i

和j

連接起來：標(biāo)號(hào)設(shè)置算法(LabelSettingAlgorithmDijkstra最短路算法的流程根節(jié)點(diǎn)5：

1→3→5：5

2→5：53→5：14→3→5：3Dijkstra最短路算法的流程根節(jié)點(diǎn)5：Dijkstra算法的復(fù)雜度

每次迭代完成一個(gè)節(jié)點(diǎn)：m

次迭代

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

次比較*使用合適的數(shù)據(jù)結(jié)構(gòu)，需要logm次比較－更新鄰接弧總共：mlogm+nDijkstra算法的復(fù)雜度每次迭代完成一個(gè)節(jié)點(diǎn)：m次迭最大流問題(MaximumFlowProblem)給定：?jiǎn)栴}：求從s

到t

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

推向t)

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

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

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

令

添加人工弧(t,s)：網(wǎng)絡(luò)流表述令割及割的容量

s-t

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

但不包含收點(diǎn)t

的節(jié)點(diǎn)集合C

割的容量(capacity)：流平衡方程：割及割的容量s-t割(cut)：包含發(fā)點(diǎn)s但不包含收最大流－最小割定理(Max-FlowMin-CutTheorem)定理.在任一網(wǎng)絡(luò)中，最大流的流量等于最小割的容量.

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

*設(shè)是對(duì)偶問題的解證明最大流－最小割定理(Max-FlowMin-CutThe線性整數(shù)規(guī)劃線性整數(shù)規(guī)劃

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

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

整數(shù)線性規(guī)劃調(diào)度問題(SchedulingProblems)

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

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

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

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

，對(duì)應(yīng)的費(fèi)用cjm

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

航線和航段的關(guān)系：?jiǎn)栴}：選取航線使得每個(gè)航段恰被覆蓋一次，且總費(fèi)用最小把航段合理的安排到不同的航線上！設(shè)備調(diào)度問題可能的航線(route)集{1,2,……機(jī)組人員調(diào)度問題

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

，對(duì)應(yīng)的費(fèi)用cjm

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

－可以理解為每組為一個(gè)航段服務(wù)航線和機(jī)組人員的關(guān)系：?jiǎn)栴}：選取航線使每組人員至少為一個(gè)航線服務(wù)，且總費(fèi)用最小把機(jī)組人員合理地安排到航線上！機(jī)組人員調(diào)度問題可能的航線(route)集{1,2,

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

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

子周游表述(SubtourFormulation)添加一族子周游(消去)約束一開始不必把所有的子周游消去約束都放進(jìn)去；可以邊算邊放！有指數(shù)多個(gè)約束！NN子周游表述(SubtourFormulation)添加一0,ti∈{1,2,…,n-1},i≥1MTZ(Miller-Tucker-Zemlin)表述引入新變量ti

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

之前經(jīng)過的城市數(shù)目弧約束0規(guī)模小！可處理有偏好的周游！0,ti∈{1,2,…,n-1},i≥1MTZ

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

其中yij

滿足

其中zij

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

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

；應(yīng)該對(duì)哪個(gè)變量進(jìn)行分支；為當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的子問題確定一個(gè)下界.2.從已經(jīng)探測(cè)到的整性葉子節(jié)點(diǎn)中，找到目前最好的整數(shù)可行解及目標(biāo)值；部分搜索策略中需要確定：1.保持一個(gè)未解決問題棧，且每個(gè)問題有一個(gè)最優(yōu)值的下界；棧(stack)方法：分支定界法的原理II下一次應(yīng)該求解哪個(gè)節(jié)點(diǎn)對(duì)應(yīng)的問題；2.63分支定界法IIIInitially,thecontinuousproblemisputinthestackwith,and算法4.3.1Branchandboundmethodforintegerprogrammingproblemthealgorithmproceedsasfollowing:(i)Ifnoproblemisinthestack,finishwithasx*andf*;Otherwisetakethetopproblemfromthestack.(ii)Ifrejecttheproblemandgoto(i).(iii)Trytosolvetheproblem:ifnofeasiblepointexistsrejecttheproblemandgoto(i).(iv)Letthesolutionbex`withf`:ifrejecttheproblemandgoto(i).(v)Ifx`isintegerfeasiablethensetandgoto(i).Selectanintegervariableisuchthat,creattwonewproblemsbybranchingonxi,placetheseonthestackwithlowerbound(orahigherlowerboundderivedfromf

`),andgoto(i).分支定界法IIIInitially,64第04章線性規(guī)劃：網(wǎng)絡(luò)流及整數(shù)規(guī)劃

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

LinearProg最小費(fèi)用流問題網(wǎng)絡(luò)單純形法

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

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

有向弧集(directedarcs)

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

的需求量

,沿著弧(i,j)運(yùn)輸1單位物品的費(fèi)用假定I：供需平衡問題網(wǎng)絡(luò)流的數(shù)據(jù)注：將供給重新表示為負(fù)需求網(wǎng)絡(luò)流問題決策變量：目標(biāo)：,沿著弧(i,j)運(yùn)輸?shù)臄?shù)量網(wǎng)絡(luò)流問題決策變量：目標(biāo)：網(wǎng)絡(luò)流問題－續(xù)約束：

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

非負(fù)性假定II：弧沒有容量限制網(wǎng)絡(luò)流問題－續(xù)約束：質(zhì)量守恒(massconservat矩陣記號(hào)A是點(diǎn)弧關(guān)聯(lián)矩陣(node-arcincidencematrix)

通常A的維數(shù)很大，并且是稀疏的注其中：矩陣記號(hào)A是點(diǎn)弧關(guān)聯(lián)矩陣(node-arcinciden對(duì)偶問題對(duì)偶變量對(duì)偶松弛變量用網(wǎng)絡(luò)記號(hào)：對(duì)偶問題對(duì)偶變量對(duì)偶松弛變量用網(wǎng)絡(luò)記號(hào)：互補(bǔ)松弛關(guān)系(ComplementarityRelations)

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

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

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

利用計(jì)算非樹弧上的對(duì)偶松弛變量

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

A的秩是m-1；

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

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

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

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

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

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

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

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

必須是橋接兩個(gè)子樹的非樹弧，

且與出弧反方向；在可選的中間選取對(duì)偶松弛最小的.入弧(d,e)對(duì)偶網(wǎng)絡(luò)單純形法假設(shè)樹解是對(duì)偶可行的，即確定的對(duì)偶變量和對(duì)偶出弧(c,a)入弧(d,e)最優(yōu)解！出弧(c,a)入弧(d,e)最優(yōu)解！

找一個(gè)樹解

法1

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

法2

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

cij

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

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

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

需求量供給量102315756*1184318*9*12*36運(yùn)輸問題的表上作業(yè)法數(shù)據(jù)表運(yùn)輸表7個(gè)頂點(diǎn)8條??！有6指派問題(AssignmentProblem)

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

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

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

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

費(fèi)用=旅行時(shí)間：根節(jié)點(diǎn)(homeorroot)：?jiǎn)栴}：找從N中每一個(gè)節(jié)點(diǎn)出發(fā)到根節(jié)點(diǎn)的最短路(有向的)根節(jié)點(diǎn)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

最短路問題(ShortestPathsProblem)給網(wǎng)絡(luò)流表述

令vi=從節(jié)點(diǎn)i

到根節(jié)點(diǎn)r

的最短時(shí)間

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

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

令

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

到r

的最短路：由最優(yōu)樹弧得到最短路的長度(時(shí)間)=網(wǎng)絡(luò)流表述令vi=從節(jié)點(diǎn)i到根節(jié)點(diǎn)r的最短時(shí)間標(biāo)號(hào)校正算法(LabelCorrectingAlgorithm)動(dòng)態(tài)規(guī)劃(DynamicProgramming)Bellman方程組、動(dòng)態(tài)規(guī)劃原理不必是一個(gè)樹！

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

vi(k)=從節(jié)點(diǎn)i

到根節(jié)點(diǎn)

r

且有k

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

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

次加/比較運(yùn)算總共需要mn次運(yùn)算標(biāo)號(hào)校正算法的復(fù)雜度vi(k)=從節(jié)點(diǎn)i到根節(jié)點(diǎn)r標(biāo)號(hào)設(shè)置算法(LabelSettingAlgorithm)Dijkstra算法，1959年記號(hào)：

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

=在i

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

初始化：

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

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

將j

添加到已完成節(jié)點(diǎn)集－對(duì)每個(gè)未完成的節(jié)點(diǎn)i

，且有弧(i,j)將i

和j

連接起來：標(biāo)號(hào)設(shè)置算法(LabelSettingAlgorithmDijkstra最短路算法的流程根節(jié)點(diǎn)5：

1→3→5：5

2→5：53→5：14→3→5：3Dijkstra最短路算法的流程根節(jié)點(diǎn)5：Dijkstra算法的復(fù)雜度

每次迭代完成一個(gè)節(jié)點(diǎn)：m

次迭代

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

次比較*使用合適的數(shù)據(jù)結(jié)構(gòu)，需要logm次比較－更新鄰接弧總共：mlogm+nDijkstra算法的復(fù)雜度每次迭代完成一個(gè)節(jié)點(diǎn)：m次迭最大流問題(MaximumFlowProblem)給定：?jiǎn)栴}：求從s

到t

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

推向t)

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

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

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

令

添加人工弧(t,s)：網(wǎng)絡(luò)流表述令割及割的容量

s-t

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

但不包含收點(diǎn)t

的節(jié)點(diǎn)集合C

割的容量(capacity)：流平衡方程：割及割的容量s-t割(cut)：包含發(fā)點(diǎn)s但不包含收最大流－最小割定理(Max-FlowMin-CutTheorem)定理.在任一網(wǎng)絡(luò)中，最大流的流量等于最小割的容量.

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

*設(shè)是對(duì)偶問題的解證明最大流－最小割定理(Max-FlowMin-CutThe線性整數(shù)規(guī)劃線性整數(shù)規(guī)劃

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

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

整數(shù)線性規(guī)劃調(diào)度問題(SchedulingProblems)

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

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

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

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

，對(duì)應(yīng)的費(fèi)用cjm

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

航線和航段的關(guān)系：?jiǎn)栴}：選取航線使得每個(gè)航段恰被覆蓋一次，且總費(fèi)用最小把航段合理的安排到不同的航線上！設(shè)備調(diào)度問題可能的航線(route)集{1,2,……機(jī)組人員調(diào)度問題

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

，對(duì)應(yīng)的費(fèi)用cjm

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

－可以理解為每組為一個(gè)航段服務(wù)航線和機(jī)組人員的關(guān)系：?jiǎn)栴}：選取航線使每組人員至少為一個(gè)航線服務(wù)，且總費(fèi)用最小把機(jī)組人員合理地安排到航線上！機(jī)組人員調(diào)度問題可能的航線(route)集{1,2,

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

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

子周游表述(SubtourFormulation)添加一族子周游(消去)約束一開始不必把所有的子周游消去約束都放進(jìn)去；可以邊算邊放！有指數(shù)多個(gè)約束！NN子周游表述(SubtourFormulation)添加一0,ti∈{1,2,…,n-1},i≥1MTZ(Miller-Tucker-Zemlin)表述引入新變量ti

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

之前經(jīng)過的城市數(shù)目弧約束0規(guī)模小！可處理有偏好的周游！0,ti∈{1,2,…,n-1},i≥1MTZ

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

其中yij

滿足

其中zij

滿足非線性目標(biāo)函數(shù)－二次多項(xiàng)式其中yij滿足其中zij假設(shè)分成3段，即k=3非線性目標(biāo)函數(shù)－連續(xù)的逐段線性函數(shù)假設(shè)分成3段，即k=3非線性目標(biāo)函數(shù)－連續(xù)的逐段線性函數(shù)非線性目標(biāo)函數(shù)－連續(xù)的非線性函數(shù)連續(xù)非線性函數(shù)的逐段線性函數(shù)近似!非線性目標(biāo)函數(shù)－連續(xù)的非線性函數(shù)連續(xù)非線性函數(shù)的逐段線性函數(shù)整數(shù)線性規(guī)劃的線性規(guī)劃松弛(LP-relaxation)