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

第3章整數(shù)規(guī)劃主要介紹三種方法：1、分支定界法（branchandboundmethod）2、割平面法（cuttingplaneapproach）3、匈牙利法第3章整數(shù)規(guī)劃§3.1

整數(shù)規(guī)劃模型介紹§3.2

分支定界法§3.3

割平面法§3.4

匈牙利算法3§3.1

整數(shù)規(guī)劃模型介紹

整數(shù)規(guī)劃的一般形式（IP）問題Max（min）z=∑cjxj∑aijxj

≤（或=，≥）bii=1，2，…，mxj

≥0j=1，2，…，nxj

Zs.t.（LIP）松弛問題Max（min）z=∑cjxj∑aijxj

≤（或=，≥）bii=1，2，…，mxj

≥0j=1，2，…，ns.t.4§3.1

整數(shù)規(guī)劃模型介紹（IP）問題與（LIP）問題關(guān)系（Min）1.(IP)問題的值

(LIP)問題的最優(yōu)值。2.(LIP)問題最優(yōu)解若是整數(shù)，則一定是(IP)問題的最優(yōu)解。5§3.1

整數(shù)規(guī)劃模型介紹整數(shù)規(guī)劃分類純整數(shù)線性規(guī)劃：決策變量都取整數(shù)值?；旌险麛?shù)線性規(guī)劃：決策變量中一部分取整數(shù)值，另一部分可以不取整數(shù)值。0-1整數(shù)線性規(guī)劃：決策變量只能取值0或1

。

6§3.1

整數(shù)規(guī)劃模型介紹整數(shù)規(guī)劃引例背包問題廠址選擇問題

組合投資問題（見教材107-108頁）

Return7§3.2分支定界法

分支定界法是一種隱枚舉方法或部分枚舉方法，是枚舉方法基礎(chǔ)上的改進(jìn)，是組合優(yōu)化重要方法。其關(guān)鍵是分支和定界。例1

MinZ=-2X1-3X25X1+7X2≤354X1+9X2≤36X1

，X2≥0X1

，X2

Z8解：先求相應(yīng)線性規(guī)劃的最優(yōu)解，為：取分割可行域，得到子問題Sub-1,Sub-2：

§3.2分支定界法Sub-2 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≥3x1x2≥0Sub-1 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1x2≥09§3.2分支定界法Sub-1的最優(yōu)解為：取

分割可行域，得到兩個(gè)子問題Sub-3,Sub-4

：Sub-3 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≤4x1x2≥0Sub-4 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x1x2≥010§3.2分支定界法Sub-3的最優(yōu)解為：獲得整數(shù)解，取得上界

，停止分枝！11§3.2分支定界法Sub-4的最優(yōu)解為：Sub-6 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≥2x1x2≥0Sub-5 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≤1x1x2≥0取

分割可行域，得到兩個(gè)子問題：Sub-5,Sub-612§3.2分支定界法Sub-5的最優(yōu)解為：取

分割可行域，得到兩個(gè)子問題：Sub-7,Sub-8Sub-7 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≤1x1≥5x1x2≥0Sub-8 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≤1x1≥6x1x2≥013§3.2分支定界法Sub-6的可行域是空集，停止分枝。Sub-7的最優(yōu)解為：獲得整數(shù)解，停止分枝！由于上界仍保持為14§3.2分支定界法Sub-8的最優(yōu)解為：取

分割可行域，得到兩個(gè)子問題：Sub-9,Sub-10Sub-10 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≤1x1≥6x2≤1x1x2≥0Sub-9 minz=-2x1-3x2 5x1+7x2≤354x1+9x2≤36x2≤2x1≥5x2≤1x1≥6x2≤0x2≥015§3.2分支定界法Sub-9的最優(yōu)解為：獲得整數(shù)解，停止分枝！由于上界仍保持為16§3.2分支定界法Sub-10的可行域是空集，停止分枝!

17§3.2分支定界法Sub-2的最優(yōu)解為：

，停止分支！18§3.2分支定界法

至此已將所有可能分解的子問題都已分解到底，最后得到兩個(gè)目標(biāo)函數(shù)值相等的最優(yōu)整數(shù)解：

（x1，x2）=（4，0）和（x1，x2）=(0，7)

