线性规划图解法和单纯形法.pptx

《线性规划图解法和单纯形法.pptx》由会员分享，可在线阅读，更多相关《线性规划图解法和单纯形法.pptx（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）第1页/共87页线性规划问题的数学模型例1.1 如图所示，如何截取x使铁皮所围成的容积最大？xa第2页/共87页线性规划问题的数学模型例1.2 某厂生产两种产品，下表给出了单位产品所需

2、资源及单位产品利润 问：应如何安排生产计划，才能使总利润最大？解：1.决策变量：设产品I、II的产量 分别为 x1、x22.目标函数：设总利润为z，则有：maxz=2x1+x23.约束条件：5x2156x1+2x224 x1+x25 x1，x20 x1=3.8,x2=1.2,z=22.8第3页/共87页线性规划问题的数学模型例1.3 已知资料如下表所示，问如何安排生产才能使利润最大？或如何考虑利润大，产品好销。设设 备备产产 品品 A B C D利润利润（元）（元）2 1 4 0 2 2 2 0 4 3 有有 效效 台台 时时12 8 16 12解：1.决策变量：设产品I、II的产量分别为 x

3、1、x22.目标函数：设总利润为z，则有：maxz=2x1+x23.约束条件：x10,x202x1+2x212x1+2x284x1164x212第4页/共87页线性规划问题的数学模型例1.4 某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量 解：要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。1.决策变量：设四种原料的使用 量分别为：x1、x2、x3、x42.目标函数：设总成本为z min z=5 x1+6 x2+7 x3+8 x43.约束条件：x1+2x2+x3+x41602x1+4x3+2x420

4、03x1x2+x3+2x4 180 x1、x2、x3、x40第5页/共87页 例1.5 某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：航线号航线号船队船队类型类型编队形式编队形式货运成本货运成本（千元队）（千元队）货运量货运量（千吨）（千吨）拖轮拖轮A型型驳船驳船B型型驳船驳船1112362521436202322472404142720船只种类船只种类船只数船只数拖拖 轮轮30A型驳船型驳船34B型驳船型驳船52航线号航线号合同货运量合同货运量12002400问：应如何编队，才能既完成合同任务，又使总货运成本为最小？线性规划问题的数学模型第6页/共87页 解：设

5、：xj为第j号类型船队的队数（j=1，2，3，4），z为总货运成本则：minz=36x1+36x2+72x3+27x4x1+x2+2x3+x4302x1+2x3344x2+4x3+4x45225x1+20 x220040 x3+20 x4400 xj0（j=1,2,3,4）线性规划问题的数学模型第7页/共87页线性规划问题的数学模型2.2.线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量DecisionvariablesDecisionvariables目标函数目标函数ObjectivefunctionObjectivefunction约束条件约束条件Const

6、raintsConstraints其特征是：其特征是：（1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性线性函数，函数，通常是求最大值或最小值；通常是求最大值或最小值；（2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性不不等式或等式。等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？第8页/共87页线性规划问题的数学模型3.3.建模条件建模条件(1)(1)优化条件优化条件：问题所要达到的目标能用线型函数描述，且：问题所要达到的目标能用线型函数描述，且能够用极值能够用极值 （maxmax或或 minmin）

7、来表示；）来表示；(2)(2)限定条件（约束条件）限定条件（约束条件）：达到目标受到一定的限制，且：达到目标受到一定的限制，且这些限制能够用决策变量的这些限制能够用决策变量的 线性等式或线性不等式表示；线性等式或线性不等式表示；(3)(3)选择条件选择条件：有多种可选择的方案供决策者选择，以便找：有多种可选择的方案供决策者选择，以便找出最优方案。出最优方案。第9页/共87页线性规划问题的数学模型4.4.建模步骤建模步骤(1)(1)确定决策变量确定决策变量：即需要我们作出决策或选择的量。一般：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量；情况下，题目问什么就设什么为决策

8、变量；(2)(2)找出所有限定条件找出所有限定条件：即决策变量受到的所有的约束；：即决策变量受到的所有的约束；(3)(3)写出目标函数写出目标函数：即问题所要达到的目标，并明确是：即问题所要达到的目标，并明确是maxmax还是还是 minmin。第10页/共87页线性规划问题的数学模型目标函数：目标函数：约束条件：约束条件：5.5.线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：第11页/共87页线性规划问题的数学模型向量形式：向量形式：其中：第12页/共87页线性规划问题的数学模型矩阵形式：矩阵形式：其中：第13页/共87页线性规划问题的数学模型6.线性规划问题的标准形式特点：(

9、1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。第14页/共87页线性规划问题的数学模型（2 2）如何化标准形式）如何化标准形式 目标函数的转换 如果是求极小值即 ，则可将目标函数乘以(-1)，可化为求极大值问题。也就是：令 ，可得到上式。即 若存在取值无约束的变量 ，可令 其中：变量的变换第15页/共87页线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量 常量 bi0 的变换:约束方程两边乘以（1）第16页/共87页线性规划问题的数学模型例1.6将下列线性规划问题化为标准形式用 替换

10、，且 解:（）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以第17页/共87页线性规划问题的数学模型(2)第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3)第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z=-z,得到maxz=-z，即当z达到最小值时z达到最大值，反之亦然;第18页/共87页线性规划问题的数学模型标准形式如下：第19页/共87页 例1.7将下列线性规划问题化为标准形式为无约束（无非负限制）

