线性规划的标准化及图解法幻灯片.ppt

《线性规划的标准化及图解法幻灯片.ppt》由会员分享，可在线阅读，更多相关《线性规划的标准化及图解法幻灯片.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划的标准化及图解法第1页，共42页，编辑于2022年，星期一2线性规划的应用在人力，物力资源有限的条件下，如何安排生产，达到最大收益？如何用最少的人力，物力资源，完成给定的任务。许多管理上的问题可以用线性规划来求解。第2页，共42页，编辑于2022年，星期一3线性规划的问题某工厂生产两种型号的电机（记为A和B），每台A型电机需用原料2个单位，4个工时，每台B型电机需用原料3个单位，2个工时，工厂共有原料100个单位，120个工时，A、B型电机的每台利润分别为600元和400元，问两种电机各生产多少可使利润最大？设A、B型电机各生产x1,x2台，x1,x2称为决策变量。利润函数600 x1

2、+400 x2目标函数2x1+3x2 1004x1+2x2 120约束条件第3页，共42页，编辑于2022年，星期一4线性规划的数学问题上述问题可写成如下的数学形式：它是求目标函数的最大值，决策变量满足一定的条件（约束条件）。第4页，共42页，编辑于2022年，星期一5线性规划的模型特点这是一个典型的利润最大化的生产计划问题。“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2 的取值。第5页，共42页，编辑于2022年，星期一6设有两个砖厂A1，A

3、2。产量分别为23万和27万，供应三个工地B1，B2，B3。其需要量分别为17万，18万和15万。砖厂到各工地的每万块砖的运价如下表：线性规划的应用模型B1B2B3A1506070A260110160如何调运，才可使总运费最小？第6页，共42页，编辑于2022年，星期一7于是得到如下的线性规划模型：该问题可推广到m个产地，n个销地的运输问题。第7页，共42页，编辑于2022年，星期一8线性规划的应用模型某饲养场使用甲,乙,丙,丁四种饲料，每种饲料的的维生素A，B，C含量及单位价格和所需的维生素如下表，要求配制一个混合饲料，每单位混合饲料的维生素A、B、C的需要量为3，5，10.甲 乙 丙 丁需

4、要量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问如何配制多少可使成本最小而又能满足需要？第8页，共42页，编辑于2022年，星期一9线性规划的应用模型设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+7x4第9页，共42页

5、，编辑于2022年，星期一10线性规划的应用模型于是可得如下的线性规划的模型：第10页，共42页，编辑于2022年，星期一11线性规划的一般形式第11页，共42页，编辑于2022年，星期一12线性规划的数学结构它是求一个函数最大值或最小值问题;这个函数称为目标函数;这个目标函数是线性函数;这个目标函数可以认为定义在一个特定的区域上.这个区域是由一组线性不等式所确定.第12页，共42页，编辑于2022年，星期一13线性规划的标准形式第13页，共42页，编辑于2022年，星期一14 可以看出，线性规划的标准形式有如下四个特点：目目标标最最大大化化、约约束束为为等等式式、决决策策变量均非负、右端项非

6、负。变量均非负、右端项非负。线性规划的标准形式对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:第14页，共42页，编辑于2022年，星期一15 1.若目标函数求极小：将线性规划化成标准形式设目标函数为 Min f=c1x1+c2x2+cnxn 则可以令z -f 求极大化问题化成求下面的极小化问题.即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f -Max z第15页，共42页，编辑于2022年，星期一16 2、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2

7、x2+ain xn bi 可以引进一个新的变量(称为松弛变量松弛变量)xn+i，xn+i 0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+xn+i=bi将线性规划化成标准形式第16页，共42页，编辑于2022年，星期一17 当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地引入变量xn+i(称为剩余变量剩余变量)xn+i0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-xn+i=bi 将线性规划化成标准形式第17页，共42页，编辑于2022年，星期一18 例2.：将以下线性规划问题转化为标准形式将线性规划化成标准形式 解：第一个约束引

8、入松弛变量x4,第二个约束引入剩余变量x5 第18页，共42页，编辑于2022年，星期一19于是，我们可以得到以下标准形式的线性规划问题：将线性规划化成标准形式第19页，共42页，编辑于2022年，星期一20 3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj=xj-xj”其中 xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。将线性规划化成标准形式第20页，共42页，编辑于2022年，星期一21 4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项

