运筹学

.第一章 线性规划与单纯形法

学习目标

    

了解线性规划模型特征并能根据实际问题写出线性规划模型 掌握线性规划化为标准型的方法

掌握线性规划的解的概念，并能够用图解法求解线性规划问题 熟练掌握线性规划的单纯形法

利用Matlab求解线性规划问题的最优解

引言

线性规划是应用数学模型对所研究的问题进行表述。线性（Linear）这个词是指模型中数学表达式的形式。规划（Programming）本质上是计划的同义词。因此线性规划是用线性数学模型表示不同的生产活动、营销活动、金融活动或其他活动的计划。

单纯形方法是美国数学家丹捷格（G.B.Dantzig）1947年提出的一般线性规划求解方法，自此以后线性规划在计算上趋向成熟，在应用中也日趋广泛和深入。

§1 线性规划数学模型

1.1问题的提出

线性规划应用的问题种类繁多，形式各异，主要分为四类线性规划问题。前三类问题分别是资源分配问题、成本效益问题以及网络配送问题。本节例1.1、例1.2、例1.3分别讨论了这三类问题。这些线性规划问题其共同特征是决策所基于的约束条件性质，三类线性规划问题约束分别是资源约束、收益约束、确定需求的约束。更多的实际问题包含至少有两种以上的约束。这类问题不能绝对地归属于这三类中的一类，于是把这第四类线性规划的问题称为混合问题。

例1.1资源分配问题

某工厂近期要安排生产甲、乙两种产品，产品甲需要用原料A，产品乙需要用原料B，由于两种产品都在一个设备上生产， 且设备使用时间有限，管理者必须合理安排两种产品的产量，使得在资源有限的条件下获得最大的利润。 因此这个问题的决策目标是收益的最大化， 研究者根据这个目标需要收集以下相关数据： 1)工厂两种原料存量以及可用设备工时数；

2)甲、乙两种产品的单位产品需要的原料和设备工时数； 3)甲、乙两种产品的单位产品利润。

1

单纯形法书稿

这些数据可以通过调研或估算得出，如表1.1所示： 表1.1

甲 乙

1 0 原料A󰀀 原料B 设备

0 2

2 3 3

x1------产品甲的数量

x2------产品乙的数量

Z ------利润

资源限制

6

8 18

4 单位利润(百万)

为建立模型，引入变量如下：

由表1.1最后一行知

Z＝4x1+3x2

目标是如何确定x1和x2，使得利润Z最大,同时需要满足资源约束。 对于原料A和原料B，有：

x1≤6，2x2≤8

对于设备工时，有：

2x1+3x2≤18

此外，甲、乙两种产品数量不可能是负值，因此，有如下对变量的非负约束：

x1 ≥0 , x2≥0

于是，问题的数学模型现在可以用代数式表述如下：

max Z＝4x1+3x2

满足：

x162x822x13x218x1,x20(1.1)(1.2)(1.3)(1.4)

实际上这是求一个线性函数在一组线性约束条件下的最大值问题，称之为线性规划问题模型。以上模型中，将x1、x2称为决策变量； Z＝4x1+3x2为目标函数；约束(1.1)～(1.3) 为函数约束；(1.4)为非负约束。

从以上过程我们可以归纳出根据实际问题建立线性规划模型的步骤： 1) 根据管理层的要求确定决策目标和收集相关数据。 2) 确定要做出的决策，引入决策变量。 3) 确定对这些决策的约束条件和目标函数。

例1.2 成本效益平衡问题

某饲料公司希望用玉米、红薯中原料配制一种混合饲料，各种原料包含的营养成分和采购成本都不同，公司管理层希望能够确定混合饲料中的各种原料数量，使得饲料能够以最低成本达到一定的营养要求。研究者根据这一目标收集到的有关数据如下（见表1.2）

表1.2

营养成分 碳水化合物 每公斤玉米 8 每公斤红薯 4 最低要求 20 2

单纯形法书稿

蛋白质 维他命 采购成本（元/公斤） 3 1 0.8 6 5 0.5 18 16 为建立线性规划模型，我们引入变量如下： x1=混合饲料中的玉米数量； x2=混合饲料中红薯的数量；

目标函数 Z=0.8x1+0.5x2，表示产量的成本函数，即如何确定x1,x2 使得成本Z=0.8 x1+0.5 x2最低且满足最低营养要求的约束，这些约束条件是： 碳水化合物要求：8 x1+4x2≥20 蛋白质物要求： 3 x1+6x2≥18 维他命物要求： x1+5x2≥16 另外非负约束： x1≥0，x2≥0 因此这个问题的线性规划模型为：

minZ0.8x10.5x28x14x2203x6x18 12s.tx15x216i1,2xi0其中“s.t.”是“subject to”的缩写，意思是“受约束于„„”。

例1.3 物流网络配送问题

某物流公司需要将甲、乙、丙三个工厂生产的一种新产品送到 A、B 两个仓库，甲、乙两个工厂的产品可以通过铁路运送到仓库A，数量不限；丙工厂的产品可以通过铁路运送到仓库B，同样，产品数量不限。 由于铁路运输成本较高，公司也可以考虑由独立的卡车来运输，可将多达80个单位的产品由甲、乙、丙三个工厂运到一个配送中心，在从配送中心以最多90单位的载货量运到各个仓库。公司管理层希望以最小的成本运送所需的货物。 为了建立该问题的数学模型，必须先了解这一网络配送问题的活动和要求。该问题涉及三个产品的生产和各线路的运输量，由于产量给定，所以决策终点是运输水平，即各线路的运输量。 首先，需要收集每条线路上的单位运输成本和各工厂产品的产量以及各仓库分配量等数据，如表1.3所示。

表1.3 工厂甲 工厂乙 工厂丙 配送中心 需求量 配送中心 $3.0 $3.5 $3.4 -- -- 仓库A $7.5 $8.2 -- $2.3 120 仓库B -- -- $9.2 $2.3 130 运输量 100 80 70 250

为了更清楚地说明问题，我们用网络图来直观表示该配送问题。见图1.1：其中 ，v1、v2、v3 表示甲、乙、丙三个工厂，节点v4表示配送中心，节点v5、v6表示两个仓库；每一条箭线表示一条可能的运输线路，并给出了相应的单位运输成本，对运输量有限制的路线的最大

3

单纯形法书稿

运输能力也同时给出。

我们要解决的是各条线路最大运输量，引入变量xij表示有vi 经过路线(vi，vj )运输到vj 的产品数。 问题的目标是总运输成本最小化，总运输成本可以表示为： 总运输成本 = 7.5x15+3 x14+8.2x25+3.5 x24+2.3 x45+3.4 x34+2.3x46+9.2 x36

$7.5 生产100 v1 $3 80 生产80 v2 $3.4 80 生产70 v3 v6 $9.2 图1.1 相应的约束条件包括对网络中的每个节点vi (i=1,2,...,6)的供求平衡约束。对生产节点v1、v2、v3来说，由某一节点运出的产品数量等于其产量，即

130仓库B $3.5 80 90 v4 $2.3 $8.2 $2.3 90 v5 120仓库A x15+x14=100 x25+x24= 80 x34+ x36=70

对配送中心v4运进的产品数量等于运出的产品数量

x14+ x24+ x34=x45+ x46

对仓库v3、v5，运进的产品数量等于其需求量

x15+ x25+ x45=120 x46+x36 =130

此外，对网络中有运输容量限制的路线的约束是：该路线上的运输产品数量不超 过该线路的运输能力，即

x14≤ 80，x24 ≤80, x34≤80, x45≤90, x46≤90

并且，所有xij ≥0 (非负约束)。因此，这个问题的线性规划模型为：

min Z=7.5x15+3 x14+8.2 x25+3.5 x24+2.3 x45+3.4 x34+2.3 x46+9.2 x36

x15x15100xx802524x34x3670x14x24x34x45x46 s.t.

xxx120152545x46x36130x1480,x2480,x3480,x4590,x4690x0ij4

单纯形法书稿

从以上的几个例子可以看出，线性规划问题有如下共同特征：

1）每个问题都用一组决策变量，这组决策变量的值都代表一个具体方案。

2）有一个衡量决策方案优劣的函数，它是决策变量的线性函数，称为目标函数。按问题不同，要求目标函数实现最大化或最小化。

