上、下层目标函数系数含参数的资源分配问题*

陶玉杰，杨 杰

(通化师范学院 数学学院,吉林 通化134002)

上、下层目标函数系数含参数的资源分配问题*

陶玉杰，杨 杰

(通化师范学院 数学学院,吉林 通化134002)

文章讨论的是上、下层决策的目标函数系数均含有参数的资源分配问题的灵敏度分析,研究了参数在确定方向上连续(或扰动)时最优解的状态，所得到的结果为决策者提供了决策依据.

资源分配问题;灵敏度分析;顶点;参数

在现实生活、生产与科研中,数据大多是观测数据或统计数据,而这些数据通常会有不同程度的随机误差或者波动,这必将影响到原最优方案的最优性,甚至还会影响其可行性[1-2].因此管理者或者决策者希望获得数据的改变带来的最优决策方案的变化情况,据此对市场作出相应敏感性方案.

本文依据上层目标函数系数和下层目标函数系数分别含参数的资源分配问题的灵敏度分析,研究上、下层目标函数系数同时含有参数的资源分配问题的灵敏度分析,研究参数在确定方向上连续(或扰动)时最优解的状态,以此得到最优解的相应变化情况.由于线性规划求解能力的原因,本文的分析只限于参数的线性扰动.在这个过程中,分析最优解的变化情况.

1 预备知识

我们所讨论的资源分配问题的基本模型M如下.

其中a,c,x∈Rn1,b,d,y∈Rn2,p∈Rm,A∈Rm×n1,B∈Rm×n2(n1,n2,m分别是x,y,p的维数,Rn表述n维空间).

在模型M中,若上、下层目标函数价值系数均是参数的线性函数,则有如下模型N,即

其中a(t),b(t)是t的线性函数,a(t)=(a1(t),a2(t),…,an1(t)),b(t)=(b1(t),b2(t),…,bn2(t)),c(t)=(c1(t),c2(t),…,cn1(t)),d(t)=(d1(t),d2(t),…,dn2(t)).其它符号同模型M. 模型N就是我们要研究的上、下层价值系数均是参数t的线性函数的资源分配问题.

定义1[3]称集合S={(x,y)|Ax+By≤p,x,y≥0}为模型M的容许集,每一(x,y)∈S称为模型M的一个容许解.

定义2[4]若(x,y)∈S,则称(x,y)是模型M的可行解,所有可行解的集合称为可行集,记为F.

定义3 max{aTx+bTy|(x,y)∈F}的最优解称为模型M的最优解.

定义4 设集合X是凸集,点x0是X中的点,如果对X中的任意两个相异的点x1,x2，以及开区间(0,1)上的任意数λ,都不可能有x0=λx1+(1-λ)x2，则称x0是凸集X的一个极点.

当一个凸集只有有限个极点时,这些点通常称为顶点.

定理1[5]模型M的最优解发生在容许集S的顶点处.

2 灵敏度分析的基本方法与步骤

由于上、下层目标函数的系数含参数,那么最优解和可行顶点都可能发生变化,而约束条件未发生变化,故所经历的顶点不发生变化.那么当参数在确定方向上连续(或扰动)时最优解的状态如何呢？由参数规划的知识可知,对于上、下层目标函数的系数含参数的问题仍可用单纯形法进行分析,下面给出灵敏度分析的步骤.其一般步骤是：

步骤1 令t=0,用程序分别求出上层规划最优解、二层规划最优解、全部顶点；

步骤2 将所有顶点代入下级参数规划中验证其可行性,求出可行顶点及可行顶点不变的参数t的范围；

步骤3 用灵敏度分析法,将参变量t直接反映到上层规划最优表和二层规划最优表中；

步骤4 由最优性条件、可行性条件分析使最优解不变参数的变化范围；

步骤5 分析参数超出这一范围后最优解的变化,若是最优性条件或可行性条件不满足,则按最小下降量原则用单纯形法求出新的最优解,转步骤3，直到将参数t的所有可能区间(-∞，+∞)都分析后为止.

下面结合具体算例作详细地分析.

例1 讨论如下的上、下层价值系数均含有参数t的资源分配问题最优解的变化情况.

解 求当t=0时的二层线性规划问题,由二层线性规划求最优解的程序可得此规划的所有顶点为(8,1),(0,5),(12,3),(16,11),(0,9),(10,14),最优解为(16,11).将所有顶点代入下级参数规划中验证其可行性,求出可行顶点及可行顶点不变的参数t的范围:当t≤1时(16,11),(0,5),(8,1),(12,3)是可行顶点;当t>1时(16,11),(0,9),(10,14)是可行顶点.最优解的情况体现在表1.

有了满足可行性的t的范围和可行顶点,将参变量t直接反映到上层规划最优表和二层规划最优表中.当t≤1时,得到如表2的结果：当t>1时可行顶点为(16,11),(0,9),(10,14).若求二层参数规划最优解,只需比较f1在可行点处函数值的大小即可.即

f1(16,11)=4t+71/5;f1(0,9)=9-36t;
f1(10,4)=16-26t.

显然f1(16,11)>f1(10,14)>f1(0,9),故(16,11)为最优解.

综上,此题的解如下表.

表1 下层目标函数系数含参数的资源分配问题解的情况

表2 上层目标函数系数含参数的资源分配问题解的情况

表3 上、下层目标函数系数含参数的资源分配问题解的情况

[1]李智慧,陶玉杰.二层决策问题的灵敏度分析(2)[J].数学的实践与认识,2006,36(10):167-171.

[2]陶玉杰,段丽芬,崔云安.二层决策问题的灵敏度分析(3)[J].河南师范大学学报,2009(4):151-153.

[3]陶玉杰.二层线性规划的灵敏度分析[D].秦皇岛:燕山大学,2004.

[4]滕春贤,李智慧.二层规划的理论与应用[M].北京:科学出版社,2002.

[5]陶玉杰.二层线性规划目标函数系数变化的灵敏度分析[J].通化师范学院学报,2008(12):3-4.

(责任编辑:陈衍峰)

10.13877/j.cnki.cn22-1284.2015.04.008

2014-12-20

陶玉杰,女,吉林抚松人,副教授.

O

A

1008-7974(2015)02-0021-02