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