第二章单纯形法(1基本思路和原理)

a 11 a 1 m P B , , P 1 m a m 1 a mm
Ｂ中的每一个列向量Ｐj（j＝１，…，m）称为基向量，与基向 量Ｐj对应的变量xj称为基变量。线性规划中除了基变量以外的变 量称为非基变量。
§5.1 单纯形法的基本思路和原理
基： 设Ａ为约束方程组（Ｆ）的m×n阶系数矩阵，（设n＞m）， 其秩为m，Ｂ是矩阵Ａ中的一个m×m的满秩子矩阵，称Ｂ 是线性规划问题的一个基．不失一般性，设
a 11 a 1 m P B , , P 1 m a m 1 a mm
Ｂ中的每一个列向量Ｐj（j＝１，…，m）称为基向量，与基向 量Ｐj对应的变量xj称为基变量。线性规划中除了基变量以外的变 量称为非基变量。
1 B2 0 0 0 1 0 0 0 1
令这个基的非基变量 x1, s2 为零, 这时约束方程就变为基变量 即: 0 s 1 300 1 1 1 0 0 0 300 s 2 1 0 1 0 1 400 s 2 400 0 1 0 0 1 s2 250 s 250 s 3 3 求解,即可得到基变量的唯一一组解: s1=300 , s2=-400 , s3=250 加上非基变量: x1= 0, x2 = 0, 得到此线性规划的一个基解.
x1 1 1 1 0 0 x2 300 s 2 1 0 1 0 400 1 0 1 0 0 1 s2 250 s 3
1 1 B3 1 0 1 0
第二章 单纯形法
Singlex Method
第二章 单纯形法
对于只有两个决策变量的线性规划问 题，可以在平面直角坐标系上作图表 我们在第三章所介绍的线性规划问题的计 示线性规划问题的有关概念，并求解 .
算机解法就是基于单纯形法编程来解决可 以含有上千个决策变量的及上千个约束条 由美国数学家丹捷格 件的复杂的线性规划问题。 (G.B.Dantzig)提出的，得到最
T，称X为线性规划问 基变量取0的值有 X x , , x , 0 , , 0 b 1 m
题的基解。
§5.1 单纯形法的基本思路和原理
线性规划问题
max z n a ij x j1 x j 0

j
n
c
j1
j
x
j
(i=1,…，m)
(j=1,…，n)
最优解： 使目标函数（Ｅ）达到最大值的可行解称为最优解．

j
n
c
j1
j
x
j
(i=1,…，m)
(j=1,…，n)
(Ｅ) (Ｆ) (Ｇ)
Hale Waihona Puke Baidu
b
i
§5.1 单纯形法的基本思路和原理
基： 设Ａ为约束方程组（Ｆ）的m×n阶系数矩阵，（设n＞m）， 其秩为m，Ｂ是矩阵Ａ中的一个m×m的满秩子矩阵，称Ｂ 是线性规划问题的一个基．不失一般性，设
1 0 0
0 0 1
都是该线性规划的一个基。 这些基都是由3个线性无关的系数列向量组成的,对应的基变量
分别为 x1 , x2 , s1 ; s1, s2, s3; x2 ,s1,s3。
§5.1 单纯形法的基本思路和原理
基解： 在约束方程组（E）中，令所有的非基变量：
x x x 0 m 1 m 2 n
1 1 B3 1 0 1 0
0 0 1
令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 即: 0 x 2 s1 300 1 1 1 0 0 x2 300 2 1 0 1 0 s1 400 x 2 400 0 1 0 0 1 0 x s 250 250 s 2 3 3 求解,即可得到基变量的唯一一组解: x2= 400 , s1= -100 , s3= -150 加上非基变量: x1= 0, s2 = 0, 得到此线性规划的一个基解.