11、线性规划问题的数学模型第20页/共87页 解:用 替换 ，且 ，将第3个约束方程两边乘以（1）将极小值问题反号，变为求极大值标准形式如下：引入变量线性规划问题的数学模型第21页/共87页 例1.8将线性规划问题化为标准型解：线性规划问题的数学模型第22页/共87页 例1.9将线性规划问题化为标准型解：Minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4284x1+2x2+3x3-9x4396x2+2x3+3x4-58x1,x3 ,x40；x2无约束 Maxz=3x15x2+5x2”8x3+7x4s.t.2x13x2+3x2”+5x3+6x4+x5=284x1+2x2

12、-2x2”+3x3-9x4-x6=39-6x2+6x2”-2x3-3x4-x7=58x1,x2,x2”,x3,x4,x5,x6,x70线性规划问题的数学模型第23页/共87页线性规划问题的数学模型7.线性规划问题的解线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。第24页/共87页线性规划问题的数学模型 可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。基：设A为约束条件的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子方阵（B0），称B是规划问题的一个基。设：称B中每个列

13、向量Pj(j=1,2,m)为基向量。与基向量Pj 对应的变量xj为基变量。除基变量以外的变量为非基变量。第25页/共87页线性规划问题的数学模型 基解：某一确定的基B，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变量取非零值的个数不大于方程数m，基解的总数不超过 基可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解第26页/共87页线性规划问题的数学模型例1.10 求线性规划问题的所有基矩阵。解:约束方程的系数矩阵为25矩阵r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即第27页/共87页图解法线

14、性规划问题的求解方法一 般 有两种方法图 解 法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式下面我们分析一下简单的情况只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观的优点，便于初学者窥探线性规划基本原理和几何意义。第28页/共87页 解题步骤4 将最优解代入目标函数，求出最优值。1 在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为可行域，可行域中的点即为可行解。2 标出目标函数值增加或者减小的方向。3 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相

15、交的点，该点就是最优解。图解法第29页/共87页图解法max Z=2X1+X2 X1+1.9X2 3.8 X1 -1.9X2 3.8s.t.X1+1.9X2 10.2 X1 -1.9X2 -3.8 X1 ，X2 0例1.11用图解法求解线性规划问题第30页/共87页图解法x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()4=2X1+X220=2X1+X217.2=2X1+X2Lo：0=2X1+X2（7.6，2）DmaxZminZ此点是唯一最优解，且最优目标函数值maxZ=17.2可行域maxZ=2X1+X2第31页/共

16、87页图解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()（7.6，2）DL0：0=3X1+5.7X2maxZ（3.8，4）34.2=3X1+5.7X2蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域第32页/共87页图解法min Z=5X1+4X2x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1+1.9X2=10.2()DL0：0=5X1+4X2maxZminZ8=5X1+4X243=5X1+4X2（0，2

17、）可行域此点是唯一最优解第33页/共87页图解法246x1x2246无界解(无最优解)maxZ=x1+2x2例1.6x1+x2=4()x1+3x2=6()3x1+x2=6()maxZminZ第34页/共87页x1x2O10203040102030405050无可行解(即无最优解)maxZ=3x1+4x2例1.7第35页/共87页 由图解法得到的几种情况 根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况：1.可行域为封闭的有界区域 (a)有唯一的最优解；(b)有无穷多个最优解；2.可行域为封闭的无界区域 (c)有唯一的最优解；(d)有无穷多个最优解；(e)目标函数无界

