运筹学讲义-单纯形方法(ppt 73页)

一、 单纯形方法
二、 线性规划的其他解法
三、 电子表格建模及其求解
四、 生产进度问题

 

（一）单纯形方法的初步讨论
1、单纯形方法的基本思想
从可行域中的一个基本可行解出发，判断它是否已是最优解，若不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找出最优解或判定问题无界为止。
从另一个角度说，就是从可行域的某一个极点出发，迭代到另一个极点，并使目标函数的值有所改善，直到找出有无最优解时为止。
2、单纯形方法：消去法
   第二步，寻找初始可行解。变量x3 、,x4对应的列
  向量A3、A4 可作为初始可行基，那么X3、X4为基      
  变量，X1、X2为非基变量，用非基量表示基变量，    则有：
                   Max  Z=50x1+30x2+0x3+0x4
               s·t·       x3 =120- 4x1-3x2
                           x4  =50 -2x1-x2
                       x1  ,  x2 ,  x3 , ,x4≥0
   令x1  、  x2 =0，得到基本可行解                                    X=（0，0，120，50）。

 

..............................