1、1溫故知新溫故知新2第五章 整數規劃3第五章 整數規劃 整數規劃問題的提出 分支定界法 割平面法 0-1型整數規劃 指派問題4純整數線性規劃純整數線性規劃（全整數規劃）（全整數規劃）混合整數線性規劃混合整數線性規劃0-10-1型線性規劃問題型線性規劃問題 整數規劃（整數規劃（Integer Programming, IPInteger Programming, IP） 要求一部分或全部決策變量必須取整數值的規劃問題稱為要求一部分或全部決策變量必須取整數值的規劃問題稱為整數規劃整數規劃。 不考慮整數條件，由余下的目標函數和約束條件構成的規不考慮整數條件，由余下的目標函數和約束條件構成的規劃問題稱

2、為該劃問題稱為該整數規劃問題的松弛問題整數規劃問題的松弛問題（slack problemslack problem） 。 若松弛問題是一個線性規劃，則稱該整數規劃為若松弛問題是一個線性規劃，則稱該整數規劃為整數線性整數線性規劃規劃（Integer Linear ProgrammingInteger Linear Programming）。）。一. 整數規劃問題的提出5整數線性規劃的數學模型整數線性規劃的數學模型112(1,2,.,)01,2,.,.,nijjjjna ximxjnx xxj=, )b中部分或全部取整數1max(min)njjjzc x或一. 整數規劃問題的提出6求解整數規劃數學

3、模型：求解整數規劃數學模型：分支定界法分支定界法割平面法割平面法一. 整數規劃問題的提出7例：求解整數規劃問題例：求解整數規劃問題(記作記作問題問題A) 1212121212max114951 (2)6313,0(4),zxxxxxxxxxx為整數 (5)記作記作問題問題B二. 分支定界法10二. 分支定界法算法思路算法思路11n 步驟一：求解問題B二. 分支定界法12n 步驟二：求解問題A二. 分支定界法13第1步：分支定界 二. 分支定界法14第1步：分支定界 二. 分支定界法15第二步：比較與剪支 二. 分支定界法16二. 分支定界法例：求解例：求解 1212121212max40901

4、97562720703,04,5zxxxxxxx xx x為整數17解解 先不考慮條件，即解相應的線性規劃B,(見圖5-2)，得最優解x1=4.81，x2=1.82，z0=356 不符合整數條件。18 這時z0 356是問題A的最優目標函數值z*的上界，記作z0= 。 而在x1=0，x2=0時，顯然是問題A的一個整數可行解，這時z=0，是z*的一個下界，記作 =0，即0z*356。zz二. 分支定界法19 首先注意其中一個非整數變量的解，如首先注意其中一個非整數變量的解，如x x1 1，在問題，在問題B B的解中的解中x x1 1=4.81=4.81。 對原問題增加兩個約束條件對原問題增加兩個

5、約束條件x x1 144，x x1 155。可將。可將原問題分解為兩個子問題原問題分解為兩個子問題B B1 1和和B B2 2( (即兩支即兩支) )。 這并不影響問題這并不影響問題A A的可行域。的可行域。二. 分支定界法20 x x1 144，x x1 155二. 分支定界法21 不考慮整數條件解問題不考慮整數條件解問題B B1 1和和B B2 2，稱此為第一次迭代。得到最，稱此為第一次迭代。得到最優解為：優解為： 顯然沒有得到全部變量是整數的解。因顯然沒有得到全部變量是整數的解。因z1z1z2z2，故將，故將 改為改為349349，那么必存在最優整數解，得到，那么必存在最優整數解，得到z

