第七章選址問題及隱枚舉法

1、1第一節(jié)第一節(jié) 整數(shù)規(guī)劃整數(shù)規(guī)劃第二節(jié)第二節(jié) 0-1規(guī)劃規(guī)劃第三節(jié)第三節(jié) 指派問題指派問題第四節(jié)第四節(jié) 整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用2 某道橋公司在同一時(shí)間內(nèi)可參加某道橋公司在同一時(shí)間內(nèi)可參加A A1 1、A A2 2、A A3 3、A A4 4四項(xiàng)工程的四項(xiàng)工程的投標(biāo)。這些項(xiàng)目要求的工期相同。公司根據(jù)招標(biāo)文件和本投標(biāo)。這些項(xiàng)目要求的工期相同。公司根據(jù)招標(biāo)文件和本公司的技術(shù)水平對(duì)每項(xiàng)工程進(jìn)行了仔細(xì)的研究和計(jì)算，將公司的技術(shù)水平對(duì)每項(xiàng)工程進(jìn)行了仔細(xì)的研究和計(jì)算，將各項(xiàng)工程的預(yù)期利潤(rùn)，主要工序的工程量及本企業(yè)的施工各項(xiàng)工程的預(yù)期利潤(rùn)，主要工序的工程量及本企業(yè)的施工能力見小表。問該公司對(duì)哪幾種項(xiàng)目投

2、標(biāo)可能獲得的總利能力見小表。問該公司對(duì)哪幾種項(xiàng)目投標(biāo)可能獲得的總利潤(rùn)最大？試建立這個(gè)問題的數(shù)學(xué)模型。潤(rùn)最大？試建立這個(gè)問題的數(shù)學(xué)模型。 工程項(xiàng)目工程項(xiàng)目預(yù)期利潤(rùn)（萬(wàn)元）預(yù)期利潤(rùn)（萬(wàn)元）土石方量（土石方量（m3）混凝土量（混凝土量（m3）其他材料（其他材料（m2）A1542002802500A282300880480A37.548003001500A4923009005200施工能力施工能力1200016009000第二節(jié)第二節(jié) 0-1規(guī)劃規(guī)劃3, 4 , 3 , 2 , 1 , , 0 , 1iAxii否則投資對(duì)項(xiàng)目4 , 3 , 2 , 11 090005200150048025001600

3、900300880280120003200480023004200 s.t.95 . 785max 4321432143214321ixxxxxxxxxxxxxxxxxzi，或設(shè)則建立的數(shù)學(xué)模型第二節(jié)第二節(jié) 0-1規(guī)劃規(guī)劃 建模建模456 每個(gè)變量都只取每個(gè)變量都只取0 0，1 1兩個(gè)值，變量取值的兩個(gè)值，變量取值的0-10-1組合組合是有限的。是有限的。 先列出各變量分別取先列出各變量分別取0 0或或1 1值的每一種組合，然后值的每一種組合，然后在滿足約束條件的變量的在滿足約束條件的變量的0-10-1組合中找出使目標(biāo)函組合中找出使目標(biāo)函數(shù)達(dá)到最優(yōu)值的組合即是該數(shù)達(dá)到最優(yōu)值的組合即是該0-10

4、-1規(guī)劃的最優(yōu)解。規(guī)劃的最優(yōu)解。 用這種方法求解變量個(gè)數(shù)為用這種方法求解變量個(gè)數(shù)為n n的的0-10-1規(guī)劃，通常需規(guī)劃，通常需檢查檢查2 2n n個(gè)組合。個(gè)組合。 計(jì)算量大，隨變量數(shù)量的增加呈集合級(jí)數(shù)增長(zhǎng)計(jì)算量大，隨變量數(shù)量的增加呈集合級(jí)數(shù)增長(zhǎng) 7 設(shè)計(jì)一種方法，只要檢查變量取值的一部分就能得到原設(shè)計(jì)一種方法，只要檢查變量取值的一部分就能得到原問題的最優(yōu)解。問題的最優(yōu)解。 這種方法稱為這種方法稱為隱枚舉法隱枚舉法。8321523maxxxxz 10,4 643 32 441 223123212312312或xxxxxxxxxxxxx9213max235zxxx 213213212321322

