【導讀】容量網(wǎng)絡(luò)的每邊另外賦值非負的單位。達到最小，特別是，如果給定總流量等于最大流，量平衡條件的，的總流量不大于，3）如果不滿足發(fā)點和收點的平衡條件，如何完成3）的任務(wù)？

　　

【正文】 或 為系數(shù)矩陣的指 派問題的最優(yōu)方案相同 nk ??1理由： A1C 2CC1C 2CCkkA? ? AxcxAcxcninjijijnjkjkjnkiinjijij ???? ? ??? ?? ???? ? 1 111 1? ? AxcxAcxcninjijijniikikninkjjijij ???? ? ??? ?? ????? 1 111 1目標函數(shù)差一個常數(shù)，約束相同，最優(yōu)解也相同 標準指派問題的第二個有用的性質(zhì) 如果 的所有元素中沒有負數(shù)，且存在 個行列號都互不相同的零元素（簡稱為獨立零元 素），那么對應的標準指派問題的最優(yōu)目標值等 于零，最優(yōu)方案可以由獨立零元素的位置確定 ?????????????????04321405010121026600811031C例如 最優(yōu)解 15544312213 ????? xxxxxnnnRC ??算法設(shè)想（匈牙利算法） 一、利用第一個性質(zhì)產(chǎn)生獨立零元素 二、對給定矩陣找到最大的獨立零元素組 三、當最大的獨立零元素組的零元素數(shù)目不夠 時增加獨立零元素的數(shù)目 通過以上步驟的迭代找到足夠的獨立零元素 ?????????????????61012961061476781296101417971215784C例 一、順序?qū)γ啃忻苛袦p去最小值產(chǎn)生零元素 C ???????????????????????????????????043204050012320377108110300463040810126303710208113401 ） 用紅圈標出一些某行或某列僅有的零元素，再 通過行列交換把這些零換到左上角（后者非必須） 行交換 ????????????????????04320405001232037710811030二、對給定矩陣找到最大數(shù)目的獨立零元素組 ????????????????????20203103772020300405308110????????????????????20203004052020310377308110? ?列交換 ????????????????????202031037720203004053081102 ） 在沒有紅圈的右下角如果有 零，一定是新的獨立零元素 3 ） 用直線覆蓋紅圈所在行 ????????????????????202031037720203004053081104 ） 在直線未覆蓋處找零，如果沒有零停止，否則 會出現(xiàn)以下兩種情況，其中黑實圈圈住的是新零 ????????????????????20203003772020300405308110????????????????????20203103772020300405308110情況二 情況一 ????????????????????20203003772020300405308110????????????????????20203103772020300405308110????????????????????20203003772020300405308110????????????????????20203103772020300405308110兩種情況的處理方法 ??????????????????10210403211180310450162600????????????????10210403211180310450162600前面第一種情況后可能發(fā)生的另外一種情況 例 ????????????????10210403211180310450162600????????????????10210403211180310450162600未覆蓋的黑圈所在列的紅圈所在 行存在沒有列直線覆蓋的零，和 前面的第二種情況一樣，但是該 黑圈所在行有紅圈，不能將該零 選為獨立零元素 此時要覆蓋剩下的零必須加直線 這種情況也一定能夠增加獨立零元素 ????????????????10210403211180310450162600?????????????????10210403211180310450162600理由：新選零未被行直線覆蓋，而該行有紅圈，紅 圈一定被列直線覆蓋，其所在列一定有黑圈（記為 A），如果 A 所在行沒有紅圈，即可按上面圖型顯 示的方法增加一個獨立零元素，如果 A 所在行有紅 圈（記為 B ）， B 一定被列直線覆蓋，其所在列一 定有黑圈（記為 C ），如果 C 所在行沒有紅圈，可 按上述方法增加獨立零元素，否則可繼續(xù)追蹤，一 定可找到所在行沒有紅圈的黑圈，增加獨立零元素 實用性考慮：第一、把所有紅圈交換到左上角沒有 必要；第二、同一副圖上不好刪除直線，可用對列 打勾表示該列有直線覆蓋，用對行打勾表示該行沒 有直線覆蓋。由此形成下面的算法 ????????????????04320405001232037710811030√ √ √ ????????????????04320405001232037710811030√ ????????????????04320405001232037710811030關(guān)于前面描述的迭代算法有以下事實： 1）每次迭代至少增加一個被圈住的零 2）所有紅圈圈住的一定是獨立零元素組 3）直線的數(shù)目和紅圈的個數(shù)相同 上述第一個事實說明迭代算法有限步停止，第二個事實 說明算法能產(chǎn)生最大的獨立零元素組，第三個事實說明 算法產(chǎn)生的是能夠覆蓋所有零元素的數(shù)目最少的直線組 找出未覆蓋處最小的數(shù)，在 沒被行直線覆蓋的行減去最 小數(shù)，然后在有負數(shù)的列加 上這個最小數(shù) ??????????????????04320405000121126601811030????????????????04321405010121026600811031三、利用第一個性質(zhì)在直線未覆蓋處產(chǎn)生零元素 ? ?????????????????04320405001232037710811030繼續(xù)找最大的獨立零元素組 ????????????????04321405010121026600811031????????????????04321405010121026600811031????????????????04321405010121026600811031????????????????04321405010121026600811031出現(xiàn)前面討論過的第三種情況， 因此一定可以增加獨立零元素 最終獲得的獨立零元素組 獨立零元素數(shù)等于任務(wù)數(shù)，已得最優(yōu)解 ???????????????????04321405010121026600811031C?????????????????1000001000000010001000100*X非標準形式指派問題如何轉(zhuǎn)換成標準問題 1）目標函數(shù)求最大 ? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???????????????????????ninjijijninjijijninjijninjijijninjijijxcAxcxAxAxc1 11 11 11 11 1minminminm a x取 ，令 ，得標準問題 ? ?? ??ninjijcA1 1? ? nnijcAC ????2）人數(shù)和事情不等的問題 補充虛擬的人或事，費用系數(shù)取 0 3）一人可做幾件事的問題 將該人轉(zhuǎn)換成相同的幾個人接受指派，這些人 的費用系數(shù)完全相同 4）某事一定不能由某人做的問題 將相應費用取為充分大的正數(shù)