线性规划模型及其应用

第四章 线性规划模型及应用

线性规划是运筹学的一个重要分支。运筹学：包括

线性规划所研究的问题：一是在资源（如钢材、电力等）受限制的前提下，研究如何合理使用这些资源，以完成更多的任务；二是在任务一定的前提下，研究如何合理安排，用最少的资源来完成给定的任务。

线性规划在实际应用中包括下列四个步骤： 1.确定问题，明确目标和限制因素； 2.建立模型； 3.模型求解；

4.应用模型和数据进行经济分析。 第一节 线性规划问题的数学模型-p2 第二节 线性规划问题的图解法-p8 第三节 线性规划问题的基本理论-p11 第四节 单纯形法-p16

第五节 运输问题的特殊解法

-p

第一节 线性规划问题的数学模型 一、问题的提出P138 二、数学模型的建立

例1：P137生产计划——最大利润问题

某企业拟生产A、B两种产品，需要经过车、铣两个工段，加工的工时定额、每天可用工时和两种产品可能获得的利润见下表。要求拟订一个获得利润最大的生产计划。

解：⑴确定变量。⑵确定目标函数。⑶列出约束条件。⑷决策变量为非负值。

设X1、X2分别为产品A、B的生产数量，则建立线性规划模型为：

MaxZ6x18x2

5x110x260



s.t.4x14x240

x,x0

12

例2：某工厂要做100套钢架，每套用长为2.9米、2.1米、

1.5米的圆钢各一根。已知原坯料每根长7.4米。如何下料，可使所用原材料最省？

解：单一下料，利用率低；套裁法，利用率高。 套裁下料方案：

设Ｘ1，Ｘ2，Ｘ3，Ｘ4，Ｘ5，Ｘ6分别表示六种下料方案切割的钢管根数，则截出：

（1）长2.9m的坯料数：Ｘ1+2Ｘ2+Ｘ4+Ｘ6根； （2）长2.1m的坯料数：2Ｘ3+2Ｘ4+Ｘ5+Ｘ6根； （3）长1.5m的坯料数：3Ｘ1+Ｘ2+2Ｘ3+3Ｘ5+Ｘ6根； 建模：

x,x,x,x,x,x123456 求

定义：求一组变量xj (j=1,2,......,n)的值，在满足线性约束条件下，使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。 3.标准形式

⑴目标函数为求最大值。若MinZc1x1c2x2cnxn，为把目标函数化为求最大值，只需令：Z1Z，

于是MinZMaxZMaxZ1，即MaxZ1MinZc1x1c2x2cnxn ⑵约束条件为等式。若约束条件为不等式，需化不等式约束条件为等式约束条件，只需引入新的非负变量以表示不等式左右两端的差额就可以了。这些新变量统称为松弛变量（剩余变量），它在目标函数中所对应的系数为零。

⑶决策变量xj有非负限制。若决策变量xk无非负限制，这样的变量称为自由变量。将它化为标准形式有两种方法：

0，xk0，令xkxkxk，①引进新的非负变量xk代入约束条件和目

标函数中，于是原问题就化为用n+1个非负变量来描述的线性规划问题。

②从约束条件中，选自由变量xk的系数不为零的等式，解出xk并代入其它m-1个约束方程和目标函数中，于是原问题就化为含n-1个非负变量，满足m-1个约束方程的线性规划问题。 ⑷约束条件右端常数bi≥0，若bi＜0时，对于等式约束，只需在等式两边同时乘以-1；对于不等式约束，只需在不等式两边同时乘以-1，同时改变不等号的方向。

xk 若xk0，令xk

例3.将线性规划问题的数学模型

MinZ3x14x22x35x4

4x1x22x3x42xx3xx141234s.t.

2x13x2x32x42 x1,x2,x30

化为标准形式。 解：

5x4 MaxZ13x14x22x35x4

x424x1x22x3x4

xx3xxxx14123445s.t.

2x4x622x13x2x32x4

,x4,x5,x60x1,x2,x3,x4

根据公式：4x1x22x3x42，得x4

4x1x22x32

MaxZ117x1x28x310

3x12x2x3x516

s.t.6x1x23x3x6

