线性规划课件.ppt

文档介绍：关于线性规划
第一页，共101页幻灯片
*
决策变量：x1, ..., xn表示要寻求的方案，每一组值就是一个方案；
约束条件：线性等式或不等式
目标函数：Z=ƒ(x1 … xn) 线性式，求Z极大或极小
线性规划模型特
Z=-X1+ X2, Z=0
2
3
1
解：(1)、确定可行域
X1 0 X1 =0 (纵)
X2 0 X2=0 (横)
0
1
2
3
X2
第十三页，共101页幻灯片
*
2
3
1
0
1
2
3
X2
A1
B
C
4
2 X1-X2 =-2
X1-2X2 =2
X1+X2 =5
(1,4)
若目标函数改为
min Z=4X1-2X2
2 X1-X2  -2
X1-2X2  2
X1+X2  5
X1 , X2 0
A2
A3
A4
O
第十四页，共101页幻灯片
*
最优解：A1A2线段上所有的点，最优值为-4
X(1)=(0, 2)T , X(2)=(1,4)T
X= X(1)+(1-) X(2) (0   1)
X1 =1- 
X2=2+4 (1-  )=4-2 
(0   1)
min Z=4X1-2X2 =-4
第十五页，共101页幻灯片
*
2
3
1
0
1
2
3
X2
A1
B
C
4
2 X1-X2 =-2
X1-2X2 =2
X1+X2 =5
(1,4)
A2
A3
A4
O
可行域：由约束平面围起来的凸多边形区域，可行域内的每一个点代表一 个可行解。
最优解：总是在可行域的边界上，一般由可行域的顶点表示。
有效与无效(紧与松)约束：与最优解相关的约束为有效(紧)约束。
图解法的观察【1】
第十六页，共101页幻灯片
*
无界
无有限最优解
例2、 maxZ=2X1+ 4X2
2X1+X2 8
-2X1+X2  2
X1 , X2 0
Z=0
2X1+ X2=8
-2X1+ X2=2
8
2
4
6
X2
4
0
X1
第十七页，共101页幻灯片
*
例3、 maxZ=3X1+2X2
-X1 -X2 1
X1 , X2 0
无解
无可行解
-1
X2
-1
X1
0
-X1-X2 =1
第十八页，共101页幻灯片
*
如果可行域为空集，线性规划问题无可行解；
如果目标函数线可以无限制地在可行域内向改善的方向移动，线性规划问题无界；
线性规划问题可能存在无穷多个最优解。
图解法的观察（2）
唯一最优解
无穷多最优解
无有限最优解
无可行解
有最优解
无最优解
总结
第十九页，共101页幻灯片
*
两个变量的LP问题的解：
(1)、可行域为凸多边形。
(2)、若有最优解，定可在可行域的顶点得到。
X(1)
X(2)
凸多边形
凹多边形
X(1)
X(2)
第二十页，共101页幻灯片
*

min Z=CTX
AX =b
X0
A m×n 满秩
X = (x1… xn)T
D={X∈Rn| AX =b, X0}≠Φ
第二十一页，共101页幻灯片
*
凸集没有凹陷部分，该集合内任取
两点连线上的任何点都应该在集合内。
定义1：
x
S
y
凸集：S是n维欧氏空间的一个集合,如果对任意
x, yS, 0≤ ≤ 1, 有x + (1 - ) y S。
第二十二页，共101页幻灯片
*
定理1 D={X∈Rn| AX =b, X0}是凸集。
第二十三页，共101页幻灯片
*
定义2： 给定b∈R1,及非零向量aT∈Rn称集合
H ={X∈Rn| aTX =b}是Rn中的一个超平面.
H+ ={X∈Rn| aTX  b}
H- ={X∈Rn| aTX  b}
H+，H-和超平面H都是凸集.
H+和H-是由超平面H产生的两个闭的半空间.
结论：线性规划的可行域是凸集。
第二十四页，共101页幻灯片
*
定义3：凸集
凸集S的顶点X：—S是一个凸集，X∈S，
对任意X(1), X(2)∈S，X(1)≠ X(2) ,和任