整數(shù)規(guī)劃解法匈牙利算法部分業(yè)界薈萃

1、4.5 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法分支定界法割平面法匈牙利法1行業(yè)知識(shí)4.5.1 整數(shù)規(guī)劃解法 分枝定界法n步驟：步驟：1、尋找替代問(wèn)題并求解、尋找替代問(wèn)題并求解2、分枝與定界、分枝與定界3、剪枝、剪枝2行業(yè)知識(shí)1、基本思路：、基本思路：整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于相應(yīng)整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于相應(yīng)的線(xiàn)性規(guī)劃的最優(yōu)解的線(xiàn)性規(guī)劃的最優(yōu)解。對(duì)于。對(duì)于極大值極大值問(wèn)題，問(wèn)題，相應(yīng)線(xiàn)性相應(yīng)線(xiàn)性規(guī)劃規(guī)劃的最大值成為整數(shù)規(guī)劃目標(biāo)函數(shù)的的最大值成為整數(shù)規(guī)劃目標(biāo)函數(shù)的上界上界。maxz=cxax=bx 0(a)max z=cxax=bx 0x為整數(shù)為整數(shù) (b)(b)為為(a)的松弛問(wèn)題。的松弛問(wèn)題。（1）替代問(wèn)

2、題的確定）替代問(wèn)題的確定3行業(yè)知識(shí)（2）替代問(wèn)題的求解）替代問(wèn)題的求解max z=cxax=bx 0(b)采用相應(yīng)的方法（如圖解法）求解出替代問(wèn)題的采用相應(yīng)的方法（如圖解法）求解出替代問(wèn)題的最優(yōu)解最優(yōu)解，觀察其是否滿(mǎn)足整數(shù)解的要求。如其，觀察其是否滿(mǎn)足整數(shù)解的要求。如其最最優(yōu)解就為整數(shù)優(yōu)解就為整數(shù)，則，則結(jié)束結(jié)束；如含有；如含有分?jǐn)?shù)分?jǐn)?shù)，則需要進(jìn)，則需要進(jìn)行行分支定界分支定界操作。操作。4行業(yè)知識(shí)（3）分支與定界）分支與定界增加約束增加約束如替代問(wèn)題的解如替代問(wèn)題的解不符合整數(shù)條件不符合整數(shù)條件，則需要對(duì)原問(wèn)題進(jìn)行，則需要對(duì)原問(wèn)題進(jìn)行分支分支。分支方法分支方法：假設(shè)替代問(wèn)題的解為：假設(shè)替代問(wèn)題

3、的解為i，i+1之間的一個(gè)數(shù)，則分成兩支：之間的一個(gè)數(shù)，則分成兩支：一支一支增加約束增加約束xji，另一支另一支增加約束增加約束xj i+1；對(duì)上述兩個(gè)問(wèn)題進(jìn)行求解：對(duì)上述兩個(gè)問(wèn)題進(jìn)行求解：不考慮整數(shù)問(wèn)題時(shí)不考慮整數(shù)問(wèn)題時(shí)，求解對(duì)應(yīng)的線(xiàn)性規(guī)劃，求解對(duì)應(yīng)的線(xiàn)性規(guī)劃問(wèn)題，觀察其最優(yōu)解是否是整數(shù)，如不是，則繼續(xù)分支定界，直到得到問(wèn)題，觀察其最優(yōu)解是否是整數(shù)，如不是，則繼續(xù)分支定界，直到得到全部整數(shù)解為止。全部整數(shù)解為止。x*xj*i+1i(c)(d)(b)xj i+1(b)xj i5行業(yè)知識(shí) max z=40x1 + 90x2 9x1+7x2 567x1+20x2 70x1 , x2 0 x1 ,

4、x2為為整數(shù)整數(shù)例：例：6行業(yè)知識(shí)解：先解該整數(shù)規(guī)劃對(duì)應(yīng)的松弛問(wèn)題解：先解該整數(shù)規(guī)劃對(duì)應(yīng)的松弛問(wèn)題x* =4.8091.817z* =355.890， 上界上界z* 選選x1分枝分枝問(wèn)題問(wèn)題(2)(1)x1 4問(wèn)題問(wèn)題(3)(1)x1 5將將4,5之間的非整數(shù)部分舍去之間的非整數(shù)部分舍去7行業(yè)知識(shí)選選(2)繼續(xù)分枝繼續(xù)分枝問(wèn)題問(wèn)題(4)(2)x2 2問(wèn)題問(wèn)題(5)(2)x2 3解為解為x1 =4x2 =2.1z=349.0解為解為x1 =5x2 =1.571z=341.39問(wèn)題問(wèn)題2問(wèn)題問(wèn)題38行業(yè)知識(shí)(1)4.8091.817355.890(2)42.1349.0(3)51.571341.3

