线性规划问题的最优解

线性规划问题的最优解

引言

线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人所重视。线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或线性方程来表示。而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作管理的重要性。

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

1.1线性规划问题的提出

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

minZCX (1)

约束条件：

AXb  (2)

X0

其中，C(c1,c2,,cn),X(x1,x2,,xn)T,b(b1,b2,,bm)T,A(aij)mn阶矩阵。设B是A中m个线性无关的列向量构成的一个基，B(aij)mm 阶矩阵，这样将矩阵A分成两个部分，即A=(B,N),X=(XB,XN),C=CB,CN,XB,CB为基B对应的非基变量和系数，XN,XN为N对应的非基变量和系数，这样将线性规划问题改写为：

X

minZCB,CNB (3)

XB

约束条件：

XB(B,N)b

 (4) XN

XX0BN

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

minZCBB1+(CN-CBB1N)XN (5)

约束条件：

XBB1NXNB1b

 (6)

X,X0BN

B1b(b'1,b2,,bm)T





B1N



a1m1a2m1

a1m2a1na2m2a2n

 

''



amm1amm2amn

将（5）（6）展开为：

minZcibi+

'

i1m

jm1



n

(cjciaij)xj (7)

'

i1

m

约束条件：

xi

jm1

a

n

'

ij

xjb'i ,i1,2,,m (8)

xj0 ,j1,2,,n (9)

令 Z0cibi , jcjciaij ,jm1,m2,,n ,称j为检验数。

'

'

i1

i1

m

m

1.2最优解判别准则

准则一：若 X(1)(b'1,b'2,,b'm,0,,0)T ，为对应于基B的基本可行解，且对于一切的 jm1,m2,,n ，j>0 ，则X 为线性规划问题的最优解。

证明：由（7）式可知，对任意一组可行解X(x1,x2,,xn)，j>0 ，Zcjxj ,

'

T

n

j1

均有 ZZ0，但 X(1) 能使等式成立，即ZZ0 ，故 X(1) 为线性规划问题的最优解。

准则二：当j0,jm1,m2,,n ，有某一个j0，设

jm1 ,i1,2,,m ,a'im10 ，则该线性规划问题有第二个最优的基本可行解。

证明：构造一个行解 X(2) ，(8') 得：

xib'ia'im1xm1 i1,2,,m xm1 0 xj0 jm2,,n

根据 原则

b'ib'L'

min' |aim10 '

1imaim1aLm1

 xm1

b'L ' , xL0

aLm1

将 X(2) 带入原目标函数（4）得：

b'L

Zcibi+(cm1-ciaim1+cLaLm1）'

aLm1i1i1,iL

m

'

m

'

'

由于 m1 cm1-ciaim10 ，故：Z

'

i1

m

i1,iL

cb

m

'

ii

+ cLbL cib'LZ0

'

i1

m

X(2)也是最优的基本可行解。

推论：若 X(1) 和 X(2) 均为最优的基本可行解，XX(1)(1)X(2) ,01 均为最优可行解。

准则三：当 j0 ,jm1,m2,,n ，有某一个 j0 ，对一切 i1,2,,m ，则该线性规划有无穷多个最优解。

证明：构造一个新解 X(3) ，由 (8')

xib'ia'im1xm1 i1,2,,m

xm1 0

xj0 jm2,,n

由于 a'im10 ，0 ,故 xi0 ,i1,2,,m 将X(1)代入原目标函数（4）得：

Z

m

i1,iL

cb

m

'

ii

+(cm1-cia'im1）

i1

m

由于：m1cm1-cia'im10

i1

故：

Z

i1,iL

cb

m

'

ii

'

+0 ,  cibi

i1

m

时，X(3)仍为可行解，得到无穷多可行解，而目标函数仍为 当 

'

ZcibiZ0 ，即X(3)也是最优解。

i1m

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

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

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

例15：求解下面的线性规划问题：

maxZ58x6,

x12x43x52x60,

x24x47x55x60, （1） x2x4x3x20,

456

3xj0,j1,2,,6.

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

b'1b'i'

因c4c50 ，及 4min':ai40,i1,2,3'0 ，

a14ai4

'

'

b'2b'i'

5min':ai50,i1,2,3'0 ，

a25a5

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

maxWx4x5

x2x3x0145

 （2）

x4x7x0452

xj0,j1,2,4,5.

易解得线性规划问题（2）的最优解为X''(x1,x2,x4,x5)T(0,0,0,0)T ,W(X'')0 , 于是可得 X*(x1,x2,,x6)T(0,0,20,0,0,0)T 是该线性规划问题（1）的唯一最优解。

例27：求解下面的线性规划问题：

maxZ5x6

x1x42x5x60

x24x442x52x625 （1） x2xx3x0

456

3xj0,j1,2,,6.

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

b'1b'i'

因c4c50 ，及 4min':ai40,i1,2,3'0 ，

a14ai4

'

'

b'2b'i'

5min':ai50,i1,2,3'0 ，

a25a5

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

maxWx4x5xx2x0145

 （2）

x2xx0453

xj0,j1,3,4,5.

易解得线性规划问题（2）有无界解，X''(x1,x3,x4,x5)T(0,3,2,1)T是该问题的一个可行解 ,W(X'')30 , 于是线性规划问题的最优解不唯一。只要取X*(x1,x2,,x6)T如下：

x10,x33s;

x225s(42421)0;x42s,x5s;x60.

那么 X'也是线性规划问题的最优解。例如，分别取s=0.5、0.25时，则(0,0,1.5,1,0.5,0)T和(0,12.5,0.75,0.5,0.25,0)T以及X*(0,25,0,0,0,0)T都是该线性规划问题（1）的最优解，其中，(0,25,0,0,0,0)T是一退化的基可行解，(0,0,1.5,1,0.5,0)T是一非退化的基可行解，而

(0,12.5,0.75,0.5,0.25,0)T解。

1TT

0,0,1.5,1,0.5,00,25,0,0,0,0是一可行解而不是基2

例34：要将两种大小不同的钢板结成A,B,C 三种规格，每张钢板可同时截得三种规格的小钢板的块数乳下表所示：

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

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

2xy15x2y18

解：需要截得第一种钢板X张，第二种钢板Y张，则x3y27 （*）

x0y0

作出可行区域图如下： 目标函数为zxy ，经过可行区域内的整点且与原点最近的直线是

xy12。它上面的整点有

（0，12）、（1,11）、（2,10）、(3,9)、（4，8）、（5，7）、（6,6）、（7,5）、（8,4）、（9,3）、（10,2）、(11,1)、（12,0），若逐一讨论其是否在可行域内比较麻烦时，只需先判断点A（

1839

,）附近的整数点是否满足条件，若满足条件，则再试附近的整55

数点；若不满足条件，则不需要再判断下去。

故此题，我们只需先判断A点附近的整数点（3,9）、（4,8），分别代入（*）式，易得它们都满足条件。故我们还需判断（2,10）、（5，7）两点，代入（*）式发现它们都不满足条件，则其余点不需要再判断。所以该题的最优解为（3,9）、（4,8）。

例43：maxS5x12x2，约束条件为：

x14

xx3

12，

5x12x210x1,x20

利用图解法求解如下：

此例中约束条件中存在和目标函数的系数成比例的约束条件，但是由于此约束条件在可行域的形成中没有发挥作用，所以此问题没有多个最优解。

图解法是求解含有两个变量的线性规划问题的一种很直观和有效的方法，所以在作出问题的可行域时，则可根据这个必要条件，若可行域中没有与目标函数平行的边界线时，则可直接判断出此问题一定没有多个最优解。

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

例51：求解问题：

minZx22x3

s.t.x12x2x32

x23x3x41xxx2235xj0,j1,2,3,4,5

解：这里B(A1,A4,A5)是一个单位矩阵，且b(2,1,2)T0,故基B是可行基，

x1,x4,x5为基变量，x2,x3为非基变量，

基B对应的基本可行解为：x(2,0,0,1,2)T，其目标函数值Z00.方程组Axb已是典式，得到第一张单纯性表如下：

注意 ，第0行的元素应是将目标函数Zx22x3化成等价的方程Zx22x30后的相应元素。

检验数210 ，故当前解不是最优解，A2列中有两个元素a22,a32均为正数，取

bb12

min2,3min,1

11a22a32

故转轴元为a22，x2为进基变量，x4为出基变量。进行旋转变换后得下表：

它对应的基本可行解为x(4,1,0,0,1)T，其目标函数值为Z01.但310，仍不是最优解，此时a33为转轴元，进行旋转变换后得下表：

它对应的基本可行解为x(量0，故为最优解。

13513

,,,0,0)T，其目标函数值为Z0.此时检验数向2222

例61：接下面的LP问题：

minZx1x2x3

s.t.3xxx1123



x14x2x32x1,x2,x30

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

3x1x2x3x41

x14x2x3x52 x,x,x,x,x012345

若用原始单纯形法求解，需再引进两个非负的人工变量，然后利用两阶段法求解。由本例所具有的特点，我们只要将等式两端同乘以（-1），就直接得到原问题的一个基本（不可行）解和对偶问题的一个可行解（检验数向量0）其对应的单纯形表如下：

直接利用对偶单纯形法求解。b2

2b11，所以x5为离基变量，由以下比值决定进基变量。

1121 min,

41a224

因而x2为进基变量，以a22为转轴元，进行旋转变换后得下表：

3155显然x4为离基变量，计算min,,1 a1113

444确定x1为进基变量，以a11为转轴元，进行旋转变换后得下表：

此时，b0，故原问题的最优解为x(

由以上例题可见，在某些情况下使用对偶单纯形法比用原始单纯形法更具优越性。

279,,0,0,0)T，其最优解为。 131313

参考文献

[1] 胡运权等.运筹学基础及应用[M].第五版 北京：高等教育出版社,2008-06.

[2] 管梅谷,郑汉鼎.线性规划[M].济南：山东科学技术出版社,1983. [3] 张香云.线性规划[M].浙江大学出版社,2009-02.

[4] 利奥尼德.尼森.瓦泽斯坦,克里斯托弗.卡特里尔.伯恩.线性规划导论[M].机械工业出版社, 2005-06.

[5] 卢开澄,卢华明.线性规划[M].清华大学出版社,2009-02.

[6] 江道琪,何建坤,陈松华.编.使用线性规划方法及其支持系统[M].清华大学出版社,2006-04. [7] 卢向华,侯定丕,魏权龄.运筹学教程[M].北京高等教育出版社,1989.

致 谢

经过三四个月的忙碌和学习，本次毕业设计已经接近尾声，作为一个本科生的毕业设计，由于经验的匮乏，难免有许多考虑不周全的地方，如果没有导师的督促指导，以及一起工作的同学们的支持，想要完成这个设计是难以想象的。

在这里，首先要感谢我的导师马晓娜老师。马老师平日里工作繁多，但在我做毕业设计的每个阶段，从外出实习到查阅资料，设计草案的确定和修改，中期检查，后期工作等整个过程中，都给了我悉心的指导。她的治学严谨和科学研究的精神也是我永远学习的榜样，并且积极影响我以后的学习和工作。

其次还要感谢大学五年来所有的老师，是他们为我们打下了数学专业专业知识的基础；同时还要感谢所有的同学们，正是因为有了你们的支持和鼓励。此次毕业设计才会顺利完成。

最后感谢宿州学院五年来对我的大力栽培！