3）存在一些约束条件，这些约束条件包括(1) 函数约束；(2)决策变量的非负约束。

1.2 线性规划的标准型

根据上节分析，线性规划的一般形式为：

max(min) Z= c1x+c2x2+  +cnxna11x1a12x2a1nxn,b1a21x1a22x2a2nxn,b2s.t. axaxax,bmnnmm11m22x1,x2,,xn0

线性规划问题有各种不同的形式。目标函数有的要求max, 有的要求min；约束条件可以是 “≤”， 也可以是“≥”形式的不等式，还可以是等式。决策变量一般是非负约束，但也允许在（-∞，∞）范围内取值，即无约束。将这种多形式的数学模型统一变换为标准形式。这里规定的标准形式为：目标函数的要求是max，约束条件的要求是等式，决策变量的要求是非负约束。在标准型式中规定各约束条件的右端项bi≥0，否则等式两端乘以“-1”。 用向量和矩阵符号表述时为：

max z=CXns.t.Pjxjb

j1x0,j1,2,,nj其中：Ｃ＝（c1,c2,„,cn）

a1jx1b1xba2j2X;Pj;b2

xanbmmj向量Pj 对应的决策变量是xj。

用矩阵描述时为：

max z=CX AX=b X≥0

5

单纯形法书稿

a11a12其中Aam1am20a1n0 P1,P2,,Pn;0amn0称A为约束条件的m×n维系数矩阵，一般m0; b为资源向量； C为价值向量；

X为决策变量向量。

下面讨论化标准型的方法：

（1）若要求目标函数实现最小化，即min z=CX。这时只需将目标函数最小化变换求目标函数最大化，即令 z′=-z，于是得到max z′= －CX。这就同标准型的目标函数的形式一致了。 （2）约束方程为不等式。这里有两种情况：一种是约束方程为‘≤’不等式，则可在‘≤’不等式的左端加入非负松弛变量xj，把原‘≤’不等式变为等式； 另一种是约束方程为‘≥’不等式，则可在‘≥’不等式的左端减去一个非负剩余变量xk（也可称松弛变量），把不等式约束条件变为等式约束条件。

（3）若变量约束中：xi ≤0,则令xi′= －xi 得到xi′≥0；若xj0,则令 xj = xj′－ xj〞,

得xj′, xj〞≥0, 用 xi′，xj′，xj〞分别代替xi，xj后得到线性规划的变量约束均为非负约束。

（4）目标函数中加上0xi (松弛变量) 下面举例说明。

例1.4 将下述线性规划化标准型 maxZ2x13x2x12x28 4x16 1加入松弛s..t变量以后4x212x1,x20例1.5 将下述线性规划化标准型

maxZ2x13x20x30x40x

x12x2x34xx41s.t.4x2x1,x2,x3,x4,x50816x512

minzx12x23x3x1x2x37xxx2 123s.t.3x1x22x35x1,x20,x3取值无约束解：按上述规则化标准型如下： 1. 用x4-x5替换x3,其中x4, x5≥0;

2. 在第一个约束不等式≤号的左端加入松弛变量x6; 3. 在第二个约束不等式≥号的左端减去剩余变量x7;

4. 令z′=-z, 把求min z改为求max z′，即可得到该问题的标准型

6

单纯形法书稿

maxz'x12x23(x4x5)0x60x7x1x2(x4x5)x67xx(xx)x721245s.t.53x1x22(x4x5)x1,x2,x4,x5,x6,x70

1.3 线性规划问题的解的概念

在讨论线性规划问题的求解前，先要了解线性规划解的概念。一般线性规划问题的标准型为：

max{Z=CX|AX=b,X≥0}

可行解： 满足上式约束条件的解x=(x1,x2,x3,…,xn)T ，称为线性规划问题的可行解。全部可行解的集合称为可行域。

最优解： 使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。

