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

§2.1 问题的提出 §2.2 图解法 §2.3 图解法的灵敏度分析 第二章 线性规划的图解法 解决以下两类问题 资源一定 产出最大 (产出：如产量、销售量、利润等) 任务一定 投入最小 (投入：如资金、人员、时间、原材料等) LP模型三要素 - 决策变量 - 约束条件（线性等式或线性不等式） - 目标函数（线性函数，最大化或最小化） 建模过程 1. 理解要解决的问题，了解解题的目标和条件； 2. 定义决策变量(x1 ，x2 ，… ，xn ), 每一组值表示一个方案； 3. 用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标； 4. 用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 一般形式 目标函数： Max（Min）z = c1 x1 + c2 x2 + … + cn xn 约束条件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤（ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤（ =, ≥ ）b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤（ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0 §2.2 图 解 法 例1. 目标函数： Max z = 50x1 + 100x2 约束条件： x1 + x2 ≤ 300 (A) 2x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E) 图解法的运算步骤 §2.2 图 解 法 §2.2 图 解 法 §2.2 图 解 法 §2.2 图 解 法 §2.2 图 解 法 §2.3 图解法的灵敏度分析 灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数(系数)ci , aij , bj 变化时，对最优解产生的影响。 目标函数 z = 50 x1 + 100 x2 在 z = x2 (x2 = z 斜率为0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜率为 -1 )之间时，原最优解x1 = 50，x2 = 250仍是最优解。 §2.3 图解法的灵敏度分析 假设产品Ⅱ的利润100元不变，即c2= 100，代到式（*）并整理得 0 ? c1 ? 100 假设产品Ⅰ的利润 50 元不变，即 c1= 50 ，代到式（*）并整理得 50 ? c2 ? + ? 假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。 §2.3 图解法的灵敏度分析 假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则 - 2 ? - (60 / 55) ? - 1 那么，最优解为 z = x1 + x2 和 z = 2 x1 + x2 的交点: x1 = 100，x2 = 200 §2.3 图解法的灵敏度分析 3.2 约束条件中右边系数 bj 的灵敏度分析 当约束条件中右边系数bj变化时,线性规划的可行域也变化,可能引起最优解的变化。 §2.3 图解法的灵敏度分析 变化后总利润－变化前总利润=增加的利润 (50×60+100×250)－(50×50+100×250)= 500 500 / 10 = 50 元 说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。 §2.3 图解法的灵敏度分析 假设原料A增加10千克时，即b2变化为410，这时可行域扩大，但最优解仍为x2 = 250 和 x1 +x2 = 300 的交点 x1 = 50，x2 = 250 。 §2.3 图解法的灵敏度分析 在一定范围内, 当约束条件右边常数增加1个单位时 （1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）； （2）若约束条件的对偶价格等于0，则最优目标函数值不变。 （3）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）； 作 业 第二章作业： P25. 6. (