9、为负时，如 bi0，则把该约束两端同时乘以-1，得到：-ai1 x1-ai2 x2-ain xn=-bi 。将线性规划化成标准形式第21页，共42页，编辑于2022年，星期一22例2.3：将以下线性规划问题转化为标准形式 将线性规划化成标准形式第一个约束加松弛变量x5,第二约束加剩余变量x6,第三个约束两端乘-1，再加剩余变量x7.第22页，共42页，编辑于2022年，星期一23解：首先，目标函数是极小化,将它化成求最大。其次考虑3个不等式约束：将线性规划化成标准形式第一个约束加松弛变量x5,2x1-3x2+5x3+6x4+x5=28第二约束加剩余变量x6,4x1+2x2+3x3-9x4x6=

10、39第三个约束两端乘-1，再加剩余变量x7 -6x2-2x3-3x4-x7=58第23页，共42页，编辑于2022年，星期一24由于x2无非负限制，可令x2=x2-x2”,其中x20，x2”0；于是，我们可以得到以下标准形式的线性规划问题：第24页，共42页，编辑于2022年，星期一25线性规划的图解法对两个决策变量的线性规划，可以利用几何的方法来研究；观察线性规划的约束区域；观察线性规划的目标函数；观察线性规划的最优解；第25页，共42页，编辑于2022年，星期一26 线性规划的图解法 对于两个决策变量的线性规划可用作图方法来求解。图解法求解线性规划问题的步骤如下：分别取决策变量x1,x2

11、为坐标向量建立直角坐标系。画出线性规划的约束区域；画出目标函数等值线；平行移动目标函数等值线，找到最优解。第26页，共42页，编辑于2022年，星期一27 线性规划的图解法 例1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500第27页，共42页，编辑于2022年，星期一28 线性规划的图解法 问题：工厂应如何安排生产可获得最大的总利润？用图解

12、法求解。解：设变量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)第28页，共42页，编辑于2022年，星期一29线性规划的图解法以决策变量x1，x2 为坐标轴建立平面直角坐标系。考虑约束条件3x1+2x2 65 3x1+2x2=65 是一个直线方程 画出这条直线。约束3x1+2x2 65是半个平面同理约束条件2x1+x2 40 也是半个平面。第29页，共42页，编辑于2022年，星期一30线性规划的

13、图解法整个约束区域是由直线3x1+2x2=65；2x1+x2=40；3x2 =75；x1=0；x2=0所围所围 约束区域在约束区域在约束区域中寻找一点中寻找一点使目标函数使目标函数最大。最大。第30页，共42页，编辑于2022年，星期一31线性规划的图解法作出目标函数的等值线：1500 x1+2500 x2=30000将目标函数等值线沿增大方向平行移动。最优解是最优解是3 3x x1 1+2+2x x2 2 =65=65和和3 3x x2 2 =75=75 两直线的交点。两直线的交点。第31页，共42页，编辑于2022年，星期一32线性规划的图解法 图解法求解线性规划第32页，共42页，编辑于

14、2022年，星期一33线性规划的图解法任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置，得到交点(5,25)T，此目标函数的值为70000。于是，我们得到这个线性规划的最优解x1=5、x2=25，最优值z=70000。即最优方案为生产甲产品5件、乙产品25件，可获得最大利润为70000元。第33页，共42页，编辑于2022年，星期一34作图法求解如下线性规划第34页，共42页，编辑于2022年，星期一35最优解点坐标:(1,5)第35页，共42页，编辑于2022年，星期一36目标函数等值线2

15、x1+3x2与约束条件4x1+6x2=9平行。第36页，共42页，编辑于2022年，星期一37令x1,则S目标函数在可行域内无界!目标函数等值线沿右下方向将减小!第37页，共42页，编辑于2022年，星期一38约束条件矛盾，线性规划无解!x1+2x2=22x1-x2=3第38页，共42页，编辑于2022年，星期一39 根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况 1.可行域为封闭的有界区域 (a)有唯一的最优解；(b)有无穷多个最优解；2.可行域为不封闭的无界区域 (c)有唯一的最优解；线性规划的图解法线性规划的图解法第39页，共42页，编辑于2022年，星期一

16、40 (d)有无穷多个最优解；(e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。3.可行域为空集 (f)没有可行解，原问题无最优解 线性规划的图解法线性规划的图解法第40页，共42页，编辑于2022年，星期一41线性规划的图解法有以下结论：线性规划的图解提示线性规划的约束区域是由若干条直线所围的多边形；若线性规划有解则最优解在约束区域的边界上达到；更进一步，线性规划的最优解可在约束区域的顶点上达到。第41页，共42页，编辑于2022年，星期一42 线性规划的图解提示若线性规划的决策变量有三个线性规划的约束区域是一个多面体；线性规划有解则最优解可在约束区域的顶点上达到求解线性规划就是寻找约束区域的顶点若线性规划的决策变量有n个线性规划的约束区域是一个多胞形；第42页，共42页，编辑于2022年，星期一