线性规划数学模型

1,第三章线性规划,线性规划（LinearProgramming,LP）是运筹学中研究较早、理论成熟的重要分支之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。在公共管理和工商管理中都有广泛的应用。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。公共交通、垃圾清理、提供服务成本最小问题；救灾抢险、消防灭火、制止犯罪的最快反应问题；控制污染、能源规划、经济布局的最优化问题，等等。,2,冯诺伊曼(VonNeuman)和摩根斯坦(Morgenstern)1944年发表的博弈论与经济行为涉及与线性规划等价的对策问题及线性规划对偶理论从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中比较著名的还有Simon，Samullson，Leontief，Arrow，Miller等,3,研究对象,有一定的人力、财力、资源条件下，如何合理安排使用，效益最高某项任务确定后，如何安排人、财、物，使之最省,4,线性规划模型,是通过对实际问题的分析而建立的表示决策变量、最优目标和约束条件之间关系的一组数学关系式，由决策变量、目标函数和约束条件三部分组成。在满足一组约束条件下，求一组决策变量的值，使目标函数达到最优。,5,线性规划的特点,决策变量连续性：求解出的决策变量值可以是整数、小数；线性函数：目标函数方程和约束条件方程都是线性方程；单目标：目标函数是单目标，只有一个极大值或一个极小值；确定性：只能应用于确定型决策问题。,6,例1、生产计划问题,A,B各生产多少,可获最大利润?,7,maxZ=40 x1+50 x2,解:设产品A,B产量分别为变量x1，x2,8,例2,求：最低成本的原料混合方案,9,解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4),minZ=2x1+5x2+6x3+8x4,10,一般式,Max(min)Z=C1X1+C2X2+CnXn,11,要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件,12,图解法,定义1：满足约束(1)、(2)的X=(X1Xn)T称为LP问题的可行解，全部可行解的集合称为可行域。,定义2：满足(3)的可行解称为LP问题的最优解,13,例1、maxZ=40X1+50X2,14,解：(1)、确定可行域X10X1=0(纵)X20X2=0(横),X1+2X230X1+2X2=30(0,15)(30,0),3X1+2X2=60(0,30)(20,0),2X2=24,15,(2)、求最优解,解：X*=(15,7.5)Zmax=975,16,17,0,最优解：BC线段B点C点X(1)=(6,12)X(2)=(15,7.5)X=X(1)+(1-)X(2)(01),求解,18,19,无界无有限最优解,20,无解无可行解,0,21,总结,22,单纯形法,单纯形法（SimplexMethod）是美国数学家但泽（Dantzig）于1947年提出的。基本思想是通过有限次的换基迭代来求出线性规划的最优解。,23,两个变量的LP问题的解：,可行域为凸多边形（凸集）,24,顶点原理,顶点（极点）凸集中满足一下条件的点：凸集中通过任意两个点的直线上都不包含此点作为内点，它只能是凸集的端点。顶点原理由于线性规划问题的可行域都是凸集，如果存在最优解，必然对应于可行域凸集的至少一个顶点；如果只有一个最优解，它必然对应于一个顶点；如果存在多个最优解，它们必然相邻。,25,顶点原理的运用,顶点原理证明，如果线性规划的最优解存在，要找到最优解，只要找到可行域凸集顶点的坐标，将其代入目标函数，使得目标函数值最大的点就是最优解。考察例1的情形。,26,单纯形法的指导思想是，不需要考察和计算所有顶点，如存在最优解，可以任意顶点为起点，求出初始解，然后转到相邻顶点，看目标函数值是否有改善。利用单纯形法解决线性规划问题，实际上是从线性规划问题的一个基本可行解转移到另一个基本可行解，同时目标函数值不减少的过程。对于两个变量的线性规划问题，就是从可行域的一个端点转移到另一个端点，而使得目标函数的值不减少。,27,线性规划的扩展,一、整数规划（整数线性规划）：部分或全部的决策变量只能取整数值。例1转变成整数规划情形,28,二、01规划：变量的取值被限定为0或1，可以看成是整数规划