基： 设Am×n(m基解： 在约束方程组的关系矩阵中，设Ｂ= (P1,P2,„,Pm),则x1,x2, x3,„, xm为基变量，xm+1,„，xn为非基变量，令所有非基变量xm+1 ,„，xn为０，得到约束方程BXB=b,由

T

克莱姆法则可得到唯一解XB = (x1,x2,„, xm)，则称由约束方程确定的唯一解X=(x1,x2,

T

x3,„, xm,0,„,0),X为线性规划问题的基解。

基可行解：满足约束条件的基解称为基可行解。

可行基： 对应于基可行解的基称为可行基。若基可行解XB中至少有一个分量为零，则称为退化的基可行解。

由此可知，退化基可行解中的非零分量一定小于m, 非退化解中非零分量一定等于m，若有关线性规划问题的所有基可行解都是非退化解，则该问题为非退化线性规划问题； 否则，称为退化线性规划问题。各解的关系如图1.2

7

单纯形法书稿

非可行解 可行解 基 可 基解 行 解

图1.2

例1.6 写出例1.1的标准形式，指出基、基变量、基解、基可行解和可行基。 解： 显然，标准形式为

maxz4x13x20x30x40x5x1 s.t.2x1xj010100

A0201023001100矩阵秩不大于３，而(p3,p4,p5)010是一个３×３的满秩阵，故(p3,p4,p5)是一001个基,x3,x4,x5是基变量，令x36,x48,x518,则x(0,0,6,8,18)x1,x2是非基变量。

Tx32x23x2j1,,5x4x568

18由此，约束方程的系数矩阵为

是一个基解。因该基解中所有变量取值为非负，故又是基可行解，对应的基(p3,p4,p5)是一个可行基。

1.4 线性规划问题的图解法

图解法简单直观，有助于了解线性规划问题求解的基本原理。现用第一节例1.1来说明图解法 。例1.1的线性规划问题是：

8

单纯形法书稿

maxZ4x13x2x162x8 2s.t.2x13x218x1,x20我们首先建立x1Ox2 坐标平面（见图1.3），坐标系上的横轴是x1轴，纵轴是x2轴。由

非负约束x1≥0、x2≥0可知，所有可行解的集合（称为可行域）应在第一象限。然后，我们要逐个地查看每个函数约束都允许的非负解，最后再综合考虑所有的约束条件。

第一个函数约束x1≤6，截取x1轴的直线x1=6线或线左边的解是满足这个约束条件的； 第二个约束2 x2≤８,即x2=4线及下方的解满足这个约束。我们将函数约束条件的边界直线称为约束边界，相应的方程称为约束边界方程。通常一个不等式约束的边界方程是用等号代替不等号。用L1表示边界方程x1=6；L2表示边界方程２x2=8; 对于另外一个函数约束２x1+3x2≤18,我们用L3表示它的约束边界方程２x1+3x2。=18。L3在x1轴和x2轴上的交点分别为（9，0）和（0，6），L3 将平面分为两个部分。约束２x1+3x2≤18所允许的解是位于L3靠近原点这边的部分，证实这一结论的最简单的办法是检验原点O(0,0) 是否满足约束条件，如果是，说明允许区域位于约束边界靠近原点的那一边，否则，位于另一边。

由于线性规划问题的一个可行解必须同时满足所有约束条件，我们要组合所有约束条件到一个图上，并且确定所有可行解的集合，即所有单个约束条件允许解的交集，如图的阴影部分。

8765432112345678910可行域l3:2x1+3x2=18L3: 2x1+3x2=18 x1=6x1=6 x2=4 x2=4

图1.3

确定了可行域后，我们希望找出可行域中哪些解是最优解，即使目标函数Z=4x1+3x2尽

可能大的可行解。为做到这一点，我们考虑给目标函数一个值，例如给定Z＝12，显然可以在图上画出一条直线4x1+3x2=12（见图1.4），在直线上任一点处，对应的目标函数值均为12，故称该直线为目标函数的等值线。Z=12只是目标函数的一个给定值，对于其他Z的给定值，如Z＝15也可在图上画出一条直线4x1+3x2=15，显然，对于Z的不同给定值k，4x1+3x2=k是一组平行的直线族，当k的值由小变大时，目标函数的等值线平行移动，它与可行域的最后一个交点（一般是可行域的一个顶点）就是所求的最优点，即图1.4中的B点。

另一种解法，在图中作出梯度方向=（4,3），在可行域作出一条直线垂直，当该直

9

单纯形法书稿

线沿着梯度方向平移时，目标函数值增大。否则，沿着反梯度方向平移时，目标函数值减小。本题是求最大值，所以该直线沿梯度方向平移，离开可行域的最后一点B（6,2）为最优解。

7L3: 2x1+3x2=18 6l3:2x1+3x2=18x1=6x1=6 54321-1-14x4x1+3x2=121+3x2=12 4x1+3x2=15 4x1+3x2=15

图1.4

由上例可以看出，线性规划问题的最优解出现在可行域的一个顶点上，此时线性规划问题有唯一最优解。但有时线性规划问题还可能出现有无穷多个最优解，无有限最优解，甚至没有可行解的情况，我们仍通过例子说明。

1）无穷多最优解。若将上例中的目标函数变为求max Z=4x1+6x2，则目标函数与等值区域边界线2x1+3x2=18平行，线段BC上的任意一点都使Z取得相同的最大值，此时线性规划问题有无穷多最优解，如图1.5所示。

x1=6 x1=6x2=4 x2=4可行域B最优解1234567891076D54E321可行域C无穷多最优解xx2=42=4 Z=4x1+6x2Z=4x1+6x2 A-1-112345678910 图1.5

2）无界解。考虑下列线性规划问题

10

单纯形法书稿

maxZx1x22x1x23 s..tx12x24x,x012在坐标平面上作边界线L1 、L2，确定可行域（如图1.6中的阴影部分所示），可以看出可行域无界，为求最优解作等值线x1 +x2 =k ,当k由小变大时，等值线沿梯度方向（1，1）T

平行移动，不论k值增大多少，等值线上总有一段位于可行域内，因此目标函数无上界，该问题无有限最优解,如图1.6所示。

L1L1 xx1+x2=k1+x2=k 可行域L2 L2 L1x1+x2=k可行域L2

图1.6

事实上，可行域无界时线性规划问题有时也有有限最优解，如上例中当目标函数变为

max Z=- x1-x2时，线性规划问题有时也有有限最优解x1=3,x2=0,即目标函数在（3，0）点处取得最大值。 3）无可行解。如果在例1.1的线性规划问题中增加一个约束条件x1+x2>12,我们有边界方程L4: x1+x2=12,约束条件为L4的上方，则该问题的可行域为空集，即没有一个点满足所有的约束条件，问题无可行解，也不存在最优解。

11

单纯形法书稿

图解法适用于求解只有两个决策变量的线性规划问题，具体步骤如下：

1） 画出每个函数约束的约束边界，用原点（或其它不再边界上的点）判断直线的哪一边是

约束条件所允许的。

2） 找出所有约束条件都同时满足的区域，即可行域。 3） 给目标函数一个特定的值k,画出目标函数等值线，当k变化是，目标函数等值线平行移

动； 对于目标函数最小化的问题，找出目标函数减少的方向，目标函数最后离开可行域的点是最优解。

4） 从图解法可以看出，线性规划问题的可行域非空时它是一个凸多边形，若线性规划问题

存在最优解，它一定在可行域的某个顶点得到，若有唯一最优解，则一定在可行域的顶点处得到；若两个顶点同时达到最优解，则两个顶点之间线段上的任意一点都是最优解。

§2 单纯形法

从上一节中我们看到，若线性规划有最优解，必在可行域的某个顶点达到。最可能想到的是把所有顶点都找出来，然后逐个比较，求出最优解，这种方法事实上是行不通的，因

20为顶点的个数非常大。例如m=20，n=40，顶点的个数有C40≈1.3×1011个，要计算这么多

顶点对象目标函数值，显然是不可能的。

换一种思考方法，从某一个基本可行解出发，每次总是寻找比上一个更好的基本可行解，如果不比上一个好就不去计算，这样做就大大减少计算量。其基本想法是判别当前解是否最优，提出问题的标准，从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数逐步增大，最后就得到了最优解。美国数学家丹捷格（G.B.Dantzig）提出的单纯形方法解决了此问题，单纯形方法到目前为止是求解线性规划的最普遍最有效的方法。

2.1初始基可行解的确定

为了确定初始基可行解，要首先找出初始可行基，其方法如下： 1） 若线性规划问题

maxzcjxjj1n

nPjxjbs.t.j1x0;j1,2,,nj

(6.1)10从Pj(j=1,2,„,n)中一般能直接观察到一个初始可行基：B00010

012）对约束条件是“≤”形式的不等式，在每个约束条件的左端加上一个松弛变量。经整理，

12

单纯形法书稿

重新对xj及aij进行编号，可得到下列方程组：

x1x2a1,m1xm1a1nxnb1a2,m1xm1a2nxnb2

(6.2)...................................................xmam,m1xm1amnxnbm10显然可以得到一个单位矩阵：B0以B 作为可行基，将每个等式移项：

0010 01x1b1a1,m1xm1a1nxnx2b2a2,m1xm1a2nxn...................................................xmbmam,m1xm1amnxn得到一个初始基可行解：

X=（x1,x2,„,xm,0,„,0）

T

=（b1,b2,„,bm,0,„,0）

3）对所有约束条件是“≥”形式的不等式及等式约束情况，化为标准型后若不存在单位矩阵式，就采用人造基方法。 即对不等式约束减去一个非负剩余变量，再加上一个非负人工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。（有关加上人工变量的线性规划问题，以后再讨论。）

T

(6.3)令xm+1=xm+2= „ =xn=0,由上式可得： xi=bi （i=1，2，„，m）

2.2 最优解的检验和解的判别

由两个变量的线性规划图解方法我们得到启示，线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况，为此需要建立对解的判别准则。根据上节得到的基解计算公式可归纳如下：

xibijm1ax(i1,2,m)

ijjn将上式代入目标函数式，整理后得到：

zcibii1mjm1(cca)xjiiji1nmj

令

13

单纯形法书稿

,z0cibi,zjciaiji1i1mmjm1,,n

于是 zz0再令jcjzjnjm1(cnjzj)xj

(jm1,,n)

则 zz0jm1jxj

,b2,,bm,0,,0)T为对应于基B 的一个基可行解，且1). 最优解判别定理：若X(0)(b1对于一切j=m+1,„,n有j0，则X(0)为最优解。称j为检验数。

,b2,,bm,0,,0)T为一基可行解，对于一切2). 无穷多最优解判别定理：若X(0)(b1j=m+1,„,n，有j0，又存在某个非基变量的检验数mk0,则线性规划问题可能有无穷多最优解。

,b2,,bm,0,,0)T为一基可行解，有一个mk0，并3). 无界解判别定理：若X(0)(b1且对k=1,2,„，m，有ai,mk≤0,那么该线性规划问题具有无界解（或称为无穷解或无最优解）。

2.3 基变换

若初始基可行解X(0)不是最优解及不能判断无界时，需要找一个新的基可行解。具体做

法是从原可行解基中换出一个列向量（当然要保持线性独立），从原非可行基中换入一个列向量，得到一个新的可行基，这称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行交换，得到一个新的基可行解。 1)换入变量的确定

当某些j0时，xj 增加则目标函数值还可以增大，这时要将某个非基变量xj换入到基变量中去（称为换入变量）。若有两个以上的j，那么选j0中大的那个，即：

max(j>0)= k 则对应的xk 为换入变量。但也可以任选或按最小足码选。

2)换出变量的确定

在确定xk为换入变量后，由于其他的非基变量仍然为非基变量，即xj=0 (j=1,2,…n且j≠k), 则由约束方程组有

14

单纯形法书稿

xibiai,1x1ai,kxkainxn0xk(aik0,i1,2,,m)xibiai,1x1ai,kxkainxn0 xk由于所有的xj0,所以若令

bi(aik0,i1,2,,m)aikminibi|aik0aikb(i1,2,,m)l

alk则xk的增加不能超过，此方程相应的变量xl即为换出变量。这是的值是按最小比值来确定的，称为最小比值原则；与此相应的alk称为主元素。

2.4 单纯形表

首先介绍一下单纯形表： 为了计算上的方便和规格化，对单纯形法计算设计了一种专门表格，称为单纯形表。表格如下1.4

表1.4

cj→ CB c1 c2 XB x1 x2 b b1 b2 c1 x1 1 0 „„ „„ „„ „„ „„ „„ cm xm 0 0 cm+1 xm+1 a1,m+1 a2,m+1 „„ „„ cn xn a1n a2n θi θθi i  cm -z  xm m bm  0 0  1 0 cibi i1„„ „„  am,m+1 „„ mcm1ciai,m1 „„  amn m θi i1cnciain i1

