《202X年如何把事情做到最好》由会员分享，可在线阅读，更多相关《202X年如何把事情做到最好（70页珍藏版）》请在金锄头文库上搜索。
1、OPERATIONSRESEARCH运筹学 怎样把事情做到最好 第一章绪论 1 1题解Operations汉语翻译工作 操作 行动 手术 运算OperationsResearch日本 运用学港台 作业研究中国大陆 运筹学OperationalResearch原来名称 意为军事行动研究 历史渊源 绪论 1 2运筹学的历史早期运筹思想 田忌赛马丁渭修宫沈括运粮Erlang1917排队论Harris1920存储论Levinson1930零售贸易康脱洛维奇1939LP 绪论 1 2运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队 绪论 1 2运筹学的历史管
2、理运筹学阶段战后人员三分 军队 大学 企业大学 课程 专业 硕士 博士企业 美国钢铁联合公司英国国家煤炭局运筹学在中国 50年代中期引入华罗庚推广优选法 统筹法中国邮递员问题 运输问题 1 3学科性质 应用学科Morse Kimball定义 运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法 Churchman定义 运筹学是应用科学的方法 技术和工具 来处理一个系统运行中的问题 使系统控制得到最优的解决方法 中国定义 运筹学是应用分析 试验 量化的方法 对经济管理系统中人力 物力 财力等资源进行统筹安排 为决策者提供有依据的最优方案 以实现最有效的管理 1 4定性与定
3、量 例 店主进货两者都是常用的决策方法定性是基础 定量是工具 定量为定服务 定性有主观性也有有效性 定量有科学性也有局限性 管理科学的发展 定量越来越多 但定量不可替代定性 1 5运筹学的模型 模型 真实事物的模仿 主要因素 相互关系 系统结构 形象模型 如地球仪 沙盘 风洞模拟模型 建港口 模拟船只到达 学生模拟企业管理系统运行 数学模型 用符号或数学工具描述现实系统 V F xi yj uk G xi yj uk 0 1 6运筹学的学科体系 规划论 线性规划 非线性规划 整数规划 目标规划 动态规划图论与网络存储论排队论决策论对策论计算机仿真 1 7运筹学的工作步骤 确定问题搜集数据建立模
4、型检验模型求解模型结果分析结果实施 1 8运筹学与计算机 计算机为运筹学提供解题工具 本书有现成的程序可以利用要学会解题的思路与方法 建立模型很重要 第二章线性规划与单纯形法 2 1LP linearprogramming 的基本概念LP是在有限资源的条件下 合理分配和利用资源 以期取得最佳的经济效益的优化方法 LP有一组有待决策的变量 一个线性的目标函数 一组线性的约束条件 2 1 1LP的数学模型例题1 生产计划问题 某厂生产两种产品 需要三种资源 已知各产品的利润 各资源的限量和各产品的资源消耗系数如下表 例题1建模 问题 如何安排生产计划 使得获利最多 步骤 1 确定决策变量 设生产A
5、产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 人力约束9X1 4X2 360设备约束4X1 5X2 200原材料约束3X1 10X2 300非负性约束X1 0X2 0 例题2 配方问题 养海狸鼠饲料中营养要求 VA每天至少700克 VB每天至少30克 VC每天刚好200克 现有五种饲料 搭配使用 饲料成分如下表 例题2建模 设抓取饲料Ix1kg 饲料IIx2kg 饲料IIIx3kg 目标函数 最省钱minZ 2x1 7x2 4x3 9x4 5x5约束条件 3x2 2x2 x3 6x4 18x5 700营养要求 x1 0 5x2 0 2x3 2x4
6、 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 例题3 人员安排问题 医院护士24小时值班 每次值班8小时 不同时段需要的护士人数不等 据统计 例题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 归纳 线性规划的一般模式 目标函数 max min Z c1x1 c2x2 c3x3 cnxn约束
7、条件 a11x1 a12x2 a13x3 a1nxn b1a21x1 a22x2 a23x3 a2nxn b2 am1x1 am2x2 am3x3 amnxn bn非负性约束 x1 0 x2 0 xn 0 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下方的半平面 所有半平面的交集称之为可行域 可行域内的任意一点 就是满足所有约束条件的解 称之为可行解 例1图示 908060402
8、0 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 概念 概念 1 可行解 满足所有约束条件的解 2 可行域 即可行解的集合 所有约束条件的交集 也就是各半平面的公共部分 满足所有约束条件的解的集合 称为可行域 3 基解 约束条件的交点称为基解 直观 4 基可行解 基解当中的可行解 5 凸集 集合内任意两点的连线上的点均属于这个集合 如 实心球 三角形 结论 可行域是个凸集可行域有有限个顶点最优值在可行域的顶点上达到无穷多解的情形无界解情形无解情形 2 1 3线性
9、规划的标准型 代数式maxZ c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmxj 0j 1 2 n 线性规划的标准型 和式 maxZ cjxj aijxj bii 1 2 mxj 0j 1 2 n j 1 n n j 1 线性规划的标准型 向量式 maxZ CX pjxj bii 1 2 mxj 0j 1 2 nC c1 c2 c3 cn X X1 X2 X3 Xn T n j 1 线性规划的标准型 矩阵式 maxZ CXAX bX 0其中 b b1 b2 bm Ta11a12 a1nA a
10、21a22 a2n am1am2 amn 标准型的特征 目标函数极大化约束条件为等式决策变量非负 非标准型转化为标准型 目标函数极小化转为极大化 minZ max Z 一个数的极小化等价于其相反数的极大化 不等式约束的转化 aijxj bi加入松弛变量 aijxj bi减去剩余变量非正变量 即xk 0则令x k xk自由变量 即xk无约束 令xk x k x k 非标准型转化举例之一 maxZ 70X1 120X2maxZ 70X1 120X29X1 4X2 3609X1 4X2 X3 3604X1 5X2 2004X1 5X2 x4 2003X1 10X2 3003X1 10X2 x5 30
11、0X1 0X2 0Xj 0j 1 2 5 非标准型转化举例之二 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 2 1 4基可行解 基的概念 如前所述LP标准型和式 maxZ cjxj aijxj bixj 0j 1 2 n矩阵式 maxZ CXAX bX 0约束方程的系数矩阵A的秩为m
12、 且m n 设A B N B是A中m m阶非奇异子矩阵 则称B是LP的一个基 即 B是A中m个线性无关向量组 n j 1 n j 1 基解的概念 不失一般性 设B是A的前m列 即B p1 p2 pm 其相对应的变量XB x1 x2 xm T 称为基变量 其余变量XN Xm 1 Xn T称为非基变量 令所有非基变量等于零 则X x1 x2 xm 0 0 T称为基解 基可行解的概念 基可行解 基解可正可负 负则不可行 违背非负性约束条件 称满足所有约束条件的基解为基可行解 退化的基可行解 若某个基变量取值为零 则称之为退化的基可行解 基解的数目 最多Cmn n m n m 例题6基可行解说明 ma
13、xZ 70X1 120X2P1P2P3P4P59X1 4X2 X3 360941004X1 5X2 x4 200A 450103X1 10X2 x5 300310001Xj 0j 1 2 5这里m 3 n 5 Cmn 10 例题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图 2 2单纯形法 2 2 1初始基可行
14、解的确定从系数矩阵中找到一个可行基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 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
15、1 a mnxn b mxm b m a mjxj 单纯形法 一般性表示 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时 达到最优解 单纯形法 2 2 2基变换若存在 j 0 则取max j K 相应之非基变量XK若取非零 将使Z增加 故令XK进基 令XK 0 其余非基变量保持为零 XK原是非基变量 取零值 若XK 0将迫使某个原基变量为零 当XK取值超过任意b i a ik时 将破坏非负性条
16、件 于是令 min b i a ika ik 0 b L a Lk 这时原基变量XL 0 由基变量变成非基变量 a Lk处在变量转换的交叉点上 称之为枢轴元素 j 0 单纯形法解题举例 单纯形表的格式 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为枢轴元素进行迭代 回到第二步 2 3单纯形法的进一步探讨 2 3 1极小化问题直接求解 检验数的判别由所有 j 0即为最优 变为所有 j 0则为最优 人工变量法之一 大M法人工变量价值系数M例人工变量法之二 构造目标函数 分阶段求解例2 3 2无穷多最优解情形 非基变量检验数 j 02 3 3退化解的情形 有两个以上 值相等 2 3 4单纯形法的计算机求解 程序说明应用举例例题1例题2 2 5LP应用举例之一 例13合理下料问题料长7 4米 截成2 9 2 1 1 5米各200根 如何截
