基于馬爾可夫過程的線性規(guī)劃方法探討

邱祎，董彥彥

（1.河南財政金融學(xué)院，鄭州451464；2.鄭州大學(xué)體育學(xué)院，鄭州450044）

基于馬爾可夫過程的線性規(guī)劃方法探討

邱祎1，董彥彥2

（1.河南財政金融學(xué)院，鄭州451464；2.鄭州大學(xué)體育學(xué)院，鄭州450044）

馬爾可夫過程作為研究無后效性動態(tài)演進(jìn)過程的統(tǒng)計方法，在經(jīng)濟(jì)管理預(yù)測工作中占有非常重要的地位。目前線性規(guī)劃法作為運籌學(xué)中的基本方法，其解法和建模方法等方面已經(jīng)得到了眾多學(xué)者的關(guān)注，并且已經(jīng)形成了很多的理論成果。但其目標(biāo)函數(shù)系數(shù)往往作為一種外生變量而存在，在經(jīng)濟(jì)管理實踐過程當(dāng)中，如果使用線性規(guī)劃方法，則必須確定目標(biāo)函數(shù)系數(shù)，而馬爾可夫過程基于狀態(tài)轉(zhuǎn)移概率，可以幫助決策者根據(jù)前一階段的確定狀態(tài)，完成對若干今后階段的目標(biāo)函數(shù)系數(shù)的預(yù)測。文章以此為基礎(chǔ)，探討進(jìn)行線性規(guī)劃模型調(diào)整的方式和方法。

馬爾可夫過程；線性規(guī)劃方法；經(jīng)濟(jì)預(yù)測；管理方法

1 應(yīng)用基礎(chǔ)

線性規(guī)劃方法作為運籌學(xué)研究的一個分支，已經(jīng)得到了相關(guān)學(xué)者的深入探討，并且在實踐過程中得到了廣泛的應(yīng)用。但是在以往的研究活動中，線性規(guī)劃模型中的目標(biāo)函數(shù)系數(shù)的確定問題本身，并不能在線性規(guī)劃的范疇內(nèi)加以解決，因此目標(biāo)函數(shù)系數(shù)往往作為一種外生變量。由于目標(biāo)函數(shù)系數(shù)相對于約束條件方程中的參數(shù)而言，更加具有不確定性，沒有良好的確定外生變量的方法，線性規(guī)劃法的應(yīng)用就會受到極其嚴(yán)重的限制。這種現(xiàn)象的產(chǎn)生和馬爾可夫鏈理論對相關(guān)問題的適應(yīng)性就構(gòu)成了馬爾可夫過程理論對線性規(guī)劃方法的應(yīng)用基礎(chǔ)。

1.1 線性規(guī)劃模型中目標(biāo)函數(shù)系數(shù)的外生性缺陷

線性規(guī)劃模型作為研究在一定的資源的約束的條件下，實現(xiàn)目標(biāo)函數(shù)最大化的分析工具由目標(biāo)函數(shù)、約束條件共同構(gòu)成。目標(biāo)函數(shù)和約束條件當(dāng)中均包含著參量和變量，目標(biāo)函數(shù)系數(shù)、約束條件方程中的參數(shù)和約束條件總額本身都是應(yīng)當(dāng)基本確定的參量。線性規(guī)劃模型的這一特征可以由以下方程加以描述：

式（2）中，矩陣A作為約束條件方程的參數(shù)矩陣其展開式可以被表達(dá)為：

式（2）中，向量X作為全部方案xi構(gòu)成的變量向量可以調(diào)整，其表達(dá)式為：

式（2）中，向量B作為全部約束條件參量構(gòu)成的參量向量可以被表達(dá)為：

在經(jīng)濟(jì)管理實踐工作中，矩陣A、向量B作為可以通過企業(yè)自身的技術(shù)設(shè)備狀況和資金狀況確定的參量，具有極高的確定性，能夠通過對技術(shù)性能和變化較小的生產(chǎn)經(jīng)營歷史數(shù)據(jù)的總結(jié)，得到相應(yīng)的確定值，雖然同樣是外生變量，但是并不需要加以特別關(guān)注。而變量向量X代表方案的集合，因此自然具有變量的屬性，需要研究人員和決策人員加以選擇，并且通過模型本身就能夠加以求解，屬于內(nèi)生變量的范疇。