他們的目標(biāo)函數(shù)值都是-14。Return原問題Sub-1Sub-2Sub-3Sub-4Sub-5Sub-6Sub-7Sub-8Sub-9Sub-10剪枝(4,2)，-14(5,1)，-13無可行解(7,0)，-14無可行解19§3.3

割平面法割平面法思想

求解(IP)的松馳問題(LIP)：若最優(yōu)解X*Z，則從X*的非整分量中選取一個(gè)構(gòu)造線性約束（Gomory割平面），將其加入原(LIP)問題，形成一個(gè)新的線性規(guī)劃并求解，（重復(fù)），直至得到整數(shù)最優(yōu)解。

關(guān)鍵：新增的線性約束將切割掉部分非整數(shù)解，至少切割掉當(dāng)前松馳問題的非整數(shù)最優(yōu)解，而不會切割掉問題的任何整數(shù)解!20§3.3

割平面法

構(gòu)造割平面的步驟：1、令xi

是(LIP)問題最優(yōu)解中非整數(shù)值的一個(gè)基變量，得：

xi+∑aikxk=bi……………（1）其中，k∈B（B：非基變量下標(biāo)集）21§3.3

割平面法構(gòu)造割平面的步驟：2、將bi

和aik

分解成整數(shù)部分I（不超過b的最大整數(shù)）與非負(fù)真分?jǐn)?shù)部分F之和：

bi=Ii+Fi

，其中0＜Fi

＜1……………..(2)aik=Iik+Fik

，其中0≤Fik

＜122§3.3

割平面法

構(gòu)造割平面的步驟：3、將（2）代入（1）：

xi+∑Iikxk-Ii=Fi-∑Fikxk……（3）4、割平面方程：

Fi-∑Fikxk≤0……（4）！將（4）加入原來(LIP)問題繼續(xù)求解。23§3.3

割平面法例2

用割平面法求解下列整數(shù)規(guī)劃。IPMinZ=3X1+4X23X1+X2≥4X1+2X2≥4X1

，X2≥0X1

，X2

ZLIPMinZ=3X1+4X23X1+X2≥4X1+2X2≥4X1

，X2≥0

24§3.3

割平面法解:（1）先求解線性規(guī)劃問題（LIP），得到最優(yōu)單純形表：Cj3400I表CBXBB–1

bX1X2X3X40X3431-100X44120-1

j03400B表1X14/510-2/51/51X28/5011/5-3/5

j44/500-2/5-9/525§3.3

割平面法(2)選擇一個(gè)非整數(shù)的基變量，例如x2=8/5，構(gòu)造割平面。增加松弛變量x5后將這個(gè)約束加到線性規(guī)劃的最優(yōu)單純形表，得到b2=8/5=1+3/5，I2=1，F(xiàn)2=3/5a23=1/5=0+1/5，I23=0，F(xiàn)23=1/5a24=-3/5=-1+2/5，I24=-1，F(xiàn)24=2/526§3.3

割平面法(3)求解新的松弛問題Cj110001表CBXBB–1

bX1X2X3X4X51X14/510-2/51/501X28/5011/5-3/500X5-3/500[-1/5]-11

j44/500-2/5-9/502表1X121001-21X21010-110X330012-5

j10000-1-227§3.3

割平面法

整數(shù)規(guī)劃最優(yōu)解線性規(guī)劃

最優(yōu)解切割約束最優(yōu)解：x1=2,x2=1Return28§3.4

匈牙利算法0-1變量只取0或1，常被用來表示系統(tǒng)是否處于某個(gè)特定的狀態(tài)，或者是否取某個(gè)特定的決策方案。如xj=1當(dāng)方案Sj被選中0否則29§3.4

匈牙利算法0-1整數(shù)規(guī)劃例3

選址問題

WAL-MART擬在常州的天寧、鐘樓、新區(qū)建立分店，有7個(gè)位置（地點(diǎn)）Ai（i=1，2，…，7）供選擇。總部規(guī)定在天寧，由A1，A2，A3

三個(gè)點(diǎn)中至多選兩個(gè)；在鐘樓，由A4，A5

兩個(gè)點(diǎn)中至少選一個(gè)；在新區(qū)，由A6，A7

兩個(gè)點(diǎn)中至少選一個(gè)。如果選Ai

點(diǎn)，設(shè)備投資為ai

元，每年可獲利潤為ci

