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

1、整整 數(shù)數(shù) 規(guī)規(guī) 劃劃(Integer Programming)整數(shù)規(guī)劃的模型整數(shù)規(guī)劃的模型分支定界法分支定界法割平面法割平面法0 01 1 整數(shù)規(guī)劃整數(shù)規(guī)劃指派問(wèn)題指派問(wèn)題（一）、整數(shù)規(guī)劃問(wèn)題實(shí)例（一）、整數(shù)規(guī)劃問(wèn)題實(shí)例 例一、合理下料問(wèn)題例一、合理下料問(wèn)題設(shè)用某型號(hào)的圓鋼下零件設(shè)用某型號(hào)的圓鋼下零件A1, A2,Am 的毛坯。在一根圓鋼的毛坯。在一根圓鋼上下料的方式有上下料的方式有B1,B2, Bn 種，每種下料方式可以得到各種，每種下料方式可以得到各種零件的毛坯數(shù)以及每種零件的需要量，如表所示。問(wèn)怎種零件的毛坯數(shù)以及每種零件的需要量，如表所示。問(wèn)怎樣安排下料方式，使得即滿足需要，所用的原

2、材料又最少？樣安排下料方式，使得即滿足需要，所用的原材料又最少？零件 方 個(gè)數(shù) 式零件零 件毛坯數(shù)nBB 1mAA 1mbb 1mnmnaaaa 1111一、整數(shù)規(guī)劃的模型一、整數(shù)規(guī)劃的模型 設(shè)：設(shè)：xj 表示用表示用Bj (j=1.2n) 種方式下料根數(shù)種方式下料根數(shù) 模型：模型：且且為為整整數(shù)數(shù)n)1.2(j 0)2 . 1( min11jnjijijnjjxmibxaxZ例二、例二、某公司計(jì)劃在某公司計(jì)劃在m個(gè)地點(diǎn)建廠，可供選擇的地點(diǎn)個(gè)地點(diǎn)建廠，可供選擇的地點(diǎn)有有A1,A2Am ，他們的生產(chǎn)能力分別是他們的生產(chǎn)能力分別是a1,a2,am（假設(shè)（假設(shè)生產(chǎn)同一產(chǎn)品）。第生產(chǎn)同一產(chǎn)品）。第i

3、i個(gè)工廠的建設(shè)費(fèi)用為個(gè)工廠的建設(shè)費(fèi)用為fi (i=1.2m),又有又有n個(gè)地點(diǎn)個(gè)地點(diǎn)B1,B2, Bn 需要銷售這種產(chǎn)品，需要銷售這種產(chǎn)品，其銷量分別為其銷量分別為b1.b2bn 。從工廠運(yùn)往銷地的單位運(yùn)費(fèi)。從工廠運(yùn)往銷地的單位運(yùn)費(fèi)為為Cij。試決定應(yīng)在哪些地方建廠，即滿足各地需要，。試決定應(yīng)在哪些地方建廠，即滿足各地需要，又使總建設(shè)費(fèi)用和總運(yùn)輸費(fèi)用最??？又使總建設(shè)費(fèi)用和總運(yùn)輸費(fèi)用最省？單 銷地廠址 價(jià)生產(chǎn)能力建設(shè)費(fèi)用銷量nmmmnmmmnnnbbbfacccAfacccAfacccABBB 2121222222121111211121 設(shè)：設(shè)： xij 表示從工廠運(yùn)往銷地的運(yùn)量表示從工廠運(yùn)往

4、銷地的運(yùn)量( (i=1.2m、j=1.2n), 1 ), 1 在在Ai建廠建廠 又設(shè)又設(shè) Yi （i=1.2m） 0 0 不在不在Ai建廠建廠 模型：模型：n)1.2jm1.2(i 1 0, 0n)1.2(j )2 . 1( min111、或或iijmijijnjiiijmiiiijijyxbxmiyaxyfxcZ 例三、機(jī)床分配問(wèn)題例三、機(jī)床分配問(wèn)題 設(shè)有設(shè)有m臺(tái)同類機(jī)床，要加工臺(tái)同類機(jī)床，要加工n種零件。已知各種零件種零件。已知各種零件的加工時(shí)間分別為的加工時(shí)間分別為a1,a2,an ，問(wèn)如何分配，使各機(jī)床，問(wèn)如何分配，使各機(jī)床的總加工任務(wù)相等，或者說(shuō)盡可能平衡。的總加工任務(wù)相等，或者說(shuō)盡

5、可能平衡。設(shè)：設(shè)： 1 1 分配第分配第i臺(tái)機(jī)床加工第臺(tái)機(jī)床加工第j j種零件；種零件； xij （i i=1.2m,=1.2m,j j=1.2n=1.2n） 0 0 相反。相反。于是，第于是，第i臺(tái)機(jī)床加工各種零件的總時(shí)間為：臺(tái)機(jī)床加工各種零件的總時(shí)間為：njijjmixa1)2 . 1( 又由于一個(gè)零件只能在一臺(tái)機(jī)床上加工，所以有又由于一個(gè)零件只能在一臺(tái)機(jī)床上加工，所以有miijmix1)2 . 1( 1 因此，求因此，求xij ，使得，使得121111minmax(,)1 (j1.2n)0 1 (i1.2m,j1.2n)nnnjjjjjmjjjjmijiijZa xa xa xxx或（二

6、）、整數(shù)規(guī)劃的數(shù)學(xué)模型（二）、整數(shù)規(guī)劃的數(shù)學(xué)模型一般形式一般形式且且部部分分或或全全部部為為整整數(shù)數(shù)或或 n)1.2(j 0)2 . 1( )min(max11jnjijijnjjjxmibxaxcZZ 依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0 01 1整數(shù)規(guī)劃。整數(shù)規(guī)劃。 純整數(shù)規(guī)劃：純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整所有決策變量要求取非負(fù)整數(shù)（這時(shí)引進(jìn)的松弛變量可以不要求取整數(shù)）。數(shù)（這時(shí)引進(jìn)的松弛變量可以不要求取整數(shù)）。 全整數(shù)規(guī)劃：全整數(shù)規(guī)劃：除了所有決策變量要求

7、取非負(fù)除了所有決策變量要求取非負(fù)整數(shù)外，系數(shù)整數(shù)外，系數(shù)aij和常數(shù)和常數(shù)bi也要求取整數(shù)（這時(shí)引也要求取整數(shù)（這時(shí)引進(jìn)的松弛變量也必須是整數(shù)）。進(jìn)的松弛變量也必須是整數(shù)）。 混合整數(shù)規(guī)劃：混合整數(shù)規(guī)劃：只有一部分的決策變量要只有一部分的決策變量要求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。求取非負(fù)整數(shù)，另一部分可以取非負(fù)實(shí)數(shù)。 01整數(shù)規(guī)劃：整數(shù)規(guī)劃：所有決策變量只能取所有決策變量只能取 0 或或 1 兩個(gè)整數(shù)兩個(gè)整數(shù)。（三）、整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系（三）、整數(shù)規(guī)劃與線性規(guī)劃的關(guān)系 從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線從數(shù)學(xué)模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的一種特殊形式

8、，求解只需在線性規(guī)劃的基礎(chǔ)上，通過(guò)舍入取整，尋求性規(guī)劃的基礎(chǔ)上，通過(guò)舍入取整，尋求滿足整數(shù)要求的解即可。但實(shí)際上兩者滿足整數(shù)要求的解即可。但實(shí)際上兩者卻有很大的不同，通過(guò)舍入得到的解卻有很大的不同，通過(guò)舍入得到的解（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚（整數(shù)）也不一定就是最優(yōu)解，有時(shí)甚至不能保證所得到的解是整數(shù)可行解。至不能保證所得到的解是整數(shù)可行解。舉例說(shuō)明。舉例說(shuō)明。例：設(shè)整數(shù)規(guī)劃問(wèn)題如下例：設(shè)整數(shù)規(guī)劃問(wèn)題如下 且為整數(shù)0,13651914max21212121xxxxxxxxZ 首先不考慮整數(shù)約束，得到線性規(guī)劃問(wèn)題（一般稱首先不考慮整數(shù)約束，得到線性規(guī)劃問(wèn)題（一般稱為松弛問(wèn)題）。為松弛問(wèn)題）

9、。0,13651914max21212121xxxxxxxxZ用用 解法求出最優(yōu)解解法求出最優(yōu)解x13/2, x2 = 10/3且有且有Z = 29/6x1x233(3/2,10/3) 現(xiàn)求整數(shù)解（最優(yōu)解）：現(xiàn)求整數(shù)解（最優(yōu)解）：如用如用“舍入取整法舍入取整法”可可得到得到4個(gè)點(diǎn)即個(gè)點(diǎn)即(1，3) (2，3)(1，4)(2，4)。顯然，。顯然，它們都不可能是整數(shù)規(guī)它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。劃的最優(yōu)解。 按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問(wèn)題按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問(wèn)題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問(wèn)題的可行解集的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問(wèn)題的可行解集是一

10、個(gè)有限集，如圖所示。是一個(gè)有限集，如圖所示。圖圖 因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最因此，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。 如上例：其中如上例：其中（2，2）（）（3，1）點(diǎn)為最點(diǎn)為最大值，大值，Z=4。 目前，常用的求解整數(shù)規(guī)劃的方法有：目前，常用的求解整數(shù)規(guī)劃的方法有： 分支定界法和割平面法；分支定界法和割平面法； 對(duì)于特別的對(duì)于特別的0 01 1規(guī)劃問(wèn)題采用隱枚舉法和匈規(guī)劃問(wèn)題采用隱枚舉法和匈牙利法。牙利法。（一）、基本思路（一）、基本思路 且為整數(shù)且為整數(shù))2 . 1( , 0)2 . 1( )(m

11、ax11mjxmibxaIPxcZjnjijijnjjj考慮純整數(shù)問(wèn)題：考慮純整數(shù)問(wèn)題：)2 . 1( , 0)2 . 1( )(max11mjxmibxaLPxcZjnjijijnjjj整數(shù)問(wèn)題的松弛問(wèn)題：整數(shù)問(wèn)題的松弛問(wèn)題：二、分枝定界法二、分枝定界法 1、先不考慮整數(shù)約束，解、先不考慮整數(shù)約束，解( IP )的松弛問(wèn)題的松弛問(wèn)題( LP )，可能得到以下情況之一：可能得到以下情況之一： .若若( LP )沒(méi)有可行解，則沒(méi)有可行解，則( IP )也沒(méi)有可行解，停止也沒(méi)有可行解，停止計(jì)算。計(jì)算。 .若若( LP )有最優(yōu)解，并符合有最優(yōu)解，并符合( IP )的整數(shù)條件，則的整數(shù)條件，則( L

12、P )的最優(yōu)解即為的最優(yōu)解即為( IP )的最優(yōu)解，停止計(jì)算。的最優(yōu)解，停止計(jì)算。 .若若( LP )有最優(yōu)解，但不符合有最優(yōu)解，但不符合( IP )的整數(shù)條件，轉(zhuǎn)的整數(shù)條件，轉(zhuǎn)入下一步。為討論方便，設(shè)入下一步。為討論方便，設(shè)( LP )的最優(yōu)解為：的最優(yōu)解為： 不不全全為為整整數(shù)數(shù)其其中中目目標(biāo)標(biāo)函函數(shù)數(shù)最最優(yōu)優(yōu)值值為為), 2 , 1(.Z)0 , 0 ,( (0)21)0(mibbbbbXiTmr 2、定界：、定界： 記記( IP )的目標(biāo)函數(shù)最優(yōu)值為的目標(biāo)函數(shù)最優(yōu)值為Z* ,以以Z(0) 作為作為Z* 的上界，的上界，記為記為 Z(0) 。再用觀察法找的一個(gè)整數(shù)可行解。再用觀察法找的一

13、個(gè)整數(shù)可行解 X，并以其相應(yīng)的目標(biāo)函數(shù)值并以其相應(yīng)的目標(biāo)函數(shù)值 Z作為作為Z* 的下界，記為的下界，記為Z Z，也可以令也可以令Z，則有：，則有： Z Z* 3、分枝：分枝： 在在( LP )的最優(yōu)解的最優(yōu)解 X(0)中，任選一個(gè)不符合整數(shù)條件中，任選一個(gè)不符合整數(shù)條件的變量，例如的變量，例如xr= = （不為整數(shù)），以（不為整數(shù)），以 表示不超過(guò)表示不超過(guò) 的最大整數(shù)。構(gòu)造兩個(gè)約束條件的最大整數(shù)。構(gòu)造兩個(gè)約束條件 xr 和和xr 1 1rbrbrbrbrbZZ如此反復(fù)進(jìn)行，直到得到如此反復(fù)進(jìn)行，直到得到ZZ* 為止，即得最優(yōu)解為止，即得最優(yōu)解 X* 。 將這兩個(gè)約束條件分別加入問(wèn)題將這兩個(gè)約

14、束條件分別加入問(wèn)題( IP ) ，形成兩個(gè)子，形成兩個(gè)子問(wèn)題問(wèn)題( IP1)和和( IP2 ) ，再解這兩個(gè)問(wèn)題的松弛問(wèn)題，再解這兩個(gè)問(wèn)題的松弛問(wèn)題( LP1)和和( LP2) 。 4、修改上、下界：按照以下兩點(diǎn)規(guī)則進(jìn)行。修改上、下界：按照以下兩點(diǎn)規(guī)則進(jìn)行。 . .在各分枝問(wèn)題中，找出目標(biāo)函數(shù)值最大者作為在各分枝問(wèn)題中，找出目標(biāo)函數(shù)值最大者作為新的上界；新的上界； . .從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值從已符合整數(shù)條件的分枝中，找出目標(biāo)函數(shù)值最大者作為新的下界。最大者作為新的下界。 5、比較與剪枝比較與剪枝 ： 各分枝的目標(biāo)函數(shù)值中，若有小于各分枝的目標(biāo)函數(shù)值中，若有小于Z 者，則剪掉

15、此者，則剪掉此枝，表明此子問(wèn)題已經(jīng)探清，不必再分枝了枝，表明此子問(wèn)題已經(jīng)探清，不必再分枝了;否則繼續(xù)否則繼續(xù)分枝。分枝。 Z例一：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（用圖解法計(jì)算）例一：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（用圖解法計(jì)算）且且全全為為整整數(shù)數(shù)0,4 30 652 5min211212121xxxxxxxxxZ記為（記為（IP）解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問(wèn)題解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問(wèn)題0,4 30 652 5min211212121xxxxxxxxxZ記為（記為（LP）（二）、例題（二）、例題用圖解法求用圖解法求（LP）的最的最優(yōu)解，如圖所示。優(yōu)解，如圖所示。x1x2

16、33(18/11,40/11)對(duì)于對(duì)于x118/111.64， 取值取值x1 1， x1 2對(duì)于對(duì)于x2 =40/11 3.64，取值取值x2 3 ，x2 4先將先將（LP）劃分為（）劃分為（LP1）和（）和（LP2）, ,取取x1 1, x1 2 x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 也是也是（IP）最小值的下最小值的下限。限。有下式：有下式：且且為為整整數(shù)數(shù)0,1 4 30 652 )1(5min2111212121xxxxxxxxIPxxZ且且為為整整數(shù)數(shù)0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ 現(xiàn)

17、在只要求出（現(xiàn)在只要求出（LP1）和（）和（LP2）的最優(yōu)解即可。）的最優(yōu)解即可。x1x233(18/11,40/11) 先求先求（LP1）, ,如圖所示。如圖所示。此時(shí)此時(shí)B 在點(diǎn)取得最優(yōu)解。在點(diǎn)取得最優(yōu)解。x11, x2 =3, Z(1)16找到整數(shù)解，問(wèn)題已探找到整數(shù)解，問(wèn)題已探明，此枝停止計(jì)算。明，此枝停止計(jì)算。11同理求同理求（LP2） ,如圖所示。如圖所示。在在C 點(diǎn)取得最優(yōu)解。點(diǎn)取得最優(yōu)解。即即x12, x2 =10/3, Z(2) 56/318.7 Z2 Z116 原問(wèn)題有比原問(wèn)題有比（16）更小的最優(yōu)解，但）更小的最優(yōu)解，但 x2 不是整數(shù)，故利用不是整數(shù)，故利用 3 10/

18、34 加入條件。加入條件。BAC加入條件：加入條件： x23, x24 有下式：有下式：且且為為整整數(shù)數(shù)0,3 2 4 30 652 )3(5min21211212121xxxxxxxxxIPxxZ且且為為整整數(shù)數(shù)0,4 2 4 30 652 )4(5min21211212121xxxxxxxxxIPxxZ只要求出（只要求出（LP3）和（）和（LP4）的最優(yōu)解即可。）的最優(yōu)解即可。x1x233(18/11,40/11)11BAC先求先求（LP3）, ,如圖所示。如圖所示。此時(shí)此時(shí)D 在點(diǎn)取得最優(yōu)解。在點(diǎn)取得最優(yōu)解。即即 x112/52.4, x2 =3, Z(3)-87/5-17.4 Z(5)

19、 F 如對(duì)如對(duì) Z(6) 繼續(xù)分解，其最小值也不會(huì)低于繼續(xù)分解，其最小值也不會(huì)低于15.5 ，問(wèn)題探明問(wèn)題探明, ,剪枝。剪枝。 至此，原問(wèn)至此，原問(wèn)題（題（IP）的最優(yōu)）的最優(yōu)解為：解為： x1=2， x2 =3, Z* = Z(5) 17以上的求解過(guò)程以上的求解過(guò)程可以用一個(gè)樹(shù)形可以用一個(gè)樹(shù)形圖表示如右：圖表示如右：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無(wú)可無(wú)可行解行解LP5x1=2, x2=3Z(5) 17LP6x1=3,

20、x2=5/2Z(6) 15.5x11x12x23x24x12x13 且全為整數(shù)且全為整數(shù)0,13651914max21212121xxxxxxxxZ練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題 （圖解法）（圖解法）LP1x1=1, x2=7/3Z(1) 10/3LPx1=3/2, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9x11x12LP5x1=1, x2=2Z(5) 3LP6無(wú)可無(wú)可行解行解x22x23LP3x1=33/14, x2=2Z(3) 61/14LP4無(wú)可無(wú)可行解行解x22x23LP7x1=2, x2=2Z(7) 4L

21、P8x1=3, x2=1Z(8) 4x12x13LP1x1=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無(wú)可無(wú)可行解行解LP7x1=2, x2=2Z(7) 4LP8x1=3, x2=1Z(8) 4x11x12x22x23x12x13且且為為整整數(shù)數(shù)0,143292)(23max21212121xxxxxxIPxxZ3200CB XB b x1x2x3x40 x3921109/20 x414230114/2-Z032003200CB XB b

22、x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4 -1/4解解:用單純形法解對(duì)應(yīng)的用單純形法解對(duì)應(yīng)的(LP)問(wèn)題問(wèn)題,如表所示如表所示,獲得最優(yōu)解。獲得最優(yōu)解。初始表初始表最終表最終表例二、用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（單純形法）例二、用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（單純形法） x1=13/4 x2=5/2 Z(0) =59/414.75選選 x2 進(jìn)行分枝，即增加兩個(gè)約束，進(jìn)行分枝，即增加兩個(gè)約束，x2 2, x2 3 有下式：有下式：且且為為整整數(shù)數(shù)0,2 14329 2) 1(23max212212121xxxxxxxIPxxZ且且為

23、為整整數(shù)數(shù)0,3 14329 2)2(23max212212121xxxxxxxIPxxZ 分別在分別在(LP1)和和(LP2)中引入松弛變量中引入松弛變量x5和和x6 ，將新加，將新加約束條件加入上表計(jì)算。即約束條件加入上表計(jì)算。即 x2+ x5= 2 , x2+x6=3 得得下表下表:32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-1/2001/2 -1/21-Z-59/400-5/4-1/403

24、x17/2101/20-1/22x22010010 x4100-11-2-Z-29/200-3/20-1/2x1=7/2, x2=2 Z(1) =29/2=14.5繼續(xù)分枝，加繼續(xù)分枝，加入約束入約束 x1 3 , x1 4LP132000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10 x3

25、1001-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ù)分枝，加入約束繼續(xù)分枝，加入約束 x1 3， x1 4有下式：有下式：且且為為整整數(shù)數(shù)0,3 2 14329 2)3(23max2112212121xxxxxxxxIPxxZ且且為為整整數(shù)數(shù)0,4 2 14329 2)4(23max2112212121xxxxxxxxIPxxZ分別引入松弛變量分別引入松弛變量x7 和和 x8 ，然后進(jìn)行計(jì)算。，然后進(jìn)行計(jì)算。CB XB b x1x2x3x4x5x73x17/2101/2

26、0-1/202x220100100 x4100-11-200 x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100 x420001-3-20 x310010-1-2-Z-130000-2-3 x1=3, x2=2 Z(3) =13找到整數(shù)解，找到整數(shù)解，問(wèn)題已探明，問(wèn)題已探明，停止計(jì)算。停止計(jì)算。LP3CB XB b x1x2x3x4x5x83x17/2101/20-1/202x22010010

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

28、) 59/4=14.75LP2x1=5/2, x2=3Z(2)27/2=13.5LP3x1=3, x2=2Z(3) 13LP4x1=4, x2=1Z(4) 14x22x23x13x14 且且全全為為整整數(shù)數(shù)0,4 30 652 5min211212121xxxxxxxxxZ練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題 （單純形法）（單純形法）cj-1-5000cBxBbx1x2x3x4x50 x32-111000 x4 30560100 x5410001-Z-1-5000cj-1-5000cBxBbx1x2x3x4x5-5x240/11011/115/110-1x1 1