在单纯形表的第2-3列列出某个基可行解中的基变量及它们的取值，接下来列出问题中的所有变量。在基变量下面各列数字分别是对应的基向量数字。表中变量x1,x2 ,…xm下面各列组成的单位矩阵就是初始基可行解对应的基。

其中： 每个基变量xj下面的数字，是该变量在约束方程的系数向量Pj 表达为基向量线性组合时的系数。

cj 为表最上端的一行数，是各变量的目标函数中的系数值

CB为表中最左端一列数是与各基变量对应的目标函数中的系数值； b 列中填入约束方程右端的常数； 检验数jcjzj(jm1,,n)称为变量xj 的检验数，将xj下面的这列数字Pj与

CB这列数中同行的数字分别相乘，再用xj上端cj值减去上述乘积之和

15

单纯形法书稿

即： cj(c1aj1ca2j2cmamj)cjcai1miij ；

θi列的数字是在确定换入变量后，按θ规则计算后填入；其中i换入变量）。

bi（其中xj 为(aij0)。

aij2.5单纯形法的计算步骤

根据以上讨论，将求解线性规划问题的单纯形法的计算步骤归纳如下： 第一步：求出线性规划的初始基可行解，列出初始单纯形表。 第二步：进行最优性检验。各非基变量检验数为jcjzj(jm1,,n)，如果，

j≤０，则表中的基可行解是问题的最优解，计算到此结束，否则进入下一步。

第三步：在j>0, j=m+1,,n中，若有某个k对应xk的系数列向量Pk≤０，则此问题无界，停止计算。否则，转入下一步。

第四步：从一个基可行解换到另一个目标函数值更大的基可行解，列出新的单纯形表。

(1) 确定换入变量，有j0，对应的变量xj就可作为换入变量，当有两个以上检验

数大于零，一般取最大的k，即kmax{j|j0}，取xk 作为换入变量。 (2) 确定换出变量。根据最小θ规则，对Pk列由公式计算得：

biblx确定是l换出变量。 min|aik0aikalk(3) 元素alk决定了从一个基本可行解到另一个可行解的转移去向，取名为主元素。以

alk 为主元素进行旋转变换，得到新的单纯形表，转到步骤二。

下面，我们用例1.1说明单纯形表进行迭代运算：

根据问题的标准型，取松弛变量x3,x4,x5为基变量，对应得单位矩阵的基得到初始基可行解X=(0,0,6,8,18),得到初始单纯形表，如表1.5所示。 表1.5 CB 0 0 0 -Z cj→ XB x3 x4 x5 4 3 0 0 0 b 6 8 18 0 x1 x2 x3 x4 x5 [1] 0 1 0 0 0 2 0 1 0 2 3 0 0 1 4 3 0 0 0 6/1 － 18/2 θi (0)T其中，非基变量的检验数

16

单纯形法书稿

11c1CBB1P14(0,0,0)04

202c2CBB1P23(0,0,0)23

32)由检验数1,2大于零，P1,P2有正分量，转入下一步 3）max(1,2)=max(4,3)=4，对应x1为进入变量，

minbi/ai1|ai10min6/1,，18/26

它对应的基变量x3是换出基变量，x3所对应的行与x1所对应的列包括检验数变为。 (1,0,0,0)T，在XB列将x3换成x1得到新单纯形表（表1.6）表1.6 CB 4 0 0 -Z

此时，新基变量XB=（x1,x4,x5）,对应于基可行解X=(6,0,0,0,8) ,相应的目标值Z=24.检验表1.6中的检验数行得知x2的检验数为3>0，说明x2应为换入基变量，计算值：

T

(1)

T

cj→ XB x1 x4 x5 4 3 0 0 0 b 6 8 9 -24 x1 x2 x3 x4 x5 1 0 1 0 0 0 2 0 1 0 2 [3] -2 0 1 0 3 -4 0 0 θi － 8/2 6/3 min{bi|ai20}min{,8/2,6/3}2 ai2所以对应的x5为换出基变量，基变量x5的行与进入基变量x2的列交叉处元素3为主元

T

素，再对主元素进行旋转变换，使x2列变为单位向量(0,0,1,0) 得到表1.7

表1.7 CB 4 0 3 -Z cj→ XB x1 x4 x2 4 3 0 0 0 b 6 4 2 -30 x1 x2 x3 x4 x5 1 0 1 0 0 0 0 4/3 1 -2/3 0 1 -2/3 0 1/3 0 0 -2 0 -1 6 4 2 -30 θi 此时，基变量为XB=( x1, x４, x２)T ,对应的基可行解为X(3)=(6,2,0,4,0)T,对应目标函数值Z=30。由于所有检验数均小于或等于0，所以此解是最优解，对应基为最优基。

17

单纯形法书稿

§3 单纯形法的进一步讨论

3.1 人工变量法

在前文中提到用人工变量法可以得到初始基可行解。但加入人工变量的数学模型与未加人工变量的数学模型一般是不等价的，一般情况下关于这一点有以下结论：

(1)加入人工变量的线性规划用单纯形方法得到最优解中，人工变量处在非基变量位置。 (2)最优解中，人工变量可能在基变量中，但取值为零，则可以求出原问题的最优解。若最 优解中包含有非零的人工变量，则原问题无可行解。

对以上结论，我们不作更多的理论上的证明，只介绍具体算法。 设线性规划问题的约束条件是

pxjj1njb

分别给每一个约束方程加入人工变量xn+1,…,xn+m, 得到

a11x1a12x2a1nxnxn1b1a21x1a22x2a2nxnxn2b2 axaxaxxbmnnmnmm111m22x1,x2,,xn0,xn1,xnm0以xn+1,…，xn+m为基变量，并可得到一个m×m单位矩阵。令非基变量x1,…,xn为零，便可得

到一个初始基可行解

X(0)(0,,0,b1,b2,,bm)T

因为人工变量是最后加入到原约束条件中的虚拟变量，要求将它们从基变量中逐个替换出来。若经过基的变换，基变量中含有某个非零人工变量，这表示有可行解。若在最终表中当所有 cj-zj≤0,而在其中还有某个非零人工变量，这表示无可行解。

1）大M法 2）

在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为此假定人工变量在目标函数(max z)中的系数为(-M)（M为任意大的正数），若目标函数为min Z，则人工变量在目标函数中系数为M，这样目标函数要实现最大化（最小化）时，应把人工变量从基变量换出，或者人工变量在基变量中，但取值为0。否则目标函数不可能实现最大化。

例1.7 现有线性规划问题

18

单纯形法书稿

minZ3x1x2x3x12x2x3114xx2x3 123s.t.x312x1x1,x2,x30试用大M法求解。

解: 在上述问题的约束条件中加入松弛变量，剩余变量，人工变量，得到

minZ3x1x2x30x40x5Mx6Mx711x12x2x3x44xx2xx5x63123s.t.x3x712x1x1,x2,x3,x4,x5,x6,x70

这里M是一个任意大的正数。

用单纯形法进行计算时，见表（1.8）。因本例是求Min，所以用所有cj-zj≥0来判别目标函数是否实现了最小化。表中的最终表表明得到最优解是

x1=4, x2=1, x3=9, x4=x5=x6=x7=0

目标函数

z= -2

表1.8

cj→ CB 0 M M cj-zj 0 M 1 cj-zj 0 1 1 cj-zj -3 1 1 cj-zj x1 x2 x3 x4 x6 x3 x4 x6 x3 XB x4 x6 x7 b 11 3 1 10 1 1 10 1 1 4 1 9 2 -3 x1 1 -4 -2 -3+6M 3 0 -2 -1 [3] 0 -2 -1 1 0 0 0 1 x2 -2 1 0 1-M -2 [1] 0 1-M 0 1 0 0 0 1 0 0 1 x3 1 2 [1] 1-3M 0 0 1 0 0 0 1 0 0 0 1 0 0 x4 1 0 0 0 1 0 0 0 1 0 0 0 1/3 -1 -2/3 1/3 0 x5 0 -1 0 M 0 -1 0 M -2 -1 0 1 -2/3 -1 -4/3 1/3 M x6 0 1 0 0 0 1 0 0 2 1 0 M-1 M x7 0 0 1 0 -1 -2 1 3M-1 -5 -2 1 M+1 θi 11 3/2 1 1 4

