混合型区间线性规划的求解

祝永武,李 炜

(杭州电子科技大学理学院,浙江杭州310018)

0 引 言

传统的决策方法侧重于确定性的决策模型的建立,由于现实问题的复杂性及信息获取的不完整,数学模型中的系数并不能完全确定。为了描述这种不确定性并在不确定环境下做出决策,引入了区间技术,即通过获取某不确定参数的变动范围来建立决策模型。区间线性规划(Linear Programmingwith Interval Coefficients,LPIC)作为一种柔性线性规划,可以很好的解决不确定系统中的优化问题。对于LPIC方面的研究,提出了不同的方案来确定区间不等式的关系[1-4],对目标函数、约束条件中含有区间数的线性规划问题进行了最优值区间讨论[5-7]。前面的研究对于含有区间等式约束的最差最优值没有解决好,且没有讨论和解决最差最优值的模型不可行的问题,通过解决这两个问题从而进一步改进和完善混合型区间线性规划的最优值区间求解模型。

1 LPIC最优值区间的确定

考虑到很多求解不确定问题的思路是把不确定问题转化为确定性的问题来进行求解,由于区间规划问题的参数是区间,因此所得的目标函数值也是一个区间,故考虑区间线性规划的最优值区间的求解。

定义如下一类目标系数、约束系数均为区间数的线性规划模型:

式1的目标系数、约束系数均为区间数,且含有不等式及等式约束,称之为LPIC混合型的标准式。任取aij∈[],LPIC变为确定型线性规划,则称该线性规划的最优解为LPIC的一个最优解,相应的最优目标函数值称为LPIC的一个最优值;LPIC最优值的集合记为Q,称ZL=min{z|z∈Q}为LPIC的最好最优值,ZR=max{z|z∈Q}为 LPIC的最差最优值,称[ZL,ZR]为LPIC的最优值区间。关于最优值区间的确定,国内外已有不少研究[7,8],总体概括可按如下算法进行:

(1)求解最好最优值区间目标函数用其最优目标函数代替,区间不等式约束用其最大范围不等式代替,并把区间等式约束用由其生成的两个边界不等式代替,得到一个确定型的线性规划,求得最好最优值ZL;

(2)求解最差最优值区间目标函数用其最差目标函数代替,区间不等式约束用其最小范围不等式代替,并把区间等式约束分别用其两个边界等式代替,得到2m-p(m-p为区间等式约束的个数)个确定型的线性规划,分别进行求解,得2m-p个最优值,再在这些最优值中选取最大者为最差最优值ZR;

(3)[ZL,ZR]即为LPIC的最优值的取值区间。

对于最优值区间的下界即最好最优值只需求解一个确定型线性规划,而对含有等式约束的最优值区间的上界即最差最优值的求解效率太低,甚至还极有可能出现模型不可行,算法失效的情形。首先所要解决的问题修改求解含有较多等式约束的最差最优值模型,使其计算量减小。由于在绝大多数情况下,最好最优值的模型都可行,而最差最优值的模型不可行,针对这一问题,给出最差最优值的算法模型。

2 确定最差最优值的新方法

最差最优值的关键在于区间等式约束如何化为确定型等式约束,将讨论在含有区间等式约束的最差最优值可行情形下的算法。

定义1 在最大范围不等式和区间等式生成的边界不等式约束条件下求得最差目标函数的最小值,称为LPIC最差最优的最小值,记为ZRL;在最大范围不等式和区间等式生成的边界不等式约束条件下求得最差目标函数的最大值,称为LPIC的最差最优的最大值,记为ZRR。

显然最差最优值ZR∈[ZRL,ZRR],最差最优值一定在等式约束边界中得到,并且是两个边界中的最差最优值较大的那个边界中得到,很显然,最差最优值较小的边界在求最差最优解的模型中是可以忽略的,而最差最优值较大的边界是要保留的。所以有如下定理。

定理1 最差最优的最小值的解x*,满足x*的等式边界(至少有一个),则最差最优解不在此边界上;最差最优的最大值的解x**,满足x**的等式边界(至少有一个),则此边界一定是最差最优解的边界。