29、8/11101/11-6/1100 x526/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無(wú)可無(wú)可行解行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23x24x12x13（一）、計(jì)算步驟：（一）、計(jì)算步驟：1、用單純形法求解、用單純形法求解( IP )對(duì)應(yīng)的松弛問(wèn)題對(duì)應(yīng)的松弛問(wèn)題( LP )： .若若( LP

30、)沒(méi)有可行解，則沒(méi)有可行解，則( IP )也沒(méi)有可行解，停止也沒(méi)有可行解，停止計(jì)算。計(jì)算。 .若若( LP )有最優(yōu)解，并符合有最優(yōu)解，并符合( IP )的整數(shù)條件，則的整數(shù)條件，則( LP )的最優(yōu)解即為的最優(yōu)解即為( IP )的最優(yōu)解，停止計(jì)算。的最優(yōu)解，停止計(jì)算。 .若若( LP )有最優(yōu)解，但不符合有最優(yōu)解，但不符合( IP )的整數(shù)條件，轉(zhuǎn)的整數(shù)條件，轉(zhuǎn)入下一步。入下一步。 三、割平面法三、割平面法 2 2、從、從( (LP) )的最優(yōu)解中，任選一個(gè)不為整數(shù)的分量的最優(yōu)解中，任選一個(gè)不為整數(shù)的分量x xr,r, ,將最優(yōu)單純形表中該行的系數(shù)將最優(yōu)單純形表中該行的系數(shù) 和和 分解為整數(shù)

