韩伯棠管理运筹学(第三版)_第二章_线性规划的图解法

.,1,线性规划是运筹学的一个重要分支。它是现代科学管理的重要手段之一，是帮助管理者作出最优决策的一个有效的方法。下面看看一些在管理上经常应用的典型线性规划问题：1合理利用线材问题。现有一批长度一定的钢管，由于生产的需要，要求截出不同规格的钢管若干。试问应如何下料，既满足了生产的需要，又使得使用的原材料钢管的数量最少。2配料问题。用若干种不同价格不同成分含量的原料，用不同的配比混合调配出一些不同价格不同规格的产品，在原料供应量的限制和保证产品成分的含量的前提下，如何获取最大的利润。,.,2,3投资问题。从许多不同的投资项目中选出一个投资方案，使得投资的回报为最大。4产品生产计划。合理充分地利用厂里现有的人力、物力、财力，作出最优的产品生产计划，使得工厂获利最大。5劳动力安排。某单位由于工作需要，在不同时间段需要不同数量的劳动力，在每个劳动力工作日连续工作八小时的规则下，如何安排劳动力，才能用最少的劳动力来满足工作的需要。,.,3,6运输问题。一个公司有若干个生产单位与销售单位，根据各生产单位的产量及销售单位的销量，如何制定调运方案，将产品运到各销售单位而总的运费最小。以上的这些问题，线性规划都能成功地加以解决。当然其在管理上的应用远不止这些。这些例子都有一个共同的特点。首先，每个例子中都要求达到某些数量上的最大化或最小化的目标。如问题1，是要求使用原料钢管最少；问题2是要求利润最大；问题3是要求投资回报最大等等。在所有线性规划的问题中某些数量上的最大化或最小化就是线性规划问题的目标。其次，所有线性规划问题都是在一定的约束条件下来追求其目标的。例如问题1，是在满足生产需要的一定数量、不同规格的钢管的约束下来追求原材料钢管的最小使用量。而在问题2中是在原料供应量的限制和保证产品成分的含量约束下来追求最大利润的。,.,4,例1某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A，B两种原材料的消耗，以及资源的限制，如下表所示。,该工厂每生产一单位产品I可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少个产品和产品才能使工厂获利最多?,.,5,.,6,这个问题可以用以下的数学模型来加以描述。工厂目前要决策的问题是生产多少个产品和生产多少个产品，把这个要决策的问题用变量x1、x2来表示，则称x1和x2为决策变量，即决策变量x1=生产I产品的数量，决策变量x2=生产产品的数量。用x1和x2的线性函数形式来表示工厂所要求的最大利润的目标：maxZ=50 x1+100 x2（称为目标函数）。其中max为最大化的符号(最小化为min)；50和100分别为单位产品、的利润。同样也可以用x1和x2的线性不等式来表示问题的约束条件。对于台时数的限制可以表示为：X1+X2300同样，两种原材料的限量可分别表示为：2X1+X2400,X2250.除了上述约束外，显然还应该有x10，x20，因为产品,产品的产量是不能取负值的。综上所述，就得到了例1的数学模型如下：,.,7,目标函数：maxZ=50 x1+100 x2，满足约束条件：x1+x2300，2x1+x2400，x2250,x10,x20.由于上述数学模型的目标函数为变量的线性函数，约束条件也为变量的线性等式或不等式，故此模型称之为线性规划。如果目标函数是变量的非线性函数，或约束条件中含有变量非线性的等式或不等式的数学模型则称之为非线性规划。把满足所有约束条件的解称为该线性规划的可行解。把使得目标函数值最大(即利润最大)的可行解称为该线性规划的最优解，此目标函数值称为最优目标函数值，简称最优值。,.,8,1要正确理解所要解决的问题，要搞清在什么条件下，追求什么样的目标。2定义决策变量，每一个问题都用一组决策变量(X1，X2,Xn)表示任何一个方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的。3用决策变量的线性函数形式写出所要追求的目标，称之为目标函数，按问题的不同，要求目标函数实现最大化或最小化。4用一组决策变量的等式或不等式来表示在解决问题过程上所必须遵循的约束条件。满足以上2、3、4三个条件的数学模型称之为线性规划的数学模型，其一般形式为:,.,9,线性规划的数学模型的一般形式为:,目标函数：max(min)Z=c1x1+c2x2+cnxn约束条件：a11x1+a12x2+a1nxn(=,)b1,a21x1+a22x2+a2nxn(=,)b2,am1x1+am2x2+amnxn(=,)bm,x1,x2,xn0.,.,10,对于只包含两个决策变量的线性规划问题，可以用图解法来求解。大于两个决策变量不能用图解法来解了。图解法.首先把每个约束条件（代表一个平面）画在二维坐标轴上。,100,300,100,300,x1,x2,.,11,100,400,100,300,x1,x2,100,100,300,x1,x2,.,12,100,400,100,300,x1,x2,Z=27500=50 x1+100 x2,阴影部分的每一点(包括边界线)都是这个线性规划的可行解，而此公共部分是例1的可行解的集合，称为可行域。,B点为最优解，坐标为（50，250）,Z=0=50 x1+100 x2,.,13,问题的解：,最佳决策为x1=50,x2=250，此时z=27500。这说明该厂的最优生产计划方案是生产I产品50单位，生产产品250单位，可得最大利润27500元。把x1=50,x2=250代入约束条件得：50+250=300台时设备250+250=350千克原料A，1250=250千克原料B这表明了生产50单位产品和250单位产品将消耗完所有可使用的设备台时数和原料B，但对原料A来说只消耗了350千克，还有(400350)=50千克没有使用。在线性规划中，对一个约束条件中没使用的资源或能力的大小称之为松弛量。,.,14,松弛变量和线性规划标准化,为了把一个线性规划标准化，需要有代表没使用的资源或能力的变量，称之为松弛变量，记为Si。显然这些松弛变量对目标函数不会产生影响，可以在目标函数中把这些松弛变量的系数看成零，加了松弛变量后我们得到如下的例1的数学模型：目标函数：maxZ=50 x1+100 x2+0s1+0s2+0s3，约束条件：x1+x2+s1=300,2x1+x2+s2=400,x2+s3=250,x1,x2,s1,s2,s30,.,15,像这样把所有的约束条件都写成等式，称为线性规划模型的标准化，所得结果称为线性规划的标准形式。在标准型中bj(右边常量)都要大于等于零，对某个bj小于零时，只要方程两边都乘以(-1)即可。实际上以后可看到应同时具备如下三个条件的模型才是标准型：一是约束条件必须化为等式；二是所有变量必须化为大于或者等于零；三是约束条件中的右端常数项必须是大于或者等于零。对例1的最优解x1=50,x2=250来说，松弛变量的值如下所示：约束条件松弛变量的值设备台时数s1=0原料As2=50原料Bs3=0,.,16,线性规划问题解的有如下特点：,1如果某一个线性规划问题有最优解，则一定有一个可行域的顶点对应一个最优解。2线性规划存在有无穷多个最优解的情况。若将例1中的目标函数变为求maxZ=50 x1+50 x2，则可见代表目标函数的直线平移到最优位置后将和直线x1+x2=300重合。详见下图。此时不仅顶点B，C都代表了最优解，而且线段BC上的所有点都代表了最优解，这样最优解就有无穷多个了。当然这些最优解都对应着相同的最优值（只有一个）：50 x1+50 x2=5050+50250=15000。,.,17,100,400,100,300,x1,x2,Z=15000=50 x1+50 x2,Z=0=50 x1+50 x2,.,18,线性规划存在无界解，即无最优解的情况。对下述线性规划问题：目标函数：maxz=x1+x2约束条件：x1-x21-3x1+2x26x10，x20,3,.,19,从图中可知该问题可行域无界，目标函数值可以增大到无穷大，成为无界解即无最优解。出现这种情况，一般说明线性规划模型有错误，该模型中忽略了一些实际存在的必要的约束条件。,注意啊,.,20,4线性规划存在无可行解的情况。若在例1的数学模型中再增加一个约束条件4x1+3x21200，显然可见新的线性规划的可行域为空域，也即不存在满足所有约束条件的x1和x2的解，当然更不存在最优解了。出现这种情况是由于约束条件自相矛盾导致的建模错误。,100,400,100,300,x1,x2,.,21,目标函数最小化的线性规划问题,某公司由于生产需要，共需要A，B两种原料至少350吨(A，B两种材料有一定替代性)，其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低?解：设x1为购进原料A的吨数，x2为购进原料B的吨数。得到了此线性规划的数学模型如下：目标函数：minf=2x1+3x2，约束条件：x1+x2350，x1125，2x1+x2600,x1,x20.,例2,.,22,用图解法来解：,Q,Q点坐标为x1=250,x2=100,.,23,Q点坐标为x1=250,x2=100。也即得到此线性规划问题的最优解，购买A原料250吨，购买B原料100吨，可使成本最小，即2x1+3x2=2250+3100=800(万元)。分析:可知购买的原料A与原料B的总量为250+100=350(吨)正好达到约束条件的最低限，所需的加工时间为2250+1100=600正好达到加工时间的最高限。而原料A的购进量250吨则比原料A购进量的最低限125吨多购进了250-125=125吨，这个超过量在线性规划中称为剩余量。,目标函数在可行域内Q点处取得最小值。Q点的坐标下面两方程的交点：,.,24,同样对于约束条件中，可以增加一些代表最低限约束的超过量，称之为剩余变量，把约束条件变为等式约束条件，加了松弛变量与剩余变量后例2的数学模型变为标准型（注意松弛变量符号为正，而剩余变量符号为负）：目标函数：minf=2x1+3x2+0s1+0s2+0s3约束条件：x1+x2-s1=350，x1-s2=125,2x1+x2+s3=600,x1,x2,s1,s2，s30.s1,s2为剩余变量，s3为松弛变量，上式中所有的约束条件也都为等式，故这也是线性规划问题的标准形式。对应于约束条件的剩余变量和松弛变量的值分别为：s1=0,s2=125,s3=0,.,25,由上节可知，线性规划的标准形式可写为目标函数：maxZ=c1x1+c2x2+cnxn或：minf=c1x1+c2x2+cnxn约束条件：a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2,am1x1+am2x2+amnxn=bm.x1,x2,xn0.其中Ci为第i个决策变量Xi在目标函数中的系数，aij为第i个约束条件中第j个决策变量xj的系数，bj为第j个约束条件中的常数项，要求bj0。当bj0时，可在方程两边都乘以-1使bj0。上节所提到的松弛变量和剩余变量都可以看成决策变量，也可以用Xi来表示而不用Si来表示。,.,26,同时满足下面三个条件的模型称为标准型：一、约束条件为等式。二、每个变量（包括松弛变量和剩余变量）都要0。三、约束条件的右边常数项要0。,.,27,灵敏度分析,所谓灵敏度分析就是在建立数学模型和求得最优解之后，研究线性规划的一些系数ci,aij,bj变化时，对最优解产生什么影响?灵敏度分析是非常重要的，首先是因为ci,aij,bj这些系数都是估计值和预测值，不一定非常精确，再则即使这些系数值在某一时刻是精确值，它们也会随着市场条件的变化而变化，不会一成不变的。例如，原材料的价格、商品的售价、加工能力、劳动力的价格等等的变化都会影响这些系数的变化，有了灵敏度分析就不必为了应付这些变化而不停地建立新的模型和求其新的最优解，也不会由于系数的估计和预测的精确性而对所求得的最优解存有不必要的怀疑。以下用图解法的灵敏度分析对目标函数中的系数ci以及对约束条件中的常数项bj进行灵敏度分析。,.,28,目标函数maxZ=C1X1+C2X2=50 x1+100 x2以例1来看一下Ci的变化是如何来影响其最优解的。从例1中知道生产一个单位的I产品可以获利50元(C1=50)，生产一个单位的产品可以获利100元(C2=100)。在目前的生产条件下求得生产I产品50单位，生产产品250单位可以获得最大利润。当I、产品中的某一产品的单位利润增加或减少时，往往都能意识到为了获取最大利润就应该增加或减少这一产品的产量，也就是改变最优解。但是往往不能精确地定出这一产品利润变化的上限与下限，利润在这个范围内变化时其最优解不变，即仍然生产50单位的I产品和250单位的产品而使获利最大。注意最优解不变不等于最优值不变。下面就用图解方法定出其上限与下限。,一、目标函数中的系数Ci的灵敏度分析,.,29,.,30,直线E的方程为：x1+x2=300,可改写为：x2=-x1+300,其斜率为-1。同理直线F:x2=0 x1+250的斜率为0。直线G:x2=-2x1+400的斜率为-2。而且目标函数：z=c1x1+c2x2可写为：x2=-c1/c2x1+z/c2可知目标函数的斜率为-c1/c2。,各直线的斜率,.,31,下面讨论Ci在什么范围内变动时，最优解位于哪些点。由上所述：1、当-1-c1/c20(2.1)时，即直线E的斜率-c1/c2直线F的斜率。目标函数的直线在E与F之间变动。故最优解仍然为B点。,.,32,问题1：固定C2，问C1在什么范围内变动时，B仍为最优解?设C2=100,则有-1-C1/1000,0C1100.即当C2=100，0C1100时B仍为最优解。问题2：固定C1，问C2在什么范围内变动时，B仍为最优解?设C1=50,则有-1-50/C20,50C2+.即当C1=50，50C2+时B仍为最优解。,.,33,2、同样在C1和C2中一个值确定不变时，可求出另一个值的变化范围，使其最优解在C点(或在A点，或在D点)。例如当0-C1/C2+时，最优解在A点（即从直线F反时针转到X2轴）。当-2-C1/C2-1时，最优解在C点。当-C1/C2-2时，最优解在D点,.,34,3、如果当C1和C2都变化时，则可以通过-1-C1/C20(2.1)式，可以判断B点是否仍为其最优解，例如当C1=60；C2=55时，因为-C1/C2=-60/55=-1.09，不满足(2.1)不等式，可知B点已不是其最优解了，但-2(直线G的斜率)-60/55-1(直线E的斜率)，所以此时C点(其坐标为x1=100，x2=200)为其最优解。,.,35,当约束条件右边系数bj变化时，其线性规划的可行域也将变化，这样就可能引起最优解的变化。为了说明这方面的灵敏度分析，不妨假设例1中的设备台时数增加了10个台时，共有台时数310个，这样例1中的设备台时数的约束条件就变为：x1+x2310,增加了10个台时，扩大了可行域。,二、约束条件中右边系数bj的灵敏度分析,.,36,图26,100,400,100,300,x1,x2,C,A,D,B,O,由上图可知新的可行域的最优解为B点，为x1=250,x1+x2=310的解：x1=60,x2=250.Z=28000,比原来27500增加了28000-27500=500元。每增加1台时获利500/10=50元。像这样在约束条件右边常量增加一个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格。即台时数约束条件的对偶价格为50元。,你知道对偶价格吗？,对偶价格的概念,.,37,从图27可以看到由于原料A增加了10千克，使例1中的原料A的约束条件变为2X1+X2410,也使得可行域扩大了，但是并不影响它的最优解和最优值，它的最优解仍是B点，它的最优值仍然是27500，没有任何的改进.(27500-27500)10=0这样得到原料A的对偶价格为零。同理可知原料B对偶价格为不为零（为50）。,图27,100,400,100,300,x1,x2,C,A,D,B,O,下面来看例1中的原料A如果增加10千克，将会对最优解和最优值产生什么影响。,.,38,其实这个问题不需要通过计算就很容易理解。由于当产品I生产50单位，产品生产250单位时，原料A还有50千克没有使用(即松弛变量s2=50)，如果再增加10千克原料，也只不过增加库存而已，是不会再增加利润的，故原料A的对偶价格为零。所以当某约束条件中的松弛变量(或剩余变量)不为零时，则这个约束条件的对偶价格为零。反之当某约束条件中的松弛变量(或剩余变量)为零