教案4-单纯形法省公开课一等奖全国示范课微课金奖PPT课件.pptx

该【教案4-单纯形法省公开课一等奖全国示范课微课金奖PPT课件 】是由【guwutang】上传分享，文档一共【30】页，该文档可以免费在线阅读，需要了解更多关于【教案4-单纯形法省公开课一等奖全国示范课微课金奖PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。本节重点：
单纯形表（尤其是检验数行）
单纯形法计算步骤
大M法
两阶段法
解存在情况判别
第1页
4．1 单纯形表
用表格法求解LP，规范表格——单纯形表以下：
第2页
计算步骤
(1).找出初始可行基，确定初始基可行解，建立初始单纯形表。
(2).检验各非基变量xj检验数，若j  0，j=m+1，…，n；则
已得到最优解，可停顿计算，不然转入下一步。
(3).在j > 0，j=m+1，…，n中，若有某个k对应xk系数列向量Pk 0，则此问题是无界解，停顿计算。不然，转入下一步。
(4).依据max(j > 0) =k，确定xk为换入变量，按 规则计算
 =min{bi/aik\aik>0}
可确定第l行基变量为换出变量。转入下一步。
第3页
用单纯形方法求解
max
z =
40
x
1
+
45
x
2
+
24
x
3

.
第4页
2 3 0 0 0
1 2 1 0 0
4 0 0 1 0
0 4 0 0 1
0 2 3 0 0 0
0
0
0
8
16
12
x3
x4
x5
4
-
3
2 3 0 0 0
2 1 0 1 0 -1/2
- 9 2 0 0 0 -3/4
0
0
3
x3
x4
x2
2
4
-
( )
3 0 1 0 0 1/4
16 4 0 0 1 0
X(0)=(0，0，8，16，12)T， z0 =0
第5页
2 3 0 0 0
2 1 0 1 0 -1/2
-13 0 0 -2 0 1/4
2
0
3
x1
x4
x2
-
4
12
3 0 1 0 0 1/4
8 0 0 -4 1 2
2 3 0 0 0
2 1 0 1 0 -1/2
-9 2 0 0 0 -3/4
0
0
3
x3
x4
x2
2
4
-
3 0 1 0 0 1/4
16 4 0 0 1 0
( )
X(1)=(0，3，2，16，0)T， z1 =9
第6页
2 3 0 0 0
2 1 0 1 0 -1/2
-13 0 0 -2 0 1/4
2
0
3
x1
x4
x2
-
4
12
3 0 1 0 0 1/4
8 0 0 -4 1 2
( )
2 3 0 0 0
4 1 0 0 1/4 0
-14 0 0 - -1/8 0
2
0
3
x1
x5
x2
2 0 1 1/2 -1/8 0
4 0 0 -2 1/2 1
X(2)=(2，3，0，8，0)T， z2 =13
X(3)=(4，2，0，0, 4)T， z3 =14
第7页
练习
第8页
§5 单纯形法深入讨论
一、 目标函数为Min情形
三种处理方法：
1 令Z’= -Z ===> Max Z’= -CX ；
2 求Min Z， 当全部检验数cj-zj>=0 时为最优，不然要迭代，换入检验数最小那个变量，确定换出变量方法和前面Max情形一样；
3 要求检验数为zj - cj， 其余过程和前面Max情形一样。
几个情况
第9页
二、 约束方程为“>=”或“=”情形（加人工变量）
人工变量法（确定初始可行基）：
原约束方程：AX=b
加入人工变量：xn+1，，xn+m
人工变量是虚拟变量，加入原方程中是作为暂时基变量，经过基旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零人工变量，原问题无可行解。
第10页