解决线性规划系统识别问题的新方法

杨 德 权, 王 佳

( 大连理工大学 系统工程研究所, 辽宁 大连 116024 )



解决线性规划系统识别问题的新方法

杨 德 权*, 王 佳

( 大连理工大学 系统工程研究所, 辽宁 大连 116024 )

对一类特殊的逆线性规划问题——线性规划系统识别——进行研究,即试图通过给定的输入-输出数据来估计线性规划模型的技术系数矩阵以及目标函数系数．构建了估计技术系数矩阵的行估计模型,并对该模型进行改进得到更好的估计模型；基于Troutt提出的最大决策效率方法,构建了估计标准化目标函数系数的模型；通过两个数值算例说明该估计方法具有良好的表面有效性,且符合提出的后续验证准则．

运筹学；逆线性规划；估计模型；线性规划系统识别

0 引 言

线性规划是运筹学中运用最广泛的技术之一,现实生活中有很多问题都被简化为线性规划问题来求解[1],比如在复杂的热力学系统中化学平衡的计算[2]、水电站水库优化调度[3]等．在建模过程中,所有的参数,包括技术系数矩阵、目标函数系数以及右端项向量均需要是已知的,但是这些参数并不易提前获知．文献[4]分析表明,在实践中应用生产计划模型常因难以获取所需的数据而受到阻碍；文献[5]则指出,企业通常很难精确地阐明他们的目标以及技术系数矩阵的约束．因此,通过适当的方法获取线性规划模型的技术系数矩阵以及目标函数系数就显得尤为重要．

Troutt等[6]提出了一类特殊的逆线性规划问题,称为线性规划系统识别(简称为LPSI)．即通过给定的一组生产单元,包括实际决策向量以及可利用资源向量,来估计线性规划模型的技术系数矩阵以及目标函数系数的问题．对此,文献[5-6]给出了解决方法．在过去的几十年,已经有许多专家学者研究技术系数矩阵以及目标函数系数的估计方法．如Sengupta[7]指出,利用随机系数回归法估计技术系数矩阵是值得研究的；而Ray[8]分析,利用随机系数回归法估计的系数可能会出现负值；进而,Dixon等[9]通过改进随机系数回归法,提出了严格不等式约束的随机系数回归法以估计非负的系数矩阵．另外,文献[10-12]针对目标函数的估计,考虑了如下逆优化问题:尽可能小地调整线性规划模型的目标函数系数,使得给定的可行解成为最优解．

然而,LPSI问题与以往的研究不同在于:它是在给定同一个前提下,即给定输入-输出数据,同时估计模型技术系数矩阵与目标函数系数的问题．自LPSI问题提出以来,有关它的研究还不多,如文献[5]给出了一个启发式算法来解决LPSI 问题．因此,本文希望做出一些努力使得LPSI问题更为人所知,也试图提出新方法来解决LPSI问题．

本文先概要介绍LPSI问题,然后针对LPSI问题提出解决方法:首先,构建估计技术系数矩阵的行估计模型(简称RE模型),并加以改进以消除RE模型潜在的问题,得出改进的RE模型(简称MRE模型)；其次,回顾文献[5]估计目标函数系数的最大决策效率方法(简称MDEA模型),通过消除MDEA模型的不足,构建估计标准化目标函数系数的模型(简称IMDEA模型)；再次,提出后续验证准则,以检验估计方法得到的结果是不是有效的．接下来给出了两个数值算例以验证估计方法的准确性,并与文献[5]的结果进行比较．

1 LPSI问题的阐述

线性规划问题通过给定输入输出来获得最优决策,其中输入是技术水平以及目标函数系数,输出是资源右端项；而LPSI问题给定的输入输出分别为可利用资源向量与实际决策向量,用来估计技术系数矩阵以及目标函数系数．这说明,LPSI 不只是一类特殊的逆线性规划问题,还属于给定输入输出的最优实现规划问题的范畴．本文接下来给出LPSI的定义,并沿用文献[6]中的标记方式,除非是特别说明,向量均指的是列向量．

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

