一类非平衡指派问题的求解方法及其应用研究

论文摘要

指派问题(又称“分配问题”)是“运筹学”中线性规划的一类经典问题。在生活实际和生产安排中,基于生产管理的具体要求而产生的各种非平衡的指派问题是目前研究的重点。本文针对实际应用中一类平衡指派问题展开研究。建立了平衡指派问题的数学模型,给出了问题的求解方法。而这些求解方法中运用最为广泛的是“匈牙利算法”。匈牙利算法是解决指派问题的一种非常简单有效的方法。文中对匈牙利算法的起源、运用、求解模型及其原理作了介绍。对于非平衡指派问题,建立了非平衡指派问题的数学模型后,文中介绍了将其转化为平衡指派问题的方法。非平衡指派问题有两种情形:一种是人员数少于任务数,另一种是人员数多于任务数。在实际的指派工作中,常会遇到某个人有没有资格去承担某项工作的问题。因此,本文建立了人员有承担量约束的指派数学模型。基于“人少任务多”最小分派问题的解法探析,指出了“加边补零法”的局限性,改进得到“加边补最小值”法,并给出优于其他算法时的情形。在此本文提出了一种新的方法,即“加边排序补小值法”,利用该算法和匈牙利算法给出人员有能力限制且“人员数少于任务数”的多目标指派问题的求解。这就将有资格限制的指派问题化为传统的指派问题来求解。而对于人员数多于任务数的指派问题文中给出的求解方法是类匈牙利算法。本文还从综合评价和改进的角度,对“承担任务有资格限制”这一点,补充条件加强的非平衡指派问题的数学模型。建立有资格约束的数学模型,给出什么才算作第i个人员“有资格”承担第j项任务;并讲述有资格约束的数学模型有解的充要条件。最后部分,论文给出了应用“加边排序补小值”法求解具体的数值例子,来说明这种新的方法的实用性和有效性。并指出论文研究的缺陷和有待改进的地方。

论文目录

• 中文摘要
• Abstract
• 第一章 绪论
• 1.1 背景介绍
• 1.1.1 指派问题
• 1.1.2 指派问题研究的现状
• 1.2 研究内容及论文的组织情况
• 1.2.1 研究内容
• 1.2.2 论文的组织情况
• 第二章 平衡指派问题的求解
• 2.1 平衡指派问题
• 2.1.1 平衡指派问题的数学模型
• 2.1.2 平衡指派问题求解原理的证明
• 2.2 匈牙利算法
• 2.2.1 匈牙利算法概述
• 2.2.2 匈牙利算法的求解步骤
• 2.2.3 匈牙利算法的改进与应用
• 第三章 非平衡指派问题的求解
• 3.1 非平衡指派问题
• 3.1.1 非平衡指派问题的数学模型
• 3.1.2 非平衡指派问题的求解原理证明
• 3.2 非平衡指派问题两种情形的求解
• 3.2.1 将非平衡指派问题转化为平衡指派问题
• m）的类匈牙利算法'>3.2.2 求解非平衡指派问题（n>m）的类匈牙利算法
• 3.2.3 求解人员有任务承担量约束（n
• 第四章 非确定型指派问题求解
• 4.1 数学模型的建立
• 4.2 问题的转换与求解
• 第五章 时间优化的指派问题求解
• 5.1 时间优化的指派问题分类
• 5.2 对不同类型的时间优化的指派问题的讨论
• 5.3 与平衡指派问题的比较
• 第六章 “加边排序补小值”法
• 6.1 “加边排序补小值”法的提出与验证
• 6.1.1 “加边排序补小值”法的原理及证明
• 6.1.2 “加边排序补小值”法的步骤
• 6.2 “加边排序补小值”法的应用
• 6.3 对条件加强的非平衡指派问题求解的补充
• 6.3.1 “加强约束条件——资格有约束”的一点补充
• 6.4 数值例子
• 第七章 结束语
• 7.1 主要工作总结
• 7.2 研究展望
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