劉義山，李驥昭

(平頂山工業(yè)職業(yè)技術學院文教部，河南平頂山 467001)

多階段決策過程最優(yōu)化問題研究

劉義山，李驥昭

(平頂山工業(yè)職業(yè)技術學院文教部，河南平頂山 467001)

討論了動態(tài)規(guī)劃的基本原理和基本方法，通過解決建設汽車樣板店的一個三階段決策問題說明其應用.

多階段決策;單階段決策;動態(tài)規(guī)劃;優(yōu)化算法;最優(yōu)決策

0 引言

在實踐中，常常會遇到這樣的決策問題［1－4］:由于過程的特殊性，可以將決策的全過程依據(jù)時間或空間劃分為若干個相互聯(lián)系的階段.動態(tài)規(guī)劃方法的關鍵是將多階段的決策問題變換成一系列的單階段問題，并逐一求解.多階段的決策過程很難直觀地描述，本文通過一個實例來說明動態(tài)規(guī)劃解決多階段決策問題的方法和過程.

1 多階段決策問題探討

例如，某汽車公司準備在華北、華東、華南3個地區(qū)建立標準的四位一體的汽車銷售樣板店.由于資金有限，只能建3個樣板店.為了達到公司銷售收入最大的目的，公司不限制在各個地區(qū)建立樣板店的數(shù)目.因此，每個地區(qū)最多建3個樣板店.每個地區(qū)預期創(chuàng)造的銷售收入見表1.

表1 每個地區(qū)可能創(chuàng)造的銷售收入Tab.1 Possible sale revenue created by each area

從表1中可以看出，如果沒有在華北和華東地區(qū)建樣板店，那么這兩個地區(qū)的銷售收入為0.如果沒有在華南地區(qū)建樣板店，華南地區(qū)仍可以通過訂購系統(tǒng)獲得每月2萬元的銷售收入.這個問題的目標函數(shù)是在建樣板店的個數(shù)有限的條件下，如何建店使公司的銷售收入總額最大.它的數(shù)學表達形式是

其中R1，R2，R3分別代表華北、華東和華南的銷售收入，x1，x2，x3表示決定在這3個地區(qū)建立樣板店的數(shù)目.

為了解決這個問題，首先定義一下階段.將在華北地區(qū)建多少樣板店作為問題第一階段的決策，將在華東地區(qū)建多少樣板店作為問題第二階段的決策，將在華南地區(qū)建多少樣板店作為問題第三階段的決策.假設這就是決策的先后順序.顯然這是一個三階段決策過程的最優(yōu)化問題.用動態(tài)規(guī)劃來解這個問題，就是要把這個三階段的決策問題化為3個較容易解決的單階段決策問題.每個單階段的決策是整個決策過程的一個環(huán)節(jié)，因為它不僅決定該階段的效果(銷售收入)，還影響到下階段的初始狀態(tài)(剩余的建店指標).在求解該問題過程中，從最后一個階段開始逐階段反向遞推，找到銷售收入最大的方案，當遞推到第一階段時，也就找到了全過程的最優(yōu)方案.這種從后向前逆推的方法叫逆序解法.

1.1 第三階段決策

將在華南地區(qū)建多少樣板店作為問題第三階段的決策.在動態(tài)規(guī)劃中假設第三階段的決策是決策過程中的最終決策，因此，如果將在華東、華北地區(qū)建樣板店作為規(guī)劃的第二階段和第一階段，那么在華南地區(qū)建幾個樣板店的決策是建立在另兩個地區(qū)已決定建店的個數(shù)的基礎上的.第三階段可能的建店方案如表2，其中S3表示第三階段剩余的建店指標，x3表示決定建店的個數(shù).

表2 第三階段可能的建店方案Tab.2 Possible scheme of building stores in phase 3

