清華大學(xué)運(yùn)籌學(xué)4整數(shù)規(guī)劃

1、第第五五章章 整數(shù)規(guī)劃整數(shù)規(guī)劃第一節(jié)第一節(jié) 整數(shù)規(guī)劃數(shù)學(xué)模型及解的特點(diǎn)整數(shù)規(guī)劃數(shù)學(xué)模型及解的特點(diǎn)第二節(jié)第二節(jié) 割平面法割平面法第四節(jié)第四節(jié) 0-1型整數(shù)規(guī)劃型整數(shù)規(guī)劃第五節(jié)第五節(jié) 指派問(wèn)題指派問(wèn)題1/68第一節(jié)第一節(jié) 整數(shù)規(guī)劃整數(shù)規(guī)劃模型及模型及解的特點(diǎn)解的特點(diǎn)一一、整數(shù)規(guī)劃模型一般形式整數(shù)規(guī)劃模型一般形式2/683/68 Max z=CX s.t. AX 或或=或或 b X0， b0 C=(c1, c2, , cn ) X=(x1, x2, , xn )T 有些或全部有些或全部xj取整數(shù)取整數(shù) b=(b1, b2, , bm )T a11 a12 a1n A= = a21 a22 a2n .

2、 . . . . . . . . mn am1 am2 amn 4/68若對(duì)決策變量不提整數(shù)要求，則上述規(guī)劃問(wèn)題稱若對(duì)決策變量不提整數(shù)要求，則上述規(guī)劃問(wèn)題稱為該為該整數(shù)規(guī)劃問(wèn)題的松弛整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題問(wèn)題。若松弛。若松弛問(wèn)題是線問(wèn)題是線性規(guī)劃問(wèn)題，則該性規(guī)劃問(wèn)題，則該整數(shù)規(guī)劃整數(shù)規(guī)劃問(wèn)題叫做問(wèn)題叫做整數(shù)線性規(guī)整數(shù)線性規(guī)劃劃。整數(shù)線性規(guī)劃有如下幾種類型：整數(shù)線性規(guī)劃有如下幾種類型：1. 純整數(shù)線性規(guī)劃純整數(shù)線性規(guī)劃全部決策變量須取整數(shù)，全部決策變量須取整數(shù)，亦稱亦稱全整數(shù)規(guī)劃全整數(shù)規(guī)劃。 2. 混合混合整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃部分決策變量須部分決策變量須取取整整數(shù)。數(shù)。3. 0-1型型整數(shù)線

3、性規(guī)劃整數(shù)線性規(guī)劃決策變量只取決策變量只取0或或1的的整數(shù)線性規(guī)劃。整數(shù)線性規(guī)劃。 5/68二、二、 整數(shù)規(guī)劃之整數(shù)規(guī)劃之例例例例1某商場(chǎng)擬用集裝箱托運(yùn)兩種貨物，每箱體某商場(chǎng)擬用集裝箱托運(yùn)兩種貨物，每箱體積、重量、可獲利潤(rùn)以及所受限制如下表。積、重量、可獲利潤(rùn)以及所受限制如下表。問(wèn)：兩種貨物各托運(yùn)多少，利潤(rùn)最大？問(wèn)：兩種貨物各托運(yùn)多少，利潤(rùn)最大？ 貨物貨物體積體積立方米立方米/箱箱重量重量百斤百斤/箱箱利潤(rùn)利潤(rùn)千元千元/箱箱服裝服裝5220玩具玩具4510托運(yùn)限制托運(yùn)限制24136/68用用x1和和x2將表示服裝和玩具的托運(yùn)箱數(shù)，則該問(wèn)將表示服裝和玩具的托運(yùn)箱數(shù)，則該問(wèn)題可表示如下：題可表示如

