线性规划课件

第一章线性规划及单纯形方法

主要内容线性规划的模型、标准型、图解法、解、单纯形法、大M法、两阶段法

讲授重点线性规划问撷的解、单纯形法、大M法、两阶段法

教学方法讲授式、启发式

本章知识结构图

第一节线性规划问题及其数学模型

一、问题的提出

在生产和经营等管理工作中，需要经常进行计划或规划，即：在现有各项资源条件(I勺限

制下，如何确定方案，使预期目标达到最优。看如下两个例子：

例1美佳公司计划制渣I、II两种家电产品。已知各制造一件时分别占用的设备A.B的

台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如

表1—1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。

表1T

III每天可用能力

设备A(h)0515

设备B(h)6224

调试工序(h)115

利润(元)21

例2捷运公司拟在下一年度的1〜4月的4个月内需租用仓库堆放物资。已知各月份所

需仓库面积数列于表1—2,仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见

表1—3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。因此该厂

可根据需要，在任何一个月初办理租借合同。每次办理时可签一份，也可签若干份租用面积

和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最

小。

表1-2单弓“100m2

月份1234

所需仓库面积：15102012

表1-3单位：元/100m2

合同租借期限1个月2个月31个月4个月

合同期内的租费2800450060007300

二、线性规划问题的数学模型

例1中先用变量X1和X2分别表示美佳公司制造家电I和II的数量。这时该公司可获取

的利润为(2x1+x，元，令Z=2XI+X2,因问题中要求获取的利润为最大，即maxz。家电I、II

的制造件数受设备A、B和调试工序能力的能力限制，同时家电I、I【制造数量不可能为负

值。由此例1的数学模型可表为；

目标函数n^xz=2x,+x2

约束条件

5X2<15(1.1。)

6x1+2.x,<24(LIZ?)

X1+x2<5(1.1c)

x^x2>0(1.1J)

例2中若用变量X”表示捷运公司在第i(i=l,…，4)个月初签订的租借期方」(j=

1,…，4)个月的仓库面积的合同(单位为lOOm?)。因5月份起该公司不需要租借仓库，故

X2%X33,X“,X42,X43,X.H均为零。该公司希望总的租借费用为最小，故有如下数学模型：

目标函数minz=2800(XII+X21+X3】+XII)+4500(X12+X22+X32)+6000(X】3+X23)+7300XM

约束条件

xu+x12+x13+x14>15

Xi2+Xl3+x14+X2l+X224-%23>10

«x[3+X]4+x22+x23+x3I+xi2>2()

X[4+X2y+%32+X41212

Xjj>0(/=l,---4;j=l,---4)

这个模型中的约束条件分别表示当月初签订的租借合同的面积数加上该月前签订的未

到期的合同的租借面积总和，应不少于该月所需的仓库面积数。

上述两个例子表明，规划问题的数学模型由三个要素组成：(1)变量，或称决策变量，

是问题中要确定的未知量，它用以表明规划中的用数量表示的方案、措施，可由决策者决定

和控制；(2)目标函数，它是决策变最的函数，按优化目标分别在这个函数前加上max或min；

(3)约束条件，指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等

式或不等式。如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策

变量的线性函数，约束条件是含决策变量的线性等式或K等式，则该类规划问题的数学模型

称为线性规划(LinearProgramming,LP)的数学模型。

假定线性规划问题中含n个变量,分别用x」(j=l,…，n)表示，在目标函数中X」的系

数为Cj(Cj通常称为价值系数)，Xj的取值受m项资源的限制，用bi(i=l,...m)表示第i种资

源的拥有量，用瓯表示变量Xj取值为1个单位时所消耗或含有的第i种资源的数量，通常

称加为技术系数或工艺系数。则上述线性规划问题的数学模型可表示为：

max(或niin)z=仇内+c2x2+…+c”x”

%内+%2工2+…+。户”《(或=，之地

。21工1+a22X2+•♦•+ainXn«(或=，之明

3+32+…+%"〃"或=，M

，…乙2。(1.2)

上述模型的简写形式为:

max(或min)z=cjxj

£%勺工（或=2曲«=1,•••，〃)

x/>0(J=l,­•,«)

(1.3)

用向量形式表达时，上述模型可写为：

max（或min）z=CX

£P为,或=,>)/?

J=I

Jij>0

(1.4)

式（1.4）中

c二(c"2,…c〃)；X=

用矩阵和向量形式来表示可写为：

max（^min）z=CX

AXW（或=,>）/?

X>0

%

A二

《%am2

A称为约束方程组（约束条件）的系数矩阵。

变量X」的取值一般为非负，即x」20；从数学意义上可以有XjWO。又如果变量.表示

第j种产品本期内产量相对于前期产量的增加值，则X」的取值范围为（-8,+8）,称X”

取值不受约束，或不无约束。

三、LP的标准形式

由于目标函数和约束条件内容和形式上的差别，线性规划问题可以有多种表达式。为了

便于讨论和制定统一的算法，规定线性规划问题的标准形式如下：

maxz=£cjXj

7=>

=b,.（i=l,

Xj>0（/=],.••〃）

标准形式的线性规划模型中，目标函数为求极大值（有些书上规定是求极小值），约束条件

全为等式，约束条件右端常数项bi全为非负值，变量Xj的取值全为非负值。对不符合标准

形式（或称非标准形式）的线性规划问题，可分别通过下列方法化为标准形式。

1.目标函数为求极小值，即为：

n

minz=j

j=i

因为求minz等价于求max（-z）,即化为：

maxz'=-'

y=i

2.右端项bKO时，只需将等式或不等式两端同乘（T）,则等式右端项必大于零。

3.约束条件为不等式。当约束条件为“W”时,如6x1+2xzW24,可令xs=24-6x「2x2：

或6X1+2X2+X3=24,显然x£（）。当约束条件为“2”时，如有10XI+12X2218,可令x尸

10XI+12X2T8或10XI+12X2-X《=18,xBO。X3和4是新加上去的变量,取值均为非负,加至U

原约束条件中去的R的是使不等式转化为等式，其中X3,称为松弛变量，X4一般称为剩余变

量，但也有称松弛变量的c松池变量或剩余变量在实际问题中分利表示未被充分利用的资源

和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。

4.取值无约束的变量。如果变量X代表某产品当年计划数与上一年计划数之差，显然

x的取值可能是正也可能为负，这时可☆x=x，-x〃，其中x，20,x〃20,将其代入线性规

划模型即可。

5.对xWO的情况，令x，=-x,显然X20。

例3将下述线性规划化为标准形式

minz=x}+2x2+3x3

-2xt+x2+x3<9

—3xj+x2+2r3>4

4Xj-2X2-3X3=-6

X]<0,x2>0,巧取值无约束

解上述问题中令z'=-Z,X；=一$,巧=M一耳’，其中，并按上述规则，该问题的标

准形式为：

r

maxz=x[-2X2-3耳++0x4+0x5

2x\+x2+Xy-Xy+x4=9

r

3x；+x2+2x3-2xJ-x5=4

4x：+2X2+3x；-=6

第二节图解法

基本概念：

可行解：一个线性规划问题有解，是指能找出一组Xj（j=l,…，）满足约束条件，称这

组Xj为问题的可行解。

通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域，可行域中使目

标函数值达到最优的可行解称为最优解。

对不存在可行解的线性规划问题，称该问题无解。

对模型中只有2个变量的线性规划问题，可以通过在平面上作图的方法求解。

一、图解法的步骤

图解法的步骤可概括为：在平面上建立直角坐标系；图示约束条件，找出可行域；图示

目标函数和寻找最优解。

下面通过上述例1来具体说明。先将例1的数学模型重列如下：

maxz=2X]+x2

15(1.5〃)

5X2<

6x+24(1.5/?)

}2X2<

