激励与沟通_运筹学ⅰ--怎样把事情做到最好

OR1 1 OPERATIONSRESEARCH运筹学 怎样把事情做到最好郝英奇 OR1 2 第一章绪论 1 1题解Operations汉语翻译工作 操作 行动 手术 运算OperationsResearch日本 运用学港台 作业研究中国大陆 运筹学OperationalResearch原来名称 意为军事行动研究 历史渊源 OR1 3 绪论 1 2运筹学的历史早期运筹思想 田忌赛马丁渭修宫沈括运粮Erlang1917排队论Harris1920存储论Levinson1930零售贸易康脱洛维奇1939LP OR1 4 绪论 1 2运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队 OR1 5 绪论 1 2运筹学的历史管理运筹学阶段战后人员三分 军队 大学 企业大学 课程 专业 硕士 博士企业 美国钢铁联合公司英国国家煤炭局运筹学在中国 50年代中期引入华罗庚推广优选法 统筹法中国邮递员问题 运输问题 OR1 6 1 3学科性质 应用学科Morse Kimball定义 运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法 Churchman定义 运筹学是应用科学的方法 技术和工具 来处理一个系统运行中的问题 使系统控制得到最优的解决方法 中国定义 运筹学是应用分析 试验 量化的方法 对经济管理系统中人力 物力 财力等资源进行统筹安排 为决策者提供有依据的最优方案 以实现最有效的管理 OR1 7 1 4定性与定量 例 店主进货两者都是常用的决策方法定性是基础 定量是工具 定量为定性服务 定性有主观性也有有效性 定量有科学性也有局限性 管理科学的发展 定量越来越多 但定量不可替代定性 OR1 8 1 5运筹学的模型 模型 真实事物的模仿 主要因素 相互关系 系统结构 形象模型 如地球仪 沙盘 风洞模拟模型 建港口 模拟船只到达 学生模拟企业管理系统运行 数学模型 用符号或数学工具描述现实系统 V F xi yj uk G xi yj uk 0 OR1 9 1 6运筹学的学科体系 规划论 线性规划 非线性规划 整数规划 目标规划 动态规划图论与网络存储论排队论决策论对策论计算机仿真 OR1 10 1 7运筹学的工作步骤 确定问题搜集数据建立模型检验模型求解模型结果分析结果实施 OR1 11 1 8运筹学与计算机 计算机为运筹学提供解题工具 本书有现成的程序可以利用要学会解题的思路与方法 建立模型很重要 OR1 12 第二章线性规划与单纯形法 2 1LP linearprogramming 的基本概念LP是在有限资源的条件下 合理分配和利用资源 以期取得最佳的经济效益的优化方法 LP有一组有待决策的变量 一个线性的目标函数 一组线性的约束条件 OR1 13 2 1 1LP的数学模型例题1 生产计划问题 某厂生产两种产品 需要三种资源 已知各产品的利润 各资源的限量和各产品的资源消耗系数如下表 OR1 14 例题1建模 问题 如何安排生产计划 使得获利最多 步骤 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 人力约束9X1 4X2 360设备约束4X1 5X2 200原材料约束3X1 10X2 300非负性约束X1 0X2 0 OR1 15 例题2 配方问题 养海狸鼠饲料中营养要求 VA每天至少700克 VB每天至少30克 VC每天刚好200克 现有五种饲料 搭配使用 饲料成分如下表 OR1 16 例题2建模 设抓取饲料Ix1kg 饲料IIx2kg 饲料IIIx3kg 目标函数 最省钱minZ 2x1 7x2 4x3 9x4 5x5约束条件 3x2 2x2 x3 6x4 18x5 700营养要求 x1 0 5x2 0 2x3 2x4 0 5x5 300 5x1 x2 0 2x3 2x4 0 8x5 200用量要求 x1 50 x2 60 x3 50 x4 70 x5 40非负性要求 x1 0 x2 0 x3 0 x4 0 x5 0 OR1 17 例题3 人员安排问题 医院护士24小时值班 每次值班8小时 不同时段需要的护士人数不等 据统计 OR1 18 例题3建模 目标函数 minZ x1 x2 x3 x4 x5 x6约束条件 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30非负性约束 xj 0 j 1 2 6 OR1 19 归纳 线性规划的一般模式 目标函数 max min Z c1x1 c2x2 c3x3 cnxn约束条件 a11x1 a12x2 a13x3 a1nxn b1a21x1 a22x2 a23x3 a2nxn b2 am1x1 am2x2 am3x3 amnxn bn非负性约束 x1 0 x2 0 xn 0 OR1 20 2 1 2线性规划图解法 由中学知识可知 y ax b是一条直线 同理 Z 70 x1 120 x2 x2 70 120 x1 Z 120也是一条直线 以Z为参数的一族等值线 9x1 4x2 360 x1 360 9 4 9x2是直线x1 360 9 4 9x2下方的半平面 所有半平面的交集称之为可行域 可行域内的任意一点 就是满足所有约束条件的解 称之为可行解 OR1 21 例1图示 9080604020 020406080100 x1 x2 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 A B C D E F G H I Z 70 x1 120 x2 OR1 22 概念 概念 1 可行解 满足所有约束条件的解 2 可行域 即可行解的集合 所有约束条件的交集 也就是各半平面的公共部分 满足所有约束条件的解的集合 称为可行域 3 基解 约束条件的交点称为基解 直观 4 基可行解 基解当中的可行解 5 凸集 集合内任意两点的连线上的点均属于这个集合 如 实心球 三角形 OR1 23 结论 可行域是个凸集可行域有有限个顶点最优值在可行域的顶点上达到无穷多解的情形无界解情形无解情形 OR1 24 2 1 3线性规划的标准型 代数式maxZ c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmxj 0j 1 2 n OR1 25 线性规划的标准型 和式 maxZ cjxj aijxj bii 1 2 mxj 0j 1 2 n j 1 n n j 1 OR1 26 线性规划的标准型 向量式 maxZ CX pjxj bii 1 2 mxj 0j 1 2 nC c1 c2 c3 cn X X1 X2 X3 Xn T n j 1 OR1 27 线性规划的标准型 矩阵式 maxZ CXAX bX 0其中 b b1 b2 bm Ta11a12 a1nA a21a22 a2n am1am2 amn OR1 28 标准型的特征 目标函数极大化约束条件为等式决策变量非负 OR1 29 非标准型转化为标准型 目标函数极小化转为极大化 minZ max Z 一个数的极小化等价于其相反数的极大化 不等式约束的转化 aijxj bi加入松弛变量 aijxj bi减去剩余变量非正变量 即xk 0则令x k xk自由变量 即xk无约束 令xk x k x k OR1 30 非标准型转化举例之一 maxZ 70X1 120X2maxZ 70X1 120X29X1 4X2 3609X1 4X2 X3 3604X1 5X2 2004X1 5X2 x4 2003X1 10X2 3003X1 10X2 x5 300X1 0X2 0Xj 0j 1 2 5 OR1 31 非标准型转化举例之二 minZ x1 2x2 3x3maxZ x 1 2x2 3 x 3 x 3 x1 x2 x3 9 x 1 x2 x 3 x 3 x4 9 x1 2x2 x3 2x 1 2x2 x 3 x 3 x5 23x1 x2 3x3 5 3x 1 x2 3 x 3 x 3 5x1 0 x2 0 x3无约束x 1 0 x2 0 x 3 0 x 3 0 x4 0 x5 0 OR1 32 2 1 4基可行解 基的概念 如前所述LP标准型和式 maxZ cjxj aijxj bixj 0j 1 2 n矩阵式 maxZ CXAX bX 0约束方程的系数矩阵A的秩为m 且m n 设A B N B是A中m m阶非奇异子矩阵 则称B是LP的一个基 即 B是A中m个线性无关向量组 n j 1 n j 1 OR1 33 基解的概念 不失一般性 设B是A的前m列 即B p1 p2 pm 其相对应的变量XB x1 x2 xm T 称为基变量 其余变量XN Xm 1 Xn T称为非基变量 令所有非基变量等于零 则X x1 x2 xm 0 0 T称为基解 OR1 34 基可行解的概念 基可行解 基解可正可负 负则不可行 违背非负性约束条件 称满足所有约束条件的基解为基可行解 退化的基可行解 若某个基变量取值为零 则称之为退化的基可行解 基解的数目 最多Cmn n m n m OR1 35 例题6基可行解说明 maxZ 70X1 120X2P1P2P3P4P59X1 4X2 X3 360941004X1 5X2 x4 200A 450103X1 10X2 x5 300310001Xj 0j 1 2 5这里m 3 n 5 Cmn 10 OR1 36 例题6基可行解说明 基 p3 p4 p5 令非基变量x1 x2 0 则基变量x3 360 x4 200 x5 300 可行解基 p2 p4 p5 令非基变量x1 0 x3 0基变量x2 90 x4 250 x5 600 非可行解基 p2 p3 p4 令非基变量x1 x5 0 则基变量x2 30 x3 240 x4 50 可行解 P21图 OR1 37 2 2单纯形法 2 2 1初始基可行解的确定从系数矩阵中找到一个可行基B 不妨设B由A的前m列组成 即B P1 P2 Pm 进行等价变换 约束方程两端分别左乘B 1得X1 a 1m 1xm 1 a 1nxn b 1x2 a 2m 1xm 1 a 2nxn b 2 xm a mm 1xm 1 a mnxn b m令非基变量为0 得基可行解X 0 b1 b2 bm 0 0 Tz0 cibi OR1 38 2 2单纯形法 2 2 2最优性检验 LP经过若干步迭代 成为如下形式 X1 a 1m 1xm 1 a 1nxn b 1x1 b 1 a 1jxjx2 a 2m 1xm 1 a 2nxn b 2x2 b 2 a 2jxj xm a mm 1xm 1 a mnxn b mxm b m a mjxj OR1 39 单纯形法 一般性表示 xi b i a ijxji 1 2 m将xi代入目标函数得 Z cjxj cixi cjxj ci b i a ijxj cjxj cibi cj cia ij xj令 j cj cia ijz0 cibi 则Z z0 jxj j判别准则 j 0时 达到最优解 OR1 40 单纯形法 2 2 2基变换若存在 j 0 则取max j K 相应之非基变量XK若取非零 将使Z增加 故令XK进基 令XK 0 其余非基变量保持为零 XK原是非基变量 取零值 若XK 0将迫使某个原基变量为零 当XK取值超过任意b i a ik时 将破坏非负性条件 于是令 min b i a ika ik 0 b L a Lk 这时原基变量XL 0 由基变量变成非基变量 a Lk处在变量转换的交叉点上 称之为枢轴元素 j 0 OR1 41 单纯形法解题举例 单纯形表的格式 OR1 42 OR1 43 2 2 3单纯形法的计算步骤 找到初始可行基 建立单纯形表计算检验数 若所有 j 0则得最优解 结束 否则转下步若某 K 0而P K 0 则最优解无界 结束 否则转下步根据max j K原则确定XK进基变量 根据 规则 min b i a ika ik 0 b L a Lk确定XL为出基变量以a Lk为枢轴元素进行迭代 回到第二步 OR1 44 2 3单纯形法的进一步探讨 2 3 1极小化问题直接求解 检验数的判别由所有 j 0即为最优 变为所有 j 0则为最优 人工变量法之一 大M法人工变量价值系数M例人工变量法之二 构造目标函数 分阶段求解例2 3 2无穷多最优解情形 非基变量检验数 j 02 3 3退化解的情形 有两个以上 值相等 OR1 45 2 3 4单纯形法的计算机求解 程序说明应用举例例题1例题2 OR1 46 2 5LP应用举例之一 例13合理下料问题料长7 4米 截成2 9 2 1 1 5米各200根 如何截取余料最少 关键 设变量 OR1 47 应用举例之二 例14混合配方问题A B C D四种原料配制三种产品 三类约束 技术要求 原料限量 市场容量 已知产品价格和原料价格 求利润最大的配方 关键 设变量 OR1 48 应用举例之三 例15 滚动投资问题兹有100万元闲钱 投资方向有四 第四年 第一年 第二年 第三年 A项目110 B项目135 C项目125 D项目104 第五年 各年投资什么项目 使第五年末资本总额为最大 OR1 49 应用举例之四 例16动态生产计划问题工厂做n个月的生产计划 第j月需求量dj 正常生产能力aj 加班生产能力bj 正常生产成本cj 加班生产成本ej 库存能力为I 库存费用hj 设期初 期末库存为零 求费用最小的生产计划 设第月正常生产xj件 加班生产件yj 存储zj件 则 本期生产 上期库存 本期库存 本期需求 OR1 50 第三章对偶问题与灵敏度分析 要求 了解LP对偶问题的实际背景了解对偶问题的建立规则与基本性质掌握对偶最优解的计算及其经济解释掌握LP的灵敏度分析理解计算机输出的影子价格与灵敏度分析的内容 OR1 51 3 1对偶问题 3 1 1对偶问题的提出回顾例题1 现在A B两产品销路不畅 可以将所有资源出租或外卖 现在要谈判 我们的价格底线是什么 OR1 52 对偶模型 设每个工时收费Y1元 设备台时费用Y2元 原材料附加费Y3元 出租收入不低于生产收入 9y1 4y2 3y3 704y1 5y2 10y3 120目标 360y1 200y2 300y3出租收入越多越好 至少不低于某数 OR1 53 原问题与对偶问题之比较 原问题 对偶问题 maxZ 70X1 120X2min 360y1 200y2 300y39X1 4X2 3609y1 4y2 3y3 704X1 5X2 200 3 1 4y1 5y2 10y3 120 3 2 3X1 10X2 300y1 0 y2 0 y3 0X1 0X2 0 OR1 54 3 1 2对偶规则 原问题一般模型 对偶问题一般模型 maxZ CXmin YbAX bYA CX 0Y 0 OR1 55 对偶规则 原问题有m个约束条件 对偶问题有m个变量原问题有n个变量 对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的技术系数矩阵转置后为对偶问题系数矩阵原问题的约束条件与对偶问题方向相反原问题与对偶问题优化方向相反 OR1 56 对偶规则 OR1 57 对偶规则简捷记法 原问题标准则对偶问题标准原问题不标准则对偶问题不标准例题2max 7y1 4y2 2y3minZ 3x1 2x2 6x3 x52y1 y2 y3 32x1 x2 4x3 x4 3x5 7y1 3y3 2x1 2x3 x4 4 4y1 2y2 6 x1 3x2 x4 x5 2y1 y2 y3 0 x1 x2 x3 0 3y1 y3 1x4 0 x5无限制y1 0y2 0y3无约束 OR1 58 3 1 3对偶问题的基本性质 对称性 对偶问题的对偶问题是原问题弱对偶性 极大化原问题的任一可行解的目标函数值 不大于其对偶问题任意可行解的目标函数值 鞍型图 无界性 原问题无界 对偶问题无可行解对偶定理 若一个问题有最优解 则另一问题也有最优解 且目标函数值相等 若原问题最优基为B 则其对偶问题最优解Y CBB 1 OR1 59 3 1 4对偶最优解的经济解释 影子价格 Z CX Yb Z b Yb YZ Yb yibi的意义 Y是检验数的反数 在Y确定的前提下 每增加一个单位的i种资源 对目标函数的贡献 结合例题1讲解影子价格 y1 0 第一种资源过剩y2 13 6 设备台时最紧张 每增加一个台时 利润增加13 6元 y3 5 2 影子价格所含有的信息 1 资源紧缺状况2 确定资源转让基价参见 P403 取得紧缺资源的代价 OR1 60 3 2灵敏度分析 为什么进行灵敏度分析 灵敏度分析的两把尺子 j Cj CBB 1pj 0 xB B 1b 03 2 1价值系数的灵敏度分析Cj变化到什么程度可以保持最优基不变 用 参看P96 例题4 87 5 C2 233 33 36 C1 96 OR1 61 灵敏度分析 右端项的灵敏度分析 bi变化到什么程度可以保持最优基不变 用尺度 xB B 1b 0例题5 1 3 121 16360B 1b 00 4 0 2200 00 0 120 16b3b3的变化范围 227 586 b3 400 OR1 62 其它形式的灵敏度分析 新产品的分析 在资源结构没有变化的条件下 是否生产这种新产品 就看它的竞争力如何 例题6 新增一种C产品 单位利润110元 使用劳动力6工时 设备5台时 原材料7公斤 问要否调整产品结构 先算检验数 j Cj CBB 1pj 6 C6 YP6 110 0 13 6 5 2 6 5 7 T 110 104 4 5 6大于零 有利可图 将P6左乘B 1 加入到末表之中 继续迭代 直到求得最优解 OR1 63 3