运筹学第讲线性规划.ppt

《运筹学第讲线性规划.ppt》由会员分享，可在线阅读，更多相关《运筹学第讲线性规划.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、运筹学第讲线性规划现在学习的是第1页，共52页线性规划问题的几何意义线性规划问题的几何意义 凸集:设K是n维欧氏空间的一点集，若任意两点 X(1)K，X(2)K的连线上的所有点 X(1)+(1-)X(2)K，(01)则称K为凸集。注：实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图中的(a)(b)是凸集，(c)不是凸集。任何两个凸集的交集仍为凸集，如图(d)。现在学习的是第2页，共52页线性规划问题的几何意义线性规划问题的几何意义结论：任何两个凸集的交集仍为凸集。证明：设A，B为凸集，则 因此同理 从而所以A与B的交集为凸集。现在学习的是第

2、3页，共52页线性规划问题的几何意义线性规划问题的几何意义 凸组合：设X(1)，X(2)，X(k)是n维欧氏空间En中的k个点，若存在1，2，k，且0i1,i=1,2,，k，使 X=1X(1)+2X(2)+kX(k)，则称X为X(1)，X(2)，X(k)的凸组合。（当0i1时，称为严格凸组合）。顶点：设K是凸集，XK；若X不能用不同的两点X(1)K和X(2)K 的线性组合表示为X=X(1)+(1-)X(2)，(01)，则称X为K的一个顶点(或极点)。注 右图中0,Q1,Q2,Q3,Q4都是顶点。现在学习的是第4页，共52页线性规划问题的几何意义线性规划问题的几何意义关于线性规划问题的几个定理：

3、定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。定理2：线性规划问题的基可行解X对应可行域(凸集)的顶点。定理3：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）以上证明过程见P16-20.现在学习的是第5页，共52页 单纯形法 尽管若线性规划问题有最优解，必可以在某顶点上得到，虽然顶点数目是有限的(它不大于个)，若采用“枚举法”找所有基可行解，然后一一比较，最终可能找到最优解。但当n,m的数较大时，这种办法是行不通的。（m=20，n=40时，顶点的个数有 个）。如何有效地找到最优解，有多种方法，这里仅介绍单纯形法(Simplex Method)。现在学习的是第6

4、页，共52页 单纯形法单纯形法 单纯形：单纯形或者n-单纯形是和三角形类似的n维几何体。精确的讲，单纯形是某个n维以上的欧几里得空间中的（n+1）个仿射无关（也就是没有m维平面包含m+1个点；这样的点集被称为处于一般位置）的点的集合的凸包。0-单纯形就是点，1-单纯形就是线段，2-单纯形就是三角形，3-单纯形就是四面体，而4-单纯形是一个五胞体（每种情况都包含内部）。标准n-单纯形：是Rn+1的子集：现在学习的是第7页，共52页 单纯形法单纯形法 单纯形法的基本思路：根据前述定理，如果线性规划问题存在最优解，则可以在基本可行解中找最优解。由于基本可行解的个数是有限的，所以通过建立一种最优性判别

5、准则，将基本可行解逐一进行检查，就可以在有限次检查后得到最优解。但是，在有些情况下，要找出所有的基本可行解是非常麻烦的，单纯形法的优越性就在于不用找出全部的基本可行解。现在学习的是第8页，共52页 单纯形法单纯形法 单纯形法的基本思路：在得到一个基本可行解X1后，判断X1是否是最优解，或者判断此问题没有最优解。如果X1是最优解，或者此问题没有最优解，则求解到此为止；若不然，则依据这个解X1求出下一个基本可行解X2，并且X2要比X1对应的目标函数值有所改善。对X2重复刚才的判断，直到得到问题的解答为止。X1X2X3现在学习的是第9页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(1)确定初始

6、基本可行解X1；(2)记Xk为求出的第k个基本可行解，根据建立的最优性准则，对Xk进行检验，若Xk是最优解，则计算终止;若不然，则转第(3)步；(3)若根据建立的无最优解准则判断此问题没有最优解，则计算终止；若不能判定没有最优解，则转第(4)步；(4)依据Xk求基本可行解Xk+1，使Z(Xk+1)Z(Xk)，令k=k+1，转回第(2)步。现在学习的是第10页，共52页 单纯形法单纯形法 单纯形法的基本步骤：是否最优是否最优是否最优是否最优转移到另一个基本可行解转移到另一个基本可行解转移到另一个基本可行解转移到另一个基本可行解（找出更大的目标函数值）（找出更大的目标函数值）（找出更大的目标函数值

