线性规划单纯形法(经典运筹学).ppt

初始单纯形表的矩阵形式： 定理1.7 对非退化线性规划问题，单纯形法必然在有限次迭代内终止于下述两种情况之一：或者找到一个最优基本可行解；或者判断该问题无界。 常数项 2 3 1 0 0 0 6 -3 2 0 1 0 0 3 0 2 0 0 1 0 5 2 1 0 0 0 1 4 基变量 4 3 0 0 0 0 z 单纯形表 主元素 b 1 0.5 0 0 0 0.5 2 0 2 1 0 0 -1 2 0 3.5 0 1 0 1.5 9 0 2 0 0 1 0 5 0 1 0 0 0 -2 z-8 检验行 b 1 0.5 0 0 0 0.5 2 0 2 1 0 0 -1 2 0 3.5 0 1 0 1.5 9 0 2 0 0 1 0 5 0 1 0 0 0 -2 z-8 b 0 1 0.5 0 0 -0.5 1 0 0 -1.75 1 0 3.25 5.5 0 0 -1 0 1 1 3 1 0 -0.25 0 0 0.75 1.5 0 0 -0.5 0 0 -1.5 z-9 为最优解 常数项 4 1 0 0 0 Z -1 1 1 0 0 2 1 -4 0 1 0 4 1 -2 0 0 1 8 4 8 1 -4 0 1 0 4 0 -3 1 1 0 6 0 2 0 -1 1 4 0 17 0 -4 0 Z-16 1 0 0 -1 2 12 0 0 1 -1/2 3/2 12 0 1 0 -1/2 1/2 2 0 0 0 9/2 -17/2 Z-48 无界! 常数项 4 1 0 0 0 Z -1 1 1 0 0 2 1 -4 0 1 0 4 1 -2 0 0 1 8 4 8 1 0 0 -1 2 12 0 0 1 -1/2 3/2 12 0 1 0 -1/2 1/2 2 0 0 0 9/2 -17/2 Z-48 对应的线性规划问题无界 所以，该线性规划问题无界 3、将约束方程化为每个方程只含一个基变量 目标函数表示成非基变量的函数 单纯形法步骤：1、化标准型 2、选定一个可行基，并得一基本可行解X？ 5、判断X是否为最优解：若目标函数行中所有检验数ci≤0, 则X为 最优解。若存在某个cj0,且所有的aij 0，则不存 在有界最优解。否则转下一步 4、做单纯形表 6、换基迭代 （1）入基变量：设ck=max{ci | ci 0},取xk为入基变量 （2）出基变量： 7、对单纯形表做初等行变换：把基变量对应的列化为 单位向量，目标函数的基变量系数化为零， 得一新的基本可行解X。 转第4步 可行 典则形式 不是单