4、下： Max z=20 x1+10 x2 (1) s.t. 5x1 +4x2 24 (2) 2x1+5x2 13 (3) x1，x20， (4) x1，x2取整數(shù)取整數(shù) (5)7/68例例2某地區(qū)要建水電站，有某地區(qū)要建水電站，有15處可行，可用資處可行，可用資金總額為金總額為B。各處所需投資和預(yù)期收益分別為。各處所需投資和預(yù)期收益分別為aj和和cj (j=1, 3, , 15)。要求是：要求是：若在第一處建，第二處也要建；若在第一處建，第二處也要建；但是，第二但是，第二處建處建；第一處不一定建；第一處不一定建；第三和第四處至少有一處必須建；第三和第四處至少有一處必須建；第五、六和第七處建兩個(gè)

5、。第五、六和第七處建兩個(gè)。問(wèn)問(wèn)：如何在這：如何在這15處布置水電站，才能預(yù)期最大收處布置水電站，才能預(yù)期最大收益？益？8/68n9/68例例3現(xiàn)有現(xiàn)有A1和和A2生產(chǎn)某產(chǎn)品，在生產(chǎn)某產(chǎn)品，在B1、B2 、B3和和B4銷售。因供不應(yīng)求，計(jì)劃再建一廠。新廠有方銷售。因供不應(yīng)求，計(jì)劃再建一廠。新廠有方案案A3和和A4，建成后年生產(chǎn)費(fèi)用分別為，建成后年生產(chǎn)費(fèi)用分別為1200和和1500萬(wàn)元。從產(chǎn)地到銷地運(yùn)費(fèi)見下表。問(wèn)哪一方案使萬(wàn)元。從產(chǎn)地到銷地運(yùn)費(fèi)見下表。問(wèn)哪一方案使新廠建成后年運(yùn)費(fèi)與生產(chǎn)費(fèi)用總和最少？新廠建成后年運(yùn)費(fèi)與生產(chǎn)費(fèi)用總和最少？ B1B2B3B4產(chǎn)能（千噸產(chǎn)能（千噸/年）年）A1293440

6、0A28357600A37612200A44525200需求量需求量（千噸（千噸/年）年） 350400 30015010/68n11/68三、解的特點(diǎn)三、解的特點(diǎn) 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃的解一定是松弛問(wèn)題的解的解一定是松弛問(wèn)題的解，可行域是松弛問(wèn)題可行域的子集。可行域是松弛問(wèn)題可行域的子集。 目標(biāo)函數(shù)值不會(huì)超過(guò)松弛問(wèn)題目標(biāo)函數(shù)值。目標(biāo)函數(shù)值不會(huì)超過(guò)松弛問(wèn)題目標(biāo)函數(shù)值。 反過(guò)來(lái)，反過(guò)來(lái)，不一定成立不一定成立。 不能不能將松弛問(wèn)題的解四舍五入當(dāng)作將松弛問(wèn)題的解四舍五入當(dāng)作整數(shù)線性整數(shù)線性規(guī)劃的解。規(guī)劃的解。 xj=1或或0， j=1, 3, , 15 12/68現(xiàn)在看托運(yùn)問(wèn)題：現(xiàn)在看托運(yùn)問(wèn)題：

7、 Max z=20 x1+10 x2 s.t. 5x1 +4x2 24 2x1+5x2 13 x1，x20， x1，x2取整數(shù)取整數(shù)先用圖解法解先用圖解法解松馳問(wèn)題松馳問(wèn)題，得得13/684x1x23225x1+4x2=24z=20 x1+10 x2=96z=15oA(4.8, 0)2x1+5x2 =136z=90(4, 1)z=1014/68最優(yōu)解最優(yōu)解是是(x1, x2)=(4.8, 0) Max z=96再看整數(shù)規(guī)劃問(wèn)題再看整數(shù)規(guī)劃問(wèn)題，若若取取x1=5，x2=0，破壞了約束條件，破壞了約束條件5x1 +4x224若取若取x1=4，x2=0 ， z=20 x1+10 x2=80，實(shí)際上實(shí)

