水廠選址-數(shù)學(xué)建模

水廠供水的優(yōu)化問題摘要：選址是生活中經(jīng)常遇到的問題，如向居民輸送自來水等都是實際需要考慮的問題，在解決此類問題時，可以將實際問題具體化，首先將總區(qū)域建立成一個平面坐標(biāo)，接著將居民區(qū)簡化成坐標(biāo)，如此，便可將復(fù)雜的生活問題化成數(shù)學(xué)建模問題。本文正是研究了一個向六個居民區(qū)輸水的A、B水廠的選址問題，對于問題一，本論文采用線性最優(yōu)化的思想，對本錢在約束函數(shù)的條件下，求解其最小值，求解過程使用lingo軟件。對于問題二，本論文把其定義為雙選址問題，首先對六個居民點，分成兩個區(qū)域，然后分別求解。為了簡單易求，我們首先選擇重心法，對其求解，但通過對其結(jié)果的分析，我們發(fā)現(xiàn)，重心法存在著缺點。所以本論文對模型進(jìn)行重建，列出了一個二元方程，然后對其最小值進(jìn)行求解。關(guān)鍵詞：最優(yōu)化，選址，線性最優(yōu)化，重心法，二元函數(shù)一、問題重述〔優(yōu)化選址問題〕某城市擬建A、B兩個水廠。水廠分小、中、大三種規(guī)模，日均貯水量分別為30萬噸、40萬噸及50萬噸，A、B兩個水廠日進(jìn)水量總和不超過80萬噸。A、B兩個水廠共同擔(dān)負(fù)供給六個居民區(qū)〔由表一給出坐標(biāo)〕用水任務(wù)，每戶日均用水量為1.0噸，水廠供給居民點用水的本錢為1.05元/噸公里。表1：各居民區(qū)的位置和擁有的家庭戶數(shù)居民點123456位置012345454412家庭戶數(shù)〔萬戶〕1011815822表一問題一：假設(shè)A、B兩個水廠的位置分別為A=A(1，4)和B=B(4，2)，試確定供水方案使總本錢最低；問題二：假設(shè)A、B兩個水廠的位置尚未確定，請你確定它們的位置及供水方案使總本錢最低；二、模型假設(shè)1.假設(shè)水廠與居民點的距離為直線距離，即忽略掉輸水管道的路線問題。2.假設(shè)水廠與居民點之間的供水費(fèi)用僅與供水長度有關(guān)，和輸水量無關(guān)。3.假設(shè)水廠的建設(shè)資金是確定的，不會因規(guī)模的大小而改變。本錢僅為供水本錢。4.假設(shè)水廠和居民區(qū)都是理性化的質(zhì)點。5.假設(shè)居民的用水量就為人均用水量乘上人口數(shù)。而且，長期不變。三、符號表示符號含義維護(hù)管道所花費(fèi)的費(fèi)用〔，〕〔i=1，2，3，4，5，6〕六個居民區(qū)的坐標(biāo)〔，〕兩個水廠向六個居民區(qū)的輸水量〔，〕〔，〕A、B水廠的坐標(biāo)各居民區(qū)所需的水量各居民區(qū)距離水廠的位置四、問題分析通過簡單的分析可以的知，總的用水量為74噸，而A、B兩廠的總進(jìn)水量為80噸，所以B兩廠的規(guī)模只能為〔30，50〕、〔40，40〕、〔50，30〕三種方式。對于問題一，是典型的線性最優(yōu)化問題，我們分三種方式對其求解。而對于問題二，我們那么是采用將完全不同的模型：首先，利用聚類算法思想，把六個居民點化分成為兩個區(qū)域，然后利用重心選址法初步判斷和偏微分法求解地方法，分別對A、B兩個水廠的位置進(jìn)行確定。五、模型的建立與求解問題一：一、模型的建立〔線性最優(yōu)化〕將從A、B〔i=1，2〕兩個水廠，向居民區(qū)1、2、3、4、5、6〔j=1，2，3，4，5，6〕送水量分別定義為。即水廠i，向用戶區(qū)j的供水量為。由乘法原那么可得，這里有十二個決策變量分別為、、、、、、、、、、、。居民點123456位置012345454412距離A廠11124.424.47距離B廠33.163232.05表二由問題所給出的居民點、水廠的坐標(biāo)，以及對模型的假設(shè)，可以計算出各水廠與各居民點的供水距離。由上面的問題分析，以及模型的假設(shè)，可知，要求總的本錢〔〕最低，于是有：Min=1.05*〔+++2+4.42+4.47+3+3.16+3+3+2+2.05〕1、對于第一種情況〔水廠的規(guī)模為30，50〕，其約束條件為：①居民需求量約束：x11+x21=10；x12+x22=11；x13+x23=8；x14+x24=15；x15+x25=8；x16+x26=22；②水廠供水量約束：x11+x12+x13+x14+x15+x16<=30；x21+x22+x23+x24+x25+x26<=50；2、對于第二種情況〔水廠的規(guī)模為40，40〕，其約束條件為：①居民需求量約束：x11+x21=10；x12+x22=11；x13+x23=8；x14+x24=15；x15+x25=8；x16+x26=22；②水廠供水量約束：x11+x12+x13+x14+x15+x16<=30；x21+x22+x23+x24+x25+x26<=50；3、對于第三種情況〔水廠的規(guī)模為50，30〕，其約束條件為：①居民需求量約束：x11+x21=10；x12+x22=11；x13+x23=8；x14+x24=15；x15+x25=8；x16+x26=22；②水廠供水量約束：x11+x12+x13+x14+x15+x16<=30；x21+x22+x23+x24+x25+x26<=50；二、模型的求解〔lingo〕把所有的約束條件作出線性規(guī)劃的模型，對取最優(yōu)化解，輸入lingo求解，求出結(jié)果如下：第一種：Globaloptimalsolutionfound.Objectivevalue:134.6898Totalsolveriterations:1VariableValueReducedCostX1110.000000.000000X1211.000000.000000X138.0000000.000000X140.0000000.000000X150.0000001.420000X160.0000002.412000X210.0000002.000000X220.0000002.160000X230.0000002.000000X2415.000000.000000X258.0000000.000000X2622.000000.000000第二種：Globaloptimalsolutionfound.Objectivevalue:134.6898Totalsolveriterations:1VariableValueReducedCostX1110.000000.000000X1211.000000.000000X138.0000000.000000X145.0000000.000000X150.0000001.420000X160.0000002.412000X210.0000002.000000X220.0000002.160000X230.0000002.000000X2410.000000.000000X258.0000000.000000X2622.000000.000000第三種：Globaloptimalsolutionfound.Objectivevalue:134.6898Totalsolveriterations:0VariableValueReducedCostX1110.000000.000000X1211.000000.000000X138.0000000.000000X1415.000000.000000X150.0000001.491000X160.0000002.532600X210.0000002.100000X220.0000002.268000X230.0000002.100000X240.0000000.000000X258.0000000.000000X2622.000000.000000三、結(jié)果分析〔三種方案〕可知三種方案的最低本錢是一樣的，不同點在于對于第四居民點的供水分配：當(dāng)水廠的規(guī)模為30，50時，全部由B水廠供給；當(dāng)水廠的規(guī)模為40，40時，A廠供給5萬噸，B廠供給10萬噸；當(dāng)水廠規(guī)模為50，30時，全部由A廠供給。又由于，假設(shè)水廠的本錢與規(guī)模無關(guān)，所以以上三種方案都是可行的。方案一：A水廠的規(guī)模為30萬噸，B水廠的規(guī)模為50萬噸；居民區(qū)1、2、3均由水廠A來供水，居民區(qū)4、5、6由B水廠來供水。方案二：A水廠的規(guī)模為40萬噸，B水廠的規(guī)模為40萬噸；居民區(qū)1、2、3均由水廠A來供水，居民區(qū)4，由A〔5萬噸〕、B〔10萬噸〕一起來供水，居民區(qū)5、6由水廠B來供水。方案三：A水廠的規(guī)模為50萬噸，B水廠的規(guī)模為30萬噸；居民區(qū)1、2、3、4均由水廠A來供水，居民區(qū)5、6那么由B來供水。三種方案的，供水本錢均為134.6898萬元。問題二：一、模型的建立〔重心法〕這是一個典型的選址問題，由于要選擇兩個水廠，根據(jù)聚類算法的思想，即同一類對象的相似度較高，而不同類的對象相似度較小的原理，需要將需求點劃分成兩個區(qū)域。1.劃分區(qū)域：首先，在坐標(biāo)紙上描繪出說有的需求區(qū)〔這里指居民區(qū)〕，并把所有需求區(qū)，用直線連接起來，以距離為邊做出一個完全圖，如下圖：圖一居民區(qū)110221.41403321.4104432.231055553.6053.160665.3853.6052.8282.2360表三然后，根據(jù)它們彼此的距離〔如表三所示〕，先刪除距離最大的邊，然后再刪除余下邊中距離最大的，依次進(jìn)行下去，直到圖被分為兩個彼此別離的圖像，如下列圖所示：圖二分為兩個區(qū)域，根據(jù)用水量和供水量可知，A廠與B廠的供水量只能為50萬噸，三十萬噸。然后分別對A、B廠進(jìn)行求解。2.公式〔重心法選址〕的推導(dǎo)：假設(shè)有n個居民點，居民點的坐標(biāo)為〔，〕，水廠的位置為〔,〕,那么供水本錢為：其中，A為單位距離的供水本錢，為兩點間的距離，為供水量。按重心法，將各居民區(qū)視為有重量的質(zhì)點，為各質(zhì)點的等效重量，重心是到各質(zhì)點距離最短距離的點，這樣，尋求水廠的地址問題，就轉(zhuǎn)化為求重心坐標(biāo)的問題，所以接下來就是解決求解重心的問題。假設(shè)各個質(zhì)點的等效質(zhì)量為G，根據(jù)重心的特征，可知，等效重量在重心對遠(yuǎn)點的力矩等于各質(zhì)點在面上的力矩之和，即：由于X軸與Y軸互相垂直，為不相關(guān)變量，所以可以把力矩延著X軸、Y軸分解，即重心對X軸、Y軸的力矩，等于各質(zhì)點對X軸、Y軸的力矩之和。那么可以得到：又因為G為等效質(zhì)量，所以?？偵峡傻茫骸?〕〔，〕就為所要求解的重心，也就是水廠的最優(yōu)位置。二、模型的求解〔Excle表格〕比照重心法，中心坐標(biāo)的求解，比擬簡單，所以本論文選擇Excle表格對其求解，A、B兩廠的求解數(shù)據(jù)與過程分別見表四和表五。對于第一塊區(qū)域〔數(shù)據(jù)如表四所示〕：居民區(qū)一居民區(qū)二居民區(qū)三居民區(qū)四∑〔求和〕x坐標(biāo)0123y坐標(biāo)4544分配量〔質(zhì)量〕101181544X*質(zhì)量011164572Y*質(zhì)量40553260187表四數(shù)據(jù)帶入公式〔1〕，可以求出=1.6363，=4.25。對于第二個區(qū)域〔數(shù)據(jù)如表五所示〕：居民區(qū)五居民區(qū)六∑〔求和〕x坐標(biāo)45y坐標(biāo)12分配量〔質(zhì)量〕82230X*質(zhì)量32110142Y*質(zhì)量84452數(shù)據(jù)帶入公式〔1〕，可以求出=4.73，=1.733。三、模型的分析〔結(jié)果比擬〕：經(jīng)過分析可以得知，雖然重心法處理問題，比擬簡單處理的數(shù)據(jù)比擬少，把二元變量轉(zhuǎn)化為易求的一元變量。但是，結(jié)果是否就是最優(yōu)解呢？為了驗證這一方法的可行性，我們新建了一個二元方程模型，并對它進(jìn)行作圖、求解。我們依然根據(jù)聚類算法的思想，把區(qū)域化作兩個區(qū)域〔詳細(xì)見上面重心法模型〕，然后，再分開進(jìn)行求解，對于假設(shè)A水廠的坐標(biāo)為〔，〕，那么對于A廠的本錢為：同理，對于B廠本錢為：對于這兩個二元函數(shù)，我們就是要求解其最小指。本論文，用matlab軟件，做出了，的分別關(guān)于〔，〕，〔，〕三維網(wǎng)狀圖，分別如圖三、圖四〔見附表〕所示：圖三圖四通過，對圖標(biāo)的分析，本論文發(fā)現(xiàn)重心法的結(jié)果與實際結(jié)果有誤差。所以，本論文對重心法重新分析：在重心法中，使用了力矩的概念，在物理學(xué)中，力矩是一個矢量，所以，應(yīng)用矢量方程表示重心和各質(zhì)點的力矩關(guān)系，應(yīng)該是一個矢量表達(dá)式：因為，Z是費(fèi)用，并非是一個向量表達(dá)式，所以：所以，“重心法”因為有矢量運(yùn)算(不做詳細(xì)說明)，并不是選址的最優(yōu)選法。四、模型的重建〔二元函數(shù)最小值〕：本論文重建模型，以最低費(fèi)用為標(biāo)準(zhǔn)，建立一個關(guān)于坐標(biāo)的二元函數(shù)：〔2〕當(dāng)Z取到最小值時，誰對應(yīng)的〔X，Y〕就是要選的水廠位置。所以，問題變成了求解復(fù)雜二元函數(shù)的最值，以及所對應(yīng)的〔X，Y〕求解。五、模型的二次求解〔matlab求解〕：本論文使用matlab對其求解。由于這是一個比擬復(fù)雜的二元函數(shù)，直接求解要求解Z的高次偏微分，而且使用matlab的“fmin函數(shù)”求最值時，軟件顯示“無法求解”。所以，最后本論文采用“迭代法”進(jìn)行求解，即遍舉所有的〔，〕，選出他們求出的Z最小值，同時，輸出他們所對應(yīng)的〔，〕?！渤绦蛉绺奖矶尽吵绦蜉敵龅膠1為第一個點的最小費(fèi)用，〔a1，b1〕為A廠的坐標(biāo)；z2為第二個點的最小費(fèi)用，〔a2，b2〕為B廠的坐標(biāo)。六、結(jié)果分析：通過，軟件的求解我們得出的最后結(jié)果是A廠〔2，4〕，B廠〔5，1〕。〔其具體結(jié)果見附表三〕花費(fèi)的費(fèi)用一共為58.5561.其相對第一個模型的結(jié)果，在圖上的擬合度更高。六、模型的評價與推廣對于第一個問題，線性最優(yōu)化方法〔模型〕已經(jīng)成為解決這一類問題的最正確方法，也是一般的通用的方法。對于第二個問題的第一個模型〔重心法選址〕，由于矢量的關(guān)系，其運(yùn)算結(jié)果會有所出入，但是，由于其運(yùn)算的簡單，適用于處理數(shù)據(jù)數(shù)據(jù)特別大，而且選址精確不是很高，再配合其他檢測、驗證模型，也可以得到比擬精確的地址。第二個模型〔二元函數(shù)取極值〕，是解決選址問題的最根本、最準(zhǔn)確的方法，但是鑒于其運(yùn)算中會出現(xiàn)多元微分求偏微分的問題，所以對于數(shù)據(jù)較多、較大的選址問題，那么是太過復(fù)雜，不適宜使用。所以，對于數(shù)據(jù)大、精確高的選址問題，要尋求更好的方法。還有，對于三個、四個······更多的水廠選址問題，也要分成多個區(qū)域，依次求解。參考文獻(xiàn)：魯小雪等雙配中心選址方法《物流科技》2010年第二期p29-33；路曉春等關(guān)于配送中心的重心選址方法的研究《北方交通大學(xué)學(xué)習(xí)報》2000年12月第24卷第6期p108-110；姜啟源等數(shù)學(xué)建模高等教育出版社2006年；王強(qiáng)等高等數(shù)學(xué)高等教育出版社2001年；七、附件一問題一的求解問題〔三個文件〕：model:min=1.05*(x11+x12+x13+2*x14+4.42*x15+4.47*x16+3*x21+3.16*x22+3*x23+2*x24+3*x25+2.058*x26);x11+x21=10;x12+x22=11;x13+x23=8;x14+x24=15;x15+x25=8;x16+x26=22;x11+x12+x13+x14+x15+x16<=30;x21+x22+x23+x24+x25+x26<=50;endmodel:min=1.05*(x11+x12+x13+2*x14+4.42*x15+4.47*x16+3*x21+3.16*x22+3*x23+2*x24+3*x25+2.058*x26);x11+x21=10;x12+x22=11;x13+x23=8;x14+x24=15;x15+x25=8;x16+x26=22;x11+