运筹学4单纯形法迭代原理ppt课件.ppt

单纯形法迭代原理 1 三 单纯形法的基本思想1 顶点的逐步转移 即从可行域的一个顶点 基本可行解 开始 转移到另一个顶点 另一个基本可行解 的迭代过程 转移的条件是使目标函数值得到改善 逐步变优 当目标函数达到最优值时 问题也就得到了最优解 2 根据线性规划问题的可行域是凸多边形或凸多面体 一个线性规划问题有最优解 就一定可以在可行域的顶点上找到 于是 若某线性规划只有唯一的一个最优解 这个最优解所对应的点一定是可行域的一个顶点 若该线性规划有多个最优解 那么肯定在可行域的顶点中可以找到至少一个最优解 顶点转移的依据 3 转移条件 转移结果 使目标函数值得到改善得到LP最优解 目标函数达到最优值2 需要解决的问题 1 为了使目标函数逐步变优 怎么转移 2 目标函数何时达到最优 判断标准是什么 4 解LP问题单纯形法的基本思路 初始可行基 设法在约束矩阵中构造出一个m阶单位阵 检验数 进基变量 检验数离基变量 最小比值准则 5 1 确定初始基本可行解 LP 希望在化LP的标准形式时 A中都含有一个m阶单位阵 6 观察法 观察系数矩阵中是否含有现成的单位阵 LP限制条件中全部是 类型的约束 将新增的松弛变量 作为初始基变量 对应的系数列向量构成单位阵 LP限制条件有 类型的约束 左端新增剩余变量 后 再加上一个非负的新变量 人工变量 LP限制条件有 类型的约束 直接在左端加上人工变量 7 在引入人工变量后 与原先的约束方程不完全等价 为此 需要在目标函数上做些 修正 大M法或两阶段法 非基变量取0 算出基变量 搭配在一起构成初始基本可行解 8 2 建立判别准则 判断 初始基本可行解或经过若干次迭代后得到的新基本可行解 当前解 是否为最优解 一般 经过若干次迭代 对于基B 用非基变量表出基变量的表达式为 典式 若 9 用非基变量表示目标函数的表达式 典式 检验数 10 其中 1 最优性判别定理 2 有无穷多个 最优解 的判别定理 11 3 进行基变换 1 进基变量的确定 原则 正检验数 或最大正检验数 所对应的变量进基 目的是使目标函数得到改善 2 离基变量的确定 在保持解的可行性的前提下 使目标函数较快增大 12 当时 为使 需要 从而 最大可取到 最小比值原则 13 离基变量 是可行解 是否还是基本解 是 14 从而 目标函数得到了改善 15 第四节单纯形表 16 1 建立初始单纯形表 假定B I b 0设maxZ c1x1 c2x2 cnxn 将目标函数改写为 Z c1x1 c2x2 cnxn 0 17 检验数行 最后一行是检验数行 标出了对应决策变量xj的检验数 第一行是价值系数行 标出了决策变量xj的价值系数cj 第二行是标示行 标出了表中主体各行的含义 第一列标出了基变量的价值系数 第二列标出了当前基变量的名称 第三列是右端项 前m个元素是当前基本可行解的基变量的取值 最小比值准则 18 将初始数据填入上表 可得到初始单纯形表 观察检验数行 若所有的 则停止计算 否则进行下一步 1 检验当前基本可行解是否为最优解 最优性判别定理 19 2 检验是否为无界解 3 选择进基变量 从而xm t是进基变量 pm t为进基向量 并称表中pm t所在的列为主列 4 选择离基变量 最小比值准则 从而xl是离基变量 并称表中离基变量所在的行为主行 5 基变换 主行和主列的交叉元素称为主元素al m t 20 Z0 Z XB cj x1 x2 xm xm 1 xn c1 c2 cm cm 1 cn CB n m mn m m n m n m a a a a a a s s 0 0 0 1 0 0 0 1 0 0 0 1 1 1 2 1 2 1 1 1 m m m b x c b x c b x c 2 2 2 1 1 1 clxlbl00 0al m 1 aln 主行同除以al m t 即将主元素化为1 将新的主行的 ai m t 倍分别加到第i行 即将主列的其他元素化为0 将新的主行的倍分别加到最后一行 即将xm t的检验数化为0 21 6 回到1 对新解作最优性检验 22 例 用单纯形法求解线性规划问题 解 标准化 23 建立初始单纯行表 基变换 24 基变换 25 基变换 26 27 说明用单纯形法从当前解迭代