元，但投資總額不能超過A元。問公司選擇哪幾個(gè)點(diǎn)可使年總利潤最大？30§3.4

匈牙利算法解：建立模型引入0-1變量1當(dāng)Ai

點(diǎn)被選用

0否則xi=（i=1，2，…，7）maxz=∑cixi∑aixi≤Ax1+x2+x3≤2x4+x5≥1x6+x7≥1xi

{0，1}31§3.4

匈牙利算法例4

指派問題（assignmentproblem）

有n個(gè)人和n件事，已知第i人做第j事的費(fèi)用為cij（i，j=1，2，…，n），要求確定人和事之間的一一對應(yīng)的指派方案，使完成這件事的總費(fèi)用最少。如任務(wù)人員ABCD甲乙丙丁312971441481317161141513932§3.4

匈牙利算法解：建立模型

令1當(dāng)指派第i人完成第j項(xiàng)任務(wù)

0否則xij=minz=∑∑cijxij∑xij=1，j=1，2，…，n∑xij=1，i=1，2，…，nxij

{0，1}33§3.4

匈牙利算法匈牙利算法

1955年，庫恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格（D.K?nig）的關(guān)于矩陣中獨(dú)立零元素的定理，提出了求解指派問題算法——匈牙利算法。34§3.4

匈牙利算法

【性質(zhì)】

若從指派問題的系數(shù)矩陣C=（cij

）n×n的某行（或某列）各元素分別減去一個(gè)常數(shù)k

，得到一個(gè)新的系數(shù)矩陣C’=（c’ij

）則以C和C’為系數(shù)矩陣的兩個(gè)指派問題有相同的最優(yōu)解。35§3.4

匈牙利算法算法步驟（1）變換系數(shù)矩陣C，使每行及每列至少有一個(gè)零元素，同時(shí)不出現(xiàn)負(fù)元素。（2）確定獨(dú)立零元素組。若|獨(dú)立零元素組|=n，結(jié)束；否則，轉(zhuǎn)步驟（3）。（3）繼續(xù)變換系數(shù)矩陣，然后返回步驟（2）。36§3.4

匈牙利算法例5求解下列指派問題（教材121頁）。2151341041415914161378119013112601011057401422497min（cij

）=37§3.4

匈牙利算法例5（續(xù)）013112601011047401420042min01370606905320100=（c’ij

）38§3.4

匈牙利算法例5（續(xù)）01370606905320100此時(shí)圈0元素的個(gè)數(shù)m=n=4.39§3.4

匈牙利算法例5（續(xù)）00010100

10000010（xij

）=最優(yōu)分配：40§3.4

匈牙利算法例6求下列指派問題（教材122頁）。任務(wù)人員ABCDE甲乙丙丁戊128715479171410961267761461096910941§3.4

匈牙利算法例6（續(xù)）解：1279798966671712149151466104107109767645020223000010572980040636542§3.4

匈牙利算法例6（續(xù)）50202230000105729800406365

此時(shí)圈0元素（獨(dú)立零元素）的個(gè)數(shù)m=4<n=5，不能確定最優(yōu)指派方案！需要繼續(xù)變換系數(shù)矩陣，以增加獨(dú)立零元素個(gè)數(shù)。方法如下：43§3.4

匈牙利算法例6（續(xù)）對未加圈0的行打√號；對所有打√號行的所有含0的列打√號；對已打√號的列中含0的行打√號；重復(fù)2)和3)，直到無可以打√號行或列為止；對未打√號的行畫一橫線，對打√號的列畫一豎線，即得能覆蓋所有0的最少直線數(shù)目的直線集合。44§3.4

匈牙利算法例6（續(xù)）50202230000105729800406365√√√45§3.4

匈牙利算法例6（續(xù)）繼續(xù)變換系數(shù)矩陣：

在未被直線覆蓋的元素中找出一個(gè)最小元素在打√號行各元素都減去這一最小元素，在打√號列的各元素都加上這一最小元素（以保證0元素不變），得新系數(shù)矩陣。若得到n個(gè)獨(dú)立的0元素，則獲最優(yōu)解；否則，重復(fù)上步驟繼續(xù)變換系數(shù)矩陣。46§3.4

匈牙利算法例6（續(xù)）50202230000105729800406365√√√最小元素=27020243