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

第五章整數(shù)規(guī)劃整數(shù)規(guī)劃數(shù)學(xué)模型純整數(shù)規(guī)劃的求解0－1規(guī)劃的求解分支定界法割平面法指派問題非標(biāo)準(zhǔn)形式的指派問題一、整數(shù)規(guī)劃的模型很多實際規(guī)劃問題都屬于整數(shù)規(guī)劃問題1.變量是人數(shù)、機器設(shè)備臺數(shù)或產(chǎn)品件數(shù)等都要求是整數(shù)；2.對某一個項目要不要投資的決策問題，可選用一個邏輯變量x，當(dāng)x=1表示投資，x=0表示不投資；3.人員的合理安排問題，當(dāng)變量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。邏輯變量也是只允許取整數(shù)值的一類變量。例合理下料問題設(shè)用某型號的圓鋼下零件A1,

A2,…,Am的毛坯。在一根圓鋼上下料的方式有B1,B2,…Bn種，每種下料方式可以得到各種零件的毛坯數(shù)以及每種零件的需要量，如表所示。問怎樣安排下料方式，使得即滿足需要，所用的原材料又最少？零件方個數(shù)式零件零件毛坯數(shù)設(shè)：xj

表示用Bj(j=1.2…n)種方式下料根數(shù)模型：零件方個數(shù)式零件零件毛坯數(shù)單銷地廠址價生產(chǎn)能力建設(shè)費用銷量例某公司計劃在m個地點建廠，可供選擇的地點有A1,A2…Am，他們的生產(chǎn)能力分別是a1,a2,…am（假設(shè)生產(chǎn)同一產(chǎn)品）。第i個工廠的建設(shè)費用為fi

(i=1.2…m),又有n個地點B1,B2,…Bn需要銷售這種產(chǎn)品，其銷量分別為b1.b2…bn

。從工廠運往銷地的單位運費為Cij。試決定應(yīng)在哪些地方建廠，即滿足各地需要，又使總建設(shè)費用和總運輸費用最省？設(shè)：

xij

表示從工廠運往銷地的運量(i=1.2…m、j=1.2…n),1在Ai建廠又設(shè)Yi＝（i=1.2…m）0不在Ai建廠模型：例機床分配問題設(shè)有m臺同類機床，要加工n種零件。已知各種零件的加工時間分別為a1,a2,…an，問如何分配，使各機床的總加工任務(wù)相等，或者說盡可能平衡。設(shè)：1分配第i臺機床加工第j種零件；

xij＝（i=1.2…m,j=1.2…n）0相反。于是，第i臺機床加工各種零件的總時間為：又由于一個零件只能在一臺機床上加工，所以有

因此，求xij，使得例投資項目選取問題

某單位擬利用閑置資金15

萬元進行對外投資，現(xiàn)有5個投資項目可供選擇，所需資金及投資回報收益期望值為項目所需資金（萬元）收益期望值（萬元）

ABCDE

64245

108769A，B，C，D，E之間的關(guān)系是：①A、C、E三項中需且只能選一項；②B、D兩項中需且只能選一項；③選C必須先選D。問題：如何選擇投資決策，使總投資期望值最大？解用xj分別表示A，B，C，D，E的被選情況，則于是投資總收益期望值：約束條件：①資金總額限制：②A，C，E選且只選一項：項目所需資金（萬元）收益期望值（萬元）

ABCDE

64245

108769④選C必須先選D：于是數(shù)學(xué)模型為以下0－1規(guī)劃：T31x=,41x=T,40x=30x=或③B，D選且只選一項：例某人有一背包可以裝10公斤重、0.025m3的物品。他準(zhǔn)備用來裝甲、乙兩種物品，每件物品的重量、體積和價值如表所示。問兩種物品各裝多少件，所裝物品的總價值最大？解設(shè)甲、乙兩種物品各裝x1、x2件，則數(shù)學(xué)模型為：物品重量(公斤/每件)體積(m3/每件)價值(元/每件)甲乙1.20.80.0020.002543例在上例中，假設(shè)此人還有一只旅行箱，最大載重量為12公斤，其體積是0.02m3。背包和旅行箱只能選擇其一，建立下列幾種情形的數(shù)學(xué)模型，使所裝物品價值最大。(1)所裝物品不變；(2)如果選擇旅行箱，則只能裝載丙和丁兩種物品，價值分別是4和3，載重量和體積的約束為解此問題可以建立兩個整數(shù)規(guī)劃模型，但用一個模型描述更簡單。引入0－1變量yi，令i=1,2分別是采用背包及旅行箱裝載。由于所裝物品不變,上例約束左邊不變,整數(shù)規(guī)劃數(shù)學(xué)模型為(2)

