【正文】 分配問題的匈牙利解法 某工廠訂購了三臺機器（ A,B,C），有四各位置可供機器安裝（位置一，二，三，四），但 B機器不能安裝在第二號位置。 分配問題的匈牙利解法 系數(shù)矩陣不是方陣 在實際問題中，往往遇到有些任務沒有人去做，或某些人沒有分配到任務的情況。 分配問題的匈牙利解法 最大值問題 匈牙利法實質(zhì)上一種求最小值的方法，如果給我們的是系數(shù)矩陣， a ij表示 的是第 i 個人員完成第 j 項任務的收益，則要求我們?nèi)绾畏峙淠橙送瓿赡稠椚蝿?，使總收益最大? 第三步 增加系數(shù)矩陣中的 0元素： 1. 找最少直線覆蓋效率矩陣中的所有 0元素 （ 1）對沒有 0*行的行打 ?， （ 2）對打 ?的行上所有有 0元素的列打 ?， （ 3）對打 ?列的上所有有 0*元素的行打 ?， （ 4）重復（ 2）（ 3）步，到過程結(jié)束 （ 5）對沒有打 ?的行畫橫線，所有打 ?的列畫垂線，找到了覆蓋所有 0元素的最少直線?，F(xiàn)有甲 , 乙 , 丙 , 丁四人，他們將中文說明書翻譯成不同語種的說明書所需的時間有表 3. 7 給出，問應分配何人去完成何工作，使所需時間最少？ 表 3 . 7 任務 人員 E J G R 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 ??????????????9118713161491514410413152分配問題的匈牙利解法 79429118713161491514410413152??????????????????2424104750111006211130??????????????????????????????001023509606017130? ? ??????????????0010235096*06017130????????????????001235*096*0601713?????????????????*01235*096*001713???????????????*23096*017 分配問題的匈牙利解法 ??????????????541100032450115280分配問題的匈牙利解法 第一步：給系數(shù)矩陣“制造” 0元素： ； 2. 從系數(shù)矩陣的每列元素減去該列的最小元素。甲、乙、丙、丁四名隊員各自游什么姿勢，才最有可能取得好成績？ 成績 自由泳 蛙 泳 蝶 泳 仰 泳 甲 56 ? 74 ? 61 ? 63 ? 乙 63 ? 69 ? 65 ? 71 ? 丙 57 ? 77 ? 63 ? 67 ? 丁 55 ? 76 ? 62 ? 62 ? 甲 —— 蝶泳 乙 —— 蛙泳 丙 —— 自由泳 丁 —— 仰泳 甲 —— 蛙泳 乙 —— 自由泳 丙 —— 蝶泳 丁 —— 仰泳 分配問題的匈牙利解法 例 3 . 10 有一份中文說明書，需譯成英，日，德，俄四種文字。甲、乙、丙、丁四名隊員各自游什么姿勢，才最有可能取得好成績？ 成績 自由泳 蛙 泳 蝶 泳 仰 泳 甲 56 ? 74 ? 61 ? 63 ? 乙 63 ? 69 ? 65 ? 71 ? 丙 57 ? 77 ? 63 ? 67 ? 丁 55 ? 76 ? 62 ? 62 ? 解：設????種姿勢個人不游第第種姿勢個人游第第jijixij01 ?????????????????????????????????????????????????????????????????4321101111111162627655676377577165696363617456443424144333231342322212413121114443424134333231242322211413121144434241343332312423222114131211，或 jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xxxxxxxxxxxxxxxxfmi nij 匹 配 某游泳隊擬選用甲、乙、丙、丁四名游泳運動員組成一個 4 ? 100 米混合接力隊，參加今年的錦標賽。 如何確定符合要求的出場陣容？ 解：設 ????? 82101,jjjx ?否則號球員出場第???????????????????????????????????????821105121178180183185186188190192187654321626418762187654321,j,xxxxxxxxxxxxxxxxxxx. xj? 求解： 1 、 3 、 4 、 5 號和 7 號隊員，平均身高 6 米 第四節(jié) 分配問題 一、 分配問題 二、匈牙利方法 分配問題 設：????否則項任務個人員去完成第表示分配第01 jix ij m in z = ? ?? ?ninjijij xa1 1 s . t . ??niijx1= 1 ， j = 1, 2 , . . . , n ??njijx1= 1 ， i = 1, 2 , . . . , n x i j = 1 或 0 分配問題 基 本 概 念 解矩陣 系數(shù)矩陣 匹配 獨立 0元素 系數(shù)矩陣的定義與性質(zhì) 某游泳隊擬選用甲、乙、丙、丁四名游泳運動員組成一個 4 ? 10 0 米混合接力隊，參加今年的錦標賽。 第三節(jié) 0—1規(guī)劃 某公司準備投資 100 萬元在甲、乙兩座城市修建健身中心，經(jīng)過多方考察，最后選定 A 1 , A 2 , A 3 , A 4 和 A 5 五個位置，并且決定在甲城市的 A 1 、 A 2 、 A 3 三個位置中最多投建兩個；在乙城市的 A 4 、 A 5 兩個位置中最少投建一個。他們的 100 米自由泳、蛙泳、蝶泳、仰泳的成績?nèi)绫硭尽? 第三步：檢驗調(diào)運方案是否是最優(yōu)方案； 如果已經(jīng)是最優(yōu)，則算法結(jié)束，問題已經(jīng)解決； 如果還不是最優(yōu)，則進入第四步； 第四步：調(diào)整非最優(yōu)的調(diào)運方案，獲得更好的調(diào)運方案，也就是進行換基迭代； ? 改進調(diào)運方案，一般采用 閉回路調(diào)整法 。本書主要介紹最常用的前兩種方法。如設備 B必要時可以加班，當然不希望加班； 設備 A既要充分利用，又盡可能不加班； 企業(yè)決策者認識到不考慮附加條件，才使利潤指標達到 14。各產(chǎn)品占用資源數(shù)據(jù)，資源擁有數(shù)及產(chǎn)品利潤（見表 1. 54 ）。 數(shù)學模型為?????????????????2,102406180221002..m a x21212121jxxxxxxxtsxxfj 其解的最優(yōu)基對應的單純形表為（見表 1 .56 ） B x 1 x 2 x 3 x 4 x 5 b 1 1 0 3/ 2 0 1/ 2 30 4 0 0 2/ 5 1 1/ 2 50 2 0 1 1/ 4 0 1/ 4 35 C 0 0 3/ 4 0 1/ 4 135 靈敏度分析（ 1） 一、 約束條件右邊常數(shù) b 的靈敏度分析 二、 目標函數(shù)變量系數(shù) c 的靈敏度分析 ( 1) 非基變量系數(shù)的靈敏度分析 ( 2) 基變量系數(shù)的靈敏度分析 靈敏度分析（ 2） 單位產(chǎn)品 產(chǎn)品 消耗工時 工序 A B C 有效工時 （小時） 零件加工（小時 / 件） 1. 0 1. 2 1. 4 4800 電 鍍（小時 / 件） 0. 5 0. 6 0. 6 1800 裝 配（小時 / 件） 0. 7 0. 7 0. 8 2400 利 潤（元 / 件） 12 15 8 解：設 x1, x2, x3 設分別表示產(chǎn)品 A , B , C 一周的計劃生產(chǎn)件數(shù)。 影子價格（ 2） 例 某工廠生產(chǎn) A , B , C 三種產(chǎn)品，每種產(chǎn)品都同時需要兩種原料，數(shù)據(jù)見表 1 . 53 表 1 . 53 原料 產(chǎn)品 A 產(chǎn)品 B 產(chǎn)品 C 現(xiàn)有原料（噸） 原料甲 2 1 2 7 原料乙 1 3 2 11 利潤（萬元） 2 3 1 解：設 x1, x2, x3分別表示計劃生產(chǎn) A , B , C 產(chǎn)品的產(chǎn)量（噸） 數(shù)學模型為 ???????????????0,1123722..32m a x321321321321xxxxxxxxxtsxxxs 引進松弛變量 x4, x5化成標準型： ?????????????????0,1123722..32m a x5432153214321321xxxxxxxxxxxxxtsxxxs 影子價格（ 3） 該問題的最優(yōu)基對應的單純形表見表 x B x 1 x