《第二章线性规划的图解法》由会员分享，可在线阅读，更多相关《第二章线性规划的图解法（64页珍藏版）》请在金锄头文库上搜索。
1、管理运筹学,第二章：线性规划的图解法,第一节：线性规划问题的提出,第二节：线性规划的图解法,第三节：图解法的灵敏度分析,本章的重点和难点：,2：图解法的灵敏度分析,1：线性规划的图解法,线性规划的定义,求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。 满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素.,第二章 线性规划的图解法,4,在管理中一些典型的线性规划应用 合理利用线材问题：如何在保证生产的条件下，下料最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最
2、大,第二章 线性规划的图解法,产品生产计划：合理利用人力、物力、财力等，使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小,第二章 线性规划的图解法,问题1:某工厂计划生产甲、乙两种产品， 生产1kg的甲需耗煤9t、电力4kw.h、油3t； 生产1kg的乙需耗煤4t、电力5kw.h、油10t； 该厂现有煤360t、电力200kw.h、油300t。 已知甲产品每千克的售价为7万元、乙产品每千克的售价为12万元。 在上述条件下决定生产方案，使得总收入最大。,第二章 线性规划的图解法,问题1具体数据如表所示：,第二章 线性规划的图解法,总收入记为f,则
3、f=7x1 +12x2 ，为体现对其求极大化，在f 的前面冠以极大号Max， 也就是：,甲、乙产品的计划产量，记为x1 ，x2；,在本例中,资源煤、电、油的数量是有限的，对产品甲和乙的生产量构成了约束，表示为：,决策变量：,目标函数：,约束条件：,Max （maximize最大化） Min (minimum) s.t. (subject to受制于),第二章 线性规划的图解法,解：设安排甲、乙产量分别为x1 ，x2 ,总收入为 f ， 则该问题的数学模型为：,第二章 线性规划的图解法,（1）决策变量：甲、乙产品的产量x1 ，x2,线性规划模型的三个基本要素： （也是所有规划问题的三个基本要素）
4、：,决策变量：需要决策的量，即等待求解的未知数。,目标函数：想要达到的目标，用决策变量的表达式表示。,约束条件：由于资源有限，为了实现目标有哪些资源限制，用决策变量的等式或不等式表示。,（3）约束条件：,（2）目标函数：总收入最大，Max f = 7 x 1 +12 x 2,第二章 线性规划的图解法,什么是线性规划模型：,决策变量为可控的连续变量。,目标函数和约束条件都是线性的。,第二章 线性规划的图解法,例2.某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：,问题：工厂应分别生产多少单位、产品才能使工厂获利最多？,第二章 线
5、性规划的图解法,目标函数：Maxz = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0,第二章 线性规划的图解法,一般形式 目标函数：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.基本概念 （1）可行解：满足约束条件的决策变量的取值 （2）可行域：可行解的全体 （3）最优解：使目标函数取得最优值的可行解 （4）最优值：最优解代入目标函数所得到的值,第二章 线性规划的图解法,例3.用图解法对下列线性规划模型进行求解。,s.t.,第二章 线性规划的图解法,18,图解法求解的步骤： 分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值。,第二章 线性规划
7、的图解法,9 8 7 6 5 4 3 2 1 0,x2,| | | | | | | | | 1 2 3 4 5 6 7 8 9,x1,x1 + 2x2 8,4x1 16,4 x2 12,x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,第二章 线性规划的图解法,9 8 7 6 5 4 3 2 1 0,| | | | | | | | | 1 2 3 4 5 6 7 8 9,x1,可行域,可行解：满足约束条件的解。红色区域中的每一个点（包括边界点）都是可行解。此区域是就是可行域。,9 8 7 6 5 4 3 2 1 0,x2,目标函数 Z = 2x1 + 3x2在这个坐标平面上，
8、它可以表示以Z为参数、-2/3为斜率的一族平行线：,位于同一直线上的点，具有相同的目标函数，称为“等值线”。,9 8 7 6 5 4 3 2 1 0,x2,当Z值由小变大时，直线 沿其法线方向向右上方移动。当移动到C时，Z值在可行域的边界上实现最大化。最优解（4，2），Z=14。,最优解 (4, 2),最优生产方案:产品1生产4kg，产品2生产2kg，最大利润14元(最优值）。,结论： 线性规划问题如果有最优解,则最优解一定在可行域的边界上取得.,第二章 线性规划的图解法,无穷多最优解,9 8 7 6 5 4 3 2 1 0,x2,| | | | | | | | | 1 2 3 4 5 6 7
9、 8 9,x1,x1 + 2x2 8,4x1 16,4 x2 12,O,可行域,第二章 线性规划的图解法,当移动到AB线段时，Z值在线段CD上实现最大化。 线段CD上的任意一点都使Z取得相同的最大值，这个线性规划问题有无穷多最优解。,9 8 7 6 5 4 3 2 1 0,x2,| | | | | | | | | 1 2 3 4 5 6 7 8 9,x1,x1 + 2x2 8,4x1 16,4 x2 12,A,B,C,D,O,可行域,第二章 线性规划的图解法,无可行解,可行域为空集，无可行解，当然也无最优解。,9 8 7 6 5 4 3 2 1 0,x2,| | | | | | | | | 1
10、 2 3 4 5 6 7 8 9,x1,l2,l1,第二章 线性规划的图解法,Maxz = x1 + 2 x2 s.t. x1 +2 x2 8 4x1 16 4x2 12 x1 3 x2 3,无界解,线性规划问题可行域无界，目标函数可以增大到无穷大,第二章 线性规划的图解法,该问题如果求目标函数的最小值，由下图可以看出在顶点B取得最优解：,B（1，0）,第二章 线性规划的图解法,唯一解 无穷多解 无有限最优解 无可行解,有最优解,无最优解,求解一个线性规划问题就是要判断该问题属于那种情况，当问题有最优解时，还需要在可行区域中求出使目标函数达到最优值的点，也就是最优解，以及目标函数的最优值。,第
11、二章 线性规划的图解法,练习题： 1.考虑下面线性规划问题： Maxz = 2 x1 + 3 x2 s.t. x1 +2 x2 6 5x1 +3 x2 15 x1 , x2 0 （1）画出其可行域 （2）当Z=6时，画出等值线2 x1 + 3 x2 =6 （3）用图解法求出其最优解以及最优目标函数值,第二章 线性规划的图解法,31,例2：.某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。
12、又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？,第二章 线性规划的图解法,32,解：目标函数： Min f = 2x1 + 3 x2 约束条件： s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。,第二章 线性规划的图解法,得Q点坐标（250，100）为最优解 X1=250,x2=100时minf=800,100,200,300,400,500,600,100,200,300,400,6
13、00,500,x1 =125,x1+x2 =350,2x1+x2 =600,x1,x2,Q,第二章 线性规划的图解法,例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表： 问题：工厂应分别生产多少单位、产品才能使工厂获利最多？,第二章 线性规划的图解法,数学模型为： 求解得：x1=50, x2=250 maxz=27500,第二章 线性规划的图解法,36,引入松驰变量（含义是资源的剩余量） 例1 中引入 s1， s2， s3 模型化为 Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3
14、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千克。,第二章 线性规划的图解法,松弛变量和剩余变量,松弛变量：在线性规划中，对于“”约束条件中没有使用的资源或能力称之为松弛变量。 剩余变量：在线性规划中，对于“”约束条件，可以增加一些代表最低限约束的超过量，称之为剩余变量。,第二章 线性规划的图解法,38,线性规划的标准化 一般形式 目标函数: 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,第二章 线性规划的图解法,标准形式 目标函数： Max z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2
