资源描述：
《最新运筹学课件-第二节---图解法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹学课件-第二节---图解法图解法举例实施图解法，以求出最优生产计划（最优解）maxZ=2x1+3x2s.t.由于线性规划模型中只有两个决策变量，因此只需建立平面直角系就可以进行图解了。第一步：建立平面直角坐标系，标出坐标原点,坐标轴的指向和单位长度。用x1轴表示产品A的产量，用x2轴表示产品B的产量。第二步：对约束条件加以图解。第三步：画出目标函数等值线，结合目标函数的要求求出最优解-----最优生产方案。令Z=2x1+3x2=c,其中c为任选的一个常数，在图中画出直线2x1+3x2=c,这条直线上的点即对应着一个可行的生产方案，即使两种产品的总利润达到c。这样
2、的直线有无数条，而且相互平行，称这样的直线为目标函数等值线。只要画出两条目标函数等值线，比如令c＝0和c=6，就能看出目标函数值递增的方向，用箭头标出这个方向。图中两条虚线l1和l2就分别代表目标函数等值线2x1+3x2=0和2x1+3x2=6,箭头表示使两种产品的总利润递增的方向。沿着箭头的方向平移目标函数等值线，使其达到可行域中的最远点E,E点就是要求的最优点，它对应的相应坐标x1=1,x2=2就是最有利的产品组合，即生产A产品等于1，B产品等于2能使两种产品的总利润达到最大值maxZ=21+32=8，x1=1,x2=2就是线性规划模型的最优解，Zmax=8
3、就是相应的目标函数最优值。尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精确值。比如E点对应的坐标值我们可以通过求解下面的联立方程，即求直线AB和CD的交点来求得。直线AB:1/3x1+1/3x2=1直线CD:1/3x1+4/3x2=30123456789x154321x2（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）设三种产品的产量分别是x1、x2、x3吨，由于有三个决策变量，用图解法求解下面的线性规划时，必须首先建立空间直角坐标系。变量超过2
4、个情况0x1x25x2=156x1+2x2=24x1+x2=5x2=-2x1+Z最优解的确定:可行域使目标函数达到最优的点,目标函数的Z值逐渐增大，一直移动到目标函数的直线与约束条件包围成的凸多边形相切时为止，切点就是最优解。(x1,x2)=(3.5,1.5),z=8.51、无穷多个最优解：将目标函数maxZ=x1+x22、无界解：可行域可伸展到无穷，导致目标函数增大到无限。产生无界解的原因是由于在建立实际问题的数学模型中遗漏某些必要的资源约束。3、无解：不存在满足约束条件的可行域。2.2线性规划求解的各种可能的结局2.2.1无穷多个最优解该线性规划的可行域为上图中
5、四边形OAED（即阴影区），虚线为目标函数等值线，箭头为目标函数值递增的方向。沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一条边界－－线段AE重合，这个结果表明，该线性规划有无穷多个最优解－－线段AE上的所有点都是最优点，它们都使目标函数取得相同的最大值Zmax=3。2.2.2无界解X1X2本例中的可行域是一个无界区域，如图中阴影区所示。虚线为目函数等值线，沿着箭头所指的方向平移可以使目标函数值无限制地增大，因此找不到最优解。如果实际问题是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大，解释不合理。此时应重
6、新检查和修改模型，否则就没有实际意义。x1x22.2.3无解x1X22.3图解法得到的启示1、求解线性规划问题时，解的情况：唯一最优解、无穷多个最优解、无界解，无解。2、若线性规划的可行域存在，则可行域一定是凸多边形（凸集）。3、若线性规划的最优解存在，则最优解（或最优解之一）一定是可行域凸集的一个顶点。4、解题思路：先找任一个顶点，计算目标函数；比较周围顶点的目标函数的值是否比此值大，一直找到使目标函数达到最大的顶点。图解法小结使用条件：仅有两个至多不超过三个决策变量的线性规划。基本步骤：第一步－－建立平面直角坐标系；第二步－－根据约束条件和非负条件画出可行域。第
7、三步－－作出目标函数等值线（至少两条），结合目标函数优化要求，平移目标函数等值线求出最优解。图解法的优缺点：简单、直观但有局限性。第三节单纯形法原理1.3.1线性规划问题解概念：可行解：满足所有约束条件的解。最优解：使目标函数达到最大值的可行解。基:设A为约束方程组的m×n阶系数矩阵(n>m),R(A)=m,B是矩阵A中的一个m×m阶满秩子矩阵,称B是线性规划问题的一个基,设列向量Pj(j=1,2,…m)为基向量,Pj所对应的变量xj基变量,其余变量为非基变量.秩:设在矩阵A中存在一个不等于零的r阶子式D,且所有的r+1阶子式全等于零,那么D为A的最高阶非零子式
