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

1、 趙 超建筑工程學院 2013年1月整數(shù)規(guī)劃的特點及應用整數(shù)規(guī)劃的特點及應用分支定界法分支定界法分配問題與匈牙利法分配問題與匈牙利法Page 3要求一部分或全部決策變量取整數(shù)值的規(guī)劃問題稱為要求一部分或全部決策變量取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標函數(shù)和約束條件整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若該松弛構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若該松弛問題是一個線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。問題是一個線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。整數(shù)線性規(guī)劃數(shù)學模型的一般形式：整數(shù)線性規(guī)劃數(shù)學模型的一

2、般形式： 且且部部分分或或全全部部為為整整數(shù)數(shù)或或 n)1.2(j 0)2 . 1( )min(max11jnjijijnjjjxmibxaxcZZPage 4 純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃。線性規(guī)劃。 混合整數(shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，混合整數(shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。 0-1型整數(shù)線性規(guī)劃：決策變量只能取值型整數(shù)線性規(guī)劃：決策變量只能取值0或或1的整數(shù)線性規(guī)的整數(shù)線性規(guī)劃。劃。Page 5例例5.1 工廠

3、工廠A1和和A2生產(chǎn)某種物資。由于該種物資供不應求，故需要生產(chǎn)某種物資。由于該種物資供不應求，故需要再建一家工廠。相應的建廠方案有再建一家工廠。相應的建廠方案有A3和和A4兩個。這種物資的需求地兩個。這種物資的需求地有有B1,B2,B3,B4四個。各工廠年生產(chǎn)能力、各地年需求量、各廠至各四個。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運費需求地的單位物資運費cij，見下表：，見下表：B1B2B3B4年生產(chǎn)能力年生產(chǎn)能力A12934400A28357600A37612200A44525200年需求量年需求量350400300150工廠工廠A3或或A4開工后，每年的生產(chǎn)費用估計分別為

4、開工后，每年的生產(chǎn)費用估計分別為1200萬或萬或1500萬萬元。現(xiàn)要決定應該建設(shè)工廠元?，F(xiàn)要決定應該建設(shè)工廠A3還是還是A4，才能使今后每年的總費用，才能使今后每年的總費用最少。最少。Page 6解：這是一個物資運輸問題，特點是事先不能確定應該建解：這是一個物資運輸問題，特點是事先不能確定應該建A3還是還是A4中哪一個，因而不知道新廠投產(chǎn)后的實際生產(chǎn)物資。中哪一個，因而不知道新廠投產(chǎn)后的實際生產(chǎn)物資。為此，引入為此，引入0-1變量：變量：)2 , 1(01 iyi若不建工廠若不建工廠若建工廠若建工廠再設(shè)再設(shè)xij為由為由Ai運往運往Bj的物資數(shù)量，單位為千噸；的物資數(shù)量，單位為千噸；z表示總費

5、用，表示總費用，單位萬元。單位萬元。則該規(guī)劃問題的數(shù)學模型可以表示為：則該規(guī)劃問題的數(shù)學模型可以表示為：Page 7 )2 , 1(1 , 0)4 , 3 , 2 , 1,(0200200600400150300400350.15001200min244434241134333231242322211413121144342414433323134232221241312111414121iyjixyxxxxyxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsyyxcziijijijij混合整數(shù)規(guī)劃問題混合整數(shù)規(guī)劃問題Page 8例例5.2 現(xiàn)有資金總額為現(xiàn)有資金總額為B?？晒┻x擇的

6、投資項目有。可供選擇的投資項目有n個，項目個，項目j所需投資額和預期收益分別為所需投資額和預期收益分別為aj和和cj（j1,2,.,n），此外由），此外由于種種原因，有三個附加條件：于種種原因，有三個附加條件：n若選擇項目若選擇項目1，就必須同時選擇項目，就必須同時選擇項目2。反之不一定。反之不一定n項目項目3和和4中至少選擇一個；中至少選擇一個；n項目項目5,6,7中恰好選擇中恰好選擇2個。個。應該怎樣選擇投資項目，才能使總預期收益最大。應該怎樣選擇投資項目，才能使總預期收益最大。Page 9解：對每個投資項目都有被選擇和不被選擇兩種可能，因此解：對每個投資項目都有被選擇和不被選擇兩種可能，

7、因此分別用分別用0和和1表示，令表示，令xj表示第表示第j個項目的決策選擇，記為：個項目的決策選擇，記為：),.,2 , 1(01njjjxj 不不投投資資對對項項目目投投資資對對項項目目投資問題可以表示為：投資問題可以表示為： ）（或或者者nxxxxxxxxBxatsxczjnjjjnjjj, 2 , 1j1021.max765431211Page 10例例5.3 5.3 指派問題或分配問題。人事部門欲安排四人到四個不指派問題或分配問題。人事部門欲安排四人到四個不同崗位工作，每個崗位一個人。經(jīng)考核四人在不同崗位的成同崗位工作，每個崗位一個人。經(jīng)考核四人在不同崗位的成績（百分制）如表所示，如何

8、安排他們的工作使總成績最好?？儯ò俜种疲┤绫硭?，如何安排他們的工作使總成績最好。 工作工作人員人員ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088Page 11設(shè)設(shè) 工工作作時時人人做做不不分分配配第第工工作作時時人人做做分分配配第第jijixij01數(shù)學模型如下：數(shù)學模型如下：4443424134333231242322211413121188809086907983829578879590739285maxxxxxxxxxxxxxxxxxZ 要求每人做一項工作，約束條件為：要求每人做一項工作，約束條件為： 111144434241343332312

9、423222114131211xxxxxxxxxxxxxxxxPage 12每項工作只能安排一人，約束條件為：每項工作只能安排一人，約束條件為： 111144342414433323134232221241312111xxxxxxxxxxxxxxxx變量約束：變量約束：4 ,3 ,2 , 110 jixij、，或或Page 13 整數(shù)規(guī)劃問題的可行解集合是它松弛問題可行解集合的一整數(shù)規(guī)劃問題的可行解集合是它松弛問題可行解集合的一個子集，任意兩個可行解的凸組合不一定滿足整數(shù)約束條件，個子集，任意兩個可行解的凸組合不一定滿足整數(shù)約束條件，因而不一定仍為可行解。因而不一定仍為可行解。 整數(shù)規(guī)劃問題的

10、可行解一定是它的松弛問題的可行解（反整數(shù)規(guī)劃問題的可行解一定是它的松弛問題的可行解（反之不一定），但其最優(yōu)解的目標函數(shù)值不會優(yōu)于后者最優(yōu)解之不一定），但其最優(yōu)解的目標函數(shù)值不會優(yōu)于后者最優(yōu)解的目標函數(shù)值。的目標函數(shù)值。Page 14例例5.3 設(shè)整數(shù)規(guī)劃問題如下設(shè)整數(shù)規(guī)劃問題如下 且且為為整整數(shù)數(shù)0,13651914max21212121xxxxxxxxZ首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。題）。 0,13651914max21212121xxxxxxxxZPage 15用圖解法求出最優(yōu)解為：用圖解法求出最優(yōu)解為：x13

11、/2, x2 = 10/3，且有，且有Z = 29/6現(xiàn)求整數(shù)解現(xiàn)求整數(shù)解(最優(yōu)解最優(yōu)解):如用舍如用舍入取整法可得到入取整法可得到4個點即個點即(1，3),(2，3),(1，4),(2，4)。顯然，。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。解。x1x233(3/2,10/3)按整數(shù)規(guī)劃約束條件，其可行按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如右的可行解集是一個有限集，如右圖所示。圖所示。其中其中(2,2),(3,1)點的目點的目標函數(shù)值最大，即為

12、標函數(shù)值最大，即為Z=4。Page 16整數(shù)規(guī)劃問題的求解方法：整數(shù)規(guī)劃問題的求解方法： 分支定界法和割平面法分支定界法和割平面法 匈牙利法（指派問題）匈牙利法（指派問題）Page 171）求整數(shù)規(guī)劃的松弛問題最優(yōu)解；）求整數(shù)規(guī)劃的松弛問題最優(yōu)解；若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解,否否則轉(zhuǎn)下一步；則轉(zhuǎn)下一步；2）分支與定界：）分支與定界：任意選一個非整數(shù)解的變量任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束：，在松弛問題中加上約束：xixi 和和 xixi+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問

13、題組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目標值是分枝問題的下界。標值是分枝問題的下界。檢查所有分枝的解及目標函數(shù)值，若某分枝的解是整數(shù)并且目標檢查所有分枝的解及目標函數(shù)值，若某分枝的解是整數(shù)并且目標函數(shù)值大于（函數(shù)值大于（max）等于其它分枝的目標值，則將其它分枝剪去不再計）等于其它分枝的目標值，則將其它分枝剪去不再計算，若還存在非整數(shù)解并且目標值大于算，若還存在非整數(shù)解并且目標值大于(max)整數(shù)解的目標值，需要繼續(xù)整數(shù)解的目標值，需要繼續(xù)分枝，再

14、檢查，直到得到最優(yōu)解。分枝，再檢查，直到得到最優(yōu)解。Page 18例例5.4 用分枝定界法求解整數(shù)規(guī)劃問題用分枝定界法求解整數(shù)規(guī)劃問題 且且全全為為整整數(shù)數(shù)0,4 30 652 5min211212121xxxxxxxxxZ解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題( (原整數(shù)規(guī)劃原整數(shù)規(guī)劃問題的松馳問題問題的松馳問題) ) 0,4 30 652 5min211212121xxxxxxxxxZLPIPPage 19用圖解法求松弛問題的最優(yōu)解，如圖所示。用圖解法求松弛問題的最優(yōu)解，如圖所示。x1x23(18/11,40/11)21123x118/11,

15、x2 =40/11Z=218/11(19.8)即即Z 也是也是IP最小值的下限。最小值的下限。對于對于x118/111.64，取值取值x1 1， x1 2對于對于x2 =40/11 3.64，取值，取值x2 3 ，x2 4先將（先將（LP）劃分為（）劃分為（LP1）和（和（LP2）,取取x1 1, x1 2Page 20分支：分支： 且且為為整整數(shù)數(shù)0,1 4 30 652 )1(5min2111212121xxxxxxxxIPxxZ 且且為為整整數(shù)數(shù)0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ分別求出（分別求出（LP1）和（）和（LP2）的最優(yōu)解。）

16、的最優(yōu)解。Page 21先求先求LP1,如圖所示。此時在如圖所示。此時在B點取得最優(yōu)解。點取得最優(yōu)解。x11, x2 =3, Z(1)16找到整數(shù)解，問題已探明，找到整數(shù)解，問題已探明，此枝停止計算。此枝停止計算。x1x233(18/11,40/11)11BAC同理求同理求LP2,如圖所示。在如圖所示。在C 點點取得最優(yōu)解。即取得最優(yōu)解。即:x12, x2 =10/3, Z(2)56/318.7 Z(2) Z(1)16 原問題有比原問題有比16更小的最優(yōu)更小的最優(yōu)解，但解，但 x2 不是整數(shù)，故繼續(xù)不是整數(shù)，故繼續(xù)分支。分支。Page 22在在IP2中分別再加入條件：中分別再加入條件： x23

17、, x24 得下式兩支：得下式兩支： 且且為為整整數(shù)數(shù)0,3 2 4 30 652 )21(5min21211212121xxxxxxxxxIPxxZ 且且為為整整數(shù)數(shù)0,4 2 4 30 652 )22(5min21211212121xxxxxxxxxIPxxZ分別求出分別求出LP21和和LP22的最優(yōu)解的最優(yōu)解Page 23x1x233(18/11,40/11)11BACD先求先求LP21,如圖所示。此時如圖所示。此時D 在點取得最優(yōu)解。在點取得最優(yōu)解。即即 x112/52.4, x2 =3, Z(21)-87/5-17.4 Z(211) 如對如對LP212繼續(xù)分解，其最小繼續(xù)分解，其最小

18、值也不會低于值也不會低于15.5 ，問題探，問題探明明,剪枝。剪枝。Page 26原整數(shù)規(guī)劃問題的最原整數(shù)規(guī)劃問題的最優(yōu)解為優(yōu)解為: x1=2, x2 =3, Z* =17以上的求解過程可以以上的求解過程可以用一個樹形圖表示如用一個樹形圖表示如右：右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=12/5, x2=3Z(21) 17.4LP22無可無可行解行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23

19、x24x12x13Page 27例例5.5 用分枝定界法求解用分枝定界法求解 且且均均取取整整數(shù)數(shù),0,255.22108.02.134max21212121xxxxxxxxZ解解: 先求對應的松弛問題（記為先求對應的松弛問題（記為LP0）)(0,255 . 22108 . 02 . 134max021212121LPxxxxxxstxxZ 用圖解法得到最優(yōu)解用圖解法得到最優(yōu)解X(3.57,7.14),Z0=35.7,如下圖所示。如下圖所示。Page 281010108 . 02 . 121 xx255 . 2221 xx松弛問題松弛問題LP0的最優(yōu)解的最優(yōu)解X=(3.57,7.14),Z0=

20、35.7x1x2oABCPage 29得得到到兩兩個個線線性性規(guī)規(guī)劃劃及及增增加加約約束束4311 xx10 x2oABC 0,3255 . 22108 . 02 . 1:134max211212121xxxxxxxLPxxZLP1LP234LP1:X=(3,7.6),Z1=34.8 0,4255 . 22108 . 02 . 1:234max211212121xxxxxxxLPxxZLP2:X=(4,6.5),Z2=35.5Page 3010 x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.33 0,64255 . 22108 . 02 . 1:2134max

21、2121212121xxxxxxxxLPxxZ，不不可可行行，得得到到線線性性規(guī)規(guī)劃劃，顯顯然然及及進進行行分分枝枝，增增加加約約束束選選擇擇目目標標值值最最大大的的分分枝枝7762222 xxxLP6不可行72x 0,74255 . 22108 . 02 . 1:2234max2121212121xxxxxxxxLPxxZ，Page 3110 x1x2oACLP134可可行行域域是是一一條條線線段段即即，, 40,464255 . 22108 . 02 . 1:21134max121121212121 xxxxxxxxxxLPxxZ：及及，得得線線性性規(guī)規(guī)劃劃及及進進行行分分枝枝，增增加加約

22、約束束，選選擇擇由由于于212211542111121LPLPxxLPZZ 6 0,65255 . 22108 . 02 . 1:21234max2121212121xxxxxxxxLPxxZ，LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212Page 32LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6) Z1=34.8LP2:X=(4,6.5) Z2=35.5x13x14LP21:X=(4.33,6) Z21=35.33x26LP211:X=(4,6) Z211=34LP212:X=(5,5) Z212=35x14x1

23、5LP22無可行解無可行解x27Page 33學習要點：學習要點： 掌握一般整數(shù)規(guī)劃問題概念及模型結(jié)構(gòu)掌握一般整數(shù)規(guī)劃問題概念及模型結(jié)構(gòu) 掌握分支定界法原理掌握分支定界法原理 能夠用分支定界法求解一般整數(shù)規(guī)劃問題能夠用分支定界法求解一般整數(shù)規(guī)劃問題課后練習：課后練習：Page 34設(shè)設(shè)n 個人被分配去做個人被分配去做n 件工作，規(guī)定每個人只做一件工作，件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第每件工作只有一個人去做。已知第i個人去做第個人去做第j 件工作的效率件工作的效率（ 時間或費用）為時間或費用）為Cij(i=1.2n;j=1.2n)并假設(shè)并假設(shè)Cij 0。問應。問應如

24、何分配才能使總效率（如何分配才能使總效率（ 時間或費用）最高？時間或費用）最高？設(shè)決策變量設(shè)決策變量 ),.,2 , 1,(ji0ji1njixij 件事件事個人做第個人做第不指派第不指派第件事件事個人做第個人做第指派第指派第Page 35指派問題的數(shù)學模型為：指派問題的數(shù)學模型為： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或取取Page 36如果從分配問題效率矩陣如果從分配問題效率矩陣aij的每一行元素中分別減的每一行元素中分別減去去(或加上或加上)一個常數(shù)一個常數(shù)ui，從每一列中分別減去，從每一列中分別

25、減去(或加上或加上)一個常一個常數(shù)數(shù)vj，得到一個新的效率矩陣，得到一個新的效率矩陣bij，則以，則以bij為效率矩陣的分為效率矩陣的分配問題與以配問題與以aij為效率矩陣的分配問題具有相同的最優(yōu)解。為效率矩陣的分配問題具有相同的最優(yōu)解。Page 371) 變換指派問題的系數(shù)矩陣變換指派問題的系數(shù)矩陣(cij)為為(bij)，使在，使在(bij)的各行各列的各行各列中都出現(xiàn)中都出現(xiàn)0元素，即元素，即 從從(cij)的每行元素都減去該行的最小元素；的每行元素都減去該行的最小元素； 再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。2) 進行試指派

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

