【作者】 杨立兴；

【导师】 张强；

【作者基本信息】 河北大学 ， 应用数学， 2002， 硕士

【摘要】 指派问题在现实生活中是很普遍的。传统的指派问题，即确定环境中的指派问题已经被研究的很成熟了。它可以用匈牙利法、隐枚举法、割平面法和分枝定界法等方法来求解。 但是我们在做决策时经常会遇到不确定的现象。具体地说，对于我们所研究的指派问题，在工作未完成之前，任何一种指派计划所消耗的费用，所花费的时间以及所能带来的利润都是不确定的。因此决策者为了得到具有指导性的决策，只能是对效率矩阵中的数据进行统计或粗略地估计。这样就产生了更加切近于生活的不确定环境中的指派问题。 在本文中我们首先建立了两类不确定环境中指派问题的模型，即随机指派问题的模型和模糊指派问题的模型。而后，受启发于Liu等人提出的用混合智能算法来求解不确定规划的思想，我们设计了一种基于模拟的禁忌搜索算法以求解所建立模型的近似最优解。最后，我们给出了两个具体的算例以验证算法的有效性。 本文的主要创新点包括： Ⅰ．建立了随机指派问题的期望值目标规划模型、机会约束目标规划模型、相关机会目标规划模型。 Ⅱ．建立了模糊指派问题的期望值目标规划模型、机会约束目标规划模型、相关机会目标规划模型。 Ⅲ．设计了混合智能算法，用于求解上述六种模型。更多还原

【Abstract】 In actual life, the assignment problem is very universal. Traditional assignment problem, that is, the assignment problem in certain environments has been studied very well. And we have many ways to solve such kind of problem.However we often meet with uncertain phenomena when we make some decisions. In more detail, as for the assignment problem, before the tasks are finished, the cost, the time and the profits of any kind of assignment plan are all uncertain. Therefore, if we want to get a directive decision, we can statistically or roughly estimate the data in efficiency matrix. As a result, the assignment problem in uncertain environments is obtained. And it is true that such kind of problem is closer to the real life.In our thesis, two kinds of models that include random parameters and fuzzy parameters respectively are firstly constructed. Secondly, enlightened by Liu’s thought that solve the uncertain programming with hybrid intelligent algorithm, we design a hybrid intelligent algorithm, that is, tabu search based on simulation to achieve the approximate best solution of the six above-mentioned models. Lastly, two specific examples are listed to verify the efficiency of our algorithm.Now we shall list our contribution to the assignment problem:1. Expected value goal programming model, chance-constrained goal programming model and dependent-chance goal programming model of random assignment problem are constructed.2. Expected value goal programming model, chance-constrained goal programming model and dependent-chance goal programming model of fuzzy assignment problem are constructed.3. A kind of hybrid intelligent algorithm is designed to solve the above-mentioned models.更多还原