《运筹学第一章.ppt》由会员分享，可在线阅读，更多相关《运筹学第一章.ppt（123页珍藏版）》请在金锄头文库上搜索。
1、运筹学OperationsResearch 授课老师 郑黎黎 考试方式 闭卷考试课堂纪律 手机关机 不要讲话不要睡觉关键词 了解 理解 掌握 熟练掌握 考试与要求 运筹学的产生和发展运筹学的定义与特点运筹学解决问题的过程运筹学的主要研究内容参考文献 绪论 运筹学在英国被称为 运筹学的产生和发展 运筹学在美国被称为 1957年我国 operationalresearch operationsresearch 缩写为O R 夫运筹帷幄之中 决胜于千里之外 汉书 1957年我国将O R 译为 运筹学 运筹学思想的出现可以追溯到很早以前 田忌齐王赛马 对策论 丁谓修宫 网络计划 等都体现了优化的思想
2、运筹学的产生和发展 田忌赛马齐王要与大臣田忌赛马 双方各出上 中 下马各一匹 对局三次 每次胜负1000金 田忌在好友 著名的军事谋略家孙膑的指导下 实施的对策为 齐王上中下田忌下上中最终净胜一局 赢得1000金 运筹学思想的出现可以追溯到很早以前 田忌齐王赛马 对策论 丁谓修宫 网络计划 等都体现了优化的思想 运筹学 作为科学概念最早出现在第二次世界大战期间 美 英等国家的作战研究小组为了解决作战中所遇到的许多错综复杂的战略 战术问题而提出的 如水雷的布置 对深水潜艇的袭击 商船护航的规模等等 运筹学的产生和发展 战后这些研究成果被应用到生产 经济领域 其发展可以分为三个阶段 1945至50
3、年代初期 创建时期 运筹学的产生和发展 1948年英国成立 运筹学俱乐部 在煤力 电力等部门推广应用运筹学相继一些大学开设运筹学课程1948年美国麻省理工学院1950年英国伯明翰大学1950年第一本运筹学杂志 运筹学季刊 在英国创刊1952年第一个运筹学学会在美国成立1947年丹齐克在研究美国空军资源优化配置时提出线性规划及其通用解法 单纯形法 战后这些研究成果被应用到生产 经济领域 其发展可以分为三个阶段 1945至50年代初期 创建时期50年代初期至50年代末期 成长时期 运筹学的产生和发展 战后这些研究成果被应用到生产 经济领域 其发展可以分为三个阶段 1945至50年代初期 创建时期5
4、0年代初期至50年代末期 成长时期 运筹学的产生和发展 此阶段的一个特点是电子计算机技术的迅速发展 使得运筹学中一些方法如单纯形法 动态规划方法等 得以用来解决实际管理统中的优化问题 促进了运筹学的推广应用 50年代未 美国大约有半数的公司在自己的经营管理中应用运筹学 如用于制订生产计划 资源分配 设备更新等方面的决策 另一个特点是有更多刊物 学会出现 战后这些研究成果被应用到生产 经济领域 其发展可以分为三个阶段 1945至50年代初期 创建时期50年代初期至50年代末期 成长时期自60年代来 运筹学迅速普及和迅速发展时期 运筹学的产生和发展 此阶段的特点是运筹学进一步细分为各个分支 专业学
5、术团体的迅速增多 更多期刊的创办 运筹学书籍的大量出版以及更多学校将运筹学课程纳入教学计划之中 第三代电子数字计算机的出现 促使运筹学得以用来研究一些大的复杂的系统 如城市交通 环境污染 国民经济计划等 战后这些研究成果被应用到生产 经济领域 其发展可以分为三个阶段 1945至50年代初期 创建时期50年代初期至50年代末期 成长时期自60年代来 运筹学迅速普及和迅速发展时期 运筹学在我国的发展 运筹学的产生和发展 运筹学的定义与特点 运筹学 OperationsResearch 直译为 运作研究 美国运筹学会认为 运筹学所研究的问题 通常是在要求有限资源的条件下科学地决定如何最好地设计和运营
6、人机系统 中国大百科全书释义 它用数学方法研究经济 民政和国防等部门在内外环境的约束条件下合理分配人力 物力 财力等资源 使实际系统有效运行的技术科学 它可以用来预测发展趋势 制定行动规划或优选可行方案 运筹学的定义与特点 还有人 运筹学是一门应用科学 它广泛应用现有的科学技术知识和数学方法 解决实际问题中提出的专门问题 为决策者选择最优决策提供定量依据 特点 系统寻优 多学科综合 辅助决策系统 是由相互关联 相互制约 相互作用的一些部分组成的具有某种功能的有机整体 运筹学研究吸收来自不同领域 具有不同经验和技能的专家为制定决策提供科学依据是运筹学的核心 运筹学解决问题的过程 运筹学解决问题的
7、过程主要包括以下几个步骤 分析和表述问题 这是对问题的定性分析过程 建立模型 运筹学模型大都包括两个部分 目标函数和约束条件 建立模型的过程就是用参数 决策变量表达目标函数 约束条件 运筹学解决问题的过程 模型求解 用各种手段求解模型 解的精度要求可由决策者提出 模型的测试 首先将历史数据输入模型 研究得到的解与历史实际的符合程度 建立对解的有效控制 任何模型都有适用范围 解是否有效 要注意模型是否有效 方案实施 将方案应用的实践中 并检验方案的可行性 若不可行重新进行上述过程 运筹学解决问题的过程 例1 某工厂生产 和 两种型号计算机 生产 型和 型计算机所需要原料分别为2和3个单位 需要的
8、工时分别是4和2个单位 在计划期内可以使用的原料的100个单位 工时为120个单位 已知生产每台 型计算机可获利润分别为6个单位和4个单位 试确定获得最大利润的生产方案 运筹学解决问题的过程 目标函数 约束条件 设z为获得的利润 和分别为生产 型和 型计算机台数 线性规划 运筹学的主要研究内容 运筹学的主要研究内容 运输问题 运输问题 线性规划非线性规划动态规划 运筹学的主要研究内容 有些经营管理活动由一系列相互关联的阶段组成 在每个阶段依次进行决策 而且上一阶段的输出状态就是下一阶段的输入状态 且各阶段决策之间相互关联 构成一个多阶段的决策过程 线性规划非线性规划动态规划 运筹学的主要研究内
9、容 某厂新购某种机床125台 据估计 这种设备5年后将被其它设备所取代 此机床如在高负荷状态下工作 年损坏率为1 2 年利润为10万元 如在低负荷状态下工作 年损坏率为1 5 年利润为6万元 问应如何安排这些机床的生产负荷 才能使5年内获得最大利润 线性规划非线性规划动态规划 图与网络分析把一些研究对象用节点表示 对象之间用边表示 点 边的集合构成图 运筹学的主要研究内容 线性规划非线性规划动态规划 图与网络分析 运筹学的主要研究内容 线性规划非线性规划动态规划 图与网络分析存贮论 用于研究存贮策略的理论和方法 为保障企业生产顺利进行 需要一定数量的原材料和零部件的储备 以调节供需不平衡 需求
10、量可以是常数 也可以是随机变量 提出订货后 货物可以一批到达也可以分批到达 某些情况下允许缺货 有些情况下不允许缺货 存贮策略研究在不同需求 供货及到达方式等情况下 确定在什么时间点及一次提出多大批订货量 使用于订购 贮存和可能发生短缺的费用和最少 运筹学的主要研究内容 线性规划非线性规划动态规划 图与网络分析存贮论排队论 运筹学的主要研究内容 线性规划非线性规划动态规划 图与网络分析存贮论排队论对策论研究具有对抗局势的模型 在这里模型中参与对抗的各方称为局中人 每个局中人均有一组策略可供选择 当采取不同的策略是对应一个收益函数 对策论为局中人提供一套完整的 定量化和程序化的选择策略的理论和方
11、法 运筹学的主要研究内容 线性规划非线性规划动态规划 图与网络分析存贮论排队论对策论决策论决策是指为最优达到目标 依据一定准则 对若干备选行动的方案进行抉择 运筹学的主要研究内容 参考文献 胡运权 运筹学教程 M 北京 清华大学出版社 2007年 钱颂迪 运筹学 M 北京 清华大学出版社 1990年 郭立夫 运筹学 M 长春 吉林大学出版社 2002年 胡运权 运筹学习题集 M 北京 清华大学出版社 2003年 倪本会 刘继泉编著 交通工程概论 M 北京 人民交通出版社 2006年 线性规划与单纯形法 线性规划 Linearprogramming 是运筹学的重要分支 是研究在一组线性等式或者不
12、等式约束下 使得某一线性目标函数取得最大 最小 的极值问题 1947年美国人丹齐克提出了用于求解线性规划的单纯形法 例2 美佳公司计划制造 两种家电产品 各制造一件时分别占用的设备A B的台时 调试时间及每天这两种家电可用能力 各售出一件时获利情况如表所示 问公司应制造两种家电各多少台 使获取的利润最大 线性规划问题及其数学模型 线性规划问题及其数学模型 例3 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下 设司乘人员在各时间段一开始时上班 并连续工作八小时 问该公交线路至少要配备多少司乘人员 线性规划问题的数学模型和图解法 目标函数 约束条件 线性规划问题的数学模型和图解法 设
13、为各班新上班人数 线性规划问题的特征 每个问题都用一组未知变量表示目标函数和约束条件 有一个目标函数 并且这个目标可表示为一组未知量的线性函数 目标函数可以是求最大也可以求最小 存在一组约束条件 这些约束条件都可以用一组未知量线性等式或不等式表示 线性规划问题的数学模型和图解法 目标函数 约束条件 线性规划问题数学模型的一般形式 其中 为价值系数 为资源系数 为技术系数 或约束系数 线性规划问题及其数学模型 线性规划问题数学模型的标准型 目标函数 约束条件 其中 为价值系数 为资源系数 为技术系数 或约束系数 线性规划问题及其数学模型 线性规划的标准形式有四个特点 目标最大化 约束为等式 右端
14、项非负 决策变量均非负 对于各种非标准形式的线性规划问题 我们总可以通过以下变换 将其转化为标准形式 线性规划问题及其数学模型 1 极小化目标函数的问题设目标函数为 则可以令 该极小化问题与下面的极大化问题有相同的最优解 线性规划问题及其数学模型 2 约束条件不是等式的问题设约束条件为 则可在约束的左端加上一个非负变量使上面的约束这个不等式约束变为等式约束 松弛变量 线性规划问题及其数学模型 同理 对于不等式约束 则可在约束的左端减去一个非负变量 则这个不等式约束变为 这个非负变量称为松弛变量或剩余变量 线性规划问题及其数学模型 线性规划问题的标准型 3 变量无符号限制的问题在标准形式中 必须
15、每一个变量均有非负约束 当某一个变量没有非负约束时 可以令 其中 即用两个非负变量之差来表示一个无符号限制的变量 当然的符号取决于和的大小 4 对于可以令 显然 5 右端项有负值的问题在标准形式中 要求右端项必须每一个分量非负 当某一个右端项系数为负时 如 则把该等式约束两端同时乘以 1 得到 线性规划问题及其数学模型 线性规划问题的标准型 若设 1 矩阵式 线性规划问题的标准型 2 向量式3 和式 在后面的公式推导中矩阵式和向量式用的比较多 线性规划问题的数学模型和图解法 图解法求解线性规划问题的步骤 分别取决策变量x1 x2为坐标向量建立直角坐标系 确定可行域 对每个不等式约束 包括非负约
16、束 条件 先画出其等式在直角坐标系中的直线 然后确定约束不等式所决定的半平面 各约束半平面交出来的区域即为可行域 图示目标函数 最优解的确定 线性规划问题的标准型和解的概念 例2的可行域表示 利用图解法求解例2的最优解 线性规划问题的标准型和解的概念 例2的可行域表示 利用图解法求解例1的最优解 线性规划问题的标准型和解的概念 图示目标函数和最优解的确定 1 1d 查看目标函数和可行域的关系 寻找线性规划问题的最优解 先将目标函数变为 求解Q2 得到问题最优值 线性规划问题的标准型和解的概念 因此 美佳公司每天制造家电 3 5件 家电 1 5件 能获得的最大利润是8 5元 线性规划问题的标准型和解的概念 无穷多个最优解情况 将例2的目标函数变为 线性规划问题的标准型和解的概念 无界解 例2只包含约束1 1a 1 1d 线性规划问题的标准型和解的概念 无可行解情况如果约束条件中存在相互矛盾的约束时 可行域为空 问题无可行解 线性规划问题的标准型和解的概念 从图解法可以看到 当线性规划问题的可行域非空时 它的可行域是有界或无界凸多边形 若线性规划存在最优解 它一定是在可行域的某个顶点得到
