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

例2.1 某工厂计划用现有的铜、铅两种资源生产甲、乙电缆，生产甲、乙两种电缆的单位售价及资源消耗如下表所示： 一、线性数学模型的建立： LP的基本概念 二、线性规划模型的求解(方法)： 第2节 图解法 条件：只有两个变量的线性规划问题 理解: X1,x2代表两个数轴： 目标函数：是一条直线（视Z为常量） 约束条件：是等式或不等式，代表直线或直线的上方或下方； 练习题：教材P24 第1题 线性规划的标准型规定为： 线性规划标准型 1.目标函数求最大值(也有的教材规定为求最小) 2.约束条件均为等式方程; 3.变量Xi为非负; 4.常数bj都大于或等于零. 线性规划的标准化过程中还有没有其它问题要处理？ 在第i个约束条件为≥型，在不等式的左边减去一个非负的变量Si,称为剩余变量；同时令相应的Ci,=0。结果如下： 转化过程 对约束条件进行处理： 1、对=的加上一个非负变量si 使之左右相等； 2、对=的减去一个非负变量sJ 使之左右相等； 减去的变量称为剩余量(surplus variable ) 加上的变量称为松弛量(slack variable ) 3、对目标函数:加系数0处理Si量 练习：线性规划模型的标准化 P25 第3题， 第3节 图解法的灵敏度分析 一、线性规划的标准化 线性规划的标准型规定为： 二、灵敏度分析 例2.1 某工厂计划用现有的铜、铅两种资源生产甲、乙电缆，生产甲、乙两种电缆的单位售价及资源消耗如下表所示： 二、灵敏度分析 二、灵敏度分析 当产品A或B的价格系数发生变化时，增加或减少时，是大利润将发生变化，也就将改变最优解。我们现在就要求出系数的最大变化范围。Ci改变时，Z不变。 从图中可知，直线F的斜率K=0 直线E的斜率K=-1 而目标函数: z=C1x1+c2x2 的斜率k=-C1/C2 那么，当 -1≤ -c1/c2 ≤ 0时顶点B仍然是最优解 先来固定C2=100,让C1变化,讨论C1的变化范围,使得Z不变. 当C1和C2同时变化时，则可通过不等式： 三、约束条件中右边系数bj的灵敏度分析 讨论bj的变化范围，使得Z最优解不变。 由于bj的变化，使得可行域发生变化，变大或缩小； 由于新增10台时，增加了500元利润，故在300台时的基础上，每增加1台时可增加500/10=50元的利润，这个增加量被称为该约束条件的对偶价格（简称为对偶价格）。 现修改另一个右边系数B2： 原料A增加10千克，而利润增加为0元，27500-27500=0元；故原料A的对偶价格为0元，（理由是原料A还有剩余未用完，即使增加数量，仍然用不上，故利润不影响）。 约束条件的对偶价格性质： （1）如果对偶价格大于0，则其最优目标函数值得到改进，MAX变大，MIN变小； （2）如果对偶价格小于0，则其最优目标函数值变坏，即求最大值时，变得更小，求最小值时，变得更大； （3）如果对偶价格等于0，则其最优目标值不变。 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当z的值增加时，目标函数与约束条件：4x1+3x2 ? 120 重合，Q1与Q2之间都是最优解。 Q1（25，0） Q2（15，20） 解的讨论： 无界解： 例：max z=x1+x2 s.t. -2x1+x2 ? 40 x1-x2 ? 20 x1,x2 ? 0 x2 50 40 30 20 10 10 20 30 40 x1 该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。 解的讨论： 无可行解： 例：max S=2x1+3x2 s.t. x1+2x2 ? 8 x1 ? 4 x2 ? 3 -2x1+x2 ? 4 x1,x2 ? 0 该问题可行域为空集，即无可行解，也不存在最优解。 解的情况： 有可行解 ⊙有唯一最优解 ⊙有无穷最优解 ⊙无最优解 无可行解 (d)可行域无界 (e)可行域无界 (f)可行域为空集 多个最优解 目标函数无界 无可行解 (a)可行域有