6/26/2025第7章整數(shù)規(guī)劃1CONTENTS目錄6/26/20257.1

整數(shù)規(guī)劃問(wèn)題及模型7.2

整數(shù)規(guī)劃的集合和幾何特性7.3

割平面法7.4

分支定界法7.50-1整數(shù)規(guī)劃7.6

啟發(fā)式算法7.7

整數(shù)規(guī)劃案例27.1整數(shù)規(guī)劃問(wèn)題及模型7.1.1整數(shù)規(guī)劃問(wèn)題引例貨物每件體積（立方英尺）每件重量（百千克）每件利潤(rùn)（百元）甲19542乙273403托運(yùn)限制1365（立方英尺）140（百千克）

例7.1某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量，可獲利潤(rùn)以及托運(yùn)所受限制如表7.1所示。甲種貨物至多托運(yùn)4件，問(wèn)兩種貨物各托運(yùn)多少件，可使獲得利潤(rùn)最大。表7.1單位貨物體積、重量及利潤(rùn)6/26/20254

7.1.1整數(shù)規(guī)劃問(wèn)題引例6/26/20255

例7.2（多維背包問(wèn)題）某投資商在計(jì)劃一個(gè)三年期的投資組合，有6個(gè)項(xiàng)目可供選擇。下表7.2給出了這些投資項(xiàng)目的信息，包括每年的支出和預(yù)期的收益，另外每年的可用資金預(yù)算為30，單位均為百萬(wàn)元。請(qǐng)為投資商的項(xiàng)目選擇問(wèn)題建立數(shù)學(xué)模型。7.1.1整數(shù)規(guī)劃問(wèn)題引例6/26/20256表

7.2

投資項(xiàng)目支出與預(yù)期收益

7.1.1整數(shù)規(guī)劃問(wèn)題引例6/26/20257

6/26/20258是一個(gè)0-1整數(shù)規(guī)劃模型。也是多維背包問(wèn)題的數(shù)學(xué)模型。多維背包問(wèn)題(Multi?dimensionalKnapsackProblem,MKP)

7.1.1整數(shù)規(guī)劃問(wèn)題引例6/26/20259

7.1.1整數(shù)規(guī)劃問(wèn)題引例6/26/202510混合整數(shù)線性規(guī)劃模型(MixedIntegerLinearProgram,MILP)該約束也可替換為：整數(shù)規(guī)劃問(wèn)題，可能存在多個(gè)不同數(shù)學(xué)模型。

7.1.1整數(shù)規(guī)劃問(wèn)題引例6/26/2025117.1.1整數(shù)規(guī)劃問(wèn)題引例6/26/202512

子環(huán)消除約束6/26/202513如果沒(méi)有子環(huán)消除約束，可能得到包含多個(gè)子環(huán)的不可行解。7.1.2整數(shù)規(guī)劃的數(shù)學(xué)模型6/26/202514純整數(shù)規(guī)劃：所有決策變量為非負(fù)整數(shù)；全整數(shù)規(guī)劃：所有變量、系數(shù)和常數(shù)均為整數(shù)；0-1整數(shù)規(guī)劃：所有決策變量只能取0獲1兩個(gè)整數(shù)?；旌险麛?shù)規(guī)劃：只有一部分決策變量為非負(fù)整數(shù)，其余變量可為非負(fù)實(shí)數(shù)；例7.5