5、9(4)42340(5)1.4283340327.12(6)5.4441340307.76(7)無(wú)解無(wú)解x1 4x1 5x2 2x2 1x2 2x2 3分支定界過(guò)程分支定界過(guò)程9行業(yè)知識(shí)4.5.2 整數(shù)規(guī)劃解法2割平面法n割平面法的基本思想基本思想：n在整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題中依次引進(jìn)線(xiàn)性約束條件(稱(chēng)gomory約束，高莫雷約束或割平面)，使問(wèn)題的可行域逐步縮小可行域逐步縮小。但每次切割時(shí)，只割去問(wèn)題的部分非整數(shù)解只割去問(wèn)題的部分非整數(shù)解，而不切割任何整數(shù)的可行解不切割任何整數(shù)的可行解，直到使問(wèn)題的目標(biāo)函數(shù)值達(dá)到最優(yōu)的整數(shù)點(diǎn)整數(shù)點(diǎn)成為縮小后可行域的一個(gè)頂點(diǎn)一個(gè)頂點(diǎn)，這樣就可以用求解線(xiàn)性規(guī)劃問(wèn)題

6、的方法找出這個(gè)最優(yōu)解。10行業(yè)知識(shí)4.5.3 整數(shù)規(guī)劃的解法匈牙利法應(yīng)用于分配問(wèn)題或指派問(wèn)題分配問(wèn)題或指派問(wèn)題n分配問(wèn)題也稱(chēng)分配問(wèn)題也稱(chēng)指派問(wèn)題指派問(wèn)題，是一種，是一種特殊的特殊的整數(shù)規(guī)劃問(wèn)題整數(shù)規(guī)劃問(wèn)題。n假定有假定有m項(xiàng)任務(wù)分配給項(xiàng)任務(wù)分配給m個(gè)人去完成個(gè)人去完成，并，并指定每人完成其中一項(xiàng)指定每人完成其中一項(xiàng)，每項(xiàng)只交給其每項(xiàng)只交給其中一個(gè)人去完成中一個(gè)人去完成，應(yīng)如何分配使，應(yīng)如何分配使總的效總的效率為最高率為最高。11行業(yè)知識(shí)1、指派問(wèn)題一般模型的引出、指派問(wèn)題一般模型的引出n例：有一份說(shuō)明書(shū)，要分別譯成英、日、德、俄四種文字，例：有一份說(shuō)明書(shū)，要分別譯成英、日、德、俄四種文字，交甲

7、、乙、丙、丁四個(gè)人去完成。因各人專(zhuān)長(zhǎng)不同，他們交甲、乙、丙、丁四個(gè)人去完成。因各人專(zhuān)長(zhǎng)不同，他們完成翻譯不同文字所需的時(shí)間完成翻譯不同文字所需的時(shí)間(h)如表所示。問(wèn)：如何分如表所示。問(wèn)：如何分配任務(wù)使效率最高（配任務(wù)使效率最高（所需總時(shí)間最短所需總時(shí)間最短）？）？ 人人工作工作 甲甲乙乙丙丙丁丁譯成英文譯成英文21097譯成日文譯成日文154148譯成德文譯成德文13141611譯成俄文譯成俄文415139從人的從人的角度看角度看從任務(wù)從任務(wù)角度看角度看12行業(yè)知識(shí)指派問(wèn)題的一般模型指派問(wèn)題的一般模型n假設(shè)：假設(shè)：naij表示指派問(wèn)題的效率矩陣表示指派問(wèn)題的效率矩陣nxij表示決策變量，決策

8、變量的取值：表示決策變量，決策變量的取值： 1,0,(1,.,m; 1,.,m)ijijxijij分配第 個(gè)人去完成第 項(xiàng)任務(wù)不分配第 個(gè)人去完成第 項(xiàng)任務(wù)13行業(yè)知識(shí)n指派問(wèn)題的一般數(shù)學(xué)模型 mimjijijxaz11min111 (1,.,m)1 (1,.,m)0 1mijjmijiijxixjx或指派問(wèn)題的一般模型指派問(wèn)題的一般模型14行業(yè)知識(shí)2、指派問(wèn)題的求解方法、指派問(wèn)題的求解方法n 單純形法單純形法n 表上作業(yè)法表上作業(yè)法n 匈牙利法匈牙利法15行業(yè)知識(shí)（1）指派問(wèn)題的求解）指派問(wèn)題的求解匈牙利法匈牙利法n核心思路核心思路：基于這樣一個(gè)事實(shí)：如果效率矩陣的所有元素aij0，而其中存

