第二章线性规划的图解法

管理运筹学第二章：线性规划的图解法第一节：线性规划问题的提出第二节：线性规划的图解法第三节：图解法的灵敏度分析本章的重点和难点：2：图解法的灵敏度分析1：线性规划的图解法线性规划的定义•求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。•满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素.第二章线性规划的图解法4在管理中一些典型的线性规划应用•合理利用线材问题：如何在保证生产的条件下，下料最少•配料问题：在原料供应量的限制下如何获取最大利润•投资问题：从投资项目中选取方案，使投资回报最大第二章线性规划的图解法•产品生产计划：合理利用人力、物力、财力等，使获利最大•劳动力安排：用最少的劳动力来满足工作的需要•运输问题：如何制定调运方案，使总运费最小第二章线性规划的图解法问题1:某工厂计划生产甲、乙两种产品，生产1kg的甲需耗煤9t、电力4kw.h、油3t；生产1kg的乙需耗煤4t、电力5kw.h、油10t；该厂现有煤360t、电力200kw.h、油300t。已知甲产品每千克的售价为7万元、乙产品每千克的售价为12万元。在上述条件下决定生产方案，使得总收入最大。第二章线性规划的图解法问题1具体数据如表所示：资源产品单耗资源甲乙资源限量煤(t)电(kw.h)油(t)9445310360200300单位产品价格712提出和形成问题建立模型求解结果的分析和应用第二章线性规划的图解法总收入记为f,则f=7x1+12x2，为体现对其求极大化，在f的前面冠以极大号Max，也就是：甲、乙产品的计划产量，记为x1，x2；在本例中资源煤、电、油的数量是有限的，对产品甲和乙的生产量构成了约束，表示为：决策变量：目标函数：约束条件：Max（maximize最大化）Min(minimum)s.t.(subjectto受制于)21127xxMaxf0,3001032005436049..21212121xxxxxxxxts第二章线性规划的图解法解：设安排甲、乙产量分别为x1，x2,总收入为f，则该问题的数学模型为：21127xxMaxf0,3001032005436049..21212121xxxxxxxxts第二章线性规划的图解法（1）决策变量：甲、乙产品的产量x1，x2★线性规划模型的三个基本要素：（也是所有规划问题的三个基本要素）：0,3001032005436049..21212121xxxxxxxxts决策变量：需要决策的量，即等待求解的未知数。目标函数：想要达到的目标，用决策变量的表达式表示。约束条件：由于资源有限，为了实现目标有哪些资源限制，用决策变量的等式或不等式表示。（3）约束条件：（2）目标函数：总收入最大，Maxf=7x1+12x2第二章线性规划的图解法什么是线性规划模型：决策变量为可控的连续变量。目标函数和约束条件都是线性的。32211ln2xxx21127xxMaxf0,3001032005436049..21212121xxxxxxxxtsx1≥0，x2≥0x1=0,1,2,3…n第二章线性规划的图解法ⅠⅡ资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元例2.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？第二章线性规划的图解法•目标函数：Maxz=50x1+100x2•约束条件：s.t.x1+x2≤300•2x1+x2≤400•x2≤250•x1,x2≥0第二章线性规划的图解法•一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥0第二章线性规划的图解法•对于只有两个变量的简单的线性规划问题，一般采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。第二章线性规划的图解法1.基本概念（1）可行解：满足约束条件的决策变量的取值（2）可行域：可行解的全体（3）最优解：使目标函数取得最优值的可行解（4）最优值：最优解代入目标函数所得到的值第二章线性规划的图解法例3.用图解法对下列线性规划模型进行求解。MaxZ=2x1+3x2x1+2x2≤84x1≤16x2≤12x1,x2≥0s.t.第二章线性规划的图解法18图解法求解的步骤：分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值。第二章线性规划的图解法9—8—7—6—5—4—3—2—1—0x2|||||||||123456789x1x1+2x284x1164x212x1+2x284x1164x212x1、x20第二章线性规划的图解法9—8—7—6—5—4—3—2—1—0|||||||||123456789x1x1+2x284x1164x212可行域ABCDO可行解：满足约束条件的解。红色区域中的每一个点（包括边界点）都是可行解。此区域是就是可行域。9—8—7—6—5—4—3—2—1—0x2|||||||||123456789x1x1+2x284x1164x212ABCDO目标函数Z=2x1+3x2在这个坐标平面上，它可以表示以Z为参数、-2/3为斜率的一族平行线：21233xxz位于同一直线上的点，具有相同的目标函数，称为“等值线”。9—8—7—6—5—4—3—2—1—0x2当Z值由小变大时，直线沿其法线方向向右上方移动。当移动到C时，Z值在可行域的边界上实现最大化。最优解（4，2），Z=14。|||||||||123456789x1x1+2x284x1164x212ABCDO最优解(4,2)最优生产方案:产品1生产4kg，产品2生产2kg，最大利润14元(最优值）。21233xxz•结论：•线性规划问题如果有最优解,则最优解一定在可行域的边界上取得.第二章线性规划的图解法无穷多最优解12121212max228416..412,0Zxxxxxstxxx9—8—7—6—5—4—3—2—1—0x2|||||||||123456789x1x1+2x284x1164x212O可行域第二章线性规划的图解法当移动到AB线段时，Z值在线段CD上实现最大化。线段CD上的任意一点都使Z取得相同的最大值，这个线性规划问题有无穷多最优解。9—8—7—6—5—4—3—2—1—0x2|||||||||123456789x1x1+2x284x1164x212ABCDO可行域第二章线性规划的图解法无可行解可行域为空集，无可行解，当然也无最优解。9—8—7—6—5—4—3—2—1—0x2|||||||||123456789x1Ol2l1第二章线性规划的图解法Maxz=x1+2x2s.t.x1+2x2≤84x1≤164x2≤12x1≥3x2≥3无界解12121212max221.20,0fxxxxstxxxxx1x20123456789654321121xx1220xx线性规划问题可行域无界，目标函数可以增大到无穷大第二章线性规划的图解法12121212min221.20,0fxxxxstxxxx该问题如果求目标函数的最小值，由下图可以看出在顶点B取得最优解：12min102xxf，，最优值为。x1x20123456789654321121xx1220xxB（1，0）第二章线性规划的图解法唯一解无穷多解无有限最优解无可行解有最优解无最优解求解一个线性规划问题就是要判断该问题属于那种情况，当问题有最优解时，还需要在可行区域中求出使目标函数达到最优值的点，也就是最优解，以及目标函数的最优值。第二章线性规划的图解法•练习题：•1.考虑下面线性规划问题：•Maxz=2x1+3x2•s.t.x1+2x2≤6•5x1+3x2≤15•x1,x2≥0（1）画出其可行域（2）当Z=6时，画出等值线2x1+3x2=6（3）用图解法求出其最优解以及最优目标函数值第二章线性规划的图解法31例2：.某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？第二章线性规划的图解法32解：目标函数：Minf=2x1+3x2约束条件：s.t.x1+x2≥350x1≥1252x1+x2≤600x1,x2≥0采用图解法。如下图：得Q点坐标（250，100）为最优解。第二章线性规划的图解法得Q点坐标（250，100）为最优解X1=250,x2=100时minf=800100200300400500600100200300400600500x1=125x1+x2=3502x1+x2=600x1x2Q第二章线性规划的图解法•例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：•问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？第二章线性规划的图解法ⅠⅡ资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元•数学模型为：•求解得：x1=50,x2=250maxz=27500第二章线性规划的图解法0,2504002300..10050max212212121xxxxxxxtsxxz36•引入松驰变量（含义是资源的剩余量）例1中引入s1，s2，s3模型化为Maxz=50x1+100x2+0s1+0s2+0s3s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0对于最优解x1=50x2=250，s1=0s2=50s3=0说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。第二章线性规划的图解法0,2504002300..10050max212212121xxxxxxxtsxxz松弛变量和剩余变量•松弛变量：在线性规划中，对于“≤”约束条件中没有使用的资源或能力称之为松弛变量。•剩余变量：在线性规划中，对于“≥”约束条件，可以增加一些代表最低限约束的超过量，称之为剩余变量。第二章线性规划的图解法38线性规划的标准化•一般形式目标函数:Max（Min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥0第二章线性规划的图解法•标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2…………am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥0，bi≥0第二章线性规划的图解法40可以看出，线性规划的标准形式有如下四个特点：–目标最大化；–约束为等式