第2章5-单纯形法求解.ppt

第 2 章 线性规划问题 单纯形法（3）——解法与习题 1、单纯形法解法过程 2、举例 线性方程组的增广矩阵表示 初始可行基B1 初始基本可行解 初始基变量 是松弛变量。 初始可行解（只要满足非负条件） 初始基本可行解 目标函数与最优性检验 第一次迭代 确定入基变量，应当是 ，它的判别数是4。 确定出基变量，方法如下，得 确定新基和求解新的基本可行解 新基 新的基变量： 新的基本可行解 新的基本可行解和目标函数 基本可行解 目标函数 第二次迭代 确定入基变量： 确定出基变量： 确定新基和求解新的基本可行解 新的基本可行解和目标函数 第三次迭代 确定新基和求解新的基本可行解 新基 新的基变量： 新的基本可行解 新的基本可行解和目标函数 基本可行解 目标函数 这是最优解。最大目标函数值为2600。 练习：例1 求解下列线性规划问题 解：引进松驰变量x3, x4，化为标准形得： 例2、求解下列线性规划问题 * * LP问题的标准形 找出一个初始基可行解 判别此基可行解 是否为最优解 求出使目标函数值 得到改善的基可行解 换基迭代 停 Y N 新基 新的基变量： 新的基本可行解 基本可行解 目标函数 确定入基变量： 确定出基变量： 从标准形中可看出存在可行基B=(A3，A4)=E2，基变量为X3，X4；非基变量为X1，X2。建立初始单纯形表得： 4 3 0 0 0 Z 2 3 1 0 3 2 0 1 24 26 x3 x4 0 0 x1 x2 x3 x4 b XB CB -4 -3 0 0 cj 由于X1，X2的检验数均为正，且X1的检验数绝对值最大，选取X1为进基变量；再按最小比值=min(24/2，26/3) =26/3，因此选取X4为出基变量，进行换基迭代。 0 1/3 0 -4/3 104/3 Z 0 5/ 3 1 -2/3 1 2/3 0 1/3 20/3 26/3 x3 x1 0 4 x1 x2 x3 x4 b XB CB 由于只有X2的检验数均为正，选取X2为进基变量；再按最小比值=min(20/5，26/2) =4，因此选取X3为出基变量，进行换基迭代。 0 0 -1/5 -6/5 36 Z 0 1 3/5 -2/5 1 0 -2/5 3/5 4 6 x2 x1 3 4 x1 x2 x3 x4 b XB CB 表中第一行的所有检验数均为负数，表明目标函数已达到最大值，上述表为最优表。从表中可得到最优解为X=（x1,x2,x3,x4）=（6，4，0，0），最优值为Z=36。