运筹学3课件.pptVIP

分配问题与匈牙利法 分配问题与匈牙利法 分配问题与匈牙利法 分配问题与匈牙利法 分配问题与匈牙利法 分配问题与匈牙利法 分配问题与匈牙利法 课堂练习：用匈牙利法求解下列指派问题。 分配问题与匈牙利法 分配问题与匈牙利法 非标准型的指派问题： 分配问题与匈牙利法 1. 最大化指派问题 分配问题与匈牙利法 解: M＝95，令 分配问题与匈牙利法 2. 不平衡的指派问题 分配问题与匈牙利法 3. 一个人可做几件事的指派问题 分配问题与匈牙利法 4. 某事一定不能由某人做的指派问题 分配问题与匈牙利法 解: 1) 这是不平衡的指派问题，首先转换为标准型，再用匈牙利法求解。 2) 由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作E必须完成，故设戊完成E的时间为M（M为非常大的数），其余效率系数为0，则标准型的效率矩阵表示为： 分配问题与匈牙利法 用匈牙利法求出最优指派方案为： Chapter5 目标规划( Goal programming ) 目标规划问题及其数学模型 问题的提出： 目标规划是在线性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。 由于现代化企业内专业分工越来越细，组织机构日益复杂，为了统一协调企业各部门围绕一个整体的目标工作，产生了目标管理这种先进的管理技术。目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，考虑现有资源情况，分析如何达到规定目标或从总体上离规定目标的差距为最小。 目标规划问题及其数学模型 例5.1 某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。 目标规划问题及其数学模型 解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型： 目标规划问题及其数学模型 目标规划问题及其数学模型 线性规划模型存在的局限性： 1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。 2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。 3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。 4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。 目标规划问题及其数学模型 目标规划怎样解决上述线性规划模型建模中的局限性？ 目标规划问题及其数学模型 目标规划问题及其数学模型 ∵正负偏差不可能同时出现，故总有： x1－x2+d--d+ =0 目标规划问题及其数学模型 3）设备B必要时可加班及加班时间要控制，目标约束表示为： 目标规划问题及其数学模型 目标规划问题及其数学模型 上述目标规划模型可以表示为： 目标规划问题及其数学模型 目标规划问题及其数学模型 用目标规划求解问题的过程： 目标规划的图解分析法 目标规划的图解分析法 3. 求满足最高优先等级目标的解 4. 转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解 5. 重复4，直到所有优先等级的目标都已审查完毕为止 6. 确定最优解和满意解。 目标规划的图解分析法 例5.2 用图解法求解下列目标规划问题 目标规划的图解分析法 目标规划的图解分析法 目标规划的图解分析法 目标规划应用举例 例5.5 已知一个生产计划的线性规划模型如下，其中目标函数为总利润，x1,x2 为产品A、B产量。 目标规划应用举例 目标规划应用举例 Chapter6 图与网络分析( Graph Theory and Network Analysis ) 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图论中图是由点和边构成，可以反映一些对象之间的关系。 一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。 图的基本概念与模型 图的基本概念与模型 定义: 图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1]; e2=[v1,v2]; 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的基本概念与模型 图的模型应用 图的基本概念与模型 解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。 图的基本概念与模型 一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，