的方案，然后不断去尝试其他的定点，判断其是
否最优，直到找到最优的方案。
School of Information Management ,CCNU
2
《运筹学》
2.1 单纯形法的基本思路：
从可行域中某一个顶点开始，判断此顶点是否是 最优解，如不是,则再找另一个使得其目标函数值更 优的顶点，称之为迭代，再判断此点是否是最优解。
Nx N
11
《运筹学》
B -1 Bx B + B -1 Nx N = B -1b Þ x B + B -1 Nx N = B -1b
Þ x B = B -1b - B -1 Nx N
令xN = 0
x B1 x B2
Bb-11 b1 = Bb-21b2
x Bm
Bb-m1 b m
B -1 Bx B = Ex B = x B
定理1
D = { x Î R n | Ax = b , x ³ 0 } 是 凸 集 .
证 任 取 x , y Î D ， w = l x + (1 - l ) y ， 其 中
l Î [0 ,1]. 由于 x ³ 0， y ³ 0，故w ³ 0. 又 Ax = b ， Ay = b ， 故
Aw = l Ax + (1 - l ) Ay = b
顶 点
School of Information Management ,CCNU
8
《运筹学》
从图解法的几何直观容易得到下面两个重要结论：
⑴．线性规划的可行区域D是若干个半平面的 交集， 它形成了一个有界的或无界的凸 多边形.
⑵．对于给定的线性规划问题，如果它有最优 解，最优解总可以在D的某个顶点上达到.
B -1 Nx N
School of Information Management ,CCNU
12
《运筹学》
xB = B -1b xN = 0
é B -1bù x=ê ú
êë 0 úû
基本解
x B1 x B2
若 B -1b ³ 0 则 x ³ 0
x 基本可行解 B 可行基
B -1b1 B -1b2
即wÎ D.
School of Information Management ,CCNU
6
《运筹学》
定理2 任意多个凸集的交还是凸集. 证 如果 x 和 y 是 I Si中的两个点，则 x 和 y 必
属 于 每 一 个 Si ，因 此 它 们 的 凸 组 合 也 在 每 一 个 Si里，从而也在I Si里.
bm
School of Information Management ,CCNU
10
《运筹学》
A = (B,N )
x
=
çæ çè
xB xN
÷ö ÷ø
Ax = b
(B
N
)ççèæ
xB xN
÷ö ÷ø
=
b
Þ Bx B + Nx N = b
b1 b2 =
bm
Bx B
School of Information Management ,CCNU
School of Information Management ,CCNU
7
《运筹学》
定义2
设 S 为 凸 集 ， x Î S .若 对 任 何 y Î S ，z Î S ， y ¹ z，以及任何0 < l < 1，都有
x ¹ ly + (1 - l )z
则 称 x 为 凸 集 S 的 一 个 顶 点 (极 点 ).
中与之对应的 m 个分量称为基变量，其余的分
量 称 为 非 基 变 量 .令 所 有 的 非 基 变 量 取 值 为 零 ，
é xB ù é B -1bù
得到的解 x = ê ú = ê
ú，称为相应于 B 的
êë x N úû êë 0 úû
基本
解
.当
B
-1b
³
0 时
，称
基本
解
x
为基本可行
解，这时对应的基B 称为可行基.
School of Information Management ,CCNU
9
《运筹学》
(2)基本可行解及线性规划基本定理
Ax = b 秩 ( A ) = m , m < n a11 x1 a12 x 2 a 21 x1
am1 x1 am 2 x2
a1n xn
b1
a2n xn =
b2
a mn x n
考虑标准形式的LP问题
m ax cTx
s
.t
.
ìï A
í ïî
x
x ≥
= 0
b
x Î R n ,c Î R n ,b Î R m , A Î R m´n
设 D = { x Î R n | Ax = b , x ³ 0} ¹ f
秩(A) = m,m < n
School of Information Management ,CCNU
第二章 单 纯 形 法
2.3 单纯形法的基本证明
School of Information Management ,CCNU
1
《运筹学》
n 由于图解方法只能解决两个决策变量的线性规划 问题，因此对于多个决策变量的线性规划问题就
无法解决； n 图解法作图难以规范； n 图解法中：总是从某个顶点开始，给出一个初始
直到找到一个顶点为其最优解，就是使得其目标函数
值最优的解，或者能判断出线性规划问题无最优解为
止。
由此可见，这里必须要解决三个问题
1）找到一个初始可行解. 2）如何判断是否是最优解 3）如果不是，如何改进（迭代）
School of Information Management ,CCNU
3
《运筹学》
线性规划问题的可行域
4
《运筹学》
定义1
设 S Ì R n 是n 维欧氏空间中的一个点集，若对任 何 x Î S , y Î S 与任何l Î [0,1]，都有
lx + (1 - l ) y Î S
就称S 是一个凸集.
凸集
极点
School of Information Management ,CCNU
凸集
5
《运筹学》
不是凸集
School of Information Management ,CCNU
14
《运筹学》
定理3
可行解 x 是基本可行解的充要条件是它的正分量所
对应的 A 中列向量线性无关.
证：不妨设 x的前 k 个分量为正分量，即
x = ( x1 ,Lformation Management ,CCNU
13
《运筹学》
B -1bm
定义3
设 B 是 秩 为 m 的 约 束 矩 阵 A Î R m´n 中 的 一 个
m 阶 满 秩 子 方 阵 ， 则 称B 为 一 个 基 (或 基 阵 ). B
中m个线性无关的列向量称为基向量，变量 x