X]+x2<5(1.5c)

xpx2>0(1.5d)

1.以变量XI为横坐标轴，X2为纵坐标轴画出直角平面坐标系，适当选取单位坐标长度。

由变量的非负约束条件（L5d）知，满足该约束条件的解（对应坐标系中的一个点）均在笫I象

限内。

2.图示约束条件，找出条件可行域。约束条件（1.5a）5x2W15决定的区域，见图

类似满足约束条件（1.5a）〜（1.5d）的点如图1-2所示，图中凸多边形°0。2。3。4所包含的

区域（用阴影线标示）是例I线性规划问题的可行域。

图1-1图1-2

3.图示目标函数。由于z是一个要求定的目标函数值，随z的变化，z=2xi+x?是斜率

图中向量P代表目标函数值Z的增大方向。

图1-3

4.最优解的确定。因最优解是可行域中使FI标函数值达到最优的点，将图1-2和图1-3

合并得到图1-4,可以看出，当代表目标函数的那条直线由原点开始向右上方移动时，z的

值逐渐增大，一直移动到目标函数的直线与约束条件包围成的凸多边形相切时为止，切点就

是代表最优解的点。因为再继续向右上方移动，Z值仍然可以增大，但在目标函的直线上找

不出一个点位于约束条件包围成的凸多边形内部或边界上。

