第1章
线性规划与单纯形法
学习目标
√了解线性规划模型特征并能根据实际问题写出线性规划模型
√掌握线性规划化标准型的方法
√掌握线性规划的解的概念，并能够用图解法求解线性规划问题
√熟练掌握线性规划的单纯形法
√利用Matlab求解线性规划问题的最优解
引言
线性规划是应用数学模型对所研究的问题进行表述。线性（linear）这个词是指模型
中数学表达式的形式。规划（programming）本质上是计划的同义词。因此，线性规划是
用线性数学模型表示不同的生产活动、营销活动、金融活动或其他活动的计划。
单纯形方法是美国数学家丹捷格（G.B.Dantzig）于1947年提出的一般线性规划求
解方法，此后线性规划在计算上趋向成熟，其应用也日趋广泛和深入。
1.1线性规划数学模型
1.1.1问题的提出
线性规划应用的问题种类繁多，形式各异，主要分为四类线性规划问题。前三类问题
分别是资源分配问题、成本效益问题以及网络配送问题。例1.1、例1.2、例1.3讨论了这
三类问题。这些线性规划问题其共同特征是决策所基于的约束条件性质，三类线性规划
问题约束分别是资源约束、收益约束、确定需求约束。更多的实际问题包含至少有两种以
上的约束。这类问题不能绝对归属于这三类中的一类，于是把这第四类线性规划的问题
称为混合问题。
例1.1资源分配问题。
某工厂近期要安排生产甲、乙两种产品，产品甲需要用原料A，产品乙需要用原料B，
由于两种产品都在一个设备上生产，且设备使用时间有限，管理者必须合理安排两种产
品的产量，使得在资源有限的条件下获得最大的利润。因此，这个问题的决策目标是收益
的最大化，研究者根据这个目标需要收集以下相关数据：
（1）工厂两种原料存量以及可用设备工时数。
（2）甲、乙两种产品的单位产品需要的原料和设备工时数。
（3）甲、乙两种产品的单位产品利润。
这些数据可以通过调研或估算得出，如表1.1所示。
为建立模型，引入变量如下：
x1＝产品甲的数量
x2＝产品乙的数量
Z＝利润
由表1.1最后一行知
Z＝4x1+3x2
目标是如何确定x1和x2，使得利润Z最大，同时需要满足资源约束。
对于原料A和原料B，有
x1≤6，2x2≤8
对于设备工时，有
2x1+3x2≤18
此外，甲、乙两种产品数量不可能是负值，因此，有如下对变量的非负约束：
x1≥0，x2≥0
于是，问题的数学模型现在可以用代数式表述如下：
maxZ＝4x1+3x2
满足：
x1≤6（1.1）
2x2≤8（1.2）
2x1+3x2≤18（1.3）
x1，x2≥0（1.4）
实际上这是求一个线性函数在一组线性约束条件下的最大值问题，称之为线性规划
问题模型。在以上模型中，将x1、x2称为决策变量，Z＝4x1+3x2为目标函数，式（1.1）～
式（1.3）为函数约束，式（1.4）为非负约束。
从以上过程我们可以归纳出根据实际问题建立线性规划模型的步骤：
（1）根据管理层的要求确定决策目标和收集相关数据。
（2）确定要做出的决策，引入决策变量。
（3）确定对这些决策的约束条件和目标函数。
例1.2成本效益平衡问题。
某饲料公司希望用玉米、红薯作原料配制一种混合饲料，各种原料包含的营养成分和
采购成本都不同，公司管理层希望能够确定混合饲料中的各种原料数量，使得饲料能够以
最低成本达到一定的营养要求。研究者根据这一目标收集到的有关数据如表1.2所示。
为建立线性规划模型，我们引入变量如下：
x1＝混合饲料中的玉米数量；
x2＝混合饲料中红薯的数量。
目标函数Z＝0.8x1+0.5x2，表示产量的成本函数，即如何确定x1、x2使得成本Z＝
0.8x1+0.5x2最低且满足最低营养要求的约束，这些约束条件是
碳水化合物要求：8x1+4x2≥20。
蛋白质物要求：3x1+6x2≥18。
维生素物要求：x1+5x2≥16。
另外非负约束：x1≥0，x2≥0。
因此这个问题的线性规划模型为
minZ＝0.8x1+0.5x2
s．t．
8x1+4x2≥20
3x1+6x2≥18
x1+5x2≥16
xi≥0，i＝1，2
其中，“s．t．”是“subjectto”的缩写，意思是“受约束于……”。
例1.3物流网络配送问题。
某物流公司需要将甲、乙、丙三个工厂生产的一种新产品送到A、B两个仓库，甲、乙
两个工厂的产品可以通过铁路运送到仓库A，数量不限；丙工厂的产品可以通过铁路运送
到仓库B，同样，产品数量不限。由于铁路运输成本较高，公司也可以考虑由独立的卡车
来运输，可将多达80单位的产品由甲、乙、丙三个工厂运到一个配送中心，再从配送中心
以最多90单位的载货量运到各个仓库。公司管理层希望以最小的成本运送所需的货物。
为了建立该问题的数学模型，必须先了解这一网络配送问题的活动和要求。该问题
涉及三个产品的生产和各线路的运输量，由于产量给定，所以决策重点是运输水平，即各
线路的运输量。
首先，需要收集每条线路上的单位运输成本和各工厂产品的产量以及各仓库分配量
等数据，如表1.3所示。
为了更清楚地说明问题，我们用网络图来直观表示该配送问题（图1.1），其中，v1、
v2、v3分别表示甲、乙、丙三个工厂，节点v4表示配送中心，节点v5、v6表示两个仓库；每
一条箭线表示一条可能的运输线路，并给出了相应的单位运输成本，对运输量有限制的路
线的最大运输能力也同时给出。
我们要解决的是各条线路最大运输量，引入变量xij表示由vi经过路线（vi，vj）运输
到vj的产品数。问题的目标是总运输成本最小化，总运输成本可以表示为
总运输成本＝7.5x15+3x14+8.2x25+3.5x24+2.3x45+3.4x34
+2.3x46+9.2x36
相应的约束条件包括对网络中的每个节点vi（i＝1，2，…，6）的供求平衡约束。对生
产节点v1、v2、v3来说，由某一节点运出的产品数量等于其产量，即
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（非负约束）。因此，这个问题的线性规划模型为
minZ＝7.5x15+3x14+8.2x25+3.5x24+2.3x45+3.4x34+2.3x46+9.2x36
s．t．
x15+x14＝100
x25+x24＝80
x34+x36＝70
x14+x24+x34＝x45+x46
x15+x25+x45＝120
x46+x36＝130
x14≤80，x24≤80，x34≤80，x45≤90，x46≤90
xij≥0
从以上的几个例子可以看出，线性规划问题有如下共同特征：
（1）每个问题都用一组决策变量，这组决策变量的值都代表一个具体方案。
（2）有一个衡量决策方案优劣的函数，它是决策变量的线性函数，称为目标函数。按
问题不同，要求目标函数实现最大化或最小化。
（3）存在一些约束条件，这些约束条件包括：①函数约束；②决策变量的约束。
1.1.2线性规划的标准型
根据1.1.1节分析，线性规划的一般形式为
max（min）Z＝c1x1+c2x2+…+cnxn
s.t.
a11x1+a12x2+…+a1nxn≤＝，≥b1
a21x1+a22x2+…+a2nxn≤＝，≥b2
·
am1x1+am2x2+…+amnxn≤＝，≥bm
x1，x2，…，xn≥0
线性规划问题有各种不同的形式。目标函数有的要求max，有的要求min；约束条件
可以是“≤”，也可以是“≥”形式的不等式，也可以是等式。决策变量一般是非负约束，
但也允许在（-∞，∞）范围内取值，即无约束。将这种多形式的数学模型统一变换为标准
形式。这里规定的标准形式为：目标函数的要求是max，约束条件的要求是等式，决策变
量的要求是非负约束。在标准型式中规定各约束条件的右端项bi≥0，否则等式两端乘以
“-1”。用向量和矩阵符号表述为
maxZ＝CX
s．t.Σ
n
j＝1
Pjxj＝b
xj≥0，j＝1，2，…，n
其中，C＝（c1，c2，…，cn）；
X＝
x1
x2
·
xn
；Pj＝
a1j
a2j
·
amj
；b＝
b1
b2
·
bm
向量Pj对应的决策变量是xj。
用矩阵描述时为
maxZ＝CX
AX＝b
X≥0
其中，A＝
a11a12…a1n
···
am1am2…amn
＝P1，P2，…，Pn；
0＝
0
0
·
0
；
A为约束条件的m×n维系数矩阵，其中，m，n＞0，m＜n；
b为资源向量；
C为价值向量；
X为决策变量向量。
下面讨论化标准型的方法：
（1）若要求目标函数实现最小化，即minZ＝CX。这时只需将目标函数最小化变换
求目标函数最大化，即令Z′＝-Z，于是得到maxZ′＝-CX。这就同标准型的目标函数
的形式一致了。
（2）约束方程为不等式。这里有两种情况：一种是约束方程为“≤”不等式，则可在
“≤”不等式的左端加入非负松弛变量xj，把原“≤”不等式变为等式；另一种是约束方程
为“≥”不等式，则可在“≥”不等式的左端减去一个非负剩余变量xk（也可称松弛变量），
把不等式约束条件变为等式约束条件。
（3）若变量约束中：xi≤0，则令x′i＝-xi得到x′i≥0；若xj酬0，则令xj＝x′j-x″j，得
x′j，x″j≥0，用x′i、x′j、x″j分别代替xi、xj后得到线性规划的变量约束均为非负约束。
（4）目标函数中加上0xi（松弛变量）。
下面举例说明。