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

第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

(1)

其中,

∑K=

i

i=1

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

收稿日期:2001-07-03

:

102

数　学　的　实　践　与　认　识35卷

设(SLP)有最优解,则必存在基最优解(最优极点),记(SLP)的最优极点集为{xiûi∈I}.另外,由(1)式不难看出,(SLP)有最优解当且仅当对于所有的极方向dj有cTdjF0.

设x*为(SLP)的最优解,若D的某极方向dj满足cTdj=0(即dj与c正交),则易见,对于任意的KE0,x*+Kdj都是最优解.我们称满足cTdj=0的极方向为最优极方向.记(SLP)的最优极方向集为{djûj∈J},则有:

定理2　若(SLP)的最优解集非空,则最优极点集非空.而且,最优极方向集非空当且仅当最优解集无界.此外,x为(SLP)的最优解当且仅当x可以表示为最优极点的凸组合与最优极方向的非负线性组合之和,即

x=

其中,

∑Kx

ii∈I

i

+

∑Ld

j

j∈J

j

(2)

∑K=

i

i∈I

1,KiE0,i∈I;LjE0,j∈J.

证明　记(SLP)的最优值为z*.若x可表示为(2)的形式,则x∈D且cTx=z*,因此x为最优解.

反过来,设x为最优解,为证明(2)式,只需证明(1)式中有:对于任意i|对于任意j|

J有Lj=0.

Th*Th*

I使Kh>0,则cx<z,因此Khcx<Khz,从而

l

iT

i

k

jT

k

I有Ki=0和

用反证法.反设存在h|

z

*

=cx=

T

∑Kcx

i=1

+

∑Lc

j=1

dF

j

∑Kc

i

i=1k

T

xi　(因为LjcTdjF0)=z　矛盾

l

T

t

T

j

*

<

同样,若反设存在t|而

k

l

iT

i

T

t

∑Kz

i

i=1

*

J,使Lt>0,则cd<0,因此Ltcd<0,所以∑Ljcd<0,从

j=1

k

jT

z

*

=cx=

T

∑Kcx

i=1

+

∑Lc

j=1

d<F

j

∑Kc

i

i=1k

T

xi

=z*　矛盾

∑Kz

i

i=1

*

定理2证毕.

2　最优解唯一性条件和确定全部最优解的计算步骤

假定我们用单纯形法求解得(SLP)的基最优解x,不妨设相应的基指标集为IB={1,2,…,m},则相应的典式为:

n

*

z=zxi+

*

+

n

j=m+1

∑Rx

j

′

ijj

j

(3)(4)(5)

j=m+1

∑a

x=b′i,　i=1,2,…,m

xjE0,　j=1,2,…,n

1期

m

薛声家,等:确定线性规划全部最优解的方法

m

′ii

103

zx

*

=

∑cb,

i=1′

Rj=cj-′

∑a

i=1

′iji

c,　j=m+1,…,n

*

=(b1,…,bm,0,…,0)

T

由于已达到最优,故RjF0,j=m+1,…,n.使用式子(3)可以证明如下定理.

定理3　x*为唯一最优解的充分条件是所有的非基变量的检验数Rj<0.若x*非退化,则上述条件也是必要的.

证明　设所有非基变量的检验数Rj<0,任取一异于x*的可行解x,若xj=0,j|IB,则由(4)式可得x=x*之矛盾.故存在h|

使用(3)式计算x的目标值

n

IB,使xh>0,从而Rhxh<0.

z=z

*

*

+

j=m+1

∑Rx

j

j

Fz*+Rhxh<z*

IB,使Rk=0,则我

由此可以看出x是唯一最优解.

反之,设x*是唯一最优解且非退化,即b′i>0,i∈IB.若存在k|们可构造如下的可行解-x:

′′

-xi=bi-aikH,-xk=H,-xj=0,

i∈IB

j|IB,j≠k

*---　　由于b′i>0,i∈IB,故H>0充分小时,x为可行解,且x≠x.x的目标值为

n

-z=z

即-x也是最优解.这与x

验数Rj<0.证毕.况:

*

*

+

j=m+1

x∑R-j

j

=z

*

+RkH=z

*

是唯一最优解的假设矛盾.因此,必定有所有非基变量的检

若唯一性条件不满足,即存在某非基变量xk的检验数Rk=0,则可能出现下面两种情

[3]

情况1:对于i=1,2,…,m,a′ikF0.这时,根据极方向的代数特征,我们可以得到

一个极方向d,其分量为

di=-a′ik,dk=1,dj=0,

m

i∈IB

(6)

j|

