第三节用单纯形法求解.ppt

第三节用单纯形法求解
*
第1页，共10页，2022年，5月20日，13点2分，星期日
◆解目标规划问题的单纯形法计算步骤
(1)建立初始单纯形表。
表中检验数行按优先因子个数分别列成K行。
当不含绝对约束时，di-(i=第三节用单纯形法求解
*
第1页，共10页，2022年，5月20日，13点2分，星期日
◆解目标规划问题的单纯形法计算步骤
(1)建立初始单纯形表。
表中检验数行按优先因子个数分别列成K行。
当不含绝对约束时，di-(i=1,2,… ,K)构成了一组基本可行解,其系数列向量构成一个基。列出初始单纯形表。置k =1；
第2页，共10页，2022年，5月20日，13点2分，星期日
(2)确定换入变量。检查当前第k行中是否存在小于0，且对应前k-1行的同列检验数为零的检验数。若有，则取其中最小者对应变量为换入变量，转(3)。若无这样的检验数，则转(5)；
第3页，共10页，2022年，5月20日，13点2分，星期日
(3)确定换出变量。按单纯形法中的最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量，转(4)；
第4页，共10页，2022年，5月20日，13点2分，星期日
(4)按照单纯形法进行基变换运算(行初等变换运算)，换入变量替换换出变量，建立新的单纯形表，返回(2)；

(5)当k = K 时，计算结束。表中的解即为满意解。否则置k = k+1，返回(2)。
第5页，共10页，2022年，5月20日，13点2分，星期日
例3：用单纯形法求解下述目标规划问题：
第6页，共10页，2022年，5月20日，13点2分，星期日
解：步1，以d1-、d2- 、d3-为基变量列出初始单纯形表见表5-1。
步2，确定换入变量。x1为换入变量。
步3，确定换出变量。 d1-为换出变量。
步4，进行迭代运算。得到表5-2。
步5，重复步2到步4的运算得到表5-3。
第7页，共10页，2022年，5月20日，13点2分，星期日
cj→
0 0 P1 0 0 P1 P2 0
CB 基 b
x1 x2 d1- d1+ d2- d2+ d3- d3+
P1 d1- 10
0 d2- 40
P2 d3- 100
[1] 0 1 -1
2 1 1 -1
3 2 1 -1
cj- zj
P1
-1 1 1
P2
-3 -2 1
表5-1
第8页，共10页，2022年，5月20日，13点2分，星期日
表5-2
cj→
0 0 P1 0 0 P1 P2 0
CB