《线性规划数学模型》PPT课件

《《线性规划数学模型》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性规划线性规划（LinearProgramming,LP）是运筹学中研究较早、理论成熟的重要分支之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的。在公共管理和工商管理中都有广泛的应用。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。公共交通、垃圾清理、提供服务成本最小问题；救灾抢险、消防灭火、制止犯罪的最快反应问题；控制污染、能源规划、经济布局的最优化问题，等等。1冯•诺伊曼(VonNeuman)和摩根斯坦(Morgenstern)1944年发表的《对策论与经济行为》涉及与线

2、性规划等价的对策问题及线性规划对偶理论从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中比较著名的还有Simon，Samullson，Leontief，Arrow，Miller等2研究对象有一定的人力、财力、资源条件下，如何合理安排使用，效益最高某项任务确定后，如何安排人、财、物，使之最省3线性规划模型是通过对实际问题的分析而建立的表示决策变量、最有目标和约束条件之间关系的一组数学关系式，由决策变量、目标函数和约束条件三部分组成。在满足一组约束条件

3、下，求一组决策变量的值，使目标函数达到最优。4线性规划的特点决策变量连续性：求解出的决策变量值可以是整数、小数；线性函数：目标函数方程和约束条件方程都是线性方程；单目标：目标函数是单目标，只有一个极大值或一个极小值；确定性：只能应用于确定型决策问题。5AB备用资源煤1230劳动日3260仓库0224利润4050例1、生产计划问题A,B各生产多少,可获最大利润?6x1+2x2303x1+2x2602x224x1，x20maxZ=40x1+50x2解:设产品A,B产量分别为变量x1，x27例2求：最低成本的原料混合方

4、案原料ABＣ每单位成本14102261253171642538每单位添加剂中维生12148素最低含量8解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4)minZ=2x1+5x2+6x3+8x44x1+6x2+x3+2x412x1+x2+7x3+5x4142x2+x3+3x48xi0(i=1,…,4)9一般式Max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn(=,)b2………am1X1+am2X2+…+amn

5、Xn(=,)bmXj0(j=1,…,n)1011要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件12图解法AX=b(1)X0(2)maxZ=CX(3)定义1：满足约束(1)、(2)的X=(X1…Xn)T称为LP问题的可行解，全部可行解的集合称为可行域。定义2：满足(3)的可行解称为LP问题的最优解13例1、maxZ=40X1+50X2X1+2X2303X1+2X2602X224X1,X2014解：(1)、确定可行域X10X1=0(纵)X20X2=0(横)X1

6、+2X230X1+2X2=30(0,15)(30,0)2030100102030X2DABC3X1+2X2=60(0,30)(20,0)2X2=2415(2)、求最优解解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C点：X1+2X2=303X1+2X2=600203010102030X1X2DABC16例2、maxZ=40X1+80X2X1+2X2303X1+2X2602X224X1,X20170Z=40X1+80X2=0X1+2X2=30DAB

7、CX2X1最优解：BC线段B点C点X(1)=(6,12)X(2)=(15,7.5)X=X(1)+(1-)X(2)(01)求解18X1=6++(1-)·15X2=12++(1-)·7.5X1=15-9X2=7.5+4.5(01)X==+(1-)maxZ=1200X1615X2127.519无界无有限最优解例3、maxZ=2X1+4X22X1+X28-2X1+X22X1,X20Z=02X1+X2=8-2X1+X2=28246X240X120例4、maxZ=3X1+2X2-X1-X21X

8、1,X20无解无可行解-1X2-1X1021总结唯一解无穷多解无有限最优解无可行解有解无解22单纯形法单纯形法（SimplexMethod）是美国数学家但泽（Dantzig）于1947年提出的。基本思想是通过有限次的换基迭代来求出线性规划的最优解。23两个变量的LP问题的解：可行域为凸多边形（凸集）X(1)X(2)