多階段決策過(guò)程最優(yōu)化問(wèn)題研究

劉義山，李驥昭

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

多階段決策過(guò)程最優(yōu)化問(wèn)題研究

劉義山，李驥昭

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

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

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

0 引言

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

1 多階段決策問(wèn)題探討

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

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

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

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

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

1.1 第三階段決策

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

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

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

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

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

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

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

1.2 第二階段決策

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

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

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

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

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

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

1.3 第一階段決策

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

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

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

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

表6 使3個(gè)地區(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個(gè)階段的銷售總收入達(dá)到最大的最優(yōu)策略Tab.8 Optimum decision of maximizing total sale revenue in 3 phases

2 結(jié)束語(yǔ)

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

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

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

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

［4］ 謝識(shí)予.經(jīng)濟(jì)博弈論［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áng)人，平頂山工業(yè)職業(yè)技術(shù)學(xué)院文教部副教授，主要研究方向:數(shù)學(xué)教育.