9、在一組位于一組位于不同行、不同列不同行、不同列的零的零元素元素，則只要令對(duì)應(yīng)對(duì)應(yīng)于這些零元素的于這些零元素的xij=1（分配任務(wù)）（分配任務(wù)），其余其余的的xij =0，則目標(biāo)函數(shù)z必然會(huì)取得最?。?）。0149392002320038512140只需令：只需令：x11=1，x23=1，x32=1，x44=1，即第一項(xiàng)各種分配給甲，即第一項(xiàng)各種分配給甲，二工作二工作丙，三丙，三乙，四乙，四丁。丁?？偣ぷ鲿r(shí)間最少?？偣ぷ鲿r(shí)間最少。效率矩陣效率矩陣16行業(yè)知識(shí)問(wèn)問(wèn) 題題n要求：效率矩陣中存在零元素，同時(shí)存在不在同要求：效率矩陣中存在零元素，同時(shí)存在不在同一行、同一列的零元素。一行、同一列的零元素。

10、n實(shí)際的效率矩陣中，是不可能存在實(shí)際的效率矩陣中，是不可能存在0元素的，那元素的，那么么如何獲得這種特殊的效率矩陣？如何獲得這種特殊的效率矩陣？n如何讓效率矩陣中產(chǎn)生零元素；如何讓效率矩陣中產(chǎn)生零元素；n如何讓產(chǎn)生的零元素位于不同行和不同列如何讓產(chǎn)生的零元素位于不同行和不同列。17行業(yè)知識(shí)（2）零元素的產(chǎn)生方法）零元素的產(chǎn)生方法：匈牙利法的基本定理匈牙利法的基本定理1n如果從分配問(wèn)題效率矩陣如果從分配問(wèn)題效率矩陣aij的每的每一行元一行元素中素中分別分別減去減去( (或加上或加上) )一個(gè)一個(gè)常數(shù)常數(shù)ui ( (被稱(chēng)被稱(chēng)為該行的位勢(shì)為該行的位勢(shì)) )，從，從每一列每一列分別分別減去減去( (或

11、或加上加上) )一個(gè)一個(gè)常數(shù)常數(shù)vj ( (稱(chēng)為該列的位勢(shì)稱(chēng)為該列的位勢(shì)) )，得，得到一個(gè)到一個(gè)新的效率矩陣新的效率矩陣bij，若其中，若其中n則則bij的最優(yōu)解等價(jià)于的最優(yōu)解等價(jià)于aij的最優(yōu)解的最優(yōu)解（說(shuō)明，（說(shuō)明，經(jīng)過(guò)變換后，有零的新效率矩陣取得最優(yōu)解時(shí)，原效經(jīng)過(guò)變換后，有零的新效率矩陣取得最優(yōu)解時(shí)，原效率矩陣也同時(shí)取得最優(yōu)解）率矩陣也同時(shí)取得最優(yōu)解） jiijijvuab18行業(yè)知識(shí)（3）獨(dú)立零元素獨(dú)立零元素的判斷方法的判斷方法：匈牙利法的基本定理匈牙利法的基本定理2n若矩陣若矩陣a的元素可分成的元素可分成“0”與非與非“0”兩部?jī)刹糠?，則分，則覆蓋覆蓋“0”元素元素的的最少直線(xiàn)最少

12、直線(xiàn)數(shù)等于數(shù)等于位位于不同行、不同列的于不同行、不同列的“0”元素的最大個(gè)數(shù)元素的最大個(gè)數(shù)。1200020312402030120002030240223119行業(yè)知識(shí)n若矩陣若矩陣a的元素可分成的元素可分成“0”與非與非“0”兩兩部分，則覆蓋部分，則覆蓋“0”元素的最少直線(xiàn)數(shù)等元素的最少直線(xiàn)數(shù)等于位于不同行、不同列的于位于不同行、不同列的“0”元素的最元素的最大個(gè)數(shù)。大個(gè)數(shù)。n將確定一個(gè)效率矩陣中最大獨(dú)立零元素的將確定一個(gè)效率矩陣中最大獨(dú)立零元素的個(gè)數(shù)，轉(zhuǎn)化為尋找覆蓋所有零元素所需的個(gè)數(shù)，轉(zhuǎn)化為尋找覆蓋所有零元素所需的最少直線(xiàn)數(shù)。最少直線(xiàn)數(shù)。 20行業(yè)知識(shí)匈牙利法的計(jì)算步驟 n 基本步驟：在