31、分解為整數(shù)部分和小數(shù)部分之和，并以該行為源行，按下式作割部分和小數(shù)部分之和，并以該行為源行，按下式作割平面方程：平面方程：rjarb nmjjrjrxff10 3 3、將所得的割平面方程作為一個(gè)新的約束條件置于、將所得的割平面方程作為一個(gè)新的約束條件置于最優(yōu)單純形表中（同時(shí)增加一個(gè)單位列向量），用對(duì)最優(yōu)單純形表中（同時(shí)增加一個(gè)單位列向量），用對(duì)偶單純形法求出新的最優(yōu)解，返回偶單純形法求出新的最優(yōu)解，返回1 1。的小數(shù)部分的小數(shù)部分的小數(shù)部分的小數(shù)部分rjarb例一：用割平面法求解整數(shù)規(guī)劃問(wèn)題例一：用割平面法求解整數(shù)規(guī)劃問(wèn)題 且且為為整整數(shù)數(shù)0,023623 max2121212xxxxxxxZ

32、解：增加松弛變量解：增加松弛變量x3和和x4 ，得到，得到(LP)的初始單純形表和的初始單純形表和最優(yōu)單純形表：最優(yōu)單純形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/2 00 -1/4 -1/4 此題的最優(yōu)解為：此題的最優(yōu)解為：X =(1 , 3/2) Z = 3/2 但不是但不是整數(shù)最優(yōu)解，引入割平面。以整數(shù)最優(yōu)解，引入割平面。以x2 為源行生成割平面，為源行生成割平面，由于由于 1/4=0+1/4, 3/2=1+1/2, 我們已將所需要的數(shù)分

