-线性规划的图解法-管理运筹学.pptx

运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外线性规划的图解法线性规划的图解法Linear ProgrammingLinear Programming第二章第二章学习重点及难点学习重点及难点 1、线性规划的、线性规划的图解法的求解过程图解法的求解过程 (重点重点)2、线性规划问题解的类型、线性规划问题解的类型 (熟练掌握熟练掌握)第二章第二章 线性规划的图解法线性规划的图解法第二章第二章 线性规划的图解法线性规划的图解法线性规划（Linear Programming，简记为LP）是运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较为成熟和应用上极为广泛的一个分支。特别是1947年G.B.Dantying提出了一般线性规划问题求解的方法单纯形法单纯形法之后，线性规划的理论与应用都得到了极大的发展。单纯形法单纯形法的有效性使它不仅是线性规划的最基本的算法之一，而且已成为整数规划和非线性规划某些算法的基础。1 线性规划问题及其数学模型一、一、线性规划问题的提出线性规划问题的提出 要利用线性规划的方法解决实际问题，首先要建立其数学模要利用线性规划的方法解决实际问题，首先要建立其数学模型型.数学模型数学模型是描述实际问题共性的抽象的数学形式，因此可是描述实际问题共性的抽象的数学形式，因此可以利用纯数学的方法进行研究，从而得到实际问题的性质及其解以利用纯数学的方法进行研究，从而得到实际问题的性质及其解决的办法。从实际问题中建立数学模型，主要有以下三个步骤：决的办法。从实际问题中建立数学模型，主要有以下三个步骤：(1)(1)根据影响所要达到目的的因素确定根据影响所要达到目的的因素确定决策变量决策变量；(2)(2)由决策变量和所要达到目的之间的函数关系确定由决策变量和所要达到目的之间的函数关系确定目标函数目标函数.(3)(3)由决策变量所受的限制条件确定决策变量所要满足的由决策变量所受的限制条件确定决策变量所要满足的约束条约束条件件；二、二、线性规划问题的数学模型线性规划问题的数学模型具体分析例具体分析例1、例、例2、例、例3，虽然它们的背景意义各不相，虽然它们的背景意义各不相同，但从数学模型角度，却具有以下一些同，但从数学模型角度，却具有以下一些共同要点共同要点：第一，第一，求一组求一组决策变量决策变量xi，并往往要求它们为非负；，并往往要求它们为非负；第二，第二，确定决策变量可能受到的约束，称为确定决策变量可能受到的约束，称为约束条件约束条件，它们可以用决策变量的线性等式或线性不等式来表示；它们可以用决策变量的线性等式或线性不等式来表示；第三，第三，在满足约束条件的前提下，使某个函数值达到最在满足约束条件的前提下，使某个函数值达到最大（如利润等）或最小（如成本、运费等）大（如利润等）或最小（如成本、运费等）.该函数称该函数称为为目标函数目标函数，它是决策变量的线性函数，它是决策变量的线性函数.具备以上三个要素的问题称为线性规划问题具备以上三个要素的问题称为线性规划问题.简单地说，简单地说，线性规划问题就是求一个线性目标函数在一组线性约束线性规划问题就是求一个线性目标函数在一组线性约束条件下的极值问题条件下的极值问题.二、二、线性规划问题的数学模型线性规划问题的数学模型一般表示形式：一般表示形式：.1、和式和式其他常用表示形式：其他常用表示形式：2、矩阵式矩阵式.3、向量式向量式302010当当当当z z值不断增加时，该直线值不断增加时，该直线值不断增加时，该直线值不断增加时，该直线x x2 2=-（3/53/5）x x1 1+Z/2500+Z/2500 沿着其法线方向向右上方移沿着其法线方向向右上方移沿着其法线方向向右上方移沿着其法线方向向右上方移动。动。动。动。2 线性规划的图解法线性规划的图解法max Z=1500 xmax Z=1500 x1 1+2500 x+2500 x2 2 s.t.3x s.t.3x1 1+2x+2x2 2 65 65 2x 2x1 1+x+x2 2 40 40 3x2 75 x x1 1,x,x2 2 0 0 由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B B （5 5，2525），最优值为），最优值为），最优值为），最优值为7000070000可行域、可行解可行域、可行解可行域、可行解可行域、可行解最优解、最优值最优解、最优值最优解、最优值最优解、最优值504030201010203040 x1可行域可行域可行域可行域50等值线等值线B唯一最优解唯一最优解*如将例1的目标函数设为z=1500 x1+1000 x2，那么，最优情况下，目标函数的等值线与直线1重合 这时，最优解有无穷多个，是线段BC上的所有点，最优值为32500.50403020101020304050BC无穷多最优解无穷多最优解无界解无界解如将例1的约束条件变为:3x1+2x2 65 2x1+x2 40 3x2 75 x1，x2 0那么，可行域成为一个上无界的区域，最优值z，这时，问题无有限最优解，即解无界。504030201010203040 x150B无可行解（无解）无可行解（无解）.如下述线性规划问题 max z=2x1+x2 s.t.x1+x2 2 2x1+3x2 8 x1,x2 0用图解法求解时看出不存在满足所有约束的公共区域（可行域）,即无可行解，当然也无最优解。这时，也简称为无解.线性规划问题解的特点和几种线性规划问题解的特点和几种可能情况：可能情况：线性规划问题的可行解的集合是线性规划问题的可行解的集合是凸集凸集凸集的凸集的极点（顶点）极点（顶点）的个数是有限的的个数是有限的最优解如果存在只可能在最优解如果存在只可能在凸集的极点凸集的极点上取上取得，而不可能发生在凸集的内部得，而不可能发生在凸集的内部线性规划问题的解可能是：线性规划问题的解可能是：唯一解、无穷唯一解、无穷多最优解、无界解和无可行解多最优解、无界解和无可行解(无解无解)3 线性规划图解法的灵敏度分析线性规划图解法的灵敏度分析灵敏度分析：在建立数学模型和求得最优解之后，灵敏度分析：在建立数学模型和求得最优解之后，研究线性规划的一些系数的变化对最优解产生什研究线性规划的一些系数的变化对最优解产生什么影响？么影响？重要的原因：重要的原因：1、模型中的系数一般都是估计值和预测值，不一、模型中的系数一般都是估计值和预测值，不一定非常准确；定非常准确；2、即使这些系数在某一时刻是精确值，它们也会、即使这些系数在某一时刻是精确值，它们也会随着市场条件的变化而变化，不会一成不变；随着市场条件的变化而变化，不会一成不变；3、有了灵敏度分析就不必为了应付这些变化而不、有了灵敏度分析就不必为了应付这些变化而不停的建立新的模型和求新的最优解。停的建立新的模型和求新的最优解。3020一、目标函数中的系数的灵敏度分析max Z=1500 xmax Z=1500 x1 1+2500 x+2500 x2 2 s.t.3x s.t.3x1 1+2x+2x2 2 65 65 2x 2x1 1+x+x2 2 40 40 3x2 75 x x1 1,x,x2 2 0 0504030201010203040 x150B由图示可知最优解为由图示可知最优解为由图示可知最优解为由图示可知最优解为B(5B(5，25),25),最优值为最优值为最优值为最优值为7000070000 x x2 2 =-3x=-3x1 1/2+/2+65 65 -3/23/2x2 2=25 0Z=cZ=c1 1x x1 1+c+c2 2x x2 2x x2 2=-c=-c1 1x x1 1/c/c2 2+z/c+z/c2 2 -c -c1 1/c/c2 2 -3/2-c -3/2-c1 1/c/c2 200一、目标函数中的系数的灵敏度分析-3/2 -c1/c2 0当当c2=2500不变时，不变时，0 c13750，最优解不变，最优解不变当当c1=1500不变时，不变时，1000 c2，最优解不变，最优解不变3020max Z=1500 xmax Z=1500 x1 1+2500 x+2500 x2 2 s.t.3x s.t.3x1 1+2x+2x2 2 65 65 2x 2x1 1+x+x2 2 40 40 3x2 75 x x1 1,x,x2 2 0 0 3x3x1 1+2x+2x2 2 66 66 x x1 1=16/3 x=16/3 x2 2=25=25Z=70500Z=70500可见资源可见资源可见资源可见资源A A每增加一个单每增加一个单每增加一个单每增加一个单位就可以多获得位就可以多获得位就可以多获得位就可以多获得500500元的利元的利元的利元的利润润润润.504030201010203040 x150B二、约束条件中常数项的灵敏度分析二、约束条件中常数项的灵敏度分析由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B(5B(5，25)25)最优值为最优值为最优值为最优值为7000070000二、约束条件中常数项的灵敏度分析二、约束条件中常数项的灵敏度分析对偶价格对偶价格:约束条件的常数项中每增加一个单位而约束条件的常数项中每增加一个单位而使最优目标函数值得到使最优目标函数值得到改进改进的数量称之为这个约的数量称之为这个约束条件的对偶价格。束条件的对偶价格。约束条件约束条件的对偶价格是的对偶价格是500元元约束条件约束条件的对偶价格是的对偶价格是 0元元当约束条件为当约束条件为松约束松约束时时,这个约束条件的对偶价格这个约束条件的对偶价格就为就为0 （该资源是（该资源是紧缺资源紧缺资源）否则当约束条件为否则当约束条件为紧约束紧约束时，这个约束条件的对时，这个约束条件的对偶价格不一定为偶价格不一定为0（该资源不是紧缺资源）（该资源不是紧缺资源）当约束条件常数项增加一个单位时当约束条件常数项增加一个单位时,有有:(1)如果对偶价格大于零如果对偶价格大于零,则其最优目标函数值得则其最优目标函数值得到改进到改进,即求最大值时即求最大值时,最优目标函数值变得更大最优目标函数值变得更大;求最小值时求最小值时,最优目标函数值变得更小最优目标函数值变得更小;(2)如果对偶价格小于零如果对偶价格小于零,则其最优目标函数值变则其最优目标函数值变坏坏,即求最大值时即求最大值时,最优目标函数值变得更小了最优目标函数值变得更小了;求求最小值时最小值时,最优目标函数值变得更大了最优目标函数值变得更大了;(3)如果对偶价格等于零如果对偶价格等于零,则其最优目标函数值不则其最优目标函数值不变。变。