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

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 某道橋公司在同一時間內(nèi)可參加某道橋公司在同一時間內(nèi)可參加A A1 1、A A2 2、A A3 3、A A4 4四項工程的四項工程的投標。這些項目要求的工期相同。公司根據(jù)招標文件和本投標。這些項目要求的工期相同。公司根據(jù)招標文件和本公司的技術(shù)水平對每項工程進行了仔細的研究和計算，將公司的技術(shù)水平對每項工程進行了仔細的研究和計算，將各項工程的預(yù)期利潤，主要工序的工程量及本企業(yè)的施工各項工程的預(yù)期利潤，主要工序的工程量及本企業(yè)的施工能力見小表。問該公司對哪幾種項目投

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

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

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

5、 (1)44 (2)3 (3)46 (4),01xxxxxxxxxxxxx或2132+355xxx過濾條件過濾條件 通過試探的方法找到一個可行解。通過試探的方法找到一個可行解。容易看出容易看出,(x1,x2,x3)=(0,0,1)是滿足約束條件的可行解。是滿足約束條件的可行解。相應(yīng)的目標函數(shù)值為相應(yīng)的目標函數(shù)值為S=5。 系數(shù)重排系數(shù)重排nmax型，目標函數(shù)中變量系數(shù)小型，目標函數(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個變量共有8種組合原先4個約束方程，需要32次計算增加過濾條件后，可減少計算次數(shù)不符合過濾條件的，就不需要繼續(xù)計算其余的約束方程了0-1型整數(shù)規(guī)劃的解法：隱枚舉法型整數(shù)規(guī)劃的解法：隱枚舉法12 系數(shù)、約束條件等重排序非必要系數(shù)、約束條件

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

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

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

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

11、7545458585 56565444464644343313160606 6323224243434242433336464設(shè)某運輸隊有6輛卡車，需分派駛往6個不同的目的地，由于各輛卡車的性能、消耗和效率不同，因而駛往各目的地的運輸成本也不同，如下表所示。試求能使總成本最低的車輛分派方案。 效率矩陣19否則目的地號車輛駛往第若分派第 , 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個約束條件，但有且只個約束條件，但有且只有有m個非零解，是自然個非零解，是自然高度退化高度退化的。的。1111min( )1 1,2,1 1,2,0,1mmijijijmijjmijiijf xa xximxjmx21

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

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

15、行，不同列的零元素，：找出所以位于不同行，不同列的零元素，即獨立零元素；并用最少條數(shù)的直線覆蓋全部零元即獨立零元素；并用最少條數(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。本例還沒有達到最優(yōu)解。25在未劃線的元素中找出在未劃線的元素中找出最小元素最小元素未劃線的各元素減去這個最小元素未劃線的各元素減去這個最小元素兩直線交叉劃線的各元素加上這個最小元素兩直線交叉劃線的各元

16、素加上這個最小元素其余元素不變其余元素不變2 1 0 0 42 3 0 4 06 2 6 0 43 0 7 3 30 1 1 1 3第三步第三步：再變換矩陣來增多獨立零元素個數(shù)；：再變換矩陣來增多獨立零元素個數(shù)；26第一輛車在第一輛車在3 3號線路號線路 第二輛車在第二輛車在5 5號線路號線路第三輛車在第三輛車在4 4號線路號線路 第四輛車在第四輛車在2 2號線路號線路第五輛車在第五輛車在1 1號線路號線路第四步第四步：得到一個新矩陣，轉(zhuǎn)到第二步，重復前述步：得到一個新矩陣，轉(zhuǎ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與原問題有同