解決線性規(guī)劃系統(tǒng)識別問題的新方法

楊 德 權(quán), 王 佳

( 大連理工大學 系統(tǒng)工程研究所, 遼寧 大連 116024 )

?

解決線性規(guī)劃系統(tǒng)識別問題的新方法

楊 德 權(quán)*, 王 佳

( 大連理工大學 系統(tǒng)工程研究所, 遼寧 大連 116024 )

對一類特殊的逆線性規(guī)劃問題——線性規(guī)劃系統(tǒng)識別——進行研究,即試圖通過給定的輸入-輸出數(shù)據(jù)來估計線性規(guī)劃模型的技術(shù)系數(shù)矩陣以及目標函數(shù)系數(shù)．構(gòu)建了估計技術(shù)系數(shù)矩陣的行估計模型,并對該模型進行改進得到更好的估計模型；基于Troutt提出的最大決策效率方法,構(gòu)建了估計標準化目標函數(shù)系數(shù)的模型；通過兩個數(shù)值算例說明該估計方法具有良好的表面有效性,且符合提出的后續(xù)驗證準則．

運籌學；逆線性規(guī)劃；估計模型；線性規(guī)劃系統(tǒng)識別

0 引 言

線性規(guī)劃是運籌學中運用最廣泛的技術(shù)之一,現(xiàn)實生活中有很多問題都被簡化為線性規(guī)劃問題來求解[1],比如在復雜的熱力學系統(tǒng)中化學平衡的計算[2]、水電站水庫優(yōu)化調(diào)度[3]等．在建模過程中,所有的參數(shù),包括技術(shù)系數(shù)矩陣、目標函數(shù)系數(shù)以及右端項向量均需要是已知的,但是這些參數(shù)并不易提前獲知．文獻[4]分析表明,在實踐中應用生產(chǎn)計劃模型常因難以獲取所需的數(shù)據(jù)而受到阻礙；文獻[5]則指出,企業(yè)通常很難精確地闡明他們的目標以及技術(shù)系數(shù)矩陣的約束．因此,通過適當?shù)姆椒ǐ@取線性規(guī)劃模型的技術(shù)系數(shù)矩陣以及目標函數(shù)系數(shù)就顯得尤為重要．

Troutt等[6]提出了一類特殊的逆線性規(guī)劃問題,稱為線性規(guī)劃系統(tǒng)識別(簡稱為LPSI)．即通過給定的一組生產(chǎn)單元,包括實際決策向量以及可利用資源向量,來估計線性規(guī)劃模型的技術(shù)系數(shù)矩陣以及目標函數(shù)系數(shù)的問題．對此,文獻[5-6]給出了解決方法．在過去的幾十年,已經(jīng)有許多專家學者研究技術(shù)系數(shù)矩陣以及目標函數(shù)系數(shù)的估計方法．如Sengupta[7]指出,利用隨機系數(shù)回歸法估計技術(shù)系數(shù)矩陣是值得研究的；而Ray[8]分析,利用隨機系數(shù)回歸法估計的系數(shù)可能會出現(xiàn)負值；進而,Dixon等[9]通過改進隨機系數(shù)回歸法,提出了嚴格不等式約束的隨機系數(shù)回歸法以估計非負的系數(shù)矩陣．另外,文獻[10-12]針對目標函數(shù)的估計,考慮了如下逆優(yōu)化問題:盡可能小地調(diào)整線性規(guī)劃模型的目標函數(shù)系數(shù),使得給定的可行解成為最優(yōu)解．

然而,LPSI問題與以往的研究不同在于:它是在給定同一個前提下,即給定輸入-輸出數(shù)據(jù),同時估計模型技術(shù)系數(shù)矩陣與目標函數(shù)系數(shù)的問題．自LPSI問題提出以來,有關(guān)它的研究還不多,如文獻[5]給出了一個啟發(fā)式算法來解決LPSI 問題．因此,本文希望做出一些努力使得LPSI問題更為人所知,也試圖提出新方法來解決LPSI問題．

