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

文档介绍：矩阵表示

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

任意非标准形式均可划为标准形式，如
引入松弛变量xn+1， xn+2 ,… xn+m.
第2页/共32页
则有

第3页/共32页
若某变量xj无非负限制，则引入xj = xj ' - xj ' ' ，
xj ', xj ' ' 0
若有上下界限制，比如xj lj, 令xj ' = xj - lj, ,
有 xj ' 0

第4页/共32页
. 图解法
当自变量个数少于3时，我们可以用较简便的
方法求解。

Min 3x +
. 2x + 4y  40
3x + 2y  50
x, y  0.
例如，考虑食谱问题
第5页/共32页

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)
第6页/共32页
2 基本性质
线性规划的可行域

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

根据表示定理，任意可行点x可表示为
第8页/共32页
把x的表达式代入(3. 2),得等价的线性规划:

第9页/共32页
于是,问题简化成

第10页/共32页