资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,安徽科技学院,运筹学,第二节 图解法,线性规划的可行解,:满足约束条件的一组,x,j,(,j,=1,2,n,),;,可行域,:全部可行解的集合;,最优解,:可行域中使目标函数达到最优的可行解;,问题无解,:不存在可行解的线性规划问题;,图解法的适用范围,:只含有,2,个变量的线性规划问题。,图解法求解的目的,:,1,、判别线性规划问题的求解结局;,2,、在存在最优解的条件下,把最优解找出来。,一、图解法的步骤,1,、在平面上建立直角坐标系;,2,、图示约束条件;,3,、找出可行域或判别是否存在可行域;,4,、图示找出最优解。,以例,1,为例说明求解的过程:,0,1,、以变量,x,1,为横坐标轴,,x,2,为纵坐标轴画出平面直角坐标系,并选取单位坐标长度。,x,1,x,2,2,、图示约束条件,找出可行域。,3,、图示目标函数。,z=2,x,1,+,x,2,是一族斜率为,-2,的平行直线。,4,、最优解的确定。,最优解点,(3.5,1.5),最优解,z=8.5,最优值增大方向,当目标函数向优化方向移动时,与可行域在一个线段上相切,此时线段上所有的点都使目标函数,z,达到最大,因此有无穷多解。,二、线性规划问题求解的几种可能结局,1,、,无穷多最优解,:如例,1,中将目标函数改为,max z=3,x,1,+,x,2,则目标函数直线族恰好与一约束平行。,0,x,1,x,2,整个线段上的点都是最优解点,二、线性规划问题求解的几种可能结局,1,、,无穷多最优解,:如例,1,中将目标函数改为,max z=3,x,1,+,x,2,则目标函数直线族恰好与一约束平行。当目标函数向优化方向移动时,与可行域在一个线段上相切,此时线段上所有的点都使目标函数,z,达到最大,因此有无穷多解。,2,、,无界解,:如例,1,中只含约束条件,x,2,3,以及,x,1,x,2,0,,则此时可行域可伸展到无穷,即变量,x,1,的取值可无限增大,不受限制,由此目标函数值也可增大至无穷。,产生无界解的原因:约束条件的遗漏,x,1,x,2,二、线性规划问题求解的几种可能结局,1,、,无穷多最优解,:如例,1,中将目标函数改为,max z=3,x,1,+,x,2,则目标函数直线族恰好与一约束平行。当目标函数向优化方向移动时,与可行域在一个线段上相切,此时线段上所有的点都使目标函数,z,达到最大,因此有无穷多解。,2,、,无界解,:如例,1,中只含约束条件,x,2,3,以及,x,1,x,2,0,,则此时可行域可伸展到无穷,即变量,x,1,的取值可无限增大,不受限制,由此目标函数值也可增大至无穷。,产生无界解的原因:约束条件的遗漏,3,、,无解或无可行解,,如下述线性规划模型,x,1,x,2,0,三、由图解法得到的启示,1,、求解线性规划时,解的情况有:,唯一最优解;,无穷多最优解;无界解;无可行解。,2,、若线性规划问题的,可行域存在,则可行域是,一个凸集。,3,、若线性规划问题的最优解存在,则,最优解或,最优解之一,(如果有无穷多的话),一定是可行,域的凸集的某个顶点,。,4,、解题思路:,先找出凸集的任一顶点,计算在该顶点处的,目标函数值;,比较周围相邻顶点的目标函数值是否比这个,值更大,如果为否,转,,否则转,;,转到比这个顶点的目标函数值大的另一个顶,点,转,;,此顶点即为最优解的点或最优解的点之一。,课堂练习:,练习,3,:利用图解法求解线性规划问题,最早运用运筹学理论的是(),练习,4,:巩固复习之选择题,A,二次世界大战期间,英国军事部门将运筹学运用到军事,战略部署,B,美国最早将运筹学运用到农业和人口规划问题上,C,二次世界大战期间,英国政府将运筹学运用到政府制定,计划,D 50,年代,运筹学运用到研究人口,能源,粮食,第三世,界经济发展等问题上,下一次课要讲的内容,0,、单纯形法的原理,1,、单纯形法的计算步骤,2,、单纯形法的进一步讨论,3,、线性规划模型的应用例子,4,、结束第一章,布置作业,提前预习!,最早运用运筹学理论的是(,A,),练习,4,:巩固复习之选择题,A,二次世界大战期间,英国军事部门将运筹学运用到军事,战略部署,B,美国最早将运筹学运用到农业和人口规划问题上,C,二次世界大战期间,英国政府将运筹学运用到政府制定,计划,D 50,年代,运筹学运用到研究人口,能源,粮食,第三世,界经济发展等问题上,Right!,最早运用运筹学理论的是(,B,),练习,4,:巩固复习之选择题,A,二次世界大战期间,英国军事部门将运筹学运用到军事,战略部署,B,美国最早将运筹学运用到农业和人口规划问题上,C,二次世界大战期间,英国政府将运筹学运用到政府制定,计划,D 50,年代,运筹学运用到研究人口,能源,粮食,第三世,界经济发展等问题上,Wrong!,最早运用运筹学理论的是(,C,),练习,4,:巩固复习之选择题,A,二次世界大战期间,英国军事部门将运筹学运用到军事,战略部署,B,美国最早将运筹学运用到农业和人口规划问题上,C,二次世界大战期间,英国政府将运筹学运用到政府制定,计划,D 50,年代,运筹学运用到研究人口,能源,粮食,第三世,界经济发展等问题上,Wrong!,最早运用运筹学理论的是(,D,),练习,4,:巩固复习之选择题,A,二次世界大战期间,英国军事部门将运筹学运用到军事,战略部署,B,美国最早将运筹学运用到农业和人口规划问题上,C,二次世界大战期间,英国政府将运筹学运用到政府制定,计划,D 50,年代,运筹学运用到研究人口,能源,粮食,第三世,界经济发展等问题上,Wrong!,
展开阅读全文