基于最速下降法及牛頓法的選址問題

(四川大學(xué) 四川 成都 610065)

一、無約束優(yōu)化方法

(一)最速下降法

最速下降法(steepest descent method)是以負(fù)梯度方向作為下降方向的極小化算法,又稱梯度法,特別適合于低維空間的無約束最優(yōu)化求解問題,例如,我們提出的平面選址問題就是二維空間的無約束優(yōu)化問題。

基本思想:求解無約束優(yōu)化問題minf(x),從當(dāng)前點xk出發(fā),取函數(shù)f(x)在點xk處的負(fù)梯度方向pk=-▽f(xk),即最速下降方向,得到點列{xk}滿足f(x(k+1))

(二)牛頓法

牛頓迭代法(Newton's method)它是牛頓在17世紀(jì)提出的一種在實數(shù)域和復(fù)數(shù)域上近似求解方程的方法。多數(shù)方程不存在求根公式，因此求精確根非常困難，甚至不可能，從而尋找方程的近似根就顯得特別重要。方法使用函數(shù)f(x)的泰勒級數(shù)的前面幾項來尋找方程f(x)=0的根。牛頓迭代法是求方程根的重要方法之一，其最大優(yōu)點是在方程f(x)=0的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復(fù)根，此時線性收斂，但是可通過一些方法變成超線性收斂。另外該方法廣泛用于計算機編程中。

二、平面選址問題

(一)平面選址問題概述

平面選址問題是運籌學(xué)中的一個經(jīng)典問題。好的選址可以為企業(yè)降低服務(wù)成本,提高服務(wù)質(zhì)量、服務(wù)效率,擴大利潤和市場份額等,進而影響到企業(yè)利潤和市場競爭力,甚至決定了企業(yè)的命運;差的選址往往會帶來很大的不便和損失,甚至是災(zāi)難,所以,選址問題的研究有著重大的經(jīng)濟、社會和軍事意義。一般意義下的選址問題可能是非常復(fù)雜的,涉及到時間的、空間的、自然的、社會的各種復(fù)雜條件。

(二)溫江超市選址問題

現(xiàn)要在成都市溫江增設(shè)一家超市，超市的供應(yīng)量輻射溫江第一小學(xué)、第二小學(xué)、實驗中學(xué)、實驗中學(xué)、中醫(yī)院、公園五大主要需求地，如何使超市到各個區(qū)域的距離最近，是我們要解決的問題。利用選址問題模型，在平面上已知五個位置點，使超市到平面上五個點的距離平方之和最小,即：

現(xiàn)以溫江實驗中學(xué)為中心，利用CAD繪制出超市選址前平面圖，如圖1所示。

溫江五大位置點的坐標(biāo)值根據(jù)地圖所示距離測得，中醫(yī)院(16,149)、公園(600，-100)、實驗中學(xué)(0,0)、第二小學(xué)(-350,50)、第一小學(xué)(-250,261)，單位m。

圖1 超市位置選址前平面圖

根據(jù)選址模型建立溫江超市選址函數(shù)為：

注：為方便計算數(shù)據(jù)整體除以100。

三、Matlab求解

針對溫江超市選址問題建立的函數(shù)，分別基于最速下降法及牛頓法利用Matlab軟件求解。

(一)基于最速下降法的選址問題求解

基于最速下降法MATLAB求解結(jié)果如下：

ans=0.0320 0.5200

(3)輸出圖像顯示，如圖2所示：

圖2 最速下降法輸出圖

從輸出圖可以發(fā)現(xiàn)，最速下降法是線性收斂，接近最優(yōu)值收斂速度減慢，迭代次數(shù)增多。

(二)基于牛頓法的選址問題求解

基于牛頓法求解結(jié)果如下：

k=1

x0=0.0320

0.5200

基于牛頓法，對于正定二次函數(shù)，只需迭代一次即可得到最優(yōu)值，收斂速度快。

(三)超市最優(yōu)位置

基于最速下降及牛頓法利用matlab求解，得出最優(yōu)位置點為(3.2,52)，現(xiàn)利用CAD繪制初超市具體選址位置圖，如圖3所示。

圖3 超市具體位置圖

四、最速下降法與牛頓法的比較

(一)最速下降法與牛頓發(fā)的優(yōu)缺點

1.最速下降法

優(yōu)點是程序設(shè)計簡單，工作量少，存儲變量較少，初始點要求不高；

缺點是最速下降方向是函數(shù)的局部性質(zhì)，(局部)下降快有利于搜索，(全局)迭代點沿垂直直線移動，越接近極小點，收斂越慢；線性收斂。

2.牛頓法

優(yōu)點是收斂速度快；

(1)如果G*正定,且初始點合適，算法二階收斂；(2)對正定二次函數(shù),迭代一次就可以得到極小點。

缺點是對初始點要求嚴(yán)格，方向構(gòu)造困難，計算復(fù)雜且占用內(nèi)存較大。

(1)對多數(shù)問題算法不是整體收斂的;(2)在每次迭代中需要計算Gk;(3)每次迭代時需要求解線性方程組;該方程組可能是奇異或病態(tài)的;求出的方向可能不下降;(4)收斂于鞍點或極大點的可能性與收斂于極小點的可能性一致。

(二)最速下降法與牛頓法的收斂速度

最速下降法的迭代點在向極小點靠近的過程中走的是曲折路線,易產(chǎn)生鋸齒現(xiàn)象,導(dǎo)致每次迭代行進的距離變得越來越小,收斂速度不快.

而如果目標(biāo)函數(shù)有連續(xù)二階偏導(dǎo)數(shù),牛頓法可以快速收斂到問題的極小點

牛頓法是二階收斂，最速下降法是線性收斂。但是牛頓法只有初值靠近真值時才收斂，最速下降法理論上無論初值如何都收斂。二者各有優(yōu)劣。

五、總結(jié)

本文主要研究了基于最速下降法和牛頓法的平面選址問題的求解方法,選擇出溫江超市的具體位置，并對最速下降法及牛頓法進行比較，用最優(yōu)方法進行選址。但在實際選址問題中不僅要考慮最短距離，還有各個影響因素，如地區(qū)經(jīng)濟、區(qū)域規(guī)劃、文化環(huán)境、消費時尚、可見度和形象特征等。綜合以上因素選擇出最優(yōu)地理位置。

本文通過最速下降法及牛頓法在實際生活中的應(yīng)用研究,以及對最速下降法及牛頓法的比較，以期能在系統(tǒng)工程優(yōu)化、經(jīng)濟金融等多個應(yīng)用領(lǐng)域給讀者一點啟發(fā),為決策者提供一定的參考依據(jù),將理論研究更好地為實際生產(chǎn)生活服務(wù)。

【參考文獻】

[1]李廷鋒.基于最速下降法的平面選址問題應(yīng)用研究[J].科技資訊,2011(36):14-14.

[2]于琛.關(guān)于牛頓法與最速下降法的注記[J].東北師大學(xué)報(自然科學(xué)版),1964,1:001.

[3]戴彧虹,劉新為.線性與非線性規(guī)劃算法與理論[J].運籌學(xué)學(xué)報,2014,18(1):69-92.

[4]張?zhí)熨n.平面選址問題概述[J].運籌學(xué)學(xué)報,1985,1:001.

[5]林詒勛,尚松蒲.平面上的點—線選址問題[J].運籌學(xué)學(xué)報,2002,6(3):61-68.

[6]馬元婧,韓波.非線性方程組的一種修正牛頓法及其連續(xù)型[D][D].哈爾濱工業(yè)大學(xué),2009.