x,x,x,x,x0

12356

作业1：

MaxZx1x2

3x12x26

s.t.x12x24 x32

,x1,x2,x20，令x1x1x1,x2x2x2 解：引入x1

MaxZx1

x1x2x2 3x1

3x1x2x2x36s.t.x1x12x22x2x44x

2x2x53x1

,x1,x2,x2,x3,x4,x50MaxZx43x513

s.t.

x33x47x539

x3,x4,x 5

0作业2：令x3x3

，那么x30,即x30，则x30 MinZ3x14x22x35x4

4x1x22x3x42s.t.x1x23x3x4142x 13x2x32x40x1,x20,x30,x4无约束

MaxZ13x14x22x3

5x45x4 4x1x22x3

x4x42s.t.x1x23x3x4x4x514

2x13x2x32x42x4x

60x1,x2,x3

,x4,x4,x5,x60令x3x3

，那么x30,即x30，则x30 根据4x1x22x3x42，解得x44x1x22x32，代入MaxZ117x1x28x3

10

x5163x12x2x3



x64 s.t.6x1x23x3

x,x,x,x,x012356

第二节 线性规划问题的图解法

图解法是用作图的方法来求线性规划问题的解，它适用于仅含两个决策变量的线性规划问题的数学模型求解。虽然这种方法的应用范围受到很大的限制，但这种方法简单、直观，而且有助于理解线性规划问题求解的基本原理。 见教材P144 图解法步骤：

⑴求可行域：在平面直角坐标系中，可行域是各约束条件所表示的半平面的公共部分。

⑵求最优解：将目标函数Z看成参数，作出等值线，然后根据原问题求最大值（或最小值）的要求，令等值线沿Z值增加（或减少）方向在可行域内平行移动，直到找到等值线与可行域最后相交的一点，即为所要求的最优解。

通过图解法求解，其可行域与最优解有可能出现下列情况： 1. 可行域为有界域。 ⑴ 有唯一的最优解; ⑵ 有多个最优解。 2. 可行域为无界区域。 ⑴ 有唯一的最优解; ⑵ 有多个最优解;

⑶ 目标函数无界（即Z →∞），因此无有限最优解。 3. 可行域为空集，因此没有可行解。

以上情况示于下图中。图中的虚线表示等值线，虚线上的箭头表示等值线的移动方向，阴影部分为可行域。 综合上述讨论，可以看到：

1. 线性规划问题的解有四种可能：唯一最优解，多个最优解，无界解（即无有限最优解）和无可行解。

2. 线性规划问题的可行域（解）如果存在，其可行域一般是凸多边形（凸集）。

3. 线性规划问题的基本可行解对应线性规划问题可行域（凸集）的顶点。

4. 线性规划问题的最优解如果存在，则最优解一定在凸多边形的某一个顶点上取得（一定存在一个基本可行解是最优解）。上述结论，都可以推广到n个决策变量的线性规划问题上去。

第三节 线性规划问题的基本理论

一、线性规划问题的解

对于线性规划问题：

MaxZcjxj

j1

n

n

aijxjbii1,2,,ms.t.j1

x0(j1,2,,n)

j

假定系数矩阵A的秩为m，且m＜n。

先定义几个解的概念：

1.可行解：满足线性规划问题约束条件和非负约束的一组值X=（x1，x2，„，xn）T，称为线性规划问题的可行解。全体可行解的集合，称为线性规划问题的可行集或可行域。

2.最优解：使目标函数Z取得最大（小）值的可行解，称为最优解。最优解对应的目标函数值，称为最优值。

3.基、基变量、非基变量：系数矩阵A中任意一个非奇异m阶子矩阵B，称为线性规划问题的一个基。如果决策变量xj所对应的系数列向量Pj包含在B中，则称xj为基变量；否则，称xj为非基变量。显然，当基改变时，相应的基变量，非基变量也随之改变。

不妨设：

a11

B

am1

a12am2

a1n

1,P2,,Pm Pamn

则x1，x2，„，xm 为基变量，x m+1，x m+2，„，xm+n为非基变量，由假设m＜n，所以约束方程组

ax

ijj1

n

j

bii1,2,,m

