资源描述：
《线性规划与单纯形法简介.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、运筹学OperationsResearch第一章线性规划及单纯形法第一章线性规划及单纯形法线性规划（LinearProgramming，简称LP）运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。1947年G.B.Dantying提出了一般线性规划问题求解的方法——单纯形法之后，线性规划的理论与应用都得到了极大的发展。60年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。§1线性规划问题及其数学模型e.g.1资源的合理利用问题问：如何安排生产计划，使得既能
2、充分利用现有资源又使总利润最大？表1产品资源甲乙库存量A1360B1140单件利润1525某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表1。第一章线性规划及单纯形法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决策变量§1线性规
3、划问题及其数学模型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试在满足营养要求的前提下，确定食品的购买量，使食品的总价格最低。第一章线性规划及单纯形法表2食品最少营养B1B2…Bn需要量A1a11a12…a1nb1A2a21a22…a2nb
4、2………………Amam1am2…amnbm单价c1c2…cn解：设xj为购买食品Bj的数量(j=1,2,…,n)（i=1,2,…,m）xj≥0（j=1,2,…,n）0≤xj≤lj§1线性规划问题及其数学模型三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成n个子系统处理。1、决策变量xj≥02、约束条件——一组决策变量的线性等式或不等式3、目标函数——决策变量的线性函数第一章线性规划及单纯形法max（min）z=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤（或=，≥）b1a21x1+a
5、22x2+…+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、除决策变量的非负约束
6、外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负。第一章线性规划及单纯形法如何转化为标准形式？1、目标函数为求极小值，即为：。因为求minz等价于求max(-z)，令z’=-z，即化为：2、约束条件为不等式，xn+1≥0松弛变量如何处理？§1线性规划问题及其数学模型３、右端项bi<0时，只需将等式两端同乘（-1）则右端项必大于零4、决策变量无非负约束设xj没有非负约束，若xj≤0，可令xj=-xj’，则xj’≥0；又若xj为自由变量，即xj可为任意实数，可令xj=xj’-xj’’，且xj’,xj’’≥0第一章线性规划及单纯形法e.g.3试将LP问题mi
7、nz=-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线性规划问题及其数
