最优化方法-线性规划-单纯形法

实用优化方法线性规划 单纯形法 线性规划 目标函数是线性的 约束条件是线性等式或不等式 线性规划 线性规划的历史 渊源要追溯到Euler Liebnitz Lagrange等GeorgeDantzig VonNeumann Princeton 和LeonidKantorovich在1940 s创建了线性规划1947年 GeorgeDantzig发明了单纯形法1979年 L Khachain找到了求解线性规划的一种有效方法 第一个多项式时间算法 椭球内点法 1984年 NarendraKarmarkan发现了另一种求解线性规划的有效方法 已证明是单纯形法的强有力的竞争者 投影内点法 现在求解大规模 退化问题最有效的是原 对偶内点法 问题 确定食品数量 满足营养需求 花费最小 变量 n种食品 m种营养成份 第j种食品的单价 每单位第j种食品所含第i种营养的数量 食用第j种食品的数量 为了健康 每天必须食用第i种营养的数量 模型 例1 食谱问题 例2 运输问题 产销平衡 不平衡的运输问题 例3 其它应用 数据包络分析 dataenvelopeanalysis DEA 网络流问题 Networkflow 博弈论 gametheory 等 线性规划的一般形式 线性规划的标准形 分析 算法 标准形的特征 极小化 等式约束 变量非负 向量表示 一般形式标准形 称松弛 slack 盈余 surplus 变量 自由变量 例5 化成标准形 定义 给定含有n个变量 m个方程的线性方程组Ax b 设B是由A的列组成的任一非奇异m m子阵 则如果置x的所有与B无关的n m个分量为零后 所得方程组的解是Ax b关于基B的基本解 basicsolution 称x中与基B对应的分量为基变量 basicvariables 退化基本解 基本解中如果有一个或多个基变量的值为零 基本解与基变量 其中 在满秩假定下 方程组Ax b总有解 且至少有一个基本解 基本可行解 定义称的非负基本解是标准形的基本可行解 basicfeasiblesolution 约束系统 线性规划的基本定理 i 若标准型有可行解 则必有基本可行解 ii 若标准型有最优解 则必有最优基本可行解 考虑线性规划标准形 其中A是秩为m的m n阶矩阵 则以下结论成立 基本可行解的个数不超过 与凸性的关系 线性规划的基本定理 标准形 凸性 凸集及性质 几何解释 连接集合中任两点的线段仍含在该集合中 性质 定义是凸集 convexset 如果对S中任意两点x y和 0 1 中的任一数满足 一些重要的凸集 注 任一线性规划的可行集是多面集 超平面 hyperplane 正 负闭半空间 极点 几何上 极点即不能位于连接该集合中其它两点的开线段上的点 极点与基本可行解的等价性定理 推论 i 若K非空 则至少有一个极点 ii 若线性规划有最优解 则必有一个极点是最优解 iii Ax b对应的约束集K最多有有限个极点 线性规划基本定理的几何形式 例2 例1 例3 Subjectto 线性规划解的几何特征 唯一解 顶点 线性规划解的几何特征 无界 没有有限最优解不可行 没有可行解 可行集 多边形 二维 多边集 高维空间 给出有效的代数刻画和严谨的几何描述 从理论上证实上述几何特征 并寻求有效算法 有解 唯一解 多个解 整条边 面 甚至整个可行集 无 下 界 线性规划问题解的几种情况 单纯形法简介 适用形式 标准形 基本可行解 极点 理论基础 线性规划的基本定理 基本思想 从约束集的某个极点 BFS开始 依次移动到相邻极点 BFS 直到找出最优解 或判断问题无界 初始化 如何找到一个BFS 判断准则 何时最优 何时无界 迭代规则 如何从一个极点 BFS迭代到相邻极点 BFS 1 转轴 基本解 相邻基本解 满秩假定 A是行满秩的 规范形 canonicalform 规范形的转换问题 什么时候可以替换 替换后新规范形是什么 替换问题 假设在上述规范形中 想用 转轴 pivot 当且仅当 可以替换 替换后 新规范形的系数 例1 求下列方程组以为基变量的基本解 x 0 0 0 4 2 1 2 BFS 相邻BFS 极点 相邻极点 问题 确定出基变量 使转轴后新规范形对应BFS 设x是BFS 且规范形如前 且假设aq进基 因为 所以 确定离基变量 至少有一个正元 例3 考虑线性方程组 a4进基 B a1 a2 a3 X 4 3 1 0 0 0 x 0 1 3 2 0 0 3 BFS 目标值减小的相邻BFS 将Ax b的任一解用非基变量表示 设x是BFS 且规范形如前 则有 相对 既约费用系数 relative reducedcostcoefficients 将Ax b的任一解x用非基变量表示为 度量变量相对于给定基的费用 确定进基变量 最优性定理 定理 BFS的提高 相对费用系数的经济解释 合成价格 相对价格 退化基本可行解 某个或某些基变量取零的基本可行解 问题 基本可行解与基的对应关系 4 计算过程 单纯形法 单纯形表 BFS对应规范形的表格 既约费用系数和BFS目标值的相反数 单纯形法的步骤 步0形成与初始BFS对应的初始表格 通过行变换求出第一张单纯形表 步1若对每个j都有 停 当前BFS是最优的 步2选取q满足 步4以为转轴元进行转轴 更新单纯形表 返步1 步3若 停 问题无界 否则 选p满足 转轴规则 进基变量 最小相对费用系数规则 出基变量 最小指标规则 例1 化标准形 得标准形的初始表格 第一张单纯形表 0 2 4 27 5 最优解 退化 degenerate 与循环 cycling 退化问题 单纯形法可能出现循环 实际中经常碰到退化问题 但很少出现循环 避免出现循环的措施 摄动法 Bland法则 字典序法 基本可行解是退化的当且仅当单纯形表最后一列有一个或者多个零 一次转轴是退化的当且仅当目标函数没有发生变化 最小系数规则 进基变量 最小系数规则 出基变量 最小指标规则 循环 定义 从某张单纯形表开始返回到该单纯形表的一串转轴 转轴规则 选取进基变量和离基变量的明确规则 循环 注 循环转轴序列中所有BFS都是退化的 是同一个BFS 第七张单纯形表 避免循环的方法 如果有多个费用系数是负的 选取下标最小的相对费用系数对应的变量为进基变量 摄动法 Charnes 1952年 Bland法则 Bland 1977 最小指标法则 字典序法 Dantzig Orden和Wolfe 1954年 如果最小正比值在多个指标处取得 取下标最小者对应的变量为进基变量 美好愿望 构造某种永远不会产生循环的转轴规则 前四张单纯形表相同 利用Bland法则作为转轴规则求解Beale的例子 最后一张单纯形表 最优单纯形表 单纯形法的收敛性 非退化线性规划 任一基本可行解非退化 5 两阶段法如何启动单纯形法 人工变量 给有需要的行乘以 1 使得b 0 方法 得到原问题的基本可行解 z 0 无可行解 z 0 有可行解 基变量中无人工变量 x是BFS B是对应的基 例1 给出下面系统的一个基本可行解 或者说明其无解 辅助问题的初始表格 第一张单纯形表 第二张单纯形表 注意基变量整列包括末行z在内除了基变量其他元素都是0 辅助问题的最优值是0 原问题的BFS 两阶段法 可求任一线性规划问题 第I阶段 启动单纯形法 构造 求解辅助问题 判断原问题不可行 或可行 可行时找到基本可行解及对应规范形 第II阶段 利用单纯形法求原问题 从上述BFS出发 求解所给问题 原问题无界或者有解 例2 利用两阶段法求解下面的问题 先构造辅助向量z x4 x5 辅助问题的最后一张单纯形表 原问题的初始表格 得到辅助问题的最后一张单纯形表后 去掉辅助变量 将原始问题的z带入表格 启动单纯形法 原问题的最优解 6 修正单纯形法 Revisedsimplexmethod 重要事实 通常仅有少数列发生转轴 2m 3m 核心问题 如何更新当前基的逆 新基的逆 仅需原始数据 c A b 和基B的逆矩阵 7 单纯形法的矩阵形式 给定基B及对应BFS xB 0 其中xB B 1b 用非基变量表示目标函数 用非基变量表示基变量 初始表格 单纯形表 初始表格通常不是单纯形表 与基矩阵B对应的单纯形表 修正单纯形法的计算步骤 步2选取q满足 步3计算yq B 1aq 若 步1计算 如果停 得最优解 步0给定BFS及对应的B 1 计算 核心计算 B 1 涉及到的计算 停 问题无界 否则 选p满足 步