有无穷多解。假设B为一个基，则在方程组

ax

ijj1

m

j

bi

jm1

axi1,2,,m

ij

j

n

中，令非基变量x m+1=x m+2=„=xm+n=0 得一个解：X=（x1，x2，„，xm，0，„，0）T

4. 基本解：对于有n个决策变量和m个约束方程的线性方程组，在取定基的情况下，令n-m个非基变量等于零，求得方程组的解，称这个解为线性规划问题的基本解。

5. 基本可行解：满足非负约束的基本解，称为基本可行解。对应于基本可行解的基B，称为可行基。

显然，一个线性规划问题的基本解的个数不超过Cnm个，因此，基本可行解的个数，一般说来要小于Cnm个。即基本可行解的个数要小于基本解的个数，最多是相等，而且每个基本可行解的非零分量个数不大于系数矩阵A的秩m。

6. 退化解：非零分量的个数小于m的基本可行解，称为退化解。 二、凸集

用集合来描述线性规划理论比较方便，为此，先定义： 线段：设A =（a1,a2,„,an），B =（b1,b2,„,bn）是n维欧

氏空间的任意两点，所有满足下列条件的点X=（x1，x2，„，xn）的集合

XA1B01

称为以A,B为端点的线段，A,B称为线段的端点，其余的点称为线段的内点。

凸集：设D为n维欧氏线性空间的一个点集。如果对任意的Xl ∈ D，X2 ∈ D, 有：

X = α Xl 十（1 一α ）X2 ∈ D （0

例如，图 14 - 3 中（a），（b）,（c）是由平面上任意两点连线上所有点组成的集合、四边形内所有点组成的集合、空间四面体内所有点组成的集合，都是凸集合 ; 而图14-3 的（d）就不是凸集合。

顶点：设D是凸集，X ∈ D, 如果D中不存在不同的两点 Xl，X2，使：

X= α Xl +（1 一α）X2 （0

则称X是D的一个顶点（或称极点）。即一个凸集的顶点，它不

能是该凸集的任何线段的内点。

凸组合：设Xl，X2，„，Xk是n维欧氏空间Vn中的k个点。如果存在λ1,λ2,„λk，且0≤λi≤1，（i=1,2,„,k），i

i1k

1，使：

X=λ1Xl+λ2X2+„+λk Xk，则称X为Xl,X2,„,Xk的凸组合。

三、线性规划问题的基本定理 定理 1 线性规划的可行解集合

DXAXb,xj0

，一定是凸集。

定理 2 线性规划问题的可行解为基本可行解的充分与必要条件是它的正分量所对应的系数列向量线性无关。

定理3



D设X





Pxb,x0，则jjj

j1

n

X是D的顶点的充分

与必要条件，X为线性规划问题的基本可行解。

定理 4 设D为有界凸集，则对任意X∈D, 可表示为D的顶点的凸组合。

定理 5 设可行域D有界，则线性规划问题的最优值一定在D的某个顶点达到。

例1所给的线性规划问题的基本解、基本可行解，并从中选出最优解。

解：引入松弛变量X3，X4，使数学模型化为标准形式：

MaxZ20x115x2

2x12x2x3600

s.t.3x1x2x4400

x,x,x,x0

1234

2210

由于AP1,P2,P3,P4 3101



显然，A的秩为2, 则线性规划问题的所有基本解、基本可行解如下表所示。由于最优解一定在可行域的顶点取得，而顶点又一定是基本可行解，且其个数是有限的，所以如例1, 只需求出该问题的所有基本可行解，将其对应目标函数值一一进行比较，就可得到最优解（见下表）。然而，当决策变量的个数n, 约束方程的个数m比较大时，上述方法是行不通的，正确的方法是构造一个逐步改进的基本可行解的序列，使其对应的目标函数值逐步向最优值接近，最终取得最优解。

线性规划问题的基本解与基本可行解

第四节 单纯形法

一、单纯形法原理 二、大M法与两阶段法 三、单纯形法的计算步骤 四、单纯形法的矩阵形式 （一）单纯形法的基本思路-p16

（二）一般线性规划问题的单纯形法-p27 （三）单纯形表-p31

