第2章__线性规划的图解法.ppt

第二章线性规划的图解法 1问题的提出 2图解法 3图解法的灵敏度分析 线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式 第一节线性规划问题及其数学模型 问题的提出 例1 生产计划问题 决策变量 Decisionvariables 目标函数 Objectivefunction 约束条件 Constraintconditions 可行域 Feasibleregion 最优解 Optimalsolution 基本概念 问题中要确定的未知量 表明规划中的用数量表示的方案 措施 可由决策者决定和控制 它是决策变量的函数 指决策变量取值时受到的各种资源条件的限制 通常表达为含决策变量的等式或不等式 满足约束条件的决策变量的取值范围 可行域中使目标函数达到最优的决策变量的值 是问题中要确定的未知量 表明规划中的用数量表示的方案 措施 可由决策者决定和控制 第1步 确定决策变量 设 I的产量 II的产量 利润 第2步 定义目标函数 MaxZ x1 x2 MaxZ 50 x1 100 x2 第2步 定义目标函数 第3步 表示约束条件 x1 x2 3002x1 x2 400 x2 250 x1 x2 0 该计划的数学模型 目标函数MaxZ 50 x1 100 x2约束条件x1 x2 3002x1 x2 400 x2 250 x1 x2 0 x1 x2 例2 某工厂拥有A B C三种类型的设备 生产甲 乙两种产品 每件产品在生产中需要占用的设备机时数 每件产品可以获得的利润以及三种设备可利用的时数如下表所示 问题 工厂应如何安排生产可获得最大的总利润 解 设变量xi为第i种 甲 乙 产品的生产件数 i 1 2 根据题意 我们知道两种产品的生产受到设备能力 机时数 的限制 对设备A 两种产品生产所占用的机时数不能超过65 于是我们可以得到不等式 3x1 2x2 65 对设备B 两种产品生产所占用的机时数不能超过40 于是我们可以得到不等式 2x1 x2 40 对设备C 两种产品生产所占用的机时数不能超过75 于是我们可以得到不等式 3x2 75 另外 产品数不可能为负 即x1 x2 0 同时 我们有一个追求目标 即获取最大利润 于是可写出目标函数z为相应的生产计划可以获得的总利润 z 1500 x1 2500 x2综合上述讨论 在加工时间以及利润与产品产量成线性关系的假设下 把目标函数和约束条件放在一起 可以建立如下的线性规划模型 目标函数Maxz 1500 x1 2500 x2约束条件s t 3x1 2x2 652x1 x2 403x2 75x1 x2 0 线性规划问题的共同特征 一组决策变量X表示一个方案 一般X大于等于零 约束条件是线性等式或不等式 目标函数是线性的 求目标函数最大化或最小化 建模过程1 理解要解决的问题 了解解题的目标和条件 2 定义决策变量 x1 x2 xn 每一组值表示一个方案 3 用决策变量的线性函数形式写出目标函数 确定最大化或最小化目标 4 用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 线性规划模型的一般形式 线性规划问题的标准形式 标准形式为 目标函数最大约束条件等式决策变量非负右端项非负 标准形式可以简写为 线性规划的标准形式有如下四个特点 目标最大化 约束为等式 决策变量均非负 右端项非负 对于各种非标准形式的线性规划问题 我们总可以通过以下变换 将其转化为标准形式 1 极小化目标函数的问题 设目标函数为Minf c1x1 c2x2 cnxn则可以令z f 该极小化问题与下面的极大化问题有相同的最优解 即Maxz c1x1 c2x2 cnxn但必须注意 尽管以上两个问题的最优解相同 但他们最优解的目标函数值却相差一个符号 即Minf Maxz 一般线性规划问题的标准形化 2 约束条件不是等式的问题 约束 加入非负松驰变量 例 目标函数MaxZ 2x1 3x2约束条件x1 2x2 84x1 164x2 12x1 x2 0 例 例 将以下线性规划问题转化为标准形式Minf 3 6x1 5 2x2 1 8x3s t 2 3x1 5 2x2 6 1x3 15 74 1x1 3 3x3 8 9x1 x2 x3 38x1 x2 x3 0 解 首先 将目标函数转换成极大化 令z f 3 6x1 5 2x2 1 8x3 当 约束 减去非负剩余变量 其次考虑约束 有2个不等式约束 引进松弛变量x4 0 剩余变量x5 0 于是 我们可以得到以下标准形式 Maxz 3 6x1 5 2x2 1 8x3s t 2 3x1 5 2x2 6 1x3 x4 15 74 1x1 3 3x3 x5 8 9x1 x2 x3 38x1 x2 x3 x4 x5 0 3 变量无符号限制的问题 在标准形式中 必须每一个变量均有非负约束 当某一个变量xj没有非负约束时 可以令xj xj xj 其中xj 0 xj 0即用两个非负变量之差来表示一个无符号限制的变量 当然xj的符号取决于xj 和xj 的大小 例 Max 解 标准形为 4 右端项有负值的问题 在标准形式中 要求右端项必须每一个分量非负 当某一个右端项系数为负时 如bi 0 则把该等式约束两端同时乘以 1 得到 ai1x1 ai2x2 ainxn bi 练习题 将以下线性规划问题转化为标准形式Minf 3x1 5x2 8x3 7x4s t 2x1 3x2 5x3 6x4 284x1 2x2 3x3 9x4 396x2 2x3 3x4 58x1 x3 x4 0 解 首先 将目标函数转换成极大化 令z f 3x1 5x2 8x3 7x4 其次考虑约束 有3个不等式约束 引进松弛变量x5 x6 x7 0 由于x2无非负限制 可令x2 x2 x2 其中x2 0 x2 0 由于第3个约束右端项系数为 58 于是把该式两端乘以 1 于是 我们可以得到以下标准形式的线性规划问题 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 例 将以下线性规划问题转化为标准形式Minf 2x1 3x2 4x3s t 3x1 4x2 5x3 62x1 x3 8x1 x2 x3 9x1 x2 x3 0 解 首先 将目标函数转换成极大化 令z f 2x1 3x2 4x3其次考虑约束 有2个不等式约束 引进松弛变量x4 x5 0 第三个约束条件的右端值为负 在等式两边同时乘 1 通过以上变换 可以得到以下标准形式的线性规划问题 Maxz 2x1 3x2 4x3s t 3x1 4x2 5x3 x4 62x1 x3 x5 8 x1 x2 x3 9x1 x2 x3 x4 x5 0 练习建立LP数学模型有两个煤厂A B 每月分别供应三个居民区X Y Z 求运费最少的方案 例1 目标函数 Maxz 50 x1 100 x2约束条件 s t x1 x2 300 A 2x1 x2 400 B x2 250 C x1 0 D x2 0 E 得到最优解 x1 50 x2 250最优目标值z 27500 2图解法 对于只有两个决策变量的线性规划问题 可以在平面直角坐标系上作图表示线性规划问题的有关概念 并求解 下面通过例1详细讲解其方法 2图解法 1 分别取决策变量X1 X2为坐标向量建立直角坐标系 在直角坐标系里 图上任意一点的坐标代表了决策变量的一组值 例1的每个约束条件都代表一个半平面 2 对每个不等式 约束条件 先取其等式在坐标系中作直线 然后确定不等式所决定的半平面 3 把五个图合并成一个图 取各约束条件的公共部分 如图所示 4 目标函数z 50 x1 100 x2 当z取某一固定值时得到一条直线 直线上的每一点都具有相同的目标函数值 称之为 等值线 平行移动等值线 当移动到B点时 z在可行域内实现了最大化 A B C D E是可行域的顶点 对有限个约束条件则其可行域的顶点也是有限的 重要结论 如果线性规划有最优解 则一定有一个可行域的顶点对应一个最优解 无穷多个最优解 若将例1中的目标函数变为maxz 50 x1 50 x2 则线段BC上的所有点都代表了最优解 无界解 即可行域的范围延伸到无穷远 目标函数值可以无穷大或无穷小 一般来说 这说明模型有错 忽略了一些必要的约束条件 无可行解 若在例1的数学模型中再增加一个约束条件4x1 3x2 1200 则可行域为空域 不存在满足约束条件的解 当然也就不存在最优解了 图解法的几点结论 由图解法得到的启示 可行域是有界或无界的凸多边形 若线性规划问题存在最优解 它一定可以在可行域的顶点得到 若两个顶点同时得到最优解 则其连线上的所有点都是最优解 解题思路 找出凸集的顶点 计算其目标函数值 比较即得 例2某公司由于生产需要 共需要A B两种原料至少350吨 A B两种材料有一定替代性 其中A原料至少购进125吨 但由于A B两种原料的规格不同 各自所需的加工时间也是不同的 加工每吨A原料需要2个小时 加工每吨B原料需要1小 而公司总共有600个加工小时 又知道每吨A原料的价格为2万元 每吨B原料的价格为3万元 试问在满足生产需要的前提下 在公司加工能力的范围内 如何购买A B两种原料 使得购进成本最低 解 目标函数 Minf 2x1 3x2约束条件 s t x1 x2 350 x1 1252x1 x2 600 x1 x2 0采用图解法 如下图 得Q点坐标 250 100 为最优解 3图解法的灵敏度分析 灵敏度分析 建立数学模型和求得最优解后 研究线性规划的一个或多个参数 系数 ci aij bj变化时 对最优解产生的影响 1 目标函数中的系数ci的灵敏度分析考虑例1的情况 ci的变化只影响目标函数等值线的斜率 目标函数z 50 x1 100 x2在z x2 x2 z斜率为0 到z x1 x2 x2 x1 z斜率为 1 之间时 原最优解x1 50 x2 100仍是最优解 一般情况 z c1x1 c2x2写成斜截式x2 c1 c2 x1 z c2 目标函数等值线的斜率为 c1 c2 当 1 c1 c2 0 时 原最优解仍是最优解 假设产品 的利润100元不变 即c2 100 代到式 并整理得0 c1 100假设产品 的利润50元不变 即c1 50 代到式 并整理得50 c2 假若产品 的利润均改变 则可直接用式 来判断 假设产品 的利润分别为60元 55元 则 2 60 55 1那么 最优解为z x1 x2和z 2x1 x2的交点x1 100 x2 200 2 约束条件中右边系数bj的灵敏度分析当约束条件中右边系数bj变化时 线性规划的可行域发生变化 可能引起最优解的变化 考虑例1的情况 假设设备台时增加10个台时 即b1变化为310 这时可行域扩大 最优解为x2 250和x1 x2 310的交点x1 60 x2 250 变化后的总利润 变化前的总利润 增加的利润 50 60 100 250 50 50 100 250 500 500 10 50元说明在一定范围内每增加 减少 1个台时的设备能力就可增加 减少 50元利润 称为该约束条件的对偶价格 假设原料A增加10