最优化理论与方法1(2014-简版) 下载本文

2、单纯形法的几何意义

3、单纯形法的计算步骤

二、单纯形表

从上述单纯形法迭代原理中可知,每一次迭代计算只要表示出当前的约束方程组及目标函数即可。

按定义,化为当前基对应的典式。

?f?c1x1?...?cmxm?cm?1xm?1?...?cnxn?0 ?x ?a1m?1xm?1?.....?a1nxn?b11???a2m?1xm?1?.....?a2nxn?b2? x2 ? ...................................?xm ?amm?1xm?1?.....?amnxn?bm ?? 例2:用单纯形表求解LP问题

解:化标准型

minmaxf?2x1?x25x2?15??6x?2x?24?12??x1?x2?5??x1,x2?0f?-2x1-x2?0x3?0x4?0x55x2?x3?15??6x?2x?x4?24?12??x5?5?x1?x2?x1,?,x5?0?

表1:列初始单纯形表(单位矩阵对应的变量为基变量)