（四）计算中可能遇到的几个问题-p37

单纯形法的基本思路是：从一个基本可行解出发，转移到另一个基本可行解，每一次转移都使目标函数值得到改善，这在数学上称为从一个基本可行解到另一个基本可行解的迭代。因为基本可行解反映在几何上就是可行域的一个顶点，而可行域的顶点个数是有限的，因此，经过有限次迭代后，就可取得最优解。先用一个例子来说明上述基本思路。 例1：P137生产计划——最大利润问题

某企业拟生产A、B两种产品，需要经过车、铣两个工段，加工的工时定额、每天可用工时和两种产品可能获得的利润见下表。要求拟订一个获得利润最大的生产计划。

解：

⑴确定变量。 ⑵确定目标函数。 ⑶列出约束条件。 ⑷决策变量为非负值。

设X1、X2分别为产品A、B的生产数量，Z表示利润，则建立线性规划模型为：

MaxZ6x18x2

5x110x260

s.t.4x14x240 x,x012

第一步将数学模型化为标准形式，并确定初始基本可行解。引入非负松弛变量x3,x4，得：

MaxZ6x18x20x30x4 ——（1）

5x110x2x360

s.t.4x14x2x440

——（2） x,x,x,x0

1234

约束方程组（2）的系数矩阵为：AP1,P2,P3,P4显然，P3与P4线性无关，因此，取BP3,P4

51014

4

0

 1

10

为基，于是，01

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

把（2）式改写成由非基变量表示基变量并代入（1）, 得：

Z06x18x2——（3）

x3605x110x2——（4） x404x4x124

令非基变量x1x20，得初始基本可行解：

X00,0,60,40

T

代入（3）式，得相应的目标函数值，Z0=0

从经济意义上讲，基本可行解X0表示一个可行方案，即工厂不安排生产A，B产品，工时也未动用，所以总利润Z0为零。

第二步检验初始基本可行解是否为最优解。

从（3）式可以看到，目标函数Z中非基变量x1,x2的系数均

为正数。如果将非基变量x1或x2转变为基变量，即x1或x2 的取值由零增大为正值，则总利润Z就会相应增加，这表明Z中非基变量的系数可以作为X0是否为最优解的检验数，当检验数为正数时，找到的基本可行解就不是最优解。因此X0不是最优解。

第三步基本可行解的改进——迭代过程。

当初始基本可行解X0不是最优解时，我们就要寻求新的基本可行解X1，使X1对应的目标函数值Z1＞Z0，这就要重新找基变量。

将原基本可行解中某个非基变量xk转变成基变量，则称xk

为换入变量。将原基本可行解中某个基变量xs转变成非基变量，则称xs为换出变量。

在（3）式中，因为x2的系数比x1的系数大，所以先让x2 增大，这对增大利润更为有利，所以选x2为换入变量，即选择目标函数中正系数最大的非基变量为换入变量。x2由零变为一个正值，此时x1仍为非基变量，其值为零，但x2的增大，必须保证x3,x4保持非负，因此，（4）式应满足：

60

x2610x36010x2040或 x404x0x102424

解此不等式组，得：x2

min6,106

当x26时，则x30，所以选基变量x3为换出变量。于是经过这一转换，新的基变量为x2,x4，非基变量为x1,x3。

为了求出以x2,x4为基变量的基本可行解，把（4）式改写成由新的非基变量x1,x3来表示新的基变量x2,x4，并代入 （3）式，得：（将x26

11

x1x3代入） 210

4

Z482x1x3

5——（5）

11

x26x1x3210

x162x2x——（6） 4135

令非基变量x1x30，得新的基本可行解

X10,6,0,16

T

代入（5）式，得相应的目标函数值：

Z148

这一结果表明，安排生产B产品6件时，可使总利润由零上升为48元。

由X0到X1的过程，称为第一次迭代过程，然后对Xl重复第二步、第三步的工作。

由（5）式，因为x1的系数为正数，所以X1不是最优解。现在在Z的表达式中，只有x1的系数为正数，因此选x1为换入变量。为保证x20,x40，x1的取值必须满足：

6

x11211/2x26x10216或

x81x4162x102

