第2章 线性规划的图解法-new.ppt

1、第二章：线性规划的图解法，1。提出问题2。图解法的灵敏度分析。第二章：线性规划的图解法。一些典型的线性规划在管理中的应用使线材得到了合理的利用：如何在保证生产的条件下减少配料；如何在原材料供应限制下获得最大利润；投资问题：从投资项目中选择方案。投资回报最大化的产品生产计划：合理利用人力、物力、财力等。以实现利润最大化。劳动力安排：用最少的劳动力满足工作需要。运输问题：如何制定运输计划，使总运费最小化。2、线性规划的构成：目标函数最大或最小约束满足决策变量，可控因素用符号表示。1.问题被提出来了。例1。工厂应该在计划期间安排两种产品的生产。众所周知，生产单位产品所需的设备以及甲、乙原料的消耗和资

2、源限制如下：问题：工厂应分别生产，线性规划模型：目标函数：max z=50 x1 100 x2约束：s.t. x1x2300 2x1x2400x250x1，x20，1问题提出，建模过程1。理解要解决的问题，明确在什么条件下追求什么目标；2.定义决策变量(x1，x2，xn)，每组值代表一个方案；3.以决策变量的线性函数形式写出目标函数，并确定最大化或最小化目标；4.使用一组决策变量的等式或不等式来表示在解决问题的过程中必须遵循的约束。一般形式目标函数：最大(最小)z=c1 x1 c2 x2 cn xn约束：s.t. a11 x1 a12 x2 a1n xn (=，)b1 a21 x1 a22 x

3、2 a2n xn (=，)b2 am1 x1 am2 x2 amn xn (=，)bm x1，x2，xn 0，4，示例1。目标函数：max z=50 x1 100 x2约束：s . t . x1x 2300(a)2x 1x 2400(b)x2250(c)X10(d)x20(e)得到最优解：x1=50，x2=250。最佳目标值是z=27500。2图解法，对于只有两个决策变量的线性规划问题，线性规划问题的相关概念可以通过在平面直角坐标系上作图来表示和求解。该方法在下面的示例1中详细说明：(1)以决策变量X1和X2作为坐标向量来建立直角坐标系。在直角坐标系中，图上任意点的坐标代表一组决策变量值，示例

4、1中的每个约束条件代表一个半平面。6，2图解法，(2)对于每个不等式(约束条件)，首先把它的等式作为坐标系中的一条直线，然后确定由不等式确定的半平面。7，x1，x1，x2，x2，2，(3)将五个图合并成一个图，并取每个约束条件的公共部分，如图2-1所示。(4)目标函数z=50 x1 100 x2，当z取一个固定值时，得到一条直线，并且直线上的每一点都有相同的目标函数值，称为“等值线”。平行移动等值线。当移动到B点时，Z在可行区域内最大化。a、b、c、d和e是可行域的顶点，并且可行域的顶点对于有限数量的约束也是有限的。9，2图解法，线性规划的标准化内容之一：引入松弛变量(意味着剩余资源量)s1，

5、s2，S3被建模为目标函数：max z=50 x1 100 x2 0 s1 0 s2 0 s3约束：s . t . x1x2s 1=3002 x1 2s 2=400 x2 3=250 x1，x2，s1，s2，S3 0对于最优解x1=50 x2=250，s1=0 s2=50 s3=0， 它表明，生产50个单位的产品和250个单位的产品将消耗所有可能的设备小时和原材料b，但仍然有50公斤的原材料a，10，2图解法，重要的结论：如果线性规划有一个最优解，必须有一个可行域的顶点对应一个最优解； 无限多的最优解。如果将示例1中的目标函数更改为max z=50 x1 50 x2，则线段BC上的所有点都代表

6、最优解。无界解。也就是说，行字段的范围扩展到无限，并且目标函数值可以是无限的或无限小的。一般来说，这表明模型是错误的，忽略了一些必要的约束；没有可行的解决办法。如果将约束条件4x1 3x21200添加到示例1的数学模型，则可行区域是空间域，并且不存在满足约束条件的解，当然，不存在最优解。11，图解法有无界解，而线性规划有无界解，即没有最优解。对于下列线性规划问题：约束条件：最大z=x1x2X1-x2 1 -3x1 2x2 6 x1 0，x2 0，12，图形解是无界的，结果用图形方法求解。如图所示，可以看出问题的可行域是无界的，目标函数值可以增加到无穷大，成为无界解，即没有最优解。13，1，2，

