运筹学总的课件.pptVIP

线性规划的图解法 §1　问题的提出 §2　图解法 §3　图解法的灵敏度分析 线性规划的组成： 目标函数 Max F 或 Min F 约束条件 s.t. subject to 满足于 决策变量 用符号来表示可控制的因素 §1　问题的提出 §1　问题的提出 建模过程 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 例1.目标函数： Max z 50 x1 + 100 x2 约束条件： s.t. x1 + x2 ≤ 300 A 2 x1 + x2 ≤ 400 B x2 ≤ 250 C x1 ≥ 0 D x2 ≥ 0 E 得到最优解： x1 50， x2 250 最优目标值 z 27500 §2　图 解 法 一、基本概念 可行解 Feasible Solution ——任一满足约束条件的一组决策变量的数值； 可行域 Feasible Region ——所有可行解组成的集合，也称为可行解集； 目标函数等值线 Objective function line ——为于同一直线上的点，具有相同的目标函数值； 二、图解法步骤 Procedure （1）画出线性规划问题的可行域； （2）画出两条目标函数等值线； （3）平行移动目标函数等值线，使目标函数在可行域范围内达到最优。 三、图解法举例 例1 max Z 50x1+100x2 x1 + x2≤300 2x1 + x2≤400 x2≤250 x1、x2≥0 例2 max Z 50x1+50x2 x1 + x2≤300 2x1 + x2≤400 x2≤250 x1、x2≥0 直 观 结 论 可行域可以是个凸多边形，可能无界，也可能为空； 若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到； 若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即LP有无穷多最优解； 若可行域非空有界，则一定有最优解。 §2　图 解 法 线性规划的标准化内容之一：——引入松驰变量（含义是资源的剩余量） 例1 中引入 s1， s2， s3 模型化为 目标函数：Maxz 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件：s.t. x1 + x2 + s1 300 2 x1 + x2 + s2 400 x2 + s3 250 x1 , x2 , s1 , s2 , s3 ≥ 0 对于最优解x1 50 x2 250 ， s1 0 s2