13、效率矩陣中產(chǎn)生零元素基本步驟：在效率矩陣中產(chǎn)生零元素判斷獨(dú)立的零元素個(gè)數(shù)是否等于任務(wù)數(shù)判斷獨(dú)立的零元素個(gè)數(shù)是否等于任務(wù)數(shù)或人數(shù)？或人數(shù)？如是，則對(duì)效率矩陣中獨(dú)立如是，則對(duì)效率矩陣中獨(dú)立零元素所處的位置進(jìn)行指派（對(duì)應(yīng)的決零元素所處的位置進(jìn)行指派（對(duì)應(yīng)的決策變量為策變量為1），完成），完成如否，則要繼續(xù)產(chǎn)如否，則要繼續(xù)產(chǎn)生足夠的獨(dú)立零元素。生足夠的獨(dú)立零元素。n通過(guò)實(shí)例來(lái)說(shuō)明匈牙利法求解指派問(wèn)題通過(guò)實(shí)例來(lái)說(shuō)明匈牙利法求解指派問(wèn)題的過(guò)程。的過(guò)程。21行業(yè)知識(shí)例：例：n有一份說(shuō)明書(shū)，要分別譯成英、日、德、俄四種文有一份說(shuō)明書(shū)，要分別譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個(gè)人去完成。因各人專(zhuān)長(zhǎng)字

14、，交甲、乙、丙、丁四個(gè)人去完成。因各人專(zhuān)長(zhǎng)不同，他們完成翻譯不同文字所需的時(shí)間不同，他們完成翻譯不同文字所需的時(shí)間(h)如表所如表所示。問(wèn)：如何分配任務(wù)使效率最高？示。問(wèn)：如何分配任務(wù)使效率最高？ 人工作 甲乙丙丁譯成英文21097譯成日文154148譯成德文13141611譯成俄文41513922行業(yè)知識(shí)效率矩陣 9 13 15 4 11 16 14 138 14 4 157 9 10 2 a23行業(yè)知識(shí)步驟一：零元素的產(chǎn)生。步驟一：零元素的產(chǎn)生。方法：方法：找出效率矩陣找出效率矩陣每行每行的的最小元素最小元素，并，并分別從每行中減去它。分別從每行中減去它。min實(shí)際含義：從事情的角度來(lái)考慮

15、，表示此事分配給此人效率最高。實(shí)際含義：從事情的角度來(lái)考慮，表示此事分配給此人效率最高。591100532410011578041142913154111614138144157910224行業(yè)知識(shí)步驟二：繼續(xù)產(chǎn)生零元素步驟二：繼續(xù)產(chǎn)生零元素方法：方法：再找出矩陣再找出矩陣每列每列的的最小元素最小元素，再分，再分別從各列中減去它。別從各列中減去它。min 0 0 5 0實(shí)際含義：從人的角度來(lái)考慮，表示某人做此事效率最高。實(shí)際含義：從人的角度來(lái)考慮，表示某人做此事效率最高。5411000324501152802 259110053410011578025行業(yè)知識(shí)步驟三：判斷零元素是否位于不同行、

16、不步驟三：判斷零元素是否位于不同行、不同列？同列？n經(jīng)過(guò)上述兩步變換后，矩陣的每行每列至經(jīng)過(guò)上述兩步變換后，矩陣的每行每列至少都有了一個(gè)零元素。少都有了一個(gè)零元素。n確定能否找出確定能否找出m個(gè)位于不同行不同列的零個(gè)位于不同行不同列的零元素的集合元素的集合(本例中本例中m=4)，直觀法：直觀法：m很小時(shí)，直接判斷得到；很小時(shí)，直接判斷得到；非直觀法：非直觀法：m很大時(shí)，根據(jù)一定規(guī)則尋找。很大時(shí)，根據(jù)一定規(guī)則尋找。26行業(yè)知識(shí)直觀法直觀法541100032450115280只有只有3個(gè)個(gè)0元素元素位于不同行、位于不同行、不同列不同列27行業(yè)知識(shí)非直觀法非直觀法-步驟步驟1（試指派過(guò)程）（試指派過(guò)

17、程）n(1) 從從第一行第一行開(kāi)始，若開(kāi)始，若該行該行只有一個(gè)零元素只有一個(gè)零元素，就對(duì)這個(gè)，就對(duì)這個(gè)零元素打上零元素打上( )號(hào)號(hào)。n同時(shí)，對(duì)打同時(shí)，對(duì)打( )號(hào)零元素號(hào)零元素所在所在列列畫(huà)一條直線(xiàn)，畫(huà)一條直線(xiàn)，表示表示此列已經(jīng)確定（人員確定），不能再?gòu)氖缕渌写肆幸呀?jīng)確定（人員確定），不能再?gòu)氖缕渌械墓ぷ鳎ㄈ蝿?wù)）的工作（任務(wù)） 。n若該行若該行沒(méi)有零元素沒(méi)有零元素或有或有兩個(gè)以上零元素兩個(gè)以上零元素(已劃去的已劃去的零元素不計(jì)在內(nèi)零元素不計(jì)在內(nèi))，則，則轉(zhuǎn)下一行轉(zhuǎn)下一行，按照上述方法依，按照上述方法依次進(jìn)行到最后一行；次進(jìn)行到最后一行；28行業(yè)知識(shí)082511054230001145例：

