生产运筹学--线性规划及单纯形法（PPT 66页）

来自中国最大的资料库下载第一章线性规划及单纯形法线性规划（LinearProgramming，简称LP）运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。1947年G.B.Dantying提出了一般线性规划问题求解的方法——单纯形法之后，线性规划的理论与应用都得到了极大的发展。60年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。来自中国最大的资料库下载§1线性规划问题及其数学模型e.g.1资源的合理利用问题问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？表1产品资源甲乙库存量A1360B1140单件利润1525某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表1。来自=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决策变量来自中国最大的资料库下载§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试在满足营养要求的前提下，确定食品的购买量，使食品的总价格最低。来自…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来自中国最大的资料库下载§1线性规划问题及其数学模型三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成n个子系统处理。1、决策变量xj≥02、约束条件——一组决策变量的线性等式或不等式3、目标函数——决策变量的线性函数来自（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）为已知常数线性规划问题的一般形式：来自中国最大的资料库下载§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、所有决策变量均非负。来自中国最大的资料库下载第一章线性规划及单纯形法如何转化为标准形式？1、目标函数为求极小值，即为：。njjjxcz1minnjjjxcz1'max因为求minz等价于求max(-z)，令z’=-z，即化为：2、约束条件为不等式，njinjijbxxa11njijijbxa1njijijbxa1xn+1≥0松弛变量如何处理？来自中国最大的资料库下载§1线性规划问题及其数学模型３、右端项bi0时，只需将等式两端同乘（-1）则右端项必大于零4、决策变量无非负约束设xj没有非负约束，若xj≤0，可令xj=-xj’，则xj’≥0；又若xj为自由变量，即xj可为任意实数，可令xj=xj’-xj’’，且xj’,xj’’≥0来自=-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≥0来自中国最大的资料库下载§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212222111211来自中国最大的资料库下载§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来自中国最大的资料库下载§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达到最大的唯一可行点来自问题图解法的基本步骤：1、在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；4、寻找最优解。来自中国最大的资料库下载§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.2来自=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4x1，x2≥01222xx1244xxOA(１,0)x1x2Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。可行域为无界区域一定无最优解吗？来自中国最大的资料库下载§2线性规划问题的图解法由以上两例分析可得如下重要结论：1、LP问题从解的角度可分为：⑴有可行解⑵无可行解a.有唯一最优解b.有无穷多最优解C.无最优解2、LP问题若有最优解，必在可行域的某个顶点上取到；若有两个顶点上同时取到，则这两点的连线上任一点都是最优解。来自中国最大的资料库下载§2线性规划问题的图解法图解法优点：直观、易掌握。有助于了解解的结构。图解法缺点：只能解决低维问题，对高维无能为力。来自中国最大的资料库下载§3线性规划问题解的基本性质讨论如下LP问题：max(1)..20(3)zcxstAxbx12,,,ncccc价值向量12,,,Tnxxxx12,,,,0Tmibbbbb右端向量111212122212nnmmmnaaaaaaAaaa其中系数矩阵决策向量假设A的秩为m,且只讨论mn的情形。什么意思？为什么？来自问题中，约束方程组（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)来自中国最大的资料库下载§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的基本解来自(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称为可行基。来自中国最大的资料库下载§3线性规划问题解的基本性质基本解唯一吗？最多有多少？mnn!最多有C=种m!(n-m)!Rn非可行解基可行解可基解行解称它是非退化的解；反之，如果有一个基变量也取零值，则称它是退化的解。一个LP问题，如果它的所有基可行解都是非退化的就称该是非退化的，否则就称它是退化的。定义4在LP问题的一个基可行解中，如果