2/3 -5/3 1 -2 4/3 -7/3 M-1/3 M-2/3 2）两阶段法

19

单纯形法书稿

用电子计算机求解含人工变量的线性规划问题时，只能用很大的数代替M,这就可能造成计算上的错误。故介绍两阶段法求线性规划问题。

第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。如

minxn1xnm0x10xnb1a11x1a1nxnxn1axaxxn2b22112nn s.t.axaxxnmbmmnnm11x1,x2,,xnm0然后用单纯形法求解上述模型，若得到0，这说明原问题存在基可行解，可以进行

第二阶段计算。否则原问题不可行解，应停止计算。

第二阶段：将第一阶段计算得到的最终表，除去人工变量。将目标函数换回原问题的目标函数，作为第二阶段的计算方法及步骤与单纯形法的相同。下面举例说明。 例1.8 线性规划

minz3x1x2x3x12x2x3114xx2x3123 s.t.2x312x1x1,x2,x30试用两阶段法求解。

解: 先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：

minwx4x5x12x2x3x44xx2xx5x6123s.t.2x32x1x1,x2,x3,x4,x5,x6,x70113 x71这里x6 、x7 是人工变量。用单纯形法求解，见表1.9。第一阶段求得的结果是w=0。得到

最优解是

x1=0, x2=1, x3=1, x4=12, x5=x6=x7=0

因人工变量x6=x7=0，所以(0,1,1,12,0) 是这线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消填入原问题的目标函数的系数。进行阶段计算。见表1.10。

T

20

单纯形法书稿

表1.9

cj→ CB XB 0 x4 1 x6 1 x7 cj-zj 0 1 0 0 1 1 表1.10 CB 0 1 1 cj-zj 0 1 1 cj-zj x1 x2 x3 cj→ XB x4 x2 x3 b 12 1 1 4 1 9 2 -3 x1 3 0 -2 -1 1 0 0 0 1 x2 0 1 0 0 0 1 0 0 1 x3 0 0 1 0 0 0 1 0 0 x4 1 0 0 0 1/3 0 2/3 1/3 0 x5 -2 -1 0 1 -2/3 -1 -4/3 1/3 θi 4 - - x4 x6 x3 x4 x6 x3 0 b 11 3 1 10 1 1 12 1 1 0 x1 1 -4 -2 6 3 0 -2 0 3 0 -2 0 0 x2 -2 1 0 -1 -2 [1] 0 -1 0 1 0 0 0 x3 1 2 [1] -3 0 0 1 0 0 0 1 0 0 X4 1 0 0 0 1 0 0 0 1 0 0 0 0 x5 0 -1 0 1 0 -1 0 1 -2 -1 0 0 1 x6 0 1 0 0 0 1 0 0 2 1 0 1 1 x7 0 0 1 0 -1 -2 1 3 -5 -2 1 1 θi 11 3/2 1 1 4

从表中得到最优解为x1=4, x2=1, x3=9, 目标函数值z=-2.

3.2 退化

单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。这时换出变量xl0,迭代后目标函数值不变。这时不同基表示为同一顶点。有人构造了一个特例，当出现退化时，进行多次迭代，而基从B1, B2,…又返回到B1,即出现计算过程的循环，便永达不到最优解。

尽管计算过程的循环现象极少出现，但还是有可能的。如何解决这问题？先后有人提出了“摄动法”，“辞典序”。1974年由勃兰特（Bland）提出一种简便的规则，简称勃兰特规则：

(1) 选取cjzj0中下标最小的非基变量xk为换入变量，即

kmin(j|cjzj0)

21

单纯形法书稿

(2) 当按θ规则计算存在两个以上最小比值时，选取下标最小的基变量为换出变量。

按勃兰特规则计算时，一定能避免出现循环。

§4 案例分析与Matlab求解

4.1 案例分析一与Matlab求解

4.1.1 案例分析

用线性规划测算上海市最低生活标准（以2005年以前数据计算）。

建立统一、规范和完善的社会保障体系，是治国安邦的根本大计，也是一项社会主义的基本制度建设。上海市最低生活保障制度从1993年实施以来，已经将近有十几个年头了。在这十几年里，上海的经济文化水平发生了巨大的变化，上海的社会保障体系也在不断地调整和完善。目前，最低生活保障标准已经从1993年的120元增长到了2002年的290元。

● 最低生活保障制度的概念 目前，最低生活保障制度是指世界上绝大多数市场经济国家普遍实行的以保障全体公民基本生存权利为目标的社会救助制度。它的通常做法是，根据维持最起码的生活需求的标准，设立一条最低生活保障线。每一个公民当其收入水平低于最低生活保障线而生活发生困难时，有权利依据国家公布的法定标准和程序获得政府提供的现金和实物救助。

● 上海建立最低生活保障制度的演进

上海于1993年6月1日正式执行上海市城镇最低生活保障制度。 1993-2002年最低保障标准及增长率见表1-9。 表1-9 最低保障标准历年变化表 年份 最低保障标准 增长率%

1993 120 0.00

1994 145 20.83

1995 165 13.79

1996 185 12.12

1997 195 5.41

1998 205 5.13

1999 280 36.59

2000 280 0.00

2001 280 0.00

2002 290 3.57

● 保障对象的范围

城市居民最低生活保障制度的保障对象是家庭人均收入低于当地最低生活保障标准的持有非农业户口的城市居民，主要包括以下三类人员：

1无生活来源、无劳动能力、无法定赡养人或抚养人的居民； ○

2领取失业救济金期间或失业救济期满仍未能重新就业，○家庭人均收入低于最低生活保障标准的居民；

3在职人员和下岗人员在领取工资或最低工资、○基本生活费后以及退休人员领取退休金后，其家庭人均收入仍低于最低生活保障标准的居民。

● 保障标准

城市居民最低生活保障标准由当地人民政府自行确定。本着既保障基本生活、又有利于克服依赖思想的原则，按照当地基本生活必需品费用和财政承受能力，实事求是地确定保障标准。

● 最低生活保障标准的测算指标： 国际上把最低生活保障线也称为贫困线，是指为度量贫困而制定的针对最起码的生存条件或者相对社会中等生活水平的差距所作的定量化的界定。所以，想要测定最低生活保障线就必须对贫困及贫困线有大体的认识。

常用的测定贫困线的方法有：比例法、绝对值法、恩格尔系数法、数学模型法、基本需求法、基期固定法等。

22

单纯形法书稿

● 最低生活保障标准中食品部分消费支出的测定 ① 建立目标函数

目标函数为每日食品总支出最少 Min Z=ΣCiXi

其中，Z表示每人每天食品支出总额。Ci表示第i种食品的市场单价，Xi表示各种食品。

约束条件1：每天的营养一定要达到标准Kj。即每天各种食品的消耗量Xi*各种食品每公斤某种营养元素含量Aij*各种食品的可食部分百分比fi相累加，累加的总和要大于或等于这种营养每日需要量。食品的可食部分百分比是指：食品中除去骨头、外壳、内脏等以后剩余的可以食用的重量占食品总重量的比重。即每天的热能、钙、铁等营养素摄入量必须达到一定的标准。用公式可以表示为：ΣAijXifi>=Kj（Aij：第i种食品中第j种营养素的含量，Kj：第i种营养素每日需要量标准，fi：第i种食品可食部分比例）。

约束条件2：蛋白质、脂肪、碳水化合物占总热量的比重要符合一定的比例。三种营养在体内转化为热能的系数分别为：每克蛋白质4kcal,脂肪9kcal，碳水化合物4kcal。设每种食品蛋白质含量Dia，没种食品脂肪含量Dib，每种食品碳水化合物含量Dic。每日蛋白质总摄入量（ΣDiaXifi）*热能转化系数（4kcal/kg）/每日热能总摄入量（ΣAi1Xifi）即为每日摄入的蛋白质占热能中的比例。脂肪与碳水化合物的计算也与蛋白质一样。用公式表示为：

10%<=(4*ΣDiaXifi)/ ΣAi1Xifi<=15% 20%<=(9*ΣDibXifi)/ ΣAi1Xifi<=25% 60%<=(4*ΣDicXifi)/ ΣAi1Xifi<=70%