不同載體所裝物品不一樣，數(shù)學(xué)模型為

M為充分大的正數(shù)?？芍?dāng)使用背包時(y1=1，y2=0)，式(b)和(d)是多余的；當(dāng)使用旅行箱時(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令(1)右端常數(shù)是k個值中的一個時，約束條件為(2)對于m組條件中有k（≤m）組起作用時，約束條件寫成這里yi=1表示第i組約束不起作用，yi=0表示第i個約束起作用。當(dāng)約束條件是“≥”符號時右端常數(shù)項應(yīng)為(3)對于m個條件中有k(≤m)個起作用時，約束條件寫成一般地:同樣可以討論對于有m個條件互相排斥、有m(≤m、≥m)個條件起作用的情形。例試引入0－1變量將下列各題分別表達為一般線性約束條件:(1)x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20;(2)若x1≤5，則x2≥0，否則x2≤8;(3)x1取值0，1，3，5，7。解(1)3個約束只有1個起作用或(3)右端常數(shù)是5個值中的1個(2)兩組約束只有一組起作用(2)若x1≤5，則x2≥0，否則x2≤8;(3)x1取值0，1，3，5，7。整數(shù)規(guī)劃的數(shù)學(xué)模型一般形式依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0－1整數(shù)規(guī)劃。純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整數(shù)（這時引進的松弛變量可以不要求取整數(shù)）。全整數(shù)規(guī)劃：除了所有決策變量要求取非負(fù)整數(shù)外，系數(shù)aij和常數(shù)bi也要求取整數(shù)（這時引進的松弛變量也必須是整數(shù)）?；旌险麛?shù)規(guī)劃：只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實數(shù)。0－1整數(shù)規(guī)劃：所有決策變量只能取0或1兩個整數(shù)。整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系

從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎(chǔ)上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實際上兩者卻有很大的不同，通過舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時甚至不能保證所得到的解是整數(shù)可行解。例：設(shè)整數(shù)規(guī)劃問題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。用圖解法求出最優(yōu)解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個點即(1，3)(2，3)(1，4)(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如圖所示。

因此，可將集合內(nèi)的整數(shù)點一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。如上例：其中（2，2）（3，1）點為最大值，Z=4。

目前，常用的求解整數(shù)規(guī)劃的方法有：

分支定界法和割平面法；對于特別的0－1規(guī)劃問題采用隱枚舉法和匈牙利法。分支定界法是一種隱枚舉法或部分枚舉法，是枚舉法基礎(chǔ)上的改進。分支定界法的關(guān)鍵是分支和定界。“分支”為整數(shù)規(guī)劃最優(yōu)解的出現(xiàn)創(chuàng)造了條件，而“定界”則可以提高搜索的效率。

所謂“定界”，是在分支過程中，若某個后繼問題恰巧獲得整數(shù)規(guī)劃問題的一個可行解，那么，它的目標(biāo)函數(shù)值就是一個“界限”，可作為衡量處理其它分支的一個依據(jù)。

若整數(shù)規(guī)劃的松馳問題的最優(yōu)解不符合整數(shù)要求，不妨假設(shè)不符合整數(shù)要求,則可構(gòu)造兩個約束條件和如此不斷繼續(xù)，直到獲得整數(shù)規(guī)劃的最優(yōu)解。這就是所謂的“分支”分支定界法基本思想：切割可行域，去掉非整數(shù)點。一次分枝變成兩個可行域，分別求最優(yōu)解.通過對松弛問題的分枝，不斷降低（IP）最優(yōu)值的上界，提高下界，當(dāng)上界等于下界時，得到最優(yōu)解。1求解純整數(shù)規(guī)劃的分支定界法IP的松馳問題：②檢驗與分支：①求解LP:③求解LP1,LP2

：設(shè)其解及最優(yōu)值分別為故對LP1剪支.的最優(yōu)值均滿足：(i)如則LP1及由LP1分支的所有子問題剪支及上下界改進分析(ii)如滿足IP的要求時，則當(dāng)是IP的可行解，故改進下界同理，此時LP1剪支.注意到IP的最優(yōu)解必是LP1或LP2的可行解,于是或改進上界：④對中不滿足IP整數(shù)要求的分量，繼續(xù)分支.例用分支定界法求解下列整數(shù)規(guī)劃模型：解先求對應(yīng)的松弛問題(記為LP0)：

用圖解法得到最優(yōu)解X＝（3.57,7.14）,Z0=35.7,如下圖所示:8.3310松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC101010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5①②1010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336①②LP1:X=(3,7.6),Z1=34.81010x1x2oACLP1346①②LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP1:X=(3,7.6),Z1=34.8LP3LP5盡管LP1的解中x1不為整數(shù)，但Z5>Z1因此LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。上述分枝過程可用下圖表示LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)

