《运筹学课件--运筹学完整课件(1-8章)》由会员分享，可在线阅读，更多相关《运筹学课件--运筹学完整课件(1-8章)（362页珍藏版）》请在金锄头文库上搜索。
1、2020 6 17 运筹学 运筹学 OperationsResearch 任课教师 杨学南电话号码 18144251719QQ号码 281068507 数学专业 计算专业学位课程 2020 6 17 运筹学 绪论 1 运筹学简述 2 运筹学的主要内容 3 本课程的特点和要求 4 本课程授课方式与考核 5 运筹学的应用 6 本课程的教材及参考书 本章主要内容 2020 6 17 运筹学 运筹学简述 运筹学 OperationsResearch 系统工程的最重要的理论基础之一 在美国有人把运筹学称之为管理科学 ManagementScience 运筹学所研究的问题 可简单地归结为一句话 依照给定条
2、件和目标 从众多方案中选择最佳方案 故有人称之为最优化技术 2020 6 17 运筹学 运筹学简述 运筹学的历史 运作研究 OperationalResearch 小组 解决复杂的战略和战术问题 例如 如何合理运用雷达有效地对付德军德空袭对商船如何进行编队护航 使船队遭受德国潜艇攻击时损失最少 在各种情况下如何调整反潜深水炸弹的爆炸深度 才能增加对德国潜艇的杀伤力等 2020 6 17 运筹学 运筹学的主要内容 数学规划 线性规划 整数规划 目标规划 动态规划 非线性规划等 图论存储论排队论对策论决策分析 2020 6 17 运筹学 本课程的特点和要求 先修课 高等数学 基础概率 线性代数特点
3、 系统整体优化 多学科的配合 模型方法的应用运筹学的研究的主要步骤 2020 6 17 运筹学 本课程授课方式与考核 讲授为主 结合习题作业 2020 6 17 运筹学 运筹学的应用 运筹学的主要应用涉及几个方面 1 生产计划2 运输问题3 人事管理4 库存管理5 市场营销6 财务和会计7 设备维修 更新和可靠性分析 项目的选择与评价8 工程优化设计9 计算机和信息系统10 城市管理 2020 6 17 运筹学 本课程的教材及参考书 选用教材 运筹学基础及应用 胡运权主编哈工大出版社参考教材 运筹学教程 胡运权主编 第2版 清华出版社 管理运筹学 韩伯棠主编 第2版 高等教育出版社 运筹学 修
4、订版 钱颂迪主编清华出版社 2020 6 17 运筹学 Chapter1线性规划 LinearProgramming LP的数学模型图解法单纯形法单纯形法的进一步讨论 人工变量法LP模型的应用 本章主要内容 2020 6 17 运筹学 线性规划问题的数学模型 1 规划问题 生产和经营管理中经常提出如何合理安排 使人力 物力等各种资源得到充分利用 获得最大的效益 这就是规划问题 线性规划通常解决下列两类问题 1 当任务或目标确定后 如何统筹兼顾 合理安排 用最少的资源 如资金 设备 原标材料 人工 时间等 去完成确定的任务或目标 2 在一定的资源条件限制下 如何组织安排生产获得最好的经济效益 如
5、产品量最多 利润最大 2020 6 17 运筹学 线性规划问题的数学模型 例1 1如图所示 如何截取x使铁皮所围成的容积最大 2020 6 17 运筹学 线性规划问题的数学模型 例1 2某企业计划生产甲 乙两种产品 这些产品分别要在A B C D 四种不同的设备上加工 按工艺资料规定 单件产品在不同设备上加工所需要的台时如下表所示 企业决策者应如何安排生产计划 使企业总的利润最大 2020 6 17 运筹学 线性规划问题的数学模型 解 设x1 x2分别为甲 乙两种产品的产量 则数学模型为 2020 6 17 运筹学 线性规划问题的数学模型 2 线性规划的数学模型由三个要素构成 决策变量Deci
6、sionvariables目标函数Objectivefunction约束条件Constraints 其特征是 1 问题的目标函数是多个决策变量的线性函数 通常是求最大值或最小值 2 问题的约束条件是一组多个决策变量的线性不等式或等式 怎样辨别一个模型是线性规划模型 2020 6 17 运筹学 线性规划问题的数学模型 目标函数 约束条件 3 线性规划数学模型的一般形式 简写为 2020 6 17 运筹学 线性规划问题的数学模型 向量形式 其中 2020 6 17 运筹学 线性规划问题的数学模型 矩阵形式 其中 2020 6 17 运筹学 线性规划问题的数学模型 3 线性规划问题的标准形式 特点
7、1 目标函数求最大值 有时求最小值 2 约束条件都为等式方程 且右端常数项bi都大于或等于零 3 决策变量xj为非负 2020 6 17 运筹学 线性规划问题的数学模型 2 如何化标准形式 目标函数的转换 如果是求极小值即 则可将目标函数乘以 1 可化为求极大值问题 也就是 令 可得到上式 即 若存在取值无约束的变量 可令其中 变量的变换 2020 6 17 运筹学 线性规划问题的数学模型 约束方程的转换 由不等式转换为等式 称为松弛变量 称为剩余变量 变量的变换 可令 显然 2020 6 17 运筹学 线性规划问题的数学模型 例1 3将下列线性规划问题化为标准形式 用替换 且 解 因为x3无
8、符号要求 即x3取正值也可取负值 标准型中要求变量非负 所以 2020 6 17 运筹学 线性规划问题的数学模型 2 第一个约束条件是 号 在 左端加入松驰变量x4 x4 0 化为等式 3 第二个约束条件是 号 在 左端减去剩余变量x5 x5 0 4 第3个约束方程右端常数项为 5 方程两边同乘以 1 将右端常数项化为正数 5 目标函数是最小值 为了化为求最大值 令z z 得到maxz z 即当z达到最小值时z 达到最大值 反之亦然 2020 6 17 运筹学 线性规划问题的数学模型 标准形式如下 2020 6 17 运筹学 线性规划问题的数学模型 4 线性规划问题的解 线性规划问题 求解线性
9、规划问题 就是从满足约束条件 2 3 的方程组中找出一个解 使目标函数 1 达到最大值 2020 6 17 运筹学 线性规划问题的数学模型 可行解 满足约束条件 的解为可行解 所有可行解的集合为可行域 最优解 使目标函数达到最大值的可行解 基 设A为约束条件 的m n阶系数矩阵 m n 其秩为m B是矩阵A中m阶满秩子矩阵 B 0 称B是规划问题的一个基 设 称B中每个列向量Pj j 12 m 为基向量 与基向量Pj对应的变量xj为基变量 除基变量以外的变量为非基变量 2020 6 17 运筹学 线性规划问题的数学模型 基解 某一确定的基B 令非基变量等于零 由约束条件方程 解出基变量 称这组
10、解为基解 在基解中变量取非0值的个数不大于方程数m 基解的总数不超过基可行解 满足变量非负约束条件的基本解 简称基可行解 可行基 对应于基可行解的基称为可行基 2020 6 17 运筹学 线性规划问题的数学模型 例1 4求线性规划问题的所有基矩阵 解 约束方程的系数矩阵为2 5矩阵 r A 2 2阶子矩阵有10个 其中基矩阵只有9个 即 2020 6 17 运筹学 图解法 线性规划问题的求解方法 一般有两种方法 图解法单纯形法 两个变量 直角坐标三个变量 立体坐标 适用于任意变量 但必需将一般形式变成标准形式 下面我们分析一下简单的情况 只有两个决策变量的线性规划问题 这时可以通过图解的方法来
11、求解 图解法具有简单 直观 便于初学者窥探线性规划基本原理和几何意义等优点 2020 6 17 运筹学 图解法 maxZ 2X1 X2X1 1 9X2 3 8X1 1 9X2 3 8s t X1 1 9X2 10 2X1 1 9X2 3 8X1 X2 0 例1 5用图解法求解线性规划问题 2020 6 17 运筹学 图解法 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 4 2X1 X2 20 2X1 X2 17 2 2X1 X2 11 2X1 X2 Lo 0 2X1 X2 7 6 2 D maxZ minZ 此点是唯一
12、最优解 且最优目标函数值maxZ 17 2 可行域 maxZ 2X1 X2 2020 6 17 运筹学 图解法 maxZ 3X1 5 7X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 7 6 2 D L0 0 3X1 5 7X2 maxZ 3 8 4 34 2 3X1 5 7X2 蓝色线段上的所有点都是最优解这种情形为有无穷多最优解 但是最优目标函数值maxZ 34 2是唯一的 可行域 2020 6 17 运筹学 图解法 minZ 5X1 4X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8
13、X1 1 9X2 10 2 D L0 0 5X1 4X2 maxZ minZ 8 5X1 4X2 43 5X1 4X2 0 2 可行域 此点是唯一最优解 2020 6 17 运筹学 图解法 2 4 6 x1 x2 2 4 6 无界解 无最优解 maxZ x1 2x2 例1 6 x1 x2 4 x1 3x2 6 3x1 x2 6 maxZ minZ x1 x2 O 10 20 30 40 10 20 30 40 50 50 无可行解 即无最优解 maxZ 3x1 4x2 例1 7 2020 6 17 运筹学 图解法 学习要点 1 通过图解法了解线性规划有几种解的形式 唯一最优解 无穷多最优解 无
14、界解 无可行解 2 作图的关键有三点 1 可行解区域要画正确 2 目标函数增加的方向不能画错 3 目标函数的直线怎样平行移动 2020 6 17 运筹学 单纯形法基本原理 凸集 如果集合C中任意两个点X1 X2 其连线上的所有点也都是集合C中的点 称C为凸集 2020 6 17 运筹学 单纯形法基本原理 定理1 若线性规划问题存在可行解 则该问题的可行域是凸集 定理2 线性规划问题的基可行解X对应可行域 凸集 的顶点 定理3 若问题存在最优解 一定存在一个基可行解是最优解 或在某个顶点取得 2020 6 17 运筹学 单纯形法的计算步骤 单纯形法的思路 找出一个初始可行解 是否最优 转移到另一
15、个基本可行解 找出更大的目标函数值 最优解 是 否 循环 核心是 变量迭代 结束 2020 6 17 运筹学 单纯形法的计算步骤 单纯形表 2020 6 17 运筹学 单纯形法的计算步骤 例1 8用单纯形法求下列线性规划的最优解 解 1 将问题化为标准型 加入松驰变量x3 x4则标准型为 2020 6 17 运筹学 单纯形法的计算步骤 2 求出线性规划的初始基可行解 列出初始单纯形表 检验数 2020 6 17 运筹学 单纯形法的计算步骤 3 进行最优性检验 如果表中所有检验数 则表中的基可行解就是问题的最优解 计算停止 否则继续下一步 4 从一个基可行解转换到另一个目标值更大的基可行解 列出
16、新的单纯形表 确定换入基的变量 选择 对应的变量xj作为换入变量 当有一个以上检验数大于0时 一般选择最大的一个检验数 即 其对应的xk作为换入变量 确定换出变量 根据下式计算并选择 选最小的 对应基变量作为换出变量 2020 6 17 运筹学 单纯形法的计算步骤 用换入变量xk替换基变量中的换出变量 得到一个新的基 对应新的基可以找出一个新的基可行解 并相应地可以画出一个新的单纯形表 5 重复3 4 步直到计算结束为止 2020 6 17 运筹学 单纯形法的计算步骤 换入列 bi ai2 ai2 0 40 10 换出行 将3化为1 5 3 1 18 0 1 3 0 1 3 10 1 1 3 30 30 0 5 3 0 4 3 乘以1 3后得到 1 0 3 5 1 5 18 0 1 1 5 2 5 4 0 0 1 1 2020 6 17 运筹学 单纯形法的计算步骤 例1 9用单纯形法求解 解 将数学模型化为标准形式 不难看出x4 x5可作为初始基变量 列单纯形表计算 2020 6 17 运筹学 单纯形法的计算步骤 20 x2 2 1 3 1 5 0 1 20 75 3 0 17 1 3
