指派問題的匈牙利解法_第1頁
指派問題的匈牙利解法_第2頁
指派問題的匈牙利解法_第3頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、指派問題的匈牙利解法1、 把各行元素分別減去本行元素的最小值；然后在此基礎上再把每列元素減去本列中的最小值。此時每行及每列中肯定都有0元素了。2、 確定獨立零元素，并作標記。（1）、首先逐行判斷是否有含有獨立0元素的行，如果有，則按行繼續處理；如沒有，則要逐列判斷是否有含有獨立0元素的列，若有，則按列繼續處理。若既沒有含有獨立0元素的行，也沒有含有獨立0元素的列，則仍然按行繼續處理。（2）在按行處理時，若某行有獨立0元素，把該0元素標記為a，把該0所在的列中的其余0元素標記為b；否則，暫時越過本行，處理后面的行。把所有含有獨立0元素的行處理完畢后，再回來處理含有2個以及2個以上的0元素的行：任

2、選一個0做a標記，再把該0所在行中的其余0元素及所在列中的其余0元素都標記為b。（3）在按列處理時，若某列有獨立0元素，把該0元素標記為a，把該0所在的行中的其余0元素標記為b；否則，暫時越過本列，處理后面的列。把所有含有獨立0元素的列處理完畢后，再回來處理含有2個以及2個以上的0元素的列：任選一個0做a標記，再把該0所在列中的其余0元素及所在行中的其余0元素都標記為b。（4）、重復上述過程，即得到獨立零元素（標記a的“0”）3、 若獨立零元素等于矩陣階數，則已經得到最優解，若小于矩陣階數，則繼續以下步驟：（1）、對沒有標記a的行作標記c（2）、在已作標記c的行中，對標記b所在列作標記c（3）、在已作標記c的列中，對標記a 所在的行作標記c（4）、對沒有標記c的行劃線，對有標記c的列劃線/ 4、 在未被直線覆蓋的所有元素中找出一個最小元素（Xmin），未被直線覆蓋的行（或列）中所有元素都減去這個數。（注：若未被直線覆蓋部分是行數列數，則是按行減，反之則按列）。 5、 這樣必然出現負元素，所以對負元素所在列（或行）中各元素都加上這一最小元素（Xmin）以消除負數。這樣，再返回步驟2，確定獨立零元素個數。重復上述操作，直到找出最優解。/特殊問題：1、 若人數和工作數不等，則用“0

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論