Z1=34.8LP2:X=(4,6.5)

Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)

Z3=35.33x2≤6LP4:X=(4,6)

Z4=34LP5:X=(5,5)

Z5=35x1≤4x1≥5無可行解x2≥7例用分枝定界法求解整數(shù)規(guī)劃問題（用圖解法計算）記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題記為（LP）用圖解法求（LP）的最優(yōu)解，如圖所示。x1x2⑴⑵33(18/11,40/11)⑶對于x1＝18/11≈1.64，取值x1≤1，x1≥2對于x2=40/11≈3.64，取值x2

≤3，x2

≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。有下式：現(xiàn)在只要求出（LP1）和（LP2）的最優(yōu)解即可。x1x2⑴⑵33(18/11,40/11)⑶

先求（LP1）,如圖所示。此時B在點取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數(shù)解，問題已探明，此枝停止計算。11同理求（LP2）,如圖所示。在C點取得最優(yōu)解。即x1＝2,x2=10/3,Z(2)＝－56/3≈－18.7∵Z2<Z1＝－16∴原問題有比（－16）更小的最優(yōu)解，但x2不是整數(shù)，故利用BAC加入條件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）的最優(yōu)解即可。x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如圖所示。此時D在點取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4<Z≈-19.8但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即3≤x1≤2。D求（LP4），如圖所示。無可行解，不再分枝。在（LP3）的基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1≤2有下式：只要求出（LP5）和（LP6）的最優(yōu)解即可。x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如圖所示。此時E在點取得最優(yōu)解。即x1＝2,x2=3,Z(5)＝－17找到整數(shù)解，問題已探明，此枝停止計算。E求（LP6），如圖所示。此時F在點取得最優(yōu)解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F如對Z(6)繼續(xù)分解，其最小值也不會低于－15.5，問題探明,剪枝。至此，原問題（IP）的最優(yōu)解為：

x1=2，x2=3,

Z*=Z(5)

＝－17以上的求解過程可以用一個樹形圖表示如右：LP1x1=1,x2=3Z(1)＝－16LPx1=18/11,x2=40/11Z(0)＝－19.8LP2x1=2,x2=10/3Z(2)＝－18.5LP3x1=12/5,x2=3Z(3)＝－17.4LP4無可行解LP5x1=2,x2=3Z(5)＝－17LP6x1=3,x2=5/2Z(6)＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃用分枝定界法求解整數(shù)規(guī)劃問題LP1x1=1,x2=7/3Z(1)＝10/3LPx1=3/2,x2=10/3Z(0)＝29/6LP2x1=2,x2=23/9Z(2)＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)＝3LP6無可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)＝61/14LP4無可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)＝4LP8x1=3,x2=1Z(8)＝4x1≤2x1≥3＃＃LP1x1=1,x2=7/3Z(1)＝10/3LPx1=2/3,x2=10/3Z(0)＝29/6LP2x1=2,x2=23/9Z(2)＝41/9LP3x1=33/14,x2=2Z(3)＝61/14LP4無可行解LP7x1=2,x2=2Z(7)＝4LP8x1=3,x2=1Z(8)＝4x1≤1x1≥2x2≤2x2≥3x1≤2x1≥3＃＃＃＃3200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用單純形法解對應(yīng)的(LP)問題,如表所示,獲得最優(yōu)解。初始表最終表例用分枝定界法求解整數(shù)規(guī)劃問題（單純形法）x1=13/4

