整數(shù)規(guī)劃課件

網(wǎng)絡(luò)優(yōu)化

Network

Optimization

清華大學(xué)課號(hào)：40420213（本），70420133（研）

第3章整數(shù)規(guī)劃（IntegerProgramming）

清華大學(xué)數(shù)學(xué)科學(xué)系謝金星

整數(shù)規(guī)劃問題的例子

例(續(xù)例1.4)指派問題(AssignmentProblem)

一家公司經(jīng)理準(zhǔn)備安排N名員工去完成N項(xiàng)任務(wù)，每人一項(xiàng).由

于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得

的回報(bào)是不同的.如何分配工作方案可以使總回報(bào)最大？

MAXZI'H%?與線性整數(shù)規(guī)劃（LIP）

s.t.=L/=12…，明非線性整數(shù)規(guī)劃（NIP）

丁純整數(shù)規(guī)劃（PIP）

_1'2_1,2,???，〃，混合整數(shù)規(guī)劃（MIP）

xije{0"，特例：0T規(guī)劃

許多網(wǎng)絡(luò)優(yōu)化問題也可以用整數(shù)規(guī)劃（IP）來建模2

3.1.1整數(shù)規(guī)劃問題的幾種描述形式

線性規(guī)劃(LP：LinearProgramming)問題的標(biāo)準(zhǔn)形式

mincTx

s.t.Ax=b(3.1)

x>0

c/eRLbeRMAeRE,才是行滿秩的，且m<n.b>0

純整數(shù)線性規(guī)劃(PILP,以后簡(jiǎn)稱整數(shù)規(guī)劃(IP))的標(biāo)準(zhǔn)形式

mincTx

s.t.Ax-b(3.2)

x>0

x,GZ

c,xeZn,beZm,AeZmx〃，力是行滿秩的，且m<n,b>0

3.1.1整數(shù)規(guī)劃問題的幾種描述形式

整數(shù)規(guī)劃的一般形式min/x

T

s.t.Q,x=bj,ieM

a：x>b^ieM(3.3)

xjeZ*,jeN

x.wZ,/wN

JJ

整數(shù)規(guī)劃的規(guī)范形式儲(chǔ)

mincTx

s.t.Ax>b(3.4)

x>0

XjGZ

整數(shù)規(guī)劃的上述三種形式是等價(jià)的：一種形式下的實(shí)例,

可以簡(jiǎn)單地等價(jià)變化為另一種形式下的實(shí)例.

3.2.2整數(shù)規(guī)劃問題的求解難度

整數(shù)規(guī)劃問題是NP困難的.

為什么不先求解相應(yīng)的線性規(guī)劃問題(一般稱為整數(shù)規(guī)劃問題

的線性規(guī)劃松弛問題，或簡(jiǎn)稱LP-Relaxation),然后將

得到的解四舍五入到最接近的整數(shù)？

LC

///目標(biāo)函數(shù)下降方向

----1------^巧

IP可行解對(duì)應(yīng)于整點(diǎn)A(2,2)和B(l,1),而最優(yōu)解為A點(diǎn).但LP松弛的最|

優(yōu)解為C(3.5,2.5)5

3.2全么模陣

IP的LP松弛的最優(yōu)解什么時(shí)候一定是整數(shù)解呢？

假設(shè)在(3.1)式所示的線性規(guī)劃問題中等式約束個(gè)數(shù)等于決策

變量個(gè)數(shù)(旭=〃),則此時(shí)的等式約束構(gòu)成一個(gè)線性方程組

det(A

x/—?j-1,2,.

det(/)

如果方陣Z為整數(shù)矩陣且b為整數(shù)向量,則det(A)和def都是整

數(shù).當(dāng)然，解工未必是整數(shù)向量.

如果det(Z)=1或則解x一定是整數(shù)向量.

3.2全么模陣-Hoffman-Kruskal定理(1956)

定理3.1設(shè)在(3.1)式所示的線性規(guī)劃問題中/為整數(shù)矩陣，且/滿行秩，

則下面三個(gè)條件等價(jià)：

(1)對(duì)每個(gè)基矩陣民其行列式det(8)=1或-1.

(2)對(duì)任何整數(shù)向量其可行域。(6)={x[-=b,xZ0}的每個(gè)

極點(diǎn)都是整數(shù)向量.

(3)對(duì)每個(gè)基矩陣8其逆矩陣也是整數(shù)矩陣.

o(R。、adj

證明(1)=>(2)：XB=(By'b=^—b

det(5°)

(2)=>(3):設(shè)夕為任一基矩陣，如果其逆矩陣不是整數(shù)矩陣，任

x

取整數(shù)向量y使得z=y+B-ei>0,這里與表示第7個(gè)分量為1其余分量為

0的“單位向量”.’

令b=比=5(歹+3一7,)=為十分，則A為整數(shù)向量，且向量

z=B-xb20為〃(b)的一個(gè)極'點(diǎn)的基向量；因此是整數(shù)向量.

因此員Z=z-y為整數(shù)向量，即是整數(shù)矩陣.

(3)=>(1):設(shè)夕為任一基矩陣，由于夕切=/，又知夕和5一都是整數(shù)

矩陣，所以det(B)=1或T.

3.2全么模陣-定義

定義3.1如果一個(gè)矩陣/的任何子方陣的行列式的值都等于3

1或T,則稱Z是全么模的（TU：TotallyUnimodular,又譯為

全單位模的），或稱/是全么模矩陣.

■模矩陣的元素只能取0,1和

定理3答:1連么模矩陣的性質(zhì)）下列命題等價(jià)：

1）/是全么模矩陣.

2）T是全么模矩陣.

3）AT是全么模矩陣.

4）（《力）是全么模矩陣.

5）（4/）,（兒0）是全么模矩陣.

/為全么模矩陣時(shí)的整數(shù)規(guī)劃問題實(shí)際上等價(jià)于對(duì)應(yīng)的LP&

松弛問題（單純形算法）.

3.2全么模陣-充分條件

定理3.3設(shè)A是由0,1和-1組成的矩陣，如果下面兩個(gè)條件同時(shí)成立，

則A為全么模矩陣.

（1）A的每一列至多含有兩個(gè)非零元素.

（2）A的行可以分為ALA2兩個(gè)集合，使得：如果A的一列中有兩

個(gè)符號(hào)不同的元素，則相應(yīng)的兩行在同一集合A1或A2中；如果A的一

列中有兩個(gè)符號(hào)相同的元素，則相應(yīng)的兩行分別位于兩個(gè)集和A1和A2

中

證明如果矩陣A滿足條件（1）和（2）,則力的任意子矩陣仍然滿足條件（1）

和（2）.所以，只需證明當(dāng)/為方陣且滿足條件（1）和（2）時(shí)，det（A）=

0,1或-1即可.下面用數(shù)學(xué)歸納法證明

當(dāng)4為1階方陣時(shí)，顯然=0,1或-1.假設(shè)結(jié)論對(duì)任意（幾-1）階方陣均成立，

下面考慮4為〃階方陣的情形.有且只有以下三種可能：

4的某一列元素全為0,貝lldet（A）=0.

4的某一列元素只有一個(gè)不為0，則det（A）=0,1或-1.

4的每一列均含有兩個(gè)非零元，=Z%，V/=l,2,...，兒

主4ieA29

則det（A）=0.

3.2全么模陣-與網(wǎng)絡(luò)優(yōu)化的關(guān)系

推論（1）一個(gè)有向圖的關(guān)聯(lián)矩陣為全么模矩陣.

（2）一個(gè)無向圖的關(guān)聯(lián)矩陣為全么模矩陣，當(dāng)且僅當(dāng)該

圖為二部圖.

當(dāng)采用整數(shù)規(guī)劃來描述網(wǎng)絡(luò)優(yōu)化問題時(shí)，其約束矩陣一般是有

向圖的關(guān)聯(lián)矩陣或它的簡(jiǎn)單變形，一般都是全么模矩陣.因此

可以認(rèn)為，許多網(wǎng)絡(luò)優(yōu)化問題都是一類特殊的整數(shù)規(guī)劃，其LP

松弛與原問題有相同的最優(yōu)解.

網(wǎng)絡(luò)優(yōu)化處于線性規(guī)劃和整數(shù)規(guī)劃的結(jié)合點(diǎn)上，或者說處于連

續(xù)優(yōu)化和離散優(yōu)化（組合優(yōu)化）的結(jié)合點(diǎn)上.

10

3.3分?jǐn)?shù)割平面法Gomory(1958)

如果給線性規(guī)劃增加一個(gè)約束，則原線性規(guī)劃問題的可行域集

合可能縮小，即可行域相當(dāng)于被“割掉”了一塊.

基本思想：如果給整數(shù)線性規(guī)劃增加一個(gè)線性約束，而沒有

“割掉”其任何可行整數(shù)解，則新問題與原問題有相同的整數(shù)

解.增加的相應(yīng)約束通常被稱為筋^平面(CuttingPlane).

首先用原始單純形法求解整數(shù)線性規(guī)劃(3.2)的LP松弛

(3.1),得到一個(gè)最優(yōu)基本解.設(shè)它對(duì)應(yīng)的基為B,且設(shè)對(duì)應(yīng)

的單純形表中第1個(gè)方程(第/行)為：(i=0,1,2,…,m)

、8(力)+ZjeNByijXj~No

記X5(0)=-Z

對(duì)約束方程兩邊取“地板函數(shù)”(用L」表示)，即取小于或

等于對(duì)應(yīng)的實(shí)數(shù)值的最大整數(shù)值.由于X為非負(fù)整數(shù)，所以

/⑴+Z卜/"l_Xo」

乙⑺+ZjcNByijXj~匕0

分?jǐn)?shù)割平面法-L^zO-

兩式相減：￡六.(為?一必J%/之.Vzo-LZo.

令4=歹「必」，，=0,1,2LM則工jeNBfijXjNfiO.

第i行的Gomory割口^

為了將它加入已經(jīng)得到的單純形表并仍然保持一個(gè)基本解，將

它進(jìn)一步變?yōu)閆jd)Xj+s=-九(3.10)

