理學整數(shù)規(guī)劃ppt課件-資料下載頁
2025-01-19 22:48本頁面
【正文】 匈牙利法的步驟 是否找到最優(yōu)指派 ????????????????6101296106147678129610141797121578435 34 “ 0”的直線 0 3 0 11 8 0 1 7 7 3 0 2 3 2 1 0 0 5 0 4 1 2 3 4 0 （ 1）行或列中只有一個“ 0”的元，作標記，如果其所在列或行有其它“ 0”的，則劃去 。 （ 2）如此反復直到所有行的 “0”被直線覆蓋 匈牙利法的步驟 （ 1）對所有不含 0元素的行打 √ √ √ 匈牙利法的步驟 √ （ 2）對已打 √的行中所有含 0元素的列打 √ （ 3）在對已打 √的列中含 0元素的行打 √ 直到無法打 √為止 , “ 0”的直線 0 3 ◎ 11 8 ◎ 1 7 7 3 0 2 3 2 1 0 ◎ 5 0 4 1 2 3 4 ◎ 匈牙利法的步驟 √ √ √ （ 4）沒打 √的行畫直線， 對打 √的列畫直線 , “ 0”的直線 0 3 ◎ 11 8 ◎ 1 7 7 3 0 2 3 2 1 0 ◎ 5 0 4 1 2 3 4 ◎ 0 3 ◎ 11 8 ◎ 1 7 7 3 0 2 3 2 1 0 ◎ 5 0 4 1 2 3 4 ◎ （ 1）未被覆蓋的元素中減去最小元素，出現(xiàn)新的 0元素 √ √ √ 匈牙利法的步驟 （ 2）打 √列中各元素都加上最小元素。 0 6 6 21 2 1 01?1?112其余元素不變 0 1 3 ◎ 11 8 ◎ 0 6 6 2 0 1 2 1 0 1 ◎ 5 0 4 1 2 3 4 ◎ （ 1）未被覆蓋的元素中減去最小元素，出現(xiàn)新的 0元素 √ √ √ 匈牙利法的步驟 （ 2）打 √列中各元素都加上最小元素。 其余元素不變 1 3 ◎ 11 8 ◎ 0 6 6 2 0 1 2 1 0 1 ◎ 5 0 4 2 2 3 4 ◎ （ 1）未被覆蓋的元素中減去最小元素，出現(xiàn)新的 0元素 （ 2）打 √列中各元素都加上最小元素。 其余元素不變 匈牙利法的步驟 0元素 1 3 0 11 8 0 0 6 6 2 0 1 2 1 0 1 0 5 0 4 2 2 3 4 0 匈牙利法的步驟 ◎ ◎ φ ◎ φ ◎ ◎ φ 匈牙利法的步驟 1 3 ◎ 11 8 φ◎ 6 6 2 ◎ 1 2 1 φ 1 φ 5 ◎ 4 2 2 3 4 ◎ 0元素 獨立的 0元素個數(shù)=矩陣的階數(shù) =5 X=(xij )n n= 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 分配矩陣： 第一項任務分配給第三個人做 第二項任務分配給第二個人做 第三項任務分配給第一個人做 第四項任務分配給第四個人做 第五項任務分配給第五個人做 （ 用最大元素 所有元素化成最小化問題 ） 四、一般的指派問題
教學課件相關推薦
鄂ICP備17016276號-1