x2=5/2Z(0)=59/4≈14.75

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

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

得下表:32000CB

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=2

Z(1)=29/2=14.5繼續(xù)分枝，加入約束

3≥x1≥4LP132000CB

XB

b

x1x2x3x4x63x113/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/2

1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3

Z(2)=27/2=13.5∵Z(2)<Z(1)∴先不考慮分枝接(LP1)繼續(xù)分枝，加入約束4≤x1≤3，有下式：分別引入松弛變量x7和x8，然后進行計算。CB

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=2

Z(3)=13找到整數(shù)解，問題已探明，停止計算。LP3CB

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=4,x2=1

Z(4)=14找到整數(shù)解，問題已探明，停止計算。LP4樹形圖如下：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＃＃＃練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問題

（單純形法）cj-1-5000cBxBbx1x2x3x4x50x32-111000x4

30560100x5410001-Z-1-5000cj-1-5000cBxBbx1x2x3x4x5-5x240/11011/115/110-1x1

18/11101/11-6/1100x526/1100-1/116/111-Z218/11006/1119/110LP1x1=1,x2=3Z(1)＝－16LPx1=18/11,x2=40/11Z(0)＝－19.8LP2x1=2,x2=10/3Z(2)＝－18.5LP3x1=12/5,x2=3Z(3)＝－17.4LP4無可行解LP5x1=2,x2=3Z(5)＝－17LP6x1=3,x2=5/2Z(6)＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃先不考慮整數(shù)約束，按一般線性規(guī)劃問題求其最優(yōu)解，線性規(guī)劃問題的最優(yōu)基本可行解是解集的一個極點，這個極點的的坐標(biāo)未必都是整數(shù)，若不是整數(shù)解，可增加一條約束，相當(dāng)于增加一個平面將這個極點割掉，稱這種方法為割平面法。割平面法的基本思想例求解整數(shù)線性規(guī)劃問題

CB

sOAx1

x2解引入松馳變量將其化為標(biāo)準(zhǔn)形式，利用單純形法求其最優(yōu)解。最優(yōu)單純形表如下

從最優(yōu)單純形表中看出約束條件變成

變形得上式分別記為

都應(yīng)小于等于0的整數(shù)。引進多余變量

1100

111

00.2500100.252.752.500-0.25-0.25

用對偶單純形法求解

110000

1100100.250000100.250000-0.25010000-0.25012.752.5-0.75-0.5

00-0.25-0.2500

取i=3為主元行,k=3為主元列,進行換基迭代。再取i=4為主元行，k=4為主元列，進行換基迭代得表。

110000

11001000100100010010-4000010-422320000-1-1

最優(yōu)基本可行解為：

設(shè)純整數(shù)規(guī)劃松弛問題的最優(yōu)解2求解IP的割平面法單純形法最終表設(shè)xi不為整數(shù)，將分離成一個整數(shù)與一個非負(fù)真分?jǐn)?shù)之和：則有上式兩邊都為整數(shù)并且有加入松弛變量si得此式稱為以xi行為源行(來源行)的割平面，或分?jǐn)?shù)切割式，或R.E.Gomory(高莫雷)約束方程。將Gomory約束方程加入到松弛問題的最優(yōu)表中，用對偶單純形法計算，若最優(yōu)解中還有非整數(shù)解，再繼續(xù)切割，直到全部為整數(shù)解。則例如，x1行：移項：令加入松弛變量s1得同理，對于x2行有：例用割平面法求解下列IP問題解放寬變量約束，對應(yīng)的松弛問題是加入松弛變量x3及x4后，用單純形法求解，得到最優(yōu)表

