第35卷第1期2005年1月

数学的实践与认识

Vol.35　No.1　

Jan.,2005　

确定线性规划全部最优解的方法

薛声家,　左小德

(暨南大学管理学院,广东广州　510632)

摘要:　使用凸多面体的表示定理,导出了标准型线性规划最优解的一般表达式,并基于单纯形法,给出最

优解唯一性条件以及当唯一性条件不满足时求出全部最优解的计算步骤,同时附有数值例子.

关键词:　线性规划;凸多面体;最优解;单纯形法

一般说来,实际上的经济管理问题所形成的线性规划的最优解给出了该实际问题的最佳实施方案.当线性规划有不止一个最优解时,便存在无穷多个最优解,求出线性规划的多个最优解是件很有意义的工作,因为它可以提供更多的最优方案供决策者选择.目前虽有不少文献对线性规划无穷多个最优解的情况进行了讨论,但有些存在错误和缺陷[1,2],另一些则讨论得不够完整、深入,缺乏详细有效的求解方法.本文使用凸多面体的表示(分解)定理,导出了标准型线性规划最优解的一般表达式,给出确定全部最优解的计算步骤,并附有数值例子.

1　线性规划最优解的一般表达式

考虑标准型线性规划问题:

Maxz=cTx

(SLP)s.t.Ax=b

xE0

　　其中,A为m×n阶矩阵,c和x为n维列向量,b为m维列向量,设rank(A)=m<n.

(SLP)的可行集D={xûAx=b,xE0}为一凸多面体,文献[3]给出了如下的表示定理:

定理1　设D={xûAx=b,xE0}非空,则它的极点集非空且包含有限多个点x,x,…,x,而且D的极方向集非空当且仅当D无界.若D无界,则它的极方向集包含有限个向量d,d,…,d.此外,x∈D当且仅当x可以表示为x,x,…,x的凸组合与d,d,…,d的非负线性组合之和,即

k

l

i

i

2

l1

2

l

1

2

k

1

2

k

1

x=

k

∑Kx

i=1

+

∑Ld

j

j=1

j

…… 此处隐藏0字 ……

(1)

　　其中,

∑K=

i

i=1

iE0,i=1,2,…,k;LjE0,j=1,2,…,l.1,K

收稿日期:2001-07-03

: