1.什么是规划论
在生产生活以及军事领域经常会遇到资源
分配问题，不同的分配方案产生的效益是不一
样的，所以，为了追求最佳效益，必须在不同
的分配方案中选择最佳的资源分配方案。规划
论就是研究针对不同需求对有限资源进行分配
的一个运筹学分支。
第三章 规划论
其中，线性规划是形成最早也是最成熟的一个分支。到
目前为止，它的应用也最广泛，是数学规划及运筹学其他分
支的基础。
线
性
规
划
整
数
规
划
动
态
规
划
零
一
规
划
非
线
性
规
划
目
标
规
划
2 理论分支
理论分支
康脱络维奇 —— 论文,生产组织与
计划中的数学方法”, 1939年。
1947年，丹捷格提出了 单纯形法
第一节 线性规划
对于一个实际问题, 如果采用线性规划去求
解, 应做两方面的工作, 一是把求解问题抽象成
能用线性规划来解的数学模型, 这就是数学建模
。 二是对这个线性规划进行求解 。 即
数
学
建
模
求
解
1 线性规划方法解决问题的过程
3.线性规划的数学模型
（ 1） 引例
某军工厂准备用三种原料来制造两种产品, 有关数据
如下表所示 。 问如何安排生产, 以使总利润达到最大化 。
单位产品 产品
消耗量
原料 （ 公斤 ）
I II 原料总量
A 9 4 360
B ４ ５ 200
C 3 10 300
单位产品利润
（元）
7 12
2 线性规划问题的数学模型
确定目标：求出生产两种产品的数量各为公斤, 以使总利
润达到最大 。
建立数学模型,
设 I 产品生产 x1 公斤, II 产品生产 x2 公斤
MAX 总利润 Z ＝ 7 x1 + 12 x2目标是
9 x1 + 4 x2 ≤ 360
4 x1 + 5 x2 ≤ 200
3 x1 + 10 x2 ≤ 300
x1,x2，, x3 ≥ 0
建立数学模型：
设 I 产品生产 x1 公斤, II 产品生产 x2 公斤
MAX 总利润 Z ＝ 7 x1 + 12 x2目标是
9 x1 + 4 x2 ≤ 360
4 x1 + 5 x2 ≤ 200
3 x1 + 10 x2 ≤ 300
x1,x2，, x3 ≥ 0
以上问题属于线性规划问题, 这类问题从数学上讲所
具有的共同特征是：
1）决策变量 。
每一个问题都用一组未知数（ x1.x2……xn） 表示某一方案，这组
未知数的一组定值代表一个具体的规划方案。通常要求这些未知
数取值是非负。以后我们称这组未知数为决策变量。
2）约束条件 。
3）目标函数 。
线性规划问题都有一个目标要求，并且这个目标可以表示为一组未知数的
线性函数，称之为目标函数，按研究问题的实际情况目标函数可以是求最小值
也可以是求最大值。我们总是希望收益、效益、效率等指标达到最大化，而对
于成本、费用,支出等指标则希望达到最小化。
（ 2）线性规划问题的共同特征
综合上述这三点, 这类问题都可以用如下数学语言
来描述 。
目标函数,max ( min ) Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn ≥（ =, ≤） b1
a21x1 + a22x2 + … a2nxn ≥（ =, ≤） b2
……
am1x1 + am2x2 + … amnxn ≥（ =, ≤） bm
x1,x2,… xn ≥ 0
3 线性规划问题的标准形式
（ 1） 线性规划的标准形式是：
目标函数,max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,… xn ≥ 0
线性规划的标准形式是：
max Z = c1 x1 + c2 x2 + … + cn xn
a11 x1 + a12 x2 + … a1n xn = b1
a21 x1 + a22 x2 + … a2n xn = b2
……
am1 x1 + am2 x2 + … amn xn = bm
x1,x2,…xn ≥ 0
max Z = ?
?
n
j
jjxc
1
i
ji
jij bxa ??
,??
?
?
???
?
?
?
mi
nj
?
?
1
1
i
ji
jij bxa ??
,
x j ≥0
用求和符号表示标准形式, 则标准形式可简写为：
3 线性规划问题的标准形式
线性规划的标准形式是：
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
用矩阵表示标准形式, 则标准形式可简写为
令 C表示由目标函数的系数构成的矩阵，即
用 A表示由约束条件的系数构成的矩阵，
即
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
?
?
?
?
21
22221
11211
?
?
?
?
?
?
Ａ＝
令 X 表示由决策变量构成的矩阵, 即
?
?
?
?
?
?
?
?
?
?
?
?
?
n
x
x
x
X
?
2
1
B表示约束条件向量，即
?
?
?
?
?
?
?
?
?
?
?
?
?
n
b
b
b
B
?
2
1
C=(c1,c2, …, c )；
3 线性规划问题的标准形式
线性规划的标准形式是：
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
用矩阵表示标准形式, 则标准形式可简写为
maxZ=CX
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
?
?
?
?
21
22221
11211
?
?
?
?
?
?
Ａ＝ ??
?
?
?
?
?
?
?
?
?
?
?
nb
b
b
B
?
2
1C=(c1,c2, …, c )；
?
?
?
?
?
?
?
?
?
?
?
?
?
nx
x
x
X
?
2
1
AX=B
X≥0
3 线性规划问题的标准形式
线性规划的标准形式是：
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
几点称谓
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
?
?
?
?
21
22221
11211
?
?
?
?
?
?
Ａ＝
?
?
?
?
?
?
?
?
?
?
?
?
?
nx
x
x
X
?
2
1
决策向量
?
?
?
?
?
?
?
?
?
?
?
?
?
nb
b
b
B
?
2
1
约束方程组的限定向量
C=(c1,c2, …, c )；价值向量
约束条件系数矩阵
（ 2） 将非标准形化为标准形式
非标准形式是
max ( min ) Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn≥（ =, ≤） b1
a21x1 + a22x2 + … a2nxn≥（ =, ≤） b2
……
am1x1 + am2x2 + … amnxn ≥（ =, ≤） bm
x1,x2,…xn ≥ 0
标准形式是,
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
（ 2） 将非标准形化为标准形式
非标准形式
min Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
（ 1 ） 若目标函数求最小
值可以把它转化为求负的同
一目标函数的最大值，即
令 Z‵ = --Z
min Z = max Z‵
非标准形式
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn ≤ b1
a21x1 + a22x2 + … a2nxn ≥ b2
……
am1x1 + am2x2 + … amnxn ≤ bm
x1,x2,…xn ≥ 0
（ 2 ） 约束方程组中有不
等式，这时有两种情况：一
种是, ≤” 形式的不等式，
则可在式子的左端加一非负
变量称为, 松弛变量, ；
如,x1 + x2 + x3 ≤ 60另外一种是 ≥形式的不等式则在左端减一松弛变量使之
变为等式约束。
如,x1 + x2 + x3 ≥ 60
（ 2） 将非标准形化为标准形式
非标准形式是
max ( min ) Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
… …… …… …… ………… …… … …
am1x1 + am2x2 + … amnxn = bm
xk 无非负要求, xj ≤0, 其余的
变量大于等于零 。
（ 3 ）若决策变量无非负要
求
令 xk =xk`--xk``,
xk`,xk``≥0
（ 3 ）若要求决策变量 xj
≤0
可令 xj` = -- xj
xj ≥0
（ 2） 将非标准形化为标准形式
试将线性规划问题化为标准形式：
minz= -x1 + 2x2 - 3x3
x1 + x2 + x3 ≤ 7
x1 - x2 + x3 ≥ 2
-3 x1 + x2 + 2 x3 = 5
x1, x2≥0
例题
（ 2） 将非标准形化为标准形式
4 用图解法求解线性规划
线性规划的图解法就是利用解析几何
的方法来求解线性规划的问题 。 因为只有
二维几何空间最为直观, 所以图解法只能
用来求解二维线性规划问题, 也就是只有
两个决策变量的线性规划问题 。 下面我们
结合实例来讲解线性规划的图解法 。
求解线性规划问题
maxZ＝ 2x1+5x2
x1≤4
x2≤3
x1+2x2≤ 8
x1≥0,x2≥0
例题
把 x1,x2 看作上平面上点的坐标, 在第一象限
内用图形将此规划问题的约束条件和目标函数都反
映出来就是
约束条件围成了一个区域, 这个凸多边形
oabcd内的任一点的坐标都满足约束条件 。 而
凸边形外的点都不能满足约束条件, 所以凸
多边形内的任一点的坐标都是这个线性规划
问题的一个解, 我们称之为可行解 。 凸多边
形构成的可行解的全体, 称为可行解集 （ 可
行域 ） 。 满足目标函数的一个可行解的全体
z=2x1+5x2是一组平行线, 随 z的增加不断向上
平移, 当移到 b点时, 达到最大值 2x1+5x2=19。
图解法解题的基本步骤
确定可行域
确定目标函数移动的方向
确定最优解
用图解法求解如下线性规划问题
min Z = 2x1 + 2x2
x1 - x2 ≥ 1
x1 + 2x2 ≤ 0
x1, x2 ≥ 0
练习 1
用图解法求解如下线性规划问题
min Z = 2x1 + 2x2
-x1 + x2 ≥1
x1 + x2 ≤-2
x1,x2 ≥0
练习 2
5 有关线性规划问题解的概念
可行域 —— 所有可行解所构成的集合就是可行域
对于图解法，可行域就是由约束条件围成的一个凸多边形，我们
如果用 R表示可行域，则
R={x/Ax=b,x≥0}
可行解 ——同样, 在可行域上的点都满足约束条件所以, 我们称
这些点为可行解 。
x=(x1,x2…x n)T
x1 + x2 + x3 + x4+ x5 = 5
5 有关线性规划问题解的概念
基 —— 设Ａ为约束方程组中的 m× n阶系数矩阵，其秩为 m，（ 秩为 m的意思
为 m行线性无关），又 B是Ａ中 m× n非奇异子矩阵（ |B|不等于 0），则称 B是
这个线性规划问题的一个基。
?
?
?
?
?
?
?
?
?
?
?
?
mmmm
m
m
aaa
aaa
aaa
?
????
?
?
21
22221
11211
B=
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
?
?
?
?
?
?
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
?
????
?
?
21
22221
11211
这是它的系数矩阵
5 有关线性规划问题解的概念
基 —— 设Ａ为约束方程组中的 m× n阶系数矩阵，其秩为 m，
（ 秩为 m的意思为 m行线性无关），又 B是Ａ中 m× n非奇异子矩
阵（ |B|不等于 0），则称 B是这个线性规划问题的一个基。
?
?
?
?
?
?
?
?
?
?
?
?
mmmm
m
m
aaa
aaa
aaa
?
????
?
?
21
22221
11211
B=
?
?
?
?
?
?
?
?
?
?
?
?
mmmm
m
m
aaa
aaa
aaa
?
????
?
?
21
22221
11211
B=
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
=（ P1,P2,……, PM）
基变量 ——称 Pj ( j=1,2…m ) 为基向量, 与 Pj相对应的 Xj ( j =1,2…m)
称为 基变量 。
?
?
?
?
?
?
?
?
?
?
?
?
mmmm
m
m
aaa
aaa
aaa
?
????
?
?
21
22221
11211
B=
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
=（ P1,P2,……, PM）
非基变量 ——其余变量称为 （ 对应于Ｂ ） 的 非基变量 。
基本解 —— 当取定一个基时, 令非基变量为 0,由克莱姆法则
可得对应于该基的唯一解 。 此解的非零数目不超过个 m个, 非 0
分量的数目等于 m的基本解称为非退化的, 否则称为退化的 。
a11x1 + a12x2 + … a1mx2 +…+ a1nxn = b1
a21x1 + a22x2 + … a2mx2 + … + a2nxn = b2
……
am1x1 + am2x2 + … a2mx2 + … + amnxn = bm
例如当我们取为基时
?
?
?
?
?
?
?
?
?
?
?
?
mmmm
m
m
aaa
aaa
aaa
?
????
?
?
21
22221
11211
B= 为基时
基本解 —— 当取定一个基时, 令非基变量为 0,由克莱姆法则
可得对应于该基的唯一解 。 此解的非零数目不超过个 m个, 非 0
分量的数目等于 m的基本解称为非退化的, 否则称为退化的 。
a11x1 + a12x2 + … a1mx2 +…+ a1nxn = b1
a21x1 + a22x2 + … a2mx2 +…+ a2nxn = b2
……
am1x1 + am2x2 + … a2mx2 +…+ amnxn = bm
X=(x1,x2,…,xm,0,0…0)
基本可行解 —— 满足非负条件的基本解叫基本可行解，它是基本解又是可行解。基
本可行解的数目（非零分量）不大于 m,并且都是非负的。一般地说，基本可行解
的数目小于基本解的数目，最多是相等。
a11x1 + a12x2 + … a1mx2 +… + a1nxn = b1
a21x1 + a22x2 + … a2mx2 + …+ a2nxn = b2
……
am1x1 + am2x2 + … a2mx2 +… + amnxn = bm
x1,x2,… xn ≥ 0
基本可行解
X=(x1,x2,…,xm,0,0…0)
基本可行解 —— 满足满足目标函数要求的可行解，称为线性规划问题的最优解。
a11x1 + a12x2 + … a1mx2 +… + a1nxn = b1
a21x1 + a22x2 + … a2mx2 + …+ a2nxn = b2
……
am1x1 + am2x2 + … a2mx2 +… + amnxn = bm
x1,x2,… xn ≥ 0
最优解
X=(x1,x2,…,xm,0,0…0)
max Z = c1x1 + c2x2 + … + cnxn
满足非负条件
可行解
基本
解
取定一个基
基本
可行解
最优解
满足目标函数要求
解 之 间 的 关 系
max z= x3
x1 + x2 + x3 + x4+ x5 = 4
x1 + x2 + x3 + x4- x5= 4
xi ≥ 0,i = 1,2,…,5
2 理论分支例题 1
对于约束方程组
x1 - x2 + 2 x3 = 1
x1 + x2 + x3 =1
x1,x2,x3 ≥0
系数矩阵 基 退化解 非退化解
2 理论分支例 题 2
对于约束方程组
系数矩阵 基 退化解 非退化解
x1 + x2 - x3 = 1
x1 - x2 - x3 = 2
x1,x2,x3 ≥0
6 线性规划解的性质
设 Ｄ 是 n 维欧氏空间的一个点集, 连接Ｄ中任
意两点 X,Y 的线段仍在Ｄ内, 则称 Ｄ 为凸集 。
1,凸集的 概念
X
Y
X
Y●
● ●
●
●
●
图中每个点都是由 n 维坐标表
示的，这个 n 维坐标与 向量
是一致的，而向量是与线性规
划问题的解是一致的。
=1
=u =1-u
1≥ u ≥0
x
yz
Z= x+ ( y- x) u= ( 1- u) x+ u y
任一点的表示方法
令 X Y 之间的相对长度为 1,X Z之间的长度站整个长度 的 比例为 U，
6 线性规划问题解的性质
设 集合 R是 n 维线性空间, 如果其中任意两点 X 和 Y,
如果对于任意 1 ≥ u ≥ 0,都有 ( 1 - u ) x + u y 仍然属
于 R, 则可说 R 为凸集 。
（ 1） 基本概念
凸集数学表述
顶点
设 集合 R 是一个凸集, Z 是这个集合中中的一点, 如果在
此集合中找不到两个不同的点 X 和 Y, 使 Z = ( 1- u ) x+ u
y, 1 ≥ u ≥0 成立, 则可说 Z 点为 S凸集的顶点 。
x1
x2
x1
x2
顶点的直观解释
（ 2） 线性规划问题解的性质定理
定理 1 线性规划问题的可行解集 R 为凸集 。
首先, 线性规划问题的可行解 X=(x1,x2,…,
xn)是一个 n 维向量, 它可以看成是一个由 n 个坐标
构成的点 。 线性规划问题可能有不止一个可行解,也就
是说可能有很多个这样的点, 这些点就构成了一个集
合, 很显然这个集合就是一个 n 维欧氏空间, 我们要
证明的结论, 就是这个集合是一个 凸集 。
X
Y
线性规划问题所有的解 所构成的集合
证明这个问题的基本思路
也就是，已知 X 和 Y 是线性规划问题的两个不同的解，要证明这
两个解的连线中间的任意一个点也是线性规划问题的解，也就是 ( 1- u) x+ u
y 也是一个解，也就是它也属于集合 R。
证明过程
设任意 X 和 Y ∈ R,目标是要证明对于任意 1≥ u ≥0,
Z= u X + ( 1- u) Y ∈ R
A Z = A （ u X + ( 1- u) Y）
因为 X,Y ∈ R,所以 X ≥0,Y ≥0,而且
AX = B
AY = B
= A uX + A ( 1- u) Y
= u B + ( 1- u) B = B
定理 2 凸集的顶点对应于基本可行解 。
首先, 线性规划问题的可行解 X=(x1,
x2,…,xn)是一个 n 维向量, 它可以看
成是一个由 n 个坐标构成的点 。 线性规划
问题可能有不止一个可行解,也就是说可能
有很多个这样的点, 这些点就构成了一个集
合, 上面已经证明这个集合是一个 凸集 。
此定理说, 这个凸集的顶点是基本可行
解,同样基本可行解也必是这个凸集的顶点,
首先还要理解基本可行解的含义,基本可
行解是线性规划问题系数矩阵一个特定的基
所对应的可行解,基本解首先是一个可行解,
然后它还是一个基本解,
可行域 R
必要性的证明
也就是已知线性规划问题的一个解 X 是这个线性
规划问题可行解集合 (可行域 ) R 的顶点,要证明 X 是此
线性规划问题的一个基本可行解,
简单地加以分析
在这个问题中,已经知道了 X 线性规划问题可行解
集合 (可行域 ) R 的顶点,那么 X 就肯定是一个可行解了,
关键是要如何再证明这个可行解是一个基本解了,
可行域 R
X
设 X = (x1,x2,…,xn)T,中有 K 个分量大于 0,
不失一般性可以设其前 K个分量大于 0,则
X =(x1,x2,…,xK,0,0,…,0 )T
那么约束条件 AX=B 中 AX 的就可以写成
AX=
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
?
?
?
?
21
22221
11211
?
?
?
?
?
?
x1
X2
…
xK
0
…
0
= (P1,P2,…,P k)
x1
X2
…
xK
x1
X2
…
xK
0
…
0
?
?
?
?
?
?
?
?
?
?
?
?
mn
n
n
mkmm
k
k
a
a
a
aaa
aaa
aaa
?
?
?
?
?
??
?
?
2
1
21
22221
11211
=
P1 P2 … Pk … Pn
?
?
?
?
?
?
?
?
?
?
?
?
mn
n
n
mkmm
k
k
a
a
a
aaa
aaa
aaa
?
?
?
?
?
??
?
?
2
1
21
22221
11211
=
x1
X2
…
xK
0
…
0
= x1 P1+ x2 P2+…+ xk Pk
最终整理结果就是：
那么,如果我们能够证明 P1,P2,…,Pk 是线性无关的,则由 P1,P2,…,Pk 列
向量所构成的矩阵
= x1 P1+ x2 P2+…+ xk Pk
x1
X2
…
xK
0
…
0
?
?
?
?
?
?
?
?
?
?
?
?
AX=
mn
n
n
mkmm
k
k
a
a
a
aaa
aaa
aaa
?
?
?
?
?
??
?
?
2
1
21
22221
11211
P1 P2 … Pk … Pn
中的 K个列向量是线性无关的,则说明必然存在一个 K阶子矩阵 BK是非奇异
矩阵,也就说明 BK是一个基,这样,也就证明了 X是一个基本可行解,
所以整个问题就转化为证明向量 P1,P2,…,Pk 是线性无关的, 用反证法
来证明这个问题。
?
?
?
?
?
?
?
?
?
?
?
?
mkmm
k
k
aaa
aaa
aaa
?
??
?
?
21
22221
11211
P1 P2 … Pk
假设 P1,P2,…,Pk 是线性相关的,则必然存在 K个不全为 0的数,y1,y2,…,
yk,使 y1 P1+ y2 P2+…+ yk Pk =0 成立。
= x1 P1+ x2 P2+…+ xk Pk
x1
X2
…
xK
0
…
0
?
?
?
?
?
?
?
?
?
?
?
?
AX=
mn
n
n
mkmm
k
k
a
a
a
aaa
aaa
aaa
?
?
?
?
?
??
?
?
2
1
21
22221
11211
P1 P2 … Pk … Pn
假设 是线性相关的 则必然存在 个不全为 的数,…
使 成立。
?
?
?
?
?
??
?
?
y1 P1+ y2 P2+…+ yk Pk= (P1,P2,…,P k)
y1
y2
…
yK
(P1,P2,…,P k,0,…0 )
y1
y2
…
yK
0
…
0
=
= AY
而
=0
我们再来看向量 X
X =(x1,x2,…,xK,0,0,…,0 ) T
因为 X 是可行解，所以 X中的每个分量 x1,x2,…,xK 都
必然大于 0,
那么就可以取足够小的数 ε,使 X+ εY＞ 0,X— εY＞ 0
因为 AX=B,AY=0那么
A（ X+ εY） = A X+ ε A Y =B+0=B
同理 A（ X— εY） = B
这说明 X+ εY, X— εY都分别是线性规划问题的
解。
而 X=1/2（ X+ εY） + 1/2 （ X— εY）
这说明点 X 是点（ X+ εY） 和点 （ X— εY） 的中
间点。是中间点就不是顶点。这与已知相互矛盾，说
明假设不成立。也就证明向量 P1,P2,…,Pk 是线性无关
的，进而证明了解 X 是线性规划问题的一个基本可行
解。
充分性的证明留给同志们自己课下学习
定理 3 如果可行域 R 有界, 则线性规划问题的
目标函数一定在其顶点处达到最大值 。
有界可行域 R 无界可行域 R
A B
CD
用反证法来证明这个问题, 设 X（ 1）, X（ 2） …… X（ h） 是可
行域的顶点, 而 X（ 0） 不是可行域的顶点, 但目标函数却在 X（ 0） 处达到了
最大值 。
有界可行域 R
X（ 1） X（ 2）
X（ H） ……
首先我们来证明 X（ 0） 可
用其他顶点进行线性表示 。 即
X（ 0） =u1 X（ 1） +u2 X
（ 2） +… + uh X（ h）,而且
u1 +u2 +… + uh =1
X（ 0）
首先我们来证明 X（ 0） 可用其他
顶点进行线性表示 。 即
X（ 0） =u1 X（ 1） +u2 X（ 2）
+… + uh X（ h）,而且 u1 +u2
+… + uh =1
有界可行域 R
X（ I） X（ L）
X（ Y）
……X（ 0）
我们以二维可行域为例来证明
这个问题 。
因为 X（ 0） =（ 1-u1） X（ Y） +u1 X（ K）
而 X（ K） = （ 1-u2） X（ I） + u2 X（ L）
u1
1-u1
X（ K）
u2 1-u2
最后可得 X（ 0） =（ 1-u1 ） X（ Y） + u1 （ 1-u2 ） X（ I） +
u1u2 X（ L）
可以验证各顶点前的 系数之和为 1。
我们可以将此结论进行一般推广，就可得到 首先我们来证明 X（ 0）
可用其他顶点进行线性表示。即
X（ 0） =u1 X（ 1） +u2 X（ 2） +…+ uh X（ h）,而且
u1 +u2 +…+ uh =1
有界可行域 R
X（ 1） X（ 2）
X（ H） ……
X（ 0）
在回到原来的问题上，因为 X（ 0） =u1 X（ 1） +u2 X（ 2） +…+ uh
X（ h）,而且 u1 +u2 +…+ uh =1，因此 Z ?=C X（ 0）
=C （ u1 X（ 1） +u2 X（ 2） +…+ uh X（ h） ）
=u1C X（ 1） +u2C X（ 2） +…+ uh CX（ h）
在所有顶点的目标函数值中，必然要有一个最大者，假设它是 X（ m）
≦ u1C X（ m） +u2C X（ m） +…+ uh CX（ m）
=u1C X（ m） +u2C X（ m） +…+ uh CX（ m）
=CX（ m）
最终得到 Z ?=C X（ 0） ≦ CX（ m）
这与已知是矛盾的，同时也说明了最优解必然在顶点上取得。
定理 3 如果可行域 R 有界, 则线性规划问题的
目标函数一定在其顶点处达到最大值 。
定理 1 线性规划问题的可行解集 R 为凸集 。
定理 2 凸集的顶点对应于基本可行解 。
定理 3 如果可行域 R 有界, 则线性规划问题的
目标函数一定在其顶点处达到最大值 。
定理 1 线性规划问题的可行解集 为凸集 。
定理 2 凸集的顶点对应于基本可行解 。
三个定理的回忆
以上三个定理说明线性规划问题的所有可行解组成一
个集合, 也就是可行域, 这个可行域是 凸集, 这个
有有限个顶点, 线性规划问题每一个基本可行解都对
应着可行域的一个顶点, 如果线性规划问题有最优解,
则最优解必然在顶点上达到 。
以上三个定理说明线性规划问
题的所有可行解组成一个集合, 也
就是可行域, 这个可行域是 凸集,
这个 有有限个顶点, 线性规划
问题每一个基本可行解都对应着可
行域的一个顶点, 如果线性规划问
题有最优解, 则最优解必然在顶点
上达到 。
三个定理
顶点个数 =
m
nC
1 单纯形法求解线性规划问题的基本思想
第二节 单纯形法
1
2
3
对于线性规划问题的标准
形式, 从可行域中一个基本可
行解出发, 寻求使目标函数值
有较大增加的另一个基本可行
解, 由于基本可行解个数是有
限的, 所以经过有限次迭代目
标函数值将逐步增大最终达到
最优 。
可行域 R
初始基本可行解
改进基本可行解
结束
最优？
单纯形法求解线性规划问题的基本思想
1
2
3
可行域 R
从以上分析可以看出,应用单纯形法求解线
性规划问题，需要解决的三个方面问题是,
1,初始基本可行解如何求；
2,如何判断是否最优 ；
3,如何求改进的基本可行解 。
引 例
求解如下线性规划
max Z = 2 x1 + 3 x2
2 x1 + x2 ≤2
X1 + 3 x2 ≤3
X1,x2 ≥0
（ 1） 将上例化为标准形式
max Z = 2 x1 + 3 x2
2 x1 + x2 +x3 =2
X1 + 3 x2 +x4 =3
X1,x2,x3,x4 ≥0
第一步 首先要求出其基本可行解来
2、找初始基本可行解
约束方程的系数矩阵为,
),,,(
1031
0112
4321 PPPPA ??
?
?
??
??
此系数矩阵 A 中的两行很显然是线性独立的，所以它的秩为 2，
我们可以任意地组合其列向量,从而得到一个基，并求基本解。
例如，列向量 P3,P4是线性无关的,所以 P3,P4组合为
矩阵可作为一个基。
),(
10
01
43 PPB ??
?
?
??
??
),(
10
01
43 PPB ??
?
?
??
??
根据这个基，对照原约束方程组，就可以求出其对应的基本可行解来
X（ 1） =（ 0,0,2,3），
将这个基本可行解代入目标函数表达式,max Z = 2 x1 + 3 x2 中，
得到目标函数值为 0，
从目标函数的表达式中，直观地看，增加非基变量 x2的值，可以是目
标函数得到较大的增长，所以 应该让非基变量 x2变为基变量（进基） x1,
仍为非基变量。即令 x1=0,同时此例中不能超过二个基变量（因为约束条
件的系数矩阵的秩为 2，最优解肯定是二为的），还得从 x3,x4中换出一个做
非基变量（离基）并需保证非负条件，
（ 2）判断基本可行解是否是最优解
如果选 x 3 变量出基（也就是使 x 3 变量变为非基变量，非基变量的值
为 0），根据（ 1）式得到 x 2 =2，将 x 2 =2 代入（ 2）式得到,x4 =--3，
这就不满足了第三个约束条件。所以不能选择 x 3 作为出基变量。
同样方法，可以验证，选择 x4 变量作为出基变量是可以的。
（ 3） 迭代（ 也就是求改进的基本可行解 ）
2 x1 + x2 +x3 = 2 ……… …（ 1）
X1 + 3 x2 +x4 = 3…… … …（ 2）
X1,x2,x3,x4 ≥0
以上选择出基变量的方法可用数学的方法归纳为 min {2/1,3/3},也就
是,
min {b1/a1j,b2/a2j,b3/a3j,…,bm/amj }
在确定了 x 2 进基,x 4 出基以后，为了求得以 x2,x3 为基变量的上述新的基本可行解
x (1) 及目标值 z (x (1)),只要对原约束方程进行一次初等变换，即把方程组中第二等式里
x2 的系数化为 1 也就是以第二等式里 x2 的系数化为 1,也就是以第二等式中 x2 的系数为
主元进行一次高斯消元，得到
2 x1 + x2 +x3 =2
X1 + 3 x2 +x4 = 3
X1,x2,x3,x4 ≥0
也就是以第二个等式中 x2 的系数为主元进行一次高斯消元，得到
1/3x1+x2 +1/3x4 = 1
5/3x1 +x3- 1/3x4 = 1
1/3x1+x2 + 1/3x4 = 1 …… ……… …（ 3）
5/3x1 +x3 -1/3x4 = 1 … ……… …… （ 4）
将上述约束条件，变成关于基变量的表达式：
x2=1-1/3x1--1/3x4≥0
x3=1-5/3x1+1/3x4≥0
将这个表达式代入目标函数得到,
Z=3+x1-x4
判断是否是最优解
迭代
2 单纯形法的一般原理
（ 1）从线性规划的系数矩阵能直接观察到。
x1 + 3 x4 + 2 x5 = 360
x2 + 4 x4 + 5 x5 = 200
x3 + 2 x4 + 7 x5 = 300
x1,x2，, x3 ≥ 0
MAX Z ＝ 7 x1 + 12 x2
B=（ P1,P2,P3）
?
?
?
?
?
?
?
?
?
?
100
010
001=
1、初始基本可行解的确定
由以上的引例我们可以看出，对于一个线性规划的问题，为了确定初始基本可行解，首先
要找到一个初始可行基，这个可行基 最好 是一个单位矩阵，主要有三种方法：
x1 + 3 x4 + 2 x5 = 360
x2 + 4 x4 + 5 x5 = 200
x3 + 2 x4 + 7 x5 = 300
x1,x2，, x3 ≥ 0
MAX Z ＝ 7 x1 + 12 x2
x1 + 3 x4 + 2 x5 = 360
x2 + 4 x4 + 5 x5 = 200
x3 + 2 x4 + 7 x5 = 300
x1,x2，, x3 ≥ 0
?
?
?
?
?
?
?
?
?
?
100
010
001
B=
?
?
?
?
?
?
?
?
?
?
001
100
010
B=
不能直接看出，要调整顺序
（ 2）对于约束条件是, ≤” 形式的不等式的情况，经过加非负的松弛
变量可以等到一个单位矩阵。
MAX Z ＝ 7 x1 + 12 x2
9 x1 + 4 x2 ≤ 360
4 x1 + 5 x2 ≤ 200
3 x1 + 10 x2 ≤ 300
x1,x2，, x3 ≥ 0
MAX Z ＝ 7 x1 + 12 x2
9 x1 + 4 x2 + x3 = 360
4 x1 + 5 x2 + x4 = 200
3 x1 + 10 x2 + x5 = 300
x1,x2，, x3, x4, x5 ≥ 0
?
?
?
?
?
?
?
?
?
?
100
010
001B=
（ 3）对于约束条件是,≥”的形式，采用人工造基的方法减去
一个非负的松弛变量，再加上一个非负的人工变量总能得到一个单
位矩阵。
x1 + 3 x4 + 2 x5 = 360
x2 + 4 x4 + 5 x5 = 200
2x3 + 2 x4 + 7 x5 ≥ 300
x1,x2，, x3 ≥ 0
MAX Z ＝ 7 x1 + 12 x2
黑
板
演
示
找到了初始基本可行基，也就相应地找到了初始
基本可行解。然后就要判断这个解是否是最优解。
判断最优时，目标函数必须化成关于非基变量的
函数，如果是最优解，停止；反之继续选代。
判断最优的标准，就是在目标函数中所有非基变
量的系数均为负，如果系数大于零则目标函数还可能
增加，因此需要将一个非基变量进基，同时相应地要
选择另一个基变量离基。
2、最优性检验
最优性检验的准则
x1 + … + a1m+1xm+1 +… + a1nxn = b1
x2 + … + a2m+1xm+1 + … + a2nxn = b2
……
xm + ammxm+1 + … + amnxn = bm
x1,x2,… xn ≥ 0
max Z = c1x1 + c2x2 + … + cnxn
x1 = b1 --( a1m+1xm+1 + …+ a1nxn )
x2 = b2 --( a2m+1xm+1 + …+ a2nxn )
……
xm = bm --( amm+1xm+1 +… + amnxn )
Z = c1x1 + c2x2 + … + cmxm + cm+1xm + 1+ … + cnxn
Z =( c1 b1 + c2b2 + … + cmbm ) + ? ?
?? ?
?
n
mj
m
i
ijiij accx
1 1
)(
Z =Z((X0 )) +
nnmmmm xxx ??? ??? ???? ?2211
?
?
?
m
i
ijii acc
1
)(
令 =
j?
( j=m+1,m+2,…,n )
接 3
3、迭代（基本可行解的转换）
通过检验数就可以确定出哪个非基变量应该
变为基变量（这叫做进基），再根据最小比值原
则就可以确定出哪个基变量应该变为非基变量
（这叫做出基）。
有了新的基变量就有了新的基本可行解，新的
基本可行解可通过高斯初等变换的方法求得。通
过高斯变换将基变量对应的列向量变换为单位列
向量，就能直接看出基本可行解 。
3 利用单纯形表解线性规划
1、结合实例讲解利用单纯形表解线性规划
max z = 2x1-x2+x3
3x1+x2+x3 ≤60
x1-x2+2x3 ≤10
x1+x2-x3 ≤20
x1,x2,x3 ≥0
将它化为标准形式
maxz=2x1-x2+x3
3x1+x2+x3+x4 = 60
x1 -x2+2x3 +x5 = 10
x1 +x2 -x3 +x6 = 20
x1,x2,x3,x4,x5,x6≥0
CB xB 2 -1 1 0 0 0 B
x1 x2 x3 x4 x5 x6
0 x4 3 1 1 1 0 0 60
0 x5 [1] –1 2 0 1 0 20
0 x6 1 1 -1 0 0 1 10
λj 2 -1 1 0 0 0
maxz=2x1-x2+x3
3x1+x2+x3+x4 = 60
x1 -x2+2x3 +x5 = 10
x1 +x2 -x3 +x6 = 20
x1,x2,x3,x4,x5,x6≥0
4、人工变量求可行基的方法
例题
max z = 3x1 - x2 - x3
x1- 2x2+ x3 ≤ 11
-4 x1 +x2+2x3 ≥3
2 x1 - x3 = -1
x 1,x 2,x 3 ≥0
首先，将它变为标准型
Max z =3x1-x2-x3
x1 - 2x2 + x3 + x4 = 11
-4x1 +x2+2x3 –x5 = 3
- 2x1 + x3 = 1
x1,x2,x3,x4,x5 ≥0
1 大 M 法
2 两阶段法
21 3m a x xxZ ??
?
?
?
?
?
??
??
??
0,0
42
8
21
21
21
xx
xx
xx
练 习 1
213m i n xxZ ??
?
?
?
?
?
??
??
??
0,0
42
8
21
21
21
xx
xx
xx
练 习 2
5、在实际求解中会遇到的问题及解决的办法
max z =x1+x2
x1 - 2x2 ≤2
x1 + x2 ≤2
x1,x2≥0
例题
max z =x1+x2
x1 - 2x2 ≤2
x1 + x2 ≤2
x1,x2≥0
首先要将它化为标准型
max z = x1+ x2
x1 - 2x2 +x3 = 2
x1 + x2 +x4 = 2
x1,x2≥0
（ 1）非基变量的检验数为 0；
在这种情况下最优解不唯一，而最优值不能改进了。
（ 2）检验数相同；
可以任选其中一个非基变量进基，选择的不同仅引起选代次数的
不同。
（ 3）最小比值相同；
进一步选代不一定会立即引起目标函数的改变，只要检验数仍为正，
则最终能够得到最优值
（ 4）退化和循环。
5、在实际求解中会遇到的问题及解决的办法
CB xB 1 1 0 0 B
x1 x2 x3 x4 x5 x6
0 x4 3 1 1 1 0 0 60
0 x5 [1] –1 2 0 1 0 20
λj 2 -1 1 0 0 0
在生产生活以及军事领域经常会遇到资源
分配问题，不同的分配方案产生的效益是不一
样的，所以，为了追求最佳效益，必须在不同
的分配方案中选择最佳的资源分配方案。规划
论就是研究针对不同需求对有限资源进行分配
的一个运筹学分支。
第三章 规划论
其中，线性规划是形成最早也是最成熟的一个分支。到
目前为止，它的应用也最广泛，是数学规划及运筹学其他分
支的基础。
线
性
规
划
整
数
规
划
动
态
规
划
零
一
规
划
非
线
性
规
划
目
标
规
划
2 理论分支
理论分支
康脱络维奇 —— 论文,生产组织与
计划中的数学方法”, 1939年。
1947年，丹捷格提出了 单纯形法
第一节 线性规划
对于一个实际问题, 如果采用线性规划去求
解, 应做两方面的工作, 一是把求解问题抽象成
能用线性规划来解的数学模型, 这就是数学建模
。 二是对这个线性规划进行求解 。 即
数
学
建
模
求
解
1 线性规划方法解决问题的过程
3.线性规划的数学模型
（ 1） 引例
某军工厂准备用三种原料来制造两种产品, 有关数据
如下表所示 。 问如何安排生产, 以使总利润达到最大化 。
单位产品 产品
消耗量
原料 （ 公斤 ）
I II 原料总量
A 9 4 360
B ４ ５ 200
C 3 10 300
单位产品利润
（元）
7 12
2 线性规划问题的数学模型
确定目标：求出生产两种产品的数量各为公斤, 以使总利
润达到最大 。
建立数学模型,
设 I 产品生产 x1 公斤, II 产品生产 x2 公斤
MAX 总利润 Z ＝ 7 x1 + 12 x2目标是
9 x1 + 4 x2 ≤ 360
4 x1 + 5 x2 ≤ 200
3 x1 + 10 x2 ≤ 300
x1,x2，, x3 ≥ 0
建立数学模型：
设 I 产品生产 x1 公斤, II 产品生产 x2 公斤
MAX 总利润 Z ＝ 7 x1 + 12 x2目标是
9 x1 + 4 x2 ≤ 360
4 x1 + 5 x2 ≤ 200
3 x1 + 10 x2 ≤ 300
x1,x2，, x3 ≥ 0
以上问题属于线性规划问题, 这类问题从数学上讲所
具有的共同特征是：
1）决策变量 。
每一个问题都用一组未知数（ x1.x2……xn） 表示某一方案，这组
未知数的一组定值代表一个具体的规划方案。通常要求这些未知
数取值是非负。以后我们称这组未知数为决策变量。
2）约束条件 。
3）目标函数 。
线性规划问题都有一个目标要求，并且这个目标可以表示为一组未知数的
线性函数，称之为目标函数，按研究问题的实际情况目标函数可以是求最小值
也可以是求最大值。我们总是希望收益、效益、效率等指标达到最大化，而对
于成本、费用,支出等指标则希望达到最小化。
（ 2）线性规划问题的共同特征
综合上述这三点, 这类问题都可以用如下数学语言
来描述 。
目标函数,max ( min ) Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn ≥（ =, ≤） b1
a21x1 + a22x2 + … a2nxn ≥（ =, ≤） b2
……
am1x1 + am2x2 + … amnxn ≥（ =, ≤） bm
x1,x2,… xn ≥ 0
3 线性规划问题的标准形式
（ 1） 线性规划的标准形式是：
目标函数,max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,… xn ≥ 0
线性规划的标准形式是：
max Z = c1 x1 + c2 x2 + … + cn xn
a11 x1 + a12 x2 + … a1n xn = b1
a21 x1 + a22 x2 + … a2n xn = b2
……
am1 x1 + am2 x2 + … amn xn = bm
x1,x2,…xn ≥ 0
max Z = ?
?
n
j
jjxc
1
i
ji
jij bxa ??
,??
?
?
???
?
?
?
mi
nj
?
?
1
1
i
ji
jij bxa ??
,
x j ≥0
用求和符号表示标准形式, 则标准形式可简写为：
3 线性规划问题的标准形式
线性规划的标准形式是：
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
用矩阵表示标准形式, 则标准形式可简写为
令 C表示由目标函数的系数构成的矩阵，即
用 A表示由约束条件的系数构成的矩阵，
即
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
?
?
?
?
21
22221
11211
?
?
?
?
?
?
Ａ＝
令 X 表示由决策变量构成的矩阵, 即
?
?
?
?
?
?
?
?
?
?
?
?
?
n
x
x
x
X
?
2
1
B表示约束条件向量，即
?
?
?
?
?
?
?
?
?
?
?
?
?
n
b
b
b
B
?
2
1
C=(c1,c2, …, c )；
3 线性规划问题的标准形式
线性规划的标准形式是：
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
用矩阵表示标准形式, 则标准形式可简写为
maxZ=CX
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
?
?
?
?
21
22221
11211
?
?
?
?
?
?
Ａ＝ ??
?
?
?
?
?
?
?
?
?
?
?
nb
b
b
B
?
2
1C=(c1,c2, …, c )；
?
?
?
?
?
?
?
?
?
?
?
?
?
nx
x
x
X
?
2
1
AX=B
X≥0
3 线性规划问题的标准形式
线性规划的标准形式是：
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
几点称谓
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
?
?
?
?
21
22221
11211
?
?
?
?
?
?
Ａ＝
?
?
?
?
?
?
?
?
?
?
?
?
?
nx
x
x
X
?
2
1
决策向量
?
?
?
?
?
?
?
?
?
?
?
?
?
nb
b
b
B
?
2
1
约束方程组的限定向量
C=(c1,c2, …, c )；价值向量
约束条件系数矩阵
（ 2） 将非标准形化为标准形式
非标准形式是
max ( min ) Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn≥（ =, ≤） b1
a21x1 + a22x2 + … a2nxn≥（ =, ≤） b2
……
am1x1 + am2x2 + … amnxn ≥（ =, ≤） bm
x1,x2,…xn ≥ 0
标准形式是,
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
（ 2） 将非标准形化为标准形式
非标准形式
min Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
（ 1 ） 若目标函数求最小
值可以把它转化为求负的同
一目标函数的最大值，即
令 Z‵ = --Z
min Z = max Z‵
非标准形式
max Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn ≤ b1
a21x1 + a22x2 + … a2nxn ≥ b2
……
am1x1 + am2x2 + … amnxn ≤ bm
x1,x2,…xn ≥ 0
（ 2 ） 约束方程组中有不
等式，这时有两种情况：一
种是, ≤” 形式的不等式，
则可在式子的左端加一非负
变量称为, 松弛变量, ；
如,x1 + x2 + x3 ≤ 60另外一种是 ≥形式的不等式则在左端减一松弛变量使之
变为等式约束。
如,x1 + x2 + x3 ≥ 60
（ 2） 将非标准形化为标准形式
非标准形式是
max ( min ) Z = c1x1 + c2x2 + … + cnxn
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
… …… …… …… ………… …… … …
am1x1 + am2x2 + … amnxn = bm
xk 无非负要求, xj ≤0, 其余的
变量大于等于零 。
（ 3 ）若决策变量无非负要
求
令 xk =xk`--xk``,
xk`,xk``≥0
（ 3 ）若要求决策变量 xj
≤0
可令 xj` = -- xj
xj ≥0
（ 2） 将非标准形化为标准形式
试将线性规划问题化为标准形式：
minz= -x1 + 2x2 - 3x3
x1 + x2 + x3 ≤ 7
x1 - x2 + x3 ≥ 2
-3 x1 + x2 + 2 x3 = 5
x1, x2≥0
例题
（ 2） 将非标准形化为标准形式
4 用图解法求解线性规划
线性规划的图解法就是利用解析几何
的方法来求解线性规划的问题 。 因为只有
二维几何空间最为直观, 所以图解法只能
用来求解二维线性规划问题, 也就是只有
两个决策变量的线性规划问题 。 下面我们
结合实例来讲解线性规划的图解法 。
求解线性规划问题
maxZ＝ 2x1+5x2
x1≤4
x2≤3
x1+2x2≤ 8
x1≥0,x2≥0
例题
把 x1,x2 看作上平面上点的坐标, 在第一象限
内用图形将此规划问题的约束条件和目标函数都反
映出来就是
约束条件围成了一个区域, 这个凸多边形
oabcd内的任一点的坐标都满足约束条件 。 而
凸边形外的点都不能满足约束条件, 所以凸
多边形内的任一点的坐标都是这个线性规划
问题的一个解, 我们称之为可行解 。 凸多边
形构成的可行解的全体, 称为可行解集 （ 可
行域 ） 。 满足目标函数的一个可行解的全体
z=2x1+5x2是一组平行线, 随 z的增加不断向上
平移, 当移到 b点时, 达到最大值 2x1+5x2=19。
图解法解题的基本步骤
确定可行域
确定目标函数移动的方向
确定最优解
用图解法求解如下线性规划问题
min Z = 2x1 + 2x2
x1 - x2 ≥ 1
x1 + 2x2 ≤ 0
x1, x2 ≥ 0
练习 1
用图解法求解如下线性规划问题
min Z = 2x1 + 2x2
-x1 + x2 ≥1
x1 + x2 ≤-2
x1,x2 ≥0
练习 2
5 有关线性规划问题解的概念
可行域 —— 所有可行解所构成的集合就是可行域
对于图解法，可行域就是由约束条件围成的一个凸多边形，我们
如果用 R表示可行域，则
R={x/Ax=b,x≥0}
可行解 ——同样, 在可行域上的点都满足约束条件所以, 我们称
这些点为可行解 。
x=(x1,x2…x n)T
x1 + x2 + x3 + x4+ x5 = 5
5 有关线性规划问题解的概念
基 —— 设Ａ为约束方程组中的 m× n阶系数矩阵，其秩为 m，（ 秩为 m的意思
为 m行线性无关），又 B是Ａ中 m× n非奇异子矩阵（ |B|不等于 0），则称 B是
这个线性规划问题的一个基。
?
?
?
?
?
?
?
?
?
?
?
?
mmmm
m
m
aaa
aaa
aaa
?
????
?
?
21
22221
11211
B=
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
x1,x2,…xn ≥ 0
?
?
?
?
?
?
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
?
????
?
?
21
22221
11211
这是它的系数矩阵
5 有关线性规划问题解的概念
基 —— 设Ａ为约束方程组中的 m× n阶系数矩阵，其秩为 m，
（ 秩为 m的意思为 m行线性无关），又 B是Ａ中 m× n非奇异子矩
阵（ |B|不等于 0），则称 B是这个线性规划问题的一个基。
?
?
?
?
?
?
?
?
?
?
?
?
mmmm
m
m
aaa
aaa
aaa
?
????
?
?
21
22221
11211
B=
?
?
?
?
?
?
?
?
?
?
?
?
mmmm
m
m
aaa
aaa
aaa
?
????
?
?
21
22221
11211
B=
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
=（ P1,P2,……, PM）
基变量 ——称 Pj ( j=1,2…m ) 为基向量, 与 Pj相对应的 Xj ( j =1,2…m)
称为 基变量 。
?
?
?
?
?
?
?
?
?
?
?
?
mmmm
m
m
aaa
aaa
aaa
?
????
?
?
21
22221
11211
B=
a11x1 + a12x2 + … a1nxn = b1
a21x1 + a22x2 + … a2nxn = b2
……
am1x1 + am2x2 + … amnxn = bm
=（ P1,P2,……, PM）
非基变量 ——其余变量称为 （ 对应于Ｂ ） 的 非基变量 。
基本解 —— 当取定一个基时, 令非基变量为 0,由克莱姆法则
可得对应于该基的唯一解 。 此解的非零数目不超过个 m个, 非 0
分量的数目等于 m的基本解称为非退化的, 否则称为退化的 。
a11x1 + a12x2 + … a1mx2 +…+ a1nxn = b1
a21x1 + a22x2 + … a2mx2 + … + a2nxn = b2
……
am1x1 + am2x2 + … a2mx2 + … + amnxn = bm
例如当我们取为基时
?
?
?
?
?
?
?
?
?
?
?
?
mmmm
m
m
aaa
aaa
aaa
?
????
?
?
21
22221
11211
B= 为基时
基本解 —— 当取定一个基时, 令非基变量为 0,由克莱姆法则
可得对应于该基的唯一解 。 此解的非零数目不超过个 m个, 非 0
分量的数目等于 m的基本解称为非退化的, 否则称为退化的 。
a11x1 + a12x2 + … a1mx2 +…+ a1nxn = b1
a21x1 + a22x2 + … a2mx2 +…+ a2nxn = b2
……
am1x1 + am2x2 + … a2mx2 +…+ amnxn = bm
X=(x1,x2,…,xm,0,0…0)
基本可行解 —— 满足非负条件的基本解叫基本可行解，它是基本解又是可行解。基
本可行解的数目（非零分量）不大于 m,并且都是非负的。一般地说，基本可行解
的数目小于基本解的数目，最多是相等。
a11x1 + a12x2 + … a1mx2 +… + a1nxn = b1
a21x1 + a22x2 + … a2mx2 + …+ a2nxn = b2
……
am1x1 + am2x2 + … a2mx2 +… + amnxn = bm
x1,x2,… xn ≥ 0
基本可行解
X=(x1,x2,…,xm,0,0…0)
基本可行解 —— 满足满足目标函数要求的可行解，称为线性规划问题的最优解。
a11x1 + a12x2 + … a1mx2 +… + a1nxn = b1
a21x1 + a22x2 + … a2mx2 + …+ a2nxn = b2
……
am1x1 + am2x2 + … a2mx2 +… + amnxn = bm
x1,x2,… xn ≥ 0
最优解
X=(x1,x2,…,xm,0,0…0)
max Z = c1x1 + c2x2 + … + cnxn
满足非负条件
可行解
基本
解
取定一个基
基本
可行解
最优解
满足目标函数要求
解 之 间 的 关 系
max z= x3
x1 + x2 + x3 + x4+ x5 = 4
x1 + x2 + x3 + x4- x5= 4
xi ≥ 0,i = 1,2,…,5
2 理论分支例题 1
对于约束方程组
x1 - x2 + 2 x3 = 1
x1 + x2 + x3 =1
x1,x2,x3 ≥0
系数矩阵 基 退化解 非退化解
2 理论分支例 题 2
对于约束方程组
系数矩阵 基 退化解 非退化解
x1 + x2 - x3 = 1
x1 - x2 - x3 = 2
x1,x2,x3 ≥0
6 线性规划解的性质
设 Ｄ 是 n 维欧氏空间的一个点集, 连接Ｄ中任
意两点 X,Y 的线段仍在Ｄ内, 则称 Ｄ 为凸集 。
1,凸集的 概念
X
Y
X
Y●
● ●
●
●
●
图中每个点都是由 n 维坐标表
示的，这个 n 维坐标与 向量
是一致的，而向量是与线性规
划问题的解是一致的。
=1
=u =1-u
1≥ u ≥0
x
yz
Z= x+ ( y- x) u= ( 1- u) x+ u y
任一点的表示方法
令 X Y 之间的相对长度为 1,X Z之间的长度站整个长度 的 比例为 U，
6 线性规划问题解的性质
设 集合 R是 n 维线性空间, 如果其中任意两点 X 和 Y,
如果对于任意 1 ≥ u ≥ 0,都有 ( 1 - u ) x + u y 仍然属
于 R, 则可说 R 为凸集 。
（ 1） 基本概念
凸集数学表述
顶点
设 集合 R 是一个凸集, Z 是这个集合中中的一点, 如果在
此集合中找不到两个不同的点 X 和 Y, 使 Z = ( 1- u ) x+ u
y, 1 ≥ u ≥0 成立, 则可说 Z 点为 S凸集的顶点 。
x1
x2
x1
x2
顶点的直观解释
（ 2） 线性规划问题解的性质定理
定理 1 线性规划问题的可行解集 R 为凸集 。
首先, 线性规划问题的可行解 X=(x1,x2,…,
xn)是一个 n 维向量, 它可以看成是一个由 n 个坐标
构成的点 。 线性规划问题可能有不止一个可行解,也就
是说可能有很多个这样的点, 这些点就构成了一个集
合, 很显然这个集合就是一个 n 维欧氏空间, 我们要
证明的结论, 就是这个集合是一个 凸集 。
X
Y
线性规划问题所有的解 所构成的集合
证明这个问题的基本思路
也就是，已知 X 和 Y 是线性规划问题的两个不同的解，要证明这
两个解的连线中间的任意一个点也是线性规划问题的解，也就是 ( 1- u) x+ u
y 也是一个解，也就是它也属于集合 R。
证明过程
设任意 X 和 Y ∈ R,目标是要证明对于任意 1≥ u ≥0,
Z= u X + ( 1- u) Y ∈ R
A Z = A （ u X + ( 1- u) Y）
因为 X,Y ∈ R,所以 X ≥0,Y ≥0,而且
AX = B
AY = B
= A uX + A ( 1- u) Y
= u B + ( 1- u) B = B
定理 2 凸集的顶点对应于基本可行解 。
首先, 线性规划问题的可行解 X=(x1,
x2,…,xn)是一个 n 维向量, 它可以看
成是一个由 n 个坐标构成的点 。 线性规划
问题可能有不止一个可行解,也就是说可能
有很多个这样的点, 这些点就构成了一个集
合, 上面已经证明这个集合是一个 凸集 。
此定理说, 这个凸集的顶点是基本可行
解,同样基本可行解也必是这个凸集的顶点,
首先还要理解基本可行解的含义,基本可
行解是线性规划问题系数矩阵一个特定的基
所对应的可行解,基本解首先是一个可行解,
然后它还是一个基本解,
可行域 R
必要性的证明
也就是已知线性规划问题的一个解 X 是这个线性
规划问题可行解集合 (可行域 ) R 的顶点,要证明 X 是此
线性规划问题的一个基本可行解,
简单地加以分析
在这个问题中,已经知道了 X 线性规划问题可行解
集合 (可行域 ) R 的顶点,那么 X 就肯定是一个可行解了,
关键是要如何再证明这个可行解是一个基本解了,
可行域 R
X
设 X = (x1,x2,…,xn)T,中有 K 个分量大于 0,
不失一般性可以设其前 K个分量大于 0,则
X =(x1,x2,…,xK,0,0,…,0 )T
那么约束条件 AX=B 中 AX 的就可以写成
AX=
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
?
?
?
?
21
22221
11211
?
?
?
?
?
?
x1
X2
…
xK
0
…
0
= (P1,P2,…,P k)
x1
X2
…
xK
x1
X2
…
xK
0
…
0
?
?
?
?
?
?
?
?
?
?
?
?
mn
n
n
mkmm
k
k
a
a
a
aaa
aaa
aaa
?
?
?
?
?
??
?
?
2
1
21
22221
11211
=
P1 P2 … Pk … Pn
?
?
?
?
?
?
?
?
?
?
?
?
mn
n
n
mkmm
k
k
a
a
a
aaa
aaa
aaa
?
?
?
?
?
??
?
?
2
1
21
22221
11211
=
x1
X2
…
xK
0
…
0
= x1 P1+ x2 P2+…+ xk Pk
最终整理结果就是：
那么,如果我们能够证明 P1,P2,…,Pk 是线性无关的,则由 P1,P2,…,Pk 列
向量所构成的矩阵
= x1 P1+ x2 P2+…+ xk Pk
x1
X2
…
xK
0
…
0
?
?
?
?
?
?
?
?
?
?
?
?
AX=
mn
n
n
mkmm
k
k
a
a
a
aaa
aaa
aaa
?
?
?
?
?
??
?
?
2
1
21
22221
11211
P1 P2 … Pk … Pn
中的 K个列向量是线性无关的,则说明必然存在一个 K阶子矩阵 BK是非奇异
矩阵,也就说明 BK是一个基,这样,也就证明了 X是一个基本可行解,
所以整个问题就转化为证明向量 P1,P2,…,Pk 是线性无关的, 用反证法
来证明这个问题。
?
?
?
?
?
?
?
?
?
?
?
?
mkmm
k
k
aaa
aaa
aaa
?
??
?
?
21
22221
11211
P1 P2 … Pk
假设 P1,P2,…,Pk 是线性相关的,则必然存在 K个不全为 0的数,y1,y2,…,
yk,使 y1 P1+ y2 P2+…+ yk Pk =0 成立。
= x1 P1+ x2 P2+…+ xk Pk
x1
X2
…
xK
0
…
0
?
?
?
?
?
?
?
?
?
?
?
?
AX=
mn
n
n
mkmm
k
k
a
a
a
aaa
aaa
aaa
?
?
?
?
?
??
?
?
2
1
21
22221
11211
P1 P2 … Pk … Pn
假设 是线性相关的 则必然存在 个不全为 的数,…
使 成立。
?
?
?
?
?
??
?
?
y1 P1+ y2 P2+…+ yk Pk= (P1,P2,…,P k)
y1
y2
…
yK
(P1,P2,…,P k,0,…0 )
y1
y2
…
yK
0
…
0
=
= AY
而
=0
我们再来看向量 X
X =(x1,x2,…,xK,0,0,…,0 ) T
因为 X 是可行解，所以 X中的每个分量 x1,x2,…,xK 都
必然大于 0,
那么就可以取足够小的数 ε,使 X+ εY＞ 0,X— εY＞ 0
因为 AX=B,AY=0那么
A（ X+ εY） = A X+ ε A Y =B+0=B
同理 A（ X— εY） = B
这说明 X+ εY, X— εY都分别是线性规划问题的
解。
而 X=1/2（ X+ εY） + 1/2 （ X— εY）
这说明点 X 是点（ X+ εY） 和点 （ X— εY） 的中
间点。是中间点就不是顶点。这与已知相互矛盾，说
明假设不成立。也就证明向量 P1,P2,…,Pk 是线性无关
的，进而证明了解 X 是线性规划问题的一个基本可行
解。
充分性的证明留给同志们自己课下学习
定理 3 如果可行域 R 有界, 则线性规划问题的
目标函数一定在其顶点处达到最大值 。
有界可行域 R 无界可行域 R
A B
CD
用反证法来证明这个问题, 设 X（ 1）, X（ 2） …… X（ h） 是可
行域的顶点, 而 X（ 0） 不是可行域的顶点, 但目标函数却在 X（ 0） 处达到了
最大值 。
有界可行域 R
X（ 1） X（ 2）
X（ H） ……
首先我们来证明 X（ 0） 可
用其他顶点进行线性表示 。 即
X（ 0） =u1 X（ 1） +u2 X
（ 2） +… + uh X（ h）,而且
u1 +u2 +… + uh =1
X（ 0）
首先我们来证明 X（ 0） 可用其他
顶点进行线性表示 。 即
X（ 0） =u1 X（ 1） +u2 X（ 2）
+… + uh X（ h）,而且 u1 +u2
+… + uh =1
有界可行域 R
X（ I） X（ L）
X（ Y）
……X（ 0）
我们以二维可行域为例来证明
这个问题 。
因为 X（ 0） =（ 1-u1） X（ Y） +u1 X（ K）
而 X（ K） = （ 1-u2） X（ I） + u2 X（ L）
u1
1-u1
X（ K）
u2 1-u2
最后可得 X（ 0） =（ 1-u1 ） X（ Y） + u1 （ 1-u2 ） X（ I） +
u1u2 X（ L）
可以验证各顶点前的 系数之和为 1。
我们可以将此结论进行一般推广，就可得到 首先我们来证明 X（ 0）
可用其他顶点进行线性表示。即
X（ 0） =u1 X（ 1） +u2 X（ 2） +…+ uh X（ h）,而且
u1 +u2 +…+ uh =1
有界可行域 R
X（ 1） X（ 2）
X（ H） ……
X（ 0）
在回到原来的问题上，因为 X（ 0） =u1 X（ 1） +u2 X（ 2） +…+ uh
X（ h）,而且 u1 +u2 +…+ uh =1，因此 Z ?=C X（ 0）
=C （ u1 X（ 1） +u2 X（ 2） +…+ uh X（ h） ）
=u1C X（ 1） +u2C X（ 2） +…+ uh CX（ h）
在所有顶点的目标函数值中，必然要有一个最大者，假设它是 X（ m）
≦ u1C X（ m） +u2C X（ m） +…+ uh CX（ m）
=u1C X（ m） +u2C X（ m） +…+ uh CX（ m）
=CX（ m）
最终得到 Z ?=C X（ 0） ≦ CX（ m）
这与已知是矛盾的，同时也说明了最优解必然在顶点上取得。
定理 3 如果可行域 R 有界, 则线性规划问题的
目标函数一定在其顶点处达到最大值 。
定理 1 线性规划问题的可行解集 R 为凸集 。
定理 2 凸集的顶点对应于基本可行解 。
定理 3 如果可行域 R 有界, 则线性规划问题的
目标函数一定在其顶点处达到最大值 。
定理 1 线性规划问题的可行解集 为凸集 。
定理 2 凸集的顶点对应于基本可行解 。
三个定理的回忆
以上三个定理说明线性规划问题的所有可行解组成一
个集合, 也就是可行域, 这个可行域是 凸集, 这个
有有限个顶点, 线性规划问题每一个基本可行解都对
应着可行域的一个顶点, 如果线性规划问题有最优解,
则最优解必然在顶点上达到 。
以上三个定理说明线性规划问
题的所有可行解组成一个集合, 也
就是可行域, 这个可行域是 凸集,
这个 有有限个顶点, 线性规划
问题每一个基本可行解都对应着可
行域的一个顶点, 如果线性规划问
题有最优解, 则最优解必然在顶点
上达到 。
三个定理
顶点个数 =
m
nC
1 单纯形法求解线性规划问题的基本思想
第二节 单纯形法
1
2
3
对于线性规划问题的标准
形式, 从可行域中一个基本可
行解出发, 寻求使目标函数值
有较大增加的另一个基本可行
解, 由于基本可行解个数是有
限的, 所以经过有限次迭代目
标函数值将逐步增大最终达到
最优 。
可行域 R
初始基本可行解
改进基本可行解
结束
最优？
单纯形法求解线性规划问题的基本思想
1
2
3
可行域 R
从以上分析可以看出,应用单纯形法求解线
性规划问题，需要解决的三个方面问题是,
1,初始基本可行解如何求；
2,如何判断是否最优 ；
3,如何求改进的基本可行解 。
引 例
求解如下线性规划
max Z = 2 x1 + 3 x2
2 x1 + x2 ≤2
X1 + 3 x2 ≤3
X1,x2 ≥0
（ 1） 将上例化为标准形式
max Z = 2 x1 + 3 x2
2 x1 + x2 +x3 =2
X1 + 3 x2 +x4 =3
X1,x2,x3,x4 ≥0
第一步 首先要求出其基本可行解来
2、找初始基本可行解
约束方程的系数矩阵为,
),,,(
1031
0112
4321 PPPPA ??
?
?
??
??
此系数矩阵 A 中的两行很显然是线性独立的，所以它的秩为 2，
我们可以任意地组合其列向量,从而得到一个基，并求基本解。
例如，列向量 P3,P4是线性无关的,所以 P3,P4组合为
矩阵可作为一个基。
),(
10
01
43 PPB ??
?
?
??
??
),(
10
01
43 PPB ??
?
?
??
??
根据这个基，对照原约束方程组，就可以求出其对应的基本可行解来
X（ 1） =（ 0,0,2,3），
将这个基本可行解代入目标函数表达式,max Z = 2 x1 + 3 x2 中，
得到目标函数值为 0，
从目标函数的表达式中，直观地看，增加非基变量 x2的值，可以是目
标函数得到较大的增长，所以 应该让非基变量 x2变为基变量（进基） x1,
仍为非基变量。即令 x1=0,同时此例中不能超过二个基变量（因为约束条
件的系数矩阵的秩为 2，最优解肯定是二为的），还得从 x3,x4中换出一个做
非基变量（离基）并需保证非负条件，
（ 2）判断基本可行解是否是最优解
如果选 x 3 变量出基（也就是使 x 3 变量变为非基变量，非基变量的值
为 0），根据（ 1）式得到 x 2 =2，将 x 2 =2 代入（ 2）式得到,x4 =--3，
这就不满足了第三个约束条件。所以不能选择 x 3 作为出基变量。
同样方法，可以验证，选择 x4 变量作为出基变量是可以的。
（ 3） 迭代（ 也就是求改进的基本可行解 ）
2 x1 + x2 +x3 = 2 ……… …（ 1）
X1 + 3 x2 +x4 = 3…… … …（ 2）
X1,x2,x3,x4 ≥0
以上选择出基变量的方法可用数学的方法归纳为 min {2/1,3/3},也就
是,
min {b1/a1j,b2/a2j,b3/a3j,…,bm/amj }
在确定了 x 2 进基,x 4 出基以后，为了求得以 x2,x3 为基变量的上述新的基本可行解
x (1) 及目标值 z (x (1)),只要对原约束方程进行一次初等变换，即把方程组中第二等式里
x2 的系数化为 1 也就是以第二等式里 x2 的系数化为 1,也就是以第二等式中 x2 的系数为
主元进行一次高斯消元，得到
2 x1 + x2 +x3 =2
X1 + 3 x2 +x4 = 3
X1,x2,x3,x4 ≥0
也就是以第二个等式中 x2 的系数为主元进行一次高斯消元，得到
1/3x1+x2 +1/3x4 = 1
5/3x1 +x3- 1/3x4 = 1
1/3x1+x2 + 1/3x4 = 1 …… ……… …（ 3）
5/3x1 +x3 -1/3x4 = 1 … ……… …… （ 4）
将上述约束条件，变成关于基变量的表达式：
x2=1-1/3x1--1/3x4≥0
x3=1-5/3x1+1/3x4≥0
将这个表达式代入目标函数得到,
Z=3+x1-x4
判断是否是最优解
迭代
2 单纯形法的一般原理
（ 1）从线性规划的系数矩阵能直接观察到。
x1 + 3 x4 + 2 x5 = 360
x2 + 4 x4 + 5 x5 = 200
x3 + 2 x4 + 7 x5 = 300
x1,x2，, x3 ≥ 0
MAX Z ＝ 7 x1 + 12 x2
B=（ P1,P2,P3）
?
?
?
?
?
?
?
?
?
?
100
010
001=
1、初始基本可行解的确定
由以上的引例我们可以看出，对于一个线性规划的问题，为了确定初始基本可行解，首先
要找到一个初始可行基，这个可行基 最好 是一个单位矩阵，主要有三种方法：
x1 + 3 x4 + 2 x5 = 360
x2 + 4 x4 + 5 x5 = 200
x3 + 2 x4 + 7 x5 = 300
x1,x2，, x3 ≥ 0
MAX Z ＝ 7 x1 + 12 x2
x1 + 3 x4 + 2 x5 = 360
x2 + 4 x4 + 5 x5 = 200
x3 + 2 x4 + 7 x5 = 300
x1,x2，, x3 ≥ 0
?
?
?
?
?
?
?
?
?
?
100
010
001
B=
?
?
?
?
?
?
?
?
?
?
001
100
010
B=
不能直接看出，要调整顺序
（ 2）对于约束条件是, ≤” 形式的不等式的情况，经过加非负的松弛
变量可以等到一个单位矩阵。
MAX Z ＝ 7 x1 + 12 x2
9 x1 + 4 x2 ≤ 360
4 x1 + 5 x2 ≤ 200
3 x1 + 10 x2 ≤ 300
x1,x2，, x3 ≥ 0
MAX Z ＝ 7 x1 + 12 x2
9 x1 + 4 x2 + x3 = 360
4 x1 + 5 x2 + x4 = 200
3 x1 + 10 x2 + x5 = 300
x1,x2，, x3, x4, x5 ≥ 0
?
?
?
?
?
?
?
?
?
?
100
010
001B=
（ 3）对于约束条件是,≥”的形式，采用人工造基的方法减去
一个非负的松弛变量，再加上一个非负的人工变量总能得到一个单
位矩阵。
x1 + 3 x4 + 2 x5 = 360
x2 + 4 x4 + 5 x5 = 200
2x3 + 2 x4 + 7 x5 ≥ 300
x1,x2，, x3 ≥ 0
MAX Z ＝ 7 x1 + 12 x2
黑
板
演
示
找到了初始基本可行基，也就相应地找到了初始
基本可行解。然后就要判断这个解是否是最优解。
判断最优时，目标函数必须化成关于非基变量的
函数，如果是最优解，停止；反之继续选代。
判断最优的标准，就是在目标函数中所有非基变
量的系数均为负，如果系数大于零则目标函数还可能
增加，因此需要将一个非基变量进基，同时相应地要
选择另一个基变量离基。
2、最优性检验
最优性检验的准则
x1 + … + a1m+1xm+1 +… + a1nxn = b1
x2 + … + a2m+1xm+1 + … + a2nxn = b2
……
xm + ammxm+1 + … + amnxn = bm
x1,x2,… xn ≥ 0
max Z = c1x1 + c2x2 + … + cnxn
x1 = b1 --( a1m+1xm+1 + …+ a1nxn )
x2 = b2 --( a2m+1xm+1 + …+ a2nxn )
……
xm = bm --( amm+1xm+1 +… + amnxn )
Z = c1x1 + c2x2 + … + cmxm + cm+1xm + 1+ … + cnxn
Z =( c1 b1 + c2b2 + … + cmbm ) + ? ?
?? ?
?
n
mj
m
i
ijiij accx
1 1
)(
Z =Z((X0 )) +
nnmmmm xxx ??? ??? ???? ?2211
?
?
?
m
i
ijii acc
1
)(
令 =
j?
( j=m+1,m+2,…,n )
接 3
3、迭代（基本可行解的转换）
通过检验数就可以确定出哪个非基变量应该
变为基变量（这叫做进基），再根据最小比值原
则就可以确定出哪个基变量应该变为非基变量
（这叫做出基）。
有了新的基变量就有了新的基本可行解，新的
基本可行解可通过高斯初等变换的方法求得。通
过高斯变换将基变量对应的列向量变换为单位列
向量，就能直接看出基本可行解 。
3 利用单纯形表解线性规划
1、结合实例讲解利用单纯形表解线性规划
max z = 2x1-x2+x3
3x1+x2+x3 ≤60
x1-x2+2x3 ≤10
x1+x2-x3 ≤20
x1,x2,x3 ≥0
将它化为标准形式
maxz=2x1-x2+x3
3x1+x2+x3+x4 = 60
x1 -x2+2x3 +x5 = 10
x1 +x2 -x3 +x6 = 20
x1,x2,x3,x4,x5,x6≥0
CB xB 2 -1 1 0 0 0 B
x1 x2 x3 x4 x5 x6
0 x4 3 1 1 1 0 0 60
0 x5 [1] –1 2 0 1 0 20
0 x6 1 1 -1 0 0 1 10
λj 2 -1 1 0 0 0
maxz=2x1-x2+x3
3x1+x2+x3+x4 = 60
x1 -x2+2x3 +x5 = 10
x1 +x2 -x3 +x6 = 20
x1,x2,x3,x4,x5,x6≥0
4、人工变量求可行基的方法
例题
max z = 3x1 - x2 - x3
x1- 2x2+ x3 ≤ 11
-4 x1 +x2+2x3 ≥3
2 x1 - x3 = -1
x 1,x 2,x 3 ≥0
首先，将它变为标准型
Max z =3x1-x2-x3
x1 - 2x2 + x3 + x4 = 11
-4x1 +x2+2x3 –x5 = 3
- 2x1 + x3 = 1
x1,x2,x3,x4,x5 ≥0
1 大 M 法
2 两阶段法
21 3m a x xxZ ??
?
?
?
?
?
??
??
??
0,0
42
8
21
21
21
xx
xx
xx
练 习 1
213m i n xxZ ??
?
?
?
?
?
??
??
??
0,0
42
8
21
21
21
xx
xx
xx
练 习 2
5、在实际求解中会遇到的问题及解决的办法
max z =x1+x2
x1 - 2x2 ≤2
x1 + x2 ≤2
x1,x2≥0
例题
max z =x1+x2
x1 - 2x2 ≤2
x1 + x2 ≤2
x1,x2≥0
首先要将它化为标准型
max z = x1+ x2
x1 - 2x2 +x3 = 2
x1 + x2 +x4 = 2
x1,x2≥0
（ 1）非基变量的检验数为 0；
在这种情况下最优解不唯一，而最优值不能改进了。
（ 2）检验数相同；
可以任选其中一个非基变量进基，选择的不同仅引起选代次数的
不同。
（ 3）最小比值相同；
进一步选代不一定会立即引起目标函数的改变，只要检验数仍为正，
则最终能够得到最优值
（ 4）退化和循环。
5、在实际求解中会遇到的问题及解决的办法
CB xB 1 1 0 0 B
x1 x2 x3 x4 x5 x6
0 x4 3 1 1 1 0 0 60
0 x5 [1] –1 2 0 1 0 20
λj 2 -1 1 0 0 0
