线性规划数学模型.ppt

第三章 线性规划 线性规划（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确定性：只能应用于确定型决策问题。 5 A B 备用资源 煤 1 2 30 劳动日 3 2 60 仓库 0 2 24 利润 40 50 例1、生产计划问题 A, B各生产多少, 可获最大利润? 6 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0 max Z= 40x1 +50x2 解:设产品A, B产量分别为变量x1 ， x2 7 例2 求：最低成本的原料混合方案 原料 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 素最低含量 8 解：设每单位添加剂中原料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) 9 一般式 Max(min)Z=C1X1+ C2X2+CnXn a11X1+ a12X2+ a1nXn (=, )b1 a21X1+ a22X2+ a2nXn (=, )b2 am1X1+ am2X2+ amnXn (=, )bm Xj 0(j=1,n) 10 要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件 11 图解法 AX=b (1) X 0 (2) maxZ=CX (3) 定义1：满足约束(1)、(2)的X=(X1 Xn)T称为 LP问题的可行解，全部可行解的集合称为可行 域。 定义2：满足(3)的可行解称为LP问题的最优解 12 例1、maxZ=40X1+ 50X2 X1+2X2 30 3X1+2X2 60 2X2 24 X1 , X2 0 13 解：(1)、确定可行域 X1 0 X1 =0 (纵) X2 0 X2=0 (横) X1+2X2 30 X1+2X2 =30 (0,15) (30,0) 203010 0 10 20 30 X2 D A B C 3X1+2X2 =60 (0,30) (20,0) 2X2 =24 14 (2)、求最优解 解：X* = (15,7.5) Zmax =975 Z=40X1+50X2 0=40X1+50X2 (0,0)， (10,-8) C点： X1+2X2 =30 3X1+2X2 =60 0 203010 10 20 30 X1 X2 D A B C 15 例2、 maxZ=40X1+ 80X2 X1+2X2 30 3X1+2X2 60 2X2 24 X1 , X2 0 16 0 Z= 40 X1 + 80X2 =0 X1 + 2X2 =30 D AB C X2 X1 最优解：BC线段 B点 C点 X(1)=(6,12) X(2)=(15,7.5) X= X(1)+(1-) X(2) (0 1) 求解 17 X1 =6+ +(1- )15 X2=12+ +(1- )7.5 X1 =15-9 X2 =7.5+4.5 (0 1) X= = +(1- ) maxZ=1200 X1 6 15 X2 12 7.5 18 无界 无有限最优解 例3、 maxZ=2X1+ 4X2 2X1+X2 8 -2X1+X2 2 X1 , X2 0 Z=0 2X1+ X2=8 -2X1+ X2=2 8 2 4 6 X2 4 0 X1 19 例4、 maxZ=3X1+2X2 -X1 -X2 1 X1 , X2 0 无解 无可行解 -1 X2 -1 X1 0 20 总结 唯一解 无穷多解 无有限最优解 无可行解 有解 无解 21 单纯形法 单纯形法（Simplex Method）是美国数学 家但泽（Dantzig）于1947年提出的。基 本思想是通过有限次的换基迭代来求出 线性规划的最优解。 22 两个变量的LP问题的解： 可行域为凸多边形（凸集） X(1) X(2) 凸多边形 凹多边形 X(1) X(2) 23 顶点原理 v顶点（极点） 凸集中满足一下条件的点：凸集中通过任意两 个点的直线上都不包含此点作为内点，它只能是凸集 的端点。 v顶点原理 由于线性规划问题的可行域都是凸集，如果 存在最优解，必然对应于可行域凸集的至少一个顶点 ；如果只有一个最优解，它必然对应于一个顶点；如 果存在多个最优解，它们必然相邻。 24 顶点原理的运用 顶点原理证明，如果线性规划的最优解 存在，要找到最优解，只要找到可行域 凸集顶点的坐标，将其代入目标函数， 使得目标函数值最大的点就是最优解。 考察例1的情形。 25 单纯形法的指导思想是，不需要考察和计算所 有顶点，如存在最优解，可以任意顶点为起点 ，求出初始解，然后转到相邻顶点，看目标函 数值是否有改善。 利用单纯形法解决线性规划问题，实际上是从 线性规划问题的一个基本可行解转移到另一个 基本可行解，同时目标函数值不减少的过程。 对于两个变量的线性规划问题，就是从可行域 的一个端点转移到另一个端点，而使得目标函 数的值不减少。 26 线性规划的扩展 一、整数规划（整数线性规划）：部分或 全部的决策变量只能取整数值。 例1转变成整数规划情形 27 二、01规划： 变量的取值被限定为0或1，可以看成 是整数规划的扩展。 例2：某市拟建设若干公共图书馆，经过调 研得到相关数据如下表。现财政预算不超过2 亿元