2.4 退化情形的处理
一、退化问题可能会出现基的循环
2 、由于退化问题的目标函数值在迭代过程中可能并不改
进,一旦前面出现的基在迭代过程中又重新出现,则后面的
迭代过程可能会在几个基上面兜圈子,此现象成为“基的循
环”。
对退化的线性规划问题,使用单纯形法时:
对非退化的线性规划问题使用单纯形法
时,
由于每次迭代都使目标函数值有所改进,从而经过有限次迭
代,必能求得最优解或判断问题无最优解。
非退化情
形:
退化情形:
3 、若问题还未达到最优就出现了“基的循环”,再按照通
常的单纯形法继续迭代下去,必然导致“死循环”,以致最终
不能得到最优解。 ( 如 P48 的 Beale 例子 )
1 、如果迭代过程中基不出现重复,则经过有限次迭代也
能得到最优解或判断问题无最优解。
( 如 2.3 节的例 4)
第 1 页 / 共 26 页