本文先概要介紹LPSI問題,然后針對LPSI問題提出解決方法:首先,構(gòu)建估計技術(shù)系數(shù)矩陣的行估計模型(簡稱RE模型),并加以改進以消除RE模型潛在的問題,得出改進的RE模型(簡稱MRE模型)；其次,回顧文獻[5]估計目標函數(shù)系數(shù)的最大決策效率方法(簡稱MDEA模型),通過消除MDEA模型的不足,構(gòu)建估計標準化目標函數(shù)系數(shù)的模型(簡稱IMDEA模型)；再次,提出后續(xù)驗證準則,以檢驗估計方法得到的結(jié)果是不是有效的．接下來給出了兩個數(shù)值算例以驗證估計方法的準確性,并與文獻[5]的結(jié)果進行比較．

1 LPSI問題的闡述

線性規(guī)劃問題通過給定輸入輸出來獲得最優(yōu)決策,其中輸入是技術(shù)水平以及目標函數(shù)系數(shù),輸出是資源右端項；而LPSI問題給定的輸入輸出分別為可利用資源向量與實際決策向量,用來估計技術(shù)系數(shù)矩陣以及目標函數(shù)系數(shù)．這說明,LPSI 不只是一類特殊的逆線性規(guī)劃問題,還屬于給定輸入輸出的最優(yōu)實現(xiàn)規(guī)劃問題的范疇．本文接下來給出LPSI的定義,并沿用文獻[6]中的標記方式,除非是特別說明,向量均指的是列向量．

Pt: maxzt+=π′ys.t. Ay≤xt；t=1,…,Tyr≥0；r=1,…,R

即LPSI問題求解的是滿足假定(1)的非負技術(shù)系數(shù)矩陣A以及滿足假定(2)的非負目標函數(shù)系數(shù)π．

2 估計非負技術(shù)系數(shù)矩陣

2.1 行估計模型

其中σ為聚合函數(shù),可選擇∑(求和)、∏(求積)、min(求最小)等．本文選取的聚合函數(shù)為∑,故RE模型的目標函數(shù)變?yōu)?/p>

通過構(gòu)造I個RE模型來估計出A的每一行元素,從而得到矩陣A．很明顯,估計出來的A滿足假定條件(1),而且是唯一的．

RE模型將假定(1)作為約束條件來建模,可以保證求得的矩陣A是符合要求的．另外,如果LPSI問題對A沒有非負限制,那么將RE模型的約束條件air≥0去掉仍然可以求解A,也就是可以拓寬RE模型的適用范圍．但是,如果存在某組觀測數(shù)據(jù)t0遠離分布整體,即xt0與yt0是奇異值,那么這組數(shù)據(jù)對估計技術(shù)系數(shù)矩陣會產(chǎn)生影響,通過RE模型估計的結(jié)果可能不會很準確．因此有必要消除這一潛在問題．

2.2 改進的RE模型

在RE模型的基礎(chǔ)上,對T組約束條件的每一組條件加上權(quán)重,即λt對應第t(t=1,…,T)組約束條件,得到改進的RE模型如下:

λt可由間距法[13]生成．間距法簡述如下:

3 估計標準化目標函數(shù)系數(shù)

3.1 回顧MDEA模型

MDEA模型是由文獻[5]提出的,能夠估計標準化目標函數(shù)系數(shù)．下文中構(gòu)建的估計目標函數(shù)系數(shù)的模型是在MDEA模型的基礎(chǔ)上改進得到的,因此有必要介紹一下MDEA模型的建模過程．

Pt對應的對偶模型Qt為

minzt-=ξt′xts.t. A′ξt≥π； ξt≥0；t=1,…,T

設(shè)yt*為模型Pt的最優(yōu)解,ξt*為模型Qt的最優(yōu)解．由假定(1)可知,yt為Pt的可行解,則有π′yt≤π′yt*．由對偶原理可知,π′yt*=ξt*′xt,故π′yt≤ξt*′xt．引入決策效率vt=π′yt/π′yt*,則vt=π′yt/ξt*′xt,且0≤vt≤1,t=1,…,T．