18、從行開(kāi)始的獨(dú)立零元素的尋找與判斷例：從行開(kāi)始的獨(dú)立零元素的尋找與判斷（ ）（ ）(0)82511(0)54230001145從行開(kāi)始標(biāo)定獨(dú)立零元從行開(kāi)始標(biāo)定獨(dú)立零元素時(shí)，只能找到兩個(gè)獨(dú)素時(shí)，只能找到兩個(gè)獨(dú)立的零元素。立的零元素。29行業(yè)知識(shí)非直觀法非直觀法-步驟步驟2n(2) 在行尋找的基礎(chǔ)上，從在行尋找的基礎(chǔ)上，從第一第一列列開(kāi)始，若開(kāi)始，若該列該列只有只有一個(gè)零元素一個(gè)零元素就對(duì)就對(duì)這個(gè)這個(gè)零元素打上零元素打上( )號(hào)號(hào)(同樣不考慮已劃去的零元同樣不考慮已劃去的零元素素)，n對(duì)打?qū)Υ? )號(hào)零元素號(hào)零元素所在行所在行畫(huà)一條直線(xiàn)畫(huà)一條直線(xiàn)（任務(wù)分（任務(wù)分配完畢，不能再分配給其他人）。配完畢，

19、不能再分配給其他人）。n若該列沒(méi)有零元素或有兩個(gè)以上零元素，若該列沒(méi)有零元素或有兩個(gè)以上零元素，則轉(zhuǎn)下一列，依次進(jìn)行到最后一列；則轉(zhuǎn)下一列，依次進(jìn)行到最后一列；30行業(yè)知識(shí)(0)82511(0)54230001145例：從列開(kāi)始的獨(dú)立零元素的尋找與判斷例：從列開(kāi)始的獨(dú)立零元素的尋找與判斷（ ）在行標(biāo)定后的基礎(chǔ)上，在行標(biāo)定后的基礎(chǔ)上，從第一列開(kāi)始標(biāo)定獨(dú)立從第一列開(kāi)始標(biāo)定獨(dú)立零元素時(shí)，只能找到一零元素時(shí)，只能找到一獨(dú)立的零元素。獨(dú)立的零元素。(0)82511(0)5423(0)00114531行業(yè)知識(shí)(0)82511(0)5423(0)001145問(wèn)問(wèn) 題題只能對(duì)三個(gè)零元素進(jìn)行標(biāo)定（代表獨(dú)立的零只

20、能對(duì)三個(gè)零元素進(jìn)行標(biāo)定（代表獨(dú)立的零元素只有三個(gè)），后續(xù)如何操作？元素只有三個(gè)），后續(xù)如何操作？32行業(yè)知識(shí)非直觀法-步驟3（第一種情形）n(3) 重復(fù)重復(fù)(1)、(2)兩個(gè)步驟兩個(gè)步驟，可能出現(xiàn)三種，可能出現(xiàn)三種情況：情況：n 效率矩陣效率矩陣每行都有一個(gè)打每行都有一個(gè)打( )號(hào)的零元號(hào)的零元素素，很顯然，按上述步驟得到的打，很顯然，按上述步驟得到的打( )號(hào)號(hào)的零元素都位于不同行不同列，只要的零元素都位于不同行不同列，只要令令對(duì)應(yīng)打?qū)?yīng)打( )號(hào)零元素對(duì)應(yīng)的決策變量號(hào)零元素對(duì)應(yīng)的決策變量xij=1就找到了問(wèn)題的就找到了問(wèn)題的最優(yōu)解最優(yōu)解； 33行業(yè)知識(shí)(0)1231(0)3412(0)53

21、82(0)第一種情形第一種情形x11=1，x22=1，x33=1，x44=1。任務(wù)一任務(wù)一甲；二甲；二乙；三乙；三丙；丙；四四丁丁任務(wù)一任務(wù)一任務(wù)二任務(wù)二任務(wù)三任務(wù)三任務(wù)四任務(wù)四甲甲 乙乙 丙丙 丁丁34行業(yè)知識(shí)非直觀法-4（第二種情形）n 打打( )號(hào)的號(hào)的零元素個(gè)數(shù)小于零元素個(gè)數(shù)小于m，但，但未被劃去未被劃去的的零元素之間存在零元素之間存在閉回路（全以閉回路（全以0為拐點(diǎn)）為拐點(diǎn)），這，這時(shí)時(shí)可順著閉回路可順著閉回路的走向，對(duì)的走向，對(duì)每個(gè)間隔每個(gè)間隔的的零元素打零元素打一一( )號(hào)號(hào)，然后對(duì)所有打，然后對(duì)所有打( )號(hào)的零元素，或所在號(hào)的零元素，或所在行，或所在列畫(huà)一條直線(xiàn)（行，或所在列

