线性规划的图解法.ppt

1 第二章线性规划的图解法 1问题的提出 2图解法 3图解法的灵敏度分析 2 第二章线性规划的图解法 在管理中一些典型的线性规划应用合理利用线材问题 如何在保证生产的条件下 下料最少配料问题 在原料供应量的限制下如何获取最大利润投资问题 从投资项目中选取方案 使投资回报最大产品生产计划 合理利用人力 物力 财力等 使获利最大劳动力安排 用最少的劳动力来满足工作的需要运输问题 如何制定调运方案 使总运费最小 线性规划的组成 目标函数MaxF或MinF约束条件s t subjectto 满足于决策变量用符号来表示可控制的因素 3 1问题的提出 例1 某工厂在计划期内要安排 两种产品的生产 已知生产单位产品所需的设备台时及A B两种原材料的消耗 资源的限制 如下表 问题 工厂应分别生产多少单位 产品才能使工厂获利最多 线性规划模型 目标函数 Maxz 50 x1 100 x2 利润 约束条件 s t x1 x2 300 设备数量约束 2x1 x2 400 原料A数量约束 x2 250 原料B数量约束 x1 x2 0 4 1问题的提出 建模过程1 理解要解决的问题 了解解题的目标和条件 2 定义决策变量 x1 x2 xn 每一组值表示一个方案 3 用决策变量的线性函数形式写出目标函数 确定最大化或最小化目标 4 用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件一般形式目标函数 Max Min z c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 5 例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详细讲解其方法 6 2图解法 1 分别取决策变量X1 X2为坐标向量建立直角坐标系 在直角坐标系里 图上任意一点的坐标代表了决策变量的一组值 例1的每个约束条件都代表一个半平面 7 2图解法 2 对每个不等式 约束条件 先取其等式在坐标系中作直线 然后确定不等式所决定的半平面 x1 x1 x2 x2 8 2图解法 3 把五个图合并成一个图 取各约束条件的公共部分 如图2 1所示 x2 x1 C B A D E 9 2图解法 4 目标函数z 50 x1 100 x2 当z取某一固定值时得到一条直线 直线上的每一点都具有相同的目标函数值 称之为 等值线 平行移动等值线 当移动到B点时 z在可行域内实现了最大化 A B C D E是可行域的顶点 对有限个约束条件则其可行域的顶点也是有限的 x1 x2 z 20000 50 x1 100 x2 图2 2 z 27500 50 x1 100 x2 z 0 50 x1 100 x2 z 10000 50 x1 100 x2 C B A D E 10 2图解法 线性规划的标准化内容之一 引入松驰变量 含义是资源的剩余量 例1中引入s1 s2 s3模型化为目标函数 Maxz 50 x1 100 x2 0s1 0s2 0s3约束条件 s t x1 x2 s1 3002x1 x2 s2 400 x2 s3 250 x1 x2 s1 s2 s3 0对于最优解x1 50 x2 250 s1 0s2 50s3 0说明 生产50单位 产品和250单位 产品将消耗完所有可能的设备台时数及原料B 但原料A则还剩余50千克 11 2图解法 重要结论 如果线性规划有唯一最优解 则一定有一个可行域的顶点对应最优解 无穷多个最优解 若将例1中的目标函数变为maxz 50 x1 50 x2 则线段BC上的所有点都代表了最优解 12 x1 x2 图2 2 z 0 50 x1 50 x2 C B A D E 13 2图解法 重要结论 无界解 即可行域的范围延伸到无穷远 目标函数值可以无穷大或无穷小 一般来说 这说明模型有错 忽略了一些必要的约束条件 无可行解 若在例1的数学模型中再增加一个约束条件4x1 3x2 1200 则可行域为空域 不存在满足约束条件的解 当然也就不存在最优解了 14 15 进一步讨论 例2某公司由于生产需要 共需要A B两种原料至少350吨 A B两种材料有一定替代性 其中A原料至少购进125吨 但由于A B两种原料的规格不同 各自所需的加工时间也是不同的 加工每吨A原料需要2个小时 加工每吨B原料需要1小时 而公司总共有600个加工小时 又知道每吨A原料的价格为2万元 每吨B原料的价格为3万元 试问在满足生产需要的前提下 在公司加工能力的范围内 如何购买A B两种原料 使得购进成本最低 16 进一步讨论 解 目标函数 Minf 2x1 3x2 购买成本 约束条件 s t x1 x2 350 总量约束 x1 125 A量的约束 2x1 x2 600 加工工时的约束 x1 x2 0 17 进一步讨论 采用图解法 如下图 得Q点坐标 250 100 为最优解 18 3图解法的灵敏度分析 线性规划的标准化一般形式目标函数 Max Min z c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0标准形式目标函数 Maxz c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 bi 0 19 3图解法的灵敏度分析 可以看出 线性规划的标准形式有如下四个特点 目标最大化 约束为等式 决策变量均非负 右端项非负 对于各种非标准形式的线性规划问题 我们总可以通过以下变换 将其转化为标准形式 20 3图解法的灵敏度分析 1 极小化目标函数的问题 设目标函数为Minf c1x1 c2x2 cnxn 可以 令z f 则该极小化问题与下面的极大化问题有相同的最优解 即Maxz c1x1 c2x2 cnxn但必须注意 尽管以上两个问题的最优解相同 但它们最优解的目标函数值却相差一个符号 即Minf Maxz 21 3图解法的灵敏度分析 2 约束条件不是等式的问题 设约束条件为ai1x1 ai2x2 ainxn bi可以引进一个新的变量s 使它等于约束右边与左边之差s bi ai1x1 ai2x2 ainxn 显然 s也具有非负约束 即s 0 这时新的约束条件成为ai1x1 ai2x2 ainxn s bi 22 3图解法的灵敏度分析 当约束条件为ai1x1 ai2x2 ainxn bi时 类似地令s ai1x1 ai2x2 ainxn bi显然 s也具有非负约束 即s 0 这时新的约束条件成为ai1x1 ai2x2 ainxn s bi 23 3图解法的灵敏度分析 为了使约束由不等式成为等式而引进的变量s 当不等式为 小于等于 时称为 松弛变量 当不等式为 大于等于 时称为 剩余变量 如果原问题中有若干个非等式约束 则将其转化为标准形式时 必须对各个约束引进不同的松弛变量 3 右端项有负值的问题 在标准形式中 要求右端项必须每一个分量非负 当某一个右端项系数为负时 如bi 0 则把该等式约束两端同时乘以 1 得到 ai1x1 ai2x2 ainxn bi 24 3图解法的灵敏度分析 例 将以下线性规划问题转化为标准形式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 25 3图解法的灵敏度分析 通过以上变换 可以得到以下标准形式的线性规划问题 Maxz 2x1 3x2 4x3s t 3x1 4x2 5x3 x4 62x1 x3 x5 8 x1 x2 x3 9x1 x2 x3 x4 x5 0 26 3图解法的灵敏度分析 4 变量无符号限制的问题 就是取值无约束在标准形式中 必须每一个变量均有非负约束 当某一个变量xj没有非负约束时 可以令xj xj xj 其中xj 0 xj 0即用两个非负变量之差来表示一个无符号限制的变量 当然xj的符号取决于xj 和xj 的大小 27 3图解法的灵敏度分析 例 将以下线性规划问题转化为标准形式Minf 2x1 3x2 4x3s t 3x1 4x2 5x3 62x1 x3 8x1 x2 x3 9x1 x2 0 x3 0解 首先 将目标函数转换成极大化 令z f 2x1 3x2 4x3其次考虑约束 有2个不等式约束 引进松弛变量x4 x5 0 第三个约束条件的右端值为负 在等式两边同时乘 1 第三个变量x3为负约束时 可以令x3 x3 28 3图解法的灵敏度分析 通过以上变换 可以得到以下标准形式的线性规划问题 Maxz 2x1 3x2 4x3 s t 3x1 4x2 5x3 x4 62x1 x3 x5 8 x1 x2 x3 9x1 x2 x3 x4 x5 0 29 3图解法的灵敏度分析 例 将以下线性规划问题转化为标准形式Minf 2x1 3x2 4x3s t 3x1 4x2 5x3 62x1 x3 8x1 x2 x3 9x1 x2 0解 首先 将目标函数转换成极大化 令z f 2x1 3x2 4x3其次考虑约束 有2个不等式约束 引进松弛变量x4 x5 0 第三个约束条件的右端值为负 在等式两边同时乘 1 变量x3没有非负约束 可以令x3 x3 x3 其中x3 0 x3 0 30 3图解法的灵敏度分析 通过以上变换 可以得到以下标准形式的线性规划问题 Maxz 2x1 3x2 4 x3 x3 s t 3x1 4x2 5 x3 x3 x4 62x1 x3 x3 x5 8 x1 x2 x3 x3 9x1 x2 x3 x3 x4 x5 0 31 3图解法的灵敏度分析 灵敏度分析 建立数学模型和求得最优解后 研究线性规划的一个或多个参数 系数 ci aij bj变化时 对最优解产生的影响 3 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 时 原最优解仍是最优解 32 33 3图解法的灵敏度分析 假设产品 的利润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 34 3图解法的灵敏度分析 3 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元利润 称为该约束条件的对偶价格 就是该设备不适用 而应用于出租时 不亏损的最低价格 35 3图解法的灵敏度分析 假设原料A增加10千克时 即b2变