第三章：线性规划数学模型

第三章 线性规划 线性规划（ Linear Programming,LP） 是运筹学中研究较早、理论成熟的重要分支之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的。 在公共管理和工商管理中都有广泛的应用。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。 公共交通、垃圾清理、提供服务成本最小问题；救灾抢险、消防灭火、制止犯罪的最快反应问题；控制污染、能源规划、经济布局的最优化问题，等等。1 冯 诺伊曼 (Von Neuman)和摩根斯坦(Morgenstern)1944年发表的 对策论与经济行为 涉及与线性规划等价的对策问题及线性规划对偶理论 从 1964年诺贝尔奖设经济学奖后，到1992年 28年间的 32名获奖者中有 13人(40%) 从事过与线性规划有关的研究工作，其中比较著名的还有 Simon，Samullson， Leontief， Arrow， Miller等2研究对象 有一定的人力、财力、资源条件下，如何合理安排使用，效益最高 某项任务确定后，如何安排人、财、物，使之最省3线性规划模型 是 通过对实际问题的分析而建立的表示决策变量、最有目标和约束条件之间关系的一组数学关系式，由决策变量、目标函数和约束条件三部分组成。 在满足一组约束条件下，求一组决策变量的值，使目标函数达到最优。4线性规划的特点v决策变量连续性：求解出的决策变量值可以是整数、小数；v线性函数：目标函数方程和约束条件方程都是线性方程；v单目标：目标函数是单目标，只有一个极大值或一个极小值；v确定性：只能应用于确定型决策问题。5A B 备用资源煤 1 2 30劳动日 3 2 60仓库 0 2 24利润 40 50例 1、生产计划问题A, B各生产多少 , 可获最大利润 ?6x1 + 2x2 30 3x1 + 2x2 602x2 24x1， x2 0max Z= 40x1 +50x2解 :设产品 A, B产量分别为变量 x1 ， x27例 2求：最低成本的原料混合方案原料 A B 每单位成本1 4 1 0 22 6 1 2 5 3 1 7 1 64 2 5 3 8每单位添加剂中维生 12 14 8 素最低含量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+ a 1nXn (=, )b1a21X1+ a22X2+ a 2nXn (=, )b2 am1X1+ am2X2+ amnXn (=, )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+ 50X2 X1+2X2 303X1+2X2 602X2 24X1 , X2 014解： (1)、确定可行域 X1 0 X1 =0 (纵 ) X2 0 X2=0 (横 ) X1+2X2 30X1+2X2 =30(0,15) (30,0)20 30100102030X2DA BC3X1+2X2 =60(0,30) (20,0) 2X2 =24 15(2)、求最优解解： X* = (15,7.5)Zmax =975Z=40X1+50X20=40X1+50X2 (0,0)， (10,-8)C点： X1+2X2 =30 3X1+2X2 =600 20 3010102030X1X2DA BC16例 2、 maxZ=40X1+ 80X2 X1+2X2 303X1+2X2 602X2 24X1 , X2 0170Z= 40 X1 + 80X2 =0 X1 + 2X2 =30DA B 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-9X2 =7.5+4.5 (0 1)X= = +(1- )maxZ=1200 X1 6 15X2 12 7.519无界无有限最优解例 3、 maxZ=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0Z=0 2X1+ X2=8-2X1+ X2=28246X240 X120例 4、 maxZ=3X1+2X2 -X1 -X2 1X1 , X2 0无解无可行解-1X2-1 X1021总结唯一解无穷多解无有限最优解无可行解有解无解22单纯形法 单纯形法（ Simplex Method） 是美国数学家但泽（ Dantzig） 于 1947年提出的。基本思想是通过有限次的换基迭代来求出线性规划的最优解。23两个变量的 LP问题的解：可行域为凸多边形（凸集）X(1)X(2)凸多边形 凹多边形X(1)X(2)24顶点原理v顶点（极点）凸集中满足一下条件的点：凸集中通过任意两个点的直线上都不包含此点作为内点，它只能是凸集的端点。v顶点原理由于线性规划问题的可行域都是凸集，如果存在最优解，必然对应于可行域凸集的至少一个顶点；如果只有一个最优解，它必然对应于一个顶点；如果存在多个最优解，它们必然相邻。25顶点原理的运用 顶点原理证明，如果线性规划的最优解存在，要找到最优解，只要找到可行域凸集顶点的坐标，将其代入目标函数，使得目标函数值最大的点就是最优解。 考察 例 1的情形。26 单纯形法的指导思想是，不需要考察和计算所有顶点，如存在最优解，可以任意顶点为起点，求出初始解，然后转到相邻顶点，看目标函数值是否有改善。 利用单纯形法解决线性规划问题，实际上是从线性规划问题的一个基本可行解转移到另一个基本可行解，同时目标函数值不减少的过程。 对于两个变量的线性规划问题，就是从可行域的一个端点转移到另一个端点，而使得目标函数的值不减少。27线性规划的扩展一、 整数规划 （整数线性规划）：部分或全部的决策变量只能取整数值。 例：某饮料公司要推出一个广告活动，现有几种广告形式，各广告的成本及估计受众数量如下表，为尽可能扩大广告的传播效果，他们想尽量增加各种广告形式的出现次数。若本次活动的预算为30000元，请写出模型并求解28二、 0 1规划 ：变量的取值被限定为 0或