复习运筹学课件__胡运权_第四版_复习要点课件.ppt

第一章 线性规划及单纯形法 §1 线性规划问题及其数学模型 　３、右端项bi 0时，只需将等式两端同乘（-1） 则右端项必大于零 第一章 线性规划及单纯形法 §2 线性规划问题的图解法 第一章 线性规划及单纯形法 LP问题图解法的基本步骤： §2 线性规划问题的图解法 第一章 线性规划及单纯形法 §2 线性规划问题的图解法 由以上两例分析可得如下重要结论： 仍然考虑先前的例子 * * 运 筹 学 Operations Research 第一章 线性规划及单纯形法 如何转化为标准形式？ 1、目标函数为求极小值，即为： 。 因为求 min z 等价于求 max (-z)，令 z’ = - z， 即化为： 2、约束条件为不等式， xn+1 ≥ 0 松弛变量 如何处理？ 4、决策变量无非负约束 设 xj 没有非负约束，若 xj ≤0，可令 xj = - xj’ ， 则 xj’ ≥0； 又若 xj 为自由变量，即 xj 可为任意实数， 可令 xj = xj’ - xj’’，且 xj’ , xj’’ ≥0 e.g. 3 试将 LP 问题 min z = -x1+2x2-3x3 s.t. x1+x2+x3 ≤7 x1-x2+x3 ≥2 -3x1+x2+2x3 = -5 x1,x2 ≥0 化为标准形式。 解： 令 x3= x4 - x5 其中x4、x5 ≥0； 对第一个约束条件加上松弛变量 x6 ； 对第二个约束条件减去松弛变量 x7 ； 对第三个约束条件两边乘以“-1” ； 令 z’=-z 把求 min z 改为求 max z’ max z’= x1-2x2+3x4- 3x5 s.t. x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x7≥0 max z = 15x1 +25x2 s.t. x1 + 3x2 ≤ 60 x1 + x2 ≤ 40 x1，x2 ≥ 0 (40,0) (0,0) B C (30,10) O (0,20) A L1 L2 Z=250 目标函数变形： x2=-3/5 x1+z/25 x2 x1 最优解： x1=30 x2 =10 最优值：zmax=700 B点是使z达到最大的唯一可行点 1、在平面上建立直角坐标系； 2、图示约束条件，确定可行域和顶点坐标； 3、图示目标函数（等值线）和移动方向； 4、寻找最优解。 max z =3x1 + 5.7x2 s.t. x1 + 1.9x2 ≥ 3.8 x1 - 1.9x2≤ 3.8 x1 + 1.9x2 ≤11.4 x1 - 1.9x2 ≥ -3.8 x1 ，x2 ≥ 0 x1 x2 o x1 - 1.9 x2 = 3.8 x1 + 1.9 x2= 3.8 x1 + 1.9 x2 = 11.4 （7.6,2） D 0=3 x1 +5.7 x2 max Z min Z （3.8,4） 34.2 = 3 x1 +5.7 x2 可行域 x1 - 1.9 x2 = -3.8 (0,2) (3.8,0) 绿色线段上的所有点 都是最优解,即有无穷多最优解。Zman=34.2 max z = 2x1 + 2x2 s.t. 2x1 – x2 ≥ 2 -x1 + 4x2≤ 4 　　 x1，x2 ≥ 0 O A (１,0) x1 x2 Note: 可行域为无界区域， 目标函数值可无限 增大，即解无界。 称为无最优解。 可行域为无界区域一定无最优解吗？ 1、LP 问题从解的角度可分为： ⑴ 有可行解 ⑵ 无可行解 有唯一最优解 b. 有无穷多最优解 C. 无最优解 2、LP 问题若有最优解，必在可行域的某个顶点上取 到；若有两个顶点上同时取到，则这两点的连线上 任一点都是最优解。 3：差值法（伏格尔法） 最小元素法的缺点是：为了节省一处的费用，有时造成其它处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小费用就近供应，就考虑次小费用，这就有一个差额，差额越大，说明不按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小调运方案。 基