在目標(biāo)函數(shù)方程式（1）中，xi作為變量同于約束條件方程，但是ci作為目標(biāo)函數(shù)參數(shù)，在量上同方案變量xi存在對應(yīng)關(guān)系，但是目標(biāo)函數(shù)系數(shù)本身并不能由企業(yè)的內(nèi)部信息所決定，而沒有目標(biāo)函數(shù)系數(shù)的確定就沒有線性規(guī)劃基本模型的確定，現(xiàn)有的運籌學(xué)和管理學(xué)研究往往對相應(yīng)內(nèi)容的研究存在盲點，這需要通過特定的方法的引進(jìn)加以彌補(bǔ)。

1.2 馬爾可夫過程理論對線性規(guī)劃方法的適用性

馬爾可夫過程理論的特點能對線性規(guī)劃理論的缺陷的有效彌補(bǔ)，就決定了馬爾可夫過程理論對線性規(guī)劃方法的輔助效能。

馬爾可夫過程理論的構(gòu)建基礎(chǔ)是概率論中的條件概率部分，而其適用對象的特征是某一時期的可觀測狀態(tài)量x(t)僅同前一階段的狀態(tài)量x(t-1)相關(guān)，因此能夠產(chǎn)生在一定條件下由x(t-1)轉(zhuǎn)化為x(t)的條件概率p( x)(t|x(t-1))，如果這種轉(zhuǎn)化的趨勢能夠持續(xù)，則該條件概率可以作為在初始狀態(tài)量之下，進(jìn)行預(yù)測的工具。

文在寅：“這是用西方的繪畫方式結(jié)合東方的技術(shù)制作出來的。左邊的畫是長白瀑布，右邊的畫是濟(jì)州島城山日出峰?！?/p>

馬爾可夫過程理論對于線性規(guī)劃過程的適應(yīng)性突出體現(xiàn)在，馬爾可夫過程是基于既有信息的一種預(yù)測方法，而線性規(guī)劃模型在實踐中，也需要經(jīng)濟(jì)管理人員對相應(yīng)信息有基本的了解?；诩扔行畔⑦M(jìn)行決策是線性規(guī)劃模型的應(yīng)用特征。而馬爾可夫過程理論的預(yù)測模式同樣以現(xiàn)有信息作為分析和判斷的基礎(chǔ)，對線性規(guī)劃模型的應(yīng)用條件具有很好的適用性。

馬爾可夫過程理論的應(yīng)用范圍主要是在同一時間節(jié)點上，具有多個相互獨立的狀態(tài)量的系統(tǒng)，系統(tǒng)內(nèi)的各個要素本身具有極強(qiáng)的獨立性，但是在不同時間節(jié)點上，狀態(tài)量之間會產(chǎn)生相互轉(zhuǎn)化的趨勢和可能。相對于線性規(guī)劃方法而言，馬爾可夫過程理論本身能夠囊括線性規(guī)劃模型中的目標(biāo)函數(shù)的多個系數(shù)，并且體現(xiàn)出多個系數(shù)之間的轉(zhuǎn)換關(guān)系。通過以往的既有信息，就可以利用馬爾可夫過程理論作為工具，對目標(biāo)函數(shù)的系數(shù)在長期的變化趨勢進(jìn)行基本型的判斷，從而產(chǎn)生較為準(zhǔn)確的目標(biāo)函數(shù)，對線性規(guī)劃模型的使用帶來方便。

但是馬爾可夫過程對線性規(guī)劃模型的應(yīng)用也受到馬爾可夫過程本身的特點的制約。經(jīng)過前文分析，馬爾可夫過程適用于具有無后效性的時間序列狀態(tài)量之間。這要求馬爾可夫過程的應(yīng)用對象為具有穩(wěn)定的變化趨勢的時間序列數(shù)據(jù)，一旦狀態(tài)量之間的轉(zhuǎn)換狀態(tài)發(fā)生變化，依據(jù)馬爾可夫過程理論的預(yù)測結(jié)果就將同現(xiàn)實發(fā)生偏差。這一特征可以通過如下模型進(jìn)行表述：