22、畫(huà)一條直線(xiàn)（一般會(huì)出現(xiàn)多種方一般會(huì)出現(xiàn)多種方案案）。如：）。如：或或0 (0) (0) 0 0 (0) 35行業(yè)知識(shí)1500400005003300第二種情形第二種情形（ ）（ ）15004(0)00(0)5003300只能給兩個(gè)零元素打括號(hào)，只能給兩個(gè)零元素打括號(hào)，還有四個(gè)零元素不能打上括還有四個(gè)零元素不能打上括號(hào)。剩下的未被劃去和未打號(hào)。剩下的未被劃去和未打括號(hào)的零元素存在閉回路。括號(hào)的零元素存在閉回路。（ ）（ ）36行業(yè)知識(shí)15(0)04(0)00(0)500330(0)x13=1，x22=1，x31=1，x44=1結(jié)論結(jié)論137行業(yè)知識(shí)結(jié)論結(jié)論2150(0)4(0)00(0)5003

23、3(0)015004(0)00(0)5003300（ ）（ ）x14=1，x22=1，x31=1，x43=138行業(yè)知識(shí)非直觀法-5（第三種情形）n 矩陣中矩陣中所有零元素或被劃去所有零元素或被劃去，或，或打上打上( )號(hào)號(hào)，但但打打( )號(hào)的零元素個(gè)數(shù)小于號(hào)的零元素個(gè)數(shù)小于m，如：，如：打括號(hào)的零元素打括號(hào)的零元素3m=4。證明。證明0元素產(chǎn)生的元素產(chǎn)生的還不夠，還應(yīng)繼續(xù)產(chǎn)生。還不夠，還應(yīng)繼續(xù)產(chǎn)生。39行業(yè)知識(shí)步驟四：繼續(xù)創(chuàng)造零元素。步驟四：繼續(xù)創(chuàng)造零元素。方法方法：為設(shè)法使每一行都有一個(gè)打?yàn)樵O(shè)法使每一行都有一個(gè)打( )號(hào)的零元素，號(hào)的零元素，需要繼續(xù)按定理需要繼續(xù)按定理1對(duì)矩陣進(jìn)行變換。對(duì)

24、矩陣進(jìn)行變換。n(1) 從矩陣從矩陣未被直線(xiàn)覆蓋未被直線(xiàn)覆蓋的數(shù)字中找出一的數(shù)字中找出一個(gè)個(gè)最小最小的數(shù)的數(shù)k；n(2) 對(duì)對(duì)矩陣的每行矩陣的每行，當(dāng)該行，當(dāng)該行有直線(xiàn)覆蓋有直線(xiàn)覆蓋時(shí)，時(shí)，令令ui= 0，無(wú)直線(xiàn)覆蓋無(wú)直線(xiàn)覆蓋的，令的，令ui=k；n(3) 對(duì)矩陣每列，對(duì)矩陣每列，有直線(xiàn)覆蓋的列有直線(xiàn)覆蓋的列，令，令vj= -k，對(duì)，對(duì)無(wú)直線(xiàn)覆蓋的列無(wú)直線(xiàn)覆蓋的列，令，令vj=0；n(4) 從原矩陣的每個(gè)元素從原矩陣的每個(gè)元素aij中分別減去中分別減去ui和和vj，得到一個(gè)新的矩陣，得到一個(gè)新的矩陣（ aij - ui - vj ），保），保證新矩陣中，原打括號(hào)的證新矩陣中，原打括號(hào)的0元素不

25、變，同元素不變，同時(shí)產(chǎn)生新的零元素。時(shí)產(chǎn)生新的零元素。40行業(yè)知識(shí)步驟五：回到第三步，反復(fù)進(jìn)行，一直到矩陣的每一步驟五：回到第三步，反復(fù)進(jìn)行，一直到矩陣的每一行都有一個(gè)打行都有一個(gè)打( )( )號(hào)的零元素為止，即找到了最優(yōu)分配號(hào)的零元素為止，即找到了最優(yōu)分配方案。方案。uivj41行業(yè)知識(shí) 人工作 甲乙丙丁譯成英文21097譯成日文154148譯成德文13141611譯成俄文415139n最優(yōu)分配方案為：n甲將說(shuō)明書(shū)譯成俄文，乙譯成日文，丙譯成英文，丁譯成德文，n全部所需時(shí)間為4+4+9+11=28小時(shí)。 42行業(yè)知識(shí)回顧：指派問(wèn)題的計(jì)算過(guò)程回顧：指派問(wèn)題的計(jì)算過(guò)程 2 10 9 715 4

