整數(shù)規(guī)劃教學(xué)課件ppt-資料下載頁
2025-01-20 06:42本頁面
【正文】 ” 選擇性少的 )。 然后劃掉同行同列的其它 0元素 。 可反復(fù)進(jìn)行 ，直到所有 0元素都已圈出和劃掉為止 。 （ 5）若 ◎ 元素的數(shù)目 m 等于矩陣的階數(shù) n，那么這指派問題的最優(yōu)解已得到。若 m n, 則轉(zhuǎn)入下一步。 第三步：作最少的直線覆蓋所有 0元素 。 (1)對沒有 ◎ 的行打 √號； (2)對已打 √號的行中所有含 216。元素的列打 √號； (3)再對打有 √號的列中含 ◎ 元素的行打 √號； (4)重復(fù) (2)， (3)直到得不出新的打 √號的行 、 列為止； (5)對沒有打 √號的行畫橫線 ， 有打 √號的列畫縱線 ，這就得到覆蓋所有 0元素的最少直線數(shù) l 。 l 應(yīng)等于 m，若不相等 ， 說明試指派過程有誤 ， 回到第二步 (4)， 另行試指派；若 l＝ m n， 須再變換當(dāng)前的系數(shù)矩陣 ，以找到 n個(gè)獨(dú)立的 0元素 ， 為此轉(zhuǎn)第四步 。 第四步：變換矩陣 (bij)以增加 0元素 。 在沒有被直線覆蓋的所有元素中找出最小元素，然后打 √各行都減去這最小元素；打 √各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。 例一： 任務(wù) 人員 A B C D 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 ????????????9118713161491514410413152????????????241047501110062111302 4 9 7 ????????????00102350960607130????????????241047501110062111304 2 ????????????00102350960607130◎ 216。 ◎ 216。 216。 ◎ ◎ ????????????0100000100101000 有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作 A、 B、 C、 D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？ 任務(wù) 人員 A B C D 甲 6 7 11 2 乙 4 5 9 8 丙 3 1 10 4 丁 5 9 8 2 例二、 求解過程如下： 第一步，變換系數(shù)矩陣： 2142 289541013895421176)(?????????????????ijc????????????0673390245100954????????????0173340240100454－ 5 第二步，試指派： ????????????17334241454 ◎ ◎ ◎ 216。 216。 找到 3 個(gè)獨(dú)立零元素 但 m = 3 n = 4 第三步，作最少的直線覆蓋所有 0元素： ????????????17334241454 ◎ ◎ ◎ 216。 216。 √ √ √ 獨(dú)立零元素的個(gè)數(shù) m等于最少直線數(shù) l，即 l＝ m=3n=4； 第四步，變換矩陣 (bij)以增加 0元素：沒有被直線覆蓋的所有元素中的最小元素為 1，然后打 √ 各行都減去 1；打 √ 各列都加上 1，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派： ????????????6244251343 0 0 0 0 0 0 ????????????0100001000011000得到 4個(gè)獨(dú)立零元素， 所以最優(yōu)解矩陣為： ????????????17334241454 ◎ ◎ ◎ 216。 216。 √ √ √ ????????????06244251343 ◎ ◎ ◎ 216。 216。 15 ????????????6244251343 ◎ ◎ ◎ 216。 216。 ◎ 練習(xí)： 11 5 7 6 4 戊 6 9 6 3 7 丁 8 6 4 5 8 丙 9 11 7 12 9 乙 11 8 9 5 7 甲 E D C B A 費(fèi) 工作 用 人員 4347511576469637964589117129118957?????????????????????????????????????71320363045202224052634021 2 ????????????????5032015304310140305242402????????????????5032015304310140305242402◎ 216。 ◎ ◎ ◎ 216。 216。 ????????????????5032015304310140305242402◎ 216。 ◎ ◎ ◎ 216。 216。 √ √ √ l =m=4 n=5 ????????????????5032015304310140305242402◎ 216。 ◎ ◎ ◎ 216。 216。 ????????????????5033004203310240306231301????????????????5033004203310240306231301◎ 216。 ◎ 216。 ◎ 216。 ◎ 216。 √ √ √ ????????????????5033004203310240306231301√ √ √ √ ????????????????5033004203310240306231301◎ 216。 ◎ 216。 ◎ 216。 ◎ 216。 √ √ √ √ √ √ √ l =m=4 n=5 ????????????????5033004203310240306231301◎ 216。 ◎ 216。 ◎ 216。 ◎ 216。 √ √ √ √ √ √ √ ????????????????6044003202300230206130300????????????????6044003202300230206130300????????????????6044003202300230206130300◎ 216。 216。 ◎ 216。 216。 ◎ 216。 ◎ 216。 ◎ 此問題有多個(gè)最優(yōu)解 28 ????????????????6044003202300230206130300◎ 216。 216。 ◎ 216。 216。 ◎ 216。 ◎ 216。 ◎ ????????????????6044003202300230206130300◎ 216。 216。 ◎ 216。 216。 ◎ 216。 ◎ 216。 ◎ 用匈牙利法求解下列指派問題，已知效率矩陣分別如下： 7 9 1 0 1 21 3 1 2 1 6 1 71 5 1 6 1 4 1 51 1 1 2 1 5 1 6????????????3 8 2 10 38 7 2 9 76 4 2 7 58 4 2 3 59 10 6 9 10??????????????
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1