解此不等式组，得：x1min12,88 当x18时，x40，因此选x4为换出变量。

以新的非基变量x3,x4来表示新的基变量x1,x2，改写 （5）、（6）式，得：（将x18

11

x3x4代入） 52

2

Z64x3x4

5

11

x22x3x454

x81x1x13452

X28,2,0,0

T

令非基变量x3x40，得基本可行解：

相应的目标函数值为： Z2=64

此时，目标函数中非基变量x3,x4的系数非正，故目标函数值已无法改善，于是X2是最优解，Z2为最优值。从经济意义上讲，当安排生产A产品8件，B产品2件时，能获得最大利润64元，此时x3x40，它表示车床工时和铣床工时这两项资源已全部用完。

上述解法与第二节图解法进行比较可以看到：第一个基本可行解

x1x20, 对应于可行域中的顶点O，此时相应的目标函数值

Z0= 0; 第二个基本可行解x10，x26, 对应于可行域中的顶点B, 此时Z1=48; 第三个基本可行解，也就是最优解

x18，x22， 对应于可行域中的顶点E，此时最优值

Z2=64。这种从一个可行域的顶点，转移到可行域中相邻的另一个顶点，而相应的目标函数值转移一次改善一次，经过有限次的转移，就取得最优解，这正是单纯形法的基本思路。

某工厂生产两种产品A、B，每件A产品要消耗钢材2kg、煤3kg，其产值为20元。每件B产品要消耗2kg、煤1kg，其产值为15元。该厂现有钢材600kg，煤400kg，问A、B两种产品各生产多少件，才能使总产值最大。

解：设x1,x2分别表示A，B产品的产量，Z表示总产值，则该问题的数学模型为：

MaxZ20x115x2

2x12x2600

s.t.3x1x2400

x,x0

12

第一步将数学模型化为标准形式，并确定初始基本可行解。引入非负松弛变量x3,x4，得：

MaxZ20x115x20x30x4 ——（1）

2x12x2x3600

s.t.3x1x2x4400

——（2） x,x,x,x0

1234

约束方程组（2）的系数矩阵为：AP1,P2,P3,P4显然，P3与

2210

 

3101

10

P4线性无关，因此，取BP3,P401为基，于是，



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

把（2）式改写成由非基变量表示基变量并代入（1）, 得：

Z020x115x2——（3）

x36002x12x2——（4） x4003xx124

令非基变量x1x20，得初始基本可行解：

X00,0,600,400

T

代入（3）式，得相应的目标函数值，Z0=0

从经济意义上讲，基本可行解X0表示一个可行方案，即工厂不安排生产A，B产品，原材料也未动用，所以总产值Z0为零。

第二步检验初始基本可行解是否为最优解。

从（3）式可以看到，目标函数Z中非基变量x1,x2的系数均

为正数。如果将非基变量x1或x2转变为基变量，即x1或x2 的取值由零增大为正值，则总产值Z就会相应增加，这表明Z中非基变量的系数可以作为X0是否为最优解的检验数，当检验数为正数时，找到的基本可行解就不是最优解。因此X0不是最优解。

第三步基本可行解的改进——迭代过程。

当初始基本可行解X0不是最优解时，我们就要寻求新的基本可行解X1，使X1对应的目标函数值Z1＞Z0，这就要重新找基变量。

将原基本可行解中某个非基变量xk转变成基变量，则称xk为换入变量。将原基本可行解中某个基变量xs转变成非基变量，

则称xs为换出变量。

在（3）式中，因为x1的系数比x2的系数大，所以先让x1 增大，这对增大产值更为有利，所以选x1为换入变量，即选择目标函数中正系数最大的非基变量为换入变量。x1由零变为一个正值，此时x2仍为非基变量，其值为零，但x1的增大，必须保证

x3,x4保持非负，因此，（4）式应满足：



x1

x36002x10或x4003x0x114



2

3

3

600

2400 3

600400400

解此不等式组，得：x1min ,

400

3

当x1

时，则x40，所以选基变量x4为换出变量。于是

经过这一转换，新的基变量为x3,x1，非基变量为x4,x2。