18、(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。3.可行域为空集 (f)没有可行解，原问题无最优解图解法第36页/共87页 由图解法得到的启示(1)线性规划问题解的情况：唯一最优解；无穷多最优解；无界解；无可行解(2)线性规划问题的可行域是凸集（凸多边形）图解法第37页/共87页图解法x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()17.2=2X1+X2Lo：0=2X1+X2（7.6，2）DmaxZminZ可行域maxZ=2X1+X2(3)最优解一定是在凸集的某个顶点第38页/共8

19、7页 解题思路 先找出凸集的任一顶点，计算其目标函数值，再与周围顶点的目标函数值比较，如不是最大（或最小），继续比较，直到找出最大（或最小）为止。图解法第39页/共87页图解法学习要点：1.通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）2.作图的关键有三点：(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动第40页/共87页连接几何形体中任意两点的线段仍完全在该几何形体之中。有限个凸集的交集仍然是凸集。单纯形法基本原理凸集第41页/共87页单纯形法基本原理凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合

20、C中的点，称C为凸集。凸集凸集不是凸集第42页/共87页单纯形法基本原理凸集凸集顶点顶点：如果凸集C中不存在任何两个不同的点X1，X2，使X成为这两个点连线上的一个点第43页/共87页单纯形法基本原理定理定理1 1：若线性规划问题存在可行解，则该问题的可行域是：若线性规划问题存在可行解，则该问题的可行域是凸集。凸集。定理定理2 2：线性规划问题的基可行解：线性规划问题的基可行解X X对应可行域对应可行域(凸集凸集)的顶点。的顶点。定理定理3 3：若问题存在最优解，一定存在一个基可行解是最优：若问题存在最优解，一定存在一个基可行解是最优解。（即在某个顶点取得）解。（即在某个顶点取得）第44页/共

21、87页几个基本定理的证明定理1 若线性规划问题存在可行解，则问题的可行域是凸集。思路：若满足线性规划约束条件 的所有点组成的几何图形C是凸集，根据凸集的定义，C内任意两点 X1,X2连线上的点也必然在C内。【证】设 为 C 内任意两点，即 ，将X1,X2代入约束条件有X1,X2连线上任意一点可以表示为：第45页/共87页将(1.9)代入约束条件并由式(1.8)得：所以 。由于集合内任意两点连线上的点均在集合内，所以 C 为凸集。第46页/共87页一个引理引理 线性规划问题的可行解 为基可行解的的充要条件是X的正分量所对应的系数列向量是线性独立的。【证】必要性由基可行解的定义是显然的。充分性：若

22、向量P1,P2,Pk是线性独立的，则必有km。1)当k=m时，它们恰好构成一个基，从而相应的基可行解为2)当k0 得第58页/共87页式(1.15)+式(1.17)，并经过整理后有由上式找到满足约束方程组 的另外一个点：其中 是 的第j 个坐标的值。要使 是一个基可行解，因 0，故应对所有i=1,.,m存在且这m个不等式中至少有一个等号成立，因为当 时，上式显然成立。第59页/共87页这样 中正分量最多有m个，容易证明m个向量线性无关，故只需按式(1.20)来确定 的值，就是一个新的基可行解。令第60页/共87页基本可行解和可行基的变换基本可行解：可行基：换出基换入基第61页/共87页STEP

23、3 最优性检验和解的判别最优性检验和解的判别将基可行解 分别代入目标函数得因 0为给定，所以只要有 通常简写为 ，它是对线性规划问题的解进行最优性检验的标志。第62页/共87页1.当所有的 时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可行解）的目标函数值都大，现有顶点对应的基可行解即为最优解。2.当所有 时，对某个非基变量 xj 有 ，且按公式(1.20)可找到0，这表明可以找到另一顶点（基可行解）目标函数也达到最大。由于该两点连线上的点也属可行域内的点，且目标函数值相等，即该线性规划问题有无穷多最优解。3.如果存在某个 又Pj向量的所有分量aij0。换基时对任意 0,恒有 因取

24、值可无限大，在由X(0)换到X(1)时目标函数值也可无限大，则线性规划问题存在无界解。第63页/共87页引例：引例：求解线性规划问题 LP规划问题的最优解可从基可行解（顶点）中找到图解法有局限性；枚举法计算量大；第64页/共87页解：第一:将该问题化成标准形第二:找初始可行解(即一个顶点)。系数矩阵A=(P1P2P3P4P5)矩阵形式第65页/共87页 因为P3，P4，P5 线性独立，故B=(P3,P4,P5)构成一个基，其对应的基变量x3，x4，x5，解出来为（用非基变量表示基变量）x3 =8-x1-2x2 x4 =16-4x1 (1)x5 =12-4x2XB=B-1b B-1NXN将(1)

25、代入目标函数中得z=0+2x1+3x2令非基变量x1=x2=0，则有z=0。这时得到一个基可行解：X(0)=(0,0,8,16,12)T-原点第66页/共87页第三:判别从目标函数z=0+2x1+3x2中得知，非基变量x1和x2的系数为正，因此，将非基变量换入基后可使目标函数增大，转入第四步第四：换基(旋转迭代)确定换入变量：由于非基变量x2的系数（正）贡献最大，故需换入的基变量为x2。换入变量已定，必须从x3，x4，x5换出一个，并且要保证其余均是非负的，即x3，x4，x50。当x1=0时，有x3=8-2x20 x4=160 x5=12-4x20 x2换入基，x1未换入，还是非基变量第67页

