线性规划的图解法.ppt

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