26、14 8a13 14 16 11 4 15 13 9 效率效率矩陣矩陣43行業(yè)知識(shí)5911005324100115780411429131541116141381441579102步驟一：產(chǎn)生每行的零元素。步驟一：產(chǎn)生每行的零元素。方法：從每行中找出最小的元素，與對(duì)應(yīng)方法：從每行中找出最小的元素，與對(duì)應(yīng)的每行元素相減的每行元素相減min每行減去每行減去對(duì)應(yīng)的最對(duì)應(yīng)的最小元素小元素44行業(yè)知識(shí)步驟二：產(chǎn)生位于每列的零元素步驟二：產(chǎn)生位于每列的零元素方法：方法：再找出矩陣再找出矩陣每列每列的的最小元素最小元素，再分，再分別從各列中減去。別從各列中減去。min 0 0 5 0541100032450

27、1152805911005324100115780每列減去每列減去對(duì)應(yīng)的最對(duì)應(yīng)的最小元素小元素保證每行、每列都至少有一個(gè)保證每行、每列都至少有一個(gè)0元素。元素。45行業(yè)知識(shí)步驟三：判斷零元素是否位于不同行、不同列。步驟三：判斷零元素是否位于不同行、不同列。方法：首先從行開(kāi)始試指派，只有一個(gè)零元素時(shí)，對(duì)零元方法：首先從行開(kāi)始試指派，只有一個(gè)零元素時(shí)，對(duì)零元素打括號(hào)，并對(duì)所在列畫(huà)直線(xiàn)。而有多個(gè)零元素，或零元素打括號(hào)，并對(duì)所在列畫(huà)直線(xiàn)。而有多個(gè)零元素，或零元素已被畫(huà)去，則轉(zhuǎn)下一行；行分析完畢后，然后從列開(kāi)始素已被畫(huà)去，則轉(zhuǎn)下一行；行分析完畢后，然后從列開(kāi)始試指派，對(duì)每列只有一個(gè)零元素時(shí)，打括號(hào)，并畫(huà)

28、去其所試指派，對(duì)每列只有一個(gè)零元素時(shí)，打括號(hào)，并畫(huà)去其所在的行。在的行。541100032450115280（ ）（ ）行試指派過(guò)程行試指派過(guò)程541100032450115280（ ）（ ）列試指派過(guò)程列試指派過(guò)程（ ）46行業(yè)知識(shí)步驟四：繼續(xù)創(chuàng)造零元素。步驟四：繼續(xù)創(chuàng)造零元素。方法：從未被畫(huà)去的元素中，找到一個(gè)最小的元素方法：從未被畫(huà)去的元素中，找到一個(gè)最小的元素k。（1）對(duì)行的操作：選擇行位勢(shì)）對(duì)行的操作：選擇行位勢(shì)ui，如果行被直線(xiàn)覆蓋，則，如果行被直線(xiàn)覆蓋，則ui=0；如果；如果未被覆蓋，未被覆蓋，ui=k；（2）列的操作：列位勢(shì)）列的操作：列位勢(shì)vj，如果列被直線(xiàn)覆蓋，如果列被直線(xiàn)

29、覆蓋，vj=-k；如果未被覆；如果未被覆蓋，蓋，vj=0。（3）產(chǎn)生新的效率矩陣：）產(chǎn)生新的效率矩陣：bij= aij -ui-vj541100032450115280（ ）（ ）（ ）1、最小元素、最小元素k=2；2、ui依次為依次為2、2、0和和2；3、vj依次取為依次取為-2、-2、0和和0.。ui2202vj-2-200bij= aij -ui-vj32110005423011308047行業(yè)知識(shí)步驟五：繼續(xù)判斷零元素是否位于不同行、不同列。步驟五：繼續(xù)判斷零元素是否位于不同行、不同列。方法：方法：首先從行開(kāi)始試指派，只有一個(gè)零元素時(shí)，對(duì)零元素打首先從行開(kāi)始試指派，只有一個(gè)零元素時(shí)，對(duì)

30、零元素打括號(hào)，并對(duì)所在列畫(huà)直線(xiàn)。而有多個(gè)零元素，或零元素已被畫(huà)括號(hào)，并對(duì)所在列畫(huà)直線(xiàn)。而有多個(gè)零元素，或零元素已被畫(huà)去，則轉(zhuǎn)下一行；行分析完畢后，然后從列開(kāi)始試指派，對(duì)每去，則轉(zhuǎn)下一行；行分析完畢后，然后從列開(kāi)始試指派，對(duì)每列只有一個(gè)零元素時(shí)，打括號(hào)，并畫(huà)去其所在的行。列只有一個(gè)零元素時(shí)，打括號(hào)，并畫(huà)去其所在的行。321100054230113080（ ）（ ）（ ）（ ）最終結(jié)果最終結(jié)果321100054230113080（ ）（ ）（ ）（ ）48行業(yè)知識(shí)步驟六：獲得最后結(jié)果。步驟六：獲得最后結(jié)果。方法：對(duì)于打括號(hào)的零元素處進(jìn)行指派，即可獲得最短時(shí)間。方法：對(duì)于打括號(hào)的零元素處進(jìn)行指派，即