接下來,引入一個標準化的約束條件π′yt0=1,t0為某一特定的觀測指數(shù),這并不會影響決策效率值．因為如果模型Pt中的目標函數(shù)系數(shù)π用kπ(k>0)替換,那么相對應的對偶模型Qt中的對偶變量同樣乘上了k,這并沒有改變決策效率vt的大小．

最后,利用文獻[14]中的最大決策效率原則,以各組觀測數(shù)據(jù)的決策效率之和作為目標函數(shù),文獻[5]提出了估計標準化目標函數(shù)系數(shù)π的MDEA模型:

3.2 MDEA模型的潛在問題

3.3 改進MDEA模型

對偶模型Qt變?yōu)镼′t:

對于模型P′t來說,由于Ay≤Ayt,故yt更加近似或者就是其最優(yōu)解；從而π′yt近似或者等于最優(yōu)值．這將會降低模型P′t與Q′t的最優(yōu)值不等情況發(fā)生的概率．

t這兩個函數(shù)值的差值盡可能地小,即兩個函數(shù)值更接近甚至相等,同時也能滿足后文提出的后續(xù)驗證準則．

綜上所述,改進的MDEA模型(簡稱IMDEA 模型)如下:

4 判定結(jié)果的合理性

4.1 后續(xù)驗證準則

對估計方法的準確性進行驗證是必要的,但是文獻[5]并沒有這么做．本文提出了一個后續(xù)驗證準則:利用估計出的目標函數(shù)系數(shù)π與技術(shù)系數(shù)矩陣A,求解模型P′t與Q′t的最優(yōu)值,如果解出的兩個最優(yōu)值相等,那么估計出的A與π也就是有效的；反之則說明估計方法不準確．在最優(yōu)值相等的情況下,稱A與π分別為有效技術(shù)系數(shù)矩陣與有效標準化目標函數(shù)系數(shù)．

4.2 最優(yōu)估計結(jié)果的選擇方法

本文針對LPSI問題提出的解決思路是,先利用RE模型或MRE模型估計出技術(shù)系數(shù)矩陣,然后再利用IMDEA模型以及估計的技術(shù)系數(shù)矩陣來估計目標函數(shù)系數(shù),并稱這兩個估計量為一組估計結(jié)果．由于MRE模型可以估計出任意多個技術(shù)系數(shù)矩陣,對應地能夠估計出多個目標函數(shù)系數(shù),即得到多組估計結(jié)果．因此,有必要選出一組最優(yōu)的估計結(jié)果．選擇方法如下:首先,需要保證估計結(jié)果符合后續(xù)驗證準則,即要求有效的技術(shù)系數(shù)矩陣與目標函數(shù)系數(shù)；其次,每一組估計結(jié)果均需求解T個模型P′t,從而得到T個最優(yōu)值,其最大值為該估計結(jié)果所能達到的最優(yōu)值；最后,對多個估計結(jié)果所對應的最優(yōu)值進行比較,其最大值為MRE模型所能達到的最優(yōu)值,而且對應的A與π為最優(yōu)的估計結(jié)果．

5 數(shù)值算例

5.1 15個醫(yī)院的測試數(shù)據(jù)

本文采用的例子與文獻[5]中的一致,是來自于Sherman[15]的15個醫(yī)院的測試數(shù)據(jù),見表1．本文數(shù)據(jù)均采用軟件Matlab R2009a編程所得．

如果需要詳細了解這些數(shù)據(jù)的來源可以查看文獻[16],在這里僅作簡要描述:給定一個初始的技術(shù)系數(shù)矩陣

以及15個輸出向量y(表中數(shù)據(jù)),再利用x=A0y求出輸入向量．

表1 15個醫(yī)院的測試數(shù)據(jù)

表2 應用MDEA模型估計的詳細數(shù)據(jù)

