线性规划图解法和单纯形法PPT课件.ppt

Chapter1线性规划 LinearProgramming LP的数学模型图解法单纯形法单纯形法的进一步讨论 人工变量法LP模型的应用 本章主要内容 线性规划问题的数学模型 1 规划问题 生产和经营管理中经常提出如何合理安排 使人力 物力等各种资源得到充分利用 获得最大的效益 这就是规划问题 线性规划通常解决下列两类问题 1 当任务或目标确定后 如何统筹兼顾 合理安排 用最少的资源 如资金 设备 原标材料 人工 时间等 去完成确定的任务或目标 2 在一定的资源条件限制下 如何组织安排生产获得最好的经济效益 如产品量最多 利润最大 线性规划问题的数学模型 例1 1如图所示 如何截取x使铁皮所围成的容积最大 线性规划问题的数学模型 例1 2某厂生产两种产品 下表给出了单位产品所需资源及单位产品利润 问 应如何安排生产计划 才能使总利润最大 解 1 决策变量 设产品I II的产量分别为x1 x2 2 目标函数 设总利润为z 则有 maxz 2x1 x2 3 约束条件 x1 3 8 x2 1 2 z 22 8 线性规划问题的数学模型 例1 3已知资料如下表所示 问如何安排生产才能使利润最大 或如何考虑利润大 产品好销 解 1 决策变量 设产品I II的产量分别为x1 x2 2 目标函数 设总利润为z 则有 maxz 2x1 x2 3 约束条件 线性规划问题的数学模型 例1 4某厂生产三种药物 这些药物可以从四种不同的原料中提取 下表给出了单位原料可提取的药物量 解 要求 生产A种药物至少160单位 B种药物恰好200单位 C种药物不超过180单位 且使原料总成本最小 1 决策变量 设四种原料的使用量分别为 x1 x2 x3 x4 2 目标函数 设总成本为zminz 5x1 6x2 7x3 8x4 3 约束条件 例1 5某航运局现有船只种类 数量以及计划期内各条航线的货运量 货运成本如下表所示 问 应如何编队 才能既完成合同任务 又使总货运成本为最小 线性规划问题的数学模型 解 设 xj为第j号类型船队的队数 j 1 2 3 4 z为总货运成本 则 minz 36x1 36x2 72x3 27x4 线性规划问题的数学模型 线性规划问题的数学模型 2 线性规划的数学模型由三个要素构成 决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints 其特征是 1 问题的目标函数是多个决策变量的线性函数 通常是求最大值或最小值 2 问题的约束条件是一组多个决策变量的线性不等式或等式 怎样辨别一个模型是线性规划模型 线性规划问题的数学模型 3 建模条件 1 优化条件 问题所要达到的目标能用线型函数描述 且能够用极值 max或min 来表示 2 限定条件 约束条件 达到目标受到一定的限制 且这些限制能够用决策变量的线性等式或线性不等式表示 3 选择条件 有多种可选择的方案供决策者选择 以便找出最优方案 线性规划问题的数学模型 4 建模步骤 1 确定决策变量 即需要我们作出决策或选择的量 一般情况下 题目问什么就设什么为决策变量 2 找出所有限定条件 即决策变量受到的所有的约束 3 写出目标函数 即问题所要达到的目标 并明确是max还是min 线性规划问题的数学模型 目标函数 约束条件 5 线性规划数学模型的一般形式 简写为 线性规划问题的数学模型 向量形式 其中 线性规划问题的数学模型 矩阵形式 其中 线性规划问题的数学模型 6 线性规划问题的标准形式 特点 1 目标函数求最大值 有时求最小值 2 约束条件都为等式方程 且右端常数项bi都大于或等于零 3 决策变量xj为非负 线性规划问题的数学模型 2 如何化标准形式 目标函数的转换 如果是求极小值即 则可将目标函数乘以 1 可化为求极大值问题 也就是 令 可得到上式 即 若存在取值无约束的变量 可令其中 变量的变换 线性规划问题的数学模型 约束方程的转换 由不等式转换为等式 称为松弛变量 称为剩余变量 常量bi 0的变换 约束方程两边乘以 1 线性规划问题的数学模型 例1 6将下列线性规划问题化为标准形式 用替换 且 解 因为x3无符号要求 即x3取正值也可取负值 标准型中要求变量非负 所以 线性规划问题的数学模型 2 第一个约束条件是 号 在 左端加入松驰变量x4 x4 0 化为等式 3 第二个约束条件是 号 在 左端减去剩余变量x5 x5 0 4 第3个约束方程右端常数项为 5 方程两边同乘以 1 将右端常数项化为正数 5 目标函数是最小值 为了化为求最大值 令z z 得到maxz z 即当z达到最小值时z 达到最大值 反之亦然 线性规划问题的数学模型 标准形式如下 例1 7将下列线性规划问题化为标准形式 为无约束 无非负限制 线性规划问题的数学模型 解 用替换 且 将第3个约束方程两边乘以 1 将极小值问题反号 变为求极大值 标准形式如下 引入变量 线性规划问题的数学模型 例1 8将线性规划问题化为标准型 解 线性规划问题的数学模型 例1 9将线性规划问题化为标准型 解 Minf 3x1 5x2 8x3 7x4s t 2x1 3x2 5x3 6x4 284x1 2x2 3x3 9x4 396x2 2x3 3x4 58x1 x3 x4 0 x2无约束 Maxz 3x1 5x2 5x2 8x3 7x4s t 2x1 3x2 3x2 5x3 6x4 x5 284x1 2x2 2x2 3x3 9x4 x6 39 6x2 6x2 2x3 3x4 x7 58x1 x2 x2 x3 x4 x5 x6 x7 0 线性规划问题的数学模型 线性规划问题的数学模型 7 线性规划问题的解 线性规划问题 求解线性规划问题 就是从满足约束条件 2 3 的方程组中找出一个解 使目标函数 1 达到最大值 线性规划问题的数学模型 可行解 满足约束条件 的解为可行解 所有可行解的集合为可行域 最优解 使目标函数达到最大值的可行解 基 设A为约束条件 的m n阶系数矩阵 m n 其秩为m B是矩阵A中m阶满秩子方阵 B 0 称B是规划问题的一个基 设 称B中每个列向量Pj j 1 2 m 为基向量 与基向量Pj对应的变量xj为基变量 除基变量以外的变量为非基变量 线性规划问题的数学模型 基解 某一确定的基B 令非基变量等于零 由约束条件方程 解出基变量 称这组解为基解 在基解中变量取非零值的个数不大于方程数m 基解的总数不超过基可行解 满足变量非负约束条件的基本解 简称基可行解 可行基 对应于基可行解的基称为可行基 线性规划问题的数学模型 例1 10求线性规划问题的所有基矩阵 解 约束方程的系数矩阵为2 5矩阵 r A 2 2阶子矩阵有10个 其中基矩阵只有9个 即 图解法 线性规划问题的求解方法 一般有两种方法 图解法单纯形法 两个变量 直角坐标三个变量 立体坐标 适用于任意变量 但必需将一般形式变成标准形式 下面我们分析一下简单的情况 只有两个决策变量的线性规划问题 这时可以通过图解的方法来求解 图解法具有简单 直观的优点 便于初学者窥探线性规划基本原理和几何意义 解题步骤 4将最优解代入目标函数 求出最优值 1在直角平面坐标系中画出所有的约束等式 并找出所有约束条件的公共部分 称为可行域 可行域中的点即为可行解 2标出目标函数值增加或者减小的方向 3若求最大 小 值 则令目标函数等值线沿 逆 目标函数值增加的方向平行移动 找与可行域最后相交的点 该点就是最优解 图解法 图解法 maxZ 2X1 X2X1 1 9X2 3 8X1 1 9X2 3 8s t X1 1 9X2 10 2X1 1 9X2 3 8X1 X2 0 例1 11用图解法求解线性规划问题 图解法 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 4 2X1 X2 20 2X1 X2 17 2 2X1 X2 Lo 0 2X1 X2 7 6 2 D maxZ minZ 此点是唯一最优解 且最优目标函数值maxZ 17 2 可行域 maxZ 2X1 X2 图解法 maxZ 3X1 5 7X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 7 6 2 D L0 0 3X1 5 7X2 maxZ 3 8 4 34 2 3X1 5 7X2 蓝色线段上的所有点都是最优解这种情形为有无穷多最优解 但是最优目标函数值maxZ 34 2是唯一的 可行域 图解法 minZ 5X1 4X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 D L0 0 5X1 4X2 maxZ minZ 8 5X1 4X2 43 5X1 4X2 0 2 可行域 此点是唯一最优解 图解法 2 4 6 x1 x2 2 4 6 无界解 无最优解 maxZ x1 2x2 例1 6 x1 x2 4 x1 3x2 6 3x1 x2 6 maxZ minZ x1 x2 O 10 20 30 40 10 20 30 40 50 50 无可行解 即无最优解 maxZ 3x1 4x2 例1 7 由图解法得到的几种情况 根据以上例题 进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况 1 可行域为封闭的有界区域 a 有唯一的最优解 b 有无穷多个最优解 2 可行域为封闭的无界区域 c 有唯一的最优解 d 有无穷多个最优解 e 目标函数无界 即虽有可行解 但在可行域中 目标函数可以无限增大或无限减少 因而没有有限最优解 3 可行域为空集 f 没有可行解 原问题无最优解 图解法 由图解法得到的启示 线性规划问题解的情况 唯一最优解 无穷多最优解 无界解 无可行解 2 线性规划问题的可行域是凸集 凸多边形 图解法 图解法 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 17 2 2X1 X2 Lo 0 2X1 X2 7 6 2 D maxZ minZ 可行域 maxZ 2X1 X2 3 最优解一定是在凸集的某个顶点 解题思路先找出凸集的任一顶点 计算其目标函数值 再与周围顶点的目标函数值比较 如不是最大 或最小 继续比较 直到找出最大 或最小 为止 图解法 图解法 学习要点 1 通过图解法了解线性规划有几种解的形式 唯一最优解 无穷多最优解 无界解 无可行解 2 作图的关键有三点 1 可行解区域要画正确 2 目标函数增加的方向不能画错 3 目标函数的直线怎样平行移动 连接几何形体中任意两点的线段仍完全在该几何形体之中 有限个凸集的交集仍然是凸集 单纯形法基本原理 凸集 单纯形法基本原理 凸集 如果集合C中任意两个点X1 X2 其连线上的所有点也都是集合C中的点 称C为凸集 单纯形法基本原理 顶点 如果凸集C中不存在任何两个不同的点X1 X2 使X成为这两个点连线上的一个点 2019 12 29 45 单纯形法基本原理 定理1 若线性规划问题存在可行解 则该问题的可行域是凸集 定理2 线性规划问题的基可行解X对应可行域 凸集 的顶点 定理3 若问题存在最优解 一定存在一个基可行解是最优解 即在某个顶点取得 几个基本定理的证明 定理1若线性规划问题存在可行解 则问题的可行域是凸集 思路 若满足线性规划约束条件的所有点组成的几何图形C是凸集 根据凸集的定义 C内任意两点X1 X2连线上的点也必然在C内 证 设为C内任意两点 即 将X1 X2代入约束条件有X1 X2连线上任意一点可以表示为 将 1 9 代入约束条件并由式 1 8 得 所以 由于集合内任意两点连线上的点均在集合内 所以C为凸集 一个引理 引理线性规划问题的可行解为基可行解的的充要条件是X的正分量所对应的系数列向量是线性独立的 证 必要性由基可行解的定义是显然的 充分性 若向量P1 P2 Pk是线性独立的 则必有k m 1 当k m时 它们恰好构成一个基 从而相应的基可行解为2 当k m时 则一定可以从其余列向量中找出 m k 个向量与P1 P2 Pk构成一个基 其对应的解恰为X 根据定义它是基可行解 定理2线性规划问题的基可行解X对应于线性规划问题可行域 凸集 的顶点 本定理需要证明 X是可行域顶点 X是基可行解 采用的是反证法 即证明X不是可行域的顶点 X不是基可行解 证 1 X不是基可行解 X不是可行域的顶点 不失一般性 假设X的前m个分量为正 故有根据假设X不是基可行解 由引理知线性相关 即存在一组不全为零的数使得有 上式乘上一个不为零的数 得 令即X不是可行域的顶点 2 X不是可行域的顶点 X不是基可行解 不失一般性 设不是可行域的顶点 因而可以找到可行域内另外两个不同点Y和Z 有 或可写为 因 故当时 必有因有 故有两式相减得因不全为零 故线性相关 由引理知X不是基可行解 定理3若线性规划问题有最优解 一定存在一个基可行解是最优解 证 设是线性规划的一个最优解 是目标函数的最大值 若不是基可行解 由定理2知不是顶点 一定能在可行域内找到通过的直线上的另外两个点将这两个点代入目标函数有 因为目标函数的最大值 故有由此 即有如果仍不是基可行解 按上面的方法继续做下去 最后一定可以到到一个基可行解 其目标函数值等于 问题得证 单纯形法的计算步骤 单纯形法的思路 找出一个初始可行解 是否最优 转移到另一个基本可行解 找出更大的目标函数值 最优解 是 否 循环 核心是 变量迭代 结束 STEP1确定初始基可行解当线性规划的约束条件全部为 时 在第i个约束条件上加上松弛变量xsi i 1 m 化为标准形式 那么约束方程满足的系数矩阵为该矩阵中含一个单位矩阵 只要以此作为基 就可以立即解出基变量的值xsi bi i 1 m 因为有bi 0 i 1 m 由此得到X 0 0 b1 bm T就是一个基可行解 当线性规划约束条件为 或者 时 化为标准形后 一般约束条件的系数矩阵也不含有单位矩阵 人工基 初始可行解 人工变量法 STEP2从初始基可行解转化为另一基可行解设初始基可行解为 其中非零坐标有m个 不失一般性 假定前m个坐标为非零 即可行基为 P1P2 Pm 因 故有写出其系数矩阵的增广矩阵 用构造人工基的方法可以使基矩阵是单位矩阵形式 因为是一个基 其他向量可用这个基的线性组合来表示将 1 16 式乘上一个正的数 0得 式 1 15 式 1 17 并经过整理后有由上式找到满足约束方程组的另外一个点 其中 是的第j个坐标的值 要使是一个基可行解 因 0 故应对所有i 1 m存在且这m个不等式中至少有一个等号成立 因为当时 上式显然成立 这样中正分量最多有m个 容易证明m个向量线性无关 故只需按式 1 20 来确定 的值 就是一个新的基可行解 令 基本可行解和可行基的变换 基本可行解 可行基 换出基 换入基 STEP3最优性检验和解的判别将基可行解分别代入目标函数得因 0为给定 所以只要有通常简写为 它是对线性规划问题的解进行最优性检验的标志 当所有的时 表明现有顶点 基可行解 的目标函数值比起相邻各顶点 基可行解 的目标函数值都大 现有顶点对应的基可行解即为最优解 当所有时 对某个非基变量xj有 且按公式 1 20 可找到 0 这表明可以找到另一顶点 基可行解 目标函数也达到最大 由于该两点连线上的点也属可行域内的点 且目标函数值相等 即该线性规划问题有无穷多最优解 如果存在某个又Pj向量的所有分量aij 0 换基时对任意 0 恒有因 取值可无限大 在由X 0 换到X 1 时目标函数值也可无限大 则线性规划问题存在无界解 引例 求解线性规划问题 LP规划问题的最优解可从基可行解 顶点 中找到 图解法有局限性 枚举法计算量大 解 第一 将该问题化成标准形 第二 找初始可行解 即一个顶点 系数矩阵A P1P2P3P4P5 矩阵形式 因为P3 P4 P5线性独立 故B P3 P4 P5 构成一个基 其对应的基变量x3 x4 x5 解出来为 用非基变量表示基变量 x3 8 x1 2x2x4 16 4x1 1 x5 12 4x2 XB B 1b B 1NXN 将 1 代入目标函数中得z 0 2x1 3x2令非基变量x1 x2 0 则有z 0 这时得到一个基可行解 X 0 0 0 8 16 12 T 原点 第三 判别从目标函数z 0 2x1 3x2中得知 非基变量x1和x2的系数为正 因此 将非基变量换入基后可使目标函数增大 转入第四步 第四 换基 旋转迭代 确定换入变量 由于非基变量x2的系数 正 贡献最大 故需换入的基变量为x2 换入变量已定 必须从x3 x4 x5换出一个 并且要保证其余均是非负的 即x3 x4 x5 0 当x1 0时 有 x3 8 2x2 0 x4 16 0 x5 12 4x2 0 x2换入基 x1未换入 还是非基变量 只要选择x2 min 8 2 12 4 3 对应基变量x5 0 从而确定用x2和x5对换 即将x5换出 用非基变量表示基变量 2x2 x3 8 x1x4 16 4x14x2 12 x5用高斯消去法 行变换 得x3 2 x1 1 2x5x4 16 4x1x2 3 1 4x5 2 将上式代入原目标函数中得z 9 2x1 3 4x5 1 返回第三步 从z 9 2x1 3 4x5 非基变量x1的系数是正的 还可增大 重复上述步骤 由于x1的系数是正的 则x1为转入变量 再由当x5 0时x3 2 x1 0 x4 16 4x1 0 x2 3 0 只要选x1 min 2 16 4 2上式就成立 因为x1 2时 基变量x3 0 从而由x1换出x3 令非基变量x1和x5为零有z 9 又得到另一个基可行解X 1 0 3 2 16 0 T 顶点Q4 x1 2x2 8 x34x1 x4 16 3 4x2 12 x5高斯消去法 行变换 得 x1 2 x3 1 2x5 0 x4 8 2x5 4x3 0 x2 3 1 4x5 0 代入目标函数中 得z 13 2x3 1 4x5令非基变量x3 x5 0有z 13 又得到另一个基可行解X 2 2 3 0 8 0 T 顶点Q3 2 用非基变量表示基变量 同理 返回第三步 再迭代 x5作为转入变量 只要取x5 min 8 2 12 4就有上式成立 x5 4时 x4 0 故用x5换x4x1 4 1 4x4x5 4 1 2x4 2x3x2 2 1 8x4 1 2x3 令x3 0 有 x1 2 1 2x5 0 x4 8 2x5 0 x2 3 1 4x5 0 3 高斯 0 Q4 Q3 Q2 Q1 代入得z 14 3 2x3 1 8x4 令x3 x4 0得z 14 新的基可行解为X 3 4 2 0 0 4 T 顶点Q2 最优解 最优目标值z 14 0 3 2 16 0 0 0 8 16 12 2 3 0 8 0 4 2 0 0 4 单纯形法的计算步骤 单纯形表 确定换出基 确定换入基 单纯形法的计算步骤 例1 12用单纯形法求下列线性规划的最优解 解 1 将问题化为标准型 加入松驰变量x3 x4则标准型为 单纯形法的计