33、解我們已將所需要的數(shù)分解為整數(shù)和分?jǐn)?shù)，所以，生成割平面的條件為為整數(shù)和分?jǐn)?shù)，所以，生成割平面的條件為: 21414143 xx也即：也即：)4141(2112114141234141432432432xxxxxxxxx0)4141(21 43 xx將將 x3=6-3x1-2x2 , x4=3x1-2x2 ,帶入帶入 中，中，得到等價(jià)的割平面條件：得到等價(jià)的割平面條件： x2 1 見(jiàn)下圖。見(jiàn)下圖。21414143 xxx1x233第一個(gè)割平面第一個(gè)割平面Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41Z-

34、3/200-1/4-1/40現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中：現(xiàn)將生成的割平面條件加入松弛變量，然后加到表中：214141143 sxxCBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-1 此時(shí)，此時(shí)，X1 (2/3, 1), Z=1,仍不是整數(shù)解。繼續(xù)以仍不是整數(shù)解。繼續(xù)以x1為源為源行生成割平面，其條件為：行生成割平面，其條件為：32323214 sx 用上表的約束解出用上表的約束解出x4 和和s1 ，將它們帶入上式得到等價(jià)，將它們帶入上式得到等價(jià)的割平面條件：的割平面條件：x1 x2 ，見(jiàn)圖：，見(jiàn)圖：x1

35、x233第一個(gè)割平面第一個(gè)割平面第二個(gè)割平面第二個(gè)割平面將生成的割平面條件加入松弛變量，然后加到表中：將生成的割平面條件加入松弛變量，然后加到表中：323232214 ssxCBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/3000-2/3-2/31Z-10000-10CBXBbx1x2x3x4s1s20 x10100-1011x20010-103/20 x3600150-60s1100011-3/2Z000010-3/2CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x31001

36、0-53/20 x4100011-3/2Z-10000-10 至此得到最優(yōu)表，其最優(yōu)解為至此得到最優(yōu)表，其最優(yōu)解為 X= (1 , 1) , Z = 1, 這這也是原問(wèn)題的最優(yōu)解。也是原問(wèn)題的最優(yōu)解。 有以上解題過(guò)程可見(jiàn)，表中含有分?jǐn)?shù)元素且算法過(guò)有以上解題過(guò)程可見(jiàn)，表中含有分?jǐn)?shù)元素且算法過(guò)程中始終保持對(duì)偶可行性，因此，這個(gè)算法也稱為分程中始終保持對(duì)偶可行性，因此，這個(gè)算法也稱為分?jǐn)?shù)對(duì)偶割平面算法。數(shù)對(duì)偶割平面算法。例二：用割平面法求解整數(shù)規(guī)劃問(wèn)題例二：用割平面法求解整數(shù)規(guī)劃問(wèn)題 且且為為整整數(shù)數(shù)0, 205462max21212121xxxxxxxxZCj1100CBXBbx1x2x3x40

