【文章內容簡介】 4 x2+x1≤3 4x1+x3≤6 x1， x2 ， x3=0或 1 第 3節(jié) 01型整數(shù)規(guī)劃 例 9： min z =2x1+5x2+3x3+4x4 4x1+x2+x3+x4≥0 2x1+4x2+2x3+4x4≥4 x1+x2x3+x4≥1 x1， x2， x3， x4=0或 1 第 3節(jié) 01型整數(shù)規(guī)劃 例 9： 解： min z = 5x2+4x4+3x3+2x1 x2+x4 +x3 4x1≥0 4x2+4x4+2x32x1≥4 x2+x4x3+x1≥1 x1， x2， x3， x4=0或 1 第 3節(jié) 01型整數(shù)規(guī)劃 ?小結 采用部分枚舉法求解 01型整數(shù)規(guī)劃，可以減少計算次數(shù)，使最優(yōu)解能較快地被發(fā)現(xiàn) 第 4節(jié) 指派問題 一、指派問題的標準形式 ? 含義：將 n項工作交給 n個人去做，由于每個人做每一項工作所用的時間等成本不同，指派問題的目標是如何安排工作，使總的時間等成本最小。 ? 標準形式：有 n個人和 n件事，已知第 i人做第 j事的費用為 cij(i,j=1,2,…,n)，要求確定人和事之間的一一對應的指派方案，使完成這 n件事的總費用最少。 ? 基本要求：在滿足特定的指派要求條件下，使指派方案的總體效果最佳。 第 4節(jié) 指派問題 二、指派問題的假設條件 ?執(zhí)行工作的人數(shù)和要完成的工作數(shù)量是相同的 ?每個人只能做一件工作 ?每件工作只能由一個人來完成 ?第 i(i=1,2,…,n)個人完成第j(j=1,2,…,n)項工作所需的成本是 cij ?目標是如何分配工作，使總的成本最小 第 4節(jié) 指派問題 例 10：有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作 E、 J、 G、 R?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種的說明書所需時間如下表所示。問應指派何人去完成何工作，使所需總時間最少。 任務 人員 E J G R 甲 乙 丙 丁 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 第 4節(jié) 指派問題 例 10： 解： 10ijijxij?? ??， 指 派 第 人 去 完 成 第 項 工 作設， 不 指 派 第 人 去 完 成 第 項 工 作1 1 1 2 4 3 4 44141m in 2 15 11 91 1 2 3 41 1 2 3 40 1 1 2 3 4ijjijijz x x x xxixjx i j??? ? ? ? ?????????? ?????（ = ， ， ， ）（ = ， ， ， ）或 （ ， = ， ， ， ）第 4節(jié) 指派問題 三、指派問題的數(shù)學模型 ?系數(shù)矩陣 ： C=(cij)n n （ 1）矩陣 C表示費用、成本、時間等 （ 2） 元素 cij表示指派第 i人去完成第 j項任務時的費用 （ 或時間 、 成本等 ） 第 4節(jié) 指派問題 ?數(shù)學模型 111110m in1 ( 1 2 )1 ( 1 2 )0 1 ( 1 2 )ijijnnij ijijnijjnijiijxijxijz c xx i nx j nx i j n?????? ?????????????? ????????引 入 決 策 變 量 ：， 指 派 第 人 做 第 項 工 作， 不 指 派 第 人 做 第 項 工 作數(shù) 學 模 型 ：， ， ， ， ，或 ， ， ， ，第 4節(jié) 指派問題 ?解矩陣 ： X=(xij)n n （ 1）矩陣每行各元素中都有且只有一個 1，表示每個人必做且只做一件事 （ 2）矩陣每列各元素中都有且只有一個 1，表示每件事必有且只有一個人去做 （ 3）有 n!個可行解 第 4節(jié) 指派問題 ?數(shù)學模型的特點 （ 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ōu)解 第 4節(jié) 指派問題 ?匈牙利法的解題步驟 變換系數(shù)矩陣 。 具體做法： 1）從系數(shù)矩陣的每行元素減去該行的最小元素。 2）再從所得的系數(shù)矩陣的每列元素減去該列的最小元素。 變換后，指派問題的系數(shù)矩陣中每行及每列都出現(xiàn) 0元素，同時不出現(xiàn)負元素，得新的系數(shù)矩陣。 第 4節(jié) 指派問題 在變換后的系數(shù)矩陣中確定獨立 0元素。 具體做法： 1）從只有 1個 0元素的行開始，給這個 0元素加圈，記作◎，然后劃去◎所在列的其它 0元素，記作 Φ。 2）給只有 1個 0元素的列的 0元素加圈，記作◎，然后劃去◎所在行的其它 0元素，記作 Φ。 3）重復 1～ 2，直到所有 0元素都被圈出或劃掉為止，◎元素即為獨立 0元素。 4）若◎元素有 n個，則已得最優(yōu)解；若◎元素少于 n，則轉入 3。 最優(yōu)解矩陣：獨立 0元素對應位置上的元素為 1，其他元素為 0。 第 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元素。 具體作法： 1）對沒有◎元素的行打‘ √’號。 2）對已打‘ √’號的行中所有 Φ元素所在的列打‘ √’號。 3）再對打‘ √’號的列中所有◎元素所在的行打‘ √’號。 4）重復 2～ 3，直到得不出新的打‘ √’號的行和列為止。 5）對沒有打‘ √’號的行劃一橫線，對已打‘ √’號的列劃一豎線，得到覆蓋所有 0元素的最少直線數(shù)。 6）若直線數(shù)少于 n，則轉入 4；若直線數(shù)等于 n，而◎元素少于 n，則回到 2，另行 試指派 。 矩陣中獨立 0元素的定理：系數(shù)矩陣中獨立 0元素的最多個數(shù)等于能覆蓋所有 0元素的最少直線數(shù)。 第 4節(jié) 指派問題 繼續(xù)變換系數(shù)矩陣。 具體作法： 1）在沒有被直線覆蓋的元素中找出最小元素。 2）打‘ √’號的行的各元素減去最小元素。 3）打‘ √’號的列的各元素加上最小元素。 4）得新的系數(shù)矩陣，重復 2，若找出 n個獨立 0元素，則得最優(yōu)解；否則返回 3，重復 3～ 4。 第 4節(jié) 指派問題 例 11：求下表所示系數(shù)矩陣的指派問題的最小解 。 任務 人員 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 1