設(shè)整數(shù)規(guī)劃問(wèn)題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問(wèn)題（一般稱為松弛問(wèn)題）。7.1.3整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系6/26/202515用圖解法求出最優(yōu)解x1＝3/2,x2=10/3且有z=29/6現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個(gè)點(diǎn)，即(1，3)(2，3)(1，4)(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問(wèn)題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問(wèn)題的可行解集是一個(gè)有限集，如圖所示。因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。7.1.3整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系6/26/2025167.2整數(shù)規(guī)劃的集合和幾何特性混合整數(shù)規(guī)劃（MILP）的一般形式：

左邊的問(wèn)題LP是整數(shù)規(guī)劃問(wèn)題IP的線性規(guī)劃松弛，求解該線性規(guī)劃松弛問(wèn)題，可得到整數(shù)規(guī)劃問(wèn)題的一個(gè)對(duì)偶界

(Dualbound)7.2.1整數(shù)規(guī)劃的集合6/26/202518

例7.6

給定如下整數(shù)規(guī)劃問(wèn)題：該整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型的等價(jià)形式為：7.2.2整數(shù)規(guī)劃的幾何特性6/26/202519

其中

例7.6的另外兩個(gè)模型：7.2.2整數(shù)規(guī)劃的幾何特性6/26/202520

模型P3也稱為該整數(shù)規(guī)劃問(wèn)題的凸包

(Convexhull)，它的可行域的每個(gè)頂點(diǎn)都是一個(gè)整數(shù)可行解。6/26/202521思考題：比較無(wú)容量限制的選址問(wèn)題的兩種數(shù)學(xué)模型，有何種關(guān)系？7.3割平面法7.3.1基本思想6/26/202523例7.7

用割平面法求解例7.6中的整數(shù)規(guī)劃問(wèn)題7.3.1基本思想6/26/202524

其中

7.3.1基本思想6/26/202525

7.3.2求解步驟6/26/202526如何計(jì)算所需的有效不等式呢？一種方式是生成

Chvatal?Gomory

割平面。

7.3.3Gomory割平面6/26/202527

6/26/2025287.3.3Gomory割平面

6/26/2025297.3.3Gomory割平面

6/26/2025307.3.3Gomory割平面例7.8

考慮如下整數(shù)規(guī)劃問(wèn)題，得到一組有效不等式。

6/26/2025317.3.3Gomory割平面

6/26/2025327.3.3Gomory割平面

7.3.4Gomory割平面法6/26/202533

7.3.4Gomory割平面法6/26/202534例7.10

用割平面法求解整數(shù)規(guī)劃問(wèn)題解：增加松弛變量x3和x4

，得到(LP)的初始單純形表和最優(yōu)單純形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201－Z00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4－Z-3/200-1/4-1/47.3.4Gomory割平面法6/26/202535此題的最優(yōu)解為：X＊

(1,3/2)，Z=3/2。以x2為源行生成割平面，由于1/4=0+1/4,3/2=1+1/2,我們已將所需要的數(shù)分解為整數(shù)和分?jǐn)?shù)，所以，生成割平面的條件為:也即：6/26/2025367.3.4Gomory割平面法

x1x2⑴⑵33第一個(gè)割平面6/26/2025377.3.4Gomory割平面法Cj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41－Z-3/200-1/4-1/40現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4－Z-10000-16/26/202538此時(shí)，X1

＝(2/3,1),Z=1,仍不是整數(shù)解。繼續(xù)以x1為源行生成割平面，其條件為：用上表的約束解出x4和s1，將它們帶入上式得到等價(jià)的割平面條件：x1≥x2，見(jiàn)圖：x1x2⑴⑵33第一個(gè)割平面第二個(gè)割平面6/26/2025397.3.4Gomory割平面法將生成的割平面條件加入松弛變量，然后加到表中：CBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31－Z-10000-10CBXBbx1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2－Z000010-3/26/26/202540CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2－Z-10000-10

至此得到最優(yōu)表，其最優(yōu)解為X＊=(1,1),Z=1,這也是原問(wèn)題的最優(yōu)解。

有以上解題過(guò)程可見(jiàn)，表中含有分?jǐn)?shù)元素且算法過(guò)程中始終保持對(duì)偶可行性，因此，這個(gè)算法也稱為分?jǐn)?shù)對(duì)偶割平面算法。6/26/202541例7.11

用割平面法求解數(shù)規(guī)劃問(wèn)題Cj1100CBXBbx1x2x3x40x3621100x4204501－Z1100CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/3－Z-13/300－1/6－1/6初始表最優(yōu)表6/26/2025427.3.4Gomory割平面法在松弛問(wèn)題最優(yōu)解中，x1,x2均為非整數(shù)解，由上表有：將系數(shù)和常數(shù)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和6/26/2025437.3.4Gomory割平面法以上兩個(gè)式子右端真分?jǐn)?shù)相等，可任選一個(gè)考慮。現(xiàn)選第二個(gè)式子，并將真分?jǐn)?shù)移到右邊得：引入松弛變量s1后得到下式，將此約束條件加到上表中，繼續(xù)求解。6/26/2025447.3.4Gomory割平面法Cj11000CBXBbx1x2x3x4s11x15/3105/6－1/601x28/301－2/31/300s1－2/300－1/3－1/31－Z－13/300－1/6－1/601x10100－101x240101－20x320011－3－Z－40000－1/2﹡得到整數(shù)最優(yōu)解，即為整數(shù)規(guī)劃的最優(yōu)解，而且此整數(shù)規(guī)劃有兩個(gè)最優(yōu)解：X＊=(0,4),Z=4,或X＊=(2,2),Z=4。6/26/2025457.3.4Gomory割平面法7.4分支定界法