6、 z* *，并且，并且00z z* *349349二. 分支定界法z22繼續對問題B1和B2進行分解 因z1z2，故先分解B1為兩支。增加條件x22者，稱為問題B3；增加條件x23者稱為問題B4。 在圖中再舍去 x22與x33 之間的可行域， 進行第二次迭代。二. 分支定界法23繼續對問題B2進行分解二. 分支定界法25分支定界法是求解整數規劃的較好方法，有著廣泛分支定界法是求解整數規劃的較好方法，有著廣泛的適用性，便于編程實現。的適用性，便于編程實現。分支定界法適用于求解混合整數規劃問題。分支定界法適用于求解混合整數規劃問題。分支定界法關鍵在于有效地分支定界。分支定界法關鍵在于有效地分支定界

7、。n分支定界法總結二. 分支定界法26第五章 整數規劃 整數規劃問題的提出 分支定界法 割平面法 0-1型整數規劃 指派問題27割平面解法的思路： 首先不考慮決策變量為整數的條件，增加線性約束條件（幾何術語稱為割平面），使得由原可行域中切割掉一部分，這部分只包含非整數解，沒有切割掉任何整數可行解。 割平面法就是找到適當的割平面（不見得一次就找到），使切割后最終得到這樣的可行域，它的切割后最終得到這樣的可行域，它的一個有整數坐標的頂點恰好是問題的最優解一個有整數坐標的頂點恰好是問題的最優解。一. 整數規劃問題的提出28n 割平面需要滿足割平面需要滿足分割有效：即真正割去可行域中一部分。最終要能夠

8、恰好割出這樣的可行域：符合整數條件的最優解正好在它的頂點上。沒有割去任何整數可行解。三. 割平面法 這個方法是這個方法是R.E.GomoryR.E.Gomory提出來的，所以又稱為提出來的，所以又稱為GomoryGomory的割平面法。的割平面法。 以下只討論純整數線性規劃的情形，現舉例說明。以下只討論純整數線性規劃的情形，現舉例說明。29例：求解純整數規劃問題例：求解純整數規劃問題 1212121212max112343,04,zxxxxxxx xx x是整數5三.割平面法 得到非整數的最優解為：得到非整數的最優解為：1234375,0, m ax244xxxxz31331133444433

9、12344441xxxxxxx311134444371234444xxxxxx由最終表得到：將有關系數和常數項分成整數與正的小數部分得到：三.割平面法32現考慮整數條件，可知上面兩式右側必須非正，得到現考慮整數條件，可知上面兩式右側必須非正，得到：331344440 xx 將此作為增加的約束條件，加入到上面的最終計算表中。將此作為增加的約束條件，加入到上面的最終計算表中。34533xxx 化簡并引入松弛變量得到：化簡并引入松弛變量得到：三.割平面法33三.割平面法34 得到得到x1 =1, x2 =1為符合整數條件的最優解，解題完成。為符合整數條件的最優解，解題完成。三.割平面法353433x

10、x三.割平面法(1,1)C(1,1)C36第一步：求解相應的松弛問題，列出最終單純形表。 三. 割平面法37第二步：分解系數為整數和非負真分數兩個部分。 三.割平面法38第三步：利用分數部分得到切割方程。 滿足割平面的滿足割平面的要求嗎？要求嗎？三.割平面法39思考：思考： 切割方程式真正進行了切割，至少把不滿切割方程式真正進行了切割，至少把不滿足整數條件的最優基可行解割掉了。足整數條件的最優基可行解割掉了。 沒有割掉任何整數可行解。沒有割掉任何整數可行解。三.割平面法40第四步：將得到的切割方程作為約束條件加到原線性規劃問題中，并求解。第五步：如果得到的解滿足整數條件，停止，否則返回到第一步

