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

管管 理理 运运 筹筹 学学1第第2 2章章线性规划的图解法线性规划的图解法2线性规划的图解法线性规划的图解法1线性规划问题的数学模型线性规划问题的数学模型3 3图解法的灵敏度分析图解法的灵敏度分析管管 理理 运运 筹筹 学学1线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）管管 理理 运运 筹筹 学学线性规划问题的数学模型例1.1如图所示，如何截取x使铁皮所围成的容积最大？xa管管 理理 运运 筹筹 学学线性规划问题的数学模型例1.2某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？设设 备备产产 品品 A A B B C C D D利润（元）利润（元）甲甲 2 2 1 1 4 4 0 0 2 2 乙乙 2 2 2 2 0 0 4 4 3 3 有有 效效 台台 时时 12 12 8 8 16 16 12 12管管 理理 运运 筹筹 学学线性规划问题的数学模型解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：maxZ=2xmaxZ=2x1 1+3x+3x2 2 xx1 10,x0,x2 200s.t.s.t.2x2x1 1+2x+2x2 21212xx1 1+2x+2x2 2884x4x1 116164x4x2 21212管管 理理 运运 筹筹 学学线性规划问题的数学模型2.2.线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量DecisionvariablesDecisionvariables，记为，记为x1,x2.x3.Xnx1,x2.x3.Xn 目标函数目标函数Objectivefunction(Objectivefunction(都有一个关于决策变量的线性函数为目标函数，要都有一个关于决策变量的线性函数为目标函数，要求这个目标函数在满足约束条件下实现最大或最小化求这个目标函数在满足约束条件下实现最大或最小化)约束条件约束条件ConstraintsConstraints（其中前（其中前MM个称为前约束条件，后个称为前约束条件，后N N个称为后约束条件）个称为后约束条件）其特征是：其特征是：（1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性函数，通常是求最函数，通常是求最大值或最小值；大值或最小值；（2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性不等式或等式。不等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？管管 理理 运运 筹筹 学学线性规划问题的数学模型目标函数：目标函数：约束条件：约束条件：3.3.线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：管管 理理 运运 筹筹 学学线性规划问题的数学模型向量形式：向量形式：其中：管管 理理 运运 筹筹 学学线性规划问题的数学模型矩阵形式：矩阵形式：其中：管管 理理 运运 筹筹 学学线性规划问题的数学模型3.线性规划问题的标准形式特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。管管 理理 运运 筹筹 学学线性规划问题的数学模型（2 2）如何化标准形式）如何化标准形式 目标函数的转换 如果是求极小值即 ，则可将目标函数乘以(-1)，可化为求极大值问题。也就是：令 ，可得到上式。即 若存在取值无约束的变量 ，可令 其中：变量的变换管管 理理 运运 筹筹 学学线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量 变量 的变换 可令 ，显然管管 理理 运运 筹筹 学学线性规划问题的数学模型例1.3将下列线性规划问题化为标准形式用 替换 ，且 解:（）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以管管 理理 运运 筹筹 学学线性规划问题的数学模型(2)第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3)第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z=-z,得到maxz=-z，即当z达到最小值时z达到最大值，反之亦然;管管 理理 运运 筹筹 学学线性规划问题的数学模型标准形式如下：管管 理理 运运 筹筹 学学线性规划问题的数学模型4.线性规划问题的解线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。管管 理理 运运 筹筹 学学线性规划问题的数学模型 可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。基：设A为约束条件的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（B0），称B是规划问题的一个基。设：称B中每个列向量Pj(j=1 2 m)为基向量。与基向量Pj 对应的变量xj为基变量。除基变量以外的变量为非基变量。管管 理理 运运 筹筹 学学线性规划问题的数学模型基解：某一确定的基B，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过基可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解管管 理理 运运 筹筹 学学线性规划问题的数学模型例1.4求线性规划问题的所有基矩阵。解:约束方程的系数矩阵为25矩阵r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即管管 理理 运运 筹筹 学学202线性规划的图解法线性规划的图解法在管理中一些典型的线性规划应用在管理中一些典型的线性规划应用合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小线性规划的组成：线性规划的组成：目标函数 Max F 或 Min F约束条件 s.t.(subject to)满足于决策变量 用符号来表示可控制的因素所要决策的问题待 定的量值。管管 理理 运运 筹筹 学学212.12.1问题的提出问题的提出例例1.某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？线性规划模型：线性规划模型：目标函数：Maxz=50 x1+100 x2约束条件：s.t.x1+x23002x1+x2400 x2250 x1,x20管管 理理 运运 筹筹 学学222.12.1问题的提出问题的提出建模过程以及线性规划的三要素建模过程以及线性规划的三要素1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件一般形式一般形式目标函数：Max（Min）z=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bm x1，x2，xn0管管 理理 运运 筹筹 学学23例例1.目标函数：Maxz=50 x1+100 x2约束条件：s.t.x1+x2300(A)2x1+x2400(B)x2250(C)x10(D)x20(E)得到最优解：x1=50，x2=250最优目标值z=275002.2图图 解解 法法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：管管 理理 运运 筹筹 学学242.2图图 解解 法法 (1)分别取决策变量X1,X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=0管管 理理 运运 筹筹 学学252.2图图 解解 法法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400管管 理理 运运 筹筹 学学262.2图图 解解 法法（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1管管 理理 运运 筹筹 学学272.2图图 解解 法法（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE管管 理理 运运 筹筹 学学282.2图图 解解 法法线性规划的标准化内容之一：线性规划的标准化内容之一：引入松驰变量（含义是资源的剩余量）例1 中引入 s1，s2，s3 模型化为目标函数：Maxz=50 x1+100 x2+0s1+0s2+0s3约束条件：s.t.x1+x2+s1=3002x1+x2+s2=400 x2+s3=250 x1,x2,s1,s2,s30 对于最优解 x1=50 x2=250，s1=0s2=50s3=0说明：生产50单位产品和250单位产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。管管 理理 运运 筹筹 学学292.2图图 解解 法法重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例1中的目标函数变为maxz=50 x1+50 x2，则线段BC上的所有点都代表了最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。管管 理理 运运 筹筹 学学30进进 一一 步步 讨讨 论论 例例2 2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？管管 理理 运运 筹筹 学学31进进 一一 步步 讨讨 论论解：目标函数：Minf=2x1+3x2约束条件：s.t.x1+x2350 x11252x1+x2600 x1,x20采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300 400 500 600100200300400600500 x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200 x1x2Q管管 理理 运运 筹筹 学学323图解法的灵敏度分析图解法的灵敏度分析线性规划的标准化线性规划的标准化一般形式一般形式目标函数：Max（Min）z=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bm x1，x2，xn0标准形式标准形式目标函数：Maxz=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bm x1，x2，xn0，bi0管管 理理 运运 筹筹 学学333图解法的灵敏度分析图解法的灵敏度分析 可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:管管 理理 运运 筹筹 学学343图解法的灵敏度分析图解法的灵敏度分析1.极小化目标函数的问题：设目标函数为 Min f=c1x1+c2x2+cnxn (可以)令 z -f，则该极小化问题与下面的极大化问题有相同的最优解，即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即 Min f -Max z管管 理理 运运 筹筹 学学353图解法的灵敏度分析图解法的灵敏度分析2、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量s，使它等于约束右边与左边之差 s=bi(ai1 x1+ai2 x2+ain xn)显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi管管 理理 运运 筹筹 学学363图解法的灵敏度分析图解法的灵敏度分析 当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-s=bi管管 理理 运运 筹筹 学学373图解法的灵敏度分析图解法的灵敏度分析 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。3.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2-ain xn=-bi。管管 理理 运运 筹筹 学学383图解法的灵敏度分析图解法的灵敏度分析例：将以下线性规划问题转化为标准形式Minf=2x1-3x2+4x3s.t.3x1+4x2-5x362x1+x38x1+x2+x3=-9x1,x2,x3 0解：首先,将目标函数转换成极大化：令 z=-f=-2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。第三个约束条件的右端值为负，在等式两边同时乘-1。管管 理理 运运 筹筹 学学393图解法的灵敏度分析图解法的灵敏度分析通过以上变换，可以得到以下标准形式的线性规划问题：Max z=-2x1+3 x2-4x3 s.t.3x1+4x2-5x3+x4 =6 2x1 +x3 -x5=8 -x1 -x2 -x3 =9 x1,x2,x3,x4,x5 0*变量无符号限制的问题*：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj=xj-xj”其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。管管 理理 运运 筹筹 学学403图解法的灵敏度分析图解法的灵敏度分析 灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）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=c1x1+c2x2写成斜截式x2=-(c1/c2)x1+z/c2目标函数等值线的斜率为-(c1/c2)，当-1-(c1/c2)0（*）时，原最优解仍是最优解。管管 理理 运运 筹筹 学学413图解法的灵敏度分析图解法的灵敏度分析假设产品的利润100元不变，即c2=100，代到式（*）并整理得0c1100假设产品的利润50元不变，即c1=50，代到式（*）并整理得50c2+假若产品、的利润均改变，则可直接用式（*）来判断。假设产品、的利润分别为60元、55元，则-2-(60/55)-1那么，最优解为z=x1+x2和z=2x1+x2的交点x1=100，x2=200。管管 理理 运运 筹筹 学学423图解法的灵敏度分析图解法的灵敏度分析3.2约束条件中右边系数bj的灵敏度分析当约束条件中右边系数bj变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例1的情况：假设设备台时增加10个台时，即b1变化为310，这时可行域扩大，最优解为x2=250和x1+x2=310的交点x1=60，x2=250。变化后的总利润-变化前的总利润=增加的利润(5060+100250)-(5050+100250)=500，500/10=50元说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。管管 理理 运运 筹筹 学学433图解法的灵敏度分析图解法的灵敏度分析假设原料A增加10千克时，即b2变化为410，这时可行域扩大，但最优解仍为x2=250和x1+x2=300的交点x1=50，x2=250。此变化对总利润无影响，该约束条件的对偶价格为0。解释：原最优解没有把原料A用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于0，则最优目标函数值不变。