第二章线性规划模型和图解法全

单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,Page,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,Page,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,Page,*,Chapter,2,线性规划,模型和图解法,(Linear Programming,-LP,),LP方法应用的典型情况,LP的数学模型,LP,模型的,图解法,LP,问题的计算机求解,本章主要内容：,Chapter,2,线性规划,模型和图解法,本章,教学目的、重点、难点,：,掌握线性规划问题数学模型建立和线性规划模型的特征；,线性规划模型的一般形式及标准形式，解的相关概念；,掌握两个变量线性规划问题的几何作图求解方法；,掌握两个变量线性规划模型可行域的特点及最优解存在的位置；,熟悉计算机,QM,软件求解线性规划问题的步骤,。,1.规划问题,阐述,生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。,线性规划通常解决下列两类问题：,（,1,）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标,（,2,）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大,.,）,LP方法应用的典型情况,2,在管理中一些典型的线性规划应用,LP方法应用的典型情况,（1）,生产的组织与计划问题：合理利用现有的 人 力、物力、财力做出最优产品生产计划。,（2）运输问题：根据生产单位的产量和销售单位的 销量，制订产品调运方案，使得总运费最小。,（3）合理下料问题：如何裁截下料，既满足生产需要，又使得所用的材料数量最少。,（4）,配料问题：在原料供应量限制和保证产品成分含量的前提下，获取最优配料方案,2,在管理中一些典型的线性规划应用,LP方法应用的典型情况,（5）营销管理问题：要从几种媒体中选择一种组合，使其在广告费用预算条件下广告效益最好。,（6）投资组合问题：选择一组股票或证券进行投资，使得有最大的回报率。,（7）人力资源管理问题：在不同的时间段需要不同数量的劳动力，如何安排劳动力才能用最少的劳动力来满足工作的需要。,线性规划问题的数学模型,线性规划问题的数学模型,易拉罐的设计理念,具体下料-模型的建立,线性规划问题的数学模型,例,1.2,某企业计划生产甲、乙两种产品。这些产品分别要在,A,、,B,、,C,、,D,、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？,设 备,产 品,A,B,C,D,利润（元）,甲,2,1,4,0,2,乙,2,2,0,4,3,有 效 台 时,12,8,16,12,2 线性规划模型的建立,线性规划问题的数学模型,解：设,x,1,、,x,2,分别为甲、乙两种产品的产量，则数学模型为：,max Z=2x,1,+3x,2,x,1,0,x,2,0,s.t.,2x,1,+2x,2,12,x,1,+2x,2,8,4x,1,16,4x,2,12,线性规划问题的数学模型,3,.线性规划的数学模型由三个要素构成,决策变量,Decision variables,目标函数,Objective function,约束条件,Constraints,其特征是：,（,1,）问题的目标函数是多个决策变量的,线性,函数，通常是求最大值或最小值；,（,2,）问题的约束条件是一组多个决策变量的,线性,不等式或等式。,怎样辨别一个模型是线性规划模型？,模型建立练习：P13,线性规划问题的数学模型,目标函数：,约束条件：,4,.线性规划数学模型的一般形式,简写为：,线性规划问题的数学模型,向量形式：,其中：,线性规划问题的数学模型,矩阵形式：,其中：,线性规划问题的数学模型,5,.线性规划问题的标准形式,特点：,(1),目标函数求最大值（有时求最小值）,(2),约束条件都为等式方程，且右端常数项,b,i,都大于或等于零,(3),决策变量,x,j,为非负。,线性规划问题的数学模型,6,如何化标准形式,目标函数的转换,如果是求极小值即,则可将目标函数乘以,(-1),，可化为求极大值问题。,也就是：令 ，可得到上式。,即,若存在取值无约束的变量 ，可令,其中：,变量的变换,线性规划问题的数学模型,约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,变量,的,变换,可令,，,显然,线性规划问题的数学模型,例,1.3,将下列线性规划问题化为标准形式,解,:,（）因为,x,3,无符号要求，即,x,3,取正值也可取负值，标准型中要求变量非负，所以,用,替换,，,且,;,线性规划问题的数学模型,(2),第一个约束条件是“”号，在“”左端加入松驰变量,x,4,，,x,4,0,化为等式；,(3),第二个约束条件是“”号，在“”左端减去剩余变量,x,5,，,x,5,0,；,(4),第,3,个约束方程右端常数项为,-5,，方程两边同乘以,(-1),将右端常数项化为正数；,(5),目标函数是最小值，为了化为求最大值，令,z=-z,得到,max z=-z,，即当,z,达到最小值时,z,达到最大值，反之亦然,;,线性规划问题的数学模型,标准形式如下：,学习要点,小结,：,1.线性规划模型在管理中的应用：生产组织，下料问题等,2.线性规划模型的构成：目标函数、约束条件；,3.将一般形式转化标准形式：目标函数求最大、最小时；,约束条件变为不等号时；常数项为负时；决策变量无约束时；,小结,作业,作业：,课堂出题练习,思考：,建立模型后怎样进行求解？,线性规划,模型的图解法,1,.,基本概念,线性规划问题,求解线性规划问题，就是从满足约束条件,(2),、,(3),的方程组中找出一个解，使目标函数,(1),达到最大值。,可行解,：满足,约束条件,（2）,、,(3),的解为可行解。所有可行解的集合为可行域。,最优解,：使目标函数达到最大值的可行解。,最优值,：,最优解带入目标函数所得的值称为线性规划的最优值。,凸集,：如果集合C中任何两点连线上所有的点都是集合C中的点，则称该集合为凸集。,线性规划,模型的图解法,线性规划,模型的图解法,凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。,凸集,凸集,不是凸集,顶 点,线性规划问题的求解方法,一 般 有,两种方法,图 解 法,单纯形法,两个变量、直角坐标,适用于任意变量、但必需将,一般形式变成标准形式,下面我们分析一下简单的情况,只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。,线性规划,模型的图解法,线性规划模型图解法基本步骤：,Step1：,建立坐标系；,Step,2,：,图示约束条件；,Step,3,：,图示目标函数；,Step,4,：,确定最优解；,图解法简单直观，有助于领会线性规划的基本性质及一般求解方法的基本思想。,线性规划,模型的图解法,max Z=2X,1,+X,2,X,1,+1.9X,2,3.8,X,1,-1.9X,2,3.8,s.t.X,1,+1.9X,2,10.2,X,1,-1.9X,2,-3.8,X,1,，,X,2,0,例1.,4,用图解法求解线性规划问题,线性规划,模型的图解法,x,1,x,2,o,X,1,-1.9X,2,=3.8,(),X,1,+1.9X,2,=3.8(,),X,1,-1.9X,2,=-3.8(,),X,1,+1.9X,2,=10.2,(),4=2,X,1,+X,2,20=2,X,1,+X,2,17.2=2,X,1,+X,2,11=2,X,1,+X,2,Lo：0=2X,1,+X,2,（,7.6,，,2,）,D,max Z,min Z,此点是唯一最优解，,且最优目标函数值,max Z=17.2,可行域,max Z=2X,1,+X,2,线性规划,模型的图解法,max Z=3X,1,+5.7X,2,x,1,x,2,o,X,1,-1.9X,2,=3.8,(),X,1,+1.9X,2,=3.8(,),X,1,-1.9X,2,=-3.8(,),X,1,+1.9X,2,=10.2,(),（,7.6,，,2,）,D,L,0,：,0=3X,1,+5.7X,2,max Z,34.2,=3,X,1,+5.7X,2,蓝色线段上的所有点都是最,优解这种情形为有无穷多最,优解，但是最优目标函数值,max Z=34.2,是唯一的。,可行域,线性规划,模型的图解法,min Z=5X1+4X2,x,1,x,2,o,X,1,-1.9X,2,=3.8,(),X,1,+1.9X,2,=3.8(,),X,1,+1.9X,2,=10.2,(),D,L,0,：,0=5X,1,+4X,2,max Z,min Z,8=5X,1,+4X,2,43=5X,1,+4X,2,（,0,，,2,）,可行域,此点是唯一最优解,线性规划,模型的图解法,2,4,6,x,1,x,2,2,4,6,无界解,(,无最优解,),max,Z,=,x,1,+2,x,2,例1.,5,x1+x2=4(),x1+3x2=6(),3x1+x2=6(),max Z,min Z,线性规划,模型的图解法,x,1,x,2,O,10,20,30,40,10,20,30,40,50,50,无可行解,(,即无最优解,),max Z=3,x,1,+4,x,2,例1.,6,线性规划,模型的图解法,练习：,用图解法求解下面线性规划模型：,线性规划,模型的图解法,分析：,用图解法求解下面线性规划模型：,图,1,最大化线性规划模型的图解法,线性规划,模型的图解法,分析：,用图解法求解下面线性规划模型：,多边形区域,OABCD,中的点就是线性规划问题的可行解（可行点），多边形区域,OABCD,称为线性规划问题的可行解区域。显然它是一个凸区域。,可行域：,目标函数：,我们将 看作参数，则 表示坐标平面上的一族平行线，直线 上任意一点的坐标对应的目标函数值均为，我们称这样的直线为等值线（或等高线）。,线性规划,模型的图解法,分析：,用图解法求解下面线性规划模型：,可得,C,点坐标,X1=4,X2=2,，对应的目标函数值为,线性规划模型有以下,4,种情况：,唯一,最优解：凸多边形的某个顶点；,无穷多最优解：目标函数直线和可行域边界一条边,重合；,无界解：如果线性规划模型的解无限的变大（变小），却不违反任何约束条件；,无可行解：不存在在满足全部约束条件的解；,线性规划,模型的图解法,计算机求解线性规规划问题,下面,介绍QM软件的使用方法：,Step1：双击QM软件图标，运行该软件。,Step2：选择“Module”按回车键，选择“Linear Programming”按回车键。选择“New”按回车键,Step3：在出现的窗口中确定约束方程个数、变量个数，选择最大值、最小值。并按“OK”确认。,Step4：输入数据。,Step5：选择“Solve”按回车键运行。,Step6：在“Windows”窗口中查看结果。（最优解、最优值、迭代过程、影子价格）。,线性规划,模型的图解法,线性规划,模型的图解法,2.使用QM软件求解线性规划模型,选择线性规划模块,（P12例题）,，输入目标函数系数和约束条件如图,1,所示,：,图 1,线性规划,模型的图解法,点击“SLOVE”按钮，进行求解，结果如图2所示。,图 2,学习要点,小结,：,1.线性规划模型的构成、将一般形式转化标准形式,2,.,通过图解法了解线性规划有几种解的形式,（唯一最优解；无穷多最优解；无界解；无可行解）,3,.,作图的关键有三点：,(1)可行解区域要画正确,(2)目标函数增加的方向不能画错,(3)目标函数的直线怎样平行移动,4.计算机求解线性规划问题,小结,作业,课后作业：,P24,1、2、3、4,思考：,求解松弛变量、剩余变量的意义？,如果模型中的决策变量大于两个时考虑用什么方法求解？,