第一节 线性规划及其单纯形求解方法

一、线性规划数学模型

（一)线性规划之实例

线性规划研究的问题主要有两类：一是某项任务确定后，如何统筹安排， 以最少的人力、物力和财力去完成该项任务；二是面对一定数量的人力、物力和财力资源，如何安排使用，使得完成的任务最多。实际上，这是一个问题的两个方面，它们都属于最优规划的范畴。以下，我们列举线性规划问题之若干实例，供读者研究。

1. 运输问题 假设某种物资（譬如煤炭、钢铁、石油等)有 m 个产地，n 个销地。第 i 产地的产量为 ai（i=1，2，⋯⋯，m)，第 j 销地的需求

m n

量为b j （j = 1，2， ，n），它们满足产销平衡条件∑a i = ∑b j 。如果产地

i=1 j=1

I 到销地 j 的单位物资的运费为 cij 试问如何安排该种物资调运计划，才能使总运费达到最小？

设 xij 表示由产地 i 供给销地 j 的物资数量，则上述问题可以表述为

求一组实值变量 xij（i=1，2，⋯，m；j=1，2，⋯，n)，使其满足：

 m

∑xij = b j

 i=1

( j = 1,

2, , n)

 n

∑xij = a i (i = 1, 2, , m)

 j=1

而且使：

xij≥0 (i = 1, 2, , m; j = 1,



2, , n)

m n

z = ∑∑cij xij → min

i=1 j= 1

1. 资源利用问题 假设某地区拥有 m 种资源，其中，第 i 种资源在规划期内的限额为 bi（i=1，2，⋯，m)。这 m 种资源可用来生产 n 种产品，其中， 生产单位数量的第 j 种产品需要消耗的第 i 种资源的数量为 aij（i=1，2，⋯，

m；j=1，2，⋯，n)，第 j 种产品的单价为 cj（j=1，2，⋯，n)。试问如何安排这几种产品的生产计划，才能使规划期内资源利用的总产值达到最大？设第 j 种产品的生产数量为 xj（j=1，2，⋯，n)，则上述资源利用问题

就是：

在约束条件

 n

∑aij x j ≤bi (i = 1, 2, , m)

 j= 1

x ≥ 0 ( j = 1, 2, , n)

 j

下，求一组实数变量 xj（j=1，2，⋯，n)，使

Z = ∑cj x j → max

j= 1

1. 合理下料问题 用某种原材料切割零件 A1，A2，⋯，Am 的毛坯，现已设计出在一块原材料上有 B1，B2，⋯，Bn 种不同的下料方式，如用 Bj 下料方式可得 Ai 种零件 aij 个，设 Ai 种零件的需要量为 bi 个。试问应该怎样组织下料活动，才能使得既满足需要，又使用去的原材料最少？

设采用 Bj 方式下料的原材料数为 xj，则上述问题可表示为：

在约束条件

 n

∑aij x j ≥bi (i = 1,

 j= 1

2, , m)

x ≥ 0

( j = 1, 2, , n)

 j

下，求一组整数变量 xj（j=1，2，⋯，n)，使得

Z = ∑x j→ min

j=1

（二)线性规划数学模型

线性规划应用之实例还有很多，譬如生产布局问题，连续投资问题，等等，不一一列举。从以上的例子可以看出，尽管它们表示的形式不尽相同， 但它们都具有以下共同的特征：（1)每一个问题都用一组未知变量（x1 ， x2，⋯，xn)表示某一规划方案，这组未知变量的一组定值代表一个具体的方案，而且通常要求这些未知变量的取值是非负的。

（2)每一个问题都有两个主要组成部分：一是目标函数，按照研究问题的不同，常常要求目标函数取最大或最小值；二是约束条件，它定义了一种求解范围，使问题的解必须在这一范围之内。

（3)每一个问题的目标函数和约束条件都是线性的。

根据上述问题的三个基本特征，我们可以抽象出线性规划问题的数学模型。它一般地可表示为：

在线性约束条件

n

∑aij x j ≤( ≥, j=1

以及非负约束条件

=)bi

(i = 1,

2, ,

m) (1)

x j ≥0( j = 1,

2, ,

n) (2)

下，求一组未知变量 xj（j=1，2，⋯，n)的值，使

Z = ∑cj x j → min(max) (3)

j=1

若采用矩阵记号，上述线性规划模型的一般形式可进一步描述为：在约束条件

AX≤（≥，=)b (1′)

以及 x≥0 (2′)