7.4.1基本思路6/26/2025471）先不考慮整數(shù)約束，解(IP)的松弛問(wèn)題(LP)，可能得到以下情況之一：⑴.若(LP)沒(méi)有可行解，則(IP)也沒(méi)有可行解，停止計(jì)算。⑵.若(LP)有最優(yōu)解，并符合(IP)的整數(shù)條件，則(LP)的最優(yōu)解即為(IP)的最優(yōu)解，停止計(jì)算。⑶.若(LP)有最優(yōu)解，但不符合(IP)的整數(shù)條件，轉(zhuǎn)入下一步。為討論方便，設(shè)(LP)的最優(yōu)解為：分支定界法的步驟如下：7.4.2一般步驟6/26/2025482）定界：記(IP)的目標(biāo)函數(shù)最優(yōu)值為Z*,以Z(0)

作為Z*

的上界，記為＝Z(0)

。再用觀察法找的一個(gè)整數(shù)可行解X′，并以其相應(yīng)的目標(biāo)函數(shù)值Z′作為Z*

的下界，記為Z＝Z′，也可以令Z＝－∞，則有：Z≤Z*≤3）分支：在(LP)的最優(yōu)解X(0)中，任選一個(gè)不符合整數(shù)條件的變量，例如xr=（不為整數(shù)），以表示不超過(guò)的最大整數(shù)。構(gòu)造兩個(gè)約束條件

xr≤和xr≥＋1將這兩個(gè)約束條件分別加入問(wèn)題(IP)，形成兩個(gè)子問(wèn)題(IP1)和(IP2)，再解這兩個(gè)問(wèn)題的松弛問(wèn)題(LP1

)和(

LP2

)。7.4.2一般步驟6/26/202549如此反復(fù)進(jìn)行，直到得到Z＝Z*＝為止，即得最優(yōu)解X*

。4）修改上、下界：按照以下兩點(diǎn)規(guī)則進(jìn)行。⑴.在各分枝問(wèn)題中，找出目標(biāo)函數(shù)值最大者作為新的上界；⑵.從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最大者作為新的下界。5）比較與剪枝各分枝的目標(biāo)函數(shù)值中，若有小于Z者，則剪掉此枝，表明此子問(wèn)題已經(jīng)探清，不必再分枝了;否則繼續(xù)分枝。7.4.2一般步驟6/26/202550分支定界法是一種隱枚舉方法（implicitenumeration）或部分枚舉方法，它不是一種有效的算法，是枚舉方法基礎(chǔ)上的改進(jìn)。其關(guān)鍵是分支和定界。例7.12MaxZ=X1+X214X1+9X2

≤51-6X1+3X2

≤1X1

，X2

≥0X1

，X2

取整數(shù)s.t.7.4.2一般步驟6/26/202551分支定界法圖解整數(shù)規(guī)劃例7.12分支定界求解過(guò)程（一）松弛問(wèn)題

MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1

，X2≥0該整數(shù)規(guī)劃松弛問(wèn)題的解為：（X1

，X2）=

（3/2，10/3）Z0=29/67.4.2一般步驟6/26/202552松弛問(wèn)題

MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1

，X2≥0（3/2，10/3）Z0=29/6LP1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≥2X1

，X2≥0LP2MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≤1X1

，X2≥0LP2：解（1，7/3）Z2=10/3LP1：解（2，23/9）Z1=41/9例7.12分支定界求解過(guò)程（二）7.4.2一般步驟6/26/202553（3/2，10/3）Z0=29/6LP1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X1

，X2≥0LP2：解（1，7/3）Z2=10/3LP1：解（2，23/9）Z1=41/9LP11MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2

X2≥3X1

，X2≥0LP12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2

X2≤2X1

，X2≥0LP12：解（33/14，2）Z12=61/14例7.12分支定界求解過(guò)程（三）7.4.2一般步驟6/26/202554（3/2，10/3）Z0=29/6LP2：解（1，7/3）Z2=10/3LP12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X2≤2X1

