[工學(xué)]運籌學(xué)整數(shù)規(guī)劃-在線瀏覽
2024-11-30 21:23本頁面
【正文】 （ 3）有 n!個可行解 第 4節(jié) 指派問題 ?數(shù)學(xué)模型的特點 （ 1）特殊的 01型整數(shù)規(guī)劃問題 （ 2）特殊的運輸問題 第 4節(jié) 指派問題 四、指派問題的解題方法 — 匈牙利法 ? 解題思路 （ 1）若從指派問題的系數(shù)矩陣（ cij）的某行（或某列）各元素分別減去一個常數(shù) k，得到一個新的矩陣（ cij′），則以（ cij）和（cij′）為系數(shù)矩陣的兩個指派問題有相同的最優(yōu)解 （ 2）獨立 0元素：位于不同行不同列的 0元素 （ 3）若在系數(shù)矩陣中找到 n個獨立 0元素，則對應(yīng)的指派方案總費用（或時間、成本等）為零，即為原指派問題的最優(yōu)解 第 4節(jié) 指派問題 ?匈牙利法的解題步驟 變換系數(shù)矩陣 。 2）再從所得的系數(shù)矩陣的每列元素減去該列的最小元素。 第 4節(jié) 指派問題 在變換后的系數(shù)矩陣中確定獨立 0元素。 2）給只有 1個 0元素的列的 0元素加圈，記作◎，然后劃去◎所在行的其它 0元素，記作 Φ。 4）若◎元素有 n個，則已得最優(yōu)解；若◎元素少于 n，則轉(zhuǎn)入 3。 第 4節(jié) 指派問題 例 10： 解：最優(yōu)解為 z*=28 440 0 0 10 1 0 0()1 0 0 00 0 1 0ijx??????????????第 4節(jié) 指派問題 用最少的直線覆蓋所有 0元素，以確定該系數(shù)矩陣中能找出最多的獨立 0元素。 2）對已打‘ √’號的行中所有 Φ元素所在的列打‘ √’號。 4）重復(fù) 2～ 3，直到得不出新的打‘ √’號的行和列為止。 6）若直線數(shù)少于 n，則轉(zhuǎn)入 4；若直線數(shù)等于 n，而◎元素少于 n，則回到 2，另行 試指派 。 第 4節(jié) 指派問題 繼續(xù)變換系數(shù)矩陣。 2）打‘ √’號的行的各元素減去最小元素。 4）得新的系數(shù)矩陣，重復(fù) 2，若找出 n個獨立 0元素，則得最優(yōu)解；否則返回 3，重復(fù) 3～ 4。 任務(wù) 人員 A B C D E 甲 乙 丙 丁 戊 12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 9 第 4節(jié) 指派問題 例 11： 解：多重最優(yōu)解，為 z*=32 5 5 5 50 1 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0( ) ( )0 0 0 0 1 0 0110 0 10 0 0 0 0 0 0 01 0 0 0 011 0 0 010ij ijxx??? ? ? ?? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ?? ? ? ?或第 4節(jié) 指派問題 ? 小結(jié) （ 1）當(dāng)指派問題的系數(shù)矩陣經(jīng)過變換，遇到在所有的行和列中， 0元素都不止一個時，可任選其中一個 0元素加圈，并同時劃去同行和同列中其他 0元素。為了盡早建成營業(yè)，商業(yè)公司決定由 5家建筑公司分別承建。商業(yè)公司應(yīng)當(dāng)對 5家建筑公司怎樣分配建造任務(wù)，才能使總的建造費用最少？ Bj Ai B1 B2 B3 B4 B5 A1 A2 A3 A4 A5 4 8 7 15 12 7 9 17 14 10 6 9 12 8 7 6 7 14 6 10 6 9 12 10 6 第 4節(jié) 指派問題 例 12： 解：最優(yōu)解為 z*=34 550 0 1 0 00 1 0 0 0() 1 0 0 0 00 0 0 1 00 0 0 0 1ijx????????????????第 3節(jié) 指派問題 五、非標(biāo)準形式的指派問題 處理方法：將非標(biāo)準形式轉(zhuǎn)化為標(biāo)準形式，然后應(yīng)用匈牙利法求解。 第 3節(jié) 指派問題 例 13：某建筑公司所屬五個工程隊，現(xiàn)有五項工程需要該公司承包。試問如何分配任務(wù)，使得該建筑公司獲得最好的經(jīng)濟效益？ 項目 施工隊 A B C D E Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ 17 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10 4 10 7 10 6 第 3節(jié) 指派問題 例 13： 解：轉(zhuǎn)化為求極小化問題，系數(shù)矩陣為 550 10 8 10 89 8 11 11 11() 10 0 5 3 52 3 11 11 713 7 10 7 11ijc?????????????第 3節(jié) 指派問題 最優(yōu)解為 z*=60 551 0 0 0 00 0 1 0 0() 0 1 0 0 00 0 0 0 10 0 0 1 0ijx????????????????第 3節(jié) 指派問題 ?人數(shù)和事數(shù)不等的指派問題 若人少事多，則添上一些虛擬的“人”，虛擬的“人”做各事的費用 cij取“ 0”，表示這些費用實際上不會發(fā)生；若人多事少，則添上一些虛擬的“事”，虛擬的“事”被各人做的費用cij仍取“ 0”。 1 0 1 1 4 2 87 1 1 1 0 1 4 1 25 6 9 1 2 1 41 3 1 5 1 1 1 0 7????????第 3節(jié) 指派問題 例 14： 解：轉(zhuǎn)化為平衡指派問題，系數(shù)矩陣為 5 510 11 4 2 87 11 10 14 12() 5 6 9 12 10 0 0 0 0413 15 11 10 7ijc?????????????第 3節(jié) 指派問題 最優(yōu)解為 z*=22 5 50 0 0 1 01 0 0 0 0() 0 1 0 0 00 0 0 0 100100ijx????????????????第 3節(jié) 指派問題 ? 某事一定不能由某人做的指派問題 若某事一定不能由某個人做，則將相應(yīng)的費用 cij取“ M”（ M是足夠大的正數(shù)）。每個人完成各項任務(wù)的時間如下表所示，由于任務(wù)數(shù)多于人數(shù)，故考慮任務(wù) E必須完成，其他 4項中可任選 3項完成。 項目 人 A B C D E 甲 乙 丙 丁 25 29 31 42 37 39 38 26 20 33 34 27 28 40 32 24 42 36 23 45 第 3節(jié) 指派問題 例 15： 解：轉(zhuǎn)化為平衡指派問題，系數(shù)矩陣為 5 525 29 31 42 3739 38 26 20 33() 34 27 280040 3224 42 36 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1