即LPSI问题求解的是满足假定(1)的非负技术系数矩阵A以及满足假定(2)的非负目标函数系数π．

2 估计非负技术系数矩阵

2.1 行估计模型

其中σ为聚合函数,可选择∑(求和)、∏(求积)、min(求最小)等．本文选取的聚合函数为∑,故RE模型的目标函数变为

通过构造I个RE模型来估计出A的每一行元素,从而得到矩阵A．很明显,估计出来的A满足假定条件(1),而且是唯一的．

RE模型将假定(1)作为约束条件来建模,可以保证求得的矩阵A是符合要求的．另外,如果LPSI问题对A没有非负限制,那么将RE模型的约束条件air≥0去掉仍然可以求解A,也就是可以拓宽RE模型的适用范围．但是,如果存在某组观测数据t0远离分布整体,即xt0与yt0是奇异值,那么这组数据对估计技术系数矩阵会产生影响,通过RE模型估计的结果可能不会很准确．因此有必要消除这一潜在问题．

2.2 改进的RE模型

在RE模型的基础上,对T组约束条件的每一组条件加上权重,即λt对应第t(t=1,…,T)组约束条件,得到改进的RE模型如下:

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

3 估计标准化目标函数系数

3.1 回顾MDEA模型

MDEA模型是由文献[5]提出的,能够估计标准化目标函数系数．下文中构建的估计目标函数系数的模型是在MDEA模型的基础上改进得到的,因此有必要介绍一下MDEA模型的建模过程．

Pt对应的对偶模型Qt为

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