11、三.割平面法41割平面法較少單獨使用。割平面法較少單獨使用。割平面法實質是一種排除法。割平面法實質是一種排除法。割平面法若和其他方法（如分枝定界法）配合使用，割平面法若和其他方法（如分枝定界法）配合使用，是有效的。是有效的。割平面法經常會碰到收斂很慢的情況，效率不高。割平面法經常會碰到收斂很慢的情況，效率不高。n割平面法總結三.割平面法42nP152 6.3（1）課后作業課后作業43第五章 整數規劃 整數規劃問題的提出 分支定界法 割平面法 0-1型整數規劃 指派問題44四. 0-1型整數規劃0 01 1型整數規劃的概念型整數規劃的概念 0101變量作為變量作為邏輯變量邏輯變量(logical

12、 variable)(logical variable)，常被用來，常被用來表示表示系統系統是否處于某個是否處于某個特定狀態特定狀態，或者決策時是否取某，或者決策時是否取某個特定方案。個特定方案。若問題含有多項若問題含有多項要素要素，而每項要素皆有兩種選擇時，可，而每項要素皆有兩種選擇時，可用用一組一組0-10-1變量來描述。變量來描述。應用中，決策變量取多個整數值的問題，可以應用中，決策變量取多個整數值的問題，可以轉化轉化為為0-10-1型問題。型問題。 決策變量僅取值決策變量僅取值0或或1的整數規劃問題稱為的整數規劃問題稱為01型整數規劃型整數規劃。這時決策變量稱為。這時決策變量稱為01變

13、量。變量。45例 引入0-1變量的實際問題投資場所的選定投資場所的選定相互排斥的計劃相互排斥的計劃 某公司擬在市東、西、南三區建立門市部。擬議中有某公司擬在市東、西、南三區建立門市部。擬議中有7個個位置位置(點點)Ai (i=1，2，7)可供選擇。規定：可供選擇。規定： 在東區，由在東區，由A1，A2，A3三個點中至多選兩個；三個點中至多選兩個； 在西區，由在西區，由A4，A5兩個點中至少選一個；兩個點中至少選一個； 在南區，由在南區，由A6，A7兩個點中至少選一個。兩個點中至少選一個。 如選用如選用Ai點，設備投資估計為點，設備投資估計為bi元，每年可獲利潤估計為元，每年可獲利潤估計為ci元

14、，但投資總額不能超過元，但投資總額不能超過B元。問應選擇哪幾個點可使元。問應選擇哪幾個點可使年利潤為最大年利潤為最大?四. 0-1型整數規劃467 , 2 , 1, 0, 1iAAxiii點沒有被選用當點被選用當令于是問題可列成： 71711234567m ax21101 (1,., 7)iiiiiiizc xb xBxxxxxxxxi目 標 函 數 ：約 束 條 件或四. 0-1型整數規劃470-1型整數規劃的數學模型型整數規劃的數學模型四. 0-1型整數規劃48求解求解0-1型整數規劃數學模型的方法型整數規劃數學模型的方法 窮舉法（完全枚舉法）窮舉法（完全枚舉法） 隱枚舉法（部分枚舉法）隱

15、枚舉法（部分枚舉法）四. 0-1型整數規劃49舉例說明隱枚舉法舉例說明隱枚舉法 1231231231223123max3252214423346(4),015zxxxxxxxxxxxxxx x x或四. 0-1型整數規劃50n第一步 找到一個可行解，增加約束條件。 四. 0-1型整數規劃51n第二步第二步 在表中列出所有約束條件，并逐次計算所有解在表中列出所有約束條件，并逐次計算所有解。 計算過程中如某一條件不滿足約束條件，同行以后各種計算過程中如某一條件不滿足約束條件，同行以后各種條件就不必再檢查。條件就不必再檢查。 在計算過程中，若遇到值以超過條件在計算過程中，若遇到值以超過條件右邊的值，

16、應改右邊的值，應改變條件變條件，使右邊為迄今為止最大者，然后繼續作。，使右邊為迄今為止最大者，然后繼續作。四. 0-1型整數規劃52改變改變約束條件，繼續實施，直至得到最優解約束條件，繼續實施，直至得到最優解。 四. 0-1型整數規劃53四. 0-1型整數規劃54隱枚舉法改進： 重新排列xi的順序使目標函數中xi的系數是遞增(不減)的，在上例中， 改寫 z=3x1-2x2+5x3=-2x2+3x1+5x3 因為-2，3，5是遞增的序，變量(x2，x1，x3)也按下述順序取值：(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)，。這樣，最優解容易比較早的發現。 四. 0-1型整數規劃