，X2≥0LP12：解（33/14，2）Z12=61/14LP121MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≥3X2≤2X1

，X2≥0LP122MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≤2X2≤2X1

，X2≥0LP121：解（3，1）Z121=4LP122：解（2，2）Z122=4LP1：解（2，23/9）Z1=41/9例7.12分支定界求解過(guò)程（四）7.4.2一般步驟6/26/202555LP（3/2，10/3）Z0=29/6LP2（1，7/3）Z2=10/3LP1（2，23/9）Z1=41/9LP12（33/14，2）Z12=61/14LP11

無(wú)可行解LP122（2，2）Z122=4LP121

（3，1）Z121=4#LP22（1，2）Z22=3LP21

無(wú)可行解####例7.12分支搜索法流程7.4.2一般步驟6/26/202556LP（3/2，10/3）Z0=29/6LP2（1，7/3）Z2=10/3LP1（2，23/9）Z1=41/9LP12（33/14，2）Z12=61/14LP11

無(wú)可行解LP122（2，2）Z122=4LP121

（3，1）Z121=4#例7.12分支定界法流程7.4.2一般步驟6/26/2025573200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用單純形法解對(duì)應(yīng)的(LP)問(wèn)題,如表所示,獲得最優(yōu)解。初始表最終表例7.13

用分支定界法求解整數(shù)規(guī)劃問(wèn)題（單純形法）7.4.2一般步驟6/26/202558x1=13/4x2=5/2Z(0)=59/4≈14.75

選x2進(jìn)行分枝，即增加兩個(gè)約束，2≥x2≥3有下式：分別在(LP1)和(LP2)中引入松弛變量x5和x6

，將新加約束條件加入上表計(jì)算。即x2+x5=2,－x2+x6=－3

得下表:7.4.2一般步驟6/26/20255932000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2Z(1)=14.5繼續(xù)分枝，加入約束3≥x1≥4LP17.4.2一般步驟6/26/20256032000CB

XB

bx1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/21/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3Z(2)=13.5∵Z(2)<Z(1)∴先不考慮分枝6/26/202561接(LP1)繼續(xù)分枝，加入約束4≤x1≤3，有下式：分別引入松弛變量x7和x8，然后進(jìn)行計(jì)算。7.4.2一般步驟6/26/202562CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3x1=3,x2=2Z(3)=13找到整數(shù)解，問(wèn)題已探明，停止計(jì)算。LP36/26/202563CB

XB

b

x1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1x1=4x2=1Z(4)=14找到整數(shù)解，問(wèn)題已探明，停止計(jì)算。LP46/26/202564樹(shù)形圖如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=13/4,x2=5/2Z(0)

＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)＝13LP4x1=4,x2=1Z(4)＝14x2≤2x2≥3x1≤3x1≥4###7.4.2一般步驟6/26/2025656/26/202566例題：用分支定界發(fā)求解下列模型。6/26/2025676/26/202568樹(shù)形圖如下：6/26/2025697.4.3分支切割法6/26/202570

對(duì)于大規(guī)模整數(shù)規(guī)劃問(wèn)題，通常采用將分支定界法與割平面法相結(jié)合的分支切割法(Branch?and?cutalgorithm)。在探索分支定界樹(shù)時(shí)，對(duì)于每一個(gè)節(jié)點(diǎn)，在計(jì)算當(dāng)前線性規(guī)劃模型后，分支切割法向模型加入當(dāng)前分?jǐn)?shù)解違反的有效不等式，再次求解線性規(guī)劃模型得到更好的對(duì)偶界。由于線性規(guī)劃模型和對(duì)偶界的加強(qiáng)，分支切割法能夠大大提升剪枝效果，減少需要計(jì)算的節(jié)點(diǎn)數(shù)量，提升求解效率。常用的整數(shù)規(guī)劃求解器如COPT、Gurobi、CPLEX和SCIP均實(shí)現(xiàn)了分支切割法。分支切割法需要快速高效地分離出當(dāng)前解違反的有效不等式，接下來(lái)介紹一些常用的有效不等式

。7.4.3分支切割法6/26/202571

7.4.3分支切割法6/26/202572

7.4.3分支切割法6/26/202573

7.50-1整數(shù)規(guī)劃7.50-1整數(shù)規(guī)劃6/26/202575例7.15

