MBA课程数据模型与决策线性规划.ppt

1 数据模型与决策 西安理工大学经济与管理学院陕西省城市发展战略研究所 学科沿革 本学科原名 运筹学 2000 3在上海复旦大学召开的 教学研讨会上通过决议 更名为 数据模型与决策 在原来运筹学的基础上 增加了数据分析的部分内容 形成了现在的模式 教学总学时仍为50学时 显示目录 MBA学位课 熊义杰教授 DataModelsandDecisions 2 关于主讲人 百度百科 3 开头的话 教学内容 按照2011新大纲分三大块 一线性规划 LinearProgramming简记 LP 含对偶规划与运输问题 二博弈分析 主要讲二人有限零和博弈 三决策论 Decision makingTheory 简记 DT 4 2011新大纲分析 新大纲三部分计划学时 共67学时 第一篇数据分析基础 21学时 第二篇优化模型 18学时 其中选授3课时 第三篇决策理论与方法 18学时 其中选授3课时 大纲在最后的说明中指出 全部内容分为必授内容和选授内容 必授内容建议40学时 全部内容为60学时 观点 1 总学时显多 2 数据分析部分比重过大 3 优化模型更适合MBA学员特点 学员的学习兴趣更浓厚 5 关于教材 第1版 国防工业出版社2004 01第2版 国防工业出版社2007 08 21世纪高等院校规划教材 21世纪高等院校优秀教材 链接材料一 链接材料二 6 教材获奖情况 红头文件 参 西安理工大学文件 西理教24号 关于2009年校级优秀教材评选和教材建设立项资助结果的通告 签发人 高勇 7 如何学好本课程 一 预修好基础课概率论及线性代数 必须预修课程 经济学 非经济学专业预修课程 管理学 非管理专业预修课程 MasterofBusinessAdministrationManagementBuildsAchievements 二 端正学习态度 8 一位哲学家 培根 说过 哲学可以使人善辩 历史可以使人明智 数学可以使人逻辑 美国是如何培养精英的 一书的作者 在他为他的书写的 序 里这样说过 他认识的一位钢琴老师相当自豪地介绍说 她的学生许多上了哈佛 MIT 布朗 其中有立志当医生的 有准备学科学的 真正要投身音乐专业的很少 包括两个她称为有 上帝赋予的天分 的孩子 也没有当钢琴家的计划 反而一个平平之辈 说要进音乐学院 9 他分析道 表面上看 明知道孩子不搞专业还这样下血本学钢琴 半小时的课50美元 一年下来 一个孩子总要上万美元 似乎很不理性 但仔细分析 就能解读出这些家长在孩子身上希望着什么 一上课就知道 弹钢琴几乎是对孩子的智力和心灵最大的挑战 小小年纪 刚刚开始读书 就得认读五线谱 同时手要跟着谱子弹出音乐来 又要把自己的感情表达出来 这一套不仅需要调动各方面的智能和感性 而且需要高度的纪律和刻苦精神 孩子要是能对付这些 你就不觉得她还有什么别的东西不能对付 所以老师十分得意地说 我的学生长大后干什么的都有 都非常出色 因为学了这些以后 学什么都快 10 教学方式 1课堂讲授2案例讨论 分析3上机实验1平时作业 加考勤占20 2案例报告 占30 3考试 50 考察方式 11 运筹学简介运筹学公认起源于二次世界大战期间英美等国的军事运筹小组 这些小组的主要任务是进行Operationalresearch 运作研究 或Operationalanalysis 运作分析 二战后 运筹学的研究主要转向经济方面 重点集中在如何用一定的投入生产更多的产出 或一定的产出如何用更少的投入来生产 从而使运筹学在管理科学中获得了长足的发展 经过50多年的发展 运筹学已成为一个门类齐全 理论完善 有着广泛应用前景的新兴的学科门类 究竟什么是运筹学 目前流行的说法比较多 从本学科的研究对象 内容和性质出发 在这里 我们把运筹学定义为 针对特定的管理决策问题 依照给定的目标和条件 从众多方案中选择最优方案的一种最优化技术和方法 运筹学的内容相当丰富 分支也很多 根据其解决问题的主要特点可将其分为两大类 即确定型模型和概率型模型 确定型模型主要包括 线性规划 整数规划 非线性规划 目标规划 动态规划 图与网络等 概率型模型主要包括决策论 对策论 排队论 存贮论以及可靠性理论等 数据模型与决策 的以下部分将主要介绍线性规划 对偶规划 运输问题和决策论等内容 12 第1章线性规划及其解法 1 1线性规划的认识 1 2线性规划的应用举例 1 3线性规划的基本理论 1 4线性规划的求解 MBA 数据模型与决策 13 1 1 1 什么是线性规划 第1章线性规划及其解法 1 1线性规划的认识 线性规划 Linearprogramm 是运筹学中研究较早 发展较快 应用较广 比较成熟的一个分支 它实质上是解决稀缺资源在有竞争的使用方向中如何进行最优分配的问题 即寻求整个问题的某个整体指标最优的问题 比如 经营管理中的 1 运输问题 2 生产组织与计划安排问题 3 合理下料问题 4 配料问题 5 布局问题等 什么是线性规划 14 1 1 2线性规划问题举例例1 1一个最大化问题某家具厂生产桌子和椅子两种家具 有关资料如下表 桌子椅子可供量木工4小时 张3小时 把120小时 月油漆工2小时 张1小时 把50小时 月售价50元 张30元 把 问该厂如何安排生产才能使每月销售收入最大 解 1 确定决策变量 设x1为桌子生产量 x2为椅子生产量2 确定目标函数 max z 50 x1 30 x23 确定约束方程 木工约束 4x1 3x2 120油漆工约束 2x1 x2 50 15 4 变量取值限制 x1 0 x2 0把以上四个部分合起来 有 max z 50 x1 30 x2s t 4x1 3x2 120 s t Subjectto 2x1 x2 50 x1 0 x2 0这就是一个最大化的线性规划模型 例1 2一个最小化问题有一种生猪催肥用的简易配合饲料由粗玉米粉和骨粉两种原料组成 有关资料如下表 粗玉米粉骨粉催肥最低要求热值4mc kg2mc kg8mc 日蛋白含量30g kg60g kg96g 日售价3元 公斤5元 公斤注 mc为百万卡路里 millioncalorie 一个最小化问题 16 解 设 分别为两种原料的配给额 则有 minz 3 5 s t 4 2 8 30 60 96 0 这是一个最小化的线性规划模型 问这两种原料应怎样配合才能在满足最低要求的条件下使总成本最低 例1 2模型 17 1 1 3 线性规划的一般式 标准式和矩阵式 由以上二例可知 线性规划就是求一个线性函数在满足一组线性等式或不等式方程在变量为非负条件下的极值问题的总称 它一般由三部分组成 1 由决策变量构成的反映决策目标的线性目标函数 2 一组由线性等式或不等式组成的关于决策变量的约束方程式 3 限制决策变量取值的非负约束 线性规划的一般形式为 s t 1 1 线性规划的一般式 18 线性规划的标准型规定如下 s t 线性规划的标准型要求所有的约束必须为等型约束 所有的变量为非负 类型变量 对目标函数的类型原则上没有硬性规定 但为了讨论方便 规定 任何一个非标准的线性规划都可以通过以下三个方面的途径转化为标 准型 1 将最小化的目标函数转化为最大化的目标函数 即 minf x max f x 如求min 1 x2 显然有最小值f 0 1 如改为最大化则为 max 1 x2 1 1 2 线性规划的标准式 以目标函数的最大化 Max 为标准型 19 2 把不等约束转化为等式约束 小于等于约束可引入 一正的松弛变量或 剩余变量 如 可变为 10 大于等于约束 可引入 一负的松弛变量 如 可变为 0 3 把所有变量取值约束转化为非负约束 若变量取值为非正 如 0 即令 0 代入原模型即可 若变量为自由变量 则可作变量的代换 令 0 0 即可 线性规划的标准式 1 2 还可以用矩阵式表示如下 max cx s t Ax b x 0 式中 x n x x x 2 1 A b 矩阵形式的主要优点是便于进一步研究 1 3 矩阵式为 20 例1 3试将下列线性规划模型标准化 ClickmousetoshowAnswers 21 1 2线性规划应用举例 线性规划应用举例 本部分拟采用自学与讲授相结合的方式教学 请同学们先阅读教材中第11页的例1和第17页的例2 然后再阅读第四章 阅读时请注意把握LP建模的要点 1 先考虑应设那些变量 2 其次考虑目标函数是什么 3 最后考虑各种限制因素 22 某企业生产甲乙丙三种产品 每一产品均须经过AB两道工序 A工序有两种设备可完成 B工序有三种设备可完成 甲产品的两道工序和乙产品的A工序可随意安排 其余只能在要求的设备上完成 有关资料如下表 试制定利润最大的产品加工方案 x1 x2 x3 x4 x5计算结果 x1 1200 x2 230 05 x3 0 x4 858 62 x5 571 43 x6 0 x7 500 x8 324 14 Z 1146 60 例1 4 教材p46 分析示例 23 1 3线性规划的基本理论 1 3 1线性规划的图解法对于只有两个变量的线性规划问题 可应用图解法求解 求解的步骤是 1 以X2为纵轴X1为横轴画平面直角坐标系 2 依次画出每条约束线和变量约束 并描出可行域方向 3 任取一目标函数值画出目标函数线 然后根据目标函数类型将该线平移至可行域边界 这时目标函数与可行域的交点即最优可行解 代入目标函数即得最优值 现对下面的例子应用图解法求解 Maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 例1 5 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解Z 4 3 14 3 46 3 6 4 8 6 0 x1 x2 例1 5唯一解的例子 注意 1 这里目标函数在可行域内移动的方向 是朝着增大纵截距的方向移动的 2 最优解为两约束线之交点的必要条件 是目标函数斜率介于两约束线斜率之间或目标函数线介于二约束线之间 比如 如果目标函数的斜率为 2 则最优解为 6 0 点 如果目标函数斜率为3 4 则最优解为 0 4 点 25 例1 6唯一解的例子Maxz 3X1 X23X1 2X2 3 1 5X1 4X2 10 2 2X1 X2 5 3 X1 X2 0 4 13 7 9 7 2 0 0 0 0 5 唯一最优解Z 13 7 9 7 30 7 下面再看一个唯一解的例子 一个有意义的线性规划应该是具有唯一解的线性规划 这个例子有三条约束线 1 X2 注意 在唯一解条件下 如何找最优点是个重要问题 这通常要看目标函数的类型 对于最大化问题 如果在关于X2的函数中 截距Z为正值 如例2 5 目标函数线应在可行域内向增大纵截距的方向移动 如果在关于X2的函数中 截距Z为负值 如本例 目标函数线应在可行域内向减小纵截距的方向移动 对于最小化问题 目标函数线在可行域内移动的方向则应与上述两种情况相反 1 2 3 X2 z 3X1 26 课堂练习 试用图解法解例1 1和例1 2 图1 2 例1 2的图解 Z 1 6 0 8 8 8元 图1 1Z 15 20 1350元 ClickmousetoshowAnswers 27 4 2 4 0 0 0 2 3 用图解法解下面的例子Maxz 2X1 4X2X1 2X2 8 1 4X1 16 2 4X2 12 3 X1 X2 0 4 例1 7无穷多解的例子 无穷多最优解 注意 多重解产生的原因 是因为目标函数线与第 1 条约束线的斜率相等 1 2 3 8 0 0 4 28 例1 8无界解的例子Maxz x1 x2 x1 x2 4 1 x1 x2 2 2 x1 x2 0 3 2 0 0 4 0 0 无界解 不等于无可行解 在这里需要注意的是 可行域无界不等于问题无界 这要看目标函数的情况 如把该问题中目标函数x1的系数由原来的1改为 3 2时 该问题有最优解Z 0 4 4 clicktoshowus 29 例1 9无可行解的例子Maxz 2x1 3x2x1 2x2 8 1 4x1 16 2 4x2 12 3 2x1 x2 4 4 x1 x2 0 5 2 0 0 4 4 0 4 2 无可行解 约束条件无共同区域 30 图解法的重要结论 1 线性规划问题的可行域是凸集 即凸多边形 2 若LP存在最优解 一定在可行域的某个顶点上得到 3 线性规划的解通常会有四种情况 即唯一解 无穷多解 无界解和无可行解 31 1 3 2线性规划解的几何意义及有关概念在一个线性规划问题中 每一个约束条件 包括资源约束与非负约束 实际上都只是由满足该不等式的所有解集构成的平面坐标中的一个半平面 三维坐标中为半空间 而所有的这些半平面中的共同部分 就构成了这个线性规划问题的解域 即可行域 如果用sj表示每一个半平面 用S表示可行域 则有S s1 s2 sm n 其中 可行域中的每一个点 为一n维向量可等价地表示为S x Ax b x 0 都称为可行解 如果S为一空集 即该问题存在矛盾约束且没有可行解 称该线性规划问题不可行 线性规划解的几何意义及有关概念 32 能够使目标函数取得极值的可行解就是最优解 但此时尚存在有界最优解和无界最优解两种可能 在S为非空的情况下 可行域可能是封闭的 也可能是不封闭的 封闭的可行域是有界可行域 否则就是无界可行域 如例1 2 如果一个线性规划问题的可行域是非空的有界可行域 则该问题一定有有界最优解 如线性规划问题的可行域无界 则该问题虽有可行解 但不一定有有界最优解 可行域无界不一定意味着线性规划问题无解 这取决于目标函数改善的方向 如果目标函数改善的方向与可行域无界的方向相反 则必存在有界最优解 33 为便于进一步讨论 现给出有关定义 定义1 1给定线性规划问题P max cx Ax b x 0 A是m n阶满秩矩阵 n m B是任一个m m阶满秩子矩阵 则称B是P的一个基 或基矩阵 一般线性规划通常最多可以有个基 不失一般性 通常假定B的m个列向量是A中的前m个列向量 与基相对应的变量称作基变量 用xB表示 余下的变量称作非基变量 用xN表示 如果所有的非基变量都可以取零值 则约束方程Ax b可改写为 BxB b 1 4 这是因为 A B N 由于B是满秩阵 式 1 4 必有唯一解xB B 1b 基 基变量和非基变量的概念可简单图示如下 见下页 线性规划的基本概念 线性规划的基矩阵 基变量 非基变量 目标函数 约束条件 行列式 0基矩阵 右边常数 在本例中 最多可以有 120基矩阵 35 定义1 2设B是P的一个基 解x B 1b 0 T称作对应于B的基本解 满足非负条件的基本解称作基本可行解 该解对应的基称作可行基 一般的LP解中最多可以有m个分量取非零值 各种解间的关系可由图1 3 维恩图或集合示意图 表示 非可行解 基本解 可行解 基本可行解 图1 3 定义1 2 36 例1 10找出下列LP问题的全部基本解 指出基本可行解和最优解 37 定义 1 3 一个基本可行解中如果存在取零值的基变量 则该解称作退 化的基本可行解 该解对应的基称作退化基 如果有关的线性规划问题的所 有基本可行解都是非退化解 则该问题称作非退化的 线性规划问题 由于退化会引起线性规划求解的困难 因此 在研究中通常总是假定 所研究的问题为非退化的线性规划问题 退化基本可行解中的非零分量一定小于 m 非退化解中的非零分量 一定等于 m 定义 1 4 凸集 若连接 n 维点集 S 中任意两点 和 的线段仍 在 S 中 则称 S 为凸集 换言之 若有 则称 S 为凸集 两点坐标值的加权平均必在两点的连线上 定义 1 5 极点 若凸集 S 中 的点 x 不能成为 S 中任何线段的内点 则 称 x 为 S 的极点 换言之 若对于任意两点 不存在 使得 则称 x 为极点 定义1 3 1 5 凸集和极点可用图表示如下 见下页 可行域的性质 线性规划的可行域是凸集基本可行解都在极点上最优解必在极点上达到 凸集 凸集 不是凸集 极点 39 1 3 3线性规划解的基本定理 定理 1 1 性规划问题所有可行解组成的集合 S 是凸集 这一定理的等价表述为 联结线性规划问题的任意两个可行解的线 段上的点仍是可行解 证 设线性规划问题的可行解集 S 其中任意两个可行解为 又 即 x 也是可行解 换言之 x 的集合 S 为凸集 定理1 1 40 定理1 2 x是线性规划问题之基本可行解的充要条件是x为可行域S x Ax b x 0 上的极点 这一定理的另一等价表达式为 可行解集S中的点x是极点的充要条件是x为基本可行解 证明略 定理1 3 线性规划的最优值必在极点上达到 证明略 注意 该定理仅适用于唯一解的情况 对多重解不适用 定理1 2 1 3 41 1 4 1运用 管理运筹学2 解线性规划运用 管理运筹学2 求解线性规划的步骤 以解例2 1为例 是 在主画面上选 线性规划 输入变量数和约束条件数 并选择目标函数类型 然后 确定 输入目标函数系数 约束条件和变量约束 如果变量有大于0的上限 可作为约束方程处理 4 求解 例2 1求解演示 1 4线性规划的解法 42 1 4 2 管理运筹学 输出结果的识读 最优解如下 目标函数最优值为 1350变量最优解相差值 x1150 x2200约束松弛 剩余变量对偶价格 10520