【正文】 試確定最優(yōu)分配方案，使完成任務(wù)的總時(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 二、有四個(gè)工人，要指派他們分別完成四項(xiàng)工作，每個(gè)人做各項(xiàng)工作所獲得的收益如下表所示，問(wèn)指派哪個(gè)人去完成哪項(xiàng)工作，可使總收益最大。又假設(shè) A必須保證分配一項(xiàng)任務(wù)， D因某種原因決定不同意承擔(dān)第 4項(xiàng)任務(wù)。求使總費(fèi)用最少的指派方案。 第 3節(jié) 指派問(wèn)題 例 17：對(duì)于 例 12的指派問(wèn)題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司 A4和 A5，而讓技術(shù)力量較強(qiáng)的建筑公司 A A2和 A3來(lái)承建。試確定最優(yōu)分配方案，使完成任務(wù)的總時(shí)間最少。 第 3節(jié) 指派問(wèn)題 例 15：分配甲、乙、丙、丁四個(gè)人去完成 A、 B、 C、D、 E五項(xiàng)任務(wù)。 第 3節(jié) 指派問(wèn)題 例 14：求下列系數(shù)矩陣的最小化指派問(wèn)題?？紤]各方面原因，規(guī)定每個(gè)工程隊(duì)只能包其中一項(xiàng)工程，由于各隊(duì)施工質(zhì)量和技術(shù)水平的差異，其承包后各隊(duì)的報(bào)酬不同，如下表所示。 第 3節(jié) 指派問(wèn)題 ?最大化指派問(wèn)題 設(shè)最大化指派問(wèn)題系數(shù)矩陣 C=(cij)n n，令矩陣 B=(bij)n n=(Mcij)n n，其中 M是足夠大的正數(shù)（通常選M=max{cij}），則以 B為系數(shù)矩陣的最小化指派問(wèn)題和以 C為系數(shù)矩陣的最大化指派問(wèn)題有相同最優(yōu)解。已知建筑公司 Ai(i=1,2, …,5)對(duì)新商店 Bj(j=1,2, …,5)的建造費(fèi)用的報(bào)價(jià)（萬(wàn)元）為cij(i,j=1,2, …,5) ，如下表所示。其最優(yōu)解為多重最優(yōu)解 （ 2）匈牙利法充分利用指派問(wèn)題的特殊性質(zhì)，有效地減少計(jì)算量 第 4節(jié) 指派問(wèn)題 例 12：某商業(yè)公司計(jì)劃開(kāi)辦五家新商店。 第 4節(jié) 指派問(wèn)題 例 11：求下表所示系數(shù)矩陣的指派問(wèn)題的最小解 。 3）打‘ √’號(hào)的列的各元素加上最小元素。 具體作法： 1）在沒(méi)有被直線(xiàn)覆蓋的元素中找出最小元素。 矩陣中獨(dú)立 0元素的定理：系數(shù)矩陣中獨(dú)立 0元素的最多個(gè)數(shù)等于能覆蓋所有 0元素的最少直線(xiàn)數(shù)。 5）對(duì)沒(méi)有打‘ √’號(hào)的行劃一橫線(xiàn)，對(duì)已打‘ √’號(hào)的列劃一豎線(xiàn)，得到覆蓋所有 0元素的最少直線(xiàn)數(shù)。 3）再對(duì)打‘ √’號(hào)的列中所有◎元素所在的行打‘ √’號(hào)。 具體作法： 1）對(duì)沒(méi)有◎元素的行打‘ √’號(hào)。 最優(yōu)解矩陣：獨(dú)立 0元素對(duì)應(yīng)位置上的元素為 1，其他元素為 0。 3）重復(fù) 1～ 2，直到所有 0元素都被圈出或劃掉為止，◎元素即為獨(dú)立 0元素。 具體做法： 1）從只有 1個(gè) 0元素的行開(kāi)始，給這個(gè) 0元素加圈，記作◎，然后劃去◎所在列的其它 0元素，記作 Φ。 變換后，指派問(wèn)題的系數(shù)矩陣中每行及每列都出現(xiàn) 0元素，同時(shí)不出現(xiàn)負(fù)元素，得新的系數(shù)矩陣。 具體做法： 1）從系數(shù)矩陣的每行元素減去該行的最小元素。問(wèn)應(yīng)指派何人去完成何工作，使所需總時(shí)間最少。 第 4節(jié) 指派問(wèn)題 二、指派問(wèn)題的假設(shè)條件 ?執(zhí)行工作的人數(shù)和要完成的工作數(shù)量是相同的 ?每個(gè)人只能做一件工作 ?每件工作只能由一個(gè)人來(lái)完成 ?第 i(i=1,2,…,n)個(gè)人完成第j(j=1,2,…,n)項(xiàng)工作所需的成本是 cij ?目標(biāo)是如何分配工作，使總的成本最小 第 4節(jié) 指派問(wèn)題 例 10：有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字，分別記作 E、 J、 G、 R。 ? 標(biāo)準(zhǔn)形式：有 n個(gè)人和 n件事，已知第 i人做第 j事的費(fèi)用為 cij(i,j=1,2,…,n)，要求確定人和事之間的一一對(duì)應(yīng)的指派方案，使完成這 n件事的總費(fèi)用最少。 第 3節(jié) 01型整數(shù)規(guī)劃 要求：用部分枚舉法求解下列 01型整數(shù)規(guī)劃。 第三，以第一個(gè)可行解計(jì)算得出的目標(biāo)函數(shù)值作為一個(gè)過(guò)濾條件，比較表中其它目標(biāo)函數(shù)值與該過(guò)濾條件：比它差的變量取值組合舍棄；比它好的變量取值組合保留，并檢驗(yàn)約束條件，同時(shí)以其計(jì)算得出的目標(biāo)函數(shù)值作為新的過(guò)濾條件替換上一個(gè)過(guò)濾條件。 Bj Ai B1 B2 B3 B4 生產(chǎn)能力 （ kt/年） A1 A2 A3 A4 2 9 3 4 8 3 5 7 7 6 1 2 4 5 2 5 400 600 200 200 需求量（ kt/年） 350 400 300 150 第 3節(jié) 01型整數(shù)規(guī)劃 例 7： 解： 341 2 3 410ij i jx A BijAyA???? ???設(shè) 為 由 運(yùn) 往 的 物 資 數(shù) 量（ ， ， ， ， ）， 若 建 工 廠(chǎng)設(shè)， 若 建 工 廠(chǎng)? ?? ?441111 21 31 4112 22 32 4213 23 33 4314 24 34 4411 12 13 1421 22 23 2431 32 33 3441 42 43 44m in 1200 1500 1350400300150400600200200 10ij ijijijz c x y yx x x xx x x xx x x xx x x xx x x xx x x xx x x x yx x x x yx??? ? ? ?????? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ? ????( 1 2 3 4)01ijy???????????????? ??， ， = ， ， ，或第 3節(jié) 01型整數(shù)規(guī)劃 三、 01型整數(shù)規(guī)劃的解法 完全枚舉法 ?定義：含有 n個(gè)變量，產(chǎn)生 2n個(gè)可能的變量組合（每一個(gè)組合即變量取值為 0或 1），比較目標(biāo)函數(shù)值確定最優(yōu)解 ?特點(diǎn)：適于變量個(gè)數(shù) n≤10的 01型整數(shù)規(guī)劃 第 3節(jié) 01型整數(shù)規(guī)劃 部分枚舉法 ?定義：只檢查 2n個(gè)可能的變量組合的一部分，確定問(wèn)題的最優(yōu)解 第 3節(jié) 01型整數(shù)規(guī)劃 ?解題思路 （ 1）某個(gè)變量組合不滿(mǎn)足其中一個(gè)約束條件時(shí)，就不必再去檢驗(yàn)其他約束條件是否可行 （ 2）確定一個(gè)可行解的目標(biāo)函數(shù)值：對(duì)于目標(biāo)函數(shù)值比它差的變量組合就不必再去檢驗(yàn)它的可行性；對(duì)于目標(biāo)函數(shù)值比它好的變量組合再去檢驗(yàn)它的可行性 第 3節(jié) 01型整數(shù)規(guī)劃 ?解題步驟 第一，按目標(biāo)函數(shù)中各變量系數(shù)的大小順序排列各變量，然后把約束條件做相應(yīng)的調(diào)整。工廠(chǎng) A3或 A4開(kāi)工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為 1200萬(wàn)元或 1500萬(wàn)元。這種物資的需求地有 B1， B2， B3， B4四個(gè)。由于該種物資供不應(yīng)求，故需要再建一家工廠(chǎng)。反之，則不一定；第二，項(xiàng)目 3和 4中至少選擇一個(gè)；第三，項(xiàng)目 5， 6和 7中恰好選擇兩個(gè)?？晒┻x擇的投資項(xiàng)目有 7個(gè)，項(xiàng)目 j所需投資額和預(yù)期收益分別為 aj和 cj(j=1,2,…,7)。 令 jA1( 1 2 )0jjjjjEAx j nEA???????， 若 選 擇， ， ， 若 選 擇第 3節(jié) 01型整數(shù)規(guī)劃