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

《《线性规划数学模型》PPT课件》由会员分享，可在线阅读，更多相关《《线性规划数学模型》PPT课件（30页珍藏版）》请在装配图网上搜索。

1、1第三章第三章 线性规划线性规划 线性规划（线性规划（Linear Programming,LP）是运筹）是运筹学中研究较早、理论成熟的重要分支之一，网学中研究较早、理论成熟的重要分支之一，网络规划，整数规划，目标规划和多目标规划都络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的。是以线性规划为基础的。在公共管理和工商管理中都有广泛的应用。解在公共管理和工商管理中都有广泛的应用。解决稀缺资源最优分配的有效方法，使付出的费决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。用最小或获得的收益最大。公共交通、垃圾清理、提供服务成本最小问题；公共交通、垃圾清理、提供服务成本最

2、小问题；救灾抢险、消防灭火、制止犯罪的最快反应问救灾抢险、消防灭火、制止犯罪的最快反应问题；控制污染、能源规划、经济布局的最优化题；控制污染、能源规划、经济布局的最优化问题，等等。问题，等等。2 冯冯诺伊曼诺伊曼(Von Neuman)和摩根斯坦和摩根斯坦(Morgenstern)1944年发表的年发表的 对策论与对策论与经济行为经济行为涉及与线性规划等价的对策涉及与线性规划等价的对策问题及线性规划对偶理论问题及线性规划对偶理论 从从1964年诺贝尔奖设经济学奖后，到年诺贝尔奖设经济学奖后，到1992年年28年间的年间的32名获奖者中有名获奖者中有13人人(40%)从事过与线性规划有关的研究工

3、作，从事过与线性规划有关的研究工作，其中比较著名的还有其中比较著名的还有Simon，Samullson，Leontief，Arrow，Miller等等3研究对象研究对象 有一定的人力、财力、资源条件下，如有一定的人力、财力、资源条件下，如何合理安排使用，效益最高何合理安排使用，效益最高 某项任务确定后，如何安排人、财、物，某项任务确定后，如何安排人、财、物，使之最省使之最省4线性规划模型 是通过对实际问题的分析而建立的表示决策变量、最有目标和约束条件之间关系的一组数学关系式，由决策变量、目标函数和约束条件三部分组成。在满足一组约束条件下，求一组决策变量的值，使目标函数达到最优。5线性规划的特点

4、v决策变量连续性：求解出的决策变量值可以是整数、小数；v线性函数：目标函数方程和约束条件方程都是线性方程；v单目标：目标函数是单目标，只有一个极大值或一个极小值；v确定性：只能应用于确定型决策问题。6 A B 备用资源备用资源 煤煤 1 2 30 劳动日劳动日 3 2 60 仓库仓库 0 2 24 利润利润 40 50例例1、生产计划问题、生产计划问题A,B各生产多少各生产多少,可获最大利润可获最大利润?7 x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0 max Z=40 x1+50 x2解解:设产品设产品A,B产量分别为变量产量分别为变量x1，x28例例2求：最低成本