27、人了。依次進行到最后一行。任務(wù)已指派完，不必再考慮別人了。依次進行到最后一行。 從只有一個從只有一個0元素的列開始（畫元素的列開始（畫的不計在內(nèi)），給該列中的的不計在內(nèi)），給該列中的0元素加圈，記作元素加圈，記作；然后劃去；然后劃去 所在行的所在行的0元素，記作元素，記作 ，表示，表示此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進行到最后一列。此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進行到最后一列。 若仍有沒有劃圈的若仍有沒有劃圈的0元素，且同行元素，且同行(列列)的的0元素至少有兩個，比元素至少有兩個，比較這行各較這行各0元素所在列中元素所在列中0元素的數(shù)目，選擇元素的數(shù)目，選擇0元素少這個

28、元素少這個0元素加元素加圈圈(表示選擇性多的要表示選擇性多的要“禮讓禮讓”選擇性少的選擇性少的)。然后劃掉同行同列。然后劃掉同行同列的其它的其它0元素。可反復進行，直到所有元素?？煞磸瓦M行，直到所有0元素都已圈出和劃掉為止。元素都已圈出和劃掉為止。Page 39 若若 元素的數(shù)目元素的數(shù)目m 等于矩陣的階數(shù)等于矩陣的階數(shù)n（即：（即：mn），那么這指，那么這指派問題的最優(yōu)解已得到。若派問題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。則轉(zhuǎn)入下一步。3) 用最少的直線通過所有用最少的直線通過所有0元素。其方法：元素。其方法： 對沒有對沒有的行打的行打“”； 對已打?qū)σ汛颉啊?的行中所有含的行中所有含

