线性规划的图解法.ppt

线性规划问题的求解方法 一 般 有 两种方法 图 解 法 单纯形法 两个变量、直角坐标 三个变量、立体坐标 适用于任意变量、但必需将 一般形式变成标准形式 下面我们分析一下简单的情况—— 只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。 * 第三节 两个变量问题的图解法 解（参见教材P21） 解（参见教材P22） * 第三节 两个变量问题的图解法 解（参见教材P23） 解（参见教材P23） 图解法 max Z = 2X1 + X2 X1 + 1.9X2 ≥ 3.8 X1 - 1.9X2 ≤ 3.8 s.t. X1 + 1.9X2 ≤10.2 X1 - 1.9X2 ≥ -3.8 X1 ，X2 ≥ 0 练习： 用图解法求解线性规划问题 图解法 x1 x2 o X1 - 1.9X2 = 3.8(≤) X1 + 1.9X2 = 3.8(≥) X1 - 1.9X2 = -3.8 (≥) X1 + 1.9X2 = 10.2(≤) 4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2） D max Z min Z 此点是唯一最优解， 且最优目标函数值 max Z=17.2 可行域 max Z = 2X1 + X2 图解法 若max Z=3X1+5.7X2 x1 x2 o X1 - 1.9X2 = 3.8 (≤) X1 + 1.9X2 = 3.8(≥) X1 - 1.9X2 = -3.8(≥) X1 + 1.9X2 = 10.2 (≤) （7.6，2） D L0： 0=3X1+5.7X2 max Z （3.8，4） 34.2 = 3X1+5.7X2 蓝色线段上的所有点都是最 优解这种情形为有无穷多最 优解，但是最优目标函数值 max Z=34.2是唯一的。 可行域 图解法 min Z=5X1+4X2 x1 x2 o X1 - 1.9X2 = 3.8 (≤) X1 + 1.9X2 = 3.8(≥) X1 + 1.9X2 = 10.2 (≤) D L0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2） 可行域 此点是唯一最优解 图解法 2 4 6 x1 x2 2 4 6 无界解(无最优解) max Z=x1+2x2 练习： x1+x2=4(≥) x1+3x2=6(≥) 3x1+x2=6(≥) max Z min Z x1 x2 O 10 20 30 40 10 20 30 40 50 50 无可行解(即无最优解) max Z=3x1+4x2 练习： 线性规划的图解法 图解法的基本步骤 X*= (4, 6)T z* = 42 1°画出可行域图形 2°画出目标函数的 等值线及其法线 3°确定最优点 max z = 3x1+5x2 x1 ≤ 8 2 x2 ≤ 12 3x1+ 4 x2 ≤ 36 x1, x2 ≥ 0 s.t. x1 x2 O(0,0) x1= 8 A(8,0) 2x2= 12 D(0,6) 3x1 + 4x2 = 36 O(0,0) x1 x2 R D(0,6) C(4,6) B(8,3) A(8,0) z = 15 z = 30 z 法向 z* = 42 边界方程 线性规划的图解法 几点说明 实际运用时还须注意以下几点: (1)若函数约束原型就是等式,则其代表的区域仅为一直线,而且问题的整个可行域R(若存在的话)也必然在此直线上。 (2)在画目标函数等值线时只须画两条就能确定其法线方向,为此, 只须赋给z 两个适当的值。 (3)在找出最优点后,关于其坐标值有两种确定方法: ① 在图上观测最优点坐标值 ② 通过解方程组得出最优点坐标值 图解法 学习要点： 1. 通过图解法了解线性规划有几种解的形式 （唯一最优解；无穷多最优解；无界解；无可行解） 2. 作图的关键有三点： (1) 可行解区域要画正确 (2) 目标函数增加的方向不能画错 (3) 目标函数的直线怎样平行移动 线性规划的图解法 几种可能结果 一、唯一解 如例1、例2都只有一个 最优点，属于唯一解的情形。 s.t. max z = 3x1+