求解下列0－1

規(guī)劃問(wèn)題7.5.1建模與求解思想6/26/202576解：對(duì)于0－1規(guī)劃問(wèn)題，由于每個(gè)變量只取0，1兩個(gè)值，一般會(huì)用窮舉法來(lái)解，即將所有的0，1組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。但此法太繁瑣，工作量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上，通過(guò)加入一定的條件，就能較快的求得最優(yōu)解。x1.x2.x3約束條件滿足條件Z值(1)(2)(3)(4)是∨否×(0.0.0)0000∨0(0.0.1)

－1101∨5(0.1.0)2414∨－2(1.0.0)1110∨3(0.1.1)15 ×(1.0.1)0211∨8(1.1.0)3×(1.1.1)26×7.5.1建模與求解思想6/26/202577由上表可知，問(wèn)題的最優(yōu)解為X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1是一個(gè)可行解，為盡快找到最優(yōu)解，可將3x1－2x2＋5x3≥5作為一個(gè)約束，凡是目標(biāo)函數(shù)值小于5的組合不必討論，如下表。x1.x2.x3約束條件滿足條件Z值(0)(1)(2)(3)(4)是∨否×(0.0.0)00000∨0(0.0.1)5－1101∨5(0.1.0)-2×(0.1.1)3×(1.0.0)3×(1.0.1)80211∨8(1.1.0)1×(1.1.1)4×7.5.1建模與求解思想6/26/202578以下討論一般形式的0－1規(guī)劃如何化為標(biāo)準(zhǔn)形式：7.5.2標(biāo)準(zhǔn)0-1整數(shù)規(guī)劃的隱枚舉法求解步驟6/26/202579例7.16

求解下列0－1規(guī)劃問(wèn)題

7.5.2標(biāo)準(zhǔn)0-1整數(shù)規(guī)劃的隱枚舉法求解步驟6/26/202580y1.y2.y3.y4.y5約束條件滿足條件Z值(1)(2)是∨否×(0.0.0.0.0)00×(1.0.0.0.0)1-1×(0.1.0.0.0)-11×(0.0.1.0.0)-21×(0.0.0.1.0)4-4∨8(1.1.0.0.0)00×(1.0.1.0.0)-10×所以，

Y*=（0.0.0.1.0），原問(wèn)題的最優(yōu)解為：X*

＝（0.0.1.0.0），Z*=87.5.2標(biāo)準(zhǔn)0-1整數(shù)規(guī)劃的隱枚舉法求解步驟6/26/202581

7.5.2標(biāo)準(zhǔn)0-1整數(shù)規(guī)劃的隱枚舉法求解步驟6/26/2025827.5.2標(biāo)準(zhǔn)0-1整數(shù)規(guī)劃的隱枚舉法求解步驟6/26/202583

7.5.3指派問(wèn)題6/26/202584分配問(wèn)題（指派問(wèn)題，Assignment

Problem）在實(shí)際當(dāng)中，我們經(jīng)常遇到這樣的問(wèn)題:有"項(xiàng)不同的需要完成，而恰好有n個(gè)員工(或n臺(tái)設(shè)備)可以分別完成其中的一項(xiàng)工作，但由于任務(wù)的性質(zhì)和個(gè)人的專長(zhǎng)不同，不同的人去完成不同的工作產(chǎn)生的效率就不一樣。假設(shè)第i個(gè)員工完成第，項(xiàng)任務(wù)的效率(時(shí)間成本等為c，應(yīng)該派哪一個(gè)員工去完成哪一項(xiàng)工作才能使總的效率最高?6/26/2025857.5.3指派問(wèn)題指派問(wèn)題的模型6/26/2025867.5.3指派問(wèn)題指派問(wèn)題的模型數(shù)據(jù)主要集中在下列系數(shù)矩陣（效益矩陣）中6/26/2025877.5.3指派問(wèn)題6/26/2025887.5.3指派問(wèn)題匈牙利法指派問(wèn)題是0-1規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1規(guī)劃或運(yùn)輸問(wèn)題的解法去求解。利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是匈牙利法，即系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少直線數(shù)。6/26/202589例7.18

