数学建模-第二章线性规划及单纯形法

1第二章线性规划及单纯形法组合优化理论CombinatorialOptimizationTheory2第二章线性规划及单纯形法线性规划（LinearProgramming，简称LP）运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。1947年G.B.Dantying提出了一般线性规划问题求解的方法——单纯形法之后，线性规划的理论与应用都得到了极大的发展。60年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。3§1线性规划问题及其数学模型e.g.1资源的合理利用问题问：如何安排生产计划，使工厂获总利润最大？表1产品资源甲乙库存量A1360B1140单件利润1525某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表1。4第二章线性规划及单纯形法maxz=15x1+25x2s.t.x1+3x2≤60x1+x2≤40x1，x2≥0解：设x1，x2为下一个生产周期产品甲和乙的产量；约束条件：Subjecttox1+3x2≤60x1+x2≤40x1，x2≥0目标函数：z=15x1+25x2表1产品资源甲乙库存量A1360B1140单件利润1525决策变量5§1线性规划问题及其数学模型e.g.2营养问题假定在市场上可买到B1,B2,…Bnn种食品，第i种食品的单价是ci,另外有m种营养A1,A2,…Am。设Bj内含有Ai种营养数量为aij(i=1~m,j=1~n)，又知人们每天对Ai营养的最少需要量为bi。见表2：表2食品最少营养B1B2…Bn需要量A1a11a12…a1nb1A2a21a22…a2nb2………………Amam1am2…amnbm单价c1c2…cn试在满足营养要求的前提下，确定食品的购买量，使食品的总价格最低。6第二章线性规划及单纯形法表2食品最少营养B1B2…Bn需要量A1a11a12…a1nb1A2a21a22…a2nb2………………Amam1am2…amnbm单价c1c2…cn解：设xj为购买食品Bj的数量(j=1,2,…,n)（i=1,2,…,m）xj≥0（j=1,2,…,n）0≤xj≤lj1minnjjjzcx1..nijjijstaxb7§1线性规划问题及其数学模型三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成n个子系统处理。1、决策变量xj≥02、约束条件——一组决策变量的线性等式或不等式3、目标函数——决策变量的线性函数8第二章线性规划及单纯形法max（min）z=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤（或=，≥）b1a21x1+a22x2+…+a2nxn≤（或=，≥）b2……am1x1+am2x2+…+amnxn≤（或=，≥）bmxj≥0（j=1,2,…,n）其中aij、bi、cj（i=1,2,…,m；j=1,2,…,n）为已知常数线性规划问题的一般形式：9§1线性规划问题及其数学模型线性规划问题的标准形式：maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……am1x1+am2x2+…+amnxn=bmxj≥0（j=1,2,…,n）bi≥0（i=1,2,…,m）特点：1、目标函数为极大化；2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负。10第二章线性规划及单纯形法如何转化为标准形式？1、目标函数为求极小值，即为：。njjjxcz1minnjjjxcz1'max因为求minz等价于求max(-z)，令z’=-z，即化为：2、约束条件为不等式，njinjijbxxa11njijijbxa1njijijbxa1xn+1≥0松弛变量如何处理？11§1线性规划问题及其数学模型３、右端项bi0时，只需将等式两端同乘（-1）则右端项必大于零4、决策变量无非负约束设xj没有非负约束，若xj≤0，可令xj=-xj’，则xj’≥0；又若xj为自由变量，即xj可为任意实数，可令xj=xj’-xj’’，且xj’,xj’’≥012第二章线性规划及单纯形法e.g.3试将LP问题minz=-x1+2x2-3x3s.t.x1+x2+x3≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0化为标准形式。解：令x3=x4-x5其中x4、x5≥0；对第一个约束条件加上松弛变量x6；对第二个约束条件减去松弛变量x7；对第三个约束条件两边乘以“-1”；令z’=-z把求minz改为求maxz’maxz’=x1-2x2+3x4-3x5s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥013§1线性规划问题及其数学模型LP的几种表示形式：),,2,1(0),,2,1(..max11njxmibxatsxczjinjjijnjjj12,,,ncccc价值向量max(1)..(2)0(3)zcxstAxbx1max..0njjjzcxstpxbx决策向量Tnxxxx,,,21右端向量0,,,,21iTmbbbbb列向量的第为jAaaapTmjjjj,,,21系数矩阵mnmmnnaaaaaaaaaA21222211121114§2线性规划问题的图解法定义1在LP问题中，凡满足约束条件(2)、(3)的解x=(x1,x2,…,xn)T称为LP问题的可行解，所有可行解的集合称为可行解集（或可行域）。记作D={x|Ax=b,x≥0}。定义2设LP问题的可行域为D，若存在x*∈D，使得对任意的x∈D都有cx*≥cx，则称x*为LP问题的最优解，相应的目标函数值称为最优值，记作z*=cx*。max(1)..(2)0(3)zcxstAxbx15§2线性规划问题的图解法maxz=15x1+25x2s.t.x1+3x2≤60x1+x2≤40x1，x2≥0(40,0)(0,0)BC(30,10)12360xx1240xxO(0,20)AL1L2Z=250目标函数变形：x2=-3/5x1+z/25x2x1最优解：x1=30x2=10最优值：zmax=700B点是使z达到最大的唯一可行点16第二章线性规划及单纯形法LP问题图解法的基本步骤：1、在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；4、寻找最优解。17§2线性规划问题的图解法maxz=3x1+5.7x2s.t.x1+1.9x2≥3.8x1-1.9x2≤3.8x1+1.9x2≤11.4x1-1.9x2≥-3.8x1，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=3x1+5.7x2maxZminZ（3.8,4）34.2=3x1+5.7x2可行域x1-1.9x2=-3.8(0,2)(3.8,0)绿色线段上的所有点都是最优解,即有无穷多最优解。Zman=34.218第二章线性规划及单纯形法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4x1，x2≥01222xx1244xxOA(１,0)x1x2Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。可行域为无界区域一定无最优解吗？19§2线性规划问题的图解法由以上两例分析可得如下重要结论：1、LP问题从解的角度可分为：⑴有可行解⑵无可行解a.有唯一最优解b.有无穷多最优解c.无最优解2、LP问题若有最优解，必在可行域的某个顶点上取到；若有两个顶点上同时取到，则这两点的连线上任一点都是最优解。20§2线性规划问题的图解法图解法优点：直观、易掌握。有助于了解解的结构。图解法缺点：只能解决低维问题，对高维无能为力。21§3线性规划问题解的基本性质讨论如下LP问题：max(1)..20(3)zcxstAxbx12,,,ncccc价值向量12,,,Tnxxxx12,,,,0Tmibbbbb右端向量111212122212nnmmmnaaaaaaAaaa其中系数矩阵决策向量假设A的秩为m,且只讨论mn的情形。什么意思？为什么？22第二章线性规划及单纯形法定义3在上述LP问题中，约束方程组（2）的系数矩阵A的任意一个m×m阶的非奇异的子方阵B（即|B|≠0），称为LP问题的一个基阵或基。111121,,,mmmmmaaBpppaa称pi(i=1,2,…,m)为基向量;xi(i=1,2,…,m)为基变量；xj(j=m+1,…,n)为非基变量pj(j=m+1,…,n)为非基向量;记：111112,,,mnmmmnmmnaaNaappp则A=(B,N)23§3线性规划问题解的基本性质A=(B,N)xB=(x1,…,xm)T,xN=(xm+1,…,xn)T则BNxxx,代入约束方程（2），得.BNxBNbxBnBxNxb自由变量（独立变量）令0Nx1BxBb11BNxBbBNx1(4)0Bbx称（4）为相应于基B的基本解24第二章线性规划及单纯形法1(4)0Bbx是可行解吗？maxz’=x1-2x2+3x4-3x5s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0111110111101312200A令x1=x2=x4=0T5199得一基本解x=(0,0,0,,,-)222如果B-1b≥0，则称（4）为相应于基B的基可行解，此时的基B称为可行基。25§3线性规划问题解的基本性质基本解唯一吗？最多有多少？mnn!最多有C=种m!(n-m)!Rn非可行解基可行解可基解行解称它是非退化的解；反之，如果有一个基变量也取零值，则称它是退化的解。一个LP问题，如果它的所有基可行解都是非退化的就称该是非退化的，否则就称它是退化的。定义4在LP问题的一个基可行解中，如果它的所有的基变量都取正值，则26第二章线性规划及单纯形法LP问题解的基本性质定理1设x是LP问题的可行解(1)若x=0，则它一定是基可行解；(2)若x≠0，则x是基可行解的充要条件是它的非零分量所对应的列向量线性无关。Ax=0定理2如果一个LP问题有可行解，则它必有基可行解。定理3如果一个LP问题有最优解，则必存在一个基可行解是它的最优解。定理2、定理3称为LP问题的基本定理定理2证明向前定理3证明LP问题是一个组合优化问题27§3线性规划问题解的基本性质定理2证明设x=(x1,x2,…,xn)T是LP问题的一个可行解，如果x=0，则由定理1知，它是LP问题的一个基可行解，定理成立。如果x≠0，不妨设x的前k个分量为非零分量。则有x1p1+x2p2+…+xkpk=b，及x10,x20,…,xk0，分两种情况讨论：(1)如果p1,p2,…,pk线性无关，即x的非零分量对应的列向量线性无关，则由定理1知，它是LP的一个基本可行解，定理成立。(2)如果p1,p2,…,pk线性相关，则必存在一组不全为零的数δ1,δ2,…,δk使得10(5)kjjjp28第二章线性规划及单纯形法假定有δi≠0，=min0(6)iiix(2)xx(1)xx12