29、元素的列打元素的列打“” ； 再對打有再對打有“”的列中含的列中含 元素的行打元素的行打“” ； 重復重復、直到得不出新的打直到得不出新的打號的行、列為止；號的行、列為止； 對沒有打?qū)]有打號的行畫橫線，有打號的行畫橫線，有打號的列畫縱線，這就得到覆蓋號的列畫縱線，這就得到覆蓋所有所有0元素的最少直線數(shù)元素的最少直線數(shù) l 。注：注：l 應等于應等于m，若不相等，說明試指派過程有誤，回到第，若不相等，說明試指派過程有誤，回到第2步，另行試步，另行試指派；若指派；若 lm n，表示還不能確定最優(yōu)指派方案，須再變換當前的系，表示還不能確定最優(yōu)指派方案，須再變換當前的系數(shù)矩陣，以找到數(shù)矩陣，以找到n

30、個獨立的個獨立的0元素，為此轉(zhuǎn)第元素，為此轉(zhuǎn)第4步。步。Page 404) 變換矩陣變換矩陣(bij)以增加以增加0元素元素在沒有被直線通過的所有元素中找出最小值，沒有被直線在沒有被直線通過的所有元素中找出最小值，沒有被直線通過的所有元素減去這個最小元素；直線交點處的元素加上這個通過的所有元素減去這個最小元素；直線交點處的元素加上這個最小值。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第最小值。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第2步。步。Page 41例例5.6 有一份中文說明書，需譯成英、日、德、俄四種文字，有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作分別記作A、B、C、D。現(xiàn)有