5、 (1)44 (2)3 (3)46 (4),01xxxxxxxxxxxxx或2132+355xxx過濾條件過濾條件 通過試探的方法找到一個(gè)可行解。通過試探的方法找到一個(gè)可行解。容易看出容易看出,(x1,x2,x3)=(0,0,1)是滿足約束條件的可行解。是滿足約束條件的可行解。相應(yīng)的目標(biāo)函數(shù)值為相應(yīng)的目標(biāo)函數(shù)值為S=5。 系數(shù)重排系數(shù)重排nmax型，目標(biāo)函數(shù)中變量系數(shù)小型，目標(biāo)函數(shù)中變量系數(shù)小-大大nmin型，相反型，相反n容易觀察容易觀察 增加過濾條件增加過濾條件(filtering constraint)10213max2+35zxxx 213213212321322 144 23 346

6、 4,01xxxxxxxxxxxxx或2132+355xxx（0 0） 約束條件重排序約束條件重排序解解約束條件約束條件是否滿足條是否滿足條件？件？z值值（0）（1）（2）（3）（4）（0，0，0）0 （0，0，1）5-11015（0，1，0）-2 （0，1，1）3（1，0，0）3（1，0，1）802118（1，1，0）1 （1，1，1）6 用全部枚舉的方法，3個(gè)變量共有8種組合原先4個(gè)約束方程，需要32次計(jì)算增加過濾條件后，可減少計(jì)算次數(shù)不符合過濾條件的，就不需要繼續(xù)計(jì)算其余的約束方程了0-1型整數(shù)規(guī)劃的解法：隱枚舉法型整數(shù)規(guī)劃的解法：隱枚舉法12 系數(shù)、約束條件等重排序非必要系數(shù)、約束條件

7、等重排序非必要 更新過濾條件更新過濾條件 當(dāng)遇到可行解的目標(biāo)值大于過濾條件當(dāng)遇到可行解的目標(biāo)值大于過濾條件（0）當(dāng)前的右端值時(shí)，應(yīng)及時(shí)將（）當(dāng)前的右端值時(shí)，應(yīng)及時(shí)將（0）右端值換成大者。右端值換成大者。 一家移動(dòng)通信公司準(zhǔn)備在四個(gè)候選的位置中挑選幾個(gè)一家移動(dòng)通信公司準(zhǔn)備在四個(gè)候選的位置中挑選幾個(gè)來(lái)建造信號(hào)發(fā)射基站，以便覆蓋一個(gè)城市中的四個(gè)地來(lái)建造信號(hào)發(fā)射基站，以便覆蓋一個(gè)城市中的四個(gè)地區(qū)。這四個(gè)位置對(duì)于四個(gè)區(qū)的覆蓋與修建費(fèi)用如下表區(qū)。這四個(gè)位置對(duì)于四個(gè)區(qū)的覆蓋與修建費(fèi)用如下表所示（在一個(gè)位置所在列與一個(gè)地區(qū)所在行的交叉點(diǎn)所示（在一個(gè)位置所在列與一個(gè)地區(qū)所在行的交叉點(diǎn)處有數(shù)字處有數(shù)字“1 1”表

