運(yùn)籌學(xué)lpilppt課件-資料下載頁(yè)

　　

【正文】 A 2 、 A 3 三個(gè)位置中最多投建兩個(gè)；在乙城市的 A 4 、 A 5 兩個(gè)位置中最少投建一個(gè)。如果已知各點(diǎn)的投資金額和年利潤(rùn)如下表 2 4 11 ： 表 2 4 11 待定地址 A 1 A 2 , A 3 A 4 A 5 投資 總額 投資金額 （萬(wàn)元） 20 30 25 40 45 100 年利潤(rùn)（萬(wàn)元） 10 25 20 25 30 問(wèn)：投建在哪些位置才會(huì)使總的年利潤(rùn)最大？ 解：設(shè)決策變量 ??????? 5432101,jjAjAjx投建健身中心不在投建健身中心在 54321101210035402530203025202510543215432154321 ,j,xxxxxxxxxxxs . t . xxxxx M a x fj???????????????????????? 求解模型 選擇在 A 3 , A 4 和 A 5 投建健身中心，年利潤(rùn) 75 萬(wàn)元 第三節(jié) 0—1規(guī)劃 在高校籃球聯(lián)賽中，某高校男子籃球隊(duì)要叢 8 名隊(duì)員中選擇平均身高最高的出場(chǎng)陣容，隊(duì)員的號(hào)碼，身高及擅長(zhǎng)的位置如表 2 4 12 所示： 表 2 4 12 隊(duì)員號(hào)碼 身高 ( m ) 位置 隊(duì)員號(hào)碼 身高 ( m ) 位置 1 中鋒 2 中鋒 3 前鋒 4 前鋒 5 前鋒 6 后衛(wèi) 7 后衛(wèi) 8 后衛(wèi) 同時(shí)，要求出場(chǎng)陣容必須滿足以下條件： （ 1 ）中鋒只能有一個(gè)上場(chǎng)； （ 2 ）至少有一名后衛(wèi)； （ 3 ）如果 1 號(hào)隊(duì)員和 4 號(hào)隊(duì)員都上場(chǎng)，則 6 號(hào)隊(duì)員不能出場(chǎng)； （ 4 ） 2 號(hào)隊(duì)員和 6 號(hào)隊(duì)員必須至少保留一個(gè)不出場(chǎng)。 如何確定符合要求的出場(chǎng)陣容？ 解：設(shè) ????? 82101,jjjx ?否則號(hào)球員出場(chǎng)第???????????????????????????????????????821105121178180183185186188190192187654321626418762187654321,j,xxxxxxxxxxxxxxxxxxx. xj? 求解： 1 、 3 、 4 、 5 號(hào)和 7 號(hào)隊(duì)員，平均身高 6 米 第四節(jié) 分配問(wèn)題 一、 分配問(wèn)題 二、匈牙利方法 分配問(wèn)題 設(shè)：????否則項(xiàng)任務(wù)個(gè)人員去完成第表示分配第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 分配問(wèn)題 基 本 概 念 解矩陣 系數(shù)矩陣 匹配 獨(dú)立 0元素 系數(shù)矩陣的定義與性質(zhì) 某游泳隊(duì)擬選用甲、乙、丙、丁四名游泳運(yùn)動(dòng)員組成一個(gè) 4 ? 10 0 米混合接力隊(duì)，參加今年的錦標(biāo)賽。他們的 100 米自由泳、蛙泳、蝶泳、仰泳的成績(jī)?nèi)绫硭尽＜住⒁摇⒈⒍∷拿?duì)員各自游什么姿勢(shì)，才最有可能取得好成績(jī)？ 成績(jī) 自由泳 蛙 泳 蝶 泳 仰 泳 甲 56 ? 74 ? 61 ? 63 ? 乙 63 ? 69 ? 65 ? 71 ? 丙 57 ? 77 ? 63 ? 67 ? 丁 55 ? 76 ? 62 ? 62 ? 解：設(shè)????種姿勢(shì)個(gè)人不游第第種姿勢(shì)個(gè)人游第第jijixij01 ?????????????????????????????????????????????????????????????????4321101111111162627655676377577165696363617456443424144333231342322212413121114443424134333231242322211413121144434241343332312423222114131211，，或 jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xxxxxxxxxxxxxxxxfmi nij 匹 配 某游泳隊(duì)擬選用甲、乙、丙、丁四名游泳運(yùn)動(dòng)員組成一個(gè) 4 ? 100 米混合接力隊(duì)，參加今年的錦標(biāo)賽。他們的 100 米自由泳、蛙泳、蝶泳、仰泳的成績(jī)?nèi)绫硭尽＜住⒁摇⒈⒍∷拿?duì)員各自游什么姿勢(shì)，才最有可能取得好成績(jī)？ 成績(jī) 自由泳 蛙 泳 蝶 泳 仰 泳 甲 56 ? 74 ? 61 ? 63 ? 乙 63 ? 69 ? 65 ? 71 ? 丙 57 ? 77 ? 63 ? 67 ? 丁 55 ? 76 ? 62 ? 62 ? 甲 —— 蝶泳 乙 —— 蛙泳 丙 —— 自由泳 丁 —— 仰泳 甲 —— 蛙泳 乙 —— 自由泳 丙 —— 蝶泳 丁 —— 仰泳 分配問(wèn)題的匈牙利解法 例 3 . 10 有一份中文說(shuō)明書(shū)，需譯成英，日，德，俄四種文字。分別記作 E , J, G , R 。現(xiàn)有甲 , 乙 , 丙 , 丁四人，他們將中文說(shuō)明書(shū)翻譯成不同語(yǔ)種的說(shuō)明書(shū)所需的時(shí)間有表 3. 7 給出，問(wèn)應(yīng)分配何人去完成何工作，使所需時(shí)間最少？ 表 3 . 7 任務(wù) 人員 E J G R 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 ??????????????9118713161491514410413152分配問(wèn)題的匈牙利解法 79429118713161491514410413152??????????????????2424104750111006211130??????????????????????????????001023509606017130? ? ??????????????0010235096*06017130????????????????001235*096*0601713?????????????????*01235*096*001713???????????????*23096*017 分配問(wèn)題的匈牙利解法 ??????????????541100032450115280分配問(wèn)題的匈牙利解法 第一步：給系數(shù)矩陣“制造” 0元素： ； 2. 從系數(shù)矩陣的每列元素減去該列的最小元素。 第二步：找 n 個(gè)獨(dú)立的“ 0”元素 ： 如果個(gè)數(shù)達(dá)到 n個(gè)，則結(jié)束，已經(jīng)的最優(yōu)解； 否則，轉(zhuǎn)第三步。 第三步 增加系數(shù)矩陣中的 0元素： 1. 找最少直線覆蓋效率矩陣中的所有 0元素 （ 1）對(duì)沒(méi)有 0*行的行打 ?， （ 2）對(duì)打 ?的行上所有有 0元素的列打 ?， （ 3）對(duì)打 ?列的上所有有 0*元素的行打 ?， （ 4）重復(fù)（ 2）（ 3）步，到過(guò)程結(jié)束 （ 5）對(duì)沒(méi)有打 ?的行畫(huà)橫線，所有打 ?的列畫(huà)垂線，找到了覆蓋所有 0元素的最少直線。 分配問(wèn)題的匈牙利解法 分配問(wèn)題的匈牙利解法 2. 增加 0元素 （ 1）在系數(shù)矩陣中沒(méi)有被覆蓋的元素中找最小元素 ?； （ 2）對(duì)沒(méi)有被直線覆蓋的行，減去最小元素 ?，對(duì)被直線覆蓋的列，加上最小元素 ?； 轉(zhuǎn)第二步。 分配問(wèn)題的匈牙利解法 最大值問(wèn)題 匈牙利法實(shí)質(zhì)上一種求最小值的方法，如果給我們的是系數(shù)矩陣， a ij表示 的是第 i 個(gè)人員完成第 j 項(xiàng)任務(wù)的收益，則要求我們?nèi)绾畏峙淠橙送瓿赡稠?xiàng)任務(wù)，使總收益最大。這種求最大值的分配問(wèn)題如何求解呢。 分配問(wèn)題的匈牙利解法 系數(shù)矩陣不是方陣 在實(shí)際問(wèn)題中，往往遇到有些任務(wù)沒(méi)有人去做，或某些人沒(méi)有分配到任務(wù)的情況。對(duì)系數(shù)矩陣來(lái)說(shuō)，表現(xiàn)為系數(shù)矩陣不是方陣，而用匈牙利法求解時(shí)，系數(shù)矩陣為方陣是必要條件。 分配問(wèn)題的匈牙利解法 某工廠訂購(gòu)了三臺(tái)機(jī)器（ A,B,C），有四各位置可供機(jī)器安裝（位置一，二，三，四），但 B機(jī)器不能安裝在第二號(hào)位置。由于這四個(gè)安裝位置離工廠中心的遠(yuǎn)近不同，所需要的原料運(yùn)送費(fèi)用也就不同，想要求總的原料運(yùn)送費(fèi)用達(dá)到最小，問(wèn)這些機(jī)器安裝在哪幾個(gè)位置最適合？ 分配問(wèn)題的匈牙利解法 費(fèi)用 位置 機(jī)器 一 二 三 四 A 13 10 12 11 B 15 M 13 20 C 5 7 10 6 D 0 0 0 0 分配問(wèn)題的匈牙利解法 ??????????????00006107520211511121013M分配問(wèn)題的匈牙利解法 某單位有四項(xiàng)任務(wù)，而有五個(gè)員工都能勝任這四項(xiàng)任務(wù)，但是由于技術(shù)水平不同，完成任務(wù)的時(shí)間也不同，問(wèn)如何分配任務(wù)使總時(shí)間最少？ 任務(wù) 員工 T1 T2 T3 T4 O1 15 18 21 24 O2 19 23 22 18 O3 26 17 16 19 O4 19 21 23 17 O5 17 18 19 17