37、x3621100 x4204501Z1100CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3Z-13/3001/61/6初初始始表表最最優(yōu)優(yōu)表表在松弛問(wèn)題最優(yōu)解中，在松弛問(wèn)題最優(yōu)解中，x1, x2 均為非整數(shù)解，由上表均為非整數(shù)解，由上表有：有：383132356165432431 xxxxxx將系數(shù)和常數(shù)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和將系數(shù)和常數(shù)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和 32231)311(321)651(65432431 xxxxxx 以上式子只須考慮一個(gè)即可，解題經(jīng)驗(yàn)表明，考慮以上式子只須考慮一個(gè)即可，解題經(jīng)驗(yàn)表明，考慮式子右端最大真分?jǐn)?shù)的式子，往往

38、會(huì)較快地找到所需式子右端最大真分?jǐn)?shù)的式子，往往會(huì)較快地找到所需割平面約束條件。以上兩個(gè)式子右端真分?jǐn)?shù)相等，可割平面約束條件。以上兩個(gè)式子右端真分?jǐn)?shù)相等，可任選一個(gè)考慮?，F(xiàn)選第二個(gè)式子，并將真分?jǐn)?shù)移到右任選一個(gè)考慮?，F(xiàn)選第二個(gè)式子，并將真分?jǐn)?shù)移到右邊得：邊得： )(313224332xxxx 32)(3143 xx引入松弛變量引入松弛變量s1 后得到下式，將此約束條件加到上表后得到下式，將此約束條件加到上表中，繼續(xù)求解。中，繼續(xù)求解。 323131143 sxxCj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31

39、Z13/3001/61/60Cj11000CBXBbx1x2x3x4s11 x10100101x24010120 x3200113Z400001/2 得到整數(shù)最優(yōu)解，即為整數(shù)規(guī)劃的最優(yōu)解，而且此整數(shù)規(guī)劃得到整數(shù)最優(yōu)解，即為整數(shù)規(guī)劃的最優(yōu)解，而且此整數(shù)規(guī)劃有兩個(gè)最優(yōu)解：有兩個(gè)最優(yōu)解： X= (0, 4), Z = 4, 或 X= (2, 2), Z = 4。 且且為為整整數(shù)數(shù)練練習(xí)習(xí)：0,421625421411max2121212121xxxxxxxxxxZCBXBbx1x2x3x4x50 x34001-1/34/34x24/30102/9-5/911x18/31001/92/9Z000-19

40、/9-2/9CBXBbx1x2x3x4x5s10 x30001-1064x230101/20-5/211x121000010 x530001/21-9/2Z000-20-1（2 ，3） 01 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的決策變量決策變量xi 只取兩個(gè)值只取兩個(gè)值0或或1，一般的解法為隱枚舉法。，一般的解法為隱枚舉法。例一、求解下列例一、求解下列01 規(guī)劃問(wèn)題規(guī)劃問(wèn)題 10,(4) 64 (3) 3 (2) 44(1) 22523max3213221321321321或或xxxxxxxxxxxxxxxxZ四、四、0 01 1 整數(shù)規(guī)劃整數(shù)規(guī)劃

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

42、0. 0. 1 ) 1 1 0 15( 0. 1. 0 ) 2 4 1 42( 1. 0. 0 ) 1 1 1 03( 0. 1. 1 ) 1 5( 1. 0. 1 ) 0 2 1 18( 1. 1. 0 ) 3( 1. 1. 1 ) 2 6 由上表可知，問(wèn)題的最優(yōu)解為由上表可知，問(wèn)題的最優(yōu)解為 X*=( x1 =1 x2=0 x3=1 )由上表可知：由上表可知： x1 =0 x2=0 x3=1 是一個(gè)可行解，為盡快是一個(gè)可行解，為盡快找到最優(yōu)解，可將找到最優(yōu)解，可將3 x12 x25 x3 5 作為一個(gè)約束，作為一個(gè)約束，凡是目標(biāo)函數(shù)值小于凡是目標(biāo)函數(shù)值小于5 的組合不必討論，如下表。的組合