约束条件3：每日的饮食习惯。ai<=Xi<=bi(ai, bi:第i种食品每天习惯消费量的上下限)。

② 变量X的含义

表1-10 变量X的含义 变量 实际含义 变量 实际含义

X1 主食 X9 水产品

X2 其他粮食 X10 蔬菜类

X3 油脂类 X11 食糖类

X4 豆制品 X12 水果类

X5 猪肉 X13 坚果及果仁

X6 鸡肉 X14 糕点类

X7 其他肉制品 X15 奶及奶制品

X8 蛋类 X16 在外饮食支出

③ 营养素达到一定标准的含义

表1-11 每100克食物中各个营养素的含量 Xi 主食 其他粮食 油脂类 豆制品 猪肉 鸡肉 其他肉制品 蛋类 水产品 蔬菜类

可食部Fi 热能Ai1 100 100 100 100 100 56 62 85 45 84

348 201.86 900 121.33 580 108.33 154 170 90.9 19.35

钙Ai2 8.5 17.86 0 269.17 6 22 10 55 118 59.02

铁Ai3 2.4 1.66 0 3.18 1.4 4.7 10 2.7 0.54 1.29

VaAi4 0 0 0.03 0.07 0 0 37393 1440 0 0.77

Vb1Ai5 0.21 0.15 0 0.12 0.53 0.02 0.07 0.16 0.02 0.03

23

单纯形法书稿

食糖类 水果类 坚果及果仁 糕点 奶及奶制品 在外饮食 100 63 62 100 100 100 Vb2Ai6 0.06 0.04 0.04 0.07 0.12 0.12 0.91 0.31 0.08 0.06 0.08 0.02 0.11 0.09 0.13 0.07

364 35.76 517.38 416 69 179.96 16 11.76 77.88 46.5 120 39.02 0.95 0.24 3.91 2.9 0.2 20.13 蛋白质Dia 7.3 5.6 0 11.66 9.5 22.47 18.3 14.7 17.13 1.22 0.25 0.91 23.09 6.9 3.3 6.82

0 0.17 0.09 259 140 52.53 脂肪Dib 1.3 0.67 100 4.59 59.8 2.6 8.85 11.6 2.54 0.23 0.1 0.14 40.75 15.6 4 12.13

0.05 0.02 0.34 0.25 0.04 0.1 碳水化合物

Dic 76.7 43.69 0 9.15 0.9 0.47 0.25 1.6 0.02 3.06 90.5 7.66 20.7 64 5 11.14

Xi 主食 其他粮食 油脂类 豆制品 猪肉 鸡肉 其他肉制品 蛋类 水产品 蔬菜类 食糖类 水果类 坚果及果仁 糕点 奶及奶制品 在外饮食

烟酸Ai7 1.6 1.21 0 0.56 4.2 6.53 5.4 0.1 1.85 0.49 1.05 0.25 3.9 1.1 0.2 1.51

VcAi8 0 6.86 0 0 0 0 0 0 0 23.42 0 6.49 4.5 0 1 2.9

④ 变量Ci的含义

表1-12 变量Ci的含义 食品 单价 食品 单价

X1 主食 2.22 X9 水产品 18.34

X2 其他粮食 6.16 X10 蔬菜类 3.01

X3 油脂类 6.55 X11 食糖类 4.19

X4 豆制品类 10.51 X12 水果类 2.98

X5 猪肉 12.77 X13 坚果及果仁 9.80

X6 鸡肉 13.45 X14 糕点类 14.39

X7 其他肉制品 14.33 X15 奶及奶制品 8.20

X8 蛋类 4.57 X16 在外饮食支出 30.87

⑤ 结果

在建立了线性规划的模型之后，可以用Matlab软件编写相应程序来求出其最优解单纯形法。根据计算得到最低生活保障标准中，食品上的消费支出为：253.64元 4.1.2 Matlab求解

自行开发单纯形法的Matlab程序如下： %m1.m文件：输入并化标准型

m=input('请输入约束条件个数: '); n=input('请输入变量个数: ');

24

f=input('请输入目标函数系数矩阵：'); a=input('请输入约束条件系数矩阵：');

b=input('请输入约束条件右端常数矩阵：'); %标准化

f1=[f,zeros(1,m)]; a1=[a,eye(m,m)]; cb=a1(:,n+1:n+m); c= f1(:,n+1:n+m); mm=zeros(1,m+n); jie=[zeros(1,n),b];

disp('初始基可行解为：') jie

dd=1:n+m;

ee=dd(:,n+1:n+m);

%m2.m文件：计算检验数 q=zeros(1,n+m); for i=1:m+n ff=f1(:,i);

ss=sum(c*a1(:,i)) t=ff-ss; q(:,i)=t; end

disp('各检验数为：') disp(q) m3

%m3.m文件判断函数是否有界 for i=1:m+n if q(:,i)>0 t=i;

if max(a1(:,t))<=0

disp('此问题无界');break; else

disp('此问题有界'); end end end m4

%m4.m判断最优解 g=q(:,1); for i=1:m+n qq=q(:,i)

单纯形法书稿

25

if g<=qq g=qq;z=i; end end if g<=0

A='目标函数已得到最优值'; disp(A); mm=mm';

u=sum(f1*mm); disp(u);

disp('最优解为:'); mm=mm' break; else g=g; end

disp('检验数最大值为：') disp(g);

disp('换出变量x为') disp(z); m5

%m5.m文件计算θ检验数 rr=a1(:,z); ct=b'./rr;

disp('θ检验数为'); ct m6

%m6.m确定换出变量 h=100000; for j=1:m ctt=ct(j,:) if ctt>0 if h>ctt

h=ct(j,:);y=j+n; end end end

disp('换出变量为'); y m7

%m7.m 迭代产生新的得到新的单纯形表单纯形法书稿

26

if y>n

cb(:,y-n)=a1(:,z); end if ycb(:,y)=a1(:,z); end b2=cb;

a1=inv(b2)*a1; if y>n

c(:,y-n)=f1(:,z); end if yc(:,y)=f1(:,z); end

b=inv(b2)*b'; b=b';

disp('新的约束矩阵为'); a1

cb=eye(m,m); m8

%m8.m文件形成新常数矩阵和可行解 if ymm(:,k)=b(:,i); end

mm(:,y)=0; else if y>n

yy=y-n; ee(:,yy)=z; for i=1:m k=ee(:,i);

mm(:,k)=b(:,i); end

mm(:,y)=0; end end mm m2

4.2 案例分析二与Matlab求解

4.2.1 案例分析

单纯形法书稿

27

单纯形法书稿

例1.9 对于例1.1, 此问题的模型建立如下：

max Z󰀀4x1+3x2x162x8s.t.22x13x218x1,x204.2.2 Matlab求解

对于此简单问题，用以上开发出来的程序计算如下： 命令：m1 并输入矩阵条件。 >> m1

请输入变量个数: 2 请输入约束条件个数: 3 请输入目标函数系数矩阵：[4,3] 请输入约束条件系数矩阵：[1,0;0,2;2,3] 请输入约束条件右端常数矩阵：[6,8,8] 按回车后计算机自动执行程序，结果如下： 目标函数已得到最优值 16

最优解为:mm = 4 0 2 8 0

(1.1)(1.2)(1.3)(1.4)

4.3 案例分析三与Matlab求解

4.3.1 案例分析

例1.10 飞乐公司经营一个回收中心，专门从事用三种废弃原材料C、P、H混合调出三种不同规格的产品ABD。根据混合时候各种材料的比例，可将该产品分为不同的等级（参照表1.12）。尽管在混合各种等级产品时允许一定的机动性，但每一等级产品中各种材料的最大值和最小值必须符合下面质量标准的规定（最大值和最小值是根据该材料的重量在该等级产品总重量中的比例来确定的）。在两种较高等级的产品中，有一种特定材料的比例是固定的。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表1.12和表1.13，问该厂应如何安排生产，使利润收入为最大？ 表1.12

产品名称 Ａ B D

规格要求 原材料C不少于５０％ 原材料Ｐ不多于２５％ 原材料C不少于２５％ 原材料P不多于５０％

不限

单价（元／kg）

50 35 25

回收中心可以从一些渠道定期收集到所需的固体废弃物，因此，可以获得维持稳定作业的处理量。表1.13给出了中心每天可以收集到每种材料的数量和原材料单价。

