[工學(xué)]運(yùn)籌學(xué)整數(shù)規(guī)劃-資料下載頁(yè)
2024-10-13 21:23本頁(yè)面
【正文】 13 12 10000000000001 13ijc???????????????第 3節(jié) 指派問(wèn)題 轉(zhuǎn)化為求極小化問(wè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é) 指派問(wèn)題 多重最優(yōu)解（之一）為 z*=43 66000000000000000 0 0 1()0 0 1 00 1 0 0 0010100001ijx??????????????第 3節(jié) 指派問(wèn)題 ? 一個(gè)人可做幾件事的指派問(wèn)題 若某個(gè)人可做幾件事，則將該人化作相同的幾個(gè)“人”來(lái)接受指派，這幾個(gè)“人”做同一件事的費(fèi)用 cij相同。 第 3節(jié) 指派問(wèn)題 例 17：對(duì)于 例 12的指派問(wèn)題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司 A4和 A5，而讓技術(shù)力量較強(qiáng)的建筑公司 A A2和 A3來(lái)承建。根據(jù)實(shí)際情況，可以允許每家建筑公司承建一家或兩家商店。求使總費(fèi)用最少的指派方案。 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é) 指派問(wèn)題 例 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é) 指派問(wèn)題 轉(zhuǎn)化為平衡指派問(wè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é) 指派問(wèn)題 多重最優(yōu)解（之一）為 z*=35 6 6111 0 0 0 00 1 0 0 0()0000 0 0 0 0000000000000 1 001ijx?????????? ??????????第 3節(jié) 指派問(wèn)題 方法二 解：轉(zhuǎn)化為平衡指派問(wè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é) 指派問(wèn)題 多重最優(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é) 指派問(wèn)題 例 18：從 A、 B、 C、 D、 E等 5人中挑選 4人去完成 4項(xiàng)工作，已知每人完成各項(xiàng)工作的時(shí)間如下表所示，規(guī)定每項(xiàng)工作只能由其中一人單獨(dú)完成，而每個(gè)人最多只能承擔(dān)其中一項(xiàng)任務(wù)。又假設(shè) A必須保證分配一項(xiàng)任務(wù)， D因某種原因決定不同意承擔(dān)第 4項(xiàng)任務(wù)。在上述條件下，試問(wèn)如何分配工作，使完成這 4項(xiàng)任務(wù)所需的總時(shí)間為最少？ 人 任務(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é) 指派問(wèn)題 例 18： 解：轉(zhuǎn)化為平衡指派問(wèn)題，并將系數(shù)矩陣轉(zhuǎn)置 5 510 5 15 202 10 5 15() 3 15 14 1315 2 79 4 150008 0ijMMc?????????????第 3節(jié) 指派問(wèn)題 最優(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ù)矩陣的指派問(wèn)題的最小解。 工作 工人 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 二、有四個(gè)工人，要指派他們分別完成四項(xiàng)工作，每個(gè)人做各項(xiàng)工作所獲得的收益如下表所示，問(wèn)指派哪個(gè)人去完成哪項(xiàng)工作，可使總收益最大。 工作 工人 A B C D 甲 乙 丙 丁 15 18 21 24 19 23 22 18 26 17 16 19 19 21 23 17 作業(yè) 14 三、根據(jù) 例 15所示表，若考慮其中有一人完成兩項(xiàng)，其他人每人完成一項(xiàng)。試確定最優(yōu)分配方案，使完成任務(wù)的總時(shí)間最少。 作業(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號(hào)-1