43、不必討論，如下表。x1 . x2. x3約束條件約束條件滿足條件滿足條件Z 值值(0) (1) (2) (3) (4)是是 否否( 0. 0. 0 ) 00( 0. 0. 1 ) 5 1 1 0 15( 0. 1. 0 )-2( 0. 1. 1 ) 3( 1. 0. 0 ) 3( 1. 0. 1 ) 8 0 2 1 18( 1. 1. 0 ) 1( 1. 1. 1 ) 4 例二、求解下列例二、求解下列01 規(guī)劃問(wèn)題規(guī)劃問(wèn)題4 . 3 . 2 . 1 1 , 05 35646 1 273max421432143214321jxxxxxxxxxxxxxxxxZj 解：由于目標(biāo)函數(shù)中變量解：由于目標(biāo)

44、函數(shù)中變量x1, x2 , x4 的系數(shù)均為負(fù)數(shù)，的系數(shù)均為負(fù)數(shù)，可作如下變換：可作如下變換： 令令 x1 1 x1 , x2 =1- x2, x3= x3, x4 =1- x4帶入原題帶入原題中，但需重新調(diào)整變量編號(hào)。令中，但需重新調(diào)整變量編號(hào)。令 x3 = x1, x4 = x2得到下式。得到下式。 1 0,435 2 461 2 1173max4321432432143214321或或xxxxxxxxxxxxxxxxxxxZ 可以從可以從( 1.1.1.1 )開(kāi)始試算，開(kāi)始試算， x(3)( 1.1.0.1 )最優(yōu)解。最優(yōu)解。 x(3)( 1.0.1.0 )是原問(wèn)題的最優(yōu)解，是原問(wèn)題的最