式（2）中的所有概率值pnn代表同一時間節(jié)點t向下一時間節(jié)點t+1過度的過程中，狀態(tài)量1向狀態(tài)量n進(jìn)行轉(zhuǎn)化的概率。如果這種轉(zhuǎn)換關(guān)系，在整個系統(tǒng)內(nèi)部的轉(zhuǎn)化關(guān)系式穩(wěn)定的，則t+n+1期的狀態(tài)量可以通過t期到t+n+1的不斷的狀態(tài)轉(zhuǎn)換關(guān)系加以體現(xiàn)，其具體的數(shù)學(xué)形式可以表達(dá)為：

這種通過不斷相乘而形成的最終狀態(tài)轉(zhuǎn)化矩陣pntrans的產(chǎn)生前提是具有相互獨立關(guān)系的前后兩期的轉(zhuǎn)化概率不斷重復(fù)作用，所形成的條件概率的最終體現(xiàn)，其理論根源在于事件A和事件B同時發(fā)生的概率為：

在兩事件相互獨立的情況下，兩事件同時發(fā)生的概率為：

在整個系統(tǒng)的包含眾多狀態(tài)的情況下，以單獨某一事件A為例，其發(fā)生的概率為：

2 方法

2.1 方法構(gòu)建的前提要求

2.1.1 實現(xiàn)目標(biāo)函數(shù)的系統(tǒng)性功能

首先，基于馬爾可夫過程的線性規(guī)劃模型中的目標(biāo)函數(shù)系數(shù)能夠產(chǎn)生系統(tǒng)性的相互影響，這一功能來自于馬爾可夫過程運算結(jié)構(gòu)。馬爾可夫過程在數(shù)學(xué)上的表達(dá)形式實際上暗含著作為某一單獨的狀態(tài)量會以一定的比例向其他狀態(tài)量進(jìn)行轉(zhuǎn)化的意義。與此同時，由于其他狀態(tài)量也會以較為穩(wěn)定的比例向該狀態(tài)量進(jìn)行轉(zhuǎn)化，從馬爾可夫過程矩陣的橫向來看，體現(xiàn)出所有狀態(tài)量向其他狀態(tài)量進(jìn)行轉(zhuǎn)化的關(guān)系，而從縱向觀察則體現(xiàn)出各狀態(tài)量接受其他狀態(tài)量所轉(zhuǎn)化而來的狀態(tài)量的情況。整個馬爾可夫過程矩陣在結(jié)構(gòu)和內(nèi)在關(guān)聯(lián)方面同投入產(chǎn)出平衡表具有一定的相似性。與投入產(chǎn)出平衡表不同的是，馬爾可夫過程矩陣本身并不包含著狀態(tài)量之間轉(zhuǎn)化而形成的技術(shù)聯(lián)系，而僅僅是數(shù)量上的轉(zhuǎn)變，這種轉(zhuǎn)變并不依賴生產(chǎn)過程給產(chǎn)品帶來的物理狀態(tài)和功能的改變，也不包含新增的無差別人類勞動的流入，而僅僅是數(shù)量上的增減變換。馬爾可夫過程矩陣的不斷相乘反映著這種系統(tǒng)性的相互關(guān)系不斷重復(fù)，各種轉(zhuǎn)化過程以穩(wěn)定的比例不斷地實現(xiàn)。這一過程的實現(xiàn)和投入產(chǎn)出法的完全消耗系數(shù)矩陣的推導(dǎo)過程同樣具有相似性。但是投入產(chǎn)出法最終構(gòu)建起的關(guān)系是最終使用和總產(chǎn)出之間的內(nèi)在聯(lián)系，依賴生產(chǎn)過程中的技術(shù)聯(lián)系，并且需要在狀態(tài)量的不斷重復(fù)的過程中扣除一部分作為最終使用是投入產(chǎn)出法的特征，而馬爾可夫過程的運行結(jié)果并不會產(chǎn)生對外部的直接產(chǎn)出。由此可見，馬爾可夫過程模型本身蘊(yùn)藏著一種狀態(tài)量系統(tǒng)相對封閉的特征，從而能夠使線性規(guī)劃方程實現(xiàn)系統(tǒng)性功能。