由该定理可知,求解最差最优解时,抛弃满足x*的等式边界(u个),保留满足x**的等式边界(v个),可将原来2m-p(m-p为区间等式约束的个数)个确定型的线性规划减少到2m-p-u-v个。最差最优值一定在等式边界中得到,所以怎样选择等式边界成为算法的关键。通过先筛选区间等式边界,从而减少计算量,优化了模型。

3 最差最优值的辅助问题不可行时的修正

由于求解最差最优值模型是在最小范围内求最优,实际上是将原来的求解空间缩小,很可能导致可行域为空,使得最差最优值模型不可行,但最差最优值仍然是存在的,通过对模型的修改来求得。

3.1 区间不等式的讨论

通过将最小范围逐步放大,使得最差最优值模型由不可行刚好转到可行,则此时的最优解就是最差最优值。Dorota Kuchta定义了带参数的最差最优值模型[8],通过确定参数从而求得最差最优值,而参数的求解并不容易。最差最优值模型不可行即最小范围不等式不可行,适当放大最小范围,当非空时,此时可求出最差最优值。如何恰好使之可行成为难点,最小范围不等式最大程度可以放大到而此时很可能已经使得可行域太大,求出的最差最优值小于ZR,从可行域为空到可行域过大,通过求目标函数的最大值从而可以确定恰好由不可行到可行的那个最优点即是最差最优值点。

于是有下述区间线性规划模型:

式2的最差最优值模型为:

如果式3不可行,则建立下述模型:

由式4,可求解最差最优值。

3.2 区间等式的讨论

由于等式边界不在可行域内,通过修改区间等式边界使得最差最优值模型不可行转到可行。将等式边界缩小到最大程度来求目标函数的最大值,从而可以确定恰好由不可行到可行的那个最优点即是最差最优值点。

区间线性规划模型式5的最差最优值模型式6不可行,即最差最优值的区间等式边界或者超出可行域,则最大程度的放大或缩小为和然后再求目标函数的最大值,从而求得最差最优解。即建立模型:

将区间线性规划最差最优值不可行模型的最小范围放大最大程度,通过逆向思维求由不可行到可行的那个最优点,从而解决了最差最优值不可行时的问题,完善了最差最优解模型。

4 总 结

通过将区间线性规划的区间参数特征化,转化成确定型线性规划求解其最优值区间,通过研究最差最优值模型的区间等式的等式边界如何确定化,以及当最差最优值模型不可行时,通过放大可行域巧妙的的求出最优值区间的上界,优化和完善了最差最优值模型,从而比较系统的解决了混合型区间线性规划的最优值区间的问题。本文的理论和方法具有普遍适用性,解决了最差最优值模型不可行的问题,虽然降低了含有区间等式约束的最差最优值的计算复杂性,但仍需计算2m-p-u-v个确定型线性规划,当等式约束较多时计算量还是较大,如何进一步优化最差最优值模型仍需做进一步的研究。

[1] Ishbuchi H,Tanaka H.Formulation and analysis of linear programming problem with interval coefficients[J].Journal of Japan Industrial Management Association,1989,40(5):320-329.

[2] Tong S.Interval number and fuzzy number linear programming[J].Fuzzy Sets and Systems,1994,66(1):301-306.

[3] 刘新旺,达庆利.一种区间数线性规划的满意解[J].系统工程学报,1999,14(2):123-128.

[4] Sengupta A,Pal TK,Chakraborty D.Interpretion of inequality constraints involving interval coefficients and a solution to interval linear programming[J].Fuzzy Sets and Systems,2001,11(9):129-138.

[5] Chinneck JW,Ramadan K.Linear Programming with Interval coefficients[J].The Journal of the operational Research Society,2000,51(2):209-220.

[6] 张吉军.区间线性规划问题的最优解[J].系统工程与电子技术,2001,23(9):53-55.

[7] 郭均鹏,李汶华.区间线性规划的标准型及其最优值区间[J].管理科学学报,2004,7(3):59-63.

[8] Dorota Kuchta.A modification of a solution concept of the linear programming problem with interval coefficients in the constraints[J].Eur JOper Res,2008,16(3):307-316.