8、際上，(x1, x2)=(4, 1)也是可行解，也是可行解，z=90可見，將松弛問(wèn)題的解四舍五入不能求得整數(shù)線可見，將松弛問(wèn)題的解四舍五入不能求得整數(shù)線性規(guī)劃的解。性規(guī)劃的解。第二節(jié)第二節(jié) 解整數(shù)規(guī)劃的割平面法解整數(shù)規(guī)劃的割平面法 就是在解松馳問(wèn)題過(guò)程就是在解松馳問(wèn)題過(guò)程中中逐一去掉非整數(shù)逐一去掉非整數(shù)解域，尋找整數(shù)解的方法，也就是解域，尋找整數(shù)解的方法，也就是“切割切割”可可行域平面。切割的辦法是增加約束條件。行域平面。切割的辦法是增加約束條件。15/68He (born 7 May 1929 in Brooklyn) is an applied mathematician. He work

9、ed at IBM as a researcher and later as an executive and his research led to the creation of new areas of applied mathematics. After his career in the corporate world, he became the president of the Alfred P. Sloan Foundation, where he oversaw programs dedicated to broadening public understanding in

10、three key areas: the economic importance of science and research; the effects of globalization on the United States; and the role of technology in education. 16/68Ralph Edward Gomory 17/68例例1 Max z=x1+x2 s.t. -x1 +x2 1 3x1+x2 4 x1，x20， x1，x2取整數(shù)取整數(shù)先用圖解法解先用圖解法解松馳問(wèn)題松馳問(wèn)題，得得18/68x1x2211-x1+x2=1z=x1+x2=2.

11、5o4/33x1+x2 =4A(3/4, 7/4)C(1, 1)R19/68最優(yōu)解最優(yōu)解是是(x1, x2)=(3/4, 7/4) Max z=10/4整數(shù)整數(shù)點(diǎn)點(diǎn)C不是頂點(diǎn)不是頂點(diǎn)，所以目標(biāo)函數(shù)就向非整數(shù)點(diǎn)所以目標(biāo)函數(shù)就向非整數(shù)點(diǎn)A呼嘯而去，若將呼嘯而去，若將C改成頂點(diǎn)，就可能攔截目標(biāo)改成頂點(diǎn)，就可能攔截目標(biāo)函數(shù)函數(shù)。20/68x1x2211-x1+x2=1o4/33x1+x2 =4C(1, 1)整數(shù)點(diǎn)整數(shù)點(diǎn)C已已經(jīng)改成頂點(diǎn)，但還經(jīng)改成頂點(diǎn)，但還攔不住目標(biāo)函數(shù)。攔不住目標(biāo)函數(shù)。DAR 21/68x1x2211-x1+x2=1o4/33x1+x2 =4C(1, 1)再切一次，整數(shù)頂點(diǎn)再切一次，

12、整數(shù)頂點(diǎn)C攔住了攔住了目標(biāo)函數(shù)。目標(biāo)函數(shù)。DBAR 22/68如何構(gòu)造用來(lái)切割平面的直線呢？如何構(gòu)造用來(lái)切割平面的直線呢？在松弛問(wèn)題約束條件中添加松弛變量：在松弛問(wèn)題約束條件中添加松弛變量： -x1 +x2 +x3 =1 3x1+x2 +x4 = 4 x1，x20， 然后，列出初始單純形表：然后，列出初始單純形表：23/68cj1100icBxBB-1bx1x2x3x40 x31-1110-0 x4431014/3z1100j0 x37/304/311/37/41x14/311/301/34z02/30-1/3j24/68cj1100icBxBB-1bx1x2x3x41x27/4013/41/

