线性规划问题的最优解

线性规划问题的最优解

引言

线性规划是运筹学的一个基区分支，其应用极其广泛，其作用认为越来越多的人所重

视。线性规划重要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的约束

条件下，是某个目的达成最小或最大，而这些约束条件用可以用一组线性不等式或线

性方程来表达。而求得目的函数的最优解尤为重要，本文就线性规划问题的最优解求解

方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作

管理的重要性。

1,线性规划问题的最优解探讨

1.1线性规划问题的提出

考虑下面的线性规划问题的标准型：

目的函数：

minZ=CT(1)

约束条件：

<AX=b⑵

[X>0

其中，，，，阶矩阵，设B是A中m个线性无关的列向量构成的一个基，阶

矩阵，这样将矩阵A提成两个部分，即A=,X=,C=,,为基B相应的非基变

量和系数，，为N相应的非基变量和系数，这样将线性规划问题改写为：

XR

minZ=(Ca,Cw)⑶

XB

约束条件:

XB

(B,N)B=H

.XN_⑷

XBXNNO

通过矩阵变换，得出关于基B的标准型如下:

,,

tninZ=C^-+(C/v-C/^-N)XA(5)

约束条件：

X+B1NX=B}b

RN(6)

X«,X1V>0

B-'b=(b、h，…,bmy

'%，n+l4，“+2…6，r'

gW_a2m.ia2m+2''*a2r