5、的原料混合方案求：最低成本的原料混合方案 原料原料 A B 每单位成本每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每单位添每单位添 加剂中维生加剂中维生 12 14 8 素最低含量素最低含量9解：设每单位添加剂中原料解：设每单位添加剂中原料i的用量为的用量为xi(i=1,2,3,4)minZ=2x1+5x2+6x3+8x4 4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 xi 0(i=1,4)10一般式一般式Max(min)Z=C1X1+C2X2+CnXna11X1+a12X2+a1nXn (=,(

6、=,)b)b1 1a21X1+a22X2+a2nXn (=,(=,)b)b2 2 am1X1+am2X2+amnXn (=,(=,)b)bm mXj j 0(0(j=1,n)11njjjXCZ1max(min),2,1(0),2,1(1njXmibXajinjjij12 要解决的问题的目标可以用数值指标反映要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择对于要实现的目标有多种方案可选择 有影响决策的若干约束条件有影响决策的若干约束条件13 图解法图解法AX=b (1)X 0 (2)maxZ=CX (3)定义定义1 1：满足约束：满足约束(1)、(2)的的X=(X1 Xn)

7、T称为称为LP问题的可行解，全部可行解的集合称为可问题的可行解，全部可行解的集合称为可行域。行域。定义定义2 2：满足：满足(3)的可行解称为的可行解称为LP问题的最优解问题的最优解14例例1、maxZ=40X1+50X2 X1+2X2 303X1+2X2 60 2X2 24 X1,X2 0 015解：解：(1)、确定可行域、确定可行域 X1 0 0 X1=0=0(纵纵)X2 0 0 X2=0=0(横横)X1+2X2 30 X1+2X2=30 (0,15)(30,0)2030100102030X2DABC3X1+2X2=60(0,30)(20,0)2X2=2416(2)、求最优解、求最优解解：

8、解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2 (0,0)，(10,-8)C点：点：X1+2X2=30 3X1+2X2=600203010102030X1X2DABC17例例2、maxZ=40X1+80X2 X1+2X2 303X1+2X2 60 2X2 24 X1,X2 0 0180Z=40 X1+80X2=0 X1+2X2=30DABCX2X1最优解：最优解：BC线段线段B点点 C点点X(1)=(6,12)X(2)=(15,7.5)X=X(1)+(1-)X(2)(0 1)求解求解19X1=6+(1-)15X2=12+(1-)7.5X1=15-9 X2

9、=7.5+4.5 (0 1)X=+(1-)maxZ=1200 X1 6 15 X2 12 7.520无界无界无有限最优解无有限最优解例例3、maxZ=2X1+4X2 2X1+X2 8 8-2X1+X2 2X1,X2 0 0Z=02X1+X2=8-2X1+X2=28246X240X121例例4、maxZ=3X1+2X2-X1-X2 1 1X1,X2 0 0无解无解无可行解无可行解-1X2-1X1022总结总结 唯一解唯一解 无穷多解无穷多解 无有限最优解无有限最优解 无可行解无可行解有解有解无解无解23单纯形法 单纯形法（Simplex Method）是美国数学家但泽（Dantzig）于1947

10、年提出的。基本思想是通过有限次的换基迭代来求出线性规划的最优解。24两个变量的两个变量的LP问题的解：问题的解：可行域为凸多边形（凸集）可行域为凸多边形（凸集）X(1)X(2)凸多边形凸多边形凹多边形凹多边形X(1)X(2)25顶点原理v顶点（极点）凸集中满足一下条件的点：凸集中通过任意两个点的直线上都不包含此点作为内点，它只能是凸集的端点。v顶点原理 由于线性规划问题的可行域都是凸集，如果存在最优解，必然对应于可行域凸集的至少一个顶点；如果只有一个最优解，它必然对应于一个顶点；如果存在多个最优解，它们必然相邻。26顶点原理的运用 顶点原理证明，如果线性规划的最优解存在，要找到最优解，只要找到

11、可行域凸集顶点的坐标，将其代入目标函数，使得目标函数值最大的点就是最优解。考察例1的情形。27 单纯形法的指导思想是，不需要考察和计算所有顶点，如存在最优解，可以任意顶点为起点，求出初始解，然后转到相邻顶点，看目标函数值是否有改善。利用单纯形法解决线性规划问题，实际上是从线性规划问题的一个基本可行解转移到另一个基本可行解，同时目标函数值不减少的过程。对于两个变量的线性规划问题，就是从可行域的一个端点转移到另一个端点，而使得目标函数的值不减少。28线性规划的扩展一、整数规划（整数线性规划）：部分或全部的决策变量只能取整数值。例：某饮料公司要推出一个广告活动，现有几种广告形式，各广告的成本及估计受众数量如下表，为尽可能扩大广告的传播效果，他们想尽量增加各种广告形式的出现次数。若本次活动的预算为30000元，请写出模型并求解29二、01规划：变量的取值被限定为0或1，可以看成是整数规划的扩展。例：（刘武教材P211练习题第二题）30三、动态规划 没有标准的模型，没有唯一确定的解法，将问题分解为若干阶段例：有12个小球，其中有且仅有一个的质量与其他11个球不同（可能轻也可能重），现有一个无刻度的天平，请用最少的称量次数找出该质量不同的小球。