26、/共87页 只要选择 x2=min(8/2，-，12/4)=3，对应基变量x5=0，从而确定用x2和x5对换，即将x5 换出，（用非基变量表示基变量）2x2+x3=8-x1x4=16-4x14x2=12-x5用高斯消去法（行变换），得x3=2-x1+1/2x5x4=16-4x1x2=3-1/4x5（2）将上式代入原目标函数中得z=9+2x1-3/4x5（1）第68页/共87页 返回第三步：从z=9+2x1-3/4x5，非基变量x1的系数是正的，还可增大。重复上述步骤。由于x1的系数是正的，则x1为转入变量，再由当x5=0时 x3 =2-x1 0 x4=16-4 x1 0 x2 =3 0 只要选

27、x1=min2，16/4，-=2上式就成立，因为x1=2时，基变量x3=0，从而由x1换出x3令非基变量x1和x5为零有z=9，又得到另一个基可行解X(1)=(0,3,2,16,0)T顶点Q4第69页/共87页 x1+2x2 =8-x3 4x1 +x4=16 (3)4x2 =12-x5高斯消去法（行变换）得 x1=2-x3+1/2x50 x4=8-2x5+4x30 x2=3-1/4x50代入目标函数中，得z=13-2x3+1/4x5令非基变量x3=x5=0有z=13，又得到另一个基可行解X(2)=(2,3,0,8,0)T顶点Q3;（2）用非基变量表示基变量第70页/共87页同理，返回第三步，再

28、迭代，x5作为转入变量只要取x5=min-，8/2，12=4就有上式成立。x5=4时，x4=0，故用x5换x4x1=4-1/4x4x5=4-1/2x4+2x3x2=2+1/8x41/2x3令x3=0，有 x1=2+1/2x50 x4=8-2x50 x2=3-1/4x50（3）+高斯第71页/共87页0Q4Q3Q2Q11123234X1X2x1+2x2=84x1=164x2=12代入得z=14-3/2x3-1/8x4，令x3=x4=0得z=14。新的基可行解为X(3)=(4,2,0,0,4)T顶点Q2(最优解)最优目标值z=14。(0,3,2,16,0)(0,0,8,16,12)(2,3,0,8

29、,0)(4,2,0,0,4)第72页/共87页单纯形法的计算步骤单纯形表确定换出基确定换入基第73页/共87页单纯形法的计算步骤例1.12 用单纯形法求下列线性规划的最优解解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:第74页/共87页单纯形法的计算步骤2）求出线性规划的初始基可行解，列出初始单纯形表。cj3400icB基基bx1x2x3x40 x34021100 x43013013400检验数第75页/共87页单纯形法的计算步骤3）进行最优性检验如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。4）从一个基可行解转换到另一个目标值更大的基可行解，列

30、出新的单纯形表确定换入基的变量。选择 ，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。确定换出变量。根据下式计算并选择，选最小的对应基变量作为换出变量。主元素第76页/共87页单纯形法的计算步骤用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。在新表中的基仍应该是单位矩阵，则应将主元素所对应的列(换入基)变成单位向量，包括约束条件的系数矩阵，基对应的值，检验数等换入变量xk的检验数应为0高斯变换第77页/共87页单纯

31、形法的计算步骤cj3400iCB基变量bx1x2x3x40 x34021100 x430130134000 x34x23x14x2换入列bi/ai2，ai204010换出行将3化为15/311801/301/3101-1/3303005/30-4/3乘以1/3后得到103/5-1/51801-1/52/5400-1-1第78页/共87页单纯形法的计算步骤例1.13 用单纯形法求解解：将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，列单纯形表计算。第79页/共87页单纯形法的计算步骤cj12100iCB基变量bx1x2x3x4x50 x4152-32100 x5201/3150112

32、1000 x42x220 x x2 221/3150120753017131/309022560 x x1 111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第80页/共87页变成标准型单纯形法的计算步骤例1.14 用单纯形法求解第81页/共87页约束方程的系数矩阵 为基变量为非基变量I 为单位矩阵且线性独立单纯形法的计算步骤第82页/共87页第83页/共87页第84页/共87页第85页/共87页单纯形法的计算步骤学习要点：1.线性规划解的概念以及3个基本定理2.熟练掌握线性规划问题的标准化3.熟练掌握单纯形法的解题思路及求解步骤第86页/共87页感谢您的观看！第87页/共87页