管理运筹学第一章-线性规划.ppt

运筹学OperationalResearch 天津大学管理学院郭均鹏 教师简介 郭均鹏 博士 副教授 硕士生导师 主要研究领域 运筹决策技术 信息管理与企业信息化 绩效考核与薪酬体系设计联系方式 天津大学管理学院 30007213602053107 guojp 课程教材 吴育华 杜纲 管理科学基础 天津大学出版社 绪论 运筹学 OperationalResearch 直译为 运作研究 产生于二战时期60年代 在工业 农业 社会等各领域得到广泛应用在我国 50年代中期由钱学森等引入 运用数学方法 为决策者进行最优决策提供科学依据的一门应用科学 一 运筹学的产生与发展 二 运筹学的性质 三 运筹学的分支 线性规划非线性规划图论与网络分析存储论决策论动态规划排队论 四 运筹学在管理中的应用 生产计划 生产作业的计划 日程表的编排 合理下料等 追求利润最大化和成本最小化库存管理运输问题 确定最小成本的运输线路 物资的调拨以及建厂地址的选择等人力资源管理 对人员的需求和使用的预测 确定人员编制 人员合理分配 建立人才评价体系等工程网络计划 确定工期 关键工序等 明确问题 问题分类 建立数学模型 求解数学模型 结果分析 实施 五 运用运筹学方法解决实际问题的工作流程 注意计算机软件的应用 Lindo Exel等 第一章线性规划 LinearProgramming 简称LP 1线性规划的模型与图解法 2线性规划的举例与软件求解 3整数规划 4运输问题 第一章线性规划 LinearProgramming 简称LP 1线性规划的模型与图解法 一 LP问题及其数学模型二 线性规划的标准型三 线性规划的图解法 一 LP问题及其数学模型 例1某工厂可生产甲 乙两种产品 需消耗煤 电 油三种资源 有关单耗数据如表 试拟定使总收入最大的生产计划 产品 资源 线性规划模型三要素 1 决策变量设甲产品生产x1 乙产品生产x2 2 目标函数MaxZ 7x1 12x2 3 约束条件 9x1 4x2 3604x1 5x2 2003x1 10 x2 300 x1 x2 0 s t 返回 SubjectTo 意为 使其满足 目标函数 Max Min Z c1x1 c2x2 cnxn a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 约束条件 s t LP模型的一般形式 课堂练习 某蓄场每日要为每头牲畜购买饲料 以使其获取所需的A B C D四种养分 有关数据如下表 现饲料可从市场上出售的M N两种饲料中选择 试决定总花费最小的购买方案 列出模型 养分 饲料 课堂练习 某蓄场每日要为每头牲畜购买饲料 以使其获取所需的A B C D四种养分 有关数据如下表 现饲料可从市场上出售的M N两种饲料中选择 试决定总花费最小的购买方案 列出模型 养分 饲料 答案 设购买M饲料x1 N饲料x2 0 5x1 0 1x2 100 2x1 0 3x2 50 3x1 0 4x2 80 2x2 7x1 x2 0 s t MinZ 300 x1 200 x2 二 线性规划的标准型 MaxZ c1x1 c2x2 cnxn a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 s t 1 标准形式 矩阵表示 MaxZ CX AX bX 0 s t 其中 C c1 c2 cn 称为价格系数A aij m n称为技术系数b b1 b2 bm 称为资源系数 1 MinZ CX MaxZ CX 2 约束条件 例如 9x1 4x2 360 9x1 4x2 x3 360 松弛变量 型约束 加松弛变量 型约束 减松弛变量 例 将如下问题化为标准型 三 线性规划的图解法 1 步骤 1 作约束的图形 可行域 可行解的集合 先作非负约束 再作资源约束 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 2 作目标函数的等值线 给z不同的值 作相应直线 判断出z增大时 直线的移动方向 将直线向增大方向移动 直至可行域边界 交点X 即为最优解 7x1 12x2 84 7x1 12x2 168 如 令7x1 12x2 847x1 12x2 168 X 20 24 Z 428 最优解 x1 0 x2 1最优目标值z 6 课堂练习图解法求解线性规划 2 LP解的几种情况 注 出现 3 4 情况时 建模有问题 图解法的结论 线性规划的可行域是凸集 线性规划的最优解若存在 必在可行域的在极点获得若在两个极点同时获得 则有无穷多最优解 极点 2线性规划应用举例与软件求解 例1 下料问题 某工厂要做100套钢架 每套用长为2 9m 2 1m 1 5m的圆钢各一根 已知原料每根长7 4m 问 应如何下料 可使所用原料最省 例1 下料问题 某工厂要做100套钢架 每套用长为2 9m 2 1m 1 5m的圆钢各一根 已知原料每根长7 4m 问 应如何下料 可使所用原料最省 2 0 1 0 1 1 2 0 0 3 1 1 1 0 9 1 0 3 0 0 3 0 1 1 0 2 2 0 2 0 1 3 0 8 0 0 4 1 4 2x1 x2 x3 x4 1002x2 x3 3x5 2x6 x7 100 x1 x3 3x4 2x6 3x7 4x8 100 x1 x2 x3 x4 x5 x6 x7 x8 0 设x1 x2 x3 x4 x5 x6 x7 x8分别为上述8种方案下料的原材料根数 建立如下的LP模型 最优解为 x1 10 x2 50 x3 0 x4 30 x5 0 x6 0 x7 0 x8 0 minZ x1 x2 x3 x4 x5 x6 x7 x8 s t 线性规划求解软件 lindo 3整数规划IntegerProgramming 简称IP 一 整数规划的一般模型 LP maxz CXAX bX 0 IP maxz CXAX bX 0X为整数 整数规划的解法 分枝定界法或割平面法 基本思想是把一个整数规划问题化为一系列的线性规划问题来求解 整数规划的分类 纯整数规划 所有变量都限制为整数混合整数规划 仅部分变量限制为整数0 1整数规划 变量的取值仅限于0或1 例 人力资源分配的问题某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下 设司机和乘务人员分别在各时间段一开始时上班 并连续工作八小时 问该公交线路怎样安排司机和乘务人员 既能满足工作需要 又配备最少司机和乘务人员 解 设xi表示第i班次时开始上班的司机和乘务人员数 于是LP模型为 x1 x6 60 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30 x1 x2 x3 x4 x5 x6 0且为整数 minz x1 x2 x3 x4 x5 x6 最优解 X 60 10 50 0 30 0 Z 150 二 0 1整数规划 投资场所的选址问题指派问题背包问题消防队问题 1 投资场所的选址问题某城市拟在东 西 南三区设立商业网点 备选位置有A1 A7共7个 如果选Ai 估计投资为bi元 利润为ci元 要求总投资不超过B元 规定东区 A1 A2 A3中至多选2个西区 A4 A5中至少选一个南区 A6 A7中至少选一个问如何设点使总利润最大 maxz xi 0或1 i 1 7 x1 x2 x3 2 x4 x5 1 x6 x7 1 s t 课堂练习1 某钻井队要从S1 S10共10个井位中确定五个钻井探油 如果选Si 估计钻探费用为ci元 并且井位选择上要满足下列条件 1 或选择S1和S7 或选择S8 2 选择了S3或S4就不能选择S5 反过来也一样 3 在S5 S6 S7 S8中最多只能选两个 问如何选择井位使总费用最小 课堂练习1 某钻井队要从S1 S10共10个井位中确定五个钻井探油 如果选Si 估计钻探费用为ci元 并且井位选择上要满足下列条件 1 或选择S1和S7 或选择S8 2 选择了S3或S4就不能选择S5 反过来也一样 3 在S5 S6 S7 S8中最多只能选两个问如何选择井位使总费用最小 minz s t 或1 i 1 10 某篮球队有8名队员 其身高和专长如下表 现要选拔5名球员上场参赛 要求 1 中锋只有1人上场 2 后卫至少有一人上场 3 只有2号上场 6号才上场要求平均身高最高 应如何选拔队员 课堂练习2 maxz 或1 i 1 8 s t 某篮球队有8名队员 其身高和专长如下表 现要选拔5名球员上场参赛 要求 1 中锋只有1人上场 2 后卫至少有一人上场 3 只有2号上场 6号才上场要求平均身高最高 应如何选拔队员 2 指派问题 例 有一份中文说明书 需译成英 日 德 俄四种文字 分别记作任务E J G R 现有甲 乙 丙 丁四人 他们将中文说明书翻译成不同语种说明书所需的时间如下表所示 问应指派何人去完成何项任务 使所需总时间最少 问题描述 n项任务可由n个人完成 由于专长不同 各人完成各任务的时间也不同 求最优安排 要求 每人只能完成一项任务 每项任务只能由一人完成 x11 x12 x13 x14 1 甲只能干一项工作 x21 x22 x23 x24 1 乙只能干一项工作 x31 x32 x33 x34 1 丙只能干一项工作 x41 x42 x43 x44 1 丁只能干一项工作 x11 x21 x31 x41 1 E任务只能一人干 x12 x22 x32 x42 1 J任务只能一人干 x13 x23 x33 x43 1 G任务只能一人干 x14 x24 x34 x44 1 R任务只能一人干 xij 0或1 i j 1 2 3 4 minz 2x11 15x12 13x13 4x14 10 x21 4x22 14x23 15x24 9x31 14x32 16x33 13x34 7x41 8x42 11x43 9x44 课堂练习 P57例2 23 例 甲 乙 丙 丁是四名游泳运动员 他们各种姿势的100m游泳成绩如表 为组成一个4 100m混合泳接力队 怎样选派运动员 方使接力队的游泳成绩最好 3 背包问题 问题描述 已知 一个背包最大容量为b公斤 有m件物品供选择 每件物品重ai公斤 价值为ci i 1 m 问题 携带哪些物品可使总价值最大 一般模型 s t 1 物品i被选中0 物品i没被选中 xi 例 一个徒步旅行者要在背包中选择一些最有价值的物品携带 他最多能带115kg的物品 现有5件物品 分别重54 35 57 46 19kg 其价值依次为7 5 9 6 3 问携带哪些物品可使总价值最大 解 模型为 s t 4 消防队问题 某城市的消防总部将全市划分为11个防火区 设有4个消防救火站 下图 表示消防站 1 11表示防火区域 图中连线表示各地区由哪个消防站负责 问题 可否减少消防站的数目 仍能同样负责各地区的防火任务 如果可以 应关闭哪个消防站 则模型为 课堂练习 某市为方便学生上学 拟在新建的居民小区增设若干所小学 已知备选校址代号及其能覆盖的居民小区编号如表所示 问为覆盖所有小区至少应建多少所小学 备选校址代号 覆盖的居民小区编号 ABCDEF 1 5 7 1 2 5 1 3 5 2 4 5 3 6 4 6 4运输问题 一 运输问题的提出生产某种产品 m个产地 A1 Am 产量 a1 amn个销地 B1 Bn 销量 b1 bn已知 Ai至Bj的运输单价为cij问题 确定Ai运往Bj的数量xij 使总运费最低 二 运输问题的表示网络图运输表线性规划模型 A2 A3 B2 A1 B3 B4 B1 运输问题网络图 a2 4 a3 9 b1 3 b2 6 b3 5 b4 6 a1 7 供应量 供应地 运价 需求量 需求地 3 11 3 10 1 9 2 8 7 4 10 5 运输问题的表格表示 运输问题线性规划模型 三 运输问题的分类 产销平衡问题 ai bj产销不平衡问题 供大于求 ai bj 供不应求 ai bj 四 运输问题的求解 表上作业法 确定初始可行调运方案最小元素法判别当前可行方案是否最优闭回路法对现有方案进行调整闭回路法 用最小元素法确定初始可行调运方案最小元素法的基本思想 就近尽量满足供应 3 1 3 4 6 3 0 1 0 4 0 3 0 3 0 3 0 0 例 最小元素法求解下面运输问题的初始解 用闭回路法进行最优性检验1 找空格的闭回路 以某空格为起点 用水平线或垂直线向前划 只能在碰到某一数字格时才能转弯 按照这一规则继续前进 直到回到起始的空格为止 2 根据闭回路计算空格的检验数 检验数 奇数顶点的单位运价之和 偶数顶点的单位运价之和 1 2 1 1 10 12 检验数的经济含义 当由产地Ai往销地Bj增运一个单位货物时所引起的总运输成本的变化数 结论 若所有检验数都大于等于0 则当前方案最优 对现有方案进行调整在负的检验数中选择绝对值最大的空格 在方案表中从该空格出发 沿着