28

单纯形法书稿

表1.13

原材料名称

C P H

每天最多供应量（kg）

100 100 60

单价（元／kg）

65 25 35

飞乐公司是绿地组织的全资公司，绿地组织是一个专门从事与环境有关业务的组织。管理层决定在表1.12和表1.13所列的约束之内，有效地将各种材料分配到各等级的产品中去，以实现每周的总利润最大。

以线性规划的形式建模

这是一个混合线性规划问题，为了给该问题建模，首先需要明确该问题所涉及的活动(activities)、资源(resources)、收益(benefits)以及确定的需求(fixed requirements)。这一步的关键在于管理层的目标是将每种材料最优地分配给每一等级的产品。每一种材料与产品的组合都是一个决策：多少材料用于这一等级的产品？这个数量就是活动的水平(level of an activity)。

每一种活动对应的是将一种固体废弃物处理混合入每一个等级的产品中去 活动的水平是混合入每一等级产品中的一种材料的数量

因此，要决策的是每周将多少元的每一种材料加入每一等级的产品中去。

因为资源有限，收益受到限制，以及确定的需求，该问题就有了相当多的约束，归纳如下：

有限的资源：四种固体废弃物所能获得的数量如表1.13的第二栏所示，此外，表1.12的第二栏还表明材料A和B的用量是有限的，这些有限的资源都将形成资源的约束条件。

规定的收益：收益是指所收集和处理的每一种材料。 确定需求的约束：

1． 表 1.12第二栏所示的材料A的原材料C不少于５０％原材料Ｐ不多于２５％， 2． 表 1.12第二栏所示的材料B的原材料C不少于２５％原材料P不多于５０％ 管理层的目标是使的三种等级的产品所能实现的每天总利润最大，因此，这就是该问题的总绩效测度（overall measure of performance）。 4.3.2 Matlab求解

如以Ac, Ap分别表示Ａ中C的成分，A中Ｐ的成分，依次类推。 根据表1.12有：

AC ≥ 0.5A, AP ≤ 0.25A, BC≥ 0.25B, BP ≤ 0.5B (4.1) 又有 ：AC + AP +AH=A， BC + BP + BH =B (4.2) 将(4.1)逐个代入(4.2)中并整理得： -0.5AC + 0.5 AP + 0.5 AH ≤0 -0.5AC + 0.75 AP - 0.5 AH ≤0 -0.75BC + 0.25 BP + 0.25 BH ≤0 -0.5BC + 0.5 BP - 0.5 BH ≤0

表1.13表明这些原材料供应量的限额。加入到产品A 、B、D的原材料C总量每天不

29

单纯形法书稿

超过100kg，P的总量不超过100kg,H总量不超过60kg,由此 ：

AC + BC + DC≤100 AP + BP + DP≤100 AH + BH + DH≤60

在约束条件中共有9个变量，为计算和叙述的方便，分别用x1,,x9表示令：

x1AC,x2AP,x3AHx4BC,x5BP,x6BHx7DC,x8DP,x9DH

由此约束条件可表示为：

0.5x10.5x20.5x300.25x0.75x0.25x01230.75x40.25x50.25x600.5x40.5x50.5x60 x1x4x7100x2x5x8100x3x6x960x,,x019我们的目的是使利润最大化，即产品价格减去原材料的价格为最大。

50(x1x2x3)产品A产品价格为：35(x4x5x6)产品B

25(x7x8x9)产品D65(x1x4x7)原材料C原材料价格：25(x2x5x8)原材料P

35(x3x6x9)原材料Hmaxz50(x1x2x3)35(x4x5x6)25(x7x8x9)65(x1x4x7)25(x2x5x8)35(x3x6x9)整理后目标函数为：max z=-15x1+25x2+15x3-30x4+10x5-40x7-10x9

面对如此多变量和约束条件的线性规划问题，如果用手算，那是件很麻烦的事，不仅需要很多时间和耐心，而且容易出错。现在利用计算机程序来计算显得小菜一碟。

首先需要输入矩阵： m1

30

单纯形法书稿

请输入约束条件个数: 7 请输入变量个数: 9

请输入目标函数系数矩阵：[-15,25,15,-30,10,0,-40,0,10] 请输入约束条件系数矩阵：

[-1/2,1/2,1/2,0,0,0,0,0,0;-1/4,3/4,-1/4,0,0,0,0,0,0;0,0,0,-3/4,1/4,1/4,0,0,0;0,0,0,-1/2,1/2,-1/2,0,0,0;1,0,0,0,4,0,0,1,0;0,1,0,0,1,0,0,1,0;0,0,1,0,0,1,0,0,1]

请输入约束条件右端常数矩阵：[0,0,0,0,100,100,60]

按下回车，计算机以迅雷不及掩耳之势就显示了结果。结果如下 ： 目标函数已得到最优值 3400 最优解为:

mm =[0 100 60 0 0 0 0 0 0 -80 -60 0 0 100 0 0]

可以得到，当x2=100, x3=60是，最优解是3400。

4.3 案例分析四与Matlab求解

4.4.1 案例分析

例1.11 上海地铁公司正准备增加其人民广场的往来班次，因此需要雇用更多的工作人员，但是不知道到底雇用多少数量的工作人员。管理层意识到中介公司的客户提供令人满意的服务水平的同时必须进行成本控制，因此，必须寻找成本与收益之间合意的平衡。于是，要求管理团队研究如何规划人员才能以最小的成本提供令人满意的服务。

分析研究新的班次时间表，以确定一天之中不同时段为实现客户满意水平必须工作的工作人员数目。在表1.14的最后一栏显示了这些数目，其中第一列给出对应的时段。表中的其他数据反应了公司与客户服务代理商协会所定协议上的一些规定，这一规定要求每一工作人员工作8小时为一班，各班的时间安排如下： 轮班 1： 6:00 AM~2:00 PM 轮班 2： 8:00 AM~4:00 PM 轮班 3： 中午~8:00 PM 轮班 4： 4:00 PM~午夜

轮班 5： 10:00 PM~6:00 AM

表1.14 上海地铁公司人员排程问题的数据

31

单纯形法书稿

轮班的时段 时段 x1 x2 x3 x4 x5 最少需要代理商 的数量 48 79 65 87 64 73 82 43 52 15 6:00 AM~8:00 AM 8:00 AM~10:00 AM 10:00 AM~中午 中午~2:00 PM 2:00 PM~4:00 PM 4:00 PM~6:00 PM 6:00 PM~8:00 PM 8:00 PM~10:00 PM 10:00 PM~午夜 午夜~6:00 PM 每个代理商的每日成本

x11 x 21 x 31 x 41 x 22 x 32 x 42 x 52 x 43 x 53 x 63 x 73 x 64 x 74 x 84 x 94 180 x 95 x 10 5 195 170 160 175 表1.14中标注xij的部分表示这段时间是有相应轮班的。因为轮班之间的重要程度有差异，所以协议中工资也因轮班所处的时间而不同。每一轮班对代理商的补偿（包括收益）如最底行所示。问题就是，在最底行数据的基础上，确定将多少代理商分派到一天之中的各个轮班中去，以使得人员费用最小，同时必须保证最后一栏中所要求的服务水平的实现。 建模

这个问题实际上是一个纯成本收益平衡问题。为了建立模型，首先必须明确包含的活动和收益。

活动对应于各轮班

活动的水平就是分派到那一轮班的代理商数目 活动的一个单位是指分派到该轮班的一个代理商

因此，线性规划通常是寻找最优活动水平组合的问题，在这里，就可描述为确定最佳的轮班人数。

收益对应于时段

在每一时段里，活动的收益就是代理商所提供给客户的服务 收益的水平由那段时间在岗位的代理商的数目来衡量的 4.4.2 Matlab求解

问题的目标是：

最小化 成本=所有代理商每日总人力成本 成本=170 x1+160 x2+175 x3+180 x4+195 x5

约束： 6:00 AM~8:00 AM之间总的代理商数= x1 48

8:00 AM~10:00 AM之间总的代理商数= x1+ x2 79 10:00 AM~中午之间总的代理商数= x1+ x265 中午~8:00 AM之间总的代理商数= x1+ x2+ x387 2:00 PM~4:00 PM之间总的代理商数= x2+ x364 4:00 PM~6:00 PM之间总的代理商数= x3+ x473

