单位文秘网 2021-07-19 08:28:50 点击: 次
打开文本图片集
【摘要】指派问题是运筹学中的一个重要的线性规划问题,它属于特殊的运输问题。运筹学已经成为各行各业进行管理决策的一个基本工具,其目的是根据实际问题的具体要求,通过定量的分析与运算,对资源运用、筹划及相关决策等问题最初综合最优的合理安排,以使有限的资源发挥更大的效益或作用。而我们所研究的指派问题旨在解决生活中所出现的形形色色的资源配置问题。
【关键词】指派问题 匈牙利算法 资源配置
一、模型的处理
(一)建立模型
指派问题AP:今有n个工人和n件工作,第i个工人做第j件工作的费用(如成本,时间,效能等)为cij,i,j=1,2,…,n.问;应如何制定一个工人和工作之间的指派方案,才能使完成这n件工作的总费用最少?
(二)算法步骤
1.知识准备
步骤1 约化费用矩阵C为C":将C的每一行的各元素都减去本行最小的元素,每一列的各元素都减去本列的最小元素,转步骤2.
步骤2 找独立格子集Q:若C"的某行(列)只有一个零元素,则将其圈起,并将与其同列的其余零元素畫×,如此重复,直到C"的所有的零元素都被圈起或画×为止.令Q={tij|c"ij=0被圈起).若|Q|=n,则得指派问题AP的最优解为xij=1.tok∈Q 0,否则,停;否则,转步骤3.
步骤3 找覆盖C"的所有零元素的数目最少的直线;若某行无圈起的零元素,则在此行打√;在打√的列中,对圈起的零元素所在的行打√.如此重复,直到再也不存在可打√的行或列为止.对未打√的行画一横线,对打√的列画一竖线。
继续约化C":令C"的未被直线覆盖的最小元素θ,将未被直线覆盖的元素所在的行(或列)的各元素都减去θ.为消除负元素,可将负元素所在的列(或行)的各元素都加上θ。
二、指派问题的应用
(排课表问题)今有4个教师A,B,C,D和4门课程:数学分析,高等代数,概率论和解析几何.不同的教师上不同的课程的课时费(单位:元)如下:
三、总结
本文主要介绍了运筹学中指派问题的求解过程,又以例题的形式充分又具体的说明了这个问题的在实际中的应用。指派问题的总体思想是求解具体情境下的最优策略,这也是运筹学的总体目的。在实际中掌握指派问题的求解方法至关重要,可以提高资源的利用率,也可以使人力调配方面得到更充分的利用,总而言之,可以使生活中的具体问题实现效益最大化。而我们指派问题可能还存在很多问题没有考虑到,有许多不确定因素没有考虑,因此以后可能会发现更为简洁的方法。
参考文献:
[1]王继强.运筹学教程[M].北京:国防工业出版社,2014.95-112.
[2]吴祈宗.运筹学[M].北京:机械工业出版社,2006.92-114.
[3]吴振华.运筹学[M].北京:北京理工大学出版社,2014.68-90.
(责任编辑:单位文秘网) )地址:https://www.kgf8887.com/show-122-67105-1.html
上一篇:探索式军事运筹学教学方法研究
下一篇:收益管理理论的基础问题及发展研究
版权声明:
本站由单位文秘网原创策划制作,欢迎订阅或转载,但请注明出处。违者必究。单位文秘网独家运营 版权所有 未经许可不得转载使用