從表2可以看出，如果3個樣板店已經決定建在另外兩個地區(qū)，那么第三階段剩余的建店指標為0，決策只能是在華南地區(qū)不建店，該地區(qū)的銷售收入為2萬元/月.如果已決定在另外兩個地區(qū)建2個店，那么第三階段剩余的建店指標為1，就要考慮在華南建1個店或不建店;同樣，如果在第三階段剩余的建店指標為2個，就要決定第三階段該建0個、1個或2個店;如果在第三階段剩余的建店指標為3個，就要決定在第三階段建0個、1個、2個或3個店.

表2中有動態(tài)規(guī)劃中的常用符號S3，x3，R3.S3為第三階段的可達狀態(tài)的集合，指當一、二階段做出建店決策后第三階段到最后階段(仍為第三階段)剩余的建店指標.在這個問題中，可達狀態(tài)是指從每個階段到最后階段剩余建樣板店的指標.從表2中可以看出，第三階段有4個可達狀態(tài)，也就是當一、二階段決策后，第三階段剩余的建店指標可能為0、1、2、3.x3代表在不同的狀態(tài)下第三階段的決策.R3表示在不同的決策下，第三階段(華南地區(qū))獲得的銷售收入.

動態(tài)規(guī)劃的下一步是決定每個可達狀態(tài)下的最優(yōu)決策.在這個問題中，每個狀態(tài)下的最優(yōu)決策就是獲得的銷售收入最大.每個狀態(tài)下的最優(yōu)決策如表3所示.

表3 每個狀態(tài)下的最優(yōu)決策Tab.3 Optimum decision in each status

第三階段各個狀態(tài)下的最優(yōu)決策要繼續(xù)運用到上一階段的決策中.

1.2 第二階段決策

既然第三階段最優(yōu)決策已知，進入上一階段決策，決定如何在華東地區(qū)建店.第二階段的可達狀態(tài)和可選的決策與第三階段基本相同.但是，每種狀態(tài)下的最優(yōu)決策的選擇就有不同.第二階段的可達狀態(tài)和可選決策如表4所示，R2+R3為二、三階段的銷售總收入，R3為第三階段最優(yōu)決策下的銷售收入.

表4中1、2、3列與表2數(shù)據(jù)求法相同，S2表示第二階段的可達狀態(tài)的集合，指當?shù)谝浑A段作出建店決策后第二階段到最后階段(第三階段)剩余的建店指標.x2和R2代表在不同的狀態(tài)下第二階段的決策和銷售收入.R3第4、5列反映的是在決定第二階段的建店數(shù)目的條件下，第三階段剩余建店的指標和相應第三階段的最優(yōu)決策.第6列表示二、三兩個階段的銷售收入.從4、5列可以看出，第三階段剩余的建店指標是第一階段決策后從第二階段到最后階段剩余的建店指標和第二階段決定建店的個數(shù)的函數(shù).例如，如果從第二階段到最后階段(第三階段)剩余建店的指標為1，而且決定在第二階段華東建店的個數(shù)為0，那么第三階段剩余建店的指標為1.

多階段決策問題的各個階段間的相互關系可以定義為狀態(tài)轉移方程.狀態(tài)轉移方程是確定由一個狀態(tài)到另一個狀態(tài)的演變過程.對于第k+1階段，該階段的狀態(tài)Sk+1與上階段的狀態(tài)Sk的狀態(tài)轉移規(guī)律為Sk+1=Sk－xk.例如，從第二階段到最后階段剩余建店的指標狀態(tài)S2為3，而決定在華東建店的個數(shù)x2為2，那么第三階段到最后階段(就是第三階段)剩余的建店指標狀態(tài)S3=S2－x2=1.

表4 第二階段的可達狀態(tài)和可選決策Tab.4 Accessible status and optional decision in phase 2

然后，再計算在第二階段每個可達狀態(tài)下因第二階段和第三階段的決策產生的兩個階段的銷售總收入R2+R3，并選取每個狀態(tài)下第二階段和第三階段銷售收入最大的決策為該狀態(tài)下的最優(yōu)決策，如表5所示，R3為第三階段最優(yōu)決策下的銷售收入，狀態(tài)S2為從第二階段到第三階段剩余的建店指標，狀態(tài)S3為第三階段剩余的建店指標.

表5 最優(yōu)決策的計算Tab.5 Calculation on optimum decision