31、甲、乙、丙、丁四人，他們將?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？如何分派任務(wù)，可使總時間最少？ 任務(wù)任務(wù)人員人員ABCD甲甲67112乙乙4598丙丙31104丁丁5982Page 42解：解：1）變換系數(shù)矩陣，增加變換系數(shù)矩陣，增加0元素。元素。2142 289541013895421176)( ijc 06733902451009545 01733402401004542）試指派（找獨立）試指派（找獨立0元素）元素）找到找到 3 個獨立零

32、元素個獨立零元素 但但 m = 3 n = 4Page 433）作最少的直線覆蓋所有作最少的直線覆蓋所有0元素元素獨立零元素的個數(shù)獨立零元素的個數(shù)m等于最少等于最少直線數(shù)直線數(shù)l，即，即lm=3n=4；4）沒有被直線通過的元素中選擇最小值為）沒有被直線通過的元素中選擇最小值為1，變換系數(shù)矩，變換系數(shù)矩陣，將沒有被直線通過的所有元素減去這個最小元素；直陣，將沒有被直線通過的所有元素減去這個最小元素；直線交點處的元素加上這個最小值。得到新的矩陣，重復線交點處的元素加上這個最小值。得到新的矩陣，重復2）步進行試指派步進行試指派Page 44 6244251343000 0

33、00試指派試指派 6244251343 得到得到4個獨立零元素，個獨立零元素， 所以最優(yōu)解矩陣為：所以最優(yōu)解矩陣為： 0100001000011000即完成即完成4個任務(wù)的總時間最少個任務(wù)的總時間最少為：為：241+8=15Page 45例例5.7 已知四人分別完成四項工作所需時間如下表，求最優(yōu)已知四人分別完成四項工作所需時間如下表，求最優(yōu)分配方案。分配方案。 任務(wù)任務(wù)人員人員ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119Page 46解：解：1）變換系數(shù)矩陣，增加變換系數(shù)矩陣，增加0元素。元素。79429118713161491514410413152 24241

34、04750111006211130 00102350960607130 00102350960607130 2）試指派（找獨立）試指派（找獨立0元素）元素） 獨立獨立0元素的個數(shù)為元素的個數(shù)為4 , 指派問題的最優(yōu)指指派問題的最優(yōu)指派方案即為甲負責派方案即為甲負責D工作，乙負責工作，乙負責B工作，工作，丙負責丙負責A工作，丁負責工作，丁負責C工作。這樣安排工作。這樣安排能使總的工作時間最少，為能使總的工作時間最少，為4491128。Page 47例例5.8 已知五人分別完成五項工作耗費如下表，求最優(yōu)分配已知五人分別完成五項工作耗費如下表，求最優(yōu)分配方案。方案。 任務(wù)任務(wù)人員人員ABCDE甲甲7

35、59811乙乙9127119丙丙85468丁丁73696戊戊467511Page 484347511576469637964589117129118957 7132036304520142405263402-1 -2解：解：1）變換系數(shù)矩陣，增加）變換系數(shù)矩陣，增加0元素。元素。Page 49 5032015304310140305242402 5032015304310140305242402 2）試指派（找獨立）試指派（找獨立0元素）元素） 獨立獨立0元素的個數(shù)元素的個數(shù)l45，故畫直線調(diào)整矩陣。，故畫直線調(diào)整矩陣。Page 50 5032015304310140305242402 選擇直

36、線外的最小元素選擇直線外的最小元素為為1；直線外元素減；直線外元素減1，直線交點元素加直線交點元素加1，其，其他保持不變。他保持不變。Page 51 5033004203310240306231301 l =m=4 n=5選擇直線外最小元素為選擇直線外最小元素為1，直線外元素減直線外元素減1，直線交，直線交點元素加點元素加1，其他保持不，其他保持不變，得到新的系數(shù)矩陣。變，得到新的系數(shù)矩陣。Page 52 6044003202300230206130300 總費用為總費用為=5+7+6+6+4=28=5+7+6+6+4=28注：此問題有多個最優(yōu)解注：此問題有多個最優(yōu)解Page 53 60440

37、03202300230206130300 總費用為總費用為=7+9+4+3+5=28=7+9+4+3+5=28Page 54 6044003202300230206130300 總費用為總費用為=8+9+4+3+4=28=8+9+4+3+4=28Page 55課堂練習：用匈牙利法求解下列指派問題。課堂練習：用匈牙利法求解下列指派問題。79 10 1213 12 16 1715 16 14 1511 12 15 163821038729764275842359106910練習練習1：練習練習2：Page 5679 10 1213 12 16 1715 16 14 1511 12 15 16382

38、10387297642758423591069104848 21 21答案：答案：Page 57匈牙利法的條件是：模型求最小值、效率匈牙利法的條件是：模型求最小值、效率cij0。當遇到各種非標準形式的指派問題時，處理方法是先將當遇到各種非標準形式的指派問題時，處理方法是先將其轉(zhuǎn)化為標準形式，然后用匈牙利法來求解。其轉(zhuǎn)化為標準形式，然后用匈牙利法來求解。Page 58處理方法：設(shè)處理方法：設(shè)m為最大化指派問題系數(shù)矩陣為最大化指派問題系數(shù)矩陣C中最大元素。中最大元素。令矩陣令矩陣B（m-cij）nn則以則以B為系數(shù)矩陣的最小化指派問題和為系數(shù)矩陣的最小化指派問題和原問題有相同的最優(yōu)解。原問題有相同的最優(yōu)解。例例4.9 某人事部門擬招聘某人事部門擬招聘4人任職人任職4項工作，對他們綜合考評的項工作，對他們綜合考評的 得分如下表（滿分得分如下表（滿分100分），如何安排工作使總分最多。分），如何安排工作使總分最多。 888090869079838295788