线性规划的图解法

第三节 两个变量问题的图解法线性性规划划问题的求解方法的求解方法一 般 有两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但必需将适用于任意变量、但必需将一般形式变成标准形式一般形式变成标准形式下面我们分析一下简单的情况 只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。2第三节 两个变量问题的图解法解（参见教材P21）解（参见教材P22）3第三节 两个变量问题的图解法解（参见教材P23）解（参见教材P23）图解法max Z=2X1+X2 X12 X12s.t.X12 X12 X1 ，X2 0练习：练习：用图解法求解线性规划问题用图解法求解线性规划问题图解法x1x2oX12()X12=3.8()X12=-3.8()X12()4=2X1+X2 20=2X1+X2 17.2=2X1+X2 11=2X1+X2 Lo：0=2X1+X2（，（，2）Dmax Zmin Z此点是唯一最优解，且最优目标函数值 可行域可行域max Z=2X1+X2图解法若max Z=3X12x1x2oX12=3.8()X12=3.8()X12=-3.8()X12=10.2()（，（，2）DL0：0=3X12 max Z（，（，4）34.2=3X12 蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值是唯一的。可行域可行域图解法min Z=5X1+4X2x1x2oX12=3.8()X12=3.8()X12=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 Zx1x2O10203040102030405050无可行解无可行解(即无最优解即无最优解)max Z=3x1+4x2练习：练习：线性规划的图解法线性规划的图解法图解法的基本步骤图解法的基本步骤 X*=(4,6)Tz*=42 1画出可行域图形画出可行域图形 2画出目标函数的画出目标函数的 等值线及其法线等值线及其法线 3确定最优点确定最优点max z=3x1+5x2 x1 8 2 x2 12 3x1+4 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 115谢谢观看！谢谢观看！