1.3 第一階段決策

現(xiàn)在考慮第一階段在華北地區(qū)建樣板店，由于這是決策過程中首先決策的第一階段，所以該階段到第三階段剩余的建店指標為3個.決定在此建店的個數(shù)可以為0、1、2和3個.這時，第二階段的可達狀態(tài)就由第二階段與第一階段的狀態(tài)轉移方程S2=S1－x1決定.

比如，表6中狀態(tài)S1為第一階段到第三階段剩余的建店指標，決策x1決定建店的個數(shù)，R1為華北銷售收入，R2+R3為第二階段最優(yōu)決策下的銷售收入，R1+R2+R3為三個階段的銷售總收入.因為S1=3，如果決定在華北建店的個數(shù)x1=1，那么從第二階段到第三階段剩余建店的指標為S2=2.從表5中得出，S2=2狀態(tài)下的最優(yōu)決策是決定在華東建兩個樣板店，在華南不建店，華東和華南兩個地區(qū)的銷售收入為17萬元/月.華東和華南兩個地區(qū)的銷售收入加上華北地區(qū)建的1個樣板店的銷售收入7萬元/月，那么3個地區(qū)的總收入為24萬元/月.

第一階段的最優(yōu)決策是使3個地區(qū)的銷售總收入最大的決策，如表7所示，狀態(tài)S1為第一階段到第三階段剩余的建店指標，決策x1為決定建店的個數(shù)，R1為華北銷售收入，狀態(tài)S2為第二階段到第三階段剩余的建店指標，第二階段最優(yōu)決策下的銷售收入R2+R3，三個階段的銷售總收入R1+R2+R3.

再按照計算的順序反推回去(稱為回代或反向追蹤)，可以找到使3個階段的銷售總收入達到最大的最優(yōu)策略.如表8所示.

表6 使3個地區(qū)的銷售總收入最大的決策方案Tab.6 Decision scheme of maximizing total sale revenue of 3 areas

表7 第一階段的最優(yōu)決策Tab.7 Optimum decision of phase 1

表8 使3個階段的銷售總收入達到最大的最優(yōu)策略Tab.8 Optimum decision of maximizing total sale revenue in 3 phases

2 結束語

動態(tài)規(guī)劃把困難的多階段決策問題變換成一系列相互聯(lián)系的比較容易的單階段問題，一個個地求解，這是經典優(yōu)化方法難以做到的.動態(tài)規(guī)劃是考察解決問題的一種途徑，而不是一種特殊的算法，不像線性規(guī)劃那樣有統(tǒng)一的數(shù)學模型和算法.動態(tài)規(guī)劃可以解決各類多階段決策問題，不像其他方法局限于解決某一類問題.以上運用動態(tài)規(guī)劃的方法解決了建設汽車樣板店的一個三階段決策問題，解決問題的思路和步驟可以運用到各種動態(tài)規(guī)劃的問題中.

［1］ 張維迎，葉民強.博弈論與信息經濟學［M］.上海:上海人民出版社，1996.

［2］ 鄧成梁，馬致山，張文杰.運籌學的原理和方法［M］.武漢:華中理工大學出版社，1996.

［3］ 施錫銓，韓其恒.博弈論［M］.上海:上海財經大學出版社，2002.

［4］ 謝識予.經濟博弈論［M］.上海:復旦大學出版社，2002.

Research on Optimization Problem of Multi-phase Decision Process

LIU Yi-shan，LI Ji-zhao

(Department of Culture and Education，Pingdingshan Industrial College of Technology，Pingdingshan467001，China)

Discussed basic principle and method of dynamic program，illustrated its application by solving a threephase decision problem of building automobile model shops.

multi-phase decision;single phase decision;dynamic program;optimization algorithm;optimum decision

O221.3

A

1007－0834(2011)02－0008－04

10.3969/j.issn.1007－0834.2011.02.003

2011－04－18

劉義山(1962—)，男，河南南陽人，平頂山工業(yè)職業(yè)技術學院文教部副教授，主要研究方向:數(shù)學教育.