为了求出以x3,x1为基变量的基本可行解，把（4）式改写成由新的非基变量x4,x2来表示新的基变量x3,x1，并代入 （3）式，得：（将x1

40011

x2x4代入） 333

80002520

Zx2x4

333——（5）

100042x3x2x4333

x4001x1x——（6） 124333

令非基变量x2x40，得新的基本可行解

4001000X1,0,,0

33

代入（5）式，得相应的目标函数值：

Z1

8000

3

4003

这一结果表明，安排生产A产品为

80003

件时，可使总产值由零上升

元。

由X0到X1的过程，称为第一次迭代过程，然后对Xl重复第二步、第三步的工作。

由（5）式，因为x2的系数为正数，所以X1不是最优解。现在在Z的表达式中，只有x2的系数为正数，因此选x2为换入变量。为保证x10,x30，x2的取值必须满足：

100041000/3

x3x20x2250334/3

x4001x0或x400/3400

2121/333

解此不等式组，得：x2min250,400250 当x2250时，x30，因此选x3为换出变量。

以新的非基变量x3,x4来表示新的基变量x1,x2，改写 （5）、（6）式，得：（将x2250

31

x3x4代入） 42

255

Z4750x3x4

42

31

x2250x3x442

x501x1x13442

X250,250,0,0

T

令非基变量x3x40，得基本可行解：

相应的目标函数值为： Z2=4750

此时，目标函数中非基变量x3,x4的系数非正，故目标函数值已无法改善，于是X2是最优解，Z2为最优值。从经济意义上讲，当安排生产A产品50件，B产品250件时，能获得最大产值4750元，此时x3x40，它表示钢和煤这两项资源已全部用完。

（二）一般线性规划问题的单纯形法

1. 确定初始基本可行解 设线性规划问题

MaxZcjxj （7）

j1

n

n

aijxjbii1,2,,ms.t.j1

（8） x0(j1,2,,n)

j

的约束方程组的系数矩阵A中含有m阶单位矩阵，不失一般性，不妨设m阶单位矩阵位于系数矩阵的前m列，因此它就组成一个基

1

0BP1,P2,Pm0

此时，约束方程组为：

0010



01

x1a1,m1xm1a1nxnb1

x2a2,m1xm1a2nxnb2xa ——（9） xaxbmnnnmm,m1m1xj0j1,2,,n

其中：x1,x2,,xm为基变量；xm1,xm2,xn为非基变量。

把（9）式改写为用非基变量来表示基变量的形式：

x1b1a1,m1xm1a1nxn

x2b2a2,m1xm1a2nxn



xmbnam,m1xm1amnxn

简写为：xibi

jm1

axi1,2,,m ——（10）

ij

j

n

令非基变量xm1xm2xn0，则得基本初始可行解：

X0b1,b2,,bm,0,,0

T

2. 最优性检验

将目标函数Z中的基变量也用非基变量表示出来，则：

nn

Zcixicjxjcibiaijxjcjxj i1jm1i1jm1jm1

m

n

m

cibici

i1

i1

mm

jm1

ax

ij

n

j



jm1

cxcbcxcax

jj

ii

jj

i

ij

j

i1

jm1

i1

jm1

m

ccajiijxj

jm1i1n

nmnmn

mm



cibicjxjciaijxjcibii1jm1i1i1

mn

令Z0cibi，j

i1

m

cjciaij

i1

m

，则：

ZZ0

jm1

x ——（11）

jj

n

最优解判别定理 设X0b1,b2,,bm,0,,0T为对应于基B 的基本可行解，且j0jm1,m2,,n，则 X0为最优解。

多重最优解判别定理（准则） 若X0b1,b2,,bm,0,,0T为一基本可行解，有j0jm1,m2,,n，且又存在某个非基变量的检验数mk0，则线性规划问题有多重最优解。

无界解的判别定理 设X0b1,b2,,bm,0,,0T为基本可行解，如果有某个非基变量检验数k＞0,且所有ak0i1,2,,m，则该线性规划问题没有有限最优解。

3. 基本可行解的改进

在最优性检验中，如果X0不是最优解，也不属于无界解的情况，那么就应进行基变换，寻找新的可行基及其对应的基本可行解。为此，我们分三步来完成。