有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書(shū)譯成不同語(yǔ)種的說(shuō)明書(shū)所需時(shí)間如下表所示，問(wèn)如何分派任務(wù)，可使總時(shí)間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁59826/26/2025907.5.3指派問(wèn)題第一步，變換系數(shù)矩陣：第二步，作最少的直線覆蓋所有0元素找到3個(gè)獨(dú)立零元素但l＝3<n=4需要進(jìn)一步變換矩陣6/26/2025917.5.3指派問(wèn)題對(duì)每行元素減去該行的最小值，再對(duì)每列元素減去該列的最小值6/26/2025927.5.3指派問(wèn)題即最優(yōu)的分配方案為甲翻譯成俄文，乙翻譯成英文，丙翻譯成日文，丁翻譯成德文在實(shí)際應(yīng)用中，常會(huì)遇到各種非標(biāo)準(zhǔn)形式的制派問(wèn)題。一般的處理方法是先將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后再用匈牙利法求解。最大化指派問(wèn)題——設(shè)最大化指派問(wèn)題系數(shù)矩陣C=(cij)，其中最大元素為m。令矩陣B=(bij)=(m-cij)，則以B為系數(shù)矩陣的最小化指派問(wèn)題和以C為系數(shù)矩陣的最大化指派問(wèn)題有相同最優(yōu)解。人數(shù)和事數(shù)不等的指派問(wèn)題——若人少事多，則添加一些虛擬的“人”，其費(fèi)用系數(shù)取0，若人多事少，則添加一些虛擬的“事”，其費(fèi)用系數(shù)取0。一個(gè)人可做幾件事的指派問(wèn)題——若某個(gè)人可以做幾件事，則將該人化作幾個(gè)“人”來(lái)接受指派。這幾個(gè)“人”做同一件事的費(fèi)用系數(shù)當(dāng)然都一樣。某事一定不能由某人做的指派問(wèn)題——若某事一定不能由某人做，則可將相應(yīng)的費(fèi)用系數(shù)取為足夠大的數(shù)M。6/26/202593非標(biāo)準(zhǔn)形式的指派問(wèn)題7.5.3指派問(wèn)題例7.19

從甲、乙、丙、丁、戊五人中選四人去完成四項(xiàng)任務(wù)，每人完成各項(xiàng)任務(wù)的時(shí)間如下表。規(guī)定每人只能完成一項(xiàng)任務(wù)。由于某種原因，甲必須被分配一項(xiàng)任務(wù)，丁不承擔(dān)第4項(xiàng)任務(wù)，試確定總花費(fèi)時(shí)間最少的分派方案。人任務(wù)甲乙丙丁戊11023159251015243155147154201513686/26/2025947.5.3指派問(wèn)題解：增加虛設(shè)任務(wù)5，各人該項(xiàng)任務(wù)時(shí)間為0，某人不完成某任務(wù)時(shí)，取時(shí)間M（充分大的時(shí)間）：人任務(wù)甲乙丙丁戊11023159251015243155147154201513685M00006/26/2025957.5.3指派問(wèn)題7.6啟發(fā)式算法6/26/2025977.6啟發(fā)式算法整數(shù)規(guī)劃求解算法：精確算法：可以在理論上保證最優(yōu)解；啟發(fā)式算法：從問(wèn)題本身結(jié)構(gòu)出發(fā)，挖掘問(wèn)題相關(guān)要素之間的聯(lián)系，尋找基于直觀或者經(jīng)驗(yàn)的適合解決該問(wèn)題的近似解算法。如果一個(gè)算法求解時(shí)間可以表示為問(wèn)題規(guī)模的多項(xiàng)式函數(shù)，就稱這個(gè)算法為多項(xiàng)式時(shí)間算法。對(duì)于很多組合優(yōu)化問(wèn)題，例如旅行商問(wèn)題、排產(chǎn)問(wèn)題等，已經(jīng)被證明不太可能存在多項(xiàng)式時(shí)間的精確算法。啟發(fā)式算法一般都能在合理時(shí)間內(nèi)給出問(wèn)題的滿意解，其與問(wèn)題最優(yōu)解之間的差距不會(huì)太大。因此，啟發(fā)式算法在實(shí)際生產(chǎn)環(huán)境中有著廣泛的應(yīng)用。6/26/2025987.6.1啟發(fā)式算法的一般原則(1)保證時(shí)間可用。啟發(fā)式算法相對(duì)于精確解算法最大的優(yōu)勢(shì)就在于它的速度，在設(shè)計(jì)啟發(fā)式算法的時(shí)候，一定要關(guān)注求解時(shí)間，盡可能提升求解效率。(2)保證解的質(zhì)量。為了能夠得到滿意解，需要啟發(fā)式算法在迭代的過(guò)程中及時(shí)掌握解的變化，并做在啟發(fā)策略上做出對(duì)應(yīng)的調(diào)整，否則很容易陷入局部最優(yōu)解。(3)保證穩(wěn)定性。啟發(fā)式算法大多會(huì)從一個(gè)初始解開(kāi)始迭代生成滿意解，必須保證設(shè)計(jì)的啟發(fā)式算法在大多數(shù)初始解下都能夠穩(wěn)定得到滿意解。(4)盡量保證通用性和可移植性。盡管啟發(fā)式算法都是針對(duì)某一特定問(wèn)題設(shè)計(jì)的，但是在設(shè)計(jì)時(shí)仍然要考慮針對(duì)該問(wèn)題的變種或者類似問(wèn)題，相似的啟發(fā)式框架和策略仍然能夠得到滿意解。6/26/2025997.6.2領(lǐng)域搜索算法鄰域搜索算法屬于啟發(fā)式算法的一種，其核心思想是：

