[计算机软件及应用]第2章线性规划的图解法ppt课件.ppt
1,第二章 线性规划的图解法,1 问题的提出2 图解法3 图解法的灵敏度分析,2,第二章 线性规划的图解法,在管理中一些典型的线性规划应用合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小,3,线性规划模型的三要素,3.约束条件：为实现优化目标需受到的限制，用 决策变量的等式或不 等式表示；,1.决策变量：需决策的量，即待求的未知数；,2.目标函数：需优化的量，即欲达的目标，用决 策变量的表达式表示；,4,1 问题的提出,例1.某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？,线性规划模型：约束条件：s.t.x1+x2 300,目标函数：Max z=50 x1+100 x2,2 x1+x2 400,x2 250,x1,x2 0,5,1 问题的提出,建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件一般形式目标函数：Max（Min）z=c1 x1+c2 x2+cn xn 约束条件：s.t.a11 x1+a12 x2+a1n xn（=,）b1 a21 x1+a22 x2+a2n xn（=,）b2 am1 x1+am2 x2+amn xn（=,）bm x1，x2，xn 0,6,例1.目标函数：Max z=50 x1+100 x2 约束条件：s.t.x1+x2 300(A)2 x1+x2 400(B)x2 250(C)x1 0(D)x2 0(E)得到最优解：x1=50，x2=250 最优目标值 z=27500,2 图 解 法,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：,7,2 图 解 法,(1)分别取决策变量X1,X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。,8,2 图 解 法,（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。,9,2 图 解 法,（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。,10,2 图 解 法,（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,2x1+x2=400,x2=250,x1+x2=300,11,2 图 解 法,（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,12,2 图 解 法,线性规划的标准化内容之一：引入松驰变量（含义是资源的剩余量）例1 中引入 s1，s2，s3 模型化为 目标函数：Max z=50 x1+100 x2+0 s1+0 s2+0 s3 约束条件：s.t.x1+x2+s1=300 2 x1+x2+s2=400 x2+s3=250 x1,x2,s1,s2,s3 0 对于最优解 x1=50 x2=250，s1=0 s2=50 s3=0 说明：生产50单位产品和250单位产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。,13,进 一 步 讨 论,例2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？目标函数：Min f=2x1+3 x2约束条件：s.t.x1+x2 350 x1 125 2 x1+x2 600 x1,x2 0,14,进 一 步 讨 论,解：目标函数：Min f=2x1+3 x2 约束条件：s.t.x1+x2 350 x1 125 2 x1+x2 600 x1,x2 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。,15,进 一 步 讨 论,解：目标函数：Min f=2x1+3 x2 约束条件：s.t.x1+x2 350 x1 125 2 x1+x2 600 x1,x2 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。,16,进 一 步 讨 论,解：目标函数：Min f=2x1+3 x2 约束条件：s.t.x1+x2 350 x1 125 2 x1+x2 600 x1,x2 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。,17,进 一 步 讨 论,解：目标函数：Min f=2x1+3 x2 约束条件：s.t.x1+x2 350 x1 125 2 x1+x2 600 x1,x2 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。,18,线性规划模型的图解法,图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。,19,问题：在上两例中,多边形，而且是“凸”形的多边形。,最优解在什么位置获得？,在边界，而且是在某个顶点获得。,线性规划的可行域是一个什么形状？,20,2.由图解法得到线性规划解的一些特性,（1）线性规划的约束集（即可行域）是一个凸多 面体。,凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：,凸集中的“极点”，又称顶点或角点，是指它属于集，但不能表示成集中某二点连线的内点。如多边形的顶点。,21,（2）线性规划的最优解（若存在的话）必能在可行域的角点获得。,因为，由图解法可知，只有当目标直线平移到边界时，才能使目标 z 达到最大限度的优化。,问题：本性质有何重要意义？,它使得在可行域中寻优的工作由“无限”上升为“有限”，从而为线性规划的算法设计提供了重要基础。,22,2 图 解 法,重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例1中的目标函数变为max z=50 x1+50 x2，则线段BC上的所有点都代表了最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。,23,线性规划解的几种情形,唯一最优解,多重最优解,无解,无有限最优解（无界解）,24,3 图解法的灵敏度分析,灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj 变化时，对最优解产生的影响。3.1 目标函数中的系数 ci 的灵敏度分析 考虑例1的情况，ci 的变化只影响目标函数等值线的斜率，目标函数 z=50 x1+100 x2 在 z=x2(x2=z 斜率为0)到 z=x1+x2(x2=-x1+z 斜率为-1)之间时，原最优解 x1=50，x2=100 仍是最优解。一般情况：z=c1 x1+c2 x2 写成斜截式 x2=-(c1/c2)x1+z/c2 目标函数等值线的斜率为-(c1/c2)，当-1-(c1/c2)0（*）时，原最优解仍是最优解。,25,Max z=50 x1+100 x2 s.t.s.t x1+x2 300(A)2 x1+x2 400(B)x2 250(C)x1 0(D)x2 0(E)得到最优解：x1=50，x2=250 最优目标值 z=27500问题：C1，C2如何变化影响最优解?分析：C1=C2=50时 最优解为？K=-C1/C2=-1,K=0,K=-2最优解分别为？,C,x1+x2 300,2 x1+x2 400,x2 250,D,26,Max z=50 x1+100 x2 s.t.s.t x1+x2 300(A)2 x1+x2 400(B)x2 250(C)x1 0(D)x2 0(E)得到最优解：x1=50，x2=250 最优目标值 z=27500分析：C1=C2=50时 最优解为？K=-C1/C2=-1，此时最优解为B-C之间所有点。K=0,此时最优解为A-B之间所有点。K=-2最优解为C-D之间所有点。,C,x1+x2 300,2 x1+x2 400,x2 250,A(0,250),D,27,Max z=50 x1+100 x2 s.t.s.t x1+x2 300(A)2 x1+x2 400(B)x2 250(C)x1 0(D)x2 0(E)得到最优解：x1=50，x2=250 最优目标值 z=27500分析：K=-C1/C2，K若介于-1和0之间，即此时最优解不变。,C,x1+x2 300,2 x1+x2 400,x2 250,A(0,250),D,28,3 图解法的灵敏度分析,Max z=50 x1+100 x2 s.t.s.t x1+x2 300(A)2 x1+x2 400(B)x2 250(C)x1 0(D)x2 0(E)得到最优解：x1=50，x2=250 最优目标值 z=27500分析：K=-C1/C2，K若介于-1和0之间，即此时最优解不变。-1-C1/C20 当C1不变，C2为在什么范围内最优解不变？C1=50，-1-50/C20 50 C2 无穷大 即C1=50时，只要C2 50，最优解不变。同理可求出C2=100，0C1100，最优解不变。,29,Max z=50 x1+100 x2 s.t.s.t x1+x2 300(A)2 x1+x2 400(B)x2 250(C)x1 0(D)x2 0(E)得到最优解：x1=50，x2=250 最优目标值 z=27500,30,3 图解法的灵敏度分析,假设产品的利润100元不变，即 c2=100，代到式（*）并整理得 0 c1 100 假设产品的利润 50 元不变，即 c1=50，代到式（*）并整理得 50 c2+假若产品、的利润均改变，则可直接用式（*）来判断。假设产品、的利润分别为60元、55元，则-2-(60/55)-1 那么，最优解为 z=x1+x2 和 z=2 x1+x2 的交点 x1=100，x2=200。,31,3 图解法的灵敏度分析,3.2 约束条件中右边系数 bj 的灵敏度分析 当约束条件中右边系数 bj 变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例1的情况：假设设备台时增加10个台时，即 b1变化为310，这时可行域扩大，最优解为 x2=250 和 x1+x2=310 的交点 x1=60，x2=250。变化后的总利润-变化前的总利润=增加的利润(5060+100250)-(5050+100250)=500，500/10=50 说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。,32,3 图解法的灵敏度分析,假设原料 A 增加10 千克时，即 b2变化为410，这时可行域扩大，但最优解仍为 x2=250 和 x1+x2=300 的交点 x1=50，x2=250。此变化对总利润无影响，该约束条件的对偶价格为 0。解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于0，则最优目标函数值不变。,