⑴确定换入变量：检验数k>0所对应的非基变量xk都可作为换入变量。当有一个以上检验数大于零时，从中找出一个最大的k：

kmaxjj0

m1jn



对应的非基变量xk为换入变量。

⑵确定换出变量：确定换出变量的原则是保持解的可行性，就是说，要使原基本可行解X0中某一个正分量变为零，而其余分量均为非负，这时就选正分量变为零的那个基变量为换出变量。

为保证Xl的可行性，选择：

lmin

1im

bib

aik0l

aikalk

对应的基变量xl为换出变量。这一选择的原则，称为最小比值原则。

换入变量所在的列，称为主元列。换出变量所在的行，称为主元行。主元列与主元行交叉位置所在的元素，称为主元素。

⑶将换入变量xk所对应的系数列向量Pk变成单位向量。为此，只要对系数矩阵的增广矩阵进行“行”的初等变换。具体步骤是对第l行元素除以alk使主元素位置上变为1然后对第l行乘以alki1,2,,m,且il，加到第l行的对应元素上，使第k列的其他元素变为零，即：

0

a1k0Pkalk转换为10 amk

0

这一运算过程，称为旋转运算。

4. 重复第2步与第3步，直到求得最优解为止。

（三）单纯形表

用单纯形法求解线性规划问题的全过程，以表格的形式来表示，既简明又方便，这种计算表格称为单纯形表。

对给定的线性规划问题，首先将它化为标准形式，如 （7）式与（9）式所示，然后建立初始单纯形表

单纯性表

表中：

cj行——填入原目标函数中各决策变量xj的价值系数。 CB列——填入基变量对应的价值系数，它随基变量的改变而变

化。

XB列——填入目前的基变量，它将随每次迭代而变化。

b列——填入约束方程右端的常数。

xj行下方——依次填入相应约束方程中各变量的系数aij。

基变量检验数必为零，非基变量的检验数填j行——检验数行，入j

cjciaij

i1m

。

Z0格——表的右下角，填入该基本可行解对应的目标函数值的

m

相反数cibi

i1

在单纯形法计算过程中，每迭代一次，找出一个新的可行基时，就要重填一张单纯形表。

还是以例1中的线性规划问题为例，来说明单纯形表的运用。

先列出初始单纯形表

从表中可以看到：因为检验数10，20，所以基本可行解

X00,0,60,40

T

不是最优解，然后选x2（6＜8）为换入变量，且x3

（60/10＜40/4）为换出变量，10为主元素，进行一次迭代，得新的单纯形表。重复上述步骤，再进行一次迭代，就获得最终单

纯形表。从最终单纯形表中看到，因为所有检验数j0，所以基本可行解X28,2,0,0T为最优解，最优值为Z2688264。

X0=（0，0，60，40）T，Z0=0 X1=（0，6，0，16，）T，Z1=48 X2=（8，2，0，0）T，Z2=64

X0=（0，0，600，400）T，Z0=0

X1=（400/3，0，1000/3，0）T，Z1=8000/3 X2=（50，250，0，0）T，Z2=4750

作业MaxZ2x1x2x30x40x50x6

3x1x2x3x460xx2xx101235s.t.

x1x2x3x620x1,x2,x3,x4,x5,x60

X0=（0，0，0，60，10，20）T，Z0=0 X1=（10，0，0，30，0，10）T，Z1=20 X2=（15，5，0，10，0， 0）T，Z2=25 例3.用单纯形法求解线性规划问题：

MaxZ2x1x23x35x4

x17x23x37x4463xxx2x81234

s.t.

2x3xxx102341

xj0j1,2,3,4

解：引进松弛变量x5,x6,x7，将原问题化为标准形式：

MaxZ2x1x23x35x40x50x60x7

x17x23x37x4x5463xxx2xx812346

s.t.

2x3xxxx1023471

xj0j1,2,3,4,,7

由初始可行基B=(P5,P6,P7)建立初始单纯形表，并进行迭代见下表。因为所有检验数λj≤0，所以得最优解（最大值）： X2=（0，12/7，0，34/7，）T，Z2=26

例4.求解线性规划问题：