本例中目标函数直线与凸多边形的切点是Q2,该点坐标可由求解直线方程6XI+2X2=24

和xE2=5得到,为⑶,3=（3.5,1.5）。将其代入目标函数得z=8.5,即美佳公司应每

天制造家电13.5件，家电H1.5件能获利最大。

二、LP求解的几种可能结局

例1用图解法得到的最优解是唯一的。但对线性规划问题的求解还可能出现下列结局：

1.无穷多最优解。如将例1中的目标函数改变为maxz=3xi+x2,则表示目标函数的直

线族恰好与约束条件（L5b）平行。当目标函数向优化方向移动时，与可行域不是在一个点上,

而是在QQz线段上相切，见图l-5o这时点《、及。、Q?之间的所有点都使目标函数z达

到最大值，即有无穷多最优解，或多重最优解。

2.无界解。如果例1中只包含约束条件（1.5Q）,这时可行域可伸展到无穷，即变量xi

的取值也可无限增大，不受限制，由此目标函数值也可增大至无穷（见图1-6）。这种情况下

问题的最优解无界。

3.无解，或无可行解。例如下述线性规划模型：

maxZ=2XI+X2

X[+巧<2

<2x1+x2>6

x^x2>0

见图1-7,其模型的约束条件之间存在矛盾。

三、由图解法得到的启示

1.求解线性规划问题时，解的情况有：唯一最优解；无穷多最优解；无界解；无可行

解。

2.若线性规划问题的可行域存在，则可行域是一个凸集。

3.若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多的话）一定是

在可行域凸集的某个顶点上得到。

4.解题思路是，先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻

顶点的目标函数值是否比这个值大，如果为否，则该顶点就是最优解的点或最优解的点之一,

否则转到比这个点的目标函数值更大的另一顶点，重复上述过程，一直到找出使目标函数值

达到最大的顶点为止。

在单纯形法原理一节中，将对2、3两点进行证明，并建立起凸集顶点的代数概念特征,

然后通过代数计算实现第4点的解题思路。

思考题代表目标函数的直线和其移动方向如何确定？

作业课后习题1-2,5-6

实践作业相关建模练习

第三节单纯形法原理

一、LP问题解的概念

线性规划问题

n

maxz=^CJXJ（1.6）

；=|

（i=l,…,〃z）（1.7）

•六।

>0（J=],■"■,/O（1.8）

可行解满足上述约束条件（1.7）、（1.8）的解乂=（-…，Xn）T,称为LP问题的可行解。

全部可行解的集合称为可行域。

最优解使目标函数（1.6）达到最大值的可行解称为最优解。

基设A为约束方程组（1.7）的mXn阶系数矩阵，（设n>m）,其秩为m,B是矩阵A中

的一个mXm阶的满秩子矩阵，称B是线性规划问题的一个基。不失一般性，设