17、55重新排列決策變量在目標函數中的順序使之在目標函數中的系數是遞增（不減）的，可以改進計算效率。隱枚舉法的計算量比窮舉法要少得多。n隱枚舉法總結隱枚舉法處理的點的個數為2n。四. 0-1型整數規劃56nP154 6.8（2）課后作業課后作業57第五章 整數規劃 整數規劃問題的提出 分支定界法 割平面法 0-1型整數規劃 指派問題58 生活中經常遇到這樣的問題：完成生活中經常遇到這樣的問題：完成若干項任務若干項任務，恰好，恰好若干若干個人個人可以承擔這些任務。由于每人的專長不同，各人完成任務可以承擔這些任務。由于每人的專長不同，各人完成任務的能力、花費和效率不同。于是產生應指派哪個人去完成哪項的

18、能力、花費和效率不同。于是產生應指派哪個人去完成哪項任務，使完成任務的任務，使完成任務的總體效果總體效果最好（花費最小，時間最少或者最好（花費最小，時間最少或者完成程度最好等）。完成程度最好等）。 五. 指派問題 這類問題稱為這類問題稱為指派問題指派問題或或分派問題分派問題，它是特殊，它是特殊的的0-10-1整數規劃問題。整數規劃問題。59例：有一份中文說明書，要譯成英、日、德、俄四種文字，例：有一份中文說明書，要譯成英、日、德、俄四種文字，記作記作E、J、G、R。現有甲、乙、丙、丁四人。他們將中文。現有甲、乙、丙、丁四人。他們將中文說明書譯成不同語種的說明書所需時間如表所示。問應指說明書譯成

19、不同語種的說明書所需時間如表所示。問應指派每人去完成何工作，使所需總時間最少？派每人去完成何工作，使所需總時間最少？五. 指派問題60 類似有：有n項加工任務，怎樣指派到n臺機床上分別完成的問題；有n條航線，怎樣指定n艘船去航行。 對應每個指派問題，需有效率矩陣或系數矩陣，其元素cij0(i,j=1,2，n)表示指派第i人去完成第j項任務時的效率(或時間、成本等)。 建模時需引入變量xij；其取值只能是1或0。并令 項任務人去完成第當不指派第項任務人去完成第當指派第jijixij, 0, 1五. 指派問題61指派問題數學模型的標準形式指派問題數學模型的標準形式1111min1,1,2,1,1,

20、2,10nnijijijnijjnijiijzc xxinxjnx或五. 指派問題這些約束條件代這些約束條件代表什么含義呢？表什么含義呢？目標函數代表什目標函數代表什么含義？么含義？62 滿足約束條件的可行解滿足約束條件的可行解x xijij也可寫成表格或矩陣形式，稱為也可寫成表格或矩陣形式，稱為解矩陣解矩陣(xij)nn 。 如前例的一個可行解矩陣如前例的一個可行解矩陣 目標函數的目標函數的價值系數矩陣價值系數矩陣(cij)nn01000010()10000001ijxl結構松散，且矩陣元結構松散，且矩陣元素等于素等于1 1或者或者0 0；l每一行、每一列只有每一行、每一列只有一個一個1元素

21、。元素。五. 指派問題63指派問題模型的特點指派問題模型的特點 變量個數多（變量個數多（n n2 2個）個） 約束（約束（2n2n個）簡單個）簡單 約束系數矩陣稀疏約束系數矩陣稀疏五. 指派問題 變量取值特殊（僅取變量取值特殊（僅取0 0或或1 1）64指派問題的求解指派問題的求解 整數規劃的一般求解方法整數規劃的一般求解方法 求解求解0-10-1型整數規劃的隱枚舉法型整數規劃的隱枚舉法 運輸問題的表上作業法運輸問題的表上作業法五. 指派問題 指派問題是指派問題是0-10-1規劃的特例，也是運輸問題的規劃的特例，也是運輸問題的特例，即特例，即n=m, ai=bj=1，當然可用以下方法求解：，當

