线性规划的标准化及图解法-课件

1线性规划的应用在人力，物力资源有限的条件下，如何安排生产，达到最大收益？如何用最少的人力，物力资源，完成给定的任务。许多管理上的问题可以用线性规划来求解。2020/12/171ppt课件2线性规划的问题某工厂生产两种型号的电机（记为A和B），每台A型电机需用原料2个单位，4个工时，每台B型电机需用原料3个单位，2个工时，工厂共有原料100个单位，120个工时，A、B型电机的每台利润分别为600元和400元，问两种电机各生产多少可使利润最大？设A、B型电机各生产x1,x2台，x1,x2称为决策变量。利润函数600 x1+400 x2目标函数2x1+3x2 1004x1+2x2 120约束条件2020/12/172ppt课件精品资料你怎么称呼老师？如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？你所经历的课堂，是讲座式还是讨论式？教师的教鞭“不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘”“太阳当空照，花儿对我笑，小鸟说早早早”5线性规划的数学问题上述问题可写成如下的数学形式：它是求目标函数的最大值，决策变量满足一定的条件（约束条件）。2020/12/175ppt课件6线性规划的模型特点这是一个典型的利润最大化的生产计划问题。“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2 的取值。2020/12/176ppt课件7设有两个砖厂A1，A2。产量分别为23万和27万，供应三个工地B1，B2，B3。其需要量分别为17万，18万和15万。砖厂到各工地的每万块砖的运价如下表：线性规划的应用模型B1B2B3A1506070A260110160如何调运，才可使总运费最小？2020/12/177ppt课件8于是得到如下的线性规划模型：该问题可推广到m个产地，n个销地的运输问题。2020/12/178ppt课件9线性规划的应用模型某饲养场使用甲,乙,丙,丁四种饲料，每种饲料的的维生素A，B，C含量及单位价格和所需的维生素如下表，要求配制一个混合饲料，每单位混合饲料的维生素A、B、C的需要量为3，5，10.甲 乙 丙 丁需要量ABC0.2 0.8 1.2 0.60.8 0.3 0.9 0.71.2 0.9 0.7 1.5 3510单价5 6 6 7问如何配制多少可使成本最小而又能满足需要？2020/12/179ppt课件10线性规划的应用模型设x1,x2,x3,x4是甲乙丙丁四种饲料的用量，则要求维生素A的含量大于3，有0.2x1+0.8x2+1.2x3+0.6x4 3要求维生素B的含量大于5，有 0.8x1+0.3x2+0.9x3+0.7x4 5要求维生素C的含量大于10，有 1.2x1+0.9x2+0.7x3+1.5x4 10目标是成本最小，有 Min 5x1+6x2+6x3+7x42020/12/1710ppt课件11线性规划的应用模型于是可得如下的线性规划的模型：2020/12/1711ppt课件12线性规划的一般形式2020/12/1712ppt课件13线性规划的数学结构它是求一个函数最大值或最小值问题;这个函数称为目标函数;这个目标函数是线性函数;这个目标函数可以认为定义在一个特定的区域上.这个区域是由一组线性不等式所确定.2020/12/1713ppt课件14线性规划的标准形式2020/12/1714ppt课件15 可以看出，线性规划的标准形式有如下四个特点：目目标标最最大大化化、约约束束为为等等式式、决策变量均非负、右端项非负。决策变量均非负、右端项非负。线性规划的标准形式对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:2020/12/1715ppt课件16 1.若目标函数求极小：将线性规划化成标准形式设目标函数为 Min f=c1x1+c2x2+cnxn 则可以令z -f 求极大化问题化成求下面的极小化问题.即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f -Max z2020/12/1716ppt课件17 2、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量(称为松弛变量松弛变量)xn+i，xn+i 0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+xn+i=bi将线性规划化成标准形式2020/12/1717ppt课件18 当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地引入变量xn+i(称为剩余变量剩余变量)xn+i0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-xn+i=bi 将线性规划化成标准形式2020/12/1718ppt课件19 例2.：将以下线性规划问题转化为标准形式将线性规划化成标准形式 解：第一个约束引入松弛变量x4,第二个约束引入剩余变量x5 2020/12/1719ppt课件20于是，我们可以得到以下标准形式的线性规划问题：将线性规划化成标准形式2020/12/1720ppt课件21 3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj=xj-xj”其中 xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。将线性规划化成标准形式2020/12/1721ppt课件22 4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项为负时，如 bi0，则把该约束两端同时乘以-1，得到：-ai1 x1-ai2 x2-ain xn=-bi 。将线性规划化成标准形式2020/12/1722ppt课件23例2.3：将以下线性规划问题转化为标准形式 将线性规划化成标准形式第一个约束加松弛变量x5,第二约束加剩余变量x6,第三个约束两端乘-1，再加剩余变量x7.2020/12/1723ppt课件24解：首先，目标函数是极小化,将它化成求最大。其次考虑3个不等式约束：将线性规划化成标准形式第一个约束加松弛变量x5,2x1-3x2+5x3+6x4+x5=28第二约束加剩余变量x6,4x1+2x2+3x3-9x4x6=39第三个约束两端乘-1，再加剩余变量x7 -6x2-2x3-3x4-x7=582020/12/1724ppt课件25由于x2无非负限制，可令x2=x2-x2”,其中x20，x2”0；于是，我们可以得到以下标准形式的线性规划问题：2020/12/1725ppt课件26线性规划的图解法对两个决策变量的线性规划，可以利用几何的方法来研究；观察线性规划的约束区域；观察线性规划的目标函数；观察线性规划的最优解；2020/12/1726ppt课件27 线性规划的图解法 对于两个决策变量的线性规划可用作图方法来求解。图解法求解线性规划问题的步骤如下：分别取决策变量x1,x2 为坐标向量建立直角坐标系。画出线性规划的约束区域；画出目标函数等值线；平行移动目标函数等值线，找到最优解。2020/12/1727ppt课件28 线性规划的图解法 例1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）15001500250025002020/12/1728ppt课件29 线性规划的图解法 问题：工厂应如何安排生产可获得最大的总利润？用图解法求解。解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据前面分析，可以建立如下的线性规划模型：Max z=1500 x1+2500 x2 s.t.3x1+2x2 65 (A)2x1+x2 40 (B)3x2 75 (C)x1,x2 0 (D,E)2020/12/1729ppt课件30线性规划的图解法以决策变量x1，x2 为坐标轴建立平面直角坐标系。考虑约束条件3x1+2x2 65 3x1+2x2=65 是一个直线方程 画出这条直线。约束3x1+2x2 65是半个平面同理约束条件2x1+x2 40 也是半个平面。2020/12/1730ppt课件31线性规划的图解法整个约束区域是由直线3x1+2x2=65；2x1+x2=40；3x2 =75；x1=0；x2=0所围所围 约束区域在约束区域在约束区域中寻找一点中寻找一点使目标函数使目标函数最大。最大。2020/12/1731ppt课件32线性规划的图解法作出目标函数的等值线：1500 x1+2500 x2=30000将目标函数等值线沿增大方向平行移动。最优解是最优解是3 3x x1 1+2+2x x2 2 =65=65和和3 3x x2 2 =75=75 两直线的交点。两直线的交点。2020/12/1732ppt课件33线性规划的图解法 图解法求解线性规划2020/12/1733ppt课件34线性规划的图解法任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置，得到交点(5,25)T，此目标函数的值为70000。于是，我们得到这个线性规划的最优解x1=5、x2=25，最优值z=70000。即最优方案为生产甲产品5件、乙产品25件，可获得最大利润为70000元。2020/12/1734ppt课件35作图法求解如下线性规划2020/12/1735ppt课件36最优解点坐标:(1,5)2020/12/1736ppt课件37目标函数等值线2x1+3x2与约束条件4x1+6x2=9平行。2020/12/1737ppt课件38令x1,则S目标函数在可行域内无界!目标函数等值线沿右下方向将减小!2020/12/1738ppt课件39约束条件矛盾，线性规划无解!x1+2x2=22x1-x2=32020/12/1739ppt课件40 根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况 1.可行域为封闭的有界区域 (a)有唯一的最优解；(b)有无穷多个最优解；2.可行域为不封闭的无界区域 (c)有唯一的最优解；线性规划的图解法线性规划的图解法2020/12/1740ppt课件41 (d)有无穷多个最优解；(e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。3.可行域为空集 (f)没有可行解，原问题无最优解 线性规划的图解法线性规划的图解法2020/12/1741ppt课件42线性规划的图解法有以下结论：线性规划的图解提示线性规划的约束区域是由若干条直线所围的多边形；若线性规划有解则最优解在约束区域的边界上达到；更进一步，线性规划的最优解可在约束区域的顶点上达到。2020/12/1742ppt课件43 线性规划的图解提示若线性规划的决策变量有三个线性规划的约束区域是一个多面体；线性规划有解则最优解可在约束区域的顶点上达到求解线性规划就是寻找约束区域的顶点若线性规划的决策变量有n个线性规划的约束区域是一个多胞形；2020/12/1743ppt课件