B中的每一个列向量Pj（j=l,…,m）称为基向量,与基向量R对应的变量Xj称为基变

量，线性规划中除基变量以外的变量称为非基变量。

基解在约束方程组（1.7）中，令所有非基变量3产X”后…二Xn=O,又因为有倒

根据克莱姆规则，由m个约束方程可解出m个基变量的唯i解XB=（XI,…，Xm）T下。将这个

解加上非基变量取0的值有X=（x“X2…，x”,0,…，0）T,称X为线性规划问题的基解。显

然在基解中变量取非零值的个数不大于方程数01,故基解的总数不超过个。

基可行解满足变量非负约束条件（L8）的基解称为基可行解。

可行基对应于基可行解的基称为可行基。

二、凸集及其顶点

凸集对简单的儿何形体可以直观地判断其凹凸性，但在高维空间，只能给出点集的解

析式，因此只能用数学解析式判断。凸集的概念为：如吴集合C中任意两点X1,汽的连线上

的所有点也都是C中的点，称C中的点，称C为凸集。曰于X”通的连线可表示为

aX}+（l-t/）X2（0<«<1）

因此凸集定义用数学解析式可表为：对任何XcC,X2wC,有aX|+（l-a）X2wC.

（°<。<1）,则称C为凸集，

顶点凸集.C中满足下述条件的点X称为顶点：如果C中不存在仟何两个不同的点儿，

儿，使X成为这两个点连线上的一个点。或者这样叙述：对任何XiwCX?不存在

X=aX\+（1一"）、2（°<”1）,则称X是凸集C的顶点。

三、几个基本定理的证明

定理1若线性规划问题存在可行解，则问题的可行域是凸集。

证若满足线性规划约束条件

gp/j=b

尸i

的所有点组成的几何图形C是凸集，根据凸集定义，C内任意两点％,X2连线上的点也必然在

C内，下面给予证明。

设X]=(Xl],X12=[Xm)『,X2=(X2I，X22L・，X2n)9C内任意两点，即X]£C,X?£C,

将X1,X?代入约束条件有

=b'^Pix2j=b

j=l7=1(1.9)

Xi,X2连线上任意一点可以表示为：

X=aX+(]-a)X(0<f/<1)

]2(1.10)

将式(1.9)代入式(1.10)得:

ZP"=£6叽+(1一J

7=1；=•

〃〃〃

=ZPj%+ZPjX2j-ZP户2j

；=17=17=1

=ab+b-ab=h

