运筹学教学课件 线性规划学习课件ppt.ppt

线性规划linearprograming 运筹学 基本内容 线性规划的基本性质及其图解法单纯形法对偶问题灵敏度分析 第一章线性规划的基本性质 线性规划问题及模型二维线性规划的求解 图解法线性规划的标准形式线性规划问题解及其性质 线性规划研究问题 主要研究解决有限资源的最佳分配问题 即如何对有限资源作出最佳方式的调配和最有力地使用 以便最充分地发挥资源的效能 以获取最佳的经济效益 生产计划问题运输问题配料问题下料问题食谱问题产品配套问题 1 生产计划问题 应如何安排生产这两种产品才能获利最多 问题分析 数学模型为 2 运输问题 设两个粮库供应三个粮店 供应量 需求量和运费如下表所示 问如何安排运输计划 可使总运费最少 建立数学模型 问题分析 数学模型 3 配料问题 某化工厂根据一项合同要为用户生产一种用甲 乙两种原料混合配制而成的特殊产品 甲 乙两种原料都含有a b c三种化学成分 其含量以及产品中各成分含量的最低量如下表所示 甲 乙两种原料成本见下表 厂方希望总成本大到最小 则应如何配制该产品 问题分析 数学模型 线性规划问题的特点 1 非负的 决策变量2 求极值的目标函数3 线性的约束条件 一般模型 线性规划的图解 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优点 最优解 6 4 8 6 0 x1 x2 图解法的步骤 可行域图形地确定所有约束条件共同构成的图形成为可行域可行域所有点 包括边界 均是可行解目标函数的等值线与最优点的确定令z取不同值 得到一组平行的等值线沿目标函数值增大的方向移动等值线 当韩淑芝最大时与可行域的交点即为最优点 最优点的求解在图上观测最优点的坐标通过解方程组得出最优点坐标值 可行域的几种情况 无界域x1 2x2 4s t x1 2x2 5x1 x2 0 1 4 2 3 5 1 2 3 x1 x2 x1 2x2 4 x1 2x2 5 可行域的几种情况 有界域 2 8 4 6 10 2 4 10 x1 3x1 4x2 36 x1 8 12 6 8 2x2 12 可行域的几种情况 空集s t x1 2x2 4x1 2x2 5x1 x2 0 1 4 2 3 5 1 2 3 x1 x2 x1 2x2 4 x1 2x2 5 最优点的几种情况 唯一解多重解无界解无可行解 线性规划的多重解 maxz x1 x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优点 最优解 6 4 8 6 0 x1 x2 maxz 2x1 x2s t x1 x2 2x1 2x2 0 x1 x2 0 线性规划无界解 1 4 2 3 5 1 2 3 x1 x2 x1 x2 2 z 2x1 x2 x1 2x2 0 无可行解 maxz x1 x2s t x1 2x2 4x1 2x2 5x1 x2 0 1 4 2 3 5 1 2 3 x1 x2 x1 2x2 4 x1 2x2 5 z x1 x2 线性规划的标准形式 线性规划标准型的简写形式 求和符号形式 线性规划标准型的简写形式 向量形式 线性规划标准型的简写形式 矩阵形式 线性规划标准型的简写形式 集合形式 线性规划的模型 线性规划模型的结构目标函数 max min约束条件 变量符号 0 unr 0线性规划的标准形式目标函数 max约束条件 变量符号 0 非标准形lp问题的标准化例题 非标准形lp问题的标准化 目标函数最小化最大化 z z不等式约束等式约束变量为负约束 无符号约束非负约束右端常数小于零非负等式两边均乘 1 松弛变量 剩余变量 线性规划问题的解及其性质 1 线性规划的解2 线性规划的基与基本可行解3 线性规划的基本定理 线性规划解的定义 1 满足线性规划问题所有约束条件的解是该问题的可行解 x x1 x2 xn t 2 线性规划问题全部可行解的集合构成线性规划问题的可行域 或称可行解集 r x ax b x 0 3 使目标函数达到极值的可行解称为线性规划问题的最优解 4 若对任意大的m 0 都存在可行解使得该线性规划的目标函数值 z cx m 则该线性规划问题无界 线性规划的基与基本可行解 基的定义 给定线性规划问题p max cx ax b x 0 a是m n满秩矩阵 n m 如果b是其中任一个m m满秩子矩阵 则称b是p的一个基 基变量与非基变量假定b由a中前m个列向量构成 约束矩阵可划分为 a b n 与基b对应的变量称为基变量 用xb表示 与非基n对应的变量称为非基变量 用xn表示 基本解 基本可行解 满足非负条件的基本解为基本可行解 该解对应的基b为可行基 如果基本可行解x 0则称该基本可行解为非退化解 非基变量为零 满足函数约束条件的解为基本解 考虑线性规划模型范例标准形maxz 3x1 5x2s t x1 x3 8x2 x4 123x1 4x2 x5 36x1 x2 x3 x4 x5 0注意 线性规划的基本解 基本可行解 极点 和可行基只与线性规划问题标准形式的约束条件有关 a p1 p2 p3 p4 p5 a矩阵包含以下10个3 3的子矩阵 b1 p1 p2 p3 b2 p1 p2 p4 b3 p1 p2 p5 b4 p1 p3 p4 b5 p1 p3 p5 b6 p1 p4 p5 b7 p2 p3 p4 b8 p2 p3 p5 b9 p2 p4 p5 b10 p3 p4 p5 由于b5 b9的行列式的值为0 不是基变量 非基变量为0 得到对应基b的解 如下x 1 4 6 4 0 0 t 对应b1 x 2 8 3 0 6 0 t 对应b2 x 3 8 6 0 0 12 t 对应b3 x 4 12 0 4 12 0 t 对应b4 x 6 8 0 0 12 3 t 对应b6 x 7 0 9 8 6 0 t 对应b7 x 8 0 6 8 0 12 t 对应b8 x 10 0 0 8 12 36 t 对应b10 是基本解 2 8 4 6 10 2 4 10 x1 x1 8 12 6 8 x1 x7 x8 x3 x10 x6 x2 x4 可行解 基本可行解 基本解 3 线性规划解的基本性质 定义1 设x1 xk是n维欧氏空间中的k个点 若存在 1 k 且满足0 i 1 i 1 k i 1 使得 x 1x1 kxk则称x是x1 xk的凸组合 定义2 集合c en称为凸集 如果对任意x1 x2 c 0 1 有 x1 1 x2 c 凸集没有凹陷部分 该集合内任取两点连线上的任何点都应该在集合内 在凸集中 不能表示为不同点的凸组合的点称为凸集的极点 用严格的定义描述如下 定义3设s为一凸集 且x s x1 s x2 s 对于0 1 若x x1 1 x2则必定有x x1 x2 则称x为s的一个极点 可以证明 线性规划的可行域以及最优解有以下性质 1 若线性规划的可行域非空 则可行域必定为一凸集 2 若线性规划的可行域非空 则至多有有限个极点 3 若线性规划有最优解 则至少有一个极点是最优解 这样 求线性规划最优解的问题 从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题 性质1 线性规划问题所有可行解组成的集合s x ax b x 0 是凸集 线性规划的可行域是由有限个 m个 超半空间的交集形成的 如果线性规划问题的可行域不空 是一个在n维空间的凸多面体 这类凸集又称为多面凸集 性质2 x是线性规划问题基本可行解的充要条件是x为可行域s x ax b x 0 的极点 这个结论被称为线性规划的基本定理 它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来 性质3 给定线性规划p max cx ax b x 0 a是秩为m的m n矩阵 i 若p存在可行解 则必存在基本可行解 ii 若p存在最优解 则必存在最优基本可行解 性质4 若线性规划问题的可行域r 则r至少有一个极点 r 可行域非空集 表明线性规划问题有可行解 则由性质3与性质2即可推出这条性质 性质5 线性规划问题可行域r的极点数目必为有限多个 基本可行解与极点一一对应阐述了可行域的极点只有有限个 并且说明可以通过求基本可行解的线性代数的方法来得到可行域的一切极点 从而有可能进一步获得最优极点 几何概念 代数概念 约束直线 满足一个等式约束的解 约束半平面 满足一个不等式约束的解 约束半平面的交集 凸多边形 满足一组不等式约束的解 约束直线的交点 基础解 可行域的极点 基础可行解 目标函数等值线 一组平行线 目标函数值等于一个常数的解 讨论 复习线性代数内容 列向量x x1 x2 xn t为n维列向量 x rn行向量x x1 x2 xn 为n维列向量 x rn矩阵 向量 运算规则加减乘 求逆运算结合律分配律交换律乘法无交换律线性相关一组向量v1 vn 如果有一组不全为零的系数 1 n 使得 1v1 nvn 0则称v1 vn是线性相关的 线性无