8、明在該位置建造信號(hào)發(fā)射基站時(shí)信表明在該位置建造信號(hào)發(fā)射基站時(shí)信號(hào)可以覆蓋對(duì)應(yīng)的地區(qū)）：號(hào)可以覆蓋對(duì)應(yīng)的地區(qū)）： 要求：構(gòu)造一個(gè)線性規(guī)劃模型，用規(guī)劃求解工具確定要求：構(gòu)造一個(gè)線性規(guī)劃模型，用規(guī)劃求解工具確定一種基站建設(shè)方案，使得既能將四個(gè)地區(qū)都覆蓋一種基站建設(shè)方案，使得既能將四個(gè)地區(qū)都覆蓋，又又使建站總費(fèi)用達(dá)到極小。使建站總費(fèi)用達(dá)到極小。13 求解結(jié)果：求解結(jié)果：1415 有有n n項(xiàng)任務(wù)，分配給項(xiàng)任務(wù)，分配給n n個(gè)人去完成，要求每個(gè)個(gè)人去完成，要求每個(gè)人完成其中一項(xiàng)任務(wù)，每項(xiàng)任務(wù)只交給其中一人完成其中一項(xiàng)任務(wù)，每項(xiàng)任務(wù)只交給其中一個(gè)人完成，已知每個(gè)人完成各項(xiàng)任務(wù)的成本個(gè)人完成，已知每個(gè)人完成

9、各項(xiàng)任務(wù)的成本（或效率），求使總成本最少的分配方案。（或效率），求使總成本最少的分配方案。 任務(wù)分配問題；指派問題；資源分配問題任務(wù)分配問題；指派問題；資源分配問題（Assignment Problem, AP）16有四個(gè)熟練工人，他們都是多面手，有四項(xiàng)任務(wù)要他們完成。若規(guī)定每人必須完成且只完成一項(xiàng)任務(wù)，而每人完成每項(xiàng)任務(wù)的工時(shí)耗費(fèi)如表，問如何分配任務(wù)使完成四項(xiàng)任務(wù)的總工時(shí)耗費(fèi)最少？任務(wù)任務(wù) 工時(shí)工時(shí)ABCD人員人員人員人員甲甲109781乙乙58771丙丙54651丁丁23451任務(wù)任務(wù)111117xij 為第 i 個(gè)工人分配去做第 j 項(xiàng)任務(wù)；aij 為第 i 個(gè)工人為完成第 j 項(xiàng)任務(wù)時(shí)

10、的工時(shí)消耗；aijmm 稱為效率矩陣mjijijixij, 2 , 1,01項(xiàng)任務(wù)項(xiàng)任務(wù)個(gè)工人未分配去做第個(gè)工人未分配去做第當(dāng)?shù)诋?dāng)?shù)陧?xiàng)任務(wù)項(xiàng)任務(wù)個(gè)工人分配去做第個(gè)工人分配去做第當(dāng)?shù)诋?dāng)?shù)?111min( )1 1,2,1 1,2,0,1mmijijijmijjmijiijf xa xximxjmx18 目的地目的地車輛編號(hào)車輛編號(hào)D D1 1D D2 2D D3 3D D4 4D D5 5D D6 61 14646666655555959202028282 22424818125256262252591913 32828222239395050272786864 4464631314545474

11、7545458585 56565444464644343313160606 6323224243434242433336464設(shè)某運(yùn)輸隊(duì)有6輛卡車，需分派駛往6個(gè)不同的目的地，由于各輛卡車的性能、消耗和效率不同，因而駛往各目的地的運(yùn)輸成本也不同，如下表所示。試求能使總成本最低的車輛分派方案。 效率矩陣19否則目的地號(hào)車輛駛往第若分派第 , 1 , 0jixij6 , 2 , 1,ji666564636261565554535251464544434241363534333231262524232221161514131211643324342432 603143644465 585447453

12、146 8627503962228 912562258124 282059556646min xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz6 , 2 , 1, 1, 06 , 2 , 1 , 16 , 2 , 1 , 1 s.t.6161jixjxixijiijjij或20AP不但是整數(shù)規(guī)劃，而且是不但是整數(shù)規(guī)劃，而且是0 1規(guī)劃；規(guī)劃；AP有有2m個(gè)約束條件，但有且只個(gè)約束條件，但有且只有有m個(gè)非零解，是自然個(gè)非零解，是自然高度退化高度退化的。的。1111min( )1 1,2,1 1,2,0,1mmijijijmijjmijiijf xa xximxjmx21

