《运筹学3.ppt》由会员分享，可在线阅读，更多相关《运筹学3.ppt（80页珍藏版）》请在三一文库上搜索。
1、分配问题与匈牙利法,2）试指派（找独立0元素）,独立0元素的个数l45，故画直线调整矩阵。,分配问题与匈牙利法,选择直线外的最小元素为1；直线外元素减1，直线交点元素加1，其他保持不变。,分配问题与匈牙利法,l =m=4 n=5,选择直线外最小元素为1，直线外元素减1，直线交点元素加1，其他保持不变，得到新的系数矩阵。,分配问题与匈牙利法,总费用为=5+7+6+6+4=28,注：此问题有多个最优解,分配问题与匈牙利法,总费用为=7+9+4+3+5=28,分配问题与匈牙利法,总费用为=8+9+4+3+4=28,分配问题与匈牙利法,课堂练习：用匈牙利法求解下列指派问题。,练习1：,练习2：,分配问
2、题与匈牙利法,48,21,答案：,分配问题与匈牙利法,非标准型的指派问题：,匈牙利法的条件是：模型求最小值、效率cij0。 当遇到各种非标准形式的指派问题时，处理方法是先将其转化为标准形式，然后用匈牙利法来求解。,分配问题与匈牙利法,1. 最大化指派问题,处理方法：设m为最大化指派问题系数矩阵C中最大元素。令矩阵B（m-cij）nn则以B为系数矩阵的最小化指派问题和原问题有相同的最优解。,例4.9 某人事部门拟招聘4人任职4项工作，对他们综合考评的 得分如下表（满分100分），如何安排工作使总分最多。,分配问题与匈牙利法,解: M95，令,用匈牙利法求解C，最优解为：,即甲安排做第二项工作、乙
3、做第三项、丙做第四项、丁做第三项, 最高总分Z92959080357,分配问题与匈牙利法,2. 不平衡的指派问题,当人数m大于工作数n时，加上mn项虚拟工作，例如：,当人数m小于工作数n时，加上nm个人，例如,分配问题与匈牙利法,3. 一个人可做几件事的指派问题,若某人可做几件事，则将该人化作相同的几个“人”来接受指派，且费用系数取值相同。,例如：丙可以同时任职A和C工作，求最优指派方案。,分配问题与匈牙利法,4. 某事一定不能由某人做的指派问题,将该人做此事的效率系数取做足够大的数，可用M表示。,例4.10 分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务。每个人完成各项任务的时间如
4、表所示。由于任务数多于人数，考虑任务E必须完成，其他4项中可任选3项完成。试确定最优分配方案，使完成任务的总时间最少。,分配问题与匈牙利法,解: 1) 这是不平衡的指派问题，首先转换为标准型，再用匈牙利法求解。 2) 由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作E必须完成，故设戊完成E的时间为M（M为非常大的数），其余效率系数为0，则标准型的效率矩阵表示为：,分配问题与匈牙利法,用匈牙利法求出最优指派方案为：,即甲B，乙D，丙E，丁A, 任务C放弃。 最少时间为105。,Chapter5 目标规划 ( Goal programming ),目标规划问题及其数学模型 目标规划的图解分
5、析法 目标规划应用举例,本章主要内容：,目标规划问题及其数学模型,问题的提出： 目标规划是在线性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。 由于现代化企业内专业分工越来越细，组织机构日益复杂，为了统一协调企业各部门围绕一个整体的目标工作，产生了目标管理这种先进的管理技术。目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，考虑现有资源情况，分析如何达到规定目标或从总体上离规定目标的差距为最小。,目标规划问题及其数学模型,例5.1 某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定
6、，如表所示。,问该企业应如何安排计划，使得计划期内的总利润收入为最大？,目标规划问题及其数学模型,解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型：,其最优解为x14，x22，z14元,目标规划问题及其数学模型,但企业的经营目标不仅仅是利润，而且要考虑多个方面，如： 力求使利润指标不低于12元； 考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例； C和D为贵重设备，严格禁止超时使用； 设备B必要时可以加班，但加班时间要控制；设备A即要求充分利用，又尽可能不加班。,要考虑上述多方面的目标，需要借助目标规划的方法。,目标规划问题及其数学模型,线性规划模型存在的局限性： 1）要求问题
7、的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。 2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。 3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。 4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。,目标规划问题及其数学模型,目标规划怎样解决上述线性规划模型建模中的局限性？,1. 设置偏差变量，用来表明实际值同目标值之间的差异。,偏差变量用下列符号表示：,d+超出目标的偏差，称正偏差变量 d-未达到目标的偏差，称负偏差变量,正负偏差变量两者必有一个为0。 当实际值超出目标
8、值时： d+0, d-=0; 当实际值未达到目标值时： d+=0, d-0; 当实际值同目标值恰好一致时： d+=0, d-=0; 故恒有d+d-=0,目标规划问题及其数学模型,2. 统一处理目标和约束。,对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如C和D设备的使用限制。,对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。,1）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为： x1=x2。由于这个比例允许有偏差， 当x1x2时，出现正偏差d+，即： x1-d+ =x2或x1x2-d+ =0,目标规划问题及其数学模型,正负偏差不可能同时出现，
9、故总有： x1x2+d-d+ =0,若希望甲的产量不低于乙的产量，即不希望d-0,用目标约束可表为:,若希望甲的产量低于乙的产量，即不希望d0,用目标约束可表为:,若希望甲的产量恰好等于乙的产量，即不希望d0,也不希望d-0用目标约束可表为:,目标规划问题及其数学模型,3）设备B必要时可加班及加班时间要控制，目标约束表示为：,2）力求使利润指标不低于12元，目标约束表示为：,4）设备A既要求充分利用，又尽可能不加班，目标约束表示为：,目标规划问题及其数学模型,3. 目标的优先级与权系数,在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低
10、可分别通过优先因子P1,P2,表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。,现假定：,第1优先级P1企业利润； 第2优先级P2甲乙产品的产量保持1:1的比例 第3优先级P3设备A,B尽量不超负荷工作。其中设备A的重要性比设备B大三倍。,目标规划问题及其数学模型,上述目标规划模型可以表示为：,目标规划问题及其数学模型,目标规划数学模型的一般形式,达成函数,目标约束,其中：gk为第k个目标约束的预期目标值， 和 为pl 优先因子对应各目标的权系数。,目标规划问题及其数学模型,用目标规划求解问题的过程：,明确问题
11、，列出目标的优先级和权系数,构造目标规划模型,求出满意解,满意否？,分析各项目标完成情况,据此制定出决策方案,N,Y,目标规划的图解分析法,目标规划的图解法：,适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。,图解法解题步骤：,1. 将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）的直线方程分别标示于坐标平面上。 2. 确定系统约束的可行域。 3. 在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向,目标规划的图解分析法,3. 求满足最高优先等级目标的解 4. 转到下一个优先等级的目标，再不破坏所有较高优先等级
12、目标的前提下，求出该优先等级目标的解 5. 重复4，直到所有优先等级的目标都已审查完毕为止 6. 确定最优解和满意解。,目标规划的图解分析法,例5.2 用图解法求解下列目标规划问题,目标规划的图解分析法,(a),(b),(c),(d ),x2,x1,(e),(f),d1-,d1+,d2+,d2-,d3-,d3+,d4-,d4+,满意解(3,3),0,4,6,8,3,4,6,2,2,目标规划的图解分析法,x1,x2,(a),(b),d1+,d1-,(c),d2-,d2+,(d),d3-,d3+,G,D,满意解是线段GD上任意点,其中G点X(2,4),D点X(10/3,10/3),0,5.5,10
13、,5,5.6,11,2,4,10/3,10/3,5,10,7,例5.3,目标规划的图解分析法,O,x1,x2,20,40,60,50,20,40,60,50,a,b,d1-,d1+,d2-,d2+,c,d,d3-,d3+,d4-,d4+,(24,26),满意解X=(24，26),例5.4,目标规划应用举例,例5.5 已知一个生产计划的线性规划模型如下，其中目标函数为总利润，x1,x2 为产品A、B产量。,现有下列目标： 1. 要求总利润必须超过 2500 元； 2. 考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件； 3. 由于甲资源供应比较紧张，不要超过现有量14
14、0。 试建立目标规划模型，并用图解法求解。,目标规划应用举例,解：以产品 A,B 的单件利润比 2.5 :1 为权系数，模型如下：,目标规划应用举例,0,x2,0,x1,140 120 100 80 60 40 20,20 40 60 80 100,A,B,C,D,C(60 ,58.3)为所求的满意解。,(24,26),Chapter6 图与网络分析 ( Graph Theory and Network Analysis ),图的基本概念与模型 树与图的最小树 最短路问题 网络的最大流,本章主要内容：,图的基本概念与模型,长,江,汉,江,武昌,汉口,汉阳,您能从武汉理工大学出发走过每座桥且只走
15、一次然后回到学校吗?,近代图论的历史可追溯到18世纪的七桥问题穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不可能存在这样的路线。,图的基本概念与模型,Knigsberg桥对应的图,图的基本概念与模型,图论中图是由点和边构成，可以反映一些对象之间的关系。 一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。,图的定义： 若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：,其中: V点集 E边集, 图G区别于几何学中的图。这里只关心图
16、中有多少个点以及哪些点之间有连线。,图的基本概念与模型,可见图论中的图与几何图、工程图是不一样的。,例如：在一个人群中，对相互认识这个关系我们可以用图来表示。,图的基本概念与模型,定义: 图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=v1,v1; e2=v1,v2;,端点,关联边,相邻,若有边e可表示为e=vi,vj，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。,图的基本概念与模型,环, 多重边, 简单图,如果边e的两个端点相重，称该边为环。如右图中边e
17、1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。,图的基本概念与模型,次，奇点，偶点，孤立点,与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。,图的次: 一个图的次等于各点的次之和。,图的基本概念与模型,链，圈，连通图,图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用表示：,起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的
18、图为连通图，否则称图不连通。,图的基本概念与模型,二部图（偶图）,图G=(V,E)的点集V可以分为两各非空子集X，Y，集XY=V,XY=,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。,(a),(b),(c),(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。,图的基本概念与模型,子图，部分图(支撑子图),图G1=V1、E1和图G2=V2，E2如果有 称G1是G2的一个子图。若有 ，则称G1是G2的一个部分图(支撑子图)。,(a),(b),（G图）,图的基本概念与模型,网络（赋权图）,设图G（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij
19、称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。 权可以代表距离、费用、通过能力(容量)等等。 端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。,图的基本概念与模型,出次与入次,有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示；以vi为终点的边数称为点vi 的入次，用表示d-(vi) ；vi 点的出次和入次之和就是该点的次。, 有向图中，所有顶点的入次之和等于所有顶点的出次之和。,图的基本概念与模型,图的模型应用,例6.1 有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F 6个项目的比赛。下表中打的是各运动员报告参加的比赛项目。问6个项目
20、的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。,图的基本概念与模型,解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。,在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如： 1) A,C,B,F,E,D 2) D,E,F,B,C,A,图的基本概念与模型,一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参
21、加考试，试设计一个考试日程表。,思考题,图的基本概念与模型,思考题解答： 以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如CEAFDB，就是一个符合要求的考试课程表。,图的基本概念与模型,A,F,E,D,C,B,图的基本概念与模型,A,F,E,D,C,B,图的基本概念与模型,图的基本性质：,定理1 任何图中，顶点次数之和等于所有边数的2倍。,定理2 任何图中，次为奇数的顶点必为偶数个。,证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶
22、点次数的总和等于边数的2倍。,证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：,2m为偶数，且偶点的次之和 也为偶数，所以 必为偶数，即奇数点的个数必为偶数。,图的基本概念与模型,图的矩阵描述： 如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有： 邻接矩阵、关联矩阵、权矩阵等。,1. 邻接矩阵 对于图G=（V，E），| V |=n， | E |=m，有nn阶方矩阵A=(aij) nn，其中,图的基本概念与模型,例6.2 下图所表示的图可以构造邻接矩阵A如下,对于赋权图G=(V,E), 其中边 有权
23、, 构造矩阵B=(bij) nn 其中：,图的基本概念与模型,2. 关联矩阵 对于图G=(V,E), | V |=n, | E |=m, 有mn阶矩阵M=(mij) mn，其中:,3. 权矩阵,图的基本概念与模型,1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0,v
24、1 v2 v3 v4 v5 v6 v7 v8,e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12,例6.3 下图所表示的图可以构造邻接矩阵M如下:,M=（mij）=,图的基本概念与模型,例6.4 下图所表示的图可以构造权矩阵B如下:,树与图的最小树,树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。,例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。,运动员,树与图的最小树,例6.3 某企业的组织机构图也可用树图表示。,树与图的最小树,树：无圈的连通图即为树,性质1：任何树中必存在次为1的点。 性质2：n 个顶点的树必有n-1 条边。
25、 性质3：树中任意两个顶点之间，恰有且仅有一条链。 性质4：树连通，但去掉任一条边，必变为不连通。 性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。,树与图的最小树,图的最小部分树(支撑树),如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。,G1,G2,树与图的最小树,树与图的最小树,树与图的最小树,树与图的最小树,树与图的最小树,树与图的最小树,求树的方法：破圈法和避圈法,破圈法,树与图的最小树,部分树,树与图的最小树,避圈法,树与图的最小树,赋权图中求最小树的方法：破圈法和避圈法,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,边数n-1=5,树与图的最小树,得到最小树：,Min C(T)=15,树与图的最小树,避圈法: 去掉G中所有边，得到n个孤立点；然后加边。 加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。,树与图的最小树,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,