劉義山，李驥昭

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

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

劉義山，李驥昭

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

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

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

0 引言

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

1 多階段決策問題探討

例如，某汽車公司準(zhǔn)備在華北、華東、華南3個地區(qū)建立標(biāo)準(zhǔn)的四位一體的汽車銷售樣板店.由于資金有限，只能建3個樣板店.為了達到公司銷售收入最大的目的，公司不限制在各個地區(qū)建立樣板店的數(shù)目.因此，每個地區(qū)最多建3個樣板店.每個地區(qū)預(yù)期創(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萬元的銷售收入.這個問題的目標(biāo)函數(shù)是在建樣板店的個數(shù)有限的條件下，如何建店使公司的銷售收入總額最大.它的數(shù)學(xué)表達形式是

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

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

1.1 第三階段決策

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

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

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

表2中有動態(tài)規(guī)劃中的常用符號S3，x3，R3.S3為第三階段的可達狀態(tài)的集合，指當(dāng)一、二階段做出建店決策后第三階段到最后階段(仍為第三階段)剩余的建店指標(biāo).在這個問題中，可達狀態(tài)是指從每個階段到最后階段剩余建樣板店的指標(biāo).從表2中可以看出，第三階段有4個可達狀態(tài)，也就是當(dāng)一、二階段決策后，第三階段剩余的建店指標(biāo)可能為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)的集合，指當(dāng)?shù)谝浑A段作出建店決策后第二階段到最后階段(第三階段)剩余的建店指標(biāo).x2和R2代表在不同的狀態(tài)下第二階段的決策和銷售收入.R3第4、5列反映的是在決定第二階段的建店數(shù)目的條件下，第三階段剩余建店的指標(biāo)和相應(yīng)第三階段的最優(yōu)決策.第6列表示二、三兩個階段的銷售收入.從4、5列可以看出，第三階段剩余的建店指標(biāo)是第一階段決策后從第二階段到最后階段剩余的建店指標(biāo)和第二階段決定建店的個數(shù)的函數(shù).例如，如果從第二階段到最后階段(第三階段)剩余建店的指標(biāo)為1，而且決定在第二階段華東建店的個數(shù)為0，那么第三階段剩余建店的指標(biāo)為1.

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

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

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

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

1.3 第一階段決策

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

比如，表6中狀態(tài)S1為第一階段到第三階段剩余的建店指標(biāo)，決策x1決定建店的個數(shù)，R1為華北銷售收入，R2+R3為第二階段最優(yōu)決策下的銷售收入，R1+R2+R3為三個階段的銷售總收入.因為S1=3，如果決定在華北建店的個數(shù)x1=1，那么從第二階段到第三階段剩余建店的指標(biāo)為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為第一階段到第三階段剩余的建店指標(biāo)，決策x1為決定建店的個數(shù)，R1為華北銷售收入，狀態(tài)S2為第二階段到第三階段剩余的建店指標(biāo)，第二階段最優(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 結(jié)束語

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

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

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

［3］ 施錫銓，韓其恒.博弈論［M］.上海:上海財經(jīng)大學(xué)出版社，2002.

［4］ 謝識予.經(jīng)濟博弈論［M］.上海:復(fù)旦大學(xué)出版社，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ù)學(xué)院文教部副教授，主要研究方向:數(shù)學(xué)教育.