13、41x13/410-1/41/4z10/400-1/2-1/2j從中可得到從中可得到 x1 -x3/4+x4/4 =3/4 x2+3x3/4 +x4/4 =7/4將其中的系數(shù)和常數(shù)項(xiàng)均分解成整數(shù)和非整數(shù)兩將其中的系數(shù)和常數(shù)項(xiàng)均分解成整數(shù)和非整數(shù)兩部分：部分：25/68可得到可得到 x1 -x3 = 3/4-(3x3/4+x4/4) x2 1 =3/4- (3x3/4 +x4/4)從從 -x1 +x2 +x3 =1 3x1+x2 +x4 = 4可知，可知，x1和和x2若是非負(fù)整數(shù)，若是非負(fù)整數(shù)， x3和和x4也是非負(fù)整也是非負(fù)整數(shù)。所以，根據(jù)數(shù)。所以，根據(jù) x1 -x3 = 3/4-(3x3/4

14、+x4/4) x2 1 =3/4- (3x3/4 +x4/4)左邊判斷，左邊判斷，3/4- (3x3/4 +x4/4)應(yīng)當(dāng)是整數(shù)，應(yīng)當(dāng)是整數(shù)，26/68而而 (3x3/4 +x4/4)是正數(shù)，一定要比是正數(shù)，一定要比3/4大，兩者之大，兩者之差才可能是整數(shù)，即，必須有差才可能是整數(shù)，即，必須有3x3/4 +x4/43/4，-3x3 -x4-3，添加松弛變量添加松弛變量x5后得到：后得到： -3x3 -x4+x5= -3，叫做，叫做切割方程，將其添加到最終單純形表中，得切割方程，將其添加到最終單純形表中，得cj11000icBxBB-1bx1x2x3x4x51x27/4013/41/401x13

15、/410-1/41/400 x5-300-3-11z-1/2/-3-1/2/-1-j/alj27/68最終單純形表最終單純形表已經(jīng)得到整數(shù)線性規(guī)劃已經(jīng)得到整數(shù)線性規(guī)劃最優(yōu)解。最優(yōu)解。(x1, x2, x3, x4)=(1, 1, 1, 0)，Max z=2。cj11000icBxBB-1bx1x2x3x4x51x2101001/41x111001/3-1/120 x310011/3-1/3z2000-1/3-1/6j/alj28/68n29/68n30/68例例2用用Gomory切割法求解如下問(wèn)題。切割法求解如下問(wèn)題。Max z=3x1-x2 s.t. 3x1 -2x2 3 5x1+4x2 1

16、0 2x1+ x2 5，x1，x2為非負(fù)為非負(fù)整數(shù)整數(shù)。先解松馳問(wèn)題先解松馳問(wèn)題 Max z=3x1-x2+0 x3+0 x4-Mx5+0 x6 s.t. 3x1 -2x2+x3 =3 5x1+4x2 -x4 +x5 =10 2x1+ x2 +x6 =5 x1，x2031/68cj3-100-M0icBxBB-1bx1x2x3x4x5x60 x333-210003/3-Mx510540-11010/50 x652100015/2z5M+34M-10-M00初始初始單純形表單純形表3x111-2/31/3000-Mx55022/3-5/3-11015/220 x6307/3-2/30019/7z

17、022M/3 -5M/3 -M0032/683x116/11102/11-1/11-0-1x215/2201-5/22-3/22-0-0 x631/2200-3/227/22-131/7z00-17/222/11-0cj3-100-M0icBxBB-1bx1x2x3x4x5x63x113/7101/70-2/7-1x29/701-2/70-3/70 x431/700-3/71-22/7z30/700-5/70-3/733/68構(gòu)造切割方程，構(gòu)造切割方程，13/7、9/7和和31/7中真分?jǐn)?shù)最大的中真分?jǐn)?shù)最大的是是13/7，對(duì)應(yīng)最終單純形表中第一行，對(duì)應(yīng)最終單純形表中第一行，所以，所以，選選取取