45、優(yōu)解，Z* =2例三、求解下列例三、求解下列01 規(guī)劃問(wèn)題規(guī)劃問(wèn)題 )5 . 4 . 3 . 2 . 1( 1054 24423 248510min543215432154321jxxxxxxxxxxxxxxxxZj或或令令 y1=x5, y2=x4, y3=x2, y4=x3, y5=x1 得到下式得到下式 )5 . 4 . 3 . 2 . 1( 10(2) 524(1) 4342 108542min543215432154321jyyyyyyyyyyyyyyyyZj或或y1 . y2. y3 . y4. y5約束條件約束條件滿足條件滿足條件Z 值值 (1) (2)是是 否否( 0. 0.

46、0. 0. 0 ) 0 0( 1. 0. 0. 0. 0 ) 1 -1( 0. 1. 0. 0. 0 ) -1 1 ( 0. 0. 1. 0. 0 ) -2 1( 0. 0. 0. 1. 0 ) 4 -48( 0. 0. 0. 0. 1 ) 3 -2 所以，所以， Y*= （0.0.0.1.0），原問(wèn)題的最優(yōu)解為：），原問(wèn)題的最優(yōu)解為： X* （0.0.1.0.0），），Z* =8 )5 , 2 , 1( 1 01 2 02236224 53 31075min5432543215432154321jxxxxxxxxxxxxxxxxxxxxZj或或（0 . 1 . 1 . 0 . 0）練習(xí)：用隱

47、枚舉法求解練習(xí)：用隱枚舉法求解0101規(guī)劃問(wèn)題規(guī)劃問(wèn)題 在實(shí)際中經(jīng)常會(huì)遇到這樣的問(wèn)題，有在實(shí)際中經(jīng)常會(huì)遇到這樣的問(wèn)題，有n 項(xiàng)不同的任項(xiàng)不同的任務(wù)，需要?jiǎng)?wù)，需要n 個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專長(zhǎng)不同，因此各人去完成不同的任務(wù)性質(zhì)和各人的專長(zhǎng)不同，因此各人去完成不同的任務(wù)的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。于是產(chǎn)生的效率（或花費(fèi)的時(shí)間或費(fèi)用）也就不同。于是產(chǎn)生了一個(gè)問(wèn)題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成了一個(gè)問(wèn)題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成 n 項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少），這類問(wèn)項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少），

48、這類問(wèn)題稱為指派問(wèn)題或分派問(wèn)題。題稱為指派問(wèn)題或分派問(wèn)題。 （一）、指派問(wèn)題的數(shù)學(xué)模型（一）、指派問(wèn)題的數(shù)學(xué)模型 設(shè)設(shè)n 個(gè)人被分配去做個(gè)人被分配去做n 件工作，規(guī)定每個(gè)人只做一件工作，規(guī)定每個(gè)人只做一件工作，每件工作只有一個(gè)人去做。已知第件工作，每件工作只有一個(gè)人去做。已知第i 個(gè)人去做個(gè)人去做第第j 件工作的的效率（件工作的的效率（ 時(shí)間或費(fèi)用）為時(shí)間或費(fèi)用）為Cij(i=1.2n;j=1.2n)并假設(shè)并假設(shè)Cij 0。問(wèn)應(yīng)如何分配才。問(wèn)應(yīng)如何分配才能使總效率（能使總效率（ 時(shí)間或費(fèi)用）最高？時(shí)間或費(fèi)用）最高？五、指派問(wèn)題五、指派問(wèn)題設(shè)決策變量設(shè)決策變量 1 分配第分配第i 個(gè)人去做第個(gè)人

49、去做第j 件工作件工作 xij = 0 相反相反 ( I,j=1.2. n )其數(shù)學(xué)模型為：其數(shù)學(xué)模型為： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或 （二）、解題步驟：（二）、解題步驟： 指派問(wèn)題是指派問(wèn)題是0-1 規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，當(dāng)然可用整數(shù)規(guī)劃，當(dāng)然可用整數(shù)規(guī)劃，0-1 規(guī)劃或運(yùn)輸問(wèn)題的解法去求規(guī)劃或運(yùn)輸問(wèn)題的解法去求解，這就如同用單純型法求解運(yùn)輸問(wèn)題一樣是不合算解，這就如同用單純型法求解運(yùn)輸問(wèn)題一樣是不合算的。利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是

50、的。利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是匈牙利法，即匈牙利法，即系數(shù)矩陣中獨(dú)立系數(shù)矩陣中獨(dú)立 0 0 元素的最多個(gè)數(shù)等于元素的最多個(gè)數(shù)等于能覆蓋所有能覆蓋所有 0 0 元素的最少直線數(shù)。元素的最少直線數(shù)。 第一步：變換指派問(wèn)題的系數(shù)矩陣（第一步：變換指派問(wèn)題的系數(shù)矩陣（cij）為）為(bij)，使，使在在(bij)的各行各列中都出現(xiàn)的各行各列中都出現(xiàn)0元素，即元素，即 (1) 從（從（cij）的每行元素都減去該行的最小元素；）的每行元素都減去該行的最小元素； (2) 再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最小元素。小元素。 第二步：進(jìn)行試指派，

51、以尋求最優(yōu)解。第二步：進(jìn)行試指派，以尋求最優(yōu)解。 在在(bij)中找盡可能多的獨(dú)立中找盡可能多的獨(dú)立0元素，若能找出元素，若能找出n個(gè)獨(dú)個(gè)獨(dú)立立0元素，就以這元素，就以這n個(gè)獨(dú)立個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣元素對(duì)應(yīng)解矩陣(xij)中的元中的元素為素為1，其余為，其余為0，這就得到最優(yōu)解。找獨(dú)立，這就得到最優(yōu)解。找獨(dú)立0元素，常元素，常用的步驟為：用的步驟為： (1)從只有一個(gè)從只有一個(gè)0元素的行元素的行(列列)開(kāi)始，給這個(gè)開(kāi)始，給這個(gè)0元素加元素加圈，記作圈，記作 。然后劃去。然后劃去 所在列所在列(行行)的其它的其它0元素，記元素，記作作 ；這表示這列所代表的任務(wù)已指派完，不必再考；這表示這列所代

