啟發(fā)式伏格爾法求解多階段決策問題

孫鵬飛，劉建永

(解放軍理工大學(xué) 野戰(zhàn)工程學(xué)院，南京　210007)

?

啟發(fā)式伏格爾法求解多階段決策問題

孫鵬飛，劉建永

(解放軍理工大學(xué) 野戰(zhàn)工程學(xué)院，南京210007)

摘要：針對動態(tài)規(guī)劃求解多階段決策問題存在的一些不足，首次創(chuàng)新性地將啟發(fā)式伏格爾法運用到求解多階段決策問題中，給出相關(guān)定義，列出其算法步驟，并分析其時間復(fù)雜度；通過案例具體說明啟發(fā)式伏格爾法求解過程，總結(jié)該算法優(yōu)缺點，為研究多階段決策問題提供一種新型并且具有實效的思路方法。

關(guān)鍵詞：啟發(fā)式伏格爾法；時間復(fù)雜度；多階段決策問題

Citation format:SUN Peng-fei，LIU Jian-yong.Heuristic Vogel Method for Solving Multistage Decision-Making Problems [J].Journal of Ordnance Equipment Engineering,2016(3):171-174.

求解多階段決策問題(Multistage Decision-Making Problems)，最常用的求解方法是動態(tài)規(guī)劃(Dynamic Programming)方法[1-2]。實踐也證明了求解此類問題用動態(tài)規(guī)劃方法比線性規(guī)劃方法或非線性規(guī)劃方法更加有效[3-4]。但利用動態(tài)規(guī)劃求解多階段決策問題，存在著一些條件限制，算法復(fù)雜度也較大，并且只適用維數(shù)相對較低的問題[5-6]?，F(xiàn)實中，在考慮決策靈活機動和方案最優(yōu)時，并不一定要嚴(yán)格采用最優(yōu)方案，有時決策容易、易于改動的次優(yōu)方案可能更適合現(xiàn)實需求。本文中考慮是否有較好的啟發(fā)式算法(Heuristic Algorithm)[7]，在解決此類問題時更加地靈活機動、易于操作。

查閱國內(nèi)外文獻資料[8-10]，伏格爾法(Vogel)主要應(yīng)用于求解運輸問題和指派問題，目前還未有關(guān)于伏格爾法在求解多階段決策問題方面的相關(guān)研究。本文探索利用啟發(fā)式伏格爾法(Heuristic Vogel Method，HVM)求解多階段決策問題，并分析其時間復(fù)雜度。

1基于啟發(fā)式伏格爾法求解最短路線問題

1.1啟發(fā)式伏格爾法基本概念

伏格爾法主要應(yīng)用于運輸問題求解最低運費，它是確定運輸問題初始調(diào)運方案中近似程度最好的一種近似方法，這種方法得出的結(jié)果很接近最優(yōu)調(diào)運方案。伏格爾法在最小元素的基礎(chǔ)上考慮，某一產(chǎn)地的產(chǎn)品若不能按照最小運費就近供應(yīng)，就考慮次小運費，這就產(chǎn)生一個差額，稱為罰金成本。罰金成本越大，說明不按最小運費調(diào)運時，運費增加越多。因而對罰金成本最大元素，就應(yīng)該采用最小運費調(diào)運[1]。

啟發(fā)式伏格爾法(HVM)可以定義：在可接受的花費(指計算時間和空間)條件下，給出待解決的組合優(yōu)化問題一個經(jīng)驗構(gòu)造或直觀性伏格爾法求解，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計[7]。

1.2啟發(fā)式伏格爾法算法步驟

假設(shè)每階段所有的狀態(tài)點與隨后階段的狀態(tài)點間均有路線，如若沒有路線，可假定其路線長度為∞，過程只有一個始點Os和一個終點Oe。

啟發(fā)式伏格爾法求解最短路線問題的算法步驟如下：

第1步，確定過程的始點Os、終點Oe、階段數(shù)n、狀態(tài)總數(shù)N，按始點Os至終點Oe順序，為每個狀態(tài)點排序，并確定第i狀態(tài)屬于哪個階段以及該狀態(tài)的決策數(shù)目mi；

第2步，計算各個狀態(tài)點的決策集中最小值與次最小值的差ci(如若狀態(tài)點只有一種決策，即不存在次最小值，則規(guī)定其罰金成本為0；若狀態(tài)點沒有決策，則不將其計入集合C中)，形成集合C；

第3步，在集合C中找出最大值，并選擇此狀態(tài)點為決策點(如若存在多個最大值，則只選取按照狀態(tài)點的排序順序最靠前的依次作為決策點)，選取此狀態(tài)點的決策集中的最小值作為此狀態(tài)點的決策；

第4步，從此階段及下階段中，除去此次決策的起、始狀態(tài)點外的其余狀態(tài)點，從集合C中除去此次決策的起、始狀態(tài)點，更新集合C；

第5步，重復(fù)第2、4步工作，直至集合C不再包含任何狀態(tài)點的罰金成本，則所有階段中均有且僅有一個狀態(tài)已做出決策，形成最終策略。

1.3啟發(fā)式伏格爾法時間復(fù)雜度

算法第1步主要判斷過程及狀態(tài)，時間復(fù)雜度為1。

算法第3步時間復(fù)雜度計算包括尋找最大值以及為該狀態(tài)點做出決策、形成階段路線兩個方面，時間復(fù)雜度：(N-1)+1。

2實例應(yīng)用

2.1實際案例

某工廠自國外進口一部精密機器，由機器制造廠到出口港有3個港口可供選擇，而進口港又有3個可供選擇，進口后可經(jīng)由兩個城市到達目的地，其間的運輸成本如圖1中所標(biāo)數(shù)字，求出運費最低的路線。

圖1　路線網(wǎng)絡(luò)圖

2.2啟發(fā)式伏格爾法求解

根據(jù)網(wǎng)絡(luò)圖以及啟發(fā)式伏格爾法算法步驟，可以確定過程的始點為A，終點為E，共有4個階段，10個狀態(tài)點。為10個狀態(tài)點依次排序，如對狀態(tài)點B1，i=2。

第二步，計算各個狀態(tài)點的決策集中最小值與次最小值的差。如對狀態(tài)點B1，B1共有3條可選路線，其中最小值為40(路線B1→C2)，次最小值為60(路線B1→C3)，二者之差，即c2=20。求出每個狀態(tài)點的最小值與次最小值之差，形成集合C，初始的集合C中一共包括[A、B1、B2、B3、C1、C2、C3、D1、D2]這9個狀態(tài)點的罰金成本。如圖2中各狀態(tài)點上的括號內(nèi)數(shù)值所示：

圖2　初始集合C

從集合C中找出最大值，B3、C1、C23個狀態(tài)點的最大值，均為30。按照本文的算法規(guī)則，選擇序號在前的狀態(tài)點B3作為決策點，并將狀態(tài)點B3的3條可選路線中最短路線B3→C2作為該階段路線，如圖3所示。

圖3　狀態(tài)B3作為首選點

圖4　更新后的集合C

圖5　路線C2→D2的選擇

圖6　路線A→B3的選擇

圖7　路線D2→E的選擇

從集合C中除去此次決策的起始狀態(tài)點D，更新后的集合C中不再包含任何狀態(tài)點的罰金成本，即所有階段均有且僅有一個狀態(tài)已做出決策， 完成了此過程路線的確定策略。最后得到路線方案：

A→B3→C2→D2→E

2.3結(jié)果分析

啟發(fā)式伏格爾法方案的路線運輸成本為110，利用動態(tài)規(guī)劃方法求解進行驗證(具體求解過程未在本文列出)，110為最優(yōu)結(jié)果。

由此總結(jié)出啟發(fā)式伏格爾法求解的特點：求解結(jié)果清晰明了，圖上標(biāo)示直觀方便；階段越多或狀態(tài)決策數(shù)目越多時，越是后面的求解過程中，越能體現(xiàn)出其計算時間優(yōu)越性。與動態(tài)規(guī)劃求解多階段決策問題的按順序或反序逐個階段進行決策，最后得出從全局出現(xiàn)的最優(yōu)決策相比，本方法并不能保證從兩端逐個階段進行，而是選取罰金成本最大值的狀態(tài)點開始，而此狀態(tài)點可能處于中間某個狀態(tài)，所以不能保證每次都能求出最優(yōu)決策，而且無法直觀驗證其結(jié)果是否為最佳方案。

