整數(shù)規(guī)劃問(wèn)題

第四章 整數(shù)規(guī)劃與分配問(wèn)題,數(shù)學(xué)模型 割平面法 分枝定界法 0-1整數(shù)規(guī)劃 分配問(wèn)題,整數(shù)規(guī)劃,Integer Linear Programming,簡(jiǎn)述,LP雖然用途廣泛，但經(jīng)常地，客觀上要求 L.P.最優(yōu)解中不能含有非整數(shù)值（如股票的購(gòu)買之解答），整數(shù)規(guī)劃就是專門用來(lái)求解這類問(wèn)題的有效工具 重點(diǎn)掌握：0-1 規(guī)劃靈活應(yīng)用、分枝定界法。,提出問(wèn)題,某廠生產(chǎn)A1，A2兩種品牌電視，用B1，B2兩種原料，具體數(shù)據(jù)如下，求如何安排生產(chǎn)使利潤(rùn)最大,整數(shù)規(guī)劃,數(shù)學(xué)模型,若所有 xj 的解為整數(shù)，稱為純整數(shù)規(guī)劃pure integer linear programming 若部分 xj 的解為整數(shù)，稱為混合整數(shù)規(guī)劃mixed integer linear programming 若xj 只取0或1，成為0-1整數(shù)規(guī)劃zero-one integer linear programming,松弛問(wèn)題,整數(shù)規(guī)劃,整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問(wèn)題的最優(yōu)解,注 釋,最優(yōu)解不一定在頂點(diǎn)上達(dá)到 最優(yōu)解不一定是松弛問(wèn)題最優(yōu)解的鄰近整數(shù)解 整數(shù)可行解遠(yuǎn)多于頂點(diǎn)，枚舉法不可取,整數(shù)規(guī)劃問(wèn)題的求解方法,分枝定界法branch and bound method 分枝定界法是一種隱枚舉方法（implicit enumeration）或部分枚舉方法，是枚舉方法基礎(chǔ)上的改進(jìn)，幾乎所有的計(jì)算機(jī)計(jì)算都用此算法。其關(guān)鍵是分支和定界。 例,Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0 X1 ， X2 取整數(shù),s.t.,6,分支定界法,思路與解題步驟 只解松弛問(wèn)題 1、在全部可行域上解松弛問(wèn)題 若松弛問(wèn)題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解 2、分枝過(guò)程 若松弛問(wèn)題最優(yōu)解中某個(gè) xk=bk 不是整數(shù)，令 bk 為 bk 的整數(shù)部分 構(gòu)造兩個(gè)新的約束條件 xk bk 和 xk bk +1，分別加于原松弛問(wèn)題，形成兩個(gè)新的整數(shù)規(guī)劃 3、求解分枝的松弛問(wèn)題 定界過(guò)程 設(shè)兩個(gè)分枝的松弛問(wèn)題分別為問(wèn)題 1 和問(wèn)題 2 ，它們的最優(yōu)解有如下情況,整數(shù)規(guī)劃,分支問(wèn)題解可能出現(xiàn)的情況,情況 2, 4, 5 找到最優(yōu)解 情況 3 在縮減的域上繼續(xù)分枝定界法 情況 6 問(wèn)題 1 的整數(shù)解作為界被保留，用于以后與問(wèn)題 2 的后續(xù)分枝所得到的解進(jìn)行比較，結(jié)論如情況 4或5,整數(shù)規(guī)劃,分支定界法圖解整數(shù)規(guī)劃,松弛問(wèn)題 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0,該整數(shù)規(guī)劃松弛問(wèn)題的解為： （X1 ，X2 ）=（3/2 ,10/3） Z1 = 29/6,14X1 + 9X2 51,- 6X1 + 3X2 1,51/14,1/3,9,整數(shù)規(guī)劃 Integer Programming（IP）,分支定界法圖解整數(shù)規(guī)劃,松弛問(wèn)題 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0,（3/2 ，10/3） Z1 = 29/6,B1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0,B2 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 1 X1 ， X2 0,B2：解 （1,7/3 ） Z21 = 17/3,B1：解 （2,23/9 ） Z11 = 41/9,1,2,10,整數(shù)規(guī)劃 Integer Programming（IP）,整數(shù)規(guī)劃問(wèn)題的求解方法 分支定界法圖解整數(shù)規(guī)劃,（3/2 ,10/3） Z1 = 29/6,B1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0,B2：解 （1,7/3 ） Z21 = 17/3,B1：解 （2,23/9 ） Z11 = 41/9,B11 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 3 X1 ， X2 0,B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,B12：解 （33/14,2 ） Z12 = 61/14,1 2,X=2,X=3,11,整數(shù)規(guī)劃 Integer Programming（IP）,整數(shù)規(guī)劃問(wèn)題的求解方法 分支定界法圖解整數(shù)規(guī)劃,（3/2 ，10/3） Z1 = 29/6,B2：解 （1,7/3 ） Z21 = 17/3,B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,B12：解 （33/14,2 ） Z12 = 61/14,B121 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 3 X2 2 X1 ， X2 0,B122 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0,B121：解 （3，1 ） Z121 = 4,B122：解 （2，2 ） Z122 = 4,B1：解 （2，23/9 ） Z11 = 41/9,1 2 3,12,割平面法cutting plane approach,割平面法求解整數(shù)規(guī)劃問(wèn)題時(shí)，若其松馳問(wèn)題的最優(yōu)解 X* 不滿足整數(shù)要求時(shí)，則從 X* 的非整分量中選取一個(gè)，用以構(gòu)造一個(gè)線性約束條件（Gomory 割平面），將其加入原松馳問(wèn)題中，形成一個(gè)新的線性規(guī)劃，然后求解之。其關(guān)鍵在于新增加的這個(gè)線性約束條件將切割掉部分非整數(shù)解，至少將當(dāng)前松馳問(wèn)題的非整數(shù)最優(yōu)解切割掉了，而不會(huì)切割掉問(wèn)題的任何整數(shù)解。,13,整數(shù)規(guī)劃 Integer Programming（IP）,整數(shù)規(guī)劃問(wèn)題的求解方法 割平面法cutting plane approach 構(gòu)造切割方程的步驟： 1、令 xi 是相應(yīng)松馳問(wèn)題的最優(yōu)解中為非整數(shù)值的一個(gè)基變量，由單純形表最終表得： xi + aik xk = bi （1 式） 其中 i Q （Q 指基變量下標(biāo)集） k K （K 指非基變量下標(biāo)集）,14,整數(shù)規(guī)劃 Integer Programming（IP）,整數(shù)規(guī)劃問(wèn)題的求解方法 割平面法cutting plane approach 構(gòu)造切割方程的步驟： 2、將 bi 和 aik 都分解成整數(shù)部分 N （不超過(guò) b 的最大整數(shù)）與非負(fù)真分?jǐn)?shù)部分 f 之和，即： bi = Ni + fi ， 其中 0 fi 1 （2 式） aik = Nik + fik ，其中 0 fik 1 例如：若 b = 2.35 ，則 N = 2 ，f = 0.35； 若 b = -1.45 ，則 N = -2 ，f = 0.55,15,整數(shù)規(guī)劃 Integer Programming（IP）,割平面法cutting plane approach 構(gòu)造切割方程的步驟： 2、將（2 式）代入（1 式）得： xi + Nik xk - Ni = fi - fik xk （3 式） 3、提出變量為整（當(dāng)然含非負(fù)）的條件： 由于（3 式）中等式左邊需整，而 0 fi 1 ，故有 fi - fik xk 0 （4 式） 此即為所需切割方程。,16,整數(shù)規(guī)劃 Integer Programming（IP）,割平面法cutting plane approach 構(gòu)造切割方程的步驟： （1）切割方程 fi - fik xk 0 真正進(jìn)行了切割，至少把非整數(shù)最優(yōu)解這一點(diǎn)切割掉了。 證明：（反證法）假設(shè)松馳問(wèn)題的最優(yōu)解 X* 未被切割掉，則由 fi - fik x*k 0， 又因?yàn)?x*k = 0，（因 x*k 為非基變量） 有 fi 0 ，這與 fi 0 矛盾。 （2）不會(huì)切割掉任何整數(shù)解，因?yàn)榍懈罘匠淌怯勺兞繛檎臈l件提出的。,17,整數(shù)規(guī)劃 Integer Programming（IP）,割平面法cutting plane approach 例求解,IP Max Z = X1 + X2 - X1 + X2 1 3X1 + X2 4 X1 ，X2 0 X1 ，X2 整數(shù),LP Max Z = X1 + X2 - X1 + X2 1 3X1 + X2 4 X1 ，X2 0,18,1、求解 LP 得到非整數(shù)最優(yōu)解： X =（3/4，7/4，0，0），Max Z = 5/2,求解步驟：,19,整數(shù)規(guī)劃 Integer Programming（IP）,求解步驟： 2、構(gòu)造切割方程： 由 B 表中的第 2 個(gè)方程 X2 + 3/4 X3 + 1/4 X4 = 7/4 有 b2 = 7/4 = 1 + 3/4 a23 = 3/4 = 0 + 3/4 ， a24 = 1/4 = 0 + 1/4 因此，切割方程為 3/4 3/4 X3 1/4 X4 0 增加松弛變量 X5 ，并將如下方程的約束條件添加到 B 表中。 - 3 X3 - 1 X4 + X5 = - 3 X5 0,20,整數(shù)規(guī)劃 Integer Programming（IP）,求解步驟： 3、求解新的松弛問(wèn)題,21,0-1整數(shù)規(guī)劃問(wèn)題,0-1 變量及其應(yīng)用 0-1變量作為邏輯變量（Logical variable），常常被引用來(lái)表示系統(tǒng)是否處于某個(gè)特定的狀態(tài)，或者決策變量是否取某個(gè)特定的方案。,xj =,1 當(dāng)決策取方案 P j 時(shí) 0 當(dāng)決策不取方案 Pj 時(shí),22,0-1整數(shù)規(guī)劃,一、項(xiàng)目選定(選址）問(wèn)題,整數(shù)規(guī)劃,在經(jīng)濟(jì)全球化的時(shí)代，許多公司為在全球范圍內(nèi)最優(yōu)地配置資源（如獲取廉價(jià)勞動(dòng)力或原料等），要在不同地方建廠或倉(cāng)庫(kù)及其他服務(wù)設(shè)施，這些都要進(jìn)行項(xiàng)目或地址的選擇。在選址之前，許多侯選地點(diǎn)要進(jìn)行分析和比較，而每個(gè)決策都涉及到一個(gè)選還是不選的問(wèn)題。,案例一,某銷售公司打算通過(guò)在武漢或長(zhǎng)春設(shè)立分公司（也許兩個(gè)城市都設(shè)）增加市場(chǎng)份額，管理層同時(shí)也計(jì)劃在新設(shè)分公司的城市最多建一個(gè)配送中心，當(dāng)然也可以不建配送中心。經(jīng)過(guò)計(jì)算，每種選擇對(duì)公司收益的凈現(xiàn)值、所需費(fèi)用列在下表中，總預(yù)算投資費(fèi)用不得超過(guò)20萬(wàn)。如何決策使總凈現(xiàn)值最大,設(shè) xj=,10,- 決策j問(wèn)題的答案是“是” - 決策j問(wèn)題的答案是“否”,max z = 18x1 + 10x2 + 12x3+8x4,最優(yōu)解 x1 =1，x2=1,案例練習(xí),例1：某油田在10個(gè)有油氣構(gòu)造處要選擇若干個(gè)鉆探采油，設(shè)第j個(gè)構(gòu)造開采時(shí)需投資aj元，投產(chǎn)后預(yù)計(jì)年收凈益為cj元，若該油田投資的總限額為b元，問(wèn)：應(yīng)選擇哪幾個(gè)構(gòu)造開采最為有利？,設(shè) xj=,10,- 選擇開采第j個(gè)構(gòu)造 -不選擇開采第j個(gè)構(gòu)造,max z=cjxj,j=1,10,ajxj b,xj0或1 (j=1,2,-,10),j=1,10,-年總收益,-投資額限制,1、表示選擇性決策,若在開采時(shí)還需滿足下述條件： （a）若開采8號(hào)，則必須同時(shí)開采6號(hào)； （b）若開采5號(hào)，則不許開采3號(hào)； （c） 2 號(hào)和4號(hào)至少開采一個(gè)； （d） 8 號(hào)與7號(hào)必須同時(shí)開采； （e）1號(hào)、4號(hào)、6號(hào)、9號(hào)開采時(shí)不能超過(guò)兩個(gè)，試表示上述約束條件。,設(shè) xj=,10,- 選擇開采第j個(gè)構(gòu)造 -不選擇開采第j個(gè)構(gòu)造,max z=cjxj,j=1,10,ajxj b,xj0或1 (j=1,2,-,10),j=1,10,-年總收益,-投資額限制,（a）當(dāng)x8=1,x6=1，x60,當(dāng)x8=0,x6=1，x6=0, x8 x6,（b）當(dāng)x5 =1,x3=0， x3 1,當(dāng)x5 =0,x3=0， x3 =1, x5 + x3 1,（c） x2 + x4 1,（d） x8 = x7,（e） x1 + x4 + x6 + x9 2,在生產(chǎn)或經(jīng)營(yíng)過(guò)程中，某一個(gè)業(yè)務(wù)活動(dòng)開展通常伴隨著固定成本的發(fā)生，比如添置或起用設(shè)備，新采購(gòu)材料時(shí)產(chǎn)生的差旅費(fèi)，對(duì)工人必要培訓(xùn)的費(fèi)用等，這些構(gòu)成產(chǎn)品的固定成本。這時(shí)，業(yè)務(wù)活動(dòng)的總成本就包括與活動(dòng)數(shù)量大小相關(guān)的變動(dòng)成本和起動(dòng)活動(dòng)的固定成本。,二 固定費(fèi)用（成本）問(wèn)題,案例,某工廠近期接到一批訂單，要安排生產(chǎn)甲、乙、丙、丁四種產(chǎn)品，每件產(chǎn)品分別需要原料A、B、C中的一種或幾種中的若干單位，合同規(guī)定要在15天內(nèi)完成，但數(shù)量不限。由于四種產(chǎn)品都在同一種設(shè)備上生產(chǎn)，且一臺(tái)設(shè)備同一時(shí)間只能加工一件產(chǎn)品。目前，工廠只有一臺(tái)正使用中的這種設(shè)備（設(shè)備1），合同期內(nèi)可擠出3天來(lái)生產(chǎn)訂單，但會(huì)產(chǎn)生150元的機(jī)會(huì)成本損失；還有一臺(tái)長(zhǎng)期未用的設(shè)備（設(shè)備2）可以啟用，啟用時(shí)要做必要的檢查和修理，費(fèi)用1000元；公司還考慮向鄰廠租用2臺(tái)（設(shè)備3，4），由于對(duì)方也在統(tǒng)籌使用，租期分別只能7和12天，租金分別2000和3100，工廠可以決定租一臺(tái)或兩臺(tái)，也可以一臺(tái)不租。另外，每種產(chǎn)品如果生產(chǎn)會(huì)有固定成本和變動(dòng)成本，具體如下表，假設(shè)每天工作8小時(shí)，工廠最多使用3臺(tái)設(shè)備，問(wèn)：工廠如何生產(chǎn)和利用設(shè)備，利潤(rùn)最大,24 120 56 96 150 1000 2000 3100,例 應(yīng)用 0-1 變量解決含互斥約束條件問(wèn)題 設(shè)：工序 B 有兩種方式完成 方式（1 ）的工時(shí)約束為 0.3X1 + 0.5X2 150 方式（2 ）的工時(shí)約束為 0.2X1 + 0.4X2 120 問(wèn)題是完成工序 B 只能從兩種方式中任選一種，如何將這兩個(gè)互斥的約束條件統(tǒng)一在一個(gè)線性規(guī)劃模型中呢？,三 互相排斥問(wèn)題,32,例 7 應(yīng)用 0-1 變量解決含互斥約束條件問(wèn)題 引入 0-1 變量,y1 =,0 若工序 B 采用方式（1 ）完成 1 若工序 B 不采用方式（1 ）完成,y2 =,0 若工序 B 采用方式（2 ）完成 1 若工序 B 不采用方式（2 ）完成,三 互相排斥問(wèn)題,33,例 7 應(yīng)用 0-1 變量解決含互斥約束條件問(wèn)題 于是前面兩個(gè)互斥的約束條件可以統(tǒng)一為如下三個(gè)約束條件： 0.3X1 + 0.5X2 150 + M1y1 0.2X1 + 0.4X2 120 + M2y2 y1 + y2 = 1 其中 M1 ，M2 都是足夠大的正數(shù)。,三 互相排斥問(wèn)題,34,案例,因?yàn)橘Y金和管理水平的限制，某公司想以相同的價(jià)格和不同的租期（工時(shí)）租賃另一公司甲、乙、丙、丁四個(gè)車間中的兩個(gè)，來(lái)生產(chǎn)五種新開發(fā)的產(chǎn)品（A、B、C、D、E）中的最多三種。由于車間的機(jī)床和工人的經(jīng)驗(yàn)不同，生產(chǎn)不同產(chǎn)品的效率也不同，導(dǎo)致不同產(chǎn)品（任一階段）在不同的車間生產(chǎn)所用的工時(shí)數(shù)不同（根據(jù)生產(chǎn)部的初步實(shí)驗(yàn)和經(jīng)驗(yàn)判斷估計(jì)出的數(shù)據(jù)見(jiàn)下表）另外，根據(jù)公司市場(chǎng)部的預(yù)測(cè)，每種產(chǎn)品的單位利潤(rùn)和在租期內(nèi)最大的銷售量以及各車間在租期內(nèi)的總工時(shí)數(shù)等也見(jiàn)表）,取M=1000，得X1=20，X3=23，X4=2，Z=434,0-1整數(shù)規(guī)劃的解法,枚舉法 隱枚舉法,整數(shù)規(guī)劃,指派(分配）問(wèn)題,例：有一份中文產(chǎn)品說(shuō)明書需譯成英、日、德、俄四種語(yǔ)言，現(xiàn)有甲、乙、丙、丁四人都可以勝任，他們譯成不同語(yǔ)言所需時(shí)間不同，如下表。求如何分配使所需總時(shí)間最少（每人只譯一種）,整數(shù)規(guī)劃,指派問(wèn)題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型 指派問(wèn)題的標(biāo)準(zhǔn)形式（以人和事為例）是： 有 n 個(gè)人和 n 件事，已知第 i 人做第 j 事的費(fèi)用為 Cij（i，j = 1，2，n），要求確定人和事之間的一一對(duì)應(yīng)的指派方案，使完成這件事的總費(fèi)用最少。如,指派問(wèn)題（assignment problem）,例：有一份中文產(chǎn)品說(shuō)明書需譯成英、日、德、俄四種語(yǔ)言，現(xiàn)有甲、乙、丙、丁四人都可以勝任，他們譯成不同語(yǔ)言所需時(shí)間不同，如下表。求如何分配使所需總時(shí)間最少（每人只譯一種）,39,建立模型：,設(shè) xij=,1,0,譯英文：,x11+ x12 + x13 + x14 =1,譯日文：,x21+ x22 + x23 + x24 =1,譯德文：,x31+ x32 + x33 + x34 =1,譯俄文：,x41+ x42 + x43 + x44 =1,甲：,x11+ x21 + x31 + x41 =1,乙：,x12+ x22 + x32 + x42 =1,丙：,x13+ x23 + x33 + x43 =1,?。?x14+ x24 + x34 + x44 =1,xij =0或1 (i=1,2,3,4; j=1,2,3,4),Min z= aijxij (aij-效率),i=1j=1,4 4,若第i項(xiàng)工作交與第j個(gè)人完成,若第i項(xiàng)工作不交與第j個(gè)人完成,一般模型,指派問(wèn)題的標(biāo)準(zhǔn)形式，令,1 當(dāng)指派第 i 人完成第 j 項(xiàng)任務(wù) 0 當(dāng)不指派第 i 人完成第 j 項(xiàng)任務(wù),xij =,min z = cijxij xij = 1， j = 1，2，n xij = 1， i = 1，2，n xij = 1 或 0,41,匈牙利解法,標(biāo)準(zhǔn)的指派問(wèn)題是一類特殊的 0-1 整數(shù)規(guī)劃問(wèn)題，可以用多種相應(yīng)的解法來(lái)求解。但是，這些方法都沒(méi)有充分利用指派問(wèn)題的特殊性質(zhì)來(lái)有效減少計(jì)算量。1955年，庫(kù)恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格（D.Knig）的關(guān)于矩陣中獨(dú)立零元素的定理，提出了指派問(wèn)題的一種解法，由此，習(xí)慣上稱之為匈牙利解法。,42,匈牙利解法的關(guān)鍵是利用了指派問(wèn)題最優(yōu)解的如下性質(zhì)： 若從指派問(wèn)題的系數(shù)矩陣 C = （ cij ）nn 的某行（或某列）各元素分別減去一個(gè)常數(shù) k ，得到一個(gè)新的系數(shù)矩陣C = （ cij ）則以 C 和 C 為系數(shù)矩陣的兩個(gè)指派問(wèn)題有相同的最優(yōu)解。,匈牙利解法,43,步驟一： 變換系數(shù)矩陣。使其每行及每列至少有一個(gè)零元素，同時(shí)不出現(xiàn)負(fù)元素。 步驟二： 進(jìn)行試指派，即確定獨(dú)立零元素。 步驟三： 繼續(xù)變換系數(shù)矩陣，然后返回步驟二。,匈牙利解法的一般步驟,44,以上例說(shuō)明步驟,2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9,0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2,2 4 9 7,min,（ cij ）=,匈牙利解法的一般步驟,45,指派問(wèn)題（assignment problem） 匈牙利解法的一般步驟 以上例說(shuō)明步驟,0 13 11 2 6 0 10 11 0 4 7 4 0 1 4 2,0 0 4 2,min,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,= （ cij ）,指派問(wèn)題（assignment problem）,46,以上例說(shuō)明步驟,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,此時(shí)加圈 0 元素的個(gè)數(shù) m = n = 4，所以得到最優(yōu)解,指派問(wèn)題（assignment problem）,47,匈牙利解法的一般步驟 以上例說(shuō)明步驟,0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0,（ xij ）=,指派問(wèn)題（assignment problem）,48,匈牙利解法的一般步驟 例,指派問(wèn)題（assignment problem）,49,匈牙利解法的一般步驟,12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 9,7 6 7 6 4,5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5,指派問(wèn)題（assignment problem）,50,匈牙利解法的一般步驟,5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5,此時(shí)加圈 0 元素的個(gè)數(shù) m = 4， 而n = 5，所以解題沒(méi)有完成。獨(dú)立零元素（加圈零元素）少于 n 個(gè)，表示還不能確定最優(yōu)指派方案。此時(shí)需確定能覆蓋所有零元素的最少直線數(shù)目的直線集合。方法如下：,指派問(wèn)題（assignment problem）,51,匈牙利解法的一般步驟,對(duì)沒(méi)有加圈零元素的行打號(hào)； 對(duì)所有打號(hào)行的所有含零元素的列打號(hào)； 再對(duì)已打號(hào)的列中含零元素的行打號(hào)； 重復(fù)2）和3），直到再也不能找到可以打號(hào)行或列為止； 對(duì)沒(méi)有打號(hào)的行畫一橫線，對(duì)打號(hào)的列畫一豎線，這樣就得到能覆蓋所有零元素的最少直線數(shù)目的直線集合。,指派問(wèn)題（assignment problem）,52,匈牙利解法的一般步驟,5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5,指派問(wèn)題（assignment problem）,53,匈牙利解法的一般步驟 繼續(xù)變換系數(shù)矩陣。其方法是在未被直線覆蓋的元素中找出一個(gè)最小元素。然后在打號(hào)行各元素都減去這一最小元素，而在打號(hào)列的各元素都加上這一最小元素，以保證原來(lái)的 0 元素不變。這樣得到新系數(shù)矩陣（其最優(yōu)解和原問(wèn)題相同）。若得到 n 個(gè)獨(dú)立的 0 元素，則已得最優(yōu)解，否則重復(fù)該步驟繼續(xù)變換系數(shù)矩陣。,指派問(wèn)題（assignment problem）,54,匈牙利解法的一般步驟,5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5,最小元素= 2,7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 3,指派問(wèn)題（assignment problem）,55,匈牙利解法的一般步驟,7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 3,此時(shí)加圈 0 元素的個(gè)數(shù) m = 5， 而n = 5，獨(dú)立零元素（加圈零元素）等于 n 個(gè)，此時(shí)已得到最優(yōu)解，其解矩陣為,指派問(wèn)題（assignment problem）,56,匈牙利解法的一般步驟,（ xij ）=,0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0,最優(yōu)指派： 甲 B 乙 C 丙 E 丁 D 戊 A,指派問(wèn)題（assignment problem）,57,在實(shí)際應(yīng)用中，常會(huì)遇到各種非標(biāo)準(zhǔn)形式的制派問(wèn)題。一般的處理方法是先將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后再用匈牙利法求解。 最大化指派問(wèn)題設(shè)最大化指派問(wèn)題系數(shù)矩陣