川大运筹学资料及试题答案PPT课件

LinearProgramming 运筹学课件 第1章线性规划 线性规划问题提出可行区域与基本可行解单纯形算法单纯形法进一步讨论 1 1线性规划问题提出 线性规划例题生产计划问题线性规划模型一般形式规范形式标准形式形式转换概念图解法 1 1 1线性规划例题 某工厂用三种原料生产三种产品 已知的条件如表所示 试制订总利润最大的生产计划 生产计划问题 问题分析 模型 1 1 2线性规划模型 一般形式 注释 向量形式 矩阵形式 标准形式 变一般形式为标准形式 约束转换实例 目标转换 变量转换 不等式变等式 松弛变量 剩余变量 几个概念 图解法 例解线性规划 注释 解可能出现的情况 可行域是空集可行域无界无最优解最优解存在且唯一 则一定在顶点上达到最优解存在且不唯一 一定存在顶点是最优解 1 2可行区域与基本可行解 可行域的几何结构基本可行解与基本定理 可行域的几何结构 基本假设凸集可行域的凸性 基本假设 凸集与顶点 基本可行解与基本定理 定义基本定理问题 例 基本解不一定是可行解 基本定理 定理2 证明 由基可行解的定义知 必要性显然成立 充分性 若向量 线性独立 则必有 当 时 它们恰好构成一个基 从而为相应的 基可行解 当 时 则一定能从剩余的列向量 中取出m k个与 构成最大的线性独立向量组 其对应的解恰为x 所以 x是基可行解 定理3 证明 1 x不是基可行解 则x不是可行域的顶点 不失一般性 假设x的前m个分量为正 则有 由定理2知 线性相关 即存在一组 不全为0的数 使得有 上式乘上一个不为0的数 与 相加 相减得 令 的选取保证 对所有的 有 所以 且 所以 x不是可行域的顶点 2 x不是可行域的顶点 则x不是基可行解 不失一般性 设 不是可行域的顶点 所以可以找到可行域内另外两个不同点Y Z 有X AY 1 a Z 0 a 1 即 因为a 0 1 a 0 故当 因为 所以 上面两式相减得 因为 不全为0 故 线性相关 即x不是基本可行解 1 3单纯形算法 算法的三个阶段算法步骤单纯形表算例 阶段1 确定初始基可行解 假设问题 引入松弛变量 得 则 可设 则 约束变为 则 初始基可行解为 则 阶段2 由一个基可行解到另一个 设初始基可行解 又设前m个坐标非0 即 因为是基可行解 所以 若我们总假定有方法使基矩阵是单位矩阵 则上式展开为 因为 是基 所以 其余向量可由它 线性表示 对上式乘以正数 上式与 相加得 从中可找到另一个满足约束的点 要使它成为基可行解 需要满足 且至少有一个取等号 又因为 若aij 0 则条件自然满足 所以 只需取 即可 阶段3 最优性检验和解的判别 把基可行解 分别代入目标 令 1 当所有的 说明 现有顶点的目标函数值 比相邻各顶点的目标函数值都大 现有顶点对应的基可行解即为唯一最优解 2 当所有的 又对某个非基变量 有 则 无穷多最优解 3 若存在某个 又 无界解 的所有分量 算法步骤 单纯形表例子 例 解 单纯形法的矩阵描述 考虑问题 引入松弛变量 得 设B是一个可行基 若 则对应于B的变量向量 则 同时将C也分成两块 所以 有 所以 LP问题写成 将 2 移项后得 将 3 左乘 将 4 代入目标 1 得 单纯形法进一步讨论 两阶段法大M法退化说明 为什么要做进一步讨论 两阶段法 第一阶段 不考虑原问题是否存在基可行解 给原问题加入人工变量 并构造只含人工变量的目标函数w 并要求实现最小化 若求解得w 0 说明原问题存在基可行解 可进入第二阶段 否 原问题无可行解 停 第二阶段 将第一阶段计算得到的最终表 除去人工变量 将目标函数行的系数换成原问题的目标函数系数 作为第二阶段的初始表 例 算例 解 第一阶段 所以 w 0 第二阶段 大M法 在一个LP问题的约束条件中加入人工变量后 要求人工变量对目标函数取值不受影响 为此假定人工变量在目标函数中的系数为 M 这样目标要实现最大化时 必须把人工变量换出基 否则不能最大化 采用大M法 引入人工变量 构造新的线性规划问题 LP 单纯形表如下 例 关于退化的说明 单纯形法计算中用 规则确定换出变量时 有时存在两个以上相同的最小比值 如此 在下一次迭代中就有一个或几个基变量等于0 这便出现退化解 为解决 先后有人提出了 摄动法 词典序法 1974