线性规划问题的图解法.ppt

一、线性规划的图解法－－－解的几何表示什麽是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求得满足约束条件和非负条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。图解法举例例3-1实施图解法，以求出最优生产计划（最优解）,给出最优值。由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。第一步：建立平面直角坐标系标出坐标原点,坐标轴的指向和单位长度。用x1轴表示产品A的产量，用x2轴表示产品B的产量。第二步：对约束条件加以图解。第三步：画出目标函数等值线，结合目标函数的要求求出最优解：最优生产方案。第四步：最优解带入目标函数，得出最优值。约束条件的图解:每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的边界，然后确定是哪个半平面。单击此处添加标题以第一个约束条件:为例,说明图解过程。单击此处添加标题怎麽画边界单击此处添加标题怎麽确定半平面单击此处添加标题 代表一个半平面其边界:x1+2x2=8x1+2x2=8及x1，x2≥0△AOB点A、B连线AB经济含义？△A0B1203x24123x18567Q4BA点A(8,0)：连接AB：设备全部占用所生产Ⅰ、Ⅱ数量对应的点的集合。全部的设备都用来生产Ⅰ产品而不生产Ⅱ产品,那么Ⅰ产品的最大可能产量为8台,计算过程为：x1+2×0?8?x1?8△Ａ0B：设备没有全部占用所生产Ⅰ、Ⅱ数量对应的点的集合。1203x24123x18567Q4BA约束条件及

非负条件x1,x2?0

代表的公共部分－－图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。另两个约束条件的边界直线CD、EF:4x1≤16，4x2≤128567x1A3x2BCDE4123102F令Z=2x1+3x2=c,其中c为任选的一个常数，在图中画出直线2x1+3x2=c,即对应着一个可行的生产结果，即使两种产品的总利润达到c。这样的直线有无数条，且相互平行，称这样的直线为目标函数等值线。只要画两条目标函数等值线，如令c＝0和c=6，可看出目标函数值变化的方向,即虚线l1和l2,箭头为产品的总利润递增的方向。最优点8567x1A3x2BCDE4123102F对应坐标x1=4,x2=2是最佳的产品组合,[4,2]T就是线性规划模型的最优解使产品的总利润达到最大值maxZ=2?4+3?2=14就是目标函数最优值。沿着箭头方向平移目标函数等值线，达到可行域中的最远点E,E点就是最优点;最优点8567x1A3x2BCDE4123102F尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精确值。比如C点对应的坐标值我们可以通过求解下面的联立方程，即求直线AB和CD的交点来求得。直线AB:x1+2x2=8直线CD:4x1=16最优点8567x1A3x2BCDE4123102F结果有唯一最优解可行域是一个非空有界区域单击此处添加标题用图解法求解线性规划的各种可能的结果单击此处添加标题可行域有几种可能?解有几种可能?单击此处添加标题讨论单击此处添加标题*