第1章 线性规划 (2)—03,04,05讲

第1章线性规划 复习1 线性规划问题的数学模型包含三个组成要素 决策变量目标函数约束条件2 线性规划数学模型的标准型 以及与非标准型的转化 3 图解法的一般步骤 本堂课的主要内容1 图解法的几何意义 2 单纯形法的概念 3 单纯形法的几何语言 4 单纯形法的代数形式5 单纯型表格 重点及难点 单纯形表 1 图解法的几何意义 凸集 Convexset 概念 设K是n维欧氏空间的一个点集 若K中的任意两点x 1 x 2 的连线上的一切点x仍在K中 则称K为凸集 即 若K中的任意两点x 1 x 2 K 存在0 1使得x x 1 1 x 2 K 则称K为凸集 例 凸集 例 非凸集 两个基本概念 凸组合 Convexcombination 设x 1 x 2 x k 是n维欧氏空间中的k个点 若存在数u1 u2 uk且0 ui 1 i 1 2 k ui 1 使得x u1x 1 u2x 2 ukx k 成立 则称x为x 1 x 2 x k 的凸组合 两个基本概念 顶点 设K是凸集 若K中的点x不能成为K中任何线段上的内点 则称x为凸集K的顶点 即 若K中的任意两点x 1 x 2 不存在数 0 1 使得x x 1 1 x 2 成立 则称x为凸集K的一个顶点 例 多边形上的点是顶点 圆周上的点都是顶点 1 图解法的几何意义 以例子1 1为例 1 图解法的几何意义 以例子1 1为例 8个顶点中 0 6 2 6 4 3 4 0 0 0 位于可行域的边界上 是可行解 称为顶点可行解 0 9 4 6 6 0 称为顶点非可行解 2 单纯形法的概念 LP 线性规划 解的基本概念 标准型 2 基 标准型中 A的秩为m 是矩阵A的满秩子矩阵 则B是线性规划问题的一个基 基矩阵 则B中的列向量为基向量 与基向量对应的决策变量称为基变量 其它变量称为非基变量 1 可行解 满足 1 2 的解 2 单纯形法的概念 3 基解 令非基变量为0 则由约束方程确定的唯一解 为基本解 简称基解 4 基可行解 若基解X 0 则称为基可行解 结论 1 LP的基可行解对应于可行域的顶点 2 若可行域有界 LP的目标函数一定可以在其可行域的顶点上达到最优 即一定存在一个基可行解是最优解 2 单纯形法的概念 求解例1 1的基 基变量 基解 基可行解和可行基 2 单纯形法的概念 求解例1 1的基 基变量 基解 基可行解和可行基 2 单纯形法的概念 求解例1 1的基 基变量 基解 基可行解和可行基 基变量 2 单纯形法的概念 求解例1 1的基 基变量 基解 基可行解和可行基 令 解得 解得 基解 2 单纯形法的概念 求解例1 1的基 基变量 基解 基可行解和可行基 基解 基解中所有变量取值为非负 故也是基可行解 对应的基是一个可行基 2 单纯形法的概念 2 1单纯形法的几何意义 单纯形法 按照一种规则的方式 从一个顶点向相邻的一个顶点转换 直到找到一个最优解为止 单纯形法的基本方法 基本方法 确定初始基可行解 检验是否最优 转到另一更好的基可行解 停 Y N 方法前提 模型化为标准型 1 化为标准型 2 确定一基可行解 令B P3 P4 P5 得 基可行解X 0 0 0 360 200 300 T 3 进基 出基 1 进基 存在正系数的非基变量 X 0 不是最优 令x2进基 2 出基 1 式中 令x1 0 得 分别令x3 x4 x5 0 得 x2 90 40 30 x5出基 代数形式 故得新基变量XB x2 x3 x4 将 1 化为 得新基可行解X 1 0 30 240 50 0 T 将 3 代入目标函数得 Z 3 4x1 1 2x5 360 Z 360 4 重复3 因存在正系数的非基变量 故继续 得 X 2 20 24 84 0 0 T Z 1 36x4 0 52x5 428 故X 2 为最优解 Z 428 单纯形法的基本方法 基本方法 确定初始基可行解 检验是否最优 转到另一更好的基可行解 停 Y N 方法前提 模型化为标准型 三 单纯形法的步骤 1 初始可行基B0的确定 若A中含有I B0 I若A中不含I 人工变量法 2 最优性检验 把目标函数用非基变量表示 检验数向量 记为 当 0时 当前解为最优解 方法 1 计算每个xj的检验数 2 若所有 j 0 则当前解为最优 否则 至少有 k 0 转3 3 换基迭代 基变换 得新基 转2 注 2 若对一切非基变量有 j 0 且存在 k 0 则有无穷多解 的计算 四 单纯形法的实现 单纯形表 12 0 0 0 单纯形表 7 90 的计算 40 30 枢纽元素 x3 x4 x2 30 0 3 1 0 0 0 1 50 2 5 0 0 1 0 5 240 7 8 0 1 0 0 4 3 4 0 0 0 1 2 或 或 30 8 20 100 x3 x1 x2 24 0 1 0 0 12 0 16 20 1 0 0 0 4 0 2 84 0 0 1 3 12 1 16 0 0 0 1 36 0 52 X 20 24 84 0 0 TZ 428 注 单纯形表中的信息 每一列的含义 B 1 bA B 1b B 1P1 B 1Pn 每个表中的B和B 1的查找 B从初表中找 B 1从当前表中找 对应于初表中的I的位置 以第2个表为例 终表分析 最优基B 和 B 1的查找 换入基变量中 得到基可行解 定理 若检验数全小于等于零 且某一个非基变量的检验数为0 则线性规划问题有无穷多最优解 无穷多最优解情况 证明 某个非基变量 为最优解 故线性规划问题有无穷多最优解 为一基可行解 有一个变量Xm k对应 因 为可行解 定理 若存在检验数大于零 但所对应的换入变量Xm k的系数向量Pm k 0 则原问题无最优解 无界解的情况 证明 构造一个新的解 分量为 定理 若非基变量检验数严格小于零 则线性规划问题有唯一最优解 定理 若检验数全小于等于零 且某一个非基变量的检验数为0 则线性规划问题有无穷多最优解 定理 若某一个非基变量的检验数大于0 其系数列向量Pm k 0 则原问题无最优解 无界解的情况 线性规划为求最大化的标准型 线性规划为求最小化的标准型时 相应的结果 定理 求最小化的最优解判别准则 1 若 C CBB 1A 0 则对应于基B的基础可行解x就是基础最优解 此时的可行基就是最优基 2 若检验数全大于等于零 且某一个非基变量的检验数为0 则线性规划问题有无穷多最优解 无穷多最优解情况 3 若存在检验数小于零 但所对应的换入变量Xm k的系数向量Pm k 0 则原问题无最优解 无界解的情况 确定换入变量时 找小于0中的最小者 课堂练习 用单纯形法求解 X 6 0 8 0 TZ 6 单纯形法的进一步讨论 人工变量法 大M法 当原问题求最大化时 假定人工变量在目标函数中的系数为 M M为任意大正数 目标函数求最大化 必须把人工变量从基变量换出 否则 不可能实现最大化 当原问题求最小化时 假定人工变量在目标函数中的系数为M M为任意大正数 目标函数求最小化 必须把人工变量从基变量换出 否则 不可能实现最小化 增加人工变量X人 xn 1 xn m T X人在目标函数中的系数为 M M为充分大正数 于是原问题化为 1问题 2方法 单纯形法求解 若 最优基变量中不含X人 则所得解的前n个分量即为X 否则 无解 3结论 例 用单纯形法求解 解 增加人工变量x5 x6 则模型化为 MaxZ 5x1 3x2 2x3 4x4 Mx5 Mx6 5x1 x2 x3 8x4 x5 102x1 4x2 3x3 2x4 x6 10 x1 x6 0 s t x5 x6 M M 10 10 5 4 5 x4 x6 4 M 10 2 x4 x2 4 3 5 3 10 x1 x2 5 3 X 5 3 5 3 0 0 T Z 40 3 单纯形法总结 1 Min型单纯形表与Max型的区别仅在于 令 k min j 0 的xk进基 当 0时最优 2 解的几种情况及其在单纯形表上的体现 讨论Max型 唯一最优解 j 0 非基 0 无穷多最优解 j 0有非基 k 0 无界解 有 k 0但B 1Pk 0 无可行解 用大M法求解 最优基中含有X人 退化解 有两个或两个以上的min 线性规划的对偶问题 DualProgramming 简称DP 一 对偶问题的提出和模型 1 问题的提出 产品组合问题 今有另公司要购买三种资源 至少出价多少 才能使原公司出让资源 设三种资源价格分别为y1 y2 y3 MinW 4y1 12y2 18y3 s t y1 3y3 3 2y2 2y3 5 y1 y2 y3 0 收购总价 收购总价 出让生产某产品的资源消耗的价值不低于该产品的利润价值 MinW 4y1 12y2 18y3 s t y1 3y3 3 2y2 2y3 5 y1 y2 y3 0 2 模型 原问题 P 对偶问题 D MinW bTY ATY CTY 0 s t 原问题 P 对偶问题 D MinW bTY ATY CTY 0 s t 3 如何求LP模型的对偶问题 1 若LP为Max型 则尽量化成 P 形式 等式 自由变量不用转换 2 若LP为Min型 则尽量化成 D 形式 等式 自由变量不用转换 例 写出下面LP的对偶 解 令 1 对称性 P 与 D 互为对偶 二 对偶性质与定理 2 弱对偶性 设X Y分别为 P D 的任一可行解 则 证 X Y为 P D 的可行解 5 对偶定理 若 P 有最优解 则 D 也有最优解 且二者最优值相等 3 解的最优性 设 分别为 P 与 D 的可行解 且 则 4 无界性 若 P 为无界解 则 D 无可行解 若 D 为无界解 则 P 无可行解 6 松紧定理 互补松弛性 设分别为 P 与 D 的可行解 例1 4讲解 掌握对偶问题的基本性质 其对偶问题的最优解为 试找出原问题的最优解 线性规划问题最优解为用对偶问题求原问题的最优解 解 标准型为 对偶问题为 标准型为 代入原问题标准型有 三 对偶问题最优解的经济解释 影子价格 Y y1 y2 y