18、 x1 + x3/7 + 2x6/7=13/7 x1 -1 =6/7- x3/7 - 2x6/7 -x3/7-2x6/7 -6/7添入松弛變量添入松弛變量x7 得得 -x3/7-2x6/7 +x7 = -6/7將其添入上面的最終單純形表，得將其添入上面的最終單純形表，得34/683x113/7101/702/70-1x29/701-2/703/700 x431/700-3/7122/700 x7-6/700-1/70-2/71z00503/2cj3-10000icBxBB-1bx1x2x3x4x6x73x11100001-1x2001-1/2003/20 x4-500-210110 x6300

19、1/201-7/2001/400-35/68cj3-10000icBxBB-1bx1x2x3x4x6x73x11100001-1x25/4010-1/40-5/40 x35/2001-1/20-11/20 x67/40001/41-3/4z7/4000-1/40-17/4構(gòu)造切割方程：構(gòu)造切割方程：5/4、5/2和和7/4真分?jǐn)?shù)最大的是真分?jǐn)?shù)最大的是7/4，對(duì)應(yīng)最終單純形表第四行，所以，選取，對(duì)應(yīng)最終單純形表第四行，所以，選取 x4/4+x5-3x7/4=7/4，即，即x5 -x7-1= 3/4 -x4/4-x7/4，3/4 -x4/4-x7/40，添入松弛變量，添入松弛變量x8 得得-x4/

20、4-x7/4 +x8 = -3/4，添入上面最終單純形表，得，添入上面最終單純形表，得36/68cj3-100000icBxBB-1bx1x2x3x4x6x7x83x111000010-1x25/4010-1/40-5/400 x35/2001-1/20-11/200 x67/40001/41-3/400 x8-3/4000-1/40-1/410001017037/68cj3-100000icBxBB-1bx1x2x3x4x6x7x83x111000010-1x2201000-1-10 x3400100-5-20 x6100001-110 x43000101-4100000-4-1X*=(x1

21、, x2, x3, x4, x6, x7, x8)=(1, 2, 4, 3, 1, 0, 0)38/68為了說(shuō)明切割方程的幾何意義，回頭看：為了說(shuō)明切割方程的幾何意義，回頭看： x1 -1 =6/7- x3/7 - 2x6/7和和x5 -x7-1= 3/4 -x4/4-x7/4，另外另外，從松馳問(wèn)題標(biāo)準(zhǔn)形式約束條件知從松馳問(wèn)題標(biāo)準(zhǔn)形式約束條件知 3x1 -2x2+x3 =3 5x1+4x2 -x4 +x5 =10 2x1+ x2 +x6 =5 即即 x3=3-3x1 +2x2 x5=10-5x1-4x2 +x4 x6 =5-2x1-x2將其代入切割方程，并考慮到將其代入切割方程，并考慮到6/7

22、- x3/7 - 2x6/7 0， 3/4 -x4/4-x7/4 0 ，39/68得到：得到： x1 -1 0和和x1 +x23這就是這就是用用x1和和x2表示的切割方程。表示的切割方程。下面下面，逐次分割松弛問(wèn)題的可行域逐次分割松弛問(wèn)題的可行域，逐步求得整逐步求得整數(shù)解。數(shù)解。40/68x1x2211o23x1-2x2 =3A(13/7, 9/7)R2.52.52x1+x2 =55x1+4x2 =10z=3x1-x2 =30/7未切割時(shí)的松弛問(wèn)題未切割時(shí)的松弛問(wèn)題41/68x1x2211o23x1-2x2 =3B(1, 5/4)R2.52.52x1+x2 =55x1+4x2 =10z=3x1

