（精选）1第一章 线性规划及单纯形法.ppt

第一章线性规划及单纯形法 1 线性规划介绍2 线性规划数学模型3 线性规划标准形式4 线性规划的图解法5 线性规划基本概念6 单纯形法7 应用举例 1 1 线性规划介绍 历史悠久 理论成熟 应用广泛运筹学的最基本的方法之一 网络规划 整数规划 目标规划和多目标规划都是以线性规划为基础的 解决稀缺资源最优分配的有效方法 使付出的费用最小或获得的收益最大 2 线性规划理论的发展 1939年前苏联康托洛维奇 KOHTOPOBUZ 生产组织与计划中的数学方法 提出 解乘数法 1 线性规划介绍 3 美国科学院院士DANTZIG 丹齐克 1948年在研究美国空军资源的优化配置时提出线性规划及其通用解法 单纯形法 被称为线性规划之父 1 线性规划介绍 线性规划之父的Dantzig 丹齐克 据说 一次上课 Dantzig迟到了 仰头看去 黑板上留了几个几个题目 他就抄了一下 回家后埋头苦做 几个星期之后 疲惫的去找老师说 这件事情真的对不起 作业好像太难了 我所以现在才交 言下很是惭愧 几天之后 他的老师就把他召了过去 兴奋的告诉他说他太兴奋了 Dantzig很不解 后来才知道原来黑板上的题目根本就不是什么家庭作业 而是老师说的本领域的未解决的问题 他给出的那个解法也就是单纯形法 这个方法是上个世纪前十位的算法 4 1 线性规划介绍 1960年 最佳资源利用的经济计算 康托洛维奇和库伯曼斯 Koopmans 两人因对资源最优分配理论的贡献而获1975年诺贝尔经济学奖 5 1961年 查恩斯与库伯提出了目标规划 艾吉利提出了用优先因子来处理多目标问题 20世纪70年代 斯 姆 李与杰斯开莱尼应用计算机处理目标规划问题 计算机50约束100变量30000约束3000000变量 1 线性规划介绍 6 从1964年诺贝尔奖设经济学奖后 到1992年28年间的32名获奖者中有13人 40 从事过与线性规划有关的研究工作 其中著名的有Simon Samullson Leontief Arrow Miller等 1 线性规划介绍 保罗 萨缪尔逊 PAULASAMUELSON 他发展了数理和动态经济理论 将经济科学提高到新的水平 他的研究涉及经济学的全部领域 于1970年获得诺贝尔经济学奖 华西里 列昂惕夫 WASSILYLEONTIEF 美国人 他发展了投入产出方法 该方法在许多重要的经济问题中得到运用 曾获1973年诺贝尔经济科学奖 肯尼斯 J 阿罗 KENNETHJ ARROW 美国人 因与约翰 希克斯 JOHNR HICKS 共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖 牟顿 米勒 MERTONM MILLER 1923 2000 美国人 由于他在金融经济学方面做出了开创性工作 于1990年获得诺贝尔经济奖 7 1 线性规划介绍 线性规划研究的主要问题 有一定的人力 财力 资源条件下 如何合理安排使用 效益最高 某项任务确定后 如何安排人 财 物 使之最省 8 例1美佳公司计划制造I II两种家电产品 已知各制造一件时分别占用的设备A B的台时 调试时间及A B设备和调试工序每天可用于这两种家电的能力 各售出一件时的获利情况如表I l所示 问该公司应制造A B两种家电各多少件 使获取的利润为最大 2 线性规划数学模型 9 例2捷运公司拟在下一年度的1 4月的4个月内需租用仓库堆放物资 已知各月份所需仓库面积数列见下表 仓库租借费用随合同期定 期限越长折扣越大 具体数字见下表 租借仓库的合同每月初都可办理 每份台同具体现定租用面积数和期限 因此该厂可根据需要 在任何一个月初办理租借台同 每次办理时可签一份 也可签若干份租用面积和租借期限不同的合同 试确定该公司签订租借合同的最优决策 目的是使所付租借费用最小 2 线性规划数学模型 10 目标函数 约束条件 解 用变量x1和x2分别表示美佳公司制造家电I和II的数量 例1 用数学语言描述 2 线性规划数学模型 11 解 设变量xij表示捷运公司在第i i 1 4 个月初签订的租借期为j j 1 4 个月的仓库面积的合同 单位为100m2 约束条件 目标函数 例2 2 线性规划数学模型 12 求 最大利润的生产计划 练习1生产计划问题 2 线性规划数学模型 13 maxZ 40 x1 50 x2 解 设产品A B产量分别为变量x1 x2 2 线性规划数学模型 14 求 最低成本的原料混合方案 练习2混合配料问题 2 线性规划数学模型 15 解 设每单位添加剂中原料i的用量为xi i 1 2 3 4 minZ 2x1 5x2 6x3 8x4 2 线性规划数学模型 16 决策变量 向量 x1 xn T决策人要考虑和控制的因素 非负约束条件 线性等式或不等式目标函数 Z x1 xn 线性式 求Z极大或极小 线性规划模型特点 2 线性规划数学模型 17 如果规划问题的数学模型中 决策变量的取值可以是连续的 目标函数是决策变量的线性函数 约束条件是含决策变量的线性等式或不等式 则该类规划问题的数学模型称为线性规划的数学模型 实际问题中线性的含义 一是严格的比例性 如生产某产品对资源的消耗量和可获取的利润 同其生产数量严格成比例 二是可叠加性 如生产多种产品时对某项资源的消耗量应等于各产品对该项资源的消耗量之和 2 线性规划数学模型 18 19 max min Z c1x1 c2x2 cnxn n个变量 价值系数 第i种资源的拥有量 技术系数或工艺系数 线性规划的一般式 2 线性规划数学模型 线性规划的简写式 2 线性规划数学模型 20 线性规划的向量表示式 2 线性规划数学模型 21 线性规划的矩阵表示式 2 线性规划数学模型 22 比例性 决策变量变化引起目标的改变量与决策变量改变量成正比 可加性 每个决策变量对目标和约束的影响独立于其它变量 连续性 每个决策变量取连续值 确定性 线性规划中的参数aij bi ci为确定值 隐含的假设 2 线性规划数学模型 23 练习3运输问题工厂需要的原棉存放在三个仓库中 现将原棉运往工厂以满足工厂生产的需求 已知原棉运到各个工厂的单位运费如表所示 问使总运费最小的运输方案 2 线性规划数学模型 24 解 设xij为i仓库运到j工厂的原棉数量 i 1 2 3j 1 2 3 minZ 2x11 x12 3x13 2x21 2x22 4x23 3x31 4x32 2x33 2 线性规划数学模型 25 练习4连续投资10万元A 从第1年到第4年每年初投资 次年末回收本利1 15 B 第3年初投资 到第5年末回收本利1 25 最大投资4万元 C 第2年初投资 到第5年末回收本利1 40 最大投资3万元 D 每年初投资 每年末回收本利1 11 求 使5年末总资本最大的投资方案 分析 2 线性规划数学模型 26 解 xik i 1 2 5 k A B C D 为第i年初投资到第k个项目的资金数 MaxZ 1 15x4A 1 40 x2C 1 25x3B 1 11x5D 2 线性规划数学模型 27 线性规划问题应用市场营销 广告预算和媒介选择 竞争性定价 新产品开发 制定销售计划 生产计划制定 合理下料 配料 生产计划 库存 劳力综合 库存管理 合理物资库存量 停车场大小 设备容量 运输问题财政 会计 预算 贷款 成本分析 投资 证券管理 人事 人员分配 人才评价 工资和奖金的确定 设备管理 维修计划 设备更新 城市管理 供水 污水管理 服务系统设计 运用 2 线性规划数学模型 28 线性规划的适用情况要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件 2 线性规划数学模型 29 线性规划模型的结构目标函数 max min约束条件 变量符号 0 0 线性规划的标准形式目标函数 max约束条件 变量符号 0 3 线性规划标准形式 30 标准型的一般型 maxZ c1x1 c2x2 cnxn 其中bi 0 i 1 2 m 3 线性规划标准形式 31 C C1C2 Cn 标准型的矩阵型 3 线性规划标准形式 32 P1x1 P2x2 Pnxn b 标准型的向量型 3 线性规划标准形式 33 线性规划问题化标准型 1 约束条件 2 变量 3 目标函数 4 右端常数 3 线性规划标准形式 34 1 约束条件 x3为松弛变量 x4为剩余变量 松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数 均未转化为价值和利润 所以引进模型后它们在目标函数中的系数均为零 当约束条件为 时 当约束条件为 时 3 线性规划标准形式 35 3 线性规划标准形式 转化为 maxZ 40X1 50X2 0 X3 0 X4 0 X5 例 maxZ 40 x1 50 x2 松弛变量 36 3 线性规划标准形式 例 剩余变量 37 2 变量 1 x 0的情况 令x1 x1 x1 2 x取值无约束的情况 令x x 令x x x 3 线性规划标准形式 38 3 x两边有约束的情况 6 6 x1 6 10 6令x1 x1 60 x1 16 3 线性规划标准形式 39 3 目标函数 令Z Z 3 线性规划标准形式 40 4 右端常数 右端项b 0时 只需将等式或不等式两端同乘 一1 则等式右端项必大于零 3 线性规划标准形式 41 例3 将minZ x1 2x2 3x3 化为标准型 3 线性规划标准形式 42 解 令x3 x4 x5 加松弛变量x6 加剩余变量x7 令Z Z maxZ x1 2x2 3x4 3x5 3 线性规划标准形式 43 1 minZ 2x1 x2 2x3 练习5将下列线性规划问题化成标准型 2 maxZ 2x1 x2 3x3 x4 3 线性规划标准形式 44 3 minZ 2x1 3x2 5x3 4 maxZ x1 3x2 3 线性规划标准形式 45 作业 课本P441 2 3 线性规划标准形式 46 定义1 满足约束 1 2 的x x1 xn T称为LP问题的可行解 全部可行解的集合称为可行域 定义2 满足 3 的可行解称为LP问题的最优解 线性规划的标准型 4 线性规划的图解法 47 图解法求解的目的 一是判别线性规划问题的求解结局 二是在存在最优解的条件下 把问题的最优解找出来 4 线性规划的图解法 48 图解法的步骤 1 在平面上建立直角坐标系 2 图示约束条件 找出可行域 3 图示目标函数和寻找最优解 4 线性规划的图解法 49 例4maxZ 40 x1 50 x2 4 线性规划的图解法 50 解 1 确定可行域x1 0 x1 0 纵 x2 0 x2 0 横 x1 2x2 30 x1 2x2 30 0 15 30 0 3x1 2x2 60 0 30 20 0 2x2 24 4 线性规划的图解法 51 2 求最优解 最优解 x 15 7 5 Zmax 975 Z 40 x1 50 x20 40 x1 50 x2 0 0 10 8 4 线性规划的图解法 52 解 最优解 BC线段B点C点x 1 6 12 x 2 15 7 5 x x 1 1 x 2 0 1 4 线性规划的图解法 53 4 线性规划的图解法 54 无界解无有限最优解 4 线性规划的图解法 55 无解无可行解 4 线性规划的图解法 56 当目标函数的直线族与某约束条件平行 且该问题有解时 约束条件无公共区域 有解但可行域可伸展到无穷时 总结 4 线性规划的图解法 57 由图解法得到的启示 1 线性规划问题的解的情况有四种 唯一最优解 无穷多最优解 无界解 无可行解 2 若线性规划可行域存在 则可行域是一个凸集 3 若有最优解 定可在可行域的顶点得到 4 解题思路是找出凸集的各顶点的最大目标函数值 4 线性规划的图解法 58 作业 用图解法解以下问题 maxZ 5x1 6x2 4 线性规划的图解法 59 一 线性规划问题的解的概念 5 线性规划基本概念 60 定义1 基 基阵 设A为约束方程组的m n阶系数矩阵设 n m 其秩为m B是矩阵A中的一个m m阶的满秩子矩阵 称B是线性规划问题的一个基 B 5 线性规划基本概念 61 B中的每一个列向量Pj称为基向量 与基向量对应的变量称为基变量 其他变量称为非基变量 5 线性规划基本概念 62 Ax b的求解 BxB NxN bBxB b NxNxB B 1b B 1NxN A BN x xBxN T 若B为单位矩阵xB b NxN若xN 0 xB B 1b 5 线性规划基本概念 63 定义2 可行解 满足方程约束条件的解x x1 x2 xn T 称为线性规划问题的可行解 全部可行解的集合称为可行域 定义3 最优解 使目标函数达到最大值的可行解 称为最优解 5 线性规划基本概念 64 基本解中最多有m个非零分量 定义6 可行基 对应于基可行解的基称为可行基 5 线性规划基本概念 65 5 线性规划基本概念 66 B P3P4P5 I是满秩子矩阵非基N P1P2 5 线性规划基本概念 67 令x1 x2 0 x3 30 x4 60 x5 24 5 线性规划基本概念 68 求出基变量是x1 x3 x4的基本解 是不是可行解 5 线性规划基本概念 69 5 线性规划基本概念 70 x 1 0 3 2 3 2 T是 5 线性规划基本概念 71 凸集 D是n维空间的一个集合 x 1 x 2 D 若对任何x 1 x 2 有x x 1 1 x 2 D 0 1 则D为凸集 定义1 凸集 如果集合D中任意两个点 其连线上的所有点也都是集合D中的点 则称D为凸集 二 凸集及其顶点 5 线性规划基本概念 72 凸多边形 凹多边形 5 线性规划基本概念 第一章 73 x 1 x 2 x k 是n维欧氏空间中的k个点 若有一组数 1 2 k满足0 i 1 i 1 k 定义2 有点x 1x 1 kx k 则称点x为x 1 x 2 x k 的凸组合 凸组合 5 线性规划基本概念 74 凸集D 点x D 若找不到两个不同的点x 1 x 2 D使得x x 1 1 x 2 0 1 则称x为D的顶点 定义3 顶点 5 线性规划基本概念 75 证明 设LP问题的可行解域为集合CC x Ax bx 0 任取x 1 x 2 C 则x x 1 1 x 2 0 0 1 又因为Ax 1 b Ax 2 b所以Ax A x 1 1 x 2 b 1 b b则x C C为凸集 定理1 LP问题的可行解域一定是凸集 三 几个基本定理的证明 5 线性规划基本概念 76 只须证明 D的k个顶点x 1 x k 有 预理1D为有界凸多面集 x D x必可表为D的顶点的凸组合 5 线性规划基本概念 77 证明可用归纳法 略 x 在边界上 x在内部 5 线性规划基本概念 78 证明 设x 1 x k 为可行域顶点 若x 不是顶点 但maxZ Cx 定理2 可行域有界 最优值必可在顶点得到 5 线性规划基本概念 79 引理2 证明 1 必要性 由基可行解的定义显然 2 充分性 若向量P1 P2 Pk线性独立 则必有k m 当k m时 它们恰好构成一个基 从而x x1 x2 xm 0 0 为相应的基可行解 当k m时 则一定可从其余列向量中找出 m k 个与P1 P2 Pk构成一个基 其对应的解恰为x 所以据定义它是基可行解 5 线性规划基本概念 80 证明 反证法 由引理2知 p1 pk线性相关必有不全为0的 1 k使 1p1 kpk 0 做 1 k 0 0 T则有A 1p1 kpk 0 定理3 5 线性规划基本概念 81 选任一不为零的数 令x 1 x 0 x 2 x 0 因为x 1 2x 1 1 2x 2 所以x不是可行域的顶点 5 线性规划基本概念 82 83 x x 1 1 x 2 0 1 xj xj 1 1 xj 2 j 1 k 0 xj 1 1 xj 2 j k 1 n 5 线性规划基本概念 因为 0 1 0 xj 1 0 xj 2 0 所以xj 1 xj 2 0 j k 1 n 即p1x1 1 pkxk 1 b a p1x1 2 pkxk 2 b b 5 线性规划基本概念 84 由 a b 得 x1 1 x1 2 p1 xk 1 xk 2 pk 0 即x不是基可行解 所以p1 pk线性相关 定理4若线性规划问题有最优解 一定存在一个基可行解是最优解 5 线性规划基本概念 85 若 LP 问题有可行解 则可行解集 可行域 是凸集 可能有界 也可能无界 有有限个顶点 5 线性规划基本概念 LP问题解的性质 86 6 单纯形法 6 1 单纯形法迭代原理6 2 单纯形法计算步骤6 3 人工变量法6 4 两阶段法6 5 计算中的几个问题 87 6 1单纯形法迭代原理 一 确定初始基可行解二 从一个基可行解转换为相邻基可行解三 最优性检验和解的判别 88 A中总存在一个单位矩阵 P1 P2 Pm 一 确定初始基可行解 当约束条件为 时 加上松驰变量的系数矩阵即为单位矩阵 当约束条件为 或 时 可以构造人工基 人为产生一个单位矩阵 基向量 基变量 非基向量 非基变量可得初始基可行解 x x1 xm xm 1 xn T b1 bm 0 0 T 6 1单纯形法迭代原理 89 两个基可行解相邻指的是它们之间变换且仅变换一个基变量 设x 0 x10 x20 xm0 0 0 T 有 系数矩阵的增广矩阵 二 基可行解的转换 6 1单纯形法迭代原理 90 两边乘上一个正数 0 得 所以得到另一个点x 1 使 可行解 基解 6 1单纯形法迭代原理 91 所以x 1 是可行解 令 存在 6 1单纯形法迭代原理 92 重新排列后不含非基向量的增广矩阵 因alj 0 故上述矩阵元素组成的行列式不为零 P1 P2 Pl 1 Pj Pl 1 Pm是一个基 所以 x 1 是基可行解 00 010 0 6 1单纯形法迭代原理 93 进行初等变换 b b1 a1j bl 1 al 1 j bl 1 al 1 j bm amj T 由此x 1 是x 0 相邻的基可行解 且由基向量组成的矩阵仍为单位矩阵 x 1 b1 a1j bl 1 al 1 j bl 1 al 1 j bm amj T 6 1单纯形法迭代原理 94 将基本可行解x 0 和x 1 分别代入目标函数得 三 最优性检验和解的判别 6 1单纯形法迭代原理 95 是对线性规划问题的解进行最优性检验的标志 当所有的 i0 又Pj 0 则有无界解 通常简写为 6 1单纯形法迭代原理 96 1 找出初始基可行解 建立单纯形表 6 2单纯形法计算步骤 97 6 2单纯形法计算步骤 5 以a l k为主元素进行旋转运算 转2 98 例10用单纯形法求解线性规划问题 maxZ 2x1 x2 6 2单纯形法计算步骤 99 解 1 先将上述问题化成标准形式有 maxZ 2x1 x2 0 x3 0 x4 0 x5 6 2单纯形法计算步骤 找到一个初始基可行解x 0 0 15 24 5 100 2 列初始单纯形表 因为 1 2 确定x1为换入变量 因为 min 24 6 5 4 所以6为主元素 x4为换出变量 6 2单纯形法计算步骤 101 3 列新单纯形表 因为 2 0 确定x2为换入变量 因为 min 15 5 4 2 6 1 4 6 3 2 所以4 6为主元素 x5为换出元素 6 2单纯形法计算步骤 102 4 列新单纯形表 因为Cj Zj 0 所以达到最优解 最优解为 x 7 2 3 2 15 2 0 0 目标函数值为Z 2 7 2 1 3 2 0 15 2 0 0 8 5 6 2单纯形法计算步骤 103 练习题 解 原问题化为标准型 6 2单纯形法计算步骤 104 列初始单纯形表 1 5 6 2单纯形法计算步骤 105 1 6 列新单纯形表 6 2单纯形法计算步骤 106 2 6 列新单纯形表 6 2单纯形法计算步骤 107 6 2单纯形法计算步骤 108 6 3人工变量法 当化为标准形后的约束条件的系数矩阵中不存在单位矩阵时 可以人为地增加变量 在最优解中人工变量取值必须为零 为此 令目标函数中人工变量的系数为任意大的负值 M 亦称大M法 109 例1 maxZ 6x1 4x2 2x1 3x2 1004x1 2x2 120 x1 14x2 22x1x2 0 6 3人工变量法 110 maxZ 6x1 4x2 2x1 3x2 x3 1004x1 2x2 x4 120 x1 14x2 x5 22x1 x5 0 解 化成标准型 6 3人工变量法 111 maxZ 6x1 4x2 Mx6 Mx7 2x1 3x2 x3 1004x1 2x2 x4 120 x1 x6 14x2 x5 x7 22x1 x7 0 加人工变量 6 3人工变量法 112 列初始单纯形表 6 3人工变量法 113 6 3人工变量法 114 6 3人工变量法 115 6 4两阶段法 为了克服大M法的困难 对添加人工变量后的线性规划问题分两个阶段来计算 称为两阶段法 解题思路 第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题 即令目标函数中其它变量的系数取零 人工变量的系数取某个负的常数 一般取 1 在保持原问题约束条件不变的情况下求这个目标函数极大化时的解 显然在第一阶段中 当人工变量取值为0时 目标函数值也为0 这时候的最优解就是原线性规划问题的一个基可行解 116 6 4两阶段法 117 解题过程 第1阶段 解辅助问题 当进行到最优表时 若W 0 则得到原问题的一个基本可行解 转入第2阶段 若W 0 则判定原问题无可行解 第2阶段 去除人工变量 求解原问题 第一阶段的最优解为原问题的初始基可行解 6 4两阶段法 118 例2 解 第 1 阶段 maxW x6 x7 6 4两阶段法 119 列初始单纯形表 第二阶段 去除人工变量 列新单纯形表求解 6 4两阶段法 120 6 4两阶段法 121 6 4两阶段法 122 6 5计算中的几个问题 2 退化 非退化 值唯一 在下一次迭代中有一个或几个基变量为0 从而出现退化解 可能会导致循环 永远达不到最优解 1 目标函数极小化时解的最优性判别以 i 0作为判别表中解是否最优的标志 123 如何解决退化问题 Dantzig规则 6 5计算中的几个问题 124 6 5计算中的几个问题 1951年Hoffman给出反例 3个方程 11个变量 1955年E M L Beale3个方程 7个变量 6次迭代后 出现循环 125 Bland原则 1976年第9届国际数学规划大会 6 5计算中的几个问题 126 3 无可行解的判别 当线性规划问题中添加人工变量后 无论用人工变量法或两阶段法 初始单纯形表中的解因含非零人工变量 故实质上是非可行解 当求解结果出现所有 i 0时 如基变量中仍含有非零的人工变量 两阶段法求解时第一阶段目标函数值不等于零 表明问题无可行解 6 5计算中的几个问题 127 6 5计算中的几个问题 例7用单纯形法求解线性规划问题 128 6 5计算中的几个问题 解 添加松弛变量和人工变量 原模型化为标准型 以X3 X5为基变量列初始单纯形表 进行计算 129 6 5计算中的几个问题 130 6 6单纯形法小结 131 6 6单纯形法小结 132 7 应用举例 例1 用长7 4m的钢材做100套钢架 每套钢架需长2 9m 2 1m 1 5m的料各一根 问如何下料 使用的原料最省 分析 可行的下料方案有 133 解