其中s為引進(jìn)的新變量(非負(fù)).

引理3.1約束(3.10)加入到LP松弛問題的最優(yōu)表之后，沒有

割掉任何整數(shù)可行點(diǎn)；并且當(dāng)九不是整數(shù)時(shí)，新表里是一個(gè)

對(duì)偶基本可行解，但不是原始可行解.

/s與B一起構(gòu)成新的基變量；基本解中s=一九＜。

12

/單純形表第0行不變，所以基本解是對(duì)偶基本可行解.

分?jǐn)?shù)對(duì)偶算法算法(FractionalDualAlgorithm,Gomory,1958)

STEPO.解ILP的LP松弛問題.如果松弛問題無解，則令

feasible=“no”；否則得松弛問題的最優(yōu)解,令feasible=“yes”,

繼續(xù)STEPL

STEP1.如果feasible="no”，則原問題無解，結(jié)束；如果

feasible="yes”且是整數(shù)解，則得到原問題的最優(yōu)解，結(jié)束；

否則繼續(xù)STEP2.

STEP2.選取某行生成割平面；在單純形表中加上生成的Gomory

割(3.10)和對(duì)應(yīng)的基變量s.

STEP3.應(yīng)用對(duì)偶單純形法求解新問題.如果對(duì)偶問題無解，令