13、根據(jù)定理 1 變換效率矩陣，使矩陣中有足夠多的零。若矩陣中存在 m 個(gè)不同行不同列的零，就找到了最優(yōu)解若覆蓋變換后的效率矩陣零元素的直線少于m 條，就尚未找到最優(yōu)解，設(shè)法進(jìn)一步變換矩陣，增加新的零匈牙利算法匈牙利算法22 有有5 5輛公交車可以在輛公交車可以在5 5條公交線路上行駛。不同車條公交線路上行駛。不同車輛在不同的路線上發(fā)生的年平均交通事故數(shù)如下輛在不同的路線上發(fā)生的年平均交通事故數(shù)如下表所示。這表所示。這5 5輛公交車如何分配，才能使全年的總輛公交車如何分配，才能使全年的總事故數(shù)最少？事故數(shù)最少？匈牙利法的解題步驟匈牙利法的解題步驟 線路編號(hào)線路編號(hào)車輛車輛R1R2R3R4R5D17

14、3328D2108697D392706D460835D55342723使費(fèi)用矩陣出現(xiàn)使費(fèi)用矩陣出現(xiàn)0元素元素 3 3 2 8 8 6 9 7 2 7 0 6 0 8 3 55 3 4 2 7 1 1 0 6 2 0 3 1 2 7 0 6 0 8 3 53 1 2 0 5初始效率矩陣初始效率矩陣第一步：變換效率矩陣，使每行每列至少有一個(gè)零(不能出現(xiàn)負(fù)值) 行變換：找出每行最小元素，從該行各元素中減去之 列變換：找出每列最小元素，從該列各元素中減去之2 1 1 0 51 2 0 3 06 2 7 0 53 0 8 3 40 1 2 0 4行變換行變換列變換列變換24第二步第二步：找出所以位于不同

15、行，不同列的零元素，：找出所以位于不同行，不同列的零元素，即獨(dú)立零元素；并用最少條數(shù)的直線覆蓋全部零元即獨(dú)立零元素；并用最少條數(shù)的直線覆蓋全部零元素；素；2 1 1 0 51 2 0 3 06 2 7 0 53 0 8 3 40 1 2 0 42 1 1 0 51 2 0 3 06 2 7 0 53 0 8 3 40 1 2 0 4如果是MM矩陣，而又要使最優(yōu)解分配在0元素位置上，劃線數(shù)量應(yīng)為M。本例還沒有達(dá)到最優(yōu)解。25在未劃線的元素中找出在未劃線的元素中找出最小元素最小元素未劃線的各元素減去這個(gè)最小元素未劃線的各元素減去這個(gè)最小元素兩直線交叉劃線的各元素加上這個(gè)最小元素兩直線交叉劃線的各元

16、素加上這個(gè)最小元素其余元素不變其余元素不變2 1 0 0 42 3 0 4 06 2 6 0 43 0 7 3 30 1 1 1 3第三步第三步：再變換矩陣來(lái)增多獨(dú)立零元素個(gè)數(shù)；：再變換矩陣來(lái)增多獨(dú)立零元素個(gè)數(shù)；26第一輛車在第一輛車在3 3號(hào)線路號(hào)線路 第二輛車在第二輛車在5 5號(hào)線路號(hào)線路第三輛車在第三輛車在4 4號(hào)線路號(hào)線路 第四輛車在第四輛車在2 2號(hào)線路號(hào)線路第五輛車在第五輛車在1 1號(hào)線路號(hào)線路第四步第四步：得到一個(gè)新矩陣，轉(zhuǎn)到第二步，重復(fù)前述步：得到一個(gè)新矩陣，轉(zhuǎn)到第二步，重復(fù)前述步驟，再檢驗(yàn)。驟，再檢驗(yàn)。2 1 0 0 42 3 0 4 06 2 6 0 43 0 7 3 30 1 1 1 32728 找到原效率矩陣最大元素找到原效率矩陣最大元素m，以，以m減去原效率矩陣減去原效率矩陣各元素值，則新矩陣的最小化各元素值，則新矩陣的最小化AP與原問題有同