最優(yōu)解X(0)＝(5/2，15/4),不是IP的最優(yōu)解。選擇表的第一行(也可以選第二行)為源行Cj4300bCBXBx1x2x3x443x1x210011/4－1/8－1/23/45/215/4λj00－5/8－1/4分離系數(shù)后改寫成加入松弛變量x5得到高莫雷約束方程將上式作為約束條件添加到上表中，用對偶單純形法計算，如表所示:Cj43000bCBXBx1x2x3x4x5430x1x2x51000101/4－1/8－1－1/23/4[－2]0015/215/4－2→λj00－5/8－1/4↑0430x1x2x41000101/2－1/21/2001－1/43/8－1/2331λj00－1/20－1/8最優(yōu)解X(1)＝(3，3)，最優(yōu)值Z＝21。所有變量為整數(shù)，X(1)就是IP的最優(yōu)解。如果不是整數(shù)解，需要繼續(xù)切割，重復(fù)上述計算過程。

如果在對偶單純形法中原切割方程的松弛變量仍為基變量，則此松弛變量所在列化為單位向量后就可以去掉該行該列，再切割。正則解1求解0－1整數(shù)規(guī)劃的隱枚舉法（適合于變量個數(shù)較少的0-1規(guī)劃）隱枚舉法的步驟：1.找出任意一可行解，目標(biāo)函數(shù)值為Z0；

2.

原問題求最大值時，則增加一個約束當(dāng)求最小值時，上式改為小于等于約束；

3.列出所有可能解，對每個可能解先檢驗式(*)，若滿足再檢驗其它約束，若不滿足式(*)，則認(rèn)為不可行，若所有約束都滿足，則認(rèn)為此解是可行解，求出目標(biāo)值；

4.目標(biāo)函數(shù)值最大(最小)的解就是最優(yōu)解。0－1規(guī)劃的求解

例用隱枚舉法求解下列BIP問題解(1)不難看出，當(dāng)所有變量等于0或1的任意組合時，第一個約束滿足，說明第一個約束沒有約束力，是多余的，從約束條件中去掉。還能通過觀察得到X0＝(1，0，0，1)是一個可行解，目標(biāo)值Z0＝11是BIP問題的下界，構(gòu)造一個約束：原BIP問題變?yōu)?2)列出變量取值0和1的組合，共24＝16個，分別代入約束條件判斷是否可行。首先判斷式(a)是否滿足，如果滿足，接下來判斷其它約束，否則認(rèn)為不可行，計算過程見下表所示。

3.列出所有可能解，對每個可能解先檢驗式(*)，若滿足再檢驗其它約束，若不滿足式(*)，則認(rèn)為不可行，若所有約束都滿足，則認(rèn)為此解是可行解，求出目標(biāo)值；jXjabcdZjjXjabcdZj1(0,0,0,0)×

9(1,0,0,0)×

2(0,0,0,1)×

10(1,0,0,1)√√√√113(0,0,1,0)×

11(1,0,1,0)×

4(0,0,1,1)×

12(1,0,1,1)√√√√145(0,1,0,0)×

13(1,1,0,0)×

6(0,1,0,1)×

14(1,1,0,1)√√√√137(0,1,1,0)×

15(1,1,1,0)√×

8(0,1,1,1)×

16(1,1,1,1)√√√×