23、-x2 =7/4用用x1=1切割切割x1=1A(13/7, 9/7)42/68x1x2211o23x1-2x2 =3C(1, 2)R”2.52.5x1+x2 =35x1+4x2 =10z=3x1-x2 =1用用x1+x2=3切割切割x1=132x1+x2 =5B(1, 5/4)A(13/7, 9/7)第四節(jié)第四節(jié) 0-1整數(shù)規(guī)劃整數(shù)規(guī)劃43/68一、一、0-1變量及其應(yīng)用變量及其應(yīng)用1. 互斥的約束條件互斥的約束條件前面托運(yùn)問(wèn)題，體積限制條件是前面托運(yùn)問(wèn)題，體積限制條件是 5x1+4x224現(xiàn)假設(shè)托運(yùn)有陸運(yùn)和水運(yùn)兩種方式，水運(yùn)時(shí)體現(xiàn)假設(shè)托運(yùn)有陸運(yùn)和水運(yùn)兩種方式，水運(yùn)時(shí)體積限制條件是積限制條件是

24、 7x1+3x2 45 為了將這兩個(gè)互斥的限制條件一塊考慮，借為了將這兩個(gè)互斥的限制條件一塊考慮，借用一個(gè)用一個(gè)0-1變量變量y，令，令 y=0，陸運(yùn)，陸運(yùn) y=1，水運(yùn)，水運(yùn)44/68這樣一來(lái)，上述兩個(gè)互斥約束條件都可以寫入這樣一來(lái)，上述兩個(gè)互斥約束條件都可以寫入模型：模型： 5x1+4x224+yM 7x1+3x245+(1-y)MM是足夠大的整數(shù)。是足夠大的整數(shù)。y=0，陸運(yùn)，陸運(yùn)，7x1+3x245+M不起作用；不起作用；y=1，水運(yùn)，水運(yùn)，5x1+4x224+M。 y在目標(biāo)函數(shù)中在目標(biāo)函數(shù)中的系數(shù)為的系數(shù)為0。45/6846/68二、二、0-1型整數(shù)線性規(guī)劃解法型整數(shù)線性規(guī)劃解法 若

25、有若有n個(gè)個(gè)0-1型決策變量，就會(huì)有型決策變量，就會(huì)有2n個(gè)取值個(gè)取值情況。問(wèn)題的解就在這情況。問(wèn)題的解就在這2n種情況之中。若種情況之中。若n=10，則有，則有1024種情況，手算工作量可觀。種情況，手算工作量可觀。 如果能很快發(fā)現(xiàn)這如果能很快發(fā)現(xiàn)這2n種種情況情況之中不符合要之中不符合要求者，就可以節(jié)省計(jì)算時(shí)間。求者，就可以節(jié)省計(jì)算時(shí)間。 我們就遵循這個(gè)思路尋找解題辦法。我們就遵循這個(gè)思路尋找解題辦法。47/68例例1求解求解0-1型整數(shù)線性規(guī)劃型整數(shù)線性規(guī)劃Max z=3x1-2x2+5x3s.t. x1+2x2-x3 2 (a) x1+4x2+x34 (b) x1+x2 3 (c) 4

26、x2+x3 6 (d) x1, x2, x3=1,048/6849/68 x1, x2, x3za b c d過(guò)濾條件過(guò)濾條件0 0 00 z00 0 15 z50 1 0-2無(wú)須檢查無(wú)須檢查0 1 13無(wú)須檢查無(wú)須檢查1 0 03無(wú)須檢查無(wú)須檢查1 0 18 z81 1 01無(wú)須檢查無(wú)須檢查1 1 16無(wú)須檢查無(wú)須檢查X* =(x1, x2, x3)T= (1, 0, 1)T，Max z=8計(jì)算工作量還需減少。計(jì)算工作量還需減少。例例2求解求解0-1型整數(shù)線性規(guī)劃型整數(shù)線性規(guī)劃Min z=3x1+7x2-x3+x4s.t. 2x1-x2+ x3 -x41 x1 -x2+6x3+4x48 5x

