上页 下页 返回
线性规划解的关系图
最优解？
非可行解
可行解
基解
基可行解
上页 下页 返回
• 例：求基解、基可行解、最优解。
max
z 2 x1 3 x 2 x 3 x3 5 x1 x 2x x 4 10 1 2 x2 x5 4 xi 0, i 1,2,,...,5
上页
下页
返回
图解法
9— 8—
x2
•可行域为凸集 •目标函数不同时 等值线的斜率不同 •最优解在顶点产生
4x1 16
7—
6— 5—
目标函数等 值线的斜率 C
4 —B
3— 2— 1—
D
最优解 4 x2 16 x1 + 2x2 8
| 6 | 7 | 8 | 9
可行域
| 1 | 2 | 3 | 4
上页 下页 返回
• 引理：可行解X为基可行解 X的正分量对应的列向量线性无关 • 定理2：线性规划问题的基可性解X 对应于可行域D的顶点。 证明：反证法。分两步。
• 定理3：若可行域有界，线性规划 问题的目标函数一定可以在 其可行域的顶点上达到最优。
上页 下页 返回
几点结论：
• 线性规划问题的可行域是凸集。 • 基可行解与可行域的顶点一一对 应，可行域有有限多个顶点。 • 最优解必在顶点上得到。
A
0பைடு நூலகம்
E
| 5
x1 下页 返回
上页
图解法
9— 8—
x2
•可行域为凸集 •目标函数不同时 等值线的斜率不同 •最优解在顶点产生
X X (1) (1 ) X ( 2) 则X为顶点.
(0 1)
凸集
上页 下页 返回
凸组合：
设X（1) ,..., X ( k )是n维向量空间中的k个点, 若存在1 ,..., k , 且0 i 1, i 1,2,..., k ,

i 1
k
i
1,
1
n=2，k=3
( 2)
使X 1 X 2 X 则X为X
(1)
... k X
(k )
,..., X
(k )
的凸组合.
X
上页
下页
返回
基本定理
定理1: 若线性规划问题存在可行域, 则其可行域:
D X AX b, X 0)
是凸集. (1) ( 2) (1) ( 2) 证明: 设：X D, X D, X X
第三节 线性规划解的性质
线性规划解的概念 线性规划问题的几何意义 （单纯形法原理）
上页
下页 继续
返回
线性规划问题解的概念
标准型
max Z CX AX b X 0
可行解:满足AX=b, X>=0的解X称为线性 规划问题的可行解。 最优解：使Z=CX达到最大值的可行解称 为最优解。
上页 下页 返回
基：若B是矩阵A中m×m阶非奇异 子矩阵（B≠0），则B是线性规划 问题的一个基。不妨设：
a11 ,..., a1m B .............. ( P 1 ,..., P m) a ,..., a mm m1
Pj , j=1，2，…,m —— 基向量。 X j ，j=1，2，…,m —— 基变量。 X j , j=m+1,…,n —— 非基变量。
上页 下页 返回
线性规划问题的几何意义
基本概念
对 X K， X 连线上的一切点
（ 1） （ 1） （ 2）
设 k是 n维欧氏空间的一点集， 凸集： K
αX （ 1 α ） X K， （ 0 α 1 ），则 K为凸集。
（ 2）
上页
下页
返回
顶点:若K是凸集，X∈K；若X不能用
不同的两点 X (1) K和X ( 2) K 的线性组合表示为：
是否基 可行解
Y Y Y N N Y N Y
下页
返回
：求基解、基可行解、最优解 。 练习：
max z 2 x1 3 x2 0 x3 0 x4 0 x5 8 x1 2 x2 x3 4 x x4 16 1 4 x2 x5 12 x1 , x2 , x3 , x4 , x5 0 1 2 1 0 0 A 4 0 0 1 0 A的秩是 3. 0 4 0 0 1
上页 下页 返回
max Z CX
求解 AX b
X 0 a1m a11 ... x1 ... ... xm a a m1 mm
a1n b1 a1m 1 xm 1 ... ... xn ... ... b a a m mm1 mn
则有：AX AX
(1)
b, X b, X
(1)
0, 0
( 2)
( 2)
上页
下页
返回
令X为X 和X 连线上的任意一点，则： X X (1) (1 ) X ( 2 ) (0 1) 显然，X 0
只要验证X在D中即可 将X代入约束条件，有：
(1)
( 2)
AX A(X (1) (1 ) X ( 2 ) ) AX (1) (1 ) AX ( 2 ) b (1 )b b 因此，X D, D是凸集。
上页 下页 返回
基变量 X B ( x1 , x2 ...xm )T 令
xm1 xm2 ... xn 0
' 1 ' 2 ' m
可求出：
X (b , b ,...b ,0,0,...,0)T
基解：称上面求出的X解为基解。 基可行解：非负的基解X称为基可行解 可行基：对应基可行解的基称为可行基
上页
下页
返回
解：
x1 x 2 x 3 x 4 x 5
1 2 3 4 5 6 7 8 0 0 0 4 5 0 0 5 10 0 5 2.5 5 4 2 4 5 5 0 5 -5 0 0 3 10 4 2 0 5 4 0 -1 0 4 0 1.5 -3 0 0 0
最优解
上页
z
5 17 10 20 15 17.5 22 19