【正文】 4 2 5 7 需求量 3 8 4 6 工廠 B 1 工廠 B 2 工廠 B 3 工廠 B 4 庫(kù)存量 ○ 3 ○ 6 0 6 倉(cāng)庫(kù) A 1 2 9 10 7 9 5 ○ 2 ○ 3 5 倉(cāng)庫(kù) A 2 1 3 4 2 5 14 3 ○ 1 ○ 6 倉(cāng)庫(kù) A 3 8 4 2 5 7 需求量 3 8 4 6 求檢驗(yàn)數(shù)的位勢(shì)法（ 1） 1v 2v …… nv B 1 B 2 …… B n 供應(yīng)量 1u A1 c 11 c 12 …… c 1 n a 1 2u A 2 c 21 c 22 …… c 2 n a 2 … … … … …… … … mu Am c m 1 c m 2 …… c mn a m 需求量 b 1 b 2 …… b n 定理：運(yùn)輸問(wèn)題變量 x ij 的檢驗(yàn)數(shù) ijjiij cvuC ??? 求檢驗(yàn)數(shù)的位勢(shì)法（ 2） 定理：運(yùn)輸問(wèn)題變量 x ij 的檢驗(yàn)數(shù) ijjiij cvuC ??? 133113 cvuC ???010100 ???? 144114 cvuC ???67130 ???? 211221 cvuC ???5126 ?????? 244224 cvuC ???52136 ????? 311331 cvuC ???14828 ?????? 322332 cvuC ???3498 ?????? ??????????????????????????????00000001344333332332222212211111ucvucvucvucvucvucvu??????????????????????????????00502040309021433332222111uvuvuvuvuvuvu????????????????????1310928604321321vvvvuuu 工廠 B 1 工廠 B 2 工廠 B 3 工廠 B 4 庫(kù)存量 ○ 3 ○ 6 0 6 倉(cāng)庫(kù) A 1 2 9 10 7 9 5 ○ 2 ○ 3 5 倉(cāng)庫(kù) A 2 1 3 4 2 5 14 3 ○ 1 ○ 6 倉(cāng)庫(kù) A 3 8 4 2 5 7 需求量 3 8 4 6 閉回路調(diào)整法 2 9 10 13 工廠 B 1 工廠 B 2 工廠 B 3 工廠 B 4 庫(kù)存量 ○ 3 ○ 6 0 6 0 倉(cāng)庫(kù) A 1 2 9 10 7 9 5 ○ 2 ○ 3 5 6 倉(cāng)庫(kù) A 2 1 3 4 2 5 14 3 ○ 1 ○ 6 8 倉(cāng)庫(kù) A 3 8 4 2 5 7 需求量 3 8 4 6 + + + ?? 65,6m a x ? ，所以 x 14 入基 θ = mi n { 閉回路上所有標(biāo)“ ”號(hào)的頂點(diǎn) x ij } 即 θ = mi n { x34 ， x 23 ， x 12 }= mi n { 6 ， 3 ， 6 } = 3 閉回路上所有標(biāo)“ +”號(hào)的 xij加上 θ 所有標(biāo)“ ”號(hào)的 xij減去 θ 基變量 x 23 的取值變成了 0 ，所以 x 23 出基 工廠 B 1 工廠 B 2 工廠 B 3 工廠 B 4 庫(kù)存量 ○ 3 ○ 6 0 6 倉(cāng)庫(kù) A 1 2 9 10 7 9 5 ○ 2 ○ 3 5 倉(cāng)庫(kù) A 2 1 3 4 2 5 14 3 ○ 1 ○ 6 倉(cāng)庫(kù) A 3 8 4 2 5 7 需求量 3 8 4 6 第三節(jié) 不平衡的運(yùn)輸問(wèn)題 ? 供過(guò)于求的運(yùn)輸問(wèn)題 ? 供不應(yīng)求的運(yùn)輸問(wèn)題 第三章 整數(shù)規(guī)劃 第一節(jié) 整數(shù)線性規(guī)劃問(wèn)題 第二節(jié) 分枝定界法 第三節(jié) 0—1 規(guī)劃 第四節(jié) 分配問(wèn)題 第一節(jié) 整數(shù)線性規(guī)劃問(wèn)題 一 、整數(shù)線性規(guī)劃問(wèn)題 二、 整數(shù)規(guī)劃的分類 ? 純整數(shù)規(guī)劃 所有變量都取非負(fù)整數(shù)的線性規(guī)劃 ? 混合整數(shù)規(guī)劃 部分變量取非負(fù)整數(shù)的線性規(guī)劃 ? 0—1規(guī)劃 變量的值只限制取 0或 1的線性規(guī)劃 第三節(jié) 0—1規(guī)劃 某游泳隊(duì)擬選用甲、乙、丙、丁四名游泳運(yùn)動(dòng)員組成一個(gè) 4 ? 10 0 米混合接力隊(duì)，參加今年的錦標(biāo)賽。甲、乙、丙、丁四名隊(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 解得結(jié)果如下： 甲 —— 蝶泳 乙 —— 蛙泳 丙 —— 自由泳 丁 —— 仰泳 總成績(jī) = 61+ 69+ 57 + 62= 249 （秒）。如果已知各點(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)。他們的 100 米自由泳、蛙泳、蝶泳、仰泳的成績(jī)?nèi)绫硭?。他們?100 米自由泳、蛙泳、蝶泳、仰泳的成績(jī)?nèi)绫硭?。分別記作 E , J, G , R 。 第二步：找 n 個(gè)獨(dú)立的“ 0”元素 ： 如果個(gè)數(shù)達(dá)到 n個(gè)，則結(jié)束，已經(jīng)的最優(yōu)解； 否則，轉(zhuǎn)第三步。 分配問(wèn)題的匈牙利解法 分配問(wèn)題的匈牙利解法 2. 增加 0元素 （ 1）在系數(shù)矩陣中沒有被覆蓋的元素中找最小元素 ?； （ 2）對(duì)沒有被直線覆蓋的行，減去最小元素 ?，對(duì)被直線覆蓋的列，加上最小元素 ?； 轉(zhuǎn)第二步。這種求最大值的分配問(wèn)題如何求解呢。對(duì)系數(shù)矩陣來(lái)說(shuō)，表現(xiàn)為系數(shù)矩陣不是方陣，而用匈牙利法求解時(shí)，系數(shù)矩陣為方陣是必要條件。由于這四個(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