27、1+3x2 +x45 x1, x2, x3, x4=1,0求目標(biāo)函數(shù)最大的問(wèn)題按價(jià)值系數(shù)由小到大重求目標(biāo)函數(shù)最大的問(wèn)題按價(jià)值系數(shù)由小到大重新排列；求最小問(wèn)題，反過(guò)來(lái)，這樣，可減少新排列；求最小問(wèn)題，反過(guò)來(lái)，這樣，可減少計(jì)算量。計(jì)算量。50/68本例可如下重新排列本例可如下重新排列Min z=7x2+3x1+x4-x3s.t. -x2 +2x1 -x4 + x31 -x2 + x1+4x4 +6x38 3x2 +5x1+x4 5 x2, x1, x4, x3 =1,051/68第五節(jié)第五節(jié) 指派問(wèn)題指派問(wèn)題52/68一、指派問(wèn)題標(biāo)準(zhǔn)形式及數(shù)學(xué)模型一、指派問(wèn)題標(biāo)準(zhǔn)形式及數(shù)學(xué)模型標(biāo)準(zhǔn)形式指派問(wèn)題標(biāo)準(zhǔn)

28、形式指派問(wèn)題定義：定義：已知已知n種資源用于種資源用于n種用途的代價(jià)種用途的代價(jià)分別分別為為cij(i, j=1, 2, , n)，如何在代價(jià)最小且每一種用途，如何在代價(jià)最小且每一種用途只用一種資源條件下分派這些資源？或者在只用一種資源條件下分派這些資源？或者在cij是收益時(shí)，如何是收益時(shí)，如何分派這些分派這些資源，才能取得最大資源，才能取得最大收益？收益？一般用一般用C表示指派問(wèn)題的系數(shù)矩陣表示指派問(wèn)題的系數(shù)矩陣(cij)。令。令xij令令為為nn個(gè)個(gè)0-1型變量，型變量， xij=1表示為第表示為第j種用途指種用途指派第派第i種資源，種資源， xij=0表示未為表示未為第第j種用途指派第種

29、用途指派第i種種資源。資源。53/6854/68例例1某公司最近在五處中標(biāo)，有五人可派。某公司最近在五處中標(biāo)，有五人可派。他們的經(jīng)驗(yàn)、語(yǔ)言、習(xí)慣、能力、社會(huì)交往和他們的經(jīng)驗(yàn)、語(yǔ)言、習(xí)慣、能力、社會(huì)交往和個(gè)人喜好等，使其在不同地方和不同工程上付個(gè)人喜好等，使其在不同地方和不同工程上付出的代價(jià)如下表。問(wèn)：如何為他們分派地點(diǎn)，出的代價(jià)如下表。問(wèn)：如何為他們分派地點(diǎn)，公司才代價(jià)最?。抗静糯鷥r(jià)最??？55/68阿聯(lián)酋阿聯(lián)酋新加坡新加坡香港香港關(guān)島關(guān)島蘇丹蘇丹王聰王聰4871512張猛張猛79171410李志李志691287孫爽孫爽6714610何立何立691210656/68二、匈牙利解法二、匈牙利解法

30、上述的枚舉法可以解指派問(wèn)題上述的枚舉法可以解指派問(wèn)題，但匈牙利法更但匈牙利法更好好。該法利用了。該法利用了C中獨(dú)立零元素的性質(zhì)。中獨(dú)立零元素的性質(zhì)。若從若從C中某行或某列各元素減去或在其上加上某中某行或某列各元素減去或在其上加上某常數(shù)常數(shù)，得到得到的新矩陣對(duì)應(yīng)的指派問(wèn)題與原矩陣的新矩陣對(duì)應(yīng)的指派問(wèn)題與原矩陣對(duì)應(yīng)者同解，即對(duì)應(yīng)者同解，即X =(xij)相同。相同。該法一般步驟該法一般步驟：Step1變換變換C，先各行分別減去本行最小元素；，先各行分別減去本行最小元素；再各列分別再各列分別減去減去本列最小本列最小元素元素；使每行、每列；使每行、每列至少有一個(gè)零，但不出現(xiàn)小于零者。然后，至少有一個(gè)零