22、然可用以下方法求解：65指派問題的求解指派問題的求解五. 指派問題 針對指派問題特點的匈牙利解法針對指派問題特點的匈牙利解法 以上方法就如同用單純形法求解運輸問題一樣以上方法就如同用單純形法求解運輸問題一樣是不合算的。利用指派問題特點有更簡便的解法。是不合算的。利用指派問題特點有更簡便的解法。 1955 1955年庫恩年庫恩KuhnKuhn給出了一種解法，是基于匈牙給出了一種解法，是基于匈牙利數學家康尼格利數學家康尼格KonigKonig給出的定理，故又稱給出的定理，故又稱“匈牙匈牙利方法利方法”66指派問題的求解指派問題的求解五. 指派問題 定理定理1 1 從效率矩陣從效率矩陣(cij )m

23、m每行（或列）減去每行（或列）減去一個常數一個常數ui（或（或vj），所得新的矩陣），所得新的矩陣(bij)mm，其中，其中bijcij ui (或或 cij vj ）的指派問題與原問題的最的指派問題與原問題的最優指派相同。優指派相同。67由定理一得指派問題最優解的性質：由定理一得指派問題最優解的性質： 從價值系數矩陣從價值系數矩陣( cij )的一行（列）各元的一行（列）各元素中分別減去行（列）的最小元素，得到新素中分別減去行（列）的最小元素，得到新矩陣矩陣( bij ) 。那么以。那么以( bij )為系數矩陣求得的最為系數矩陣求得的最優解和用原系數矩陣求得的最優解相同。優解和用原系數矩陣

24、求得的最優解相同。 五. 指派問題68 利用這個性質，可使原系數矩陣變換為含利用這個性質，可使原系數矩陣變換為含有很多有很多0 0元素的新系數矩陣，而最優解保持不元素的新系數矩陣，而最優解保持不變。變。 在系數矩陣在系數矩陣( ( bij ) )中，我們關心位于不同中，我們關心位于不同行不同列的行不同列的0 0元素，以下簡稱為元素，以下簡稱為獨立的獨立的0 0元素元素。五. 指派問題69獨立的獨立的0 0元素元素位于不同行不同列的位于不同行不同列的0 0元素。元素。 若能在系數矩陣若能在系數矩陣(b(bijij) )中找出中找出n n個獨立的個獨立的0 0元元素，則令解矩陣素，則令解矩陣(x(

25、xijij) )中對應這個獨立的中對應這個獨立的0 0元素的元素的元素取值為元素取值為1 1，其他元素取值為，其他元素取值為0 0。將其代入目。將其代入目標函數中，標函數中，z zb b=b=bijijx xijij得得z zb b=0=0。它一定是最小。它一定是最小。 這就是以這就是以(b(bijij) )為系數矩陣的指派問題的最為系數矩陣的指派問題的最優解。也就得到了原問題的最優解。優解。也就得到了原問題的最優解。五. 指派問題70指派問題的求解指派問題的求解五. 指派問題 定理定理2 2 矩陣中覆蓋所有矩陣中覆蓋所有0 0元素的最少直線數，元素的最少直線數，等于位于不同行且不同列的等于位

26、于不同行且不同列的0 0元素最大個數。元素最大個數。71例：有一份中文說明書，要譯成英、日、德、俄四種文字，例：有一份中文說明書，要譯成英、日、德、俄四種文字，記作記作E、J、G、R。現有甲、乙、丙、丁四人。他們將中文。現有甲、乙、丙、丁四人。他們將中文說明書譯成不同語種的說明書所需時間如表所示。問應指說明書譯成不同語種的說明書所需時間如表所示。問應指派每人去完成何工作，使所需總時間最少？派每人去完成何工作，使所需總時間最少？五. 指派問題72指派問題的解法：指派問題的解法：第一步：第一步：使指派問題的系數矩陣經變換，在各行各列使指派問題的系數矩陣經變換，在各行各列中都出現中都出現0 0元素。

27、元素。（1 1）從系數矩陣的每行元素減去該行的最小元素；）從系數矩陣的每行元素減去該行的最小元素；（2 2）再從所得的系數矩陣的每列元素中減去該列的最）再從所得的系數矩陣的每列元素中減去該列的最 小元素。小元素。 若該行（列）已有若該行（列）已有0 0元素，那就不必再減了。元素，那就不必再減了。五. 指派問題73第二步：第二步：進行試指派，以尋求最優解進行試指派，以尋求最優解 經第一步變換后，系數矩陣中每行每列都有了經第一步變換后，系數矩陣中每行每列都有了0 0元素，但需找出元素，但需找出n n個獨立的個獨立的0 0元素。若能找出，就以元素。若能找出，就以這些獨立這些獨立0 0元素對應解矩陣元

28、素對應解矩陣(x(xijij) )中元素為中元素為1 1，其余為，其余為0 0。這就得到最優解。這就得到最優解。 當當n n較小時，可用較小時，可用觀察法、試探法觀察法、試探法去找出去找出n n個獨個獨立立0 0元素。若元素。若n n較大時，就必須按一定的步驟去找。較大時，就必須按一定的步驟去找。五. 指派問題74試指派步驟試指派步驟：（1 1）從只有一個）從只有一個0 0元素的行（列）開始，給這個元素的行（列）開始，給這個0 0元素元素加圈，記作：加圈，記作：。這表示對這行所代表的人，只這表示對這行所代表的人，只有一種任務可指派，或這列所代表的任務，只有有一種任務可指派，或這列所代表的任務，

29、只有一人可指派一人可指派。然后劃去。然后劃去所在列（行）的其他所在列（行）的其他0 0元元素，記作：素，記作：。這表示這列所代表的任務已指派這表示這列所代表的任務已指派完，或這行所代表的人已指派完，或這行所代表的人已指派。（2 2）給只有一個）給只有一個0 0元素的列（行）的元素的列（行）的0 0元素加圈，記作：元素加圈，記作：，然后劃去，然后劃去所行（列）的所行（列）的0 0元素，記作：元素，記作： 。（3 3）重復（）重復（1 1）（）（2 2）步驟，直到所有）步驟，直到所有0 0元素都被圈出和元素都被圈出和劃掉。劃掉。五. 指派問題75例：有一份中文說明書，要譯成英、日、德、俄四種文字，

30、例：有一份中文說明書，要譯成英、日、德、俄四種文字，記作記作E、J、G、R。現有甲、乙、丙、丁四人。他們將中文。現有甲、乙、丙、丁四人。他們將中文說明書譯成不同語種的說明書所需時間如表所示。問應指說明書譯成不同語種的說明書所需時間如表所示。問應指派每人去完成何工作，使所需總時間最少？派每人去完成何工作，使所需總時間最少？五. 指派問題76解：將系數矩陣進行變換解：將系數矩陣進行變換 min01311221513426010111041415 405749141613 9014278119742 minijc01370606905320100ijb按步驟進行指派，得到：按步驟進行指派，得到： 1

31、376695321五. 指派問題77可見找到了4個獨立的0元素，所以得最優解為： 0001010010000010ijx 這表示：指定甲譯出俄文，乙譯出日文，丙譯出英文，丁譯出德文所需總時間最少minz = cijxij= 4 + 4 + 9 + 11 = 28 (小時小時) i j五. 指派問題78（4 4） 若仍有沒有加圈的若仍有沒有加圈的0 0元素，且同行（列）的元素，且同行（列）的0 0元素至少元素至少有兩個（表示對這人可以從兩項任務中指派其一），這可用有兩個（表示對這人可以從兩項任務中指派其一），這可用不同的方案去試探。不同的方案去試探。 從剩有從剩有0 0元素的最少行（列）開始，比

32、較這行（列）各元素的最少行（列）開始，比較這行（列）各0 0元素所在列（行）中元素所在列（行）中0 0元素的數目，選擇元素的數目，選擇0 0元素少的那列（行）元素少的那列（行）的這個的這個0 0元素加圈（表示選擇性多的要元素加圈（表示選擇性多的要“禮讓禮讓”選擇性小選擇性小的。），然后劃掉同行同列的其它的。），然后劃掉同行同列的其它0 0元素。元素。 可以反復進行。直到所有的可以反復進行。直到所有的0 0元素都已圈出和劃掉為止。元素都已圈出和劃掉為止。五. 指派問題79（5 5）若）若元素的數目元素的數目m m等于矩陣的階數等于矩陣的階數 n n，則，則這指派問題的最優解已得到。這指派問題的最

33、優解已得到。 若若 m nm n，則轉入下一步，進一步處理。，則轉入下一步，進一步處理。五. 指派問題80例：求下表所示效率矩陣的指派問題的最小解。五. 指派問題81min12797975020289666623000717121497010572151466106980044107109406365解：將系數矩陣進行變換 五. 指派問題82按步驟進行試指派，得矩陣 ： 52223105729846365這里的的個數m=4，而n=5；故解題沒有完成，應按以下步驟繼續進行。五. 指派問題83五. 指派問題第三步：第三步：作最少的直線覆蓋所有作最少的直線覆蓋所有0 0元素。（元素。（以確定該以確定

34、該系數矩陣中能找到最多的獨立系數矩陣中能找到最多的獨立0 0元素個數元素個數）。）。84五. 指派問題 定理定理2 2 矩陣中覆蓋矩陣中覆蓋0 0元素的最少直元素的最少直線數，等于位于不同行且不同列的線數，等于位于不同行且不同列的0 0元素元素最大個數。最大個數。85五. 指派問題第三步：第三步：作最少的直線覆蓋所有作最少的直線覆蓋所有0 0元素。（元素。（以確定該以確定該系數矩陣中能找到最多的獨立系數矩陣中能找到最多的獨立0 0元素個數元素個數）。）。為此按以下步驟進行：為此按以下步驟進行：（1 1）對沒有）對沒有的行打的行打號；號；（2 2）對已打）對已打號的行中所含號的行中所含 元素的列

35、打元素的列打號；號；（3 3）再對打有）再對打有號的列中所含號的列中所含元素的行打元素的行打號；號；（4 4）重復）重復(2)(3)(2)(3)直到不能得到新打直到不能得到新打行、列為止；行、列為止；（5 5）對沒有打對沒有打號的行劃一橫線，有打號的行劃一橫線，有打號的列劃號的列劃一縱線。一縱線。86這就得到了覆蓋所有0元素的最少直線數，設為l。若ln 說明必須再變換當前的系數矩陣，才能找到 n 個獨立的0元素，為此轉第四步。若l = n而 m n 應回到第二步（4），另行試探。（說明還能找到更多的獨立0元素）。五. 指派問題87對上例的矩陣按以上次序進行。五. 指派問題可知 l=4n=5，所以對矩陣進行變換，轉第四步。88第四步：第四步：對矩陣對矩陣進行變換，目的是增加進行變換，目的是增加0 0元素。元素。 （1 1）在沒有被直線覆蓋的部分中找出最小元素；）在沒有被直線覆蓋的部分中找出最小元素； （2 2）打）打的行中各元素都減去這最小元素；的行中各元素都減去這最小元素； （3 3）打）打的列中各元素都加上這最小元素的列中各元素都加上這最小元素 這樣在保證原來這樣在保證原來0 0元素不變的情況下