feasible=“no”；否則設(shè)為新的當(dāng)前最優(yōu)解.轉(zhuǎn)STEP1.

13

分?jǐn)?shù)對(duì)偶算法算法(FractionalDualAlgorithm,Gomory,1958)

例3.1用分?jǐn)?shù)割平面法求解：maxx2

s.t.35+2X2<6

-35+2X2<0

2￡Z

將其LP松弛問題化為標(biāo)準(zhǔn)形：maxx2=-min(-x2)

s.t.3/+2X2+%=6

—3xj+2+x—0

%1,x2,x3,x4>0

bX]X4

x2x3

-z=00-100

x3=63210

14

%4=0-3201

分?jǐn)?shù)對(duì)偶算法算法(FractionalDualAlgorithm,Gomory,1958)

b%4

%2x3

-z=00-100

二63210

人=0-3201

b%4

x2x3

-z=0-3/2001/2

X3=6601-1

x=0-3/2101/2

b%]

x2x3

XX

-z=3/2001/41/41―3+74—7

巧=1101/6-1/6

X2=3/2011/41/4

分?jǐn)?shù)對(duì)偶算法算法(FractionalDualAlgorithm,Gomory,1958)

分?jǐn)?shù)對(duì)偶算法算法(FractionalDualAlgorithm,Gomory,1958)