7、）（找出更大的目标函数值）最优解最优解最优解最优解是是是是否否否否核心是：变量迭代核心是：变量迭代核心是：变量迭代核心是：变量迭代结束结束结束结束找出一个初始可行解找出一个初始可行解找出一个初始可行解找出一个初始可行解循循循循环环环环现在学习的是第11页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(1)确定初始的基本可行解X1；-假设在约束系数矩阵中含有单位阵并且bi 0，i=1,2,m，则令单位阵所在列对应的变量为基变量，其他变量为非基变量，并令非基变量取零值，可得到初始基本可行解。-对于所有行约束条件为“”不等式，在每行引入松弛变量化为标准形后，所有松弛变量的系数矩阵正好为单位矩阵。

8、-当化为标准形后系数矩阵中不含有单位阵时，确定初始基本可行解的方法可采用人工变量法。-首先假设系数矩阵含单位阵的情况。现在学习的是第12页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(2)确定最优性判别准则；设线性规划问题(LP)约束系数矩阵中的前m列为一个单位阵，其模型有如下形式，其中bi 0，i=1,2,m。目标函数：max z =c1 x1+c2 x2+cn xn 约束条件：s.t.x1+a1m+1 x m+1+a1n xn =b1 x2+a2m+1 x m+1+a2n xn =b2 (LP)xm+amm+1 x m+1+amn xn=bm x1，x2，xn 0.现在学习的是第13

9、页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(2)确定最优性判别准则；取x1，xm为基变量，xm+1，xn为非基变量。基本解为X1=（b1，b2，bm，0，0）T。将上式约束方程组变为：x1=b1-（a1m+1 x m+1+a1n xn）x2=b2-（a2m+1 x m+1+a2n xn）xm=bm-（amm+1 x m+1+amn xn）代入目标函数中：Z=c1 x1+c2 x2+cn xn现在学习的是第14页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(2)确定最优性判别准则；记得到目标函数由当前解X1的非基变量的线性表示：其中Z1即为X1对应的目标函数值。现在学习的是第15

10、页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(2)确定最优性判别准则；将上面结果整理后，可得到与原线性规划等价的模型定义：称此等价模型为基本可行解X1对应的典式。现在学习的是第16页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(2)确定最优性判别准则；定理4：设X1=（b1，b2，bm，0，0）T为线性规划(LP)的基本可行解，如果在其对应的典式中则X1为最优解。注：此定理就是单纯形法中的最优性判别准则。现在学习的是第17页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(2)确定最优性判别准则；证明：设 为任一可行解,Z0为其目标函数值。将X0代入基本可行解X1对应的典式的目

11、标函数中，有 由式 ，则有 说明Z1为最大值，X1为最优解，定理得证。现在学习的是第18页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(2)确定最优性判别准则；注：典式中的 称为基本可行解的检验数，确切地说，是X1的非基变量的检验数。为了统一起见，对X1的基变量也规定检验数 ，显然，应有 (因为典式中不含基变量，实际通过公式计算也为零)，即基变量的检验数为零。现在学习的是第19页，共52页 单纯形法单纯形法例3.1 为下面线性规划问题的一个基本可行解，试判断其是否为最优解。解:将模型化为基本可行解X1对应的典式，X1=(6,2,15,0,0)T 可知，x4,x5为非基变量，约束条件已具有

12、典式形式，只需要将目标函数由非基变量x4,x5线性表示即可：Z=-(6-x4-6x5)+(2+x4-x5)+2(15-6x4-2x5)+2 x4+x5=26-8 x4+2x5由此可知 ，其中 不满足最优性准则，因此不能判断X1为最优解。现在学习的是第20页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(3)确定无最优解判别准则；定理5 设X1为线性规划问题的基本可行解，如果在X1对应的典式中存在检验数 ，并且 的约束系数 皆小于等于零，则该线性规划问题的目标函数在可行域上没有上界，即没有最优解（无界解）。例 3.2 判断下面的问题是否没有最优解。现在学习的是第21页，共52页 单纯形法单纯

13、形法解:取 为基本可行解，对于X1此模型已经为典式形式。其中检验数 ，并且 皆小于等于零，由定理判断无最优解。怎么理解？分析：由约束条件可知，对于x3取任何非负值，此问题都存在可行解 ，目标函数值为 。故而可知当M逐渐增大时，Z也相应增大，当 时，因此Z为最大值，规划无最优解。现在学习的是第22页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(4)基本可行解的迭代；定义:根据已有的基本可行解求新的基本可行解称为迭代。定义:将原基本可行解X1中的某个非基变量变为基变量，称为进基变量；将X1的某个基变量变为非基变量，称为出基变量。注:迭代的过程实际就是要实现进基变量和出基变量之间 的转换。现在