IB,j≠k

因为cd=ck-

T

∑a

i=1

′

iki

c=Rk=0,因此,所得到的极方向d是最优极方向.

H=min{bi/aikûaik>0}i∈I

B

情况2:存在i∈IB,使a′ik>0,则以xk为入基变量,使用H规则(最小比值规则)

′

′

′

确定出基变量.若H>0,则转轴后可得到新的基最优解;若H=0,则转轴后虽然得到

了新的基,但基最优解x*保持不变.

下面给出求所有基最优解和最优极方向的计算步骤.

步骤1:使用单纯形法解(SLP).若在最优单纯形表中所有非基变量的检验数Rj<0,则(SLP)有唯一最优解;否则进入步骤2.

k;

104

数　学　的　实　践　与　认　识35卷

步骤3:以xk为入基变量,使用H规则确定出基变量,转轴后可得到新的基最优解或原基最优解的新最优单纯形表.

对每个最优单纯形表,重复进行步骤2和步骤3,直到处理完所有满足Rk=0的非基变量xk.

由于各个基最优解都是两两“相邻”的,所以在有限步后(必要时可以使用避免发生基循环的方法),可找出(SLP)的所有基最优解和所有最优极方向,因而确定了(SLP)的全部最优解.

例:考虑下列线性规划问题

maxz=-x1+3x3-x4

s.t.

x1　　-x2

-3x1+2x2+9x3+2x4

x2

4x1+3x2+5x3x1,x2,…,x7E0

使用单纯形方法求解可得最优单纯形表(表1)

表1

cj

cB0300

xBx5x3x7x2

b521726

-1x1[1]-0.333-4.667

00

0x200010

3x301000

-1x400.2221.1110-1.667

0x510000

0x6-10-4-10

0x700100

5———Hi

+x5

-2x6-x6

+x5

=3=22=2-x7=4

由表1可以得到基最优解x1=(0,2,2,0,5,0,17)T,最优值z*=6.

1

由于非基变量x6的检验数R6=0,且各a′i6F0,根据(6)式便得到一个最优极方向d=

(0,1,0,0,1,1,4).

在表1中还有非基变量x1的检验数R1=0,且各a′i1中存在正元素,令x5出基,x1进基,转轴后得到另一个最优单纯形表(见表2).

表2

cj

cB-1300

xBx1x3x7x2

b53.66740.33326

-1x110000

0x200010

3x301000

-1x400.2221.1110-1.667

0x510.3334.66700

0x6-1-0.333-8.667-10

0x700100

T

表2给出了另一个基最优解x2=(5,2,3.667,0,0,0,40.333)T.

2由于非基变量检验数R6=0,且所有a′i6F0,因此得到另一个最优极方向d=(1,1,

0.0,..

1期薛声家,等:确定线性规划全部最优解的方法

105

本例最优解的一般表达式为:

x=Kx1+(1-K)x2+L1d1+L2d2

其中0FKF1,L1,L2E0.

参考文献:

[1]　钱颂迪等.运筹学(修订版)[M].北京:清华大学出版社,1990,23—25.[2]　赵风治.线性规划计算方法[M].北京:科学出版社,1981.55—60.

[3]　BazaraaMS,JarvisJJ,SheraliHD.LinearProgrammingandNetworkFlows.2nd-Edition[M].JohnWiley,New

York,1990.60—70.

[4]　郑义建.线性规划问题最优解集的结构与仅有唯一最优解的充分条件[J].应用数学与计算数学学报,1992,6(1):

42—46.

[5]　张新辉.有无穷多最优解线性规划问题[J].运筹与管理,1995,4(1):1—4.[6]　李军.线性规划无穷多最优解的讨论[J].运筹与管理,1999,8(1):87—92.[7]　徐增坤.数学规划引论[M].北京:科学出版社,2000.7—9.

AnApproachforDeterminingallOptimizationSolutionsofLinearProgramming

XUESheng-jia,　ZUOXiao-de

(ManagementCollege,JinanUniversity,GuangzhouGuangdong510632,China)

Abstract:　Withtherepresentationtheoremofconvexpolyhedron,thispaperderivesthegeneralexpressionforoptimalsolutionstostandardlinearprogramming.Basedonthesimplexmethod,wegivetheuniquenessconditionofoptimalsolutionandthecomputationalprocedurestofindalloptimalsolutionsiftheuniquenessconditioinisnotsatisfied.Anumericalexampleisalsogiven.

Keywords:　linearprogramming;convexpolyhedron;optimalsolution;simplexmethod

本文来源：https://www.bwwdw.com/article/b5p4.html