孫鵬飛，劉建永

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

?

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

孫鵬飛，劉建永

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2實(shí)例應(yīng)用

2.1實(shí)際案例

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

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

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

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

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

圖2　初始集合C

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

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

圖4　更新后的集合C

圖5　路線C2→D2的選擇

圖6　路線A→B3的選擇

圖7　路線D2→E的選擇

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

A→B3→C2→D2→E

2.3結(jié)果分析

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

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

3結(jié)論

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

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

參考文獻(xiàn)：

[1]錢頌迪.運(yùn)籌學(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] 汪潘義.改進(jìn)的伏格爾法及其應(yīng)用[J].統(tǒng)計(jì)與決策,2014(15):83-85.

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

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

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

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

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

中圖分類號(hào)：E072

文獻(xiàn)標(biāo)識(shí)碼：A

doi:10.11809/scbgxb2016.03.041

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

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

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

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