一个特殊指派问题及其解法，本文主要内容关键词为：解法论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号：O22 文献标识码：A
一、问题的提出
通常的指派问题[1,2]多是求项目的总工时最少，而很多情况下人们并不关心项目总工时多少，而只关心项目能否在最短时间完成，即历时最少的指派问题。目前从公开发表的资料未见这方面的研究，我们在这里给出了该问题的数学模型及其解法，完整地解决了这个问题。
二、数学模型
今有工作m项分配给m个人去做，每人做每项工作的效率已知，其中第i人做第j项工作的工作效率为
。规定每人做一项工作，且每项工作仅一人去做，问如果同时开工，如何安排可使该项工作尽早完成（历时最短）。
三、问题的求解
（一）线性规划解法
对于该指派问题，其数学模型(MP)虽然是整数规划模型，但由于目标函数是非线性函数，因此不可以直接应用解整数规划问题的分支定界法、割平面法等线性规划的方法去求解。但是在这里我们可以进行适当的转化，将其非线性目标化为线性目标，这样就可以应用文献[3]所提到的解整数规划问题的线性规划解法去求解。具体的方法是将(MP)化为下面的混整数规划模型
定理1中的结论是显然的，这里不作具体证明。根据上面的结论，我们只要利用分支定界法等线性规划解法求解(MILP)即可得到该类指派问题的最优解。
（二）矩阵变换解法
为了求解的便捷，下面我们再讨论一种可在效率矩阵上直接操作的方法，称之为矩阵变换解法，具体步骤如下：
第一步 给出初始指派
为了使初始指派接近目标，我们采取最小—最大元素法，具体方法是：
表1 工作效率表
译成英文 译成日文 译成德文 译成俄文
甲 2 109 2
乙15 4
14 8
丙13 14
1611
丁 4 15
13 9
四、应用举例
例1 现有一份资料需译成英、日、德、俄4种文字，今让甲、乙、丙、丁4人同时去完成，每人译且仅译一种文字。他们虽然对4种语言皆通，但因个人专长不同，他们翻译各种文种所需时间有别，具体数据如表1，试问如果4人同时开始翻译，应如何安排翻译工作可使该资料在最短时间译出？需多长时间？
解 该指派问题的效率矩阵数为
step3 对新的指派继续检验
经检验，该指派已为最佳指派。即甲译德文，乙译日文，丙译俄文，丁译英文可使资料在最短时间译出，最短需时11。
该指派总工时为28，而总工时最少的指派是甲译俄文，乙译日文，丙译德文，丁译英文，总工时26，用时16。因此两种指派不能互相替代。
现实生活中，人们要求不昔一切代价早日完成的事情有很多，这种指派的意义不言而喻，翻遍中外的运筹学教科书和资料也未见有人提及，（可能是我们孤陋寡闻吧！），拿出来供大家商榷。