设yt*为模型Pt的最优解,ξt*为模型Qt的最优解．由假定(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为某一特定的观测指数,这并不会影响决策效率值．因为如果模型Pt中的目标函数系数π用kπ(k>0)替换,那么相对应的对偶模型Qt中的对偶变量同样乘上了k,这并没有改变决策效率vt的大小．

最后,利用文献[14]中的最大决策效率原则,以各组观测数据的决策效率之和作为目标函数,文献[5]提出了估计标准化目标函数系数π的MDEA模型:

3.2 MDEA模型的潜在问题

3.3 改进MDEA模型

对偶模型Qt变为Q′t:

对于模型P′t来说,由于Ay≤Ayt,故yt更加近似或者就是其最优解；从而π′yt近似或者等于最优值．这将会降低模型P′t与Q′t的最优值不等情况发生的概率．

t这两个函数值的差值尽可能地小,即两个函数值更接近甚至相等,同时也能满足后文提出的后续验证准则．

综上所述,改进的MDEA模型(简称IMDEA 模型)如下:

4 判定结果的合理性

4.1 后续验证准则

对估计方法的准确性进行验证是必要的,但是文献[5]并没有这么做．本文提出了一个后续验证准则:利用估计出的目标函数系数π与技术系数矩阵A,求解模型P′t与Q′t的最优值,如果解出的两个最优值相等,那么估计出的A与π也就是有效的；反之则说明估计方法不准确．在最优值相等的情况下,称A与π分别为有效技术系数矩阵与有效标准化目标函数系数．

4.2 最优估计结果的选择方法

本文针对LPSI问题提出的解决思路是,先利用RE模型或MRE模型估计出技术系数矩阵,然后再利用IMDEA模型以及估计的技术系数矩阵来估计目标函数系数,并称这两个估计量为一组估计结果．由于MRE模型可以估计出任意多个技术系数矩阵,对应地能够估计出多个目标函数系数,即得到多组估计结果．因此,有必要选出一组最优的估计结果．选择方法如下:首先,需要保证估计结果符合后续验证准则,即要求有效的技术系数矩阵与目标函数系数；其次,每一组估计结果均需求解T个模型P′t,从而得到T个最优值,其最大值为该估计结果所能达到的最优值；最后,对多个估计结果所对应的最优值进行比较,其最大值为MRE模型所能达到的最优值,而且对应的A与π为最优的估计结果．

5 数值算例

5.1 15个医院的测试数据

本文采用的例子与文献[5]中的一致,是来自于Sherman[15]的15个医院的测试数据,见表1．本文数据均采用软件Matlab R2009a编程所得．

如果需要详细了解这些数据的来源可以查看文献[16],在这里仅作简要描述:给定一个初始的技术系数矩阵

以及15个输出向量y(表中数据),再利用x=A0y求出输入向量．

表1 15个医院的测试数据

表2 应用MDEA模型估计的详细数据

5.1.2 验证本文所提方法的准确性 利用文献[5]估计的技术系数矩阵,通过IMDEA模型估计目标函数系数π=(0.000 176 4 0.000 212 0 0.000 934 1)．通过验证发现,模型P′t与Q′t的最优值近似相等,详细数据参见表3．考虑到计算机的误差,可以近似地认为二者是相等的．故判断IMDEA模型是有效的．

利用RE模型得到的技术系数矩阵,以及利用IMDEA模型得到的目标函数系数如下:

π1=(0.000 168 3 0.000 225 1 0.000 896 0),最优值z=2.223 2,而且模型P′t与Q′t的最优值近似相等,详细数据参见表4．

为了方便起见,本文仅利用MRE模型构造30个A．按照4.2给出的选择最优估计结果的方法,得到最优的技术系数矩阵以及目标函数系数如下:

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

最优值z=2.223 3,而且模型P′t与Q′t的最优值近似相等,详细数据参见表5．

比较最优值可知,MRE模型的结果比RE模型的结果要好一些．而且,RE模型与MRE模型估计的最优有效技术系数矩阵与初始的A0相比都很接近,相比文献[5]估计的结果要精确很多,说明本文提出的模型在处理该问题上取得了令人满意的结果．

5.2 IMDEA模型的进一步验证

由于5.1中的数值算例并没有给出初始的目标函数系数,这就导致不能直观地判断IMDEA模型估计的精度．接下来,本文根据上一个算例,构造出一组新的数据来验证本文提出的IMDEA模型的准确性,并与MDEA模型进行比较．数据构造的具体步骤如下:

表3 应用IMDEA模型估计的详细数据

表4 应用RE和IMDEA模型估计的详细数据

表5 应用MRE和IMDEA模型估计的详细数据

步骤1给定一个目标函数系数π*．

例如π*=(0.000 167 9 0.000 225 0 0.000 922 8),它是利用IMDEA模型以及初始的A0求解出来的,作为已知的目标函数系数．

步骤2根据初始的A0以及表1中的xt,再加上步骤1的π*,解模型Pt可得最优解yt*来替换表1的输出向量yt．yt*的具体数据参见表6．

步骤4最后,通过IMDEA模型以及MDEA模型估计目标函数系数,并与初始的目标函数系数进行比较,得出优劣结论．

表6 输出向量

利用IMDEA模型与MDEA模型估计出来的目标函数系数分别为(0.000 166 3 0.000 221 7 0.000 650 6),(0.000 170 5 0.000 219 2 0)．将估计出的目标函数系数的各个元素与初始目标函数系数的各个元素进行比较,得到绝对偏差百分比为(0.994% 1.483% 29.503%),(1.547% 2.568% 100%)．显然IMDEA模型估计的目标函数系数比MDEA模型更接近初始值,因此IMDEA模型更有效．

6 结 语

文献[6]提出的LPSI问题,即通过给定的输入-输出数据来估计技术系数矩阵以及目标函数系数,具有较大的理论意义和实用价值．但是,文献[5]提出的解决方法存在两个明显的不足:一是估计技术系数矩阵的结果不够准确；二是估计标准化目标函数系数的MDEA模型在建模时存在缺陷,而且并没有验证估计结果是否符合建模的要求．本文针对这两方面提出了改进方法．首先,提出了RE模型以及MRE模型,可以更好地估计技术系数矩阵．其次,通过消除MDEA模型潜在的问题,得到了更好的IMDEA模型．同时提出了后续验证准则,以验证所得的结果是否满足建模的要求．最后,两个数值算例验证了本文提出的方法比文献[5]的方法有明显的优势．

[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．

杨德权*(1965-),男,博士,副教授,E-mail:drydq123@aliyun.com.

O221

：A

10.7511/dllgxb201401021