《线性规划》ppt课件

OPERATIONSRESEARCH运筹学 怎样把事情做到最好张朝伦 1 绪论 Operations汉语翻译工作 操作 行动 手术 运算OperationsResearch日本 运用学港台 作业研究中国大陆 运筹学OperationalResearch原来名称 意为军事行动研究 历史渊源 2 运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队 3 运筹学在中国 50年代中期引入华罗庚推广优选法 统筹法中国邮递员问题 运输问题 4 学科性质 应用学科Morse Kimball定义 运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法 Churchman定义 运筹学是应用科学的方法 技术和工具 来处理一个系统运行中的问题 使系统控制得到最优的解决方法 中国定义 运筹学是应用分析 试验 量化的方法 对经济管理系统中人力 物力 财力等资源进行统筹安排 为决策者提供有依据的最优方案 以实现最有效的管理 5 运筹学的工作步骤 确定问题搜集数据建立模型检验模型求解模型结果分析结果实施 6 运筹学与计算机 计算机为运筹学提供解题工具 要学会解题的思路与方法 建立模型很重要 7 线性规划 LinearProgramming 简称LP 线性规划的发展1939年 前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题1947年 Dantzig提出求解线性规划的单纯形法1950 1956年 主要研究线性规划的对偶理论1958年 发表整数规划的割平面法1960年 Dantzig和Wolfe研究成功分解算法 奠定了大规模线性规划问题理论和算法的基础 1979年 Khachiyan 1984年 Karmarkaa研究成功线性规划的多项式算法 8 线性规划研究的主要问题一类是已有一定数量的资源 人力 物质 时间等 研究如何充分合理地使用它们 才能使完成的任务量为最大 实际上 上述两类问题是一个问题的两个不同的方面 都是求问题的最优解 max或min 另一类是当一项任务确定以后 研究如何统筹安排 才能使完成任务所耗费的资源量为最少 9 线性规划 线性规划的基本概念一 问题的提出 解 1 决策变量 设产品I II的产量分别为x1 x2 2 目标函数 设总运费为z 则有 maxz 2x1 3x2 3 约束条件 10 例1 2某厂生产三种药物 这些药物可以从四种不同的原料中提取 下表给出了单位原料可提取的药物量 要求 生产A种药物至少160单位 B种药物恰好200单位 C种药物不超过180单位 且使原料总成本最小 解 1 决策变量 设四种原料的使用量分别为 x1 x2 x3 x4 2 目标函数 设总成本为z 则有 minz 5x1 6x2 7x3 8x4 3 约束条件 11 例3 合理下料问题 12 例3 合理下料问题设xj分别代表采用切割方案1 8的套数 13 二 数学模型 1 决策变量 X x1 x2 xn T 2 目标函数 max minz c1x1 c2x2 cnxn 14 三 模型特点 1都用一组决策变量X x1 x2 xn T表示某一方案 且决策变量取值非负 满足以上三个条件的数学模型称为线性规划 2都有一个要达到的目标 并且目标要求可以表示成决策变量的线性函数 3都有一组约束条件 这些约束条件可以用决策变量的线性等式或线性不等式来表示 15 其它形式 其中 求和形式 矩阵形式 决策变量 常数项 系数矩阵 价值系数 其中 16 线性规划数学模型的建立 一 建模条件 1优化条件 问题所要达到的目标能用线型函数描述 且能够用极值 max或min 来表示 2限定条件 达到目标受到一定的限制 且这些限制能够用决策变量的线性等式或线性不等式表示 3选择条件 有多种可选择的方案供决策者选择 以便找出最优方案 17 线性规划图解法 一 解题步骤 4将最优解代入目标函数 求出最优值 1在直角平面坐标系中画出所有的约束等式 并找出所有约束条件的公共部分 称为可行域 可行域中的点称为可行解 2标出目标函数值增加的方向 3若求最大 小 值 则令目标函数等值线沿 逆 目标函数值增加的方向平行移动 找与可行域最后相交的点 该点就是最优解 18 二 建模步骤 1确定决策变量 即需要我们作出决策或选择的量 一般情况下 题目问什么就设什么为决策变量 2找出所有限定条件 即决策变量受到的所有的约束 3写出目标函数 即问题所要达到的目标 并明确是max还是min 19 线性规划的图解 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 6 4 8 6 0 x1 x2 20 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地 在每个产地的供应量与每个销地的需求量已知 并知道各地之间的运输单价的前提下 如何确定一个使得总的运输费用最小的方案 一 运输问题 21 例1 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地的每件物品的运费如下表所示 问应如何调运 使得总运输费最小 22 解 我们知道A1 A2两个产地的总产量为 200 300 500 件 B1 B2 B3三个销地的总销量为 150 150 200 500 件 总产量等于总销量这是一个产销平衡的运输问题 把A1 A2的产量全部分配给B1 B2 B3 正好满足这三个销地的需要 23 从上表可写出此问题的数学模型 满足产地产量的约束条件为 x11 x12 x13 200 x21 x22 x23 300 满足销地销量的约束条件为 x11 x21 200 x12 x22 300 x13 x23 200 24 所以此运输问题的线性规划的模型如下 目标函数 minf 6x11 4x12 6x13 6x21 5x22 5x23约束条件 x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 25 二 分派问题 例设有工作m件 人员 个 且一人做一件工作 第i人做j件工作的时间 或费用 为cij 问如何分派这些人员使总时间 或费用 最少 解1 第i人做第j件工作 设xij 0 否则则得0 1规划 26 27 三 网络问题 一个网络包括一些结点 用圆圈表示 每个结点由几条弧 用箭头表示 与其它结点相连 如图 21542012891510714108123136 28 最短路问题 解 设1 有从i到期j的弧xij 0 否则则得0 1规划 Minz 20 x12 14x13 15x24 12x25 10 x34 13x36 8x45 9x47 8x56 10 x57 12x67 总路程 S t X12 x13 1 从1出发的汽车为一辆 x12 x24 x25 0 x13 x34 x36 0 x24 x34 x45 x47 0 29 x25 x45 x56 x57 0 x36 x56 x67 0 x47 x57 x67 1 到达7的汽车为一辆 Xij 0 或1 i j 1 2 7 30 四 选址问题 例 某公司拟定在东 西 南三区建立门市部 拟议中有7个地址A1 A2 A7可供选择 并规定 在东区 A1 A2 A3中至多选两个 在西区 A4 A5中至少选一个 在南区 A6 A7中至少选一个 若选Ai 投资bi元 每年可获利估计为ci元 总投资不超过b元 问如何选择门市部的地址公司的年利润最大 31 解设1 选择Ai xi 0 否则则得0 1规划模型 32 33 五 曲线拟合问题 例已知变量y随变量x变化 并且已知一组观测值 xi yi I 1 2 n 1 拟合一条回归直线 使回归值与观察值的绝对偏差之和最小 2 拟合一条回归直线 使回归值与观察值的最大偏差最小 34 解设所求回归直线方程为y a bx 1 据题意 应求使最小的a b 由于函数中带有绝对值 不便用数学分析方法来处理 但用线性规划方法来处理就变得较容易 令则得线性规划模型 35 模型中 xi yi已知 ui vi a b为决策变量 原问题化为含 2n 2 个决策变量 n个约束方程的一极小化问题 36 六 人员安排问题 例某公司的营业时间是上午8点到22点 以两小时为一时段 各时段内所需的服务人员数如下表 每个服务人员可在任一时段开始上班 但要工作8小时 而工资都相同 问应如何安排服务人员使公司所付工资总数最少 37 38 解设xi为时段i开始工作的人数 i 1 2 3 4 由于各班工资相同 要求公司所付的工资最少也就是要求服务人员最少 于是可得整数规划模型 39 例某公司的营业时间是上午8点到21点 服务人员中途需要1小时吃饭和休息时间 每人的工作时间为8小时 上午8点到17点工作的人员月工资为800元 中午12点到21点工作的人员月工资为900元 为保证营业时间内都有人上班 公司安排了四个班次 其班次和休息时间安排如下表一 各时段需求的人数如上例之表 只是第6 7段合并为18点到21点 需求人数为10人 问应如何安排服务人员既满足需求又使公司所付工资总数最少 40 表一 41 解为了便于建立模型 可用各班中途休息的起止时刻和上例之表中时间区间的起止时间分细 并求出各班工作的关联表 见表二 表中j列的 1 表示该班次在相应的时段内工作 0 表示不工作 42 表二 43 设xi表示第i班安排的人数 i 1 2 3 4 则可得整数规划模型 44 七 有配套约束的资源优化问题 例某公司计划用资金60万来购买A B C三种运输汽车 已知A种汽车每辆为1万元 每班需一名司机 可完成每公里2100吨 B种汽车每辆为2万元 每班需两名司机 可完成每公里3600吨 C种汽车每辆为2 3万元 每班需两名司机 可完成每公里3780吨 每辆汽车每天最多安排三班 每个司机每天最多安排一班 购买汽车数量不超过30辆 司机不超过145人 问 每种汽车应购买多少辆 可使公司今后每天可完成的公里吨数最大 45 解设购买A种汽车中 每天只安排一班的有x11辆 每天安排二班的有x12辆 每天安排三班的有x13辆 同样设购买B种汽车依次有x21 x22 x23辆 购买C种汽车依次有x31 x32 x33辆 因此有 46 八 多周期动态生产计划问题 例某柴油机厂接到今年1至4季度柴油机生产订单分别为 3000台 4500台 3500台 5000台 该厂每季度正常生产量为3000台 若加班可多生产1500台 正常生产成本为每台5000元 加班生产还要追加成本每台1500元 库存成本为每台每季度200元 问该柴油机厂该如何组织生产才能使生产成本最低 47 解设xi1为第i个季度正常生产的柴油机台数 xi2为第i个季度加班生产的柴油机台数 xi3为第i个季度初库存数 i 1 2 3 4 第一季度初及年底的库存数均产零 若记di为第i季度的需求量 c1 c2 c3分别为正常生产 加班生产 库存 每季度 每台柴油机的成本 则其数学模型为 代入具体数据 得数学模型如下 48 49 十二 投资问题 投资者经常会遇到投资项目的组合选择问题 要考虑的因素有收益率 风险 增长潜力等条件 并进行综合权衡 以求得一个最佳投资方案 例某投资公司有50万元可用于长期投资 可供选择的投资项目包括购买国库券 购买公司债券 投资房地产 购买股票 银行短期或长期储蓄 各种投资方式的投资期限 年收益率 风险系数 增长潜力的具体参数见下表 若投资者希望投资组合的平均年限不超过5年 平均的期望收益率不低于13 风险系数不超过4 收益的增长潜力不低于10 问在满足上述要求前提下 投机者该如何选择投资组合使平均年平均收益率最高 50 51 解设xi为第i种投资方式在总投资中所占的比利 则该数学模型为 52 例某投资者有资金10万元 考虑在今后5年内给下列4个项目进行投资 已知 项目A 从第1年到第4年每年年初需要投资 并于次年末回收本利115 项目B 第3年初需要投资 到第5年末能回收本利125 但规定投资额不超过4万元项目C 第2年初需要投资 到第5年末能回收本利140 但规定最大投资额不超过3万元 项目D 5年内每年初可购买公债 于当年亩归还 并加利息6 问该投资者应如何安排他的资金 确定给这些项目每年的投资额 使到第5年末能拥有的资金本利总额为最大 53 解记xiA xiB xiC xiD i 1 2 5 分别表示第i年初给项目A B C D的投资额 它们都是决策变量 为了便于书写数学模型 列表如下 54 根据项目A B C D的不同情况 在第5年末能收回的本利分别为 1 15x4A 1 25x3B 1 40 x2C 及1 06x5D 因此目标函数为 maxz 1 15x4A 1 25x3B 1 40 x2C 1 06x5D 约束条件是每年年初的投资额等于该投资者年初所拥有的资金 第1年年初该投资者拥有10万元资金 故有x1A x1D 10000 第2年年初该投资者手中拥有资金只有 1 6 x1D 故有x2A x2C x2D 1 06x1D 第3年年初该投资者拥有资金从D项目收回的本金 1 06x2D 及从项目A中第1年投