31、可獲得最短時(shí)間。321100054230113080（ ）（ ）（ ）（ ）p x13=1（工作一（工作一丙）丙）p x22=1 （工作二（工作二乙）乙）p x34=1 （工作三（工作三?。┒。﹑ x41=1（工作四（工作四甲）甲）最短時(shí)間為：最短時(shí)間為：9+4+11+4=28 h。指派結(jié)果指派結(jié)果49行業(yè)知識(shí)4.5.4 極大化的指派問(wèn)題極大化的指派問(wèn)題對(duì)于目標(biāo)為求極大的指派問(wèn)題，先要對(duì)對(duì)于目標(biāo)為求極大的指派問(wèn)題，先要對(duì)效率矩陣進(jìn)行處理：效率矩陣進(jìn)行處理：（1）找出效率矩陣中的最大值，分別用）找出效率矩陣中的最大值，分別用它去減陣中每一元素，得到新矩陣；它去減陣中每一元素，得到新矩陣；（2）對(duì)

32、新得到的矩陣用原匈牙利法求解。）對(duì)新得到的矩陣用原匈牙利法求解。50行業(yè)知識(shí)11maxmmijijijza x11min()mmijijijwaxmax()()ijijijbaa 51行業(yè)知識(shí)例、有例、有 4 種機(jī)械要分別安裝在種機(jī)械要分別安裝在4個(gè)工地，它們個(gè)工地，它們 在在4個(gè)工地的工作效率不同，問(wèn)應(yīng)如何指?jìng)€(gè)工地的工作效率不同，問(wèn)應(yīng)如何指 派，可使派，可使4臺(tái)機(jī)械發(fā)揮的總效益最大？臺(tái)機(jī)械發(fā)揮的總效益最大？ 工地工地機(jī)器機(jī)器 甲甲 乙乙 丙丙 丁丁 30 25 40 32 32 35 30 36 35 40 34 27 28 43 32 3852行業(yè)知識(shí)解：解：原效益矩陣中原效益矩陣中 ma

33、x cij= cij=43所以所以 bij= 43 cij ( i , j=1, 2, 3, 4）新新矩矩陣陣原原矩矩陣陣 5110151693871381111318133832432827344035363035323240253053行業(yè)知識(shí)4.5.5 人數(shù)和任務(wù)數(shù)不相等人數(shù)和任務(wù)數(shù)不相等例例 、4項(xiàng)工作分配給項(xiàng)工作分配給6個(gè)人完成，有人可不做個(gè)人完成，有人可不做 工作人 123456 3 6 2 6 7 1 4 4 3 6 5 8 6 4 3 7 5 2 4 3 5 7 6 2 54行業(yè)知識(shí)解：虛設(shè)兩項(xiàng)假想的任務(wù)解：虛設(shè)兩項(xiàng)假想的任務(wù) 工作工作人人 123456 3 6 2 6 0 0

34、 7 1 4 4 0 0 3 6 5 8 0 0 6 4 3 7 0 0 5 2 4 3 0 0 5 7 6 2 0 055行業(yè)知識(shí) 工作工作人人 123456 0 5 0 4 0 0 4 0 2 2 0 0 0 5 3 6 0 0 3 3 1 5 0 0 2 1 2 1 0 0 2 6 4 0 0 0（0）（0）（0）（0）（0）（0）人員安排：人員安排：1 ，2 ；3 ；4，5休息；休息；6 總的時(shí)間為：總的時(shí)間為：2+1+3+2=856行業(yè)知識(shí) 工作工作人人 123456 0 5 0 4 0 0 4 0 2 2 0 0 0 5 3 6 0 0 3 3 1 5 0 0 2 1 2 1 0 0 2 6 4 0 0 0（0）（0）（0）（0）（0）（0）人員安排：人員安排：1 ，2 ；3 ；4，5休息；休息；6 總的時(shí)間為：總的時(shí)間為：2+1+3+2=857行業(yè)知識(shí)例、例、4人完成人完成5項(xiàng)任務(wù)，每人可完成項(xiàng)任務(wù)，每人可完成12項(xiàng)項(xiàng) 任務(wù)任務(wù)人人a b c d e甲乙丙丁 25 29 31 42 37 39 38 26 20 33 34 27 28 40 32 24 42 36 23 4558行業(yè)知識(shí)解：解：因每個(gè)人可擔(dān)任因每個(gè)人可擔(dān)任一至二項(xiàng)一至二項(xiàng)任務(wù)，因此將任務(wù)，因此將4人人 看作