下，求未知向量 x=[x1，x2，⋯，xn]^T，使得Z=CX→min(max) (3′)

其中

b=[b1，b2，⋯，bm]^T c=[c1，c2，⋯，cn]

 a11

a12

a 1n 

 a a a 

A = 



21 22 2 n 

Μ Μ Μ



二、线性规划的标准形式

am1

am2

a mn 

（一)线性规划的标准形式

为了讨论与计算上的方便，常常需要将线性规划问题的数学模型转化为标准形式，即在约束条件：

a11 x1 + a12 x2 + + a1n x n = b1

a x + a x + + a x = b

 21 1 22 2 2n n 2





(4)

a m1 x1 + am2 x2 + + a mn x n = bm

以及

xj≥0（j=1，2，⋯，n) (5)

下，求一组未知变量 xj（j=1，2，⋯，n)的值，使

N

达到最小值。

Z = ∑cj x j j=1

(6)

其缩写形式为：在约束条件

∑aij x j = bi (i = 1, 2, , m) (4′)

j=1

以及

xj≥0（j=1，2，⋯，n) (5′)

下，求一组未知变量 xj（j=1，2，⋯，n)的值，使得：

Z = ∑cj x j→ min (6′)

j=1

采用距阵记号，上述标准形式还可以进一步简记为：在约束条件AX=b （4″)

以及X≥0（5″)

下，求未知向量 X，使得：

Z=CX→min （6″)

在通常情况下，b 和 c 为已知常数向量；A 为已知常数矩阵，且 A 的秩为

m。

上述标准形式的线性规划，常被记为如下更为紧凑的形式：

 n

minz = ∑c jx j

 j=1

 n

∑aij x j = b i (i = 1,

 j= 1

x ≥0( j = 1, 2, ,

2, , m)

n)

 j



或

minZ = CX

AX = b

X≥0

（二)化为标准形式的方法

具体的线性规划问题，其数学模型常常是各式各样的，它们不一定符合线性规划的标准形式的要求，为了将其转化为标准形式，常常需要对目标函数或约束条件采用一定的变换方法进行转换。

1. 目标函数化为标准形式的方法 如果其线性规划问题的目标函数为： maxZ=CX

则令 Z′=-Z，显然：

-maxZ=min（-Z)=minZ′ 所以，可将原问题的目标函数换为：

minZ′=-CX 这就是标准形式的目标函数了。

1. 约束方程化为标准形式的方法 如果第 k 个约束方程为不等式，即

a k1x1 + a k2 x 2 + + a kn x n ≤（≥）b k

则只需在原问题中引入松弛变量 xn+k≥0，并将第 k 个方程改写为： ak1x1+ak2x2+⋯+aknxn+（-)xn+k=bk

而将其目标函数看作

n n

z = ∑c jx j = ∑x jc j + o·xn +k

j=1 j=1

这样就将原问题转化为标准形式的线性规划模型了。三、线性规划的解及其性质

（一)线性规划的解

1. 可行解与最优解 在线性规划问题中，称满足约束条件（即满足线性约

束和非负约束)的一组变量值 x=[x1，x2，⋯，xn]T 为可行解。所有可行解组成的集合称为可行域。使目标函数最大或最小化的可行解称为最优解。

1. 基本解与基本可行解 在线性规划问题（4″)—（6″)式中，如果我们

把约束方程组的 m×n 阶系数矩阵 A 写成由 n 个列向量组成的分块矩阵A=[p1，p2，⋯，pn] （7)

在（7)式中，pj=[a1j，a2j，⋯，amj]^T（j=1，2，⋯，n)。则 pj 是对应变量 xj 的系数列向量。

如果 B 是 A 中的一个 m×m 阶的非奇异子阵，则称 B 为该线性规划问题的一个基。不失一般性，不妨设：

a11

a21

a 12

a 22

a1m 

a 2 m 

B = Μ Μ Μ

a a a

 = [p1 , p 2





, pm ] (8)

m1 m2 mm

则称 pj（j=1，2，⋯，m)为基向量，与基向量 pj 相对应的变量 xj（j=1，2，⋯， m)为基变量，而其余的变量 xi（j=m+1，m+2，⋯，n)为非基变量。

如果 XB=[x1，x2，⋯，xm]^T 是方程组

BXB=b （9)

的解，则 X=[x1，x2，⋯，xm，0，0，⋯，0]^T 为方程组（4″)式的一个解， 它称之为对应于基 B 的基本解。

满足非负约束条件的基本解，称为基本可行解。对应于基本可行解的基