14、学习的是第23页，共52页 单纯形法单纯形法迭代方法:设 为基变量，并且存在检验数 ，由X1 的典式形式的目标函数的表达式可知其中Z1为X1对应的目标函数值。由于 ，故若选 xk 为进基变量时(一般基变量的取值大于零)，可使目标函数值进一步增加。因此确定xk为进基变量。基本可行解X1的典式形式的约束方程组为在基本可行解中，基变量的个数是固定的m个,xk进基，则必有一个基变量转换为非基变量。现在学习的是第24页，共52页 单纯形法单纯形法 为了确定出基变量，首先在典式的约束中，令除xm以外的其余非基变量仍取零值，得到:根据这个关系式，又考虑到每个决策变量的可行性，从而选取xk，使其满足如下的关系

15、式:现在学习的是第25页，共52页 单纯形法单纯形法 当 时，因为bi 非负，故只需要 即可;当 时，则需 。综合上面两种情况，因此，应使 xk 满足注:因为最优性判别准则和无最优解判别定理不成立，故可以保证 的存在性，以及 。按照上面的规则确定的变量xk，当 时，使得原 第l 个基变量的值变为:即基变量 xl 成为出基变量。现在学习的是第26页，共52页 单纯形法单纯形法 可以证明，矩阵 仍为可行基，因此得到新的基本可行解 ，其中各分量的值为:根据X1的典式的表达式中的目标函数，将X2代入计算得:新解比原解有所改善，增量为 至此，完成了基本可行解的迭代。现在学习的是第27页，共52页 单纯形

16、法单纯形法 定义:一般称 为最小比值规则，或称为 规则，其中的 称为中心元素（主元）。现将基本可行解的迭代过程归纳如下：设已得到基本可行解对应的典式形式。(1)取 对应的xk为进基变量。（主要是提高收敛效率，使得每次的增量 最大。）(2)按最小比值规则确定xk的值，并确定出基变量。(3)按右式确定新的基本可行解。现在学习的是第28页，共52页 单纯形法单纯形法例3.3 根据基本可行解X1以及典式，迭代求新的基本可行解，并指出目标函数值的增量。其典式为X1的目标函数值为Z1=26解:由于 ，所以确定x5 为进基变量。按最小比值规则计算出 因此 ，同时确定xl为出基变量，取零值，另外x4 为非基变

17、量仍取零值。现在学习的是第29页，共52页 单纯形法单纯形法将这些取值代入X2计算公式中，得到新的基本可行解为其目标函数值为目标函数值的增量为 。对X2还应继续判断其是否是最优解。则问题转化为如何确定新的基本可行解X2的检验数。现在学习的是第30页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(5)新的基本可行解的检验数的确定。不失一般性，考虑下面的线性规划模型:假设已得到的基本可行解 不是最优解。并假设经过计算，确定x5为进基变量，x1为出基变量，a15为中心元素，得到新的基本可行解 ,现在学习的是第31页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(5)新的基本可行解的检验数的确

18、定。为了判断X2是否最优解，需要对约束方程组进行适当变换，找出X2对应的典式形式。为此，首先要在约束方程组中将新基变量x2,x3,x5显式表示出来，然后代入目标函数，得到目标函数由新的非基变量的线性表示，从而得到X2对应的检验数。这些变换可以经过下面的矩阵变换实现，即根据约束方程组构造矩阵式，对其进行初等行变换，变为矩阵式现在学习的是第32页，共52页 单纯形法单纯形法 单纯形法的基本步骤：(5)新的基本可行解的检验数的确定。即：将进基变量x5对应的第5列向量化为单位向量，其中将中心元素a15化为1。由上面得到转化后的矩阵式，得到新的基本可行解X2对应的典式形式：其中 即为新解X2的检验数，根

19、据他们的正负，可以判断X2是否最优解。现在学习的是第33页，共52页 单纯形法单纯形法例3.4 对例3.3中得到的基本可行解X2，判断其是否是最优解。由此可得到在求X2的检验数时用到的矩阵解:是根据 得到的，而X1对应的典式为将进基变量x5对应的第5列向量化为单位向量，将中心元素a15=6化为1，得到:现在学习的是第34页，共52页 单纯形法单纯形法由此矩阵可知，的检验数 ，全部小于等于零，因此X2就是最优解。现在学习的是第35页，共52页 单纯形法单纯形法小结 单纯形法的主要步骤：Step1 确定初始的基本可行解X1，求出X1对应的典式；Step2 根据最优性准则判别定理判断X1是否是最优解

20、，若是，算法停止，X1即为最优解。否则，根据无最优解判别准则判断此线性规划是否无最优解，若是，算法停止，此规划无最优解；否则，转Step3；Step3 由 确定xk为进基变量，根据最小比值规则确定xk的值 ，确定中心元素和出基变量；Step4 采用初等行变换将中心元素化为1，并将中心元素所在列化为单位列向量确定新的基本可行解X2，以及X2对应的检验数，转Step2。现在学习的是第36页，共52页 单纯形法单纯形法 单纯形法的求解过程，实际上是在一系列表格上进行的。从这些表格上可以得到基本解、检验数等信息，这些表格称为单纯形表。每一个单纯形表相当于一个矩阵，每次迭代就是对矩阵进行初等行变换。例3