32

单纯形法书稿

6:00 PM~8:00 PM之间总的代理商数= x3+ x482 8:00 PM~10:00 PM之间总的代理商数= x443 10:00 PM~午夜之间总的代理商数= x4+ x552 午夜~6:00 PM之间总的代理商数= x515

对如此多变量和约束条件的线性规划问题，如果用手算，那是件很麻烦得事，不仅需要很多时间和耐心，而且容易出错。现在利用计算机程序来计算。

首先需要输入矩阵： m1 请输入约束条件个数: 10 请输入变量个数: 5

请输入目标函数系数矩阵：[170，160，175，180，195] 请输入约束条件系数矩阵：

[1,0,0,0,0;1,1,0,0,0;1,1,0,0,0;1,1,1,0,0;0,1,1,0,0;0,0,1,1,0;0,0,1,1,0;0,0,0,1,0;0,0,0,1,1;0,0,0,0,1]

请输入约束条件右端常数矩阵：[48，79，65，87，64，73，82，43，52，15] 按下回车，计算机显示了结果。结果如下 ： 目标函数已得到最优值 30610

可以得到，当x1=48, x2 =31，x3=39, x4=43, x5=15时，最优解是30610。

本章小结

1) 对给定的线性规划问题应首先化为标准形式，选取或构造一个单位矩阵作为基，求出初始基可行解并列出初始单纯形表。对各种类型的线性规划问题如何化为标准形式可参见下表表1.18中xsi为松弛变量（或剩余变量），xai为人工变量。见表1.18

表1.18 变 量 xj0xj0xj无约束 不需要处理 令xjxj;xj0令xjxjxj;xj,xj0 33

单纯形法书稿

约 束 条 件 b0b0b0 b0b0 不需要处理 约束条件两端同乘－１ 加松弛变量xsi 加人工变量xai 减去剩余（松弛）变量xsi,加人工变量xai 目 标 函 数 max z min z 加入变量的系数 松弛变量xsi 人工变量xaii 不需要处理 令zz,求maxz ０ －M

2) 对目标函数max的线性规划问题，用单纯形法计算步骤的框图如下：

34

单纯形法书稿

名词辞条

线性规划

Linear programming 英文缩写LP

线性规划是指研究线性约束条件下线性目标函数的极值问题的数学理论与方法。即对于统筹规划问题，为如何合理地、有效地利用现有有限的人力、物力、财力资源来完成更多的任务。或者如何才能以最少的代价去实现目标。作出的最优决策，提供科学的依据。 目标函数 Objective

运用单纯形法解某些线性规划问题时，在一定约束条件下要达到的目标，用数学模型表示，就称为目标函数。 约束条件 Constraints

运用单纯形法解某些线性规划问题时，该问题已知并须遵守的前提条件称为约束条件。 可行解

Alternative optimal solutions

一个线性规划问题有解，就能找出一组xj（j =1.，，，n），满足约束条件，称这组xj为问题的可行解。通常线性规划问题总是含有多个可行解。 可行域 Feasible region

全部可行解的集合叫可行域。 数学模型

Mathematical models

数学模型是研究和掌握系统运动规律的有力工具，它是分析、设计、预报或预测、控制实际系统的基础。数学模型的种类很多，而且有各种不同的分类方法。要对实际规划问题做定量分析，必须先加以抽象，建立数学模型。它是用字母、数字和其他数学符号构成的等式或不等式，或用图表、图象、框图、数理逻辑等来描述系统的特征及其内部内部或与外部联系的模型。它是正式系统的一种抽象。 单纯形法 Simplex method

是求解线性规划问题的一种常用基本方法。单纯形法的思路是：根据问题的标准型，从可行域中一个基本可行解（一个顶点）开始，转换到另一个基本可行解（一个顶点），并且使目标函数值增大，当目标函数值达到最大时问题就得到了最优解。单纯形法的特点是：（1）二元情况下满足约束条件的集合是凸边型，在多元情况下，满足约束条件的集合是凸多边型。（2）目标函数的最大值或最小值恰好在多边型的顶点，在多元情况下，目标函数值一定在凸集的极点上。（3）各极点的值代入目标函数中，进行比较就可以求得极值，即所求得的解。

习 题

1.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界

解还是无可行解？

35

单纯形法书稿

minzx11.5x25x10x5012x13x23xx1（1） （2） 12s.t.x1x22s.t.x4x,x0212x1,x20maxz2x12x2（3）

maxzx13x2maxzx1x2x1x21x1x20 (4) s.t.0.5x1x22s.t.3x1x23x,x0x,x01212

1.2 将下列线性规划问题化为标准形式

(1)minZ4x1x22x3(2)minZ2x13x24x3x44x1x22x38x1x23x32x462xx3x42x3xx2x4 1231234s.t.s.t.3xxx6123x12x2x3x49x10,x2无约束，x30x10,x20,x3,x4无符号约束

1.3 用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步得到的基

可行解对应与图解法可行域中的哪个点。

2x1x243x2x12122x5(1) (2) 2s.t.5x1x210s.t.x,x0x13x2612x1,x20

1.4 对下列线性规划问题，找出所有基本解，判断哪些是基可行解，并用图解法说明 。

maxz2x1x2maxz3x12x2x12x25x1x26xx4

(1) (2)s.t.2x1x210s.t.12x,x05x13x21512x1,x20

1.5 考虑以下线性规划

maxz3x12x2maxz3x12x236

单纯形法书稿

maxz3x12x2x1x232xx18 12s.t.x26x1,x20(1) 用图解法求解此问题。

(2) 说明图中每个顶点对应的边界方程、基本解、基本变量。

1.6 考虑以下线性规划问题

maxz69x1x3x52x65x210x3x42x515s.t.x110x22x34 x23x33x5x66xi0i1,2,3,4,5,6(1)找出一个初始基可行解及相应的基变量与非基变量。 (2)将线性规划转化为标准形式，并列出单纯形表。 (3)以上初始基可行解是否为最优解，为什么？

1.7 用单纯形法求解如下问题

maxz3x12x2maxzx16x24x3x12x24x12x22x310（1）s.t.3x12x216 (2)s..t4x4xx20x123 1x23x12x2x317x1,x20i1,2,3xi0i1,2,3maxz2x13x25x3minz2x13x2x32x1x23x310(3)x14x4x52x65s..tx12x2x36 (4)x22x43x5x642x12xs..t28x32x45x56x66xi0i1,2,3xi0i1,2,3,4,5,6minz6x1x210x3x45x1x24x33x420(5)s.t.3x12x22x3x425

4x1x2x33x410xi0i1,2,3,4

1.8 已知线性规划问题

37

单纯形法书稿

maxz2x23x32x52x57x13x2x3x4xx12 234s.t.8x5x6104x23x3xi0i1,2,3,4,5,6某一基B(P2,P3,P6)对应的单纯形表为1.15。 表1.15 CB XB X2 X3 X6 -Z B x1 x2 x3 x4 x5 x6 2/5 1 0 1/10 0 1/5 0 1 3/10 0 1 0 0 -1/2 1

-1

(1) 对于上表对应的基B，求B

(2) 将表上空白处填上数字，完成以上单纯形表。 (3) 判定表中给出的解是否为最优解。

1.9 求最大目标函数值的线性规划问题的单纯形表为表1.16 表1.16 CB XB b x1 x4 x5 -Z b1 4 5 -30 x1 x2 x3 x4 x5 x6 1 -1 4 0 0 0 0 -2 3 1 0 -1 0 -3 -1 0 1 3 0 δ2 δ3 0 0 δ6

问表1.16中b1、δ2、δ3、δ6为何值时有： （1） 表中的解为唯一最优解。 （2） 表中的解为无穷多最优解。 （3） 表中的解为退化的可行解。 （4） 线性规划问题无有限最优解。

1.10 某昼夜服务的公交线路每天时间区段内所需司机和乘务人员数如下表： 表1.17

班次 1 2 3 4 5 6 时间 6:00～10:00 10:00～14:00 14:00～18:00 18:00～22:00 22:00～2:00 2:00～6:00 所需人数 60 70 60 50 20 30 设司机和乘务人员分别在各时间区段开始上班，并连续工作八小时，问该公交线路至少配备多少名司机和乘务人员。列出这个问题的线性规划模型并求解。

38