称为可行基。

线性规划问题的以上几个解的关系，可用图 3-1 来描述。

（二)线性规划解的性质

1. 凸集和顶点 为了说明线性规划解的性质，需要引入凸集和顶点的概念。

若连结 n 维点集 S 中的任意两点 x⁽¹⁾和 x⁽²⁾之间的线段仍在 S 中，则称 S 为凸集。例如，三角形、平行四边形、正多边形、圆、球体、正多面体等都是凸集。而圆环、空心球等都不是凸集。

若凸集 S 中的点 X^（0)不能成为 S 中任何线段的内点，则称 X^（0)为 S 的顶点或极点。例如，三角形、平行四边形、正多边形、正多面体的顶点以及圆周上的点等都是极点。

1. 线性规划解的性质 可以证明，线性规划问题的解具有以下性质：

（1)线性规划问题的可行解集（可行域)为凸集。

（2)可行解集 S 中的点 X 是顶点的充要条件为 X 是基本可行解。

（3)若可行解集有界，则线性规划问题的最优值一定可以在其顶点上达到。由于系数矩阵 A 中的基是有限的，因此基本可行解也是有限的，这就是说可行解集的顶点数目是有限的。所以，如果线性规划问题有最优解，就只需从其可行解集的有限个顶点中去寻找。

四、线性规划问题的求解方法——单纯形法

（一)单纯形表

在标准形式线性规划（4″)-（6″)句式中，不妨设 B=[p1，p2，⋯，pm] 是一个基，令 N=[pm+1，pm+2，⋯，pn]，则 A=[B，N]。记基变量为 xB=[x1，x2，⋯， xm]^T，非基变量为 xN=[xm+1，xm+2，⋯，xn]^T，则运用分块矩阵的运算法则可知，（4″)式可以被进一步改写为

BXB+NXN=b （10)

用 B^-1 左乘（10)式两端，并作适当整理，可得

XB=B^-1b-B^-1NXN （11)

（11)式就是用非基变量表示基变量的关系式。

相应地，记 CB=[c1，c2，⋯，cm]，CN=[cm+1，cm+2，⋯，cn]，C=[CB，CN]， 则目标函数亦可以改写为

Z=CBB^-1b+（CN-CBB^-1N)XN （12)

显然，XB=B^-1b，XN=0 构成了对应于基 B 的基本解，其相应的目标函数值为 Z=CBB^-1b。

如果 B^-1b≥0，则 XB=B^-1b，XN=0 构成了一个基本可行解，B 是一个可行基。

如果 CBB^-1N-CN≤0，则由（12)式可以看出，对于一切可行解 X，有 Z=CX

≥CBB^-1b。这就是说，对应于 B 的基本可行解为最优解，这时，B 也被称为最优基。

由于

CBB^-1A-C=CBB^-1[B，N]-[CB，CN]

=[CB，CBB^-1N]-[CB，CN]

=[0，（CBB^-1N-CN)]

（13)

即 CBB^-1N-CN≤0 与 CBB^-1A-C≤0 等价，故可得以下最优性判定定理。定理：对于基 B，若 B^-1b≥0，且 CBB^-1A-C≤0，则对应于基 B 的基本解

为最优解，B 为最优基。

由（12)和（13)式可得：

Z+（CBB^-1A-C)X=CBB^-1b （14)

用 B^-1 左乘（4″)式两端得：

B^-1AX=B^-1b （15)

联合（14)与（15)式可得：

1 C B⁻¹A − CZ  C B⁻¹b

   =  B 

(16)

0

B−1A

X

 B−1 b 

在（16)式中，称系数距阵

C B⁻¹b 1 C B⁻¹A − C

 B B 

B⁻¹b 0

或

B−1A 

C ⁻¹b C B⁻¹A − C

 B B 

 B−1b B−1A 

为对应于基 B 的单纯形表，记作 T（B)。

如果记 CBB^-1b=b00，CBB^-1A-C=[b01，b02，⋯，b0n]，B^-1b=[b10，b20，⋯， bm0]^T，以及

b11

b12

b1n 

b b b 

B⁻¹A = 



21 22 2 n 





则：

b 00



b10

bm1

b 01

b11

b m2

b02

b12

bmn 

b0n 



b1n 

T(B) = b b b b 

 20 21 22 2 n 

Μ Μ Μ Μ 

 

b m0

bm1

bm2

b mn 