21、.5 求解下面的线性规划问题现在学习的是第37页，共52页 单纯形法单纯形法解:单纯形表的主要步骤1：构造初始单纯形表；单纯形表是根据线性规划问题的基本可行解对应的典式形式得到的。现在取X1=(5,0,0,6,24)T求作为初始基本可行解，显然，模型中目标函数不是典式形式，因此需要将x4=6-x2+4x3代入目标函数Z，经整理得到 Z=6+x2+2x3。现在学习的是第38页，共52页 单纯形法单纯形法构造初始单纯形表cj02-210CBXBbx1x2x3x4x50 x15111000 x4601-4100 x52402601cj-zj0 1200CB表示基变量的系数，XB表示当前基变量，b表示

22、当前基变量的取值，cj行为基变量的价值系数，为待填入的按最小比值规则计算的值。现在学习的是第39页，共52页 单纯形法单纯形法解:单纯形表的主要步骤2：迭代求新的基本可行解及其检验数；在上面的单纯形表中，x2,x3检验数大于零，不满足最优性准则，需要进行迭代。确定中心元素以及进、出基变量，将中心元素化为1，中心元素所在列化为单位向量。cj02-210CBXBbx1x2x3x4x50 x151110050 x4601-410-0 x524026014cj-zj0 1200现在学习的是第40页，共52页 单纯形法单纯形法解:单纯形表的主要步骤2：迭代求新的基本可行解及其检验数；cj02-210CB

23、XBbx1x2x3x4x50 x1112/300-1/63/20 x42207/3012/366/7-2x3401/3101/612cj-zj0 1/320-1/3现在学习的是第41页，共52页 单纯形法单纯形法解:单纯形表的主要步骤3：继续迭代；cj02-210CBXBbx1x2x3x4x52x23/23/2100-1/40 x437/2-7/20015/4-2x37/2-1/20101/4cj-zj-1/2 000-1/4 此表格中全部检验数均小于等于零，故得到最优解 X*=(0,3/2,7/2,37/2,0)T,其对应的目标函数值为29/2。最优单纯形表最优单纯形表现在学习的是第42页，

24、共52页 单纯形法单纯形法例3.5 用单纯形法求解 解:初始基本可行解为X1=(7,0,0,12,0,10)T,所给模型即为典式，可直接建立单纯形表进行计算。现在学习的是第43页，共52页 单纯形法单纯形法cj0-130-20CBXBbx1x2x3x4x5x60 x1713-102070 x4120-2410030 x6100-4308110/3cj-zj00-130-20现在学习的是第44页，共52页 单纯形法单纯形法cj0-130-20CBXBbx1x2x3x4x5x60 x11015/201/4203x330-1/211/4000 x610-5/20-3/481cj-zj-901/20-

25、3/4-20现在学习的是第45页，共52页 单纯形法单纯形法cj0-130-20CBXBbx1x2x3x4x5x6-1x245/2101/104/503x351/5013/102/500 x611100-1/2101cj-zj-11-1/500-4/5-12/50由上表得知，最优解为X*=(0,4,5,0,0,11)T,最优值为11。现在学习的是第46页，共52页 软件实现软件实现例3.6 求解Max 2x1+3x2 St.4x1+3x2=10 3x1+5x2=12 x10 x20model:model:maxmax=2*x1+3*x2;2*x1+3*x2;4*x1+3*x210;4*x1+3

26、*x210;4*x1+3*x210;4*x1+3*x210;3*x1+5*x212;3*x1+5*x212;endlingo现在学习的是第47页，共52页 软件实现软件实现现在学习的是第48页，共52页 软件实现软件实现Global optimal solution found at iteration:2Objective value:7.454545Variable Value Reduced Cost x1 1.272727 0.000000 x2 1.636364 0.000000Row Slack or Surplus Dual Price 1 7.454545 1.000000 2

27、 0.000000 0.9090909E-01 3 0.000000 0.5454545现在学习的是第49页，共52页 软件实现软件实现现在学习的是第50页，共52页 软件实现软件实现 线性规划的matlab解法：问题形式1：min z=CTx S.t.A x b指令：（x，z）=linprog(f,A,b)问题形式2：min z=CTx S.t.A x b Aeq x=beq指令：（x，z）=linprog(f,A,b,Aeq,beq)现在学习的是第51页，共52页 软件实现软件实现 线性规划的matlab解法：问题形式3：min z=CTx S.t.A x b Aeq x=beq lb x ub指令：（x，z）=linprog(f,A,b,Aeq,beq,lb,ub)注:若没有不等式约束,可用 替代A和b,若没有等式约束,可用 替代Aeq和beq,若某个xi下无界或上无界,可设定-inf或 inf；现在学习的是第52页，共52页