5.1.2 驗證本文所提方法的準確性 利用文獻[5]估計的技術(shù)系數(shù)矩陣,通過IMDEA模型估計目標函數(shù)系數(shù)π=(0.000 176 4 0.000 212 0 0.000 934 1)．通過驗證發(fā)現(xiàn),模型P′t與Q′t的最優(yōu)值近似相等,詳細數(shù)據(jù)參見表3．考慮到計算機的誤差,可以近似地認為二者是相等的．故判斷IMDEA模型是有效的．

利用RE模型得到的技術(shù)系數(shù)矩陣,以及利用IMDEA模型得到的目標函數(shù)系數(shù)如下:

π1=(0.000 168 3 0.000 225 1 0.000 896 0),最優(yōu)值z=2.223 2,而且模型P′t與Q′t的最優(yōu)值近似相等,詳細數(shù)據(jù)參見表4．

為了方便起見,本文僅利用MRE模型構(gòu)造30個A．按照4.2給出的選擇最優(yōu)估計結(jié)果的方法,得到最優(yōu)的技術(shù)系數(shù)矩陣以及目標函數(shù)系數(shù)如下:

π2=(0.000 168 4 0.000 225 1 0.000 896 0),

最優(yōu)值z=2.223 3,而且模型P′t與Q′t的最優(yōu)值近似相等,詳細數(shù)據(jù)參見表5．

比較最優(yōu)值可知,MRE模型的結(jié)果比RE模型的結(jié)果要好一些．而且,RE模型與MRE模型估計的最優(yōu)有效技術(shù)系數(shù)矩陣與初始的A0相比都很接近,相比文獻[5]估計的結(jié)果要精確很多,說明本文提出的模型在處理該問題上取得了令人滿意的結(jié)果．

5.2 IMDEA模型的進一步驗證

由于5.1中的數(shù)值算例并沒有給出初始的目標函數(shù)系數(shù),這就導致不能直觀地判斷IMDEA模型估計的精度．接下來,本文根據(jù)上一個算例,構(gòu)造出一組新的數(shù)據(jù)來驗證本文提出的IMDEA模型的準確性,并與MDEA模型進行比較．數(shù)據(jù)構(gòu)造的具體步驟如下:

表3 應用IMDEA模型估計的詳細數(shù)據(jù)

表4 應用RE和IMDEA模型估計的詳細數(shù)據(jù)

表5 應用MRE和IMDEA模型估計的詳細數(shù)據(jù)

步驟1給定一個目標函數(shù)系數(shù)π*．

例如π*=(0.000 167 9 0.000 225 0 0.000 922 8),它是利用IMDEA模型以及初始的A0求解出來的,作為已知的目標函數(shù)系數(shù)．

步驟2根據(jù)初始的A0以及表1中的xt,再加上步驟1的π*,解模型Pt可得最優(yōu)解yt*來替換表1的輸出向量yt．yt*的具體數(shù)據(jù)參見表6．

步驟4最后,通過IMDEA模型以及MDEA模型估計目標函數(shù)系數(shù),并與初始的目標函數(shù)系數(shù)進行比較,得出優(yōu)劣結(jié)論．

表6 輸出向量

利用IMDEA模型與MDEA模型估計出來的目標函數(shù)系數(shù)分別為(0.000 166 3 0.000 221 7 0.000 650 6),(0.000 170 5 0.000 219 2 0)．將估計出的目標函數(shù)系數(shù)的各個元素與初始目標函數(shù)系數(shù)的各個元素進行比較,得到絕對偏差百分比為(0.994% 1.483% 29.503%),(1.547% 2.568% 100%)．顯然IMDEA模型估計的目標函數(shù)系數(shù)比MDEA模型更接近初始值,因此IMDEA模型更有效．

6 結(jié) 語

文獻[6]提出的LPSI問題,即通過給定的輸入-輸出數(shù)據(jù)來估計技術(shù)系數(shù)矩陣以及目標函數(shù)系數(shù),具有較大的理論意義和實用價值．但是,文獻[5]提出的解決方法存在兩個明顯的不足:一是估計技術(shù)系數(shù)矩陣的結(jié)果不夠準確；二是估計標準化目標函數(shù)系數(shù)的MDEA模型在建模時存在缺陷,而且并沒有驗證估計結(jié)果是否符合建模的要求．本文針對這兩方面提出了改進方法．首先,提出了RE模型以及MRE模型,可以更好地估計技術(shù)系數(shù)矩陣．其次,通過消除MDEA模型潛在的問題,得到了更好的IMDEA模型．同時提出了后續(xù)驗證準則,以驗證所得的結(jié)果是否滿足建模的要求．最后,兩個數(shù)值算例驗證了本文提出的方法比文獻[5]的方法有明顯的優(yōu)勢．

