运筹学案例ppt课件

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进基变量