《毕业论文（设计）-指派问题及其应用》由会员分享，可在线阅读，更多相关《毕业论文（设计）-指派问题及其应用（19页珍藏版）》请在金锄头文库上搜索。
1、石家庄学院毕业论文- 1 -1 1 引言引言指派问题是现实生活中经常遇到的一类组合优化问题，应用十分广泛在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有个人可承担这些任务由n于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同于是产生应指派哪个人去完成哪项任务，使完成项任务的总效率最高(或所需总时间最小)这n些问题的解决都涉及到指派问题它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳通常的指派问题多是求项目的总工时最少，而很多情况下人们并不关心项目总工时多少，而只关心项目能否在最短时间完成，即历时最少的指派问题1955 年，美国运筹学家HWKuhn 依据匈牙
2、利数学家Konig 的0元素覆盖定理首次建立了人 事指派问题求解的匈牙利法1992年，建立了关于nn人事指派问题求解的指派矩阵同解变换与同解改造理论及削高排除法1994年，nn北京大学张立昂教授依据指派矩阵同解变换理论设计出人事指派问题的周良泽nn算法在本文中给出了一类人员招聘问题，建筑中以及图书馆资源配置的数学模型，利用运筹学中线性规划中的指派问题进行决策，建立量化的分配模型，应用匈牙利算法解决了实际生活中遇到的这些问题2 2 指派问题的相关知识指派问题的相关知识线性规划是运筹学的一大分支，是目前管理中经常使用而又卓有成效的优化技术线性规划在运用过程中主要可以解决两类问题，一类问题是在任务确
3、定后，如何统筹安排，做到用尽量少的人力和物力资源来完成任务；另一类问题是在一定量的人力、物力资源条件下，如何安排、使用它们，使完成的任务最多，在这样的条件下常常解决的是指派问题2 2.1.1 数学模型的介绍数学模型的介绍为了建立标准指派问题的数学模型，引入个 0-1 变量：2n（=1，2， ，n) 件事。人做第，若指派第件事；人做第，若不指派第 ji1ii0Xijji,这样，问题的数学模型可写成ninjijijxczmin指派问题及其应用- 2 -., 2 , 1, 10;, 2 , 1, 1;, 2 , 1, 1. .11njninjtsxxxijnjijniijLLL或其中，第一个式子表示
4、每件事必有且只有一个人去做第二个式子表示每个人必做且只做一件事2.22.2 匈牙利匈牙利法法指派问题是一类特殊的运输问题，也是 0-1 型整数规划问题，因此可以有多种解法求解但是由于指派问题的数学结构的特殊性，可用比求解运输问题或者 0-1型整数规划更简便有效的方法来求解指派问题，这就是所谓的匈牙利法该算法于1955 年由库恩提出因其关键定理由匈牙利数学家康尼格予以证明，故称为匈牙利法定理定理 1 1 设 是效率矩阵,若可行解的 个 1(在解矩阵的不同行不同列上)对 nnijb*xn应的 个都为 0, 则 x*是最优解(显然=0)nijb)(*xz则是最优解因此需对效率矩阵作变换,使变换后效率
5、矩阵 含有ijx nnijb 个不同行不同列个 0由此求得最优解矩阵的 个 1 是对应于效率矩阵的这 个nnn0指派问题的最优解有这样性质，若从效率矩阵()的一行(列)各元素中分别减ijc去该行(列)的最小元素，得到新矩阵()，那么以()为效率矩阵求得的最优解和ijbijb用原效率矩阵求得的最优解相同 定理定理 2 2 设给定了以 ()为效率矩阵指派问题，现将的元素改变为 CijcGCijc，为常数则以= ()为效率矩阵指派问题与有相同jiijijcbj与iBijbGG的最优解证明 首先效率矩阵的这种变化只是目标值在变换，并不影响约束方程组，其次用和分别记问题与的目标函数值,则zzGGijij
6、jiijij ijijxcxbziij jj jij iiij ijijxxxcjj iiz即和只相差一个常数,故它们有相同的最优解利用这个性质，可使原效率zz石家庄学院毕业论文- 3 -矩阵变换为含有很多 0 元素的新效率矩阵，而最优解保持不变，在效率矩阵()中，ijb我们关心位于不同行不同列的 0 元素，以下简称为独立的 0 元素若能在效率矩阵()中找出 个独立的 0 元素；则令解矩阵()中对应这 个ijbnijxn独立的 0 元素的元素取值为 1，其他元素取值为 0将其代入目标函数中得，它一定是最小0ij ijijxbz这就是以()为效率矩阵的指派问题的最优解也就得到了原问题的最优解ij
7、b2.32.3 匈牙利法的解法步骤匈牙利法的解法步骤第一步：使指派问题的效率矩阵经变换，在各行各列中都出现 0 元素(1) 从效率矩阵的每行元素减去该行的最小元素；(2) 再从所得效率矩阵的每列元素中减去该列的最小元素若某行(列)已有 0元素，那就不必再减了第二步:做能覆盖所有零元素的最少数目的直线集合此时，若直线数等于 ,则可 n得出最优解，否则，转到第三步 第三步: 变换效率矩阵，使未被直线覆盖的元素中出现零元素回到第二步在未被直线覆盖的元素中总有一个最小元素对未被直线覆盖的元素所在的行（或行）中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必会出现零元素，但同时却又使已被直线覆
8、盖的元素中出现负元素为了消除负元素，只要对它们所在的列（或行）中各元素都加上这一最小元素（可以看作减去这一最小元素的相反数）即可第四步：进行指派，寻求最优解需找出 个独立的 0 元素若能找出，就以这些n独立 0 元素对应解矩阵()中的元素为 1，其余为 0，这就得到最优解当 较小ijxn时，可用观察法去找出 个独立 0 元素若 较大时，就必须按一定的步骤去找，nn常用的步骤为： (1)从只有一个 0 元素的行(列)开始，给这个 0 元素加圈，记作这表示对这行所代表的人只有一种任务可指派然后划去所在列的其他 0 元素，记作 这表示这列所代表的任务已指派完，不必再考虑别人了如此反复进行，直到所有
9、0元素都被圈出和划掉为止 (2)若遇到同行(列)的 0 元素至少有两个(表示可以从两项任务中指派其一)，可以任选一行(列)中某一个 0 元素，再划去同行(列)的其他 0 元素3 3 应用举例应用举例随着科学技术的不断进步，指派问题已经越来越多地出现在我们生活中为解决一个实际问题，建立数学模型是一种有效的重要方法对于建立起来的数学模型，指派问题及其应用- 4 -还需要用一定的技术手段（如匈牙利法等）求解数学问题，以达到解决实际问题的目的这在现在的生活中是常用3.13.1 平衡指派问题的应用平衡指派问题的应用在实际生活和生产安排中，经常遇到要指派不同的工作人员去完成数目相同的工作由于每个人的专长不
10、同，不同的人去完成各项任务的效率(或所花时间或成本等)一般地也不同这样，就产生了指派何人去完成何任务，使总效率最高(或所花时间最少或成本最低等)的问题这就是在运筹学中的所谓的平衡指派问题，下面就运用以上介绍的知识到实际问题中3.1.1 建筑中的应用例 某商业公司设计开办五家新闻商店 为了尽早建成营业，54321,BBBBB商业公司通知了五个建筑公司，以便让每家新商店由一个建筑公司54321,AAAAA承建建筑公司对新商店的建造费用的投标均见表商业公司应当对五家建筑公司怎样分配建造任务，才能使总建造费用最少？解 这是一个标准的指派问题若设 0-1 变量（=1,2,3,4,5) 时不承建，当时承建
11、当jiji ijBABAx0, 1ji,则问题的数学模型为105 , 4 , 3 , 2 , 115 , 4 , 3 , 2 , 11. .61084min515155541211或，ijjijiijxixjxtsxxxxzL其效率矩阵为61012961061476781296101417971215784C对各行元素分别减去本行的最小元素，对各列也如此，得石家庄学院毕业论文- 5 -61012961061476781296101417971215784C04630408101263037102081134004320405001232037710811030容易看出，可用四条直线覆盖所有零元
12、素，这是最少数直线集合，由于的阶C数 =5，故需对效率矩阵继续变换nC04320405001232037710811030为了使未被直线覆盖的元素中出现零元素，将第二行和第三行中各元素减去未被直线覆盖元素中的最小元素 1但这样一来，第一列中出现了负元素，因而再对第一列各元素分别加上 1，即04320405001232037710811030043204050001211-26601-81103004321405010121026600811031此时，已不能用少于五条直线来覆盖所有零元素，故已可看得最优指派方案为了得到最优指派方案，对效率矩阵进行圈零：043214051121026608110
13、31先找出零元素最少行列,然后对其它行列的零元素进行筛选,保证各行列只有一个零元素所以，本题最优解为1000001000000010001000100X也就是说，最优指派方案为：让承建,承建, 承建,承建,1A3B2A2B3A1B4A4B承建,这样总的建设费用最少,为 7+9+6+6+6=34 万元5A5B指派问题及其应用- 6 -3.1.2图书馆资源优化配置中的应用长期以来图书馆决策以多年来积累的管理经验为基础进行微调或不调，这种决策方式缺乏科学性，难以实现资源的最优配置因此，以建立科学合理的定量管理办法为基础，辅之以多年经验进行决策既能满足图书馆资源优化的需求，又能为领导决策节省大量时间目
14、前，高校图书馆经费紧张已是不争的事实，如何合理、有效地利用有限资源已成为高校图书馆当前工作的重要任务利用运筹学中线性规划中的指派问题进行决策，建立量化的模型例 图书加工流程一般分为：分类、编目、统计、入库而不同的工作人员，由于性格、专业背景等的不同对各项工序的执行效率不同如何合理指派任务使整体工作能快速、高效地完成?解 若能对不同工作人员对于不同工序的完成情况进行合理评价，给出合理的效率数，从而得出效率矩阵，进而可以运用匈牙利法进行工作指派建立效率系数表，如下图所示 表 1 工序人员甲 乙 丙 丁分类30 25 40 32编目32 35 30 36统计35 40 34 27入库28 43 32 384 , 2 , 1, 104 , 2 , 1, 14 , 2 , 1, 1. .min51514141LLLjixixjxtsxbfijiijjijijijij或其中表示第 名人员分配到第个岗位；表示第 名人员分配到第1ijxij0ijxi个岗位运用运筹学中指派问题的知识可以建立如下数学模型：j43maxijijX石家庄学院毕业论文- 7 -所以 （ =1,2,3,4）可建立如下效率矩阵：ijijXB 43ji,记作511015169387138111131813B5110151360506148015105
