《运筹学——第2章线性规划的图解法》由会员分享，可在线阅读，更多相关《运筹学——第2章线性规划的图解法（44页珍藏版）》请在金锄头文库上搜索。
1、1,线性规划是运筹学的一个重要分支。它是现代科学管理的重要手段之一，是帮助管理者作出最优决策的一个有效的方法。下面看看一些在管理上经常应用的典型线性规划问题： 1合理利用线材问题。现有一批长度一定的钢管，由于生产的需要，要求截出不同规格的钢管若干。试问应如何下料，既满足了生产的需要，又使得使用的原材料钢管的数量最少。 2配料问题。用若干种不同价格不同成分含量的原料，用不同的配比混合调配出一些不同价格不同规格的产品，在原料供应量的限制和保证产品成分的含量的前提下，如何获取最大的利润。,2,3投资问题。从许多不同的投资项目中选出一个投资方案，使得投资的回报为最大。 4产品生产计划。合理充分地利用厂
2、里现有的人力、物力、财力，作出最优的产品生产计划，使得工厂获利最大。 5劳动力安排。某单位由于工作需要，在不同时间段需要不同数量的劳动力，在每个劳动力工作日连续工作八小时的规则下，如何安排劳动力，才能用最少的劳动力来满足工作的需要。,3,6运输问题。一个公司有若干个生产单位与销售单位，根据各生产单位的产量及销售单位的销量，如何制定调运方案，将产品运到各销售单位而总的运费最小。 以上的这些问题，线性规划都能成功地加以解决。这些例子都有一个共同的特点: 首先，每个例子中都要求达到某些数量上的最大化或最小化的目标。 其次，所有线性规划问题都是在一定的约束条件下来追求其目标的。,4,例1某工厂在计划期
3、内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A，B两种原材料的消耗，以及资源的限制，如下表所示。,该工厂每生产一单位产品I可获利50元，每生产一单位产品可获利100 元，问工厂应分别生产多少个产品和产品才能使工厂获利最多?,5,6,这个问题可以用以下的数学模型来加以描述。工厂目前要决策的问题是生产多少个产品和生产多少个产品，把这个要决策的问题用变量x1、x2来表示，则称x1和x2为决策变量，即决策变量x1=生产I产品的数量，决策变量x2=生产产品的数量。 用x1和x2的线性函数形式来表示工厂所要求的最大利润的目标： max Z=50 x1+100x2 （称为目标函数）。 其中ma
4、x为最大化的符号(最小化为min)；50和100分别为单位产品 、 的利润。同样也可以用x1和x2的线性不等式来表示问题的约束条件。对于台时数的限制可以表示为： X1+X2300 同样，两种原材料的限量可分别表示为： 2X1+X2400, X2250. 除了上述约束外，显然还应该有x10，x20，因为产品, 产品的 产量是不能取负值的。综上所述，就得到了例1的数学模型如下：,7,目标函数： max Z=50x1+100x2， 满足约束条件：x1+x2300， 2 x1+x2400， x2250, x10, x20. 由于上述数学模型的目标函数为变量的线性函数，约束条件也为变量的线性等式或不等式
5、，故此模型称之为线性规划。如果目标函数是变量的非线性函数，或约束条件中含有变量非线性的等式或不等式的数学模型则称之为非线性规划。 把满足所有约束条件的解称为该线性规划的可行解。把使得目标函数值最大(即利润最大)的可行解称为该线性规划的最优解，此目标函数值称为最优目标函数值，简称最优值。,8,1要正确理解所要解决的问题，要搞清在什么条件下，追求什么样的目标。 2定义决策变量，每一个问题都用一组决策变量(X1，X2, , Xn)表示任何一个方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的。 3用决策变量的线性函数形式写出所要追求的目标，称之为目标函数，按问题的不同，要求目标函数实
6、现最大化或最小化。 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,对于只包含两个决策变量的线性规划问题，可以用图解法来求解。大于两个决策变量不能用图解法来解了。 图解法.首
7、先把每个约束条件（代表一个平面）画在二维坐标轴上。,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=50x1+100x2,阴影部分的每一点(包括边界线)都是这个线性规划的可行解，而此公共部分是例1的可行解的集合，称为可行域。,B点为最优解，坐标为（50，250）,Z=0=50x1+100x2,13,问题的解：,最佳决策为x1=50, x2=250，此时z=27500。 这说明该厂的最优生产计划方案是生产I产品50单位，生产产品250单位，可得最大利
8、润27500元。 把x1=50, x2=250代入约束条件得： 50+250=300台时设备 250+250=350千克原料A， 1250=250千克原料B 这表明了生产50单位产品和250单位产品将消耗完所有可使用的设备台时数和原料B，但对原料A来说只消耗了350千克，还有(400350)=50千克没有使用。在线性规划中，对一个约束条件中没使用的资源或能力的大小称之为松弛量。,14,松弛变量和线性规划标准化,为了把一个线性规划标准化，需要有代表没使用的资源或能力的变量，称之为松弛变量，记为Si。显然这些松弛变量对目标函数不会产生影响，可以在目标函数中把这些松弛变量的系数看成零，加了松弛变量后
9、我们得到如下的例1的数学模型： 目标函数： max Z=50x1+100x2+0s1+0s2+0s3， 约束条件： x1+x2+s1=300, 2x1+x2+s2=400, x2+s3=250, x1,x2,s1,s2,s30,15,像这样把所有的约束条件都写成等式，称为线性规划模型的标准化，所得结果称为线性规划的标准形式。在标准型中 bj(右边常量)都要大于等于零， 对某个bj小于零时，只要方程两边都乘以(-1)即可。 实际上以后可看到应同时具备如下三个条件的模型才是标准型： 一是约束条件必须化为等式；二是所有变量必须化为大于或者等于零；三是约束条件中的右端常数项必须是大于或者等于零。 对例
10、1 的最优解 x1=50,x2=250来说，松弛变量的值如下所示： 约束条件 松弛变量的值 设备台时数 s1=0 原料A s2=50 原料B s3=0,16,习题1： 目标函数： max Z=6x1+2x2， 满足约束条件：2x1+3x29， 4x1+7x24， x10, x20. 1、用图解法求解 2、写出线性规划问题的标准形式 3、求出此线性规划问题的两个松弛变量的值,17,线性规划问题解的有如下特点：,1如果某一个线性规划问题有最优解，则一定有一个可行域的顶点对应一个最优解。 2线性规划存在有无穷多个最优解的情况。若将例1中的目标函数变为求max Z =50x1+50x2，则可见代表目标
11、函数的直线平移到最优位置后将和直线x1+x2=300重合。详见下图。 此时不仅顶点B，C都代表了最优解，而且线段BC上的所有点都代表了最优解，这样最优解就有无穷多个了。当然这些最优解都对应着相同的最优值（只有一个）： 50x1+50x2=5050+50250=15000。,18,100,400,100,300,x1,x2,Z=15000=50x1+50x2,Z=0=50x1+50x2,19,线性规划存在无界解，即无最优解的情况。对下述线性规划问题： 目标函数： max z =x1+x2 约束条件： x1-x21 - 3x1+2x26 x10，x20,3,20,从图中可知该问题可行域无界，目标函
12、数值可以增大到无穷大，成为无界解即无最优解。出现这种情况，一般说明线性规划模型有错误，该模型中忽略了一些实际存在的必要的约束条件。,注意啊,21,4线性规划存在无可行解的情况。若在例1的数学模型中再增加一个约束条件4x1+3x21200，显然可见新的线性规划的可行域为空域，也即不存在满足所有约束条件的x1和x2的解，当然更不存在最优解了。出现这种情况是由于约束条件自相矛盾导致的建模错误。,100,400,100,300,x1,x2,22,目标函数最小化的线性规划问题,某公司由于生产需要，共需要A，B两种原料至少350吨(A，B两种材料有一定替代性)，其中A原料至少购进125吨。但由于A，B两种
13、原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低? 解：设x1为购进原料A的吨数，x2为购进原料B的吨数。得到了此线性规划的数学模型如下： 目标函数： min f=2x1+3x2， 约束条件： x1+x2350， x1125，2x1+x2600, x1,x20.,例2,23,用图解法来解：,Q,Q点坐标为x1=250, x2=100,24,Q点坐标为x1=250,x
14、2=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点的坐标下面两方程的交点：,25,同样对于约束条件中，可以增加一些代表最低限约束的超过量，称之为剩余变量，把约束条件
15、变为等式约束条件，加了松弛变量与剩余变量后例2的数学模型变为标准型（注意松弛变量符号为正，而剩余变量符号为负）： 目标函数： min f =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,26,习题2： 目标函数： max Z=2x1+3x2， 满足约束条件：-3x1+x21， 4x1+2x220， 4x1-x2 10， -x1+2x25， x10, x20. 1、用图解法求解 2、写出线性规划问题的标准形式 3、求出此线性规划问题的四个松弛变量的值,27,由上节可知，线性规划的标准形式可写为 目标函数：max Z=c1x1+c2x2+cnxn 或： min f=c1x1+c2x2+cnxn 约束条件：a11x1+a12x2+