對(duì)于當(dāng)前解，通過(guò)鄰域動(dòng)作，形成其鄰域，再根據(jù)一定的選取策略，從鄰域中選取新的當(dāng)前解，通過(guò)對(duì)解的局部調(diào)整不斷優(yōu)化算法結(jié)果。在鄰域搜索算法中，每一次迭代的當(dāng)前解都有其對(duì)應(yīng)的鄰域。鄰域是根據(jù)鄰域結(jié)構(gòu)定義的，通過(guò)對(duì)當(dāng)前解進(jìn)行變換得到的解的集合。要實(shí)現(xiàn)對(duì)當(dāng)前解進(jìn)行變化就需要用到算子。算子是將一個(gè)元素在向量空間中轉(zhuǎn)換為另一個(gè)元素的映射。算子的設(shè)計(jì)和實(shí)現(xiàn)是鄰域搜索算法設(shè)計(jì)中非常重要的一環(huán)，它決定了算法搜索的范圍，對(duì)算法的好壞有著最直接的影響。6/26/20251007.6.2領(lǐng)域搜索算法鄰域搜索的迭代步驟：Step1：建立一個(gè)初始解作為當(dāng)前解。Step2：利用鄰域動(dòng)作生成當(dāng)前解的鄰域，根據(jù)選取策略，在鄰域中選取新的解作為當(dāng)前解。Step3：若當(dāng)前解優(yōu)于當(dāng)前找到的最好解，則更新當(dāng)前找到的最好解。Step4：若達(dá)到停止條件，則停止計(jì)算并輸出最好解；否則返回Step2。常見(jiàn)的兩種停止條件：(1) 迭代次數(shù)超過(guò)閾值：提前設(shè)定最大迭代次數(shù)，在迭代次數(shù)到達(dá)最大時(shí)停止計(jì)算。(2) 目標(biāo)函數(shù)值的改善小于閾值：每次更新最優(yōu)解時(shí)，計(jì)算與上一次最優(yōu)解的差距，若改善量小于設(shè)定的閾值，則停止計(jì)算。6/26/20251017.6.3

求解旅行商問(wèn)題的鄰域搜索算法旅行商問(wèn)題（TravellingSalesmanProblem，TSP）：

給定若干個(gè)城市及兩兩城市間的距離，要求幫助一個(gè)旅行商選擇一條路徑，使得旅行商能夠從其中一個(gè)城市出發(fā)，經(jīng)過(guò)所有的城市，并且每個(gè)城市只能訪問(wèn)一次，最后返回出發(fā)的城市。路徑選擇的目標(biāo)是使得旅行商經(jīng)過(guò)的路徑距離之和最短。例7.20

含八個(gè)城市的TSP問(wèn)題，城市具體坐標(biāo)如下表所示：6/26/20251027.6.3

求解旅行商問(wèn)題的鄰域搜索算法(1)構(gòu)造初始解

使用隨機(jī)的方式構(gòu)造初始解，本題初始解按城市標(biāo)號(hào)遞增構(gòu)造，即1?2?3?4?5?6?7?8?1。通過(guò)計(jì)算，初始解的總路程為