31、，但不出現(xiàn)小于零者。然后，Step2在新在新C中確定獨(dú)立零，個(gè)數(shù)若為中確定獨(dú)立零，個(gè)數(shù)若為n，則已經(jīng)，則已經(jīng)得到最優(yōu)解。若少于得到最優(yōu)解。若少于n，則劃直線覆蓋零，并，則劃直線覆蓋零，并57/68找出最少條數(shù)覆蓋所有獨(dú)立零的直線全體。然找出最少條數(shù)覆蓋所有獨(dú)立零的直線全體。然后轉(zhuǎn)后轉(zhuǎn)step3。對(duì)于對(duì)于C非非負(fù)的指派問(wèn)題，若從中找出負(fù)的指派問(wèn)題，若從中找出n個(gè)處于個(gè)處于不同行、不同列的零，總代價(jià)一定為零，最優(yōu)不同行、不同列的零，總代價(jià)一定為零，最優(yōu)。若某行（列）有多個(gè)零，選定一個(gè)后，不能。若某行（列）有多個(gè)零，選定一個(gè)后，不能再選別的。所以，所謂再選別的。所以，所謂n個(gè)零，一定應(yīng)是獨(dú)立個(gè)零，一

32、定應(yīng)是獨(dú)立的。如果獨(dú)立零個(gè)數(shù)少于的。如果獨(dú)立零個(gè)數(shù)少于n，找出最少條數(shù)覆找出最少條數(shù)覆蓋所有獨(dú)立零的直線全體蓋所有獨(dú)立零的直線全體。Step3繼續(xù)變換繼續(xù)變換C，然后，回到，然后，回到step2。以下舉例說(shuō)明這三個(gè)步驟。以下舉例說(shuō)明這三個(gè)步驟。58/68例例2派項(xiàng)目經(jīng)理求最小代價(jià)問(wèn)題。派項(xiàng)目經(jīng)理求最小代價(jià)問(wèn)題。 4 8 7 15 12 7 9 17 14 10 C = 6 9 12 8 7 6 7 14 6 10 6 9 12 10 6Step1 變換變換C，先各行分別減去本行最小元素先各行分別減去本行最小元素；再各列分別減去本列最小；再各列分別減去本列最小元素：元素：59/68 0 4 3

33、11 8 0 2 10 7 3 C 0 3 6 2 1 0 1 8 0 4 0 3 6 4 0 0 3 0 11 8 0 1 7 7 3 0 2 3 2 1 = C 0 0 5 0 4 0 2 3 4 0C每行每列都已有零。每行每列都已有零。60/68 3 11 8 1 7 7 3 C = 2 3 2 1 5 4 2 3 4 只有四個(gè)獨(dú)立只有四個(gè)獨(dú)立零，故須找能覆蓋所有零零，故須找能覆蓋所有零數(shù)目最少數(shù)目最少的直線的直線。 3 11 8 1 7 7 3 C = 2 3 2 1 5 4 2 3 4 61/6800000000 3 11 8 1 7 7 3 C = 2 3 2 1 5 4 為了為了在未覆蓋在未覆蓋 2 3 4 行列中出現(xiàn)零行列中出現(xiàn)零，從中找出最小元素，從中找出最小元素1，從第二、三行減去。，從第二、三行減去。 3 11 8 -1 0 6 6 2 C = -1 1 2 1 0 5 4 2 3 4 62/680000000由于第一列出現(xiàn)負(fù)數(shù)，該列再加由于第一列出現(xiàn)負(fù)數(shù)，該列再加1： 1 3 0 11 8 0 0 6 6 2 C 0 1 2 1 0 =C“ 1 0 5 0 4 1 2 3 4 0 回到回到step2 1 3 11 8 6 6 2 C“ = 1 2 1 1 5 4 1 2 3 4 63/6800