所以*=〃乂|+(1一/*2£。°由于集合中任意两点连线上的点均在集合内，所以c为凸

集。

引理线性规划问题的可行解X=3,…，Xn)为基可行解的充要条件是X的正分量所对

应的系数列向量是线性独立的。

证(1)必要性。由基可行解的定义显然。

(2)充分性。若向量PhP2,…,Pk线性独立,则必有kWm；当k=m时,它们恰好构

成一个基，从而X=(x]，X2,-0,0)为相应的基可行解。当k〈m时，则一定可以

从其余列向量中找出(m-k)个与pi,P2,…，Pk构成一个基，其对应的解恰为X,所以据定义

它是基可行解。

定理2线性规划问题的基可行解X对应线性规划问题可行域(凸集)的顶点。

证本定理需要证明：X是可行域顶点OX是基瓦行解。下面采用的是反证法，即证

明：X不是可行域的顶点=X不是基口J行解。卜面分两步来证明。

(DX不是基可行解nX不是可行域的顶点。

不失一般性，假设X的前m个分量为正，故有

£3=b

尸1(1.11)

由引理知P”…，Pn,线性相关，即存在一组不全为零的数&(i=l,…，m),使得有

6：巴+—必+・・・+6，产0(1.12)

(1.12)式乘上一个不为零的数p得：

口3E+口52P2+…+口5磊1=0(1.13)

+，

(1.13)+(1.11)得：(xi+pdi)Pi+(X2+P62)P2"+(x.+p6n)Pn=0

(1.11)-(1.13)得：(Xl-116l)P|+(X2-p62)P2+，，，+(x^>-p5n)Pr>=0

令X⑴=[(Xi+p6i)Pi,(Xz+p52)P2,,•,»(xB+p5n)Pi»,0,0]

X(2)=[(X]-p5i)P),(x2-p52)P2,(x^-pSjP,,,0,•••,0]

乂口可以这样来选取，使得对所有i=l，…，m有

0由此x⑴WC,X⑵WC,又X=1X⑴+TX⑵，

即X不是可行域的顶点。

(2)x不是可行域的顶点=>x不是基本可行解。

不失一般性，设X=(X]，X2,…，Xr,。，…，。)不是可行域的顶点，因而可以找到可行

域内另外两个不同点Y和Z,<X=aY+(l-a)Z(O<a<l),或可写为:

Xj=ayj+(l-a)zj(0<a<l;j=L•••,n)

因a>0,l-a>0,故当Xj=O时,必有y_j=Zj=O

ipixJ=ip>xJ=b

因有六।

£PjYj=，PjYj=b

j=ij=i(1.14)

£PjZj=£PjZj=b

月>='(1.15)

S5—Zj)Pj=o

(1.15)得z

因()'/一4)不全为零，故七「・・，七线形相关，即x不是基可行接解。

定理3若线性规划问题有最优解，一定存在一个基可行解是最优解。

Z=CX(0)=£c产，

证设X®=(£)，引，…瘾)是线性规划的一个最优解，闩是目

标函数的最大值。若X⑼不是基可行解，由定理2知x(°)不是顶点，一定能在可行域内找

到通过X(°)的直线上的另外两个点(X⑼+口6)20和(X(°L口3)20。将这两个点代入目标

函数有

(0)(0)(0)

C(X+p5)=CX+cX

C(X(0)-p6)=CX(0)-CX(0)

因CX⑼为目标函数的最大值，故有

X⑼2cx⑼+CX⑼

X⑼2cx⑼-CX⑼

由此CR5=0,即有C(X(°)+pb)=cX<0)=C(X(0)-p5)o如果(x©+口5)或(X@—口"仍不

是基可行解，按上面的方法继续做下去，最后•定可以找到•个基可行解，其目标函数值等

于CX⑼，问题得证。

四、单纯形法迭代原理

由上述定理3可知，如果线性规划问题存在最优解，一定有一个基可行解是最优解。因

此单纯形法迭代的基本思路是：先找出一个基可行解,判断其是否为最优解,如为否,则

转换到相邻的基可行解,并使目标函数值不断增大,一直找到最优解为止。

1.确定初始基可行解

对标准型的级性规划问题

maxz=2r

y=i

舄为=〃(1.16)

[^>0(J=l,-,n)(1.17)

在约束条件(1.16)式的变量的系数矩阵中总会存在一个单位矩阵

1o•••o'

01…0

（4，g,…，匕）=.••

•*•a

o0…1

(1.18)

当线性规划的约束条件均为W号时，加上松弛变量&。、工"，的系数矩阵即为单位矩阵。对

约束条件为2或=的情况，为便于找到初始基可行解，可以构造人工基，人为产生一个单位

矩阵，这将在本章第五节中讨论。

（1.⑻式乜儿…记”称为基向量，问其对应的变量对……%称为基变量，模型中的

其它变量七用“小2,…，豆称为非基变量。在（1.16）式中令所有非基变量等于零，即可找到

一个解

X=（阳，…,（,工……,X"）'=他，…,如。,…,。）,

因有b20,故X满足约束（1.17）,是一个基可行解。

2.从一个基可行解转换为相邻的基可行解

定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。

设初始基可行解中的前m个为基变量，即

X⑼=（邸,x30,…,。）丁

代入约束条件（1.16）有

=b

1=1(1.19)

写出（1.19）系数矩阵的增广矩阵

6户2…匕Pg...Pj•-P.b

-

10…0…%…4“

b

01…0a2.m+\…a2j…a2n2

00…I…以…an.nb，n_

号，

因“，…，E”是一个基，其它向量可用这个基的线性组合来表示，有

P

J=1=1

P出

或j-<=«=0(1.20)

将(1.20)式乘上一个正的数e〉o得：

p£%e

0(>=»=«)=0(1.21)

(1.19)+(1.21)式并经过整理后有

m

Z6_&aPj=b

M(1.22)

m

ZPjX.=h

由(1.22)式找到满足约束方程组』的另一个点X⑴，有

X⑴=(#一-…,。，…,0),

6其中是X⑴的第j个坐标的值。要使X⑴是一个基本可行解，因规定0>0,故应对所有

i=l>,,,»m存在

咛-%20（1.23）

令这m个不等式中至少有一个等号成立。因为当为4°时，（1.23）式显然成立，故可令

1—I%>0»=

9二minI"".

故X⑴是一个可行解。又因与变量工「；石7"：+:.。斗”，弓对应的向量，经重新排列后加

上b列有如下形式矩阵（不含b歹U）和增广矩阵（含b歹U）

P?…P-P,儿…Pmb

0…0%0…0瓦

01…0%0…0h2

*■*••■♦*•*

•*••**

00…10…0瓦一1

00…0%0…0向

00…0ai+}j1…0坛।

•••••••

00…0a丽0…1b,“

因徇故由上述矩阵元素组成的行列式不为零，儿八，…，巳"与'E+I，…，匕是一个

基。

在上述增广矩阵中进行行的初等变换，将第/行乘上（"均）,再分别乘以（一％）（'=L

…+…，〃）加到各行上去，则增广矩阵左半部变成为单位矩阵，又因瓦/旬=9,

故

匕=（伪—珈_/，…，2-1-的-1,八夕，2+1—的+i,八…也”—为到）

由此X⑴是同X⑼相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。

3.最优性检验和解的判别

将基本可行解X前和X⑴分别代入目标函数得

=ZcM。-弧]+&」

1=1

r=li=l

m

=z@+e[CjNq%]

i=i（1.25）

[c厂Z]>0£_ZCiaij]

（1.25）式中因夕〉°为给定，所以只要有I，就有Z”）>z⑼。«=1

通常简写为（J-zQ或电,它是对线性规划问题的解进行最优性检验的标志。

（1）当所有的°，4°时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可

行解）的目标函数值都大，根据线性规划问题的可行域是凸集的证明及凸集的性质，可以判

定现有顶点对应的基可行解即为最优解。

（2）当所有的又对某个非基变量乙有Cj-Z/=°,且按（1.24）式可以找到

夕这表明可以找到另一顶点（基可行解）目标函数值也达到最大。由于该两点连线上的

点也是可行域内的点，且弓标函数值相等，即该线性规划问题有无穷多最优解。反之，当所

有非基变量的°，<0时，线性规划问题具有唯一最优解。

⑶如果存在某个%>°又4,由式（1.23）看出对任意的均有

":一勿歹二°，因而°的取值可无限增大不受限制。由式（1.25）看到z⑴也可无限增大，表

明线性规划有无界解・。

思考题如何利用原理构造算法？

作业课后习题3,9,10

实践作业相关建模练习

第四节单纯形法计算步骤

单纯形法的计算步骤如下：

第1步：求初始基可行解，列出初始单纯形表。

对非标准型的线性规划问题首先要化成标准形式。由于总可以设法使约束方程的系数矩

阵中包含一个单位矩阵（4,2,…，匕），以此作为基求H问题的一个初始基可行解。

为检验一个基可行解是否最优，需要将其目标函数值与相邻基可行解的目标函数俏进行

比较。为了书写规范和便于计算，对单纯形法的计算设计了一种专门表格，称为单纯形表（见

表1-5）。迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解

的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。

表1-5

CjCi•••Cn•••c.iCn

♦♦・

CB基bXix„•••XjXn

•♦••••

Cixibi10a«jXin

C2xb0♦♦♦0•••

22a2jX2n

:::•••••・♦•

*•

••••••

CnXnbn01clfljXin

0•♦♦0•••

Cj-Zjtnm

-Vc.a.

n4一/tn

i=li=\

单纯形表结构为：表的第2列〜3列列出基可行解中的基变量及聿口取值。接下来列出问

题中所有变最，基变显下面列是单位矩阵，非基变最山下面数字是该变量系数向量口表

为基向量线性组合时的系数。因小,...,P’是单位向量，故有

Pj=%泻+〃2力+，…，+♦.匕

表1-5最上端的一行数是各变量在目标函数中的系数值，最左端一列数是与各基变量对

应的目标函数中的系数值琮。

对Xj只要将它下面这一列数字与Cn中同行的数字分别相乘，再用它上端Cj值减去上述

乘积之和有

cca

/\Jiii,iJ

<7y=c.-+c2a2j+.•.+cinamj）='（126）

对j=l,…，n,将分别按（1.26）式求得的检验数bj,或写为（和一Zj）记入表的最下面一

行。

第2步：最优性检验。

如表中所有检验数"，一z，)40,且基变量中不含有人工变量时，表中的基可行解即

为最优解，计算结束(对基变量中含人工变量时的解的最优性检验将在下一节中讨论)。当

表中存在(勺-Z/)>°时，如有号则问题为无界解，计算结束；否则转下一步，

第3步:从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。

1.确定换入基的变量，只要有检验数bj>°,对应的变量与就可作为换入基的变量，

当有一个以上检验数大于零时，一般从中找出最大一个

<7k=max{%I*>0)

其对应的变量与，作为换入基的变量(简称换入变量)。

2.确定换出基的变量，根据上一节中确定o的规则，对几列由式(1.24)计算得到

6-min{—|aik>o]--

心aik(1.27)

确定匹，是换出基的变量(简称换出变量)。元素外决定了从一个基可行解到相邻基可

行解的转移去向，取名主元素。

3.用换入变量％替换基变量中的换出变量巧，得到一个新的基(p】，…，pi,Pk,

Pi”…,p)。对应这个基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表

(表1-6)«

在这个新的表中的基仍应是单位矩阵，即入应变换成单位向量。为此在表1—5中进行

行的初等变换，并将运算结果填入表1—6相应格中。

(1)将主元素所在L行数字除以主元素ag即有

b

bt=/

/。收(1.28)

(2)将表1-6中刚计箕得到的第L行数字乘上(-aik)加到表1-5的第i行数字上,记入表

1-6的相应行。即有

〃=2-且q(iw/)

。伙

与=b.------a式-1)

%(1.29)

表1-6

%J。…Cj•••Q-

••••♦•••♦•••

CB基b,,%Xj…4

b「b联/

1…•••0…a\j-a\k.一•••0•••

aikaik

*

_L...a

0…0•••,ij•••1•••

aikaik5k

*

C-V-bqamkbq

CmX,”°hI-u•••1…amj-a,nk-----•••0•••

6ka!k5k

（q-zjb.

C-Z.0•••0…（的z）（q_zy）0•••

aik

⑶表1-6变量的检验类l求法见式（1.26）o其中：

（G-Z/）=q----l-gq4文+ck-

a朱i=l/=/+1

qi<

一十—Z^ciaik

a改〃伙日

小

，一1mn/-1

（j-z/）=j-[Zcq+ZG%]一一t-X+q一£，%」

<=l/=/+1az=l<=/+1

ma9

car

=（j-Eiij）（，一工6怎）

a

r-liki=l

C

~~~（k_z〃）

=（Cj-Z/）alk（i,3j

第4步：重复第2,3两步，一直到计算结束为止。

例5用单纯形法求解线性规划问题

maxz=2X]+x2

5x<15

6x）+2X<24

,2

+x2<5

X],x2>0

解先将上述问题化标准形式有：

maxz=2司+x2+Ox3+Ox4

5X2+x3=15

6x）+2X2+x4=24

Xj+x2+x5=5

X\-5之°

其约束条件系数矩阵的增广矩阵为

RP2P3PA