《管理运筹学-第2章-线性规划的图解法.ppt》由会员分享，可在线阅读，更多相关《管理运筹学-第2章-线性规划的图解法.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章 线性规划的图解法一、线性规划问题及其数学模型 在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。例1.1某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产方案。资源产品资源单耗甲乙资源限量煤电油9445310360200300单位产品价格712解：设安排甲、乙产量分别为,总收入为，则模型为：目标函数：总收入，记为z,则 ，为体现 对其追求极大化，在z 的前面冠以极大号Max；决策变量：甲、乙产品的计划产量，记为 ；约束条件：分别来自资源煤、电、油限量的约束，和产 量非负的约束，表示为线性线性规划模型的三要素
2、3.约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示。1.决策变量：需决策的量，即待求的未知数；2.目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；线性规划模型的一般形式：（以MAX型、约束为例）决策变量：目标函数：约束条件：则模型可表示为模型一般式的矩阵形式记回顾例1.1的模型其中表示决策变量的向量；表示产品的价格向量；表示资源限制向量；表示产品对资源的单耗系数矩阵。一般地其中 称为决策变量向量，称为价格系数向量,称为技术系数矩阵,称为资源限制向量。问题：为什么 A 称为技术系数矩阵？二、线性规划模型的图解法n图解法是用画图的方式求解线性规划的一种方法。它虽然只
3、能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。2023/3/9例例1 用图解法求解线性规划问题用图解法求解线性规划问题maxZ=50X1+100X2X1+X23002X1+X2400s.t.X2250X1，X202023/3/9（1）分别取决策变量 X1，X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=02023/3/91313（2）对每个不等式（约束条件），先取其等式在坐标系中作直线，然后确定不等式所决定的半平面
4、。X1+X2300X1+X2=3001001002002X1+X24002X1+X2=400300200300400100200300 x1x1100200300 x2x22023/3/914（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100X2250X2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图图2-1x1x22023/3/915（4）目标函数Z=50X1+100X2，当Z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z
5、在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE由图可知：顶点B为最优解。X1=50,X2=250Z=50 x50+250 x100=27500（1）做约束的图形先做非负约束的图形；再做资源约束的图形。以例1.1为例，其约束为 各约束的公共部分即模型的约束，称可行域。1.图解法的步骤(2)做目标的图形做出相应的二直线，便可看出增大的方向。对于目标函数便可做出相应的二组任给Z
6、 不同的值，形成二直线，用虚线表示。以例1.1为例，其目标为分别令（3）求出最优解 将目标直线向使目标 优化的方向移，直至可行域的边界为止，这时其与可行域的“切”点 即最优解。如在例1.1中，是可行域的一个角点，经求解交出 的二约束直线联立的方程可解得 由图解法的结果得到例1.1的最优解 还可将其代入目标函数求得相应的最优目标值 。说明当甲产量安排20个单位，乙产量安排24个单位时，可获得最大的收入428。2.由图解法得到线性规划解的一些特性（1）线性规划的约束集（即可行域）是一个凸多线性规划的约束集（即可行域）是一个凸多面体。面体。凸多面体凸多面体:把多面体的任何一个面伸展成把多面体的任何一
7、个面伸展成平面，如果所有其他各面都在这个平面的同侧，平面，如果所有其他各面都在这个平面的同侧，这样的多面体就叫做凸多面体。这样的多面体就叫做凸多面体。凸多面体的任何截面都是凸多面体的任何截面都是凸多边形。凸多边形。（2）线性规划的最优解（若存在的话）必能在线性规划的最优解（若存在的话）必能在可行域的角点（顶点）获得。可行域的角点（顶点）获得。因为，由图解法可知，只有当目标直线平移到边界时，才能使目标 z 达到最大限度的优化。问题：本性质有何重要意义？本性质重要意义：本性质重要意义：这样，问题就转化为这样，问题就转化为从有限从有限多个角点中寻找最优点多个角点中寻找最优点，使，使原来从所有可行解中
8、去原来从所有可行解中去寻找寻找最优解的工作大大简化最优解的工作大大简化。线。线性规划的性规划的单纯形解法单纯形解法的依据的依据就是这两个性质。就是这两个性质。（3）线性规划解的几种情形 唯一最优解 多重最优解 无解 无有限最优解（无界解）重要结论：重要结论：n如果线性规划有最优解，则一定有一个可如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；行域的顶点对应一个最优解；n无穷多个最优解。无穷多个最优解。n无界解。即可行域的范围延伸到无穷远，无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的
9、说，这说明模型有错，忽略了一些必要的约束条件；约束条件；n无可行解。则可行域为空域，不存在满足无可行解。则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。约束条件的解，当然也就不存在最优解了。小结小结线性规划线性规划LP(linear programming)的定义：的定义：LP是在是在有限资源有限资源的条件下，的条件下，合理分配合理分配和和利用资源，以期取得利用资源，以期取得最佳最佳的经济效益的的经济效益的优化方法。优化方法。LP有一组有一组决策变量决策变量，一个一个目目标函数标函数，一组一组约束条件约束条件，目标函数和约束方程都是线性的。目标函数和约束方程都是线性的。重要性：
10、重要性：要想在工农业生产、交通运输、商业贸易等各方面提高效益，有两种途径：一是革新技术，二是改进生产组织与计划，即合理安排有限的人力和物力资源，最合理地组织生产过程。数学规划能够为更好地配置资源、组织生产数学规划能够为更好地配置资源、组织生产提供理论与方法提供理论与方法，包括线性规划、非线性规划、整数规划、多目标规划等很多分支。其中线性规划是在现代管理中运用最广、其中线性规划是在现代管理中运用最广、理论比较完善的一个部分。随着电子计算机的理论比较完善的一个部分。随着电子计算机的发展，数学规划在现代管理中的重要性日益明发展，数学规划在现代管理中的重要性日益明显。显。线性规划的标准化内容之一：线性
11、规划的标准化内容之一：引入松驰变量（含义是资源松驰变量（含义是资源的剩余量）的剩余量）例1.1 中引入 s1，s2，s3 模型化为目标函数：Maxz=7x1+12x2+0s1+0s2+0s3约束条件：9x1+4x2+s1=3604x1+5x2+s2=200s.t.3x1+10 x2+s3=300 x1,x2,s1,s2,s30 对于最优解 x1=20 x2=24，s1=84s2=0s3=0说明：生产20单位甲产品和24单位乙产品将消耗完所有可能的电和油，但对煤则还剩余84个单位。线性规划的标准化线性规划的标准化n一般形式一般形式目标函数：Max（Min）z=c1x1+c2x2+cnxn约束条件
12、：a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2s.t.am1x1+am2x2+amnxn（=,）bm x1，x2，xn0n标准形式标准形式目标函数：Maxz=c1x1+c2x2+cnxn约束条件：a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2s.t.am1x1+am2x2+amnxn=bm x1，x2，xn0，bi0 可可以以看看出出，线线性性规规划划的的标标准准形形式式有有如如下下四四个个特特点：点：n目标最大化；目标最大化；n约束为等式；约束为等式；n决策变量均非负；决策变量均非负；n右端项非负。右端项非负。
13、对对于于各各种种非非标标准准形形式式的的线线性性规规划划问问题题，我我们们总可以通过以下变换，将其转化为标准形式总可以通过以下变换，将其转化为标准形式:1.极小化目标函数的问题：设目标函数为 Min f=c1x1+c2x2+cnxn (可以)令 z -f，则该极小化问题与下面的极大化问题有相同的最优解，即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即 Min f -Max z2.约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量s，使它等于约束右边与左边之
14、差 s=bi(ai1 x1+ai2 x2+ain xn)显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi 当约束条件为 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 为了使约束由不等式成为等式而引进的变量s，当不等式为不等式为“小于等于小于等于”时称为“松弛变量松弛变量”；当不等式为不等式为“大于等于大于等于”时称为“剩余变量剩余变量”。如果原问题中有若干个非
15、等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。3.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi0，则把该等式约束两端同时乘以-1，得到：例：将以下线性规划问题转化为标准形式Minf=2x1-3x2+4x33x1+4x2-5x362x1+x38s.t.x1+x2+x3=-9x1,x2,x3 0解：首先,将目标函数转换成极大化：令 z=-f=-2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进松弛变量与剩余变量 x4，x5 0。第三个约束条件的右端值为负，在等式两边同时乘-1。通过以上变换，可以得到以下标准形式的线
16、性规划问题：Max z=-2x1+3 x2-4x3 3x1+4x2-5x3+x4 =6 s.t.2x1 +x3 -x5 =8 -x1 -x2 -x3 =9 x1,x2,x3,x4,x5 0*4.变量无符号限制的问题*：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj=xj-xj”其中 xj 0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj 和xj”的大小。36三、图解法的灵敏度分析 灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj变化时，对最优解产生的影响。3.1
17、 目标函数中的系数目标函数中的系数 ci 的灵敏度分析的灵敏度分析考虑例1的情况，ci的变化只影响目标函数等值线的斜率，目标函数z=50 x1+100 x2在z=x2(x2=z斜率为0)到z=x1+x2(x2=-x1+z斜率为-1)之间时，原最优解x1=50，x2=100仍是最优解。n一般情况：z=c1x1+c2x2写成斜截式x2=-(c1/c2)x1+z/c2目标函数等值线的斜率为-(c1/c2)，当-1-(c1/c2)0（*）时，原最优解仍是最优解。37n假设产品的利润100元不变，即c2=100，代到式（*）并整理得0c1100n假设产品的利润50元不变，即c1=50，代到式（*）并整理
18、得50c2+n假若产品、的利润均改变，则可直接用式（*）来判断。n假设产品、的利润分别为60元、55元，则-2-(60/55)-1那么，最优解为z=x1+x2和z=2x1+x2的交点x1=100，x2=200。383.2约束条件中右边系数bj的灵敏度分析当约束条件中右边系数bj变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例1的情况：假设设备台时增加10个台时，即b1变化为310，这时可行域扩大，最优解为x2=250和x1+x2=310的交点x1=60，x2=250。变化后的总利润-变化前的总利润=增加的利润(5060+100250)-(5050+100250)=500500/1
19、0=50元。说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。39假设原料A增加10千克时，即b2变化为410，这时可行域扩大，但最优解仍为x2=250和x1+x2=300的交点x1=50，x2=250。此变化对总利润无影响，该约束条件的对偶价格为0。解释：原最优解没有把原料A用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于0，则最优目标函数值不变。作业：作业：教材教材P23：1；2;3；4；5