2.1.2 實現(xiàn)目標(biāo)系數(shù)的穩(wěn)定與可轉(zhuǎn)換性

馬爾可夫過程要求內(nèi)部狀態(tài)量的系統(tǒng)性變化關(guān)系依賴于系統(tǒng)的變化趨勢的穩(wěn)定性。這種穩(wěn)定性的直接表現(xiàn)是過程矩陣的數(shù)值應(yīng)當(dāng)變動較小，而其內(nèi)涵則主要體現(xiàn)為這一矩陣當(dāng)中的橫向關(guān)系當(dāng)中體現(xiàn)出一種單獨狀態(tài)量的輸出的穩(wěn)定，而縱向狀態(tài)量應(yīng)當(dāng)體現(xiàn)出一種輸入的穩(wěn)定。無論是輸入還是輸出均應(yīng)當(dāng)以單個的狀態(tài)量作為觀察視角。但是這一過程的實現(xiàn)前提則是整個系統(tǒng)的外部環(huán)境變化較小，從而導(dǎo)致整個系統(tǒng)內(nèi)部的轉(zhuǎn)移關(guān)系較為穩(wěn)定。但是馬爾可夫過程并不排斥狀態(tài)之間的轉(zhuǎn)移關(guān)系的變化。一旦發(fā)生狀態(tài)之間轉(zhuǎn)移關(guān)系的變動就可以將整個模型當(dāng)中的轉(zhuǎn)移矩陣進(jìn)行調(diào)整。但是馬爾可夫過程所要求的狀態(tài)轉(zhuǎn)移矩陣的變動過程要求狀態(tài)量的個數(shù)不能夠發(fā)生改變。由于馬爾可夫過程矩陣是一個沿著主對角線對稱的單位矩陣，一旦這一矩陣發(fā)生變化，矩陣之間的相乘就變得不可能，整個模型就不再有效。

2.2 方法構(gòu)建

上文探討了馬爾可夫過程的特點和其對線性規(guī)劃模型的應(yīng)用價值。在此基礎(chǔ)上，本文將對馬爾可夫過程和線性規(guī)劃方法進(jìn)行融合。

已知，某一時間節(jié)點t上，線性規(guī)劃模型所需要的目標(biāo)函數(shù)系數(shù)向量：，并且可以由此構(gòu)建出線性規(guī)劃模型：

該模型的符號含義同于式（2）。

從而可得該時期的目標(biāo)函數(shù)系數(shù)矩陣為：

并且由此可以對線性規(guī)劃模型本身進(jìn)行調(diào)整：

此時符號的含義同于式（2）。

由此可見，此時的線性規(guī)劃模型已經(jīng)轉(zhuǎn)變?yōu)橐环N以概率期望為手段，囊括預(yù)測分析的最優(yōu)化模型。使用此模型時可以完全立足于已有的基本信息，根據(jù)歷史經(jīng)驗進(jìn)行推測，并且完成最優(yōu)化的決策工作，從而彌補(bǔ)線性規(guī)劃模型的缺陷。

3 應(yīng)用范圍

基于馬爾可夫過程的線性規(guī)劃方法一方面受到馬爾可夫過程理論特點的制約，另一方面也受到線性規(guī)劃方法本身的制約?；隈R爾可夫過程的線性規(guī)劃方法不能夠適用于決策變量之間存在著函數(shù)關(guān)系的動態(tài)規(guī)劃方法，而僅僅能夠適用于決策變量相互獨立的線性規(guī)劃方法。這種限制來源于馬爾可夫過程所要求的各個狀態(tài)量均在同一時間節(jié)點上存在的特點，更是動態(tài)規(guī)劃方法在模型構(gòu)建過程中，必須要求目標(biāo)函數(shù)系數(shù)不能夠在同一時間上同時發(fā)揮作用的限制的結(jié)果。