bX.X,%,x4x54

-z=1000010

X]=2/3100-1/32/30

X2=1010010

*3=20011-40

X0,—-2/3000-2/3-2/31

X

bX]%2x35%6

-z=1000010

X]=110001-1/2

X2=1010010

x_

Jz—10010-53/2

%4=100011-3/2

得到最優(yōu)解為（1,1）,是整數(shù)解.結(jié)束，原問題最

優(yōu)解為（1,1）,最大值為L(zhǎng)

17

對(duì)分?jǐn)?shù)割平面算法,我們作以下幾點(diǎn)說明

⑴該算法能否保證其有限性，即是否一定在有限步內(nèi)停止?我們知道,線性

規(guī)劃的單純形法可能出現(xiàn)循環(huán)，因此不一定在有限步內(nèi)停止.所以，分?jǐn)?shù)割

平面算法也不一定在有限步內(nèi)停止.但是，當(dāng)在(對(duì)偶)單純形法中采用字典

序反循環(huán)法則時(shí),可以證明分?jǐn)?shù)割平面算法一定在有限步內(nèi)停止.

⑵可以看出，該算法在計(jì)算過程中不斷增加割平面的個(gè)數(shù)，因此約束越來

越多.為了防止割平面?zhèn)€數(shù)任意增加，一般可以作如下處理：如果一個(gè)松弛

變量應(yīng)進(jìn)入基,則將相應(yīng)的行和列從單純形表中去掉，即去掉了對(duì)應(yīng)的割平

面.因此,單純形表中的約束行數(shù)不會(huì)多于變量個(gè)數(shù).

(3)該算法在計(jì)算機(jī)上實(shí)現(xiàn)過程中會(huì)有一點(diǎn)麻煩：由于存在誤差，判定

個(gè)實(shí)數(shù)是否為整數(shù)是比較困難的.為了克服這一困難,人們提出了全整數(shù)算

法.

(4)分?jǐn)?shù)對(duì)偶算法采用對(duì)偶單純形法,在達(dá)到最優(yōu)解之前得不到原問題的

可行解，因此如果計(jì)算時(shí)間過長(zhǎng)而不得不中間停機(jī)時(shí)，結(jié)果往往無法使用.

為了解決這一問題,人們提出了原始整數(shù)割平面算法.

18

3.4分枝定界法（Branchand

Bound）

基本思想：隱式地枚舉一切可行解（組合優(yōu)化）

所謂分枝，就是逐次對(duì)解空間進(jìn)行劃分；而所謂定界，是指對(duì)于

每個(gè)劃分后的解空間（即每個(gè)分枝），要計(jì)算原問題的最優(yōu)解的

下界（對(duì)極小化問題）.這些下界用來在求解過程中判定是否

需要對(duì)目前的解空間（即分枝）進(jìn)一步劃分，也就是盡可能去掉

一些明顯的非最優(yōu)點(diǎn)，從而避免完全枚舉.

定界方法中經(jīng)常采用的有Lagrange松弛方法和線性規(guī)劃松弛方法等

?T

若在某一時(shí)刻，得到mmcxmincTx

一個(gè)全整數(shù)解的費(fèi)用力Ax-bAx-b

為小,則馬,為原問題x>

x>00

的一個(gè)上界；/0

Xj>X：+1X<X

否則得該分枝的一個(gè)

19

下界，繼續(xù)分枝.

分枝定界算法

STEPO.令activeset={0}（原問題）；〃二°°；currentbest=0.

STEP1.如果activeset=0,則已經(jīng)得到原問題的最優(yōu)解,結(jié)束;否

則從活躍分枝點(diǎn)集合activeset中選擇一個(gè)分枝點(diǎn)％將左從

activeset中去掉,繼續(xù)STEP2.

STEP2.生成左的各分枝i=1,2,…,%及其對(duì)應(yīng)的下界孫

STEP3.對(duì)分枝％=12…,%:如果分枝，得到的是全整數(shù)解且召＜4

則令我為且current