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

线性规划建模
第一节  线性规划建模的几个问题
第二节  常见的线性规划模型
第三节  案例讨论
第四节  对偶单纯形方法
第五节  敏感性分析

 

（一）单纯形方法的初步讨论
1、单纯形方法的基本思想
            从可行域中的一个基本可行解出发，判断它是否已是最优解，若不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找出最优解或判定问题无界为止。
           从另一个角度说，就是从可行域的某一个极点出发，迭代到另一个极点，并使目标函数的值有所改善，直到找出有无最优解时为止。
（一）单纯形方法的初步讨论
2、单纯形方法：消去法
[例]求解线性规划模型
      解：第一步，将线性规划模型标准化：
                    Max  Z=50x1+30x2+0x3+0x4
               s·t·     4x1+3x2+x3            =120
                    2x1+x2+      +x4  =50
                       x1  ,  x2 ,  x3 , ,x4≥0
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）。

 

 

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