文档详情

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

发布:2017-03-22约4.42千字共53页下载文档
文本预览下载声明
初始单纯形表的矩阵形式: 定理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步 可行 典则形式 不是单
显示全部
相似文档