[工學(xué)]運籌學(xué)整數(shù)規(guī)劃-資料下載頁
2024-10-13 21:23本頁面
【正文】 13 12 10000000000001 13ijc???????????????第 3節(jié) 指派問題 轉(zhuǎn)化為求極小化問題，系數(shù)矩陣為 661 0 8 9 8 1 3 1 37 6 7 5 1 3 1 35 4 5 3 1 3 1 3()3 3 4 2 1 3 1 31 2 3 1 1 3 1 30 1 2 0 1 3 1 3ijc???????????????第 3節(jié) 指派問題 多重最優(yōu)解（之一）為 z*=43 66000000000000000 0 0 1()0 0 1 00 1 0 0 0010100001ijx??????????????第 3節(jié) 指派問題 ? 一個人可做幾件事的指派問題 若某個人可做幾件事，則將該人化作相同的幾個“人”來接受指派，這幾個“人”做同一件事的費用 cij相同。 第 3節(jié) 指派問題 例 17：對于 例 12的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司 A4和 A5，而讓技術(shù)力量較強的建筑公司 A A2和 A3來承建。根據(jù)實際情況，可以允許每家建筑公司承建一家或兩家商店。求使總費用最少的指派方案。 Bj Ai B1 B2 B3 B4 B5 A1 A2 A3 4 8 7 15 12 7 9 17 14 10 6 9 12 8 7 第 3節(jié) 指派問題 例 17：方法一 解：系數(shù)矩陣轉(zhuǎn)化為 6 54 8 7 15 127 9 17 14 8 7 15 127 9 17 14 10()6 9 124 106 9 12 8 787ijc??????????? ??????????第 3節(jié) 指派問題 轉(zhuǎn)化為平衡指派問題，系數(shù)矩陣為 6 64 8 7 1 5 1 27 9 1 7 14 8 7 1 5 1 27 9 1 7 1 4 1 0()6 9 14 1 06 9 1 2 8 7002 8 70000ijc???????????????第 3節(jié) 指派問題 多重最優(yōu)解（之一）為 z*=35 6 6111 0 0 0 00 1 0 0 0()0000 0 0 0 0000000000000 1 001ijx?????????? ??????????第 3節(jié) 指派問題 方法二 解：轉(zhuǎn)化為平衡指派問題，系數(shù)矩陣為 5 54 8 7 1 5 1 27 9 1 7 1 4 1 0() 6 9 1 24 8 7 8 74 8 7 8 787ijc?????????????????第 3節(jié) 指派問題 多重最優(yōu)解（之一）為 z*=35 5 50 0 01 0 0 0 00 1 0 0 0()00 0 0 00 0 0 0 111ijx????????????????第 3節(jié) 指派問題 例 18：從 A、 B、 C、 D、 E等 5人中挑選 4人去完成 4項工作，已知每人完成各項工作的時間如下表所示，規(guī)定每項工作只能由其中一人單獨完成，而每個人最多只能承擔(dān)其中一項任務(wù)。又假設(shè) A必須保證分配一項任務(wù)， D因某種原因決定不同意承擔(dān)第 4項任務(wù)。在上述條件下，試問如何分配工作，使完成這 4項任務(wù)所需的總時間為最少？ 人 任務(wù) A B C D E Ⅰ Ⅱ Ⅲ Ⅳ 10 2 3 15 9 5 10 15 2 4 15 5 14 7 15 20 15 13 6 8 第 3節(jié) 指派問題 例 18： 解：轉(zhuǎn)化為平衡指派問題，并將系數(shù)矩陣轉(zhuǎn)置 5 510 5 15 202 10 5 15() 3 15 14 1315 2 79 4 150008 0ijMMc?????????????第 3節(jié) 指派問題 最優(yōu)解為 z*=21 550 1 0 00 0 1 0() 1 0 0 0000000 0 0 1 00 0 1ijx????????????????作業(yè) 14 作業(yè) 14： 一、求下列系數(shù)矩陣的指派問題的最小解。 工作 工人 A B C D 甲 乙 丙 丁 7 9 10 12 13 12 16 17 15 16 14 15 11 12 15 16 工作 工人 A B C D E 甲 乙 丙 丁 戊 3 8 2 10 3 8 7 2 9 7 6 4 2 7 5 8 4 2 3 5 9 10 6 9 10 作業(yè) 14 二、有四個工人，要指派他們分別完成四項工作，每個人做各項工作所獲得的收益如下表所示，問指派哪個人去完成哪項工作，可使總收益最大。 工作 工人 A B C D 甲 乙 丙 丁 15 18 21 24 19 23 22 18 26 17 16 19 19 21 23 17 作業(yè) 14 三、根據(jù) 例 15所示表，若考慮其中有一人完成兩項，其他人每人完成一項。試確定最優(yōu)分配方案，使完成任務(wù)的總時間最少。 作業(yè) 14答案 一、 0 0 1 00 1 0 0480 0 0 11 0 0 0z??????? ???????0 0 0 0 10 0 1 0 0210 1 0 0 00 0 0 1 01 0 0 0 0z????????? ?????????作業(yè) 14答案 二、 三、 0 0 0 10 1 0 0961 0 0 00 0 1 0z??????? ???????0 1 0 0 0 0 1 0 0 00 0 1 0 0 0 0 0 1 01310 0 0 0 1 0 0 0 0 11 0 0 0 0 1 0 0 0 00 0 0 1 0 0 0 1 0 0zB C D E A?? ? ? ?? ? ? ?? ? ? ?? ? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?多 重 解 或甲 完 成 ， 乙 完 成 和 ， 丙 完 成 ， 丁 完
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1