52、表的任務(wù)已指派完，不必再考慮別人了。慮別人了。 (2)給只有一個(gè)給只有一個(gè)0元素的列元素的列(行行)中的中的0元素加圈，記作元素加圈，記作；然后劃去；然后劃去 所在行的所在行的0元素，記作元素，記作 (3)反復(fù)進(jìn)行反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的兩步，直到盡可能多的0元素都元素都被圈出和劃掉為止。被圈出和劃掉為止。 (4)若仍有沒(méi)有劃圈的若仍有沒(méi)有劃圈的0元素，且同行元素，且同行(列列)的的0元素至元素至少有兩個(gè)，則從剩有少有兩個(gè)，則從剩有0元素最少的行元素最少的行(列列)開(kāi)始，比較這開(kāi)始，比較這行各行各0元素所在列中元素所在列中0元素的數(shù)目，選擇元素的數(shù)目，選擇0元素少的那列元素少

53、的那列的這個(gè)的這個(gè)0元素加圈元素加圈(表示選擇性多的要表示選擇性多的要“禮讓禮讓”選擇性選擇性少的少的)。然后劃掉同行同列的其它。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，元素?？煞磸?fù)進(jìn)行，直到所有直到所有0元素都已圈出和劃掉為止。元素都已圈出和劃掉為止。 （5）若）若 元素的數(shù)目元素的數(shù)目m 等于矩陣的階數(shù)等于矩陣的階數(shù)n，那么這指，那么這指派問(wèn)題的最優(yōu)解已得到。若派問(wèn)題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。則轉(zhuǎn)入下一步。 第三步：作最少的直線覆蓋所有第三步：作最少的直線覆蓋所有0元素。元素。 (1)對(duì)沒(méi)有對(duì)沒(méi)有的行打的行打號(hào)；號(hào)； (2)對(duì)已打?qū)σ汛蛱?hào)的行中所有含號(hào)的行中所有含元素的列

54、打元素的列打號(hào)；號(hào)； (3)再對(duì)打有再對(duì)打有號(hào)的列中含號(hào)的列中含 元素的行打元素的行打號(hào)；號(hào)； (4)重復(fù)重復(fù)(2)，(3)直到得不出新的打直到得不出新的打號(hào)的行、列為止；號(hào)的行、列為止； (5)對(duì)沒(méi)有打?qū)](méi)有打號(hào)的行畫(huà)橫線，有打號(hào)的行畫(huà)橫線，有打號(hào)的列畫(huà)縱線，號(hào)的列畫(huà)縱線，這就得到覆蓋所有這就得到覆蓋所有0元素的最少直線數(shù)元素的最少直線數(shù) l 。l 應(yīng)等于應(yīng)等于m，若不相等，說(shuō)明試指派過(guò)程有誤，回到第二步若不相等，說(shuō)明試指派過(guò)程有誤，回到第二步(4)，另，另行試指派；若行試指派；若 lm n，須再變換當(dāng)前的系數(shù)矩陣，須再變換當(dāng)前的系數(shù)矩陣，以找到以找到n個(gè)獨(dú)立的個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步。

55、元素，為此轉(zhuǎn)第四步。第四步：變換矩陣第四步：變換矩陣(bij)以增加以增加0元素。元素。在沒(méi)有被直線覆蓋的所有元素中找出最小元素，然后在沒(méi)有被直線覆蓋的所有元素中找出最小元素，然后打打各行都減去這最小元素；打各行都減去這最小元素；打各列都加上這最小元各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問(wèn)題仍相同。轉(zhuǎn)回第二步。的最優(yōu)解和原問(wèn)題仍相同。轉(zhuǎn)回第二步。 例一：例一： 任務(wù)任務(wù)人員人員ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119 9118713161491514410413152 2410

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

57、丙丙31104丁丁5982例二、例二、求解過(guò)程如下：求解過(guò)程如下：第一步，變換系數(shù)矩陣：第一步，變換系數(shù)矩陣：2142 289541013895421176)( ijc 0673390245100954 01733402401004545第二步，試指派：第二步，試指派：找到找到 3 3 個(gè)獨(dú)立零元素個(gè)獨(dú)立零元素 但但 m m = 3 3 n = 4 第三步，作最少的直線覆蓋所有第三步，作最少的直線覆蓋所有0 0元素：元素：立零元素的個(gè)數(shù)獨(dú)立零元素的個(gè)數(shù)m等于最少直線數(shù)等于最少直線數(shù)l，即，即lm=3n=4； 第四步，變換矩陣第四步，變換矩陣(

58、 (bij) )以增加以增加0 0元素：沒(méi)有被直線元素：沒(méi)有被直線覆蓋的所有元素中的最小元素為覆蓋的所有元素中的最小元素為1 1，然后打，然后打各行都減各行都減去去1 1；打；打各列都加上各列都加上1 1，得如下矩陣，并轉(zhuǎn)第二步進(jìn)，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派：行試指派： 6244251343000 0 00 0100001000011000得到得到4 4個(gè)獨(dú)個(gè)獨(dú)立零元素，立零元素， 所以最優(yōu)解所以最優(yōu)解矩陣為：矩陣為：0624425134315 6244251343練習(xí)：練習(xí)：115764戊戊69637丁丁86458丙丙9117129乙乙118957甲甲EDCBA費(fèi)費(fèi) 工作工作 用用人員人員43475115764696379645891171291