线性规划图解法ppt课件.ppt

《线性规划图解法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图解法线性规划问题的求解方法一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式下面我们分析一下简单的情况——只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。图解法一、线性规划的图解法（解的几何表示）对于只有两个变量的线性规划问题，可以在二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下：（1）分别取决策变量x1，x2为坐标向量建立直角坐标系；图解法（2）对每个约

2、束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面。各约束半平面交出来的区域（存在或不存在），若存在，其中的点表示的解称为此线性规划的可行解。这些符合约束限制的点集合，称为可行集或可行域。进行（3）；否则该线性规划问题无可行解。图解法（3）任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置（有时交于无穷远处，此时称无有限最优解）。若有交点时，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数

3、的值即最优值。图解法图解法简单、直观，便于初学者了解线性规划基本原理和几何意义；例2.10用图解法求解线性规划问题max:z=50x1+30x2s.t.4x1+3x21202x1+x250x10，x20图解法x2x14050302x1+x25020101020304x1+3x2120z=50x1+30x2=600z=50x1+30x2=900z=50x1+30x2=1350(15,20)图解法图解法的观察（一）有效与无效(紧与松)约束：与最优解相关的约束为有效(紧)约束。最优解：总是在可行域的边界上，一般由可行域的顶点表示。可行

4、域：由约束平面围起来的凸多边形区域，可行域内的每一个点代表一个可行解。图解法例2.11用图解法求解maxz=x1+x2s.t.x1+2x24x1-2x25x1,x20无可行解的线性规划问题图解法14235123x1x2x1+2x24x1-2x25图解法例2.12用图解法求解：maxz=2x1+x2s.t.x1+x22x1-2x20x1,x20无界的线性规划问题图解法14235123x1x2x1+x22z=2x1+x2x1-2x20图解法如果目标函数线平行与一个约束线，线性规划问题有无穷多最优解。例2.13用图解法求解：m

5、axz=40x1+30x2s.t.4x1+3x21202x1+x250x10，x20存在无穷多最优解图解法x2x14050302x1+x25020101020304x1+3x2120z=40x1+30x2图解法图解法的观察（二）如果可行域为空集，线性规划问题无可行解；如果目标函数等值线可以无限制地在可行域内向改善的方向移动，线性规划问题无界;线性规划问题也可能存在无穷多个最优解。图解法maxZ=2X1+X2X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例

6、1.5用图解法求解线性规划问题图解法x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X220=2X1+X217.2=2X1+X211=2X1+X2Lo：0=2X1+X2（7.6，2）DmaxZminZ此点是唯一最优解，且最优目标函数值maxZ=17.2可行域maxZ=2X1+X2图解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)

7、（7.6，2）DL0：0=3X1+5.7X2maxZ（3.8，4）34.2=3X1+5.7X2蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域图解法minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2maxZminZ8=5X1+4X243=5X1+4X2（0，2）可行域此点是唯一最优解图解法246x1x2246无界解(无最优解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3

8、x2=6(≥)3x1+x2=6(≥)maxZminZx1x2O10203040102030405050无可行解(即无最优解)maxZ=3x1+4x2例1.7图解法学习要点：1.通