fici•••([

\7W//H-1W/M+2/jrn/

将(5)(6)展开为：

minZ=£c4+2qa.)巧.⑺

i,ly=m+l/=!

约束条件：

n

%+Z。/产从，i=l,2,…,〃z(8)

J=//HI

X.>0,/=1,2,…,〃(9)

M叫

令Z()=gc屹，(7-=c--Zq%,/=〃[+1,〃i+2,…,〃，称丐为检查数。

r=l/=!

1.2最优解判别准则

准则一：若，为相应于基B的基本可行解，且对于一切的，＞0,则X为

线性规划问题的最优解。

证明：》0,由（）式可知，对任意一组可行解，，均有，但能

使等式成立，即，故为线性规划问题的最优解。

准则二：当，，有某一个，设，，，则该线性规划问题有笫二个

最优的基本可行解。

证明：构造一个行解，（）得：

A;.=bi-a»n+ix/n+1z=l,2,-

（+i=。°＞。

=0/=川+2,…,〃

根据夕原则

c.bi[...bL

”=mm1———Ia而+i>()>=----

i£运叫aiJn+\

X”r+1-0-.,4=0

(I

将带入原目的函数（4）得:

m"7bt

z=»也+(q”+|-Zqa加+1+cLau,^

i=U#AZ=lClbn^\

由于-,故：

X⑵也是最优的基本可行解。

推论：若和均为最优的基本可行解,均为最优可行解。

准则三：当0,,有某一个，对一切，则该线性规划有无穷多个最

优解。

证明：构造一个新解，由（）

x{=bi-ai,n+ix/n+li=1,2,…，/〃

x.=00>0

x.=0j=m+2.---,n

由于，，故，

将代入原目的函数（4）得:

z=工也+9.-£中加+1）o

f=!1=1

由于：一

故：

mm

z=＞也+o,o=2ch

/=l.r*Z.i=l

当时，仍为可行解，得到无穷多可行解，而目的函数仍为

,即也是最优解。

以下举出一些实例，进一步说明线性规划最优解的具体求解方法:

2.线性规划最优解的问题举例

2.1图解法求解线性规划问题

例：求解下面的线性规划问题:

maxZ=5-8X6,

*+2X4-3X5-2X6=0,

«x2-4X4+7X5+5X6=0,(1)

x3+2X4+4X5-3.r6=20,

x>>0,j=l,2,---,6.

显然X*=(x”电，…，8)T=(0,0,20.0,0,0)r是该线性规划问题(1)的一个最优解。

因，及，

可考虑如下线性规划问题:

maxW=x4+x5

$+2X4-3X5=0

(2)

x2-4X4+7X5=0

^>0,j=1,2,4,5.

易解得线性规划问题(2)的最优解为r=($,%,々，毛尸=(。，。,。，。),W(X')=0,于

r

是可得X*=(x,,x2,-,x6)=(0,0,20,0,0,0/是该线性规划问题(的唯一最优解。

例：求解下面的线性规划问题：

maxZ=5-xfi

$+x4-2X5-x6=0

«x2+4X4+42/-2%=25(1)

x3-2X4+X5+3%=0

巧.NO,j=l,2,・・・,6.

rr

显然X*=(x1,x2,---,x6)=(0,20,0,0,0,0)是该线性规划问题(1)的一个最优解。

因，及

可考虑如下线性规划问题:

maxW=

x+x-2X=0

145(2)

-2X4+x5=0

Xj>0,；=1,3,4,5.

易解得线性规划问题（2）有无界解，是该问题的一个可行解，，于是线性规划

问题的最优解不唯一。只要取如下:

X=0,=3s;

占=25-5(4x2+42x1)>0;

xA-2s,x5=s;

%=0.

那么也是线性规划问题的最优解。例如，分别取s「0.5.0.25时，则和以及

都是该线性规划问题（1）的最优解，其中，是一退化的基可行解，是一非退化的

基可行解，而是一可行解而不是基解。

例：要将两种大小不同的钢板结成A,B,C三种规格，每张钢板可同时截得三种规格

的小钢板的块数乳下表所示：

钢板类型A规格B规格C规格

规格类型

第一种钢板211

第二种钢板123

今需A,B,C三种规格的成品分别为15,18,27块，问：各截取这两种钢板多

少张可得所需三种规格成品，且使得所用钢板张数最少？

解：需要截得第一种钢板X张，第二种钢板Y张，则(*)

作出可行区域图如下：

目的函数为，通过可行区域内的整点且与原点最近的直线是。它上面的整点有(0,

12)、(1,11)、(2,10)、(3,9)、(4,8)、(5,1)、(6,6)、(7,5)、(8,4)、(9,3)、(10,2)、

(11.1).(12,0),若逐个讨论其是否在可行域内比较麻烦时，只需先判断点A()附

近的整数点是否满足条件，若满足条件，则再试附近的整数点；若不满足条件，则不需

要再判断下去。

故此题，我们只需先判断A点附近的整数点(3,9)、(4,8),分别代入(*)式，易

得它们都满足条件。故我们还需判断(2,10)、(5,7)两点，代入(*)式发现它们都

不满足条件，则其余点不需要再判断。所以该题的最优解为(3,9)、(4,8)。

例：，约束条件为：

运用图解法求解如下：

比例中约束条件中存在和目的函数的系数成比例的约束条件，但是由于此约束条件在

可行域的形成中没有发挥作用，所以此问题没有多个最优解。

图解法是求解具有两个变量的线性规划问题的一种很直观和有效的方法，所以在作

出问题的可行域时，则可根据这个必要条件，若可行域中没有与目的函数平行的边界

线时，则可直接判断出此问题一定没有多个最优解。

2.2单纯型法求解线性规划问题

例：求解问题:

minZ=-x2+2x3

s.t.x1-2X2+&=2

■x2-3X3+x4=1

X2-X3+X5=2

XjNO、j=1,2,3,4,5

解：这里是一个单位矩阵，且，故基B是可行基，为基变量，为非基变量，基B

相应的基本可行解为：，其目的函数值.方程组已是典式，得到第一张单纯性表

如下：

X]x2工45RIIS

01-2000

X1-21002

%0I,-3101

01-1012

注意，第0行的元素应是将目的函数化成等价的方程后的相应元素。

检查数，故当前解不是最优解，列中有两个元素均为正数，取

min1^r,=r|=mim•=1

故转轴元为，为进基变量，为出基变量。进行旋转变换后得下表:

当x2•口XsRHS

001-10-1

■ri10-5204

x201-3101

%002,-111

它相应的基本可行解为，其目的函数值为.但，仍不是最优解，此时为转轴元

进行旋转变换后得下表：

x2X,KHS

000_3

22

100513

2~2

01035

~222

00111

~222

它相应的基本可行解为，其目的函数值为.此时检查数向量，故为最优解。

例：接下面的LP问题：

minZ=xt+x2+x3

+x+>I

*2

-%1+4X2+X3>2

xpx2,x3>0

解：引进非负的剩余变量，将不等式约束化为等式约束

+x2+x3-x4=\

--Xi+4X2+-x5=2

xpx2,x3,x4,x5>0

若用原始8x2£RHS

单纯形法

求解，需

再引进两

个非负的

人工变量，

然后运用

两阶段法

求解。由本

例所具有

的特点，

我们只要

将等式两

端同乘以

（-1）,就

直接得到

原问题的

一个基本

（不可行）

解和对偶

问题的一

个可行解

（检查数

向量）其

相应的单

纯形表如

下：

Z-1-1-1000

%-3-1-110-1

1-44-111-2

直接运用对偶单纯形法求解。，所认为离基变量，由以下比值决定进基变量。

『1T]_Q」

-,-----——

「4-1Ja224

因而为X,*5RHS

进基变量，

认为转

轴元，进

行旋转变

换后得下

表：

_5030

-4-442

_130_31_1,1

~~4-442

1

x210

4442

显然为离基变量，计算

拟定为&xy七刀4X,RHS

进基变量，

认为转

轴元，进

行旋转变

换后得下

表：

00529

~V3"1313

*1