最优化理论与方法1（2014-简版）

然后利用单纯形法求解即可（下面举例说明，仍用大M法的例)。 举例：求解线性规划问题

minf??3x1?x2?x3

?x1?2x2?x3?11??4x?x?2x?3?123s.t.?

?x3?1??2x1??x1,x2,x3?0解：(1)构造第一阶段问题并求解。

minf'?x6?x7

?11?x1?2x2?x3?x4??4x?x?2x?x5?x6?3?123 s.t.??2x?x?x?1137??xj?0?j?1,2,?,7??利用单纯形法求解

表3中不含人工变量且f'?0，转入第二阶段。

表4：去掉人工变量后的初始单纯形表

表5：最终单纯形表

单纯形法计算中的几个问题： 1、目标函数极小化时解的最优性判断 只需用检验数?j?0作为最优性的标志。 2、无可行解的判断

当求解结果出现所有?j?0时，如基变量仍含有非零的人工变量（两阶段法求解时第一阶段目标函数值不等于0），则原线性规划问

题无可行解。

单纯形法有三种形式：① 方程组形式；② 表格形式；③ 矩阵形式。 一、方程组形式的单纯形法 1、思路

由一个基本可行解转化为另一个基本可行解。 例1：

minf??3x1?5x2 f?3x1?5x2?0

?x1?x3?8?2x?x?12?24改写 s.t. ??3x1?4x2?x5?36??x1,x2,x3,x4,x5,minf??3x1?5x2?0?x1?x3?8?2x?x?12?24 ??3x1?4x2?x5?36??x1,x2,x3,x4,x5?0