线性规划图解法线性规划图解法解几何表示.pptx

1 （2）对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面。各约束半平面交出来的区域(存在或不存在），若存在，其中的点表示的解称为此线性规划的可行解。这些符合约束限制的点集合，称为可行集或可行域。否则该线性规划问题无可行解。第1页/共24页2 （3）任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无穷远处，此时称无有限最优解）。若有交点时，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。第2页/共24页3 例2.5某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500第3页/共24页4 问题：工厂应如何安排生产可获得最大的总利润？用图解法求解。解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据前面分析，可以建立如下的线性规划模型：Max z=1500 x1+2500 x2 s.t.3x1+2x2 65 (A)2x1+x2 40 (B)3x2 75 (C)x1,x2 0 (D,E)第4页/共24页5 按照图解法的步骤在以决策变量x1，x2 为坐标向量的平面直角坐标系上对每个约束（包括非负约束）条件作出直线，并通过判断确定不等式所决定的半平面。各约束半平面交出来的区域即可行集或可行域如下图阴影所示。第5页/共24页6 图解法求解线性规划第6页/共24页7 任意给定目标函数一个值作一条目标函数的等值线，确定该等值线平移后值增加的方向；平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置，得到交点(5,25)T，此目标函数的值为70000。于是，得到这个线性规划的最优解x1=5、x2=25，最优值z=70000。即最优方案为生产甲产品5件、乙产品25件，可获得最大利润为70000元。第7页/共24页8 例2.6在例2.2的线性规划模型中，如果目标函数变为：Max z=1500 x1+1000 x2 那么，目标函数的等值线与直线（A）重合。这时，最优解有无穷多个：从点(5,25)T到点(15,10)T 线段上的所有点，最优值为32500。如下图所示：第8页/共24页9 无穷多解的情况第9页/共24页10 例2.7在例2.2的线性规划模型中,如果约束条件（A）、（C）变为：3 x1+2 x2 65 (A）3 x2 75 (C）并且去掉（D、E）的非负限制。那么，可行域成为一个上无界的区域。这时，没有有限最优解，如下图所示：第10页/共24页11 无有限解的情况第11页/共24页12 例2.8在例2.2的线性规划模型中，如果增加约束条件（F）为：x1+x2 40 （F）那么，可行域成为空的区域。这时，没有可行解，显然线性规划问题无 解。如下图所示：第12页/共24页13 无可行解的情况第13页/共24页14可行域和解有哪些情况？第14页/共24页15线性规划的可行域和最优解的几种可能的情况 1.可行域为封闭的有界区域 (a)有唯一的最优解；(b)有无穷多个最优解；第15页/共24页16可行域有界唯一最优解可行域有界多个最优解第16页/共24页17 2.可行域为封闭的无界区域 (c)有唯一的最优解；(d)有无穷多个最优解；(e)目标函数无界(即虽有可解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。第17页/共24页18可行域无界唯一最优解可行域无界无穷多最优解第18页/共24页19可行域无界目标函数无界第19页/共24页20 3.可行域为空集 (f)没有可行解，原问题无最优解 第20页/共24页21可行域为空集无可行解第21页/共24页22 作业：P59 3 第22页/共24页23结束放映结束放映第23页/共24页24感谢您的观看！第24页/共24页