线性规划的基本定理ppt课件.ppt

文档介绍：
1标准形式及图解法

1
可编辑课件
矩阵表示

其中A是mn矩阵，c是n维行向量， b是m维列向量。
评注：为计算需要，一般假设b，可在方程两端乘以(-1)即可化为非负。
2
可编辑课件

任意非标准形式均可划为标准形式，如
引入松弛变量xn+1， xn+2 ,… xn+m.
3
可编辑课件
则有

4
可编辑课件
若某变量xj无非负限制，则引入xj = xj ' - xj ' ' ，
xj ', xj ' ' 0
若有上下界限制，比如xj lj, 令xj ' = xj - lj, ,
有 xj ' 0

5
可编辑课件
. 图解法
当自变量个数少于3时，我们可以用较简便的
方法求解。

Min 3x +
. 2x + 4y  40
3x + 2y  50
x, y  0.
例如，考虑食谱问题
6
可编辑课件

30
10
40
20
50
10
20
30
40
50
y
x
0
3x +
2x+4y40
3x+2y50
(15, )
可行区域的极点：
(0, 25)
(15, ) 最优解
(20, 0)
7
可编辑课件
2 基本性质
线性规划的可行域

定理 线性规划的可行域是凸集.
最优极点
观察上例，最优解在极点(15,)达到，我们
现在来证明这一事实:线性规划若存在最优解,
则最优解一定可在某极点上达到.
8
可编辑课件
考察线性规划的标准形式(3. 2)

根据表示定理，任意可行点x可表示为
9
可编辑课件
把x的表达式代入(3. 2),得等价的线性规划:

10
可编辑课件