7、3，4，-1，-2，1，2，3，4，-1，z=0=x1x2，z=1=x1x2，z=3=x1x2，进一步讨论。但是，由于原料甲和原料乙的规格不同，它们的加工时间也不同。每吨原料甲加工2小时，每吨原料乙加工1小时，公司共有600个加工小时。我们也知道原材料甲的价格是每吨2万元，原材料乙的价格是每吨3万元。在满足生产需求的前提下，在公司加工能力范围内，如何采购原材料甲和乙，使采购成本最低？14，进一步讨论，解决方案：目标函数：min f=2x1 3 x2约束：s.t. x1 x2 350 x1 125 2 x1 x2 600 x1，x2 0采用图解法。如下图所示，Q点(250，100)的坐标是最优解

8、。15，3图形方法的灵敏度分析，线性规划目标函数的标准化一般形式：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 . a11x 1 a12x 2 a1n xn=b1a 21 xa 22x 2 a2 nxn=b2am 1x 1 a2 x2 amnxn=图形方法bm x1，x2，xn 0，bi 0，16，

9、3的灵敏度分析表明，线性规划的标准形式有以下四个特殊点：目标最大化； 约束是等式；决策变量不是负的；右端项不是负数。对于各种非标准线性规划问题，我们总是可以通过下面的变换把它们转化为标准：17，3图解法的灵敏度分析。1.最小化目标函数：如果目标函数是min f=c1x1c2cnxn (can) make z -f，那么最小化问题具有与下面的最大化问题相同的最优解。即max z=-c1x1-c2x2 - cnxn，但必须注意的是，虽然上述两个问题的最优解是相同的，但它们的最优解的目标函数值相差一个符号，即最小f-max z的灵敏度分析，18，3图解法，2。约束条件不是等式的问题：如果约束条件是a

10、i1 x1 ai2 x2 ain xn bi，可以引入一个新的变量S，使其等于约束s=bi(ai1 x1 ai2 x2 ain xn)的左右两边之差。显然，S还有一个非负约束，即s0。这时，新的约束条件就变成了ai1x1ai2ainxn s=bi，19，3的图解法的灵敏度分析。当约束条件是ai1x1ai2ainxn bi时，类似地，s=(ai1x1ai2ainxn)-bi显然，s也具有非负约束，即s0。此时，新的光束减少条件成为图形方法AI1x1ai2ainxn-s=bi，20，3的灵敏度分析，并且当不等式“小于或等于”时，为了将约束从不等式变为等式而引入的变量S被称为“松弛变量”。当不等式“

11、大于或等于”时，称为“剩余变量”。如果原问题中有几个不相等的约束，那么当每个约束转化为标准形式时，必须引入不同的松弛变量或剩余变量。21，3。右端项具有负值的问题：在标准形式中，要求右端项的每个组成部分都必须是非负值。当某个右端项的系数为负时，如bi0，将等式约束的两端同时乘以-1，得到：-ai1x1-ai2x2-ainxn=-bi。3灵敏度分析的图解法，例如：将下面的线性规划问题转化为标准形式min f=2x 1-3x 24 x3 s . t . 3x 14 x2-5x 36 2x 1 x3 8 x1x 2 x3=-9x 1，x2，x3 0解：首先，将目标函数转化为最大化：让z=-f=-2x

12、1 3x2-4x3考虑约束条件，有两个不等式约束条件，并引入松弛变量或剩余变量x4，x5 0。第三个约束的右端是负的，在等式的两边乘以-1。22，3，通过上面的变换，我们可以得到下面的标准线性规划问题：max z=-2x 13 x2-4x 3s . t . 3x 14 x2-5x 3 x4=62x 1x 3-X5=8-x1-x2-x3=9 x1，x2，x3，x4，x50 * * *。当变量xj没有非负约束时，xj=xj- xj 其中xj0，xj 0表示一个无符号的受限变量，由两个非负变量之差决定。当然，xj的符号取决于xj和XJ的大小。”，23，3图解法灵敏度分析：在建立数学模型并找到最优解后

13、，研究线性规划的一个或多个参数(系数)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 (*)时，原来的最优解仍然是最优解。24，3图形灵敏度分析，假设产品的利润100元不变，即c2=100，

14、用公式(*)代替，整理为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。25，3图解法的灵敏度分析，3.2约束条件下右系数bj的灵敏度分析当约束条件下的右系数bj改变时，线性规划的可行域也改变，这可能导致最优解的改变。考虑示例1的情况：当添加10个站点时，即b1变为310，则可行区域扩展，并且最优解是x2=250和x1 x2=310，x1=60，x2=250的交集。变更后总利润-变更前总利润=增加利润(5060 100250)-(50 50 100 250)=500，500/10=50元表明，当设备容量在一定范围内增加(减少)一个单位时，50元利润可以增加(减少)，这就是这个约束条件的双重价格。26，3。假设当原料A增加10千克时，即b2变为410，则可行区域扩大，但是最优解仍然是x2=250和x1