[2]Belov G. On linear programming approach for the calculation of chemical equilibrium in complex thermodynamic systems [J]. Journal of Mathematical Chemistry, 2010,47(1):446-456.

[3]CHENG Chun-tian, WANG Wen-chuan, XU Dong-mei,etal. Optimizing hydropower reservoir operation using hybrid genetic algorithm and chaos [J]. Water Resources Management, 2008,22(7):895-909.

[4]Troutt M D, Pang Wan-kai, Hou Shui-hung. Behavioral estimation of mathematical programming objective function coefficients [J]. Management Science, 2006,52(3):422-434.

[5]Troutt M D, Brandyberry A A, Sohn C,etal. Linear programming system identification:the general nonnegative parameters case [J]. European Journal of Operational Research, 2008,185(1):63-75.

[6]Troutt M D, Tadisina S K, Sohn C,etal. Linear programming system identification [J]. European Journal of Operational Research, 2005,161(3):663-672.

[7]Sengupta J K. Regression and programming:overview of linkages [J]. Arthaniti:a Bi-annual Journal of the Department of Economics, Calcutta University, 1975,17:1-17.

[8]Ray S. Methods of estimating the input coefficients for linear programming models [J]. American Journal of Agricultural Economics, 1985,67(3):660-665.

[9]Dixon B L, Hornbaker R H. Estimating the technology coefficients in linear programming models [J]. American Journal of Agricultural Economics, 1992,74(4):1029-1039.

[10]HUANG Si-ming, LIU Zhen-hong. On the inverse problem of linear programming and its application to minimum weight perfectk-matching [J]. European Journal of Operational Research, 1999,112(2):421-426.

[11]Sokkalingam P T, Ahuja R K, Orlin J B. Solving inverse spanning tree problems through network flow techniques [J]. Operations Research, 1999,47(2):291-298.

[12]Ahuja R K, Orlin J B. Inverse optimization [J]. Operations Research, 2001,49(5):771-783.

[13]Devroye L. Non-uniform Random Variate Generation [M]. New York:Springer-Verlag, 1986.

[14]Troutt M D. A maximum decisional efficiency estimation principle [J]. Management Science, 1995,41(1):76-83.

[15]Sherman H D. Measurement of hospital technical efficiency:A comparative evaluation of data envelopment analysis and other approaches for locating inefficiency in health care organizations [D]. Boston:Harvard University, 1981.

[16]Bowlin W F, Charnes A, Cooper W W,etal. Data envelopment analysis and regression approaches to efficiency estimation and evaluation [J]. Annals of Operations Research, 1984,2(1):113-138.

Anewmethodtosolveproblemoflinearprogrammingsystemidentification

YANG De-quan*, WANG Jia

( Institute of Systems Engineering, Dalian University of Technology, Dalian 116024, China )

A special kind of inverse linear programming called linear programming system identification, which seeks to estimate the technological coefficient matrix and the objective function coefficient vector with the given input-output data, is considered. The row estimation model and the modified row estimation model are constructed to estimate the technological coefficient matrix, and based on the maximum decision-making efficiency approach proposed by Troutt, an estimation model is constructed to estimate the objective function coefficient vector. It is found that the estimation method exhibits excellent face validity for two test datasets, and corresponds with the proposed subsequent validation criteria.

operational research; inverse linear programming; estimation model; linear programming system identification

1000-8608(2014)01-0139-08

2013-05-06；

: 2013-12-01．

楊德權(quán)*(1965-),男,博士,副教授,E-mail:drydq123@aliyun.com.

O221

：A

10.7511/dllgxb201401021