動態(tài)規(guī)劃方法的建立基礎(chǔ)是線性規(guī)劃方法，但是動態(tài)規(guī)劃方法要求決策變量之間存在著清晰的函數(shù)關(guān)系。這就要求各個決策變量連帶著目標(biāo)函數(shù)系數(shù)不能夠在同一時間節(jié)點上出現(xiàn)，必須保持著嚴(yán)格的先后次序關(guān)系。在此條件之下，動態(tài)規(guī)劃的目標(biāo)函數(shù)系數(shù)難以在同一時間節(jié)點上同時作用，因而具有相互獨立的特征。在動態(tài)規(guī)劃方法當(dāng)中，目標(biāo)函數(shù)系數(shù)可能在內(nèi)容上完全相同，數(shù)量上大體相當(dāng)，相互之間不存在任何相互轉(zhuǎn)化的關(guān)系。這就完全突破了馬爾可夫過程的適用范圍，從而導(dǎo)致馬爾可夫過程不能正確描述和預(yù)測動態(tài)規(guī)劃的目標(biāo)函數(shù)系數(shù)的情況的發(fā)生。

但是基于馬爾可夫過程的線性規(guī)劃方法同動態(tài)規(guī)劃方法在應(yīng)用范圍方面又具有一定的重合性?；隈R爾可夫過程的線性規(guī)劃方法的著眼點在于調(diào)整未來的目標(biāo)函數(shù)系數(shù)，而動態(tài)規(guī)劃方法則側(cè)重于將既有資源在未來的多個時間節(jié)點方面加以分配。由此可見，基于馬爾可夫過程的線性規(guī)劃方法適用于由于狀態(tài)量的變化不斷累積而在未來呈現(xiàn)出整體性和系統(tǒng)性變化的預(yù)測和最優(yōu)化領(lǐng)域。動態(tài)規(guī)劃方法則適用于能夠體現(xiàn)當(dāng)期資源在不同時間節(jié)點具有不同價值的約束最優(yōu)化問題的求解。相對于動態(tài)規(guī)劃方法而言，基于馬爾可夫過程的線性規(guī)劃方法更加能夠體現(xiàn)不同時間節(jié)點上狀態(tài)量的相互聯(lián)系，這種狀態(tài)量的關(guān)系最終體現(xiàn)為線性規(guī)劃方法當(dāng)中的目標(biāo)函數(shù)系數(shù)的關(guān)系。

4 結(jié)論

本文提出了依據(jù)狀態(tài)轉(zhuǎn)移概率矩陣，進(jìn)行目標(biāo)函數(shù)系數(shù)修正的線性規(guī)劃調(diào)整模型，該模型可以完全立足于已有的基本信息，根據(jù)歷史經(jīng)驗進(jìn)行推測，并且完成最優(yōu)化的決策工作，從而彌補(bǔ)線性規(guī)劃模型的缺陷。但是該模型的應(yīng)用前提在于狀態(tài)轉(zhuǎn)移過程保持穩(wěn)定性，否則該模型的最優(yōu)結(jié)果將不再有效。

本文也對基于馬爾可夫過程的線性規(guī)劃方法的特點和適用范圍進(jìn)行了討論，并且提出其目標(biāo)函數(shù)系數(shù)的系統(tǒng)性相互影響和變動趨勢的穩(wěn)定性兩個方面特征，以及基于馬爾可夫過程的線性規(guī)劃方法適用于目標(biāo)函數(shù)系數(shù)存在不同時間節(jié)點上的相互聯(lián)系情況的理論探討。

[1]曾梅清,田大鋼.線性規(guī)劃問題的算法綜述[J].科學(xué)技術(shù)與工程, 2010,(1).

[2]彭曲,丁治明,郭黎敏.基于馬爾可夫鏈的軌跡預(yù)測[J].計算機(jī)科學(xué), 2010,(8).

[3]胡迪鶴.關(guān)于隨機(jī)環(huán)境中的馬爾可夫過程的簡介[J].數(shù)學(xué)物理學(xué)報, 2010,(5).

（責(zé)任編輯/浩天）

O211.62

A

1002-6487（2017）10-0088-03

邱祎（1980—），男，河南鄭州人，碩士，講師，研究方向：數(shù)理統(tǒng)計學(xué)。

董彥彥（1978—），女，河南舞鋼人，碩士，講師，研究方向：應(yīng)用統(tǒng)計學(xué)。