（17)式表明，单纯形表就是把非基变量作为参数，表示基变量和目标函数时的系数矩阵。b00 就是对应于基 B 的基本解下的目标函数值；b10，b20，⋯， bm0 就是对应于基 B 的基本解的基变量值；b01，b02，⋯，b0n 为检验系数，如果这组数均非正，则这一基本可行解就是最优解。

（二)单纯形法的计算步骤

单纯形法求解线性规划问题的计算步骤如下：

第一步，找出初始可行基 B=[pj1，pj2，⋯，pjm]，建立初始单纯形表。第二步，判别、检查所有的检验系数 b0j（j=1，2，⋯，n)。

（1)如果所有的 b0j≤0（j=1，2，⋯，n)，则由最优性判定定理知，已获最优解。

（2)若检验系数 b0j（j=1，2，⋯，m)中，有些为正数，但其中某一正的

检验系数所对应的列向量的各分量均非正，则线性规划问题无解。

（3)若检验系数 b0j（j=1，2，⋯，n)中，有些为正数，且它们所对应的列向量中有正的分量，则进行换基迭代。

第三步，选主元。在所有 b0j＞0 的检验系数中选取最大的一个 b0s，其

对应的非基变量为 xs，对应的列向量为 ps=[b1s，b2s，⋯，bms]^T。如果

b i0

θ = min b



b_is＞0 =

b r 0

b

则确定 brs 为主元项。

 is

 rs

第四步，在基 B 中调进 ps，换出pjr，得到一个新的基 B′=[pj1，pj2，⋯， pjr-1，ps，pjr+1，⋯pjm]。

第五步，在单纯形表上进行初等行变换，使第 S 列向量变为单位向量， 又得一张新的单纯形表。

第六步，转入上述第二步。

例 1：用单纯形方法求解线性规划问题：

x1 + 3x2 ≤12

2x + x ≤9

 1 2

x ≥0，x ≥0

 1 2

maxZ=2x1+3x2

解：首先引入松弛变量 x3，x4，把原问题化为标准形式：

x1 + 3x2 + x3 = 12

2x + x + x = 9

 1 2 4

x ，x ，x ，x ≥0

在上述问题中，

 1 2 3 4

minZ′=-2x1-3x2

A = 1 3 1 0,

2 1 0 1

p = 1, p

1 2 2

= 3, p

1 3

1

0



p = 0

  

12

   

4 1, b = 9 ,

C = [−2,

− 3, 0, 0]

   

第一步，因为B = [p ，p ]为单位矩阵，且B^-1b = b＞0，故B 是一个

1 3 4 1 1

可行基。由于C B^-1b = 0，C B^-1A - C = -C，B^-1A = A，所以对应于B1的初

B 1 B - 1

始单纯形表（表 3-1)如下：

表 3-1

第二步，判别。在初始单纯形表中，b01=2，b02=3，所以 B1 不是最优基， 要进行换基迭代。

第三步，选主元。由于 max{2，3}=3，所以取 s=2，其对应的非基变量

3 12

为x2 ，对应的列向量为p2 = ( )。θ = min{ ,

9

} = 4，所以r = 1。因而主元项

为 b12=3。

1 3 1

3 0

第四步，p2 调入基，p3退出基，得新一的基B2 = （p2 ，p4 ） = （1 1）。

第五步，对初始单纯形表进行初等行变换，使 p2 变为单位向量，可得B2 下的新单纯形表（表 3-2)。

表 3-2

第六步，转入第二步。因为在对应于 B2 的单纯形表中，检验系数有正数

3 1

b01 = 1，重复以上步骤可得对应于B3 = （p2 ，p1） = （ 1 2 ）的单纯形表。

的单纯形表（表 3-3)。因为在对应于 B3 的单纯形表中，检验系数已经没有正数，所以 B3 是最优基，其对应的基本最优解为：x1=3，x2=3，x3=0，x4=0， 目标函数最小值为 Z′=-15。而对于原问题，其最优解为 x1=3，x2=3，目标函数最大值为 Z=15。

表 3-3

五、线性规划应用实例

（一)问题的提出