3結(jié)論

本文將啟發(fā)式伏格爾法思想應(yīng)用到求解多階段決策問題中，方法簡便，理論可靠，而且結(jié)果清晰明了，研究前景開闊，在實際運用中取得了良好效果。本文實例比較簡單，在實際中有可能存在多個始、終點的情況，或是狀態(tài)不滿足無后效性的情況，在這些特殊情況下，本算法可能會得到很壞的答案或效率極差，這就違背了算法初衷。

本文下一步工作將在兩方面展開深入研究，一是對該算法求解的實效性以及算法復(fù)雜度進行研究，改善優(yōu)化算法；二是完善規(guī)范算法步驟，實現(xiàn)算法計算機編程，使其達到在較為復(fù)雜的情況下，也能滿足在計算機運行的準(zhǔn)確性和穩(wěn)定性。

參考文獻：

[1]錢頌迪.運籌學(xué)[M].3版.北京：清華大學(xué)出版社，2005.

[2]BELLMAN R E,DREYFUS S E.Applied Dynamic Programming[M].Princeton University Press,1962.

[3]SVEN D.Nonlinear and Dynamic Programming[M].Springer-Verlag,1975.

[4]KUMAR P,SINGH N,TEWARI N K.A nonlinear goal programming model for multistage,multiobjective decision problems with application to grouping and loading problem in a flexible manufacturing system[J].European Journal of Operational Research,1991,53(2):166-171.

[5]YANG MAO,LI YONG,SU LI.Opportunistic spectrum sharing in software defined wireless network[J].Journal of Systems Engineering and Electronics,2014,25(6):934-941.

[6]LI YONG-YAN,GAO WEN,WU CHUNMING.Deployment of Sensors in WSN:An Efficient Approach Based on Dynamic Programming[J].Chinese Journal of Electronics,2015,24(1):33-37.

[7]EDWARD A，SILVER,VICTOR R.A tutorial on heuristic methods[J].European Journal of Operational Research,1980(5):153-162.

[8] 汪潘義.改進的伏格爾法及其應(yīng)用[J].統(tǒng)計與決策,2014(15):83-85.

[9]牛斌,趙龍.基于Vogel的車輛調(diào)用優(yōu)化算法研究[J].計算機與現(xiàn)代化,2011(5):7-10.

[10]張敏,張子杰.伏格爾法在退化性運輸問題中的應(yīng)用方法[J].河北工程技術(shù)高等?？茖W(xué)校學(xué)報,2009,12(4):21-23.

(責(zé)任編輯唐定國)

Heuristic Vogel Method for Solving Multistage Decision-Making Problems

SUN Peng-fei，LIU Jian-yong

(College of Field Engineering, PLA University of Science and Technology, Nanjing 210007, China)

Abstract:To solve the shortages appeared in the process of solving multistage decision-making problems with dynamic programming, Heuristic Vogel method was creatively applied in solving this kind of issues for the first time. Its definitions and algorithm steps were provided and its time complexity was analyzed. This paper illustrated the solving process of Heuristic Vogel method with a case, and summarized its advantages and disadvantages and provided a new and effective method for the research of solving multistage decision-making problems.

Key words:Heuristic Vogel method; time complexity; multistage decision-making problem

文章編號：1006-0707(2016)03-0171-04

中圖分類號：E072

文獻標(biāo)識碼：A

doi:10.11809/scbgxb2016.03.041

作者簡介：孫鵬飛(1989—)，男，主要從事指揮自動化與戰(zhàn)場環(huán)境數(shù)字化研究。

收稿日期：2015-09-23；修回日期：2015-10-09

本文引用格式：孫鵬飛，劉建永.啟發(fā)式伏格爾法求解多階段決策問題[J].兵器裝備工程學(xué)報，2016(3):171-174.

【基礎(chǔ)理論與應(yīng)用研究】