(3)由上表知，BIP問題的最優(yōu)解：X＝(1，0，1，1)，最優(yōu)值Z＝14。注：(1)選擇不同的初始可行解，計算量會不一樣。一般地，當(dāng)目標(biāo)函數(shù)求最大值時，首先考慮目標(biāo)函數(shù)系數(shù)最大的變量等于1。當(dāng)目標(biāo)函數(shù)求最小值時，先考慮目標(biāo)函數(shù)系數(shù)最大的變量等于0；(2)在上表的計算過程中，當(dāng)目標(biāo)值等于14時，將其下界11改為14，可以減少計算量。在實際中經(jīng)常會遇到這樣的問題，有n項不同的任務(wù)，需要n個人分別完成其中的一項，但由于任務(wù)的性質(zhì)和各人的專長不同，因此各人去完成不同的任務(wù)的效率（或花費的時間或費用）也就不同。于是產(chǎn)生了一個問題，應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)的總效率最高（或所需時間最少），這類問題稱為指派問題或分派問題。指派問題是0-1規(guī)劃的特例，也是運輸問題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1規(guī)劃或運輸問題的解法去求解，這就如同用單純型法求解運輸問題一樣是不合算的。利用指派問題的特點可有更簡便的解法，這就是匈牙利法，即系數(shù)矩陣中獨立0元素的最多個數(shù)等于能覆蓋所有0元素的最少直線數(shù)。指派問題例人事部門欲安排四人到四個不同的崗位工作，每個崗位一個人．經(jīng)考核四人在不同崗位的成績（百分制）如表所示，如何安排他們的工作使總成績最好。工作人員ABCD甲85927390乙95877895丙82837990丁86908088解設(shè)1數(shù)學(xué)模型數(shù)學(xué)模型為：甲乙丙丁ABCD

假設(shè)m個人恰好做m項工作，第i個人做第j項工作的效率為cij≥0，效率矩陣為[cij]，如何分配工作使效率最佳(min或max)的數(shù)學(xué)模型為2解指派問題的匈牙利算法匈牙利法的條件：問題求最小值、人數(shù)與工作數(shù)相等及效率非負(fù)

定理1如果從分配問題效率矩陣[cij]的某一行元素中分別減去(或加上)一個常數(shù)ui(被稱為該行的位勢)，從某一列分別減去(或加上)一個常數(shù)vj(稱為該列的位勢)，得到一個新的效率矩陣[bij]，其中bij=cij－ui－vj,則[bij]的最優(yōu)解等價于[cij]的最優(yōu)解，這里cij、bij均非負(fù)．定理2若矩陣A的元素可分成“0”與非“0”兩部分，則覆蓋“0”元素的最少直線數(shù)等于位于不同行不同列的“0”元素(稱為獨立元素)的最大個數(shù)．如果最少直線數(shù)等于m，則存在m個獨立的“0”元素，令這些零元素對應(yīng)的xij等于1，其余變量等于0，這時目標(biāo)函數(shù)值等于零，得到最優(yōu)解．例某汽車公司擬將四種新產(chǎn)品配置到四個工廠生產(chǎn)，四個工廠的單位產(chǎn)品成本(元/件)如表所示．求最優(yōu)生產(chǎn)配置方案．產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠27550150230工廠36570170250工廠48255200280解問題求最小值。第一步：找出效率矩陣每行的最小元素，并分別從每行中減去最小元素，有第二步：找出矩陣每列的最小元素，再分別從每列中減去，有

第三步：用最少的直線覆蓋所有“0”，得第四步：這里直線數(shù)等于3(等于4時停止運算)，要進行下一輪計算．從矩陣未被直線覆蓋的數(shù)字中找出一個最小數(shù)k并且減去k，矩陣中k＝5．

直線相交處的元素加上k，被直線覆蓋而沒有相交的元素不變，得到下列矩陣第四步等價于第1、3行減去5，同時第1列加上5得到的結(jié)果第五步：覆蓋所有零最少需要4條直線，表明矩陣中存在4個不同行不同列的零元素．容易看出4個“0”的位置()()()()或()()()()得到兩個最優(yōu)解有兩個最優(yōu)方案第一種方案：第一個工廠加工產(chǎn)品1，第二工廠加工產(chǎn)品3，第三個工廠加工產(chǎn)品4，第四個工廠加工產(chǎn)品2；第二種方案：第一個工廠加工產(chǎn)品1，第二工廠加工產(chǎn)品4，第三個工廠加工產(chǎn)品3，第四個工廠加工產(chǎn)品2；單件產(chǎn)品總成本Z＝58＋150＋250＋55＝513例有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982求解過程如下：第一步，變換系數(shù)矩陣：－5第二步，試指派：◎◎◎??找到3個獨立零元素但m=3<n=

4第三步，作最少的直線覆蓋所有0元素：

◎