【正文】 x2≤3 x2≥4 x1≤2 x1≥3 ＃ ＃ ＃ ＃ 應(yīng)用舉例：布點(diǎn)問題 ? 共同目標(biāo)：滿足公共要求，布點(diǎn)最少，節(jié)約投資費(fèi)用。 ? 例：某市 6個(gè)區(qū)，希望設(shè)置最少消防站以便節(jié)省費(fèi)用。各區(qū)之間消防車行駛的時(shí)間見右表。 地點(diǎn) 一區(qū) 二區(qū) 三區(qū) 四區(qū) 五區(qū) 六區(qū) 一區(qū) 0 二區(qū) 10 0 三區(qū) 16 24 0 四區(qū) 28 32 12 0 五區(qū) 27 17 27 15 0 六區(qū) 20 10 21 25 14 0 布點(diǎn)問題的數(shù)學(xué)模型： ? 設(shè) 0?1為決策變量，當(dāng) xi=1表示 i地區(qū)設(shè)站，表示 xi=0 i地區(qū)不設(shè)站。 例一、求解下列 0－ 1 規(guī)劃問題 ???????????????????????10,( 4 ) 64 ( 3 ) 3 ( 2 ) 44( 1 ) 22523m a x3213221321321321或xxxxxxxxxxxxxxxxZ四、 0－ 1 整數(shù)規(guī)劃 解：對于 0－ 1 規(guī)劃問題，由于每個(gè)變量只取 0， 1兩個(gè)值，一般會(huì)用窮舉法來解，即將所有的 0， 1 組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。而隱枚舉法就是在此基礎(chǔ)上，通過加入一定的條件，就能較快的求得最優(yōu)解。 x1 . x2. x3 約束條件 滿足條件 Z 值 (0) (1) (2) (3) (4) 是 ∨ 否 ( 0. 0. 0 ) 0 0 0 0 0 ∨ 0 ( 0. 0. 1 ) 5 － 1 1 0 1 ∨ 5 ( 0. 1. 0 ) 2 ( 0. 1. 1 ) 3 ( 1. 0. 0 ) 3 ( 1. 0. 1 ) 8 0 2 1 1 ∨ 8 ( 1. 1. 0 ) 1 ( 1. 1. 1 ) 4 例二、求解下列 0－ 1 規(guī)劃問題 ????????????????????????? 1 ,05 35646 1 273m a x421432143214321jxxxxxxxxxxxxxxxxZj 解：由于目標(biāo)函數(shù)中變量 x1, x2 , x4 的系數(shù)均為負(fù)數(shù)，可作如下變換： 令 x1 ＝ 1－ x1′ , x2 =1 x2′, x3= x3′, x4 =1 x4′帶入原題中，但需重新調(diào)整變量編號(hào)。 ???????????????????????????????????????????1 0,435 2 461 2 1173m a x4321432432143214321或xxxxxxxxxxxxxxxxxxxZ 可以從 ( )開始試算， x′(3)＝ ( )最優(yōu)解。于是產(chǎn)生了一個(gè)問題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成 n 項(xiàng)任務(wù)的總效率最高（或所需時(shí)間最少），這類問題稱為指派問題或分派問題。已知第 I 個(gè)人去做第 j 件工作的的效率（ 時(shí)間或費(fèi)用）為Cij(i=… n。問應(yīng)如何分配才能使總效率（ 時(shí)間或費(fèi)用）最高？ 五、指派問題 設(shè)決策變量 1 分配第 i 個(gè)人去做第 j 件工作 xij = 0 相反 ( I,j=. … n ) 其數(shù)學(xué)模型為： ????????????????????? ???? ?)..,1(0)..( 1)..( 1m i n111 1njixnjxnixxcZijniijnjijninjijij???或 （二）、解題步驟： 指派問題是 01 規(guī)劃的特例，也是運(yùn)輸問題的特例，當(dāng)然可用整數(shù)規(guī)劃， 01 規(guī)劃或運(yùn)輸問題的解法去求解，這就如同用單純型法求解運(yùn)輸問題一樣是不合算的。 第一步：變換指派問題的系數(shù)矩陣 （ cij） 為 (bij)， 使在 (bij)的各行各列中都出現(xiàn) 0元素 ， 即 (1) 從 （ cij） 的每行元素都減去該行的最小元素； (2) 再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素 。 在 (bij)中找盡可能多的獨(dú)立 0元素 ， 若能找出 n個(gè)獨(dú)立 0元素 ， 就以這 n個(gè)獨(dú)立 0元素對應(yīng)解矩陣 (xij)中的元素為 1， 其余為 0， 這就得到最優(yōu)解 。 然后劃去 ◎ 所在列 (行 )的其它 0元素 ， 記作 216。 (2)給只有一個(gè) 0元素的列 (行 )中的 0元素加圈 ， 記作◎ ；然后劃去 ◎ 所在行的 0元素 ， 記作 216。 (4)若仍有沒有劃圈的 0元素 ， 且同行 (列 )的 0元素至少有兩個(gè) ， 則從剩有 0元素最少的行 (列 )開始 ， 比較這行各 0元素所在列中 0元素的數(shù)目 ， 選擇 0元素少的那列的這個(gè) 0元素加圈 (表示選擇性多的要 “ 禮讓 ” 選擇性少的 )。 可反復(fù)進(jìn)行 ，直到所有 0元素都已圈出和劃掉為止 。若 m n, 則轉(zhuǎn)入下一步。 (1)對沒有 ◎ 的行打 √號(hào)； (2)對已打 √號(hào)的行中所有含 216。 l 應(yīng)等于 m，若不相等 ， 說明試指派過程有誤 ， 回到第二步 (4)， 另行試指派；若 l＝ m n， 須再變換當(dāng)前的系數(shù)矩陣 ，以找到 n個(gè)獨(dú)立的 0元素 ， 為此轉(zhuǎn)第四步 。 在沒有被直線覆蓋的所有元素中找出最小元素，然后打 √各行都減去這最小元素；打 √各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。轉(zhuǎn)回第二步。 ◎ 216。 ◎ ◎ ????????????0100000100101000 有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作 A、 B、 C、 D。 216。 216。 216。 216。 216。 ◎ ◎ ◎ 216。 ????????????????5032015304310140305242402◎ 216。 216。 ◎ ◎ ◎ 216。 ????????????????5033004203310240306231301????????????????5033004203310240306231301◎ 216。 ◎ 216。 √ √ √ ????????????????5033004203310240306231301√ √ √ √ ????????????????5033004203310240306231301◎ 216。 ◎ 216。 √ √ √ √ √ √ √ l =m=4 n=5 ????????????????5033004203310240306231301◎ 216。 ◎ 216。 √ √ √ √ √ √ √ ????????????????6044003202300230206130300????????????????6044003202300230206130300????????????????6044003202300230206130300◎ 216。 ◎ 216。 ◎ 216。 ◎ 此問題有多個(gè)最優(yōu)解 28 ????????????????6044003202300230206130300◎ 216。 ◎ 216。 ◎ 216。 ◎ ????????????????6044003202300230206130300◎ 216。 ◎ 216。 ◎ 216。 ◎ 用匈牙利法求解下列指派問題，已知效率矩陣分別如下： 7 9 1 0 1 21 3 1 2 1 6 1 71 5 1 6 1 4 1 51 1 1 2 1 5 1 6????????????3 8 2 10 38 7 2 9 76 4 2 7 58 4 2 3 59 10 6 9 10??????????????