MinZ2x25x4x6

x12x20x3x4x50x620x3x0x4x2xx4123456

s.t.

0x1x2x32x43x50x63xj0j1,2,3,4,5,6

解：因为系数矩阵中列向量P1,P3,P6为单位向量，可作为可行基，所以x1,x3,x6为基变量，将目标函数化为标准形式：

MaxZ1Z2x25x4x6

约束条件已经是等式约束，所以保持不变。列初始单纯形表时，需要指出的是，检验数行的系数可以通过公式：

jcjciaij

i1m

计算后填入，也可以将目标函数中的基变量用非基变量表示后的系数填入，如本例，应先将目标函数Z1中的基变量x6用非基变量表示后

Z12x25x443x24x42x54x2x42x5

的系数填入检验数行（见下表）

因为λ1=4＞0，而它对应的x1系数列向量中各系数均小于零，所以原问题无有限最优解。 （四）计算中可能遇到的几个问题

1.求目标函数最小值的线性规划

对于处理这类问题的第一种方法是将它化为等价的求目标函数最大值的线性规划问题，应用单纯形法求解，两个问题的最优解是一样的，但它们的最优值相差一个符号。处理这类问题的另一种方法是，由（11）式知道，如果所有检验数λj≥0则：

ZZ0

jm1

x

j

n

j

Z0

而基本可行解X0使上式等号成立，故X0是最优解，且： minZ = Z0

所以求解目标函数为最小值的线性规划问题也可直接用单纯形法，所不同的只是当所有检验数λj≥0时，则相应的基本可行解X0为最优解。如果当X0不是最优解还需进一步迭代时，应选负检验数中取绝对值为最大者所对应的非基变量为换入变量进行迭代。

2. 选换入变量时，出现多种可能的情况

jj0时，出现有两个或两个以上相在对检验数行求max

同的最大正检验数，同它们所对应的非基变量都可以作为换入变量。但按决策变量、松弛变量、剩余变量的排列顺序，下标小的往往是决策变量，因此习惯于取下标小的非基变量为换入变量。

3. 选换出变量时，出现多种可能的情况 在应用最小比值法则时：

bb

maxiaik0l

aikalk

出现两个或两个以上相同的比值θ，同它们对应的基变量都可以作为换出变量。那么究竟选哪一个为换出变量呢？下面通过例（5）予以说明。

例5.这是一张求目标函数最大值的单纯形表

从上表可以看出，非基变量x1为换入变量，按最小比值法则，有两个相等的最小比值：θ1=θ2=3，与之对应的基变量X4，X5都可作为换出变量进行迭代（见下表）

从表上表可以看到，x4同x5无论哪一个作为换出变量，当换入变量x1由0增加到3时x4，x5，的值都将同时减少到0, 但只能让其中一个成为非基变量，其值自然为零，而另一个作为基变量其值也等于零，这就出现了退化解。如果选x4为换出变量，那么经过四次迭代后，取得最优解；如果选x5为换出变量，那

么经过两次迭代就取得最优解。因此，从相同的最小比值对应的基变量中一般选下标最大的基变量为换出变量。

4. 多重最优解

在单纯形表的最终表中，如果非基变量对应的检验数为零时，则所讨论的线性规划问题一般来说有无穷多个最优解。

例6.解线性规划问题：

MaxZ3x1x2

x1x2x34

xxx2124

s.t.

6x2xx18251

xj0j1,2,3,4,5

解：由初始可行基B=（P3,P4,P5）建立初始单纯形表，并进行迭代（见下表）

由于所有检验数λj≤0, 所以基本可行解 X1 =（3，0，1，5，0）T 为最优解，相应的最大值为：Z* =9

在最终表中，注意到除基变量的检验数为零外，还有非基变量x2的检验数也为零，这说明存在着可选择的另一个可能，令x2为换入变量，则x3为换出变量，再进行一次迭代（见上表）。又得到一个最优解：

X2 =（5/2，3/2，0，3，0）T 最大值仍为：Z* =9

由于可行域是凸集合，凸集合中两个不同的最优解X1和X2

的连线上的点都是最优解，例6有无穷个最优解，即有多重最优解。