第三讲 单纯形法（20100310）.ppt

leijunli@126.com 单纯形法迭代原理 §1.4（表格）单纯形法的计算步骤 为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似，下面来建立这种计算表。 线性规划的方程组 根据增广矩阵设计计算表 计算步骤 对于目标函数求极大情形 (1) 按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。 (2) 计算各非基变量的检验数， 检查检验数，若所有检验数 则已得到最优解，可停止计算。否则转入下一步。 (3) 在σj＞0,j=m+1,…,n中，若有某个σk对应xk的系数列向量Pk≤0，则此问题是无界，停止计算。 否则，转入下一步。 (4) 根据max(σj＞0)=σk，确定xk为换入变量，按θ规则计算 (5) 以alk为主元素进行迭代(即用高斯消去法或称为旋转运算)，把xk所对应的列向量 将XB列中的xl换为xk，得到新的单纯形表。重复(2)～(5)，直到终止。 练习 0 0 0 -3/2 -1/8 0 -14 -z 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 0 0 4 4 2 x3 x1 x6 x2 0 2 0 3 x1 x2 x3 x4 x5 x6 b xB cB 2 3 0 0 0 0 cj 0 0 0 -2 0 1/4 -13 -z 4 － 4 12 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4 2 2 8 3 x3 x1 x5 x2 0 2 0 3 x1 x2 x3 x4 x5 x6 b xB cB 2 3 0 0 0 0 cj * * * 非可行解 可 行 解 基解 基可行解 线性规划问题的基本定理 定理1 若线性规划问题存在可行解，则问题的可行 域是凸集。 定理2 线性规划问题的基可行解 X 对应线性规 划问题可行域（凸集）的顶点。 定理3 若线性规划问题有最优解，一定存在一个基 可行解是最优解。 从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。 一、基本思想 将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。 单纯形法迭代原理 例1: 化为标准型 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 ⑴ ⑵ ⑶ ⑷ 作 图 x2 x1 (4 2) ⑴ ⑵ ⑶ ⑷ 例1、 图解法 ∴ 唯一最优解为：x1 = 4, x2 = 2, 最优值:Z = 14. 可行域 约束方程的系数矩阵 为基变量 为非基变量 E 为单位矩阵且可逆 非最优解！ 令： 则： ∴ 基本可行解为（0,0,12,8,16,12） 此时，Z = 0 检验数~~ x2进基 第一次: 基变量: 基解: 目标函数值: 目标函数: x2进基 令x1=0, 得: 为出基变量 第二次: 基变量: 基解: 目标函数值: 目标函数: x1进基 令x6=0, 得: 为出基变量 第三次: 基变量: 基解: 目标函数值: 目标函数: x6进基 令x4=0, 得: 为出基变量 为出基变量? ? 第四次: 基变量: 基解: 目标函数值: 目标函数: 最优！ 0 0 -1 -1/2