j
n
c
j1
j
x
j
(i=1,…，m)
(j=1,…，n)
(Ｅ) (Ｆ) (Ｇ)
b
i
， X x , , x 1 n
T
称为线性规划问题的可行解．全部可行解的集合称为可行域．
§5.1 单纯形法的基本思路和原理
线性规划问题
max z n a ij x j1 x j 0
的约束方程:
x1= 0, x2= 400, s1= -100, s2= 0, s3= -150,
矩阵方程 AX = b
我们找到A 的一个基:
x1 1 1 1 0 0 x2 300 s 2 1 0 1 0 400 1 0 1 0 0 1 s2 250 s 3
的约束方程:
x1=0, x2=0, s1=300
s2=400
s3=250
§5.1 单纯形法的基本思路和原理
基解： 在约束方程组（E）中，令所有的非基变量：
x x x 0 m 1 m 2 n
又因为有
B 0 ，根据克莱姆法则，由m个约束方程可以解
T 出m个基变量的唯一解 X 。将这个解加上非 x , , x b 1 m
1 1 B3 1 0 1 0
0 0 1
均为基
可行基
不是可行基
§5.1 单纯形法的基本思路和原理
由于在这个基解中s1＝－100，s3＝－150，不满足该线 性规划最后一个变量非负的约束条件，显然不是此线性规划
的可行解，一个基解可以是可行解，也可以是非可行解，它
们之间的主要区别在于其所有变量的解是否满足非负的条件。
的约束方程:
s2=0
s3=-150
矩阵方程 AX = b
我们找到A 的一个基:
x1 1 1 1 0 0 x2 300 s 2 1 0 1 0 400 1 0 1 0 0 1 s2 250 s 3
0 0 1
令这个基的非基变量 x1, s2 为零, 这时约束方程就变为基变量 即: 0 x 2 s1 300 1 1 1 0 0 x2 300 x1=0, 2 1 0 1 0 s1 400 x 2 400 0 1 0 0 1 0 x s 250 250 x2=400 s 2 3 3 求解,即可得到基变量的唯一一组解: x2= 400 , s1= -100 , s3= -150 s1=-100 加上非基变量: x1= 0, s2 = 0, 得到此线性规划的一个基解.
1 B2 0 0 0 1 0 0 0 1
令这个基的非基变量 x1, x2 为零, 这时约束方程就变为基变量 即: 0 s 1 300 1 1 1 0 0 0 300 s 2 1 0 1 0 1 400 s 2 400 0 1 0 0 1 s2 250 s 250 s 3 3 求解,即可得到基变量的唯一一组解: s1=300 , s2=-400 , s3=250 加上非基变量: x1= 0, x2 = 0, 得到此线性规划的一个基解.
(Ｅ) (Ｆ) (Ｇ)
b
i
基可行解：
满足变量非负约束条件 ( G ) 的基解称为基可行解。
可行基： 对应于基可行解的基称为可行基。
矩阵方程 AX = b
我们找到A 的一个基:
x1 1 1 1 0 0 x2 300 s 2 1 0 1 0 400 1 0 1 0 0 1 s2 250 s 3
应的变量s1, s2, s3是基变量。除了基变量以外的变量 x1, x2是非基变量。
A (p ,p ,p ,p ,p ) 2101 0 . 1 2 3 4 5 Ｂ中的每一个列向量p3, p4, p5 是基向量，与其对 0 1 0 0 1
§5.1 单纯形法的基本思路和原理
标准形式为: 目标函数：max z = 50x1+100x2+0s1+0s2+0s3 约束条件： x1 + x2 +s1 = 300 2x1 + x2 +s 2 = 400 x2 +s3 = 250 x1, x2, s1, s2, s3≥0。 这是由三个五元线性方程组成的方程组，它的系数矩阵为:
11100 A (p ,p ,p ,p ,p ) 2101 0 . 1 2 3 4 5 0 1 0 0 1
的约束方程:
x1=0, x2=0, s1=300
s2=400
s3=250
x1=0, x2=0, s1=300 s2=400 s3=250
x1= 0, x2= 400, s1= -100, s2= 0, s3= -150, 均为基解
基可行解
不是基可行解
1 B2 0 0
0 1 0
0 0 1
§5.1 单纯形法的基本思路和原理
定理:
线性规划问题的基可行解 X 对应线性规划问题可行域
的顶点.
在这里，可行域的顶点已不再像图解法中那样直接可见
了。在单纯形法中的可行域的顶点叫做基可行解，第一 个找到的可行域的顶点叫做初始基可行解。
§5.1 单纯形法的基本思路和原理
例：找出下述线性规划问题的全部基解，指出其中 的基可行解，并确定最优解：
§5.1 单纯形法的基本思路和原理
可以看到 s1, s2, s3的系数列向量
1 p3 0 0 .
0 p4 1 0
.
0 p5 0 1
.
是线性独立的,这些向量构成一个基
1 0 0 这是由三个五元线性方程组成的方程组，它的系数矩阵为 : B p3, p4, p5 0 1 0 11 100 0 0 1
111 0 0 A (p ,p ,p ,p ,p ) 210 1 0 . 1 2 3 4 5 0 1 0 0 1
在此例题中：
1 2 0 1 1 1 1 0 0
1 0 0 0 1 0 0 0 1
1 1 1
广泛应用的线性规划的代数算法
－－单纯形法，这恐怕是在运筹
学发展史上最辉煌的一笔。
第五章 单纯形法
• 5.1 单纯形法的基本思路和原理
§5.1 单纯形法的基本思路和原理
线性规划问题
max z n a ij x j1 x j 0
可行解： 满足上述约束条件（Ｆ），（Ｇ）的解
又因为有
B 0 ，根据克莱姆法则，由m个约束方程可以解
T 出m个基变量的唯一解 X 。将这个解加上非 x , , x b 1 m
T，称X为线性规划问 基变量取0的值有 X x , , x , 0 , , 0 b 1 m
题的基解。
矩阵方程 AX = b
我们找到A 的一个基: