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

(四川大學 四川 成都 610065)

一、無約束優化方法

(一)最速下降法

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

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

(二)牛頓法

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

二、平面選址問題

(一)平面選址問題概述

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

(二)溫江超市選址問題

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

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

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

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

根據選址模型建立溫江超市選址函數為：

注：為方便計算數據整體除以100。

三、Matlab求解

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

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

基于最速下降法MATLAB求解結果如下：

ans=0.0320 0.5200

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

圖2 最速下降法輸出圖

從輸出圖可以發現，最速下降法是線性收斂，接近最優值收斂速度減慢，迭代次數增多。

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

基于牛頓法求解結果如下：

k=1

x0=0.0320

0.5200

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

(三)超市最優位置

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

圖3 超市具體位置圖

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

(一)最速下降法與牛頓發的優缺點

1.最速下降法

優點是程序設計簡單，工作量少，存儲變量較少，初始點要求不高；

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

2.牛頓法

優點是收斂速度快；

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

缺點是對初始點要求嚴格，方向構造困難，計算復雜且占用內存較大。

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

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

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

而如果目標函數有連續二階偏導數,牛頓法可以快速收斂到問題的極小點

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

五、總結

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

本文通過最速下降法及牛頓法在實際生活中的應用研究,以及對最速下降法及牛頓法的比較，以期能在系統工程優化、經濟金融等多個應用領域給讀者一點啟發,為決策者提供一定的參考依據,將理論研究更好地為實際生產生活服務。

【參考文獻】

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

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

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

[4]張天賜.平面選址問題概述[J].運籌學學報,1985,1:001.

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

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