1983 年底，甘肃省委从实际出发，在大量的调查和可行性分析的基础上，对中部干旱地区提出了“三年停止植被破坏，五年解决温饱问题”的近期目标，鼓励农民种草养畜，走农牧草相结合的道路，并先后在通渭县的申家山、会宁县的大岔社等地，由省科委和草原工作队技术指导，对种草养畜工作进行试点。1986 年初，中部干旱地区的农业生产结构发生了重大变化， 草在种植业中占了较大的比重，养畜工作也初见成效，同时大部分地区的粮食生产已基本上得到了自给，农业生态环境逐步改善，农民依靠出售草籽而得到了较多的经济收入。但是，自 1986 年以来，草籽价格暴跌，而且国家不再统一收购草籽，这直接影响了农民的经济收入，有些人不愿再用耕地种草， 在这种情况下，中部干旱地区的农业生产结构如何调整，怎样实现草畜转化？ 这是人们所关心的问题。为了解决这一问题，笔者曾以会宁县大盆社为例， 运用线性规划方法建立了农业生产结构调整的规划模型，并由此探讨了甘肃中部干旱地区的农业生产结构问题。该规划模型的基期为 1986 年，报告期为

1990 年。实践证明，该模型在指导本地农业生产活动方面起到了一定的作用。以下，我们将这一研究成果作一些简单地介绍。

（二)模型的建立

1. 建模原则 在模型的建立过程中，我们提出了如下的建模原则。

（1)实现“草畜转化”，使农业生态环境继续得到改善，使土地资源的利用继续趋于合理化。

（2)经济效益与生态效益相结合，用经济效益刺激生态效益的提高，以生态效益保证经济效益的实现。

（3)着重考虑“三料”问题，同时也考虑农民的吃粮与花钱问题。

（4)模型不但要有理论意义，而且要有实用价值，因此，模型变量的选取要恰当，约束条件的提出要合理，模型参数的确定要准确，切合实际。

（5)考虑到剩余劳动力的存在，把“劳务输出”作为农业生产结构调整的一个重大决策问题考虑。

1. 模型结构

（1)模型变量：模型中的变量，分为外生变量与内生变量两类，外生变量是指由方针政策等因素决定的变量，内生变量是由模型本身所决定的变量。本模型的内生变量如下：

x1：粮食作物面积（亩)；x2：经济作物面积（亩)；x3：耕地种草面积

（亩)；x4：荒山造林或种草面积；x5 ：大畜存栏数（头)；x6 ：生猪年末存栏数（头)；x7：兔年末存栏数（只)；x8：劳务输出的劳动力个数（个)。

（2)目标函数：使农、林、牧各业的年平均产值达到最大（以 1986 年现行价格计算)。

（3)约束条件：①粮食的生产与分配；粮食总产量-籽种-公购粮-牲畜饲料粮≥农业人口的总口粮。

②燃料。作物秸杆×30％+荒山产柴量×80％+衣壳×50％≥全年燃料总量；

③饲料。作物秸杆×70％+装子×50％+耕地种草产量+可利用的野生草量

≥各类畜的食草总量。（作物秸杆的 30％作燃料；70％作饲草；装子的 50

％作燃料，50％作饲草；对于中部地区的林业应采取保护性政策，因此，用柴量可按产柴量的 80％计)。

④肥料：人类 + 猪粪 + 畜粪× 2 + 鸡羊粪≥粮食作物与经济作物所需

3

2 1

有机肥总量。（畜粪有 3 用于土地，其余 3 被用于烧炕）。

⑤耕地总面积限制。

⑥经济作物面积限制。

⑦耕地草面积限制。

⑧荒山面积限制。

⑨耕畜限制。

⑩水约束。

(11)劳动力限制。(12)经济收入。

1. 数学模型 以上模型结构数量化，可得如下的数学模型：

求：maxZ=33x1+50x2+135x5+40x2+100x6+5x7+800x8+9334 满足：

 1 4

 2 2 5 5

 1 2 3



 4



 1 2 3 4



xi ≥0 (i = 1, 2, , 8)

上 述 模 型 求 解 得 ：maxZ=11519190（ 元 ) x1=730.41（亩)，x2=77.50（亩)；x3=817.10（亩)；x4=773.19（亩)，

x5=54.00（头)；x6=93.15（头)；x7=1264.47（只)，x8=25.59（个)。

（三)甘肃中部干旱地区农业生产结构的特征

通过对会宁县大盆社农业生产结构优化结果的分析，笔者认为甘肃中部干旱地区农业生产结构应具有下述特征。

（1)自给性的农业是产业构成的基础，粮食生产的自给是其它一切生产的必要前提。

（2)商品性的畜牧业是产业构成的主体，草畜转化是生态效益变成经济效益的有效途径。

（3)纽带性的草业是农牧相互联系、相互促进的中枢性产业。

（4)保护性林业是改善生态环境的重要措施，也是农村燃料的主要来源。

（5)剩余劳动力的存在，为农副产品的初级加工及农村第二、第三产业的发展提供了可能的条件。