搜索
运筹学实践报告指派问题第一部分问题背景泰泽公司（Tazer）是一家制药公司。它进入医药市场已经有12年的历史了，并且推出了6种新药。这6种新药中5种是市场上已经存在药物的同类产品，所以销售的情况并不是很乐观。然而，主治高血压的第6种药物却获得了巨大的成功。由于泰泽公司拥有生产治疗高血压药物的专利权，所以公司并没有遇到什么竞争对手。仅仅从第6种药物中所获得的利润就可以使泰泽公司正常运营下去。在过去的12年中，泰泽公司不断地进行适量的研究和发展工作，但是却并没有发现有哪一种药物能够获得像高血压药物一样的成功。一个原因是公司没有大量投资进行创新研究开发的动力。公司依赖高血压药物，觉得没有必要花费大量的资源寻找新药物的突破。但是现在泰泽公司不得不面对竞争的压力了。高血压药物的专利保护期还有5年1。泰泽公司知道只要专利期限一到，大量药品制造公司就会像秃鹰一样涌进市场。历史数据表明普通药物会降低品牌药物75%的销售量。今年泰泽公司投入大量的资金进行研究和开发工作以求能够取得突破，给公司带来像高血压药物一样的巨大成功。泰泽公司相信如果现在就开始进行大量的研究和开发工作，在高血压药物专利到期之后能够发明一种成功药物的概率是很高的。作为泰泽公司研究和开发的负责人，你将负责选择项目并为每一个项目指派项目负责人。在研究了市场的需要，分析了当前药物的不足并且拜会了大量在有良好前景的医药领域进行研究的科学家之后，你决定你的部门进行五个项目，如下所示：Up项目：开发一种更加有效的抗忧郁剂，这种新药并不会带来使用者情绪的急剧变化。Stable项目：开发一种治疗躁狂抑郁病的新药。Choice项目：为女性开发一种副作用更小的节育方法。Hope项目：开发一种预防HIV的疫苗。Release项目：开发一种更有效的降压药。对于这5个项目之中的任何一个来说，由于在进行研究之前你并不知道使用的配方以及哪种配方是有效的，所以你只能明确研究所要解决的疾病。你还有5位资深的科学家来领导进行这5个项目。有一点你十分清楚，那就是科学家都是一些喜怒无常的人，而且他们只有在受到项目所带来的挑战和激励的时候才会努力工作。为了保证这些科学家都能够到他们感兴趣的项目中去，你为这个项目建立了一个投标系统。这5位科学家每个人都有1000点的投标点。1一般来说，专利权保护发明的期限为17年。在1995年，GATT立法拓展专利权的保护期限到20年。在本案例之中，泰泽公司的高血压药物的注册时间是在1995年之前，所以专利权只能够保护这种药物17年。他们向每一个项目投标，并且把较多的投标点投向自己最感兴趣的项目之中。下表显示了这5位科学家进行投标的情况。项目克瓦尔博士朱诺博士特塞博士米凯博士罗林斯博士Up项目1000100267100Stable项目40020010015333Choice项目2008001009933Hope项目200010045134Release项目100060030800第二部分指派问题的标准形式与建模指派问题（Assignmentproblem）的定义：在满足特定指派要求条件下，使指派方案总体效果最佳。在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高。这类问题称为指派问题。指派问题的标准形式是：有n个人和n件事，已知第i个人做第j件事的费用为ijc(i,j=1,2,…，n)，要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最小。设n2个0-1变量10ijx数学模型为njiortsZxxxxcijnjijniijninjijij，,2,1,1011.min1111若指派第i个人做第j件事若不指派第i个人做第j件事(i,j=1,2,...,n)第三部分不同类型的指派问题我们将指派问题分为几个不同的类型，解决不同指派问题的基本理念是将其转化为标准型，之后再求解。（一）最大化指派问题生活中有许多问题是需要我们求目标函数的最大值的，例如本题中我们需要求解使科学家的满意度最大化。这时，我们就需要了解与掌握最大化指派问题的解法。最大化指派问题的解法同标准型指派问题类似，只是将目标函数取最小值改为目标函数取最大值。其余的建模与求解过程均与标准型相同。（以下几种类型的问题，我们默认均以最大化问题为前提。）（二）人数与项目数不等的指派问题这里默认一人只能领导一个项目。将问题转化为标准指派问题是求解问题的主体思路。人数与项目数不等的指派问题分为两种情况，一种是人数小于项目数的指派问题，另一种是人数大于项目数的指派问题。我们将原问题默认为最大化指派问题，即求目标为目标函数的最大值。首先，关于人数小于项目数的指派问题的解法，我们需要添加虚拟的人，虚拟人的个数与人数和项目数之间的差额确定，并将虚拟人对应的系数矩阵中的系数设置为0。添加虚拟人后，就将原问题转化为人数与项目数相等的标准型指派问题，接着按标准型指派问题的建模和求解步骤求解。得到结果后，虚拟人对应的项目就是我们应该放弃的项目。另外，关于人数大于项目数的指派问题的解法，我们需要添加虚拟的项目，虚拟项目的个数与人数和项目数之间的差额确定，并将虚拟项目对应的系数矩阵中的系数与其对应的项目的系数相同。（例如，A项目可以由两个人领导，那么我们将A项目变为A1项目，并添加A2虚拟项目，使得A1与A2对应的系数相等。）添加虚拟项目后，就将原问题转化为人数与项目数相等的标准型指派问题，接着按标准型指派问题的建模和求解步骤求解。得到结果后，分别领导相同系数项目的人即为共同领导同一项目的人。（即求得分别领导A1与A2项目的人为共同领导A项目的人。）（三）一人可以领导多个项目的指派问题一人领导多个项目的指派问题其实与人数大于项目数的指派问题的解法类似，只是将虚拟项目改为虚拟人。关于一人领导多个项目的指派问题的解法，我们需要添加虚拟的人，虚拟人的个数与人数和项目数之间的差额确定，并将虚拟人对应的系数矩阵中的系数与其对应的人的系数相同。（例如，甲可以同时领导两个项目，那么我们将甲变为甲1，并添加甲2虚拟人，使得甲1与甲2对应的系数相等。）添加虚拟人后，就将原问题转化为人数与项目数相等的标准型指派问题，接着按标准型指派问题的建模和求解步骤求解。得到结果后，相同系数的人领导的项目则是这个人同时领导的项目。（即求得甲1和甲2领导的项目即为甲所领导的两个项目。）（四）某人不能领导某项目的指派问题某人不能领导某项目，我们可以直接将对应于人和项目的交叉项的系数设置为一个负的无穷大的数，因为这里我们是要求目标函数的最大值。在后面的实际问题求解中，我们将系数设置为-10000。其余建模与求解过程与标准型指派问题相同。第四部分实际问题分析（一）问题一（最大化指派问题）：根据所给出的投标情况，你需要为每一个项目指派一位资深的科学家并且使得这位科学家的满意度最高。那么应当怎样进行指派？1.目标：选择一种方案使得5位博士的总满意度最大化。2.Excel求解过程：如下图3.解释：投标约束表示一个博士只能领导一个约束。项目约束表示一个项目只能由一个博士领导。4.结论:如上图所示，自变量矩阵中“1”代表对应的博士领导对应的项目，5位博士的总投标点数即总满意度为2551。（二）问题二（人数小于项目数的指派问题）：罗林斯博士接到了哈佛医学院的邀请去完成一个教学任务，而你却非常想把她留下来。但是哈佛的声望会使她离开公司。如果这种情况真的发生的话，公司就只有放弃那个最缺乏热情的项目。公司应当放弃哪一个项目？1.解题思路：将问题转化为标准指派问题是求解问题的主体思路。因为本题目中存在5个项目和4位博士，所以添加一个虚拟博士，使得博士数目与项目数目相等。将虚拟博士的满意度系数均设置为0，求解出结果后虚拟博士所领导的项目则是泰泽公司需要抛弃的项目。2.目标:博士总满意度最高。3.Excel求解过程：如下图4.结论:如上图所示，自变量矩阵中“1”代表对应的博士领导对应的项目，4位博士的总投标点数即总满意度为2251。虚拟博士所领导的Up项目则是需要抛弃的项目。（三）问题三（一人可以领导多个项目的指派问题）：当然你并不愿意放弃任何一个项目，因为如果放弃一个项目而只剩下4个项目的话，会大大降低找到突破性新药的概率。你决定让朱诺博士或者米凯博士同时领导两个项目。大只有4个科学家的情况下，让哪一个科学家领导哪一个项目才能使得对项目的热情最大？1.目标：博士的总满意度最大化2.Excel求解过程：如下图3.解释：本题中存在4位博士和5个项目，其中朱诺博士或者米凯博士可以同时领导两个项目。项目约束与之前的题目类似，表示一个项目只能由一位博士领导。投标约束则与之前的题目中不同，本题中克瓦尔博士与特塞博士的投标约束仍然是对应一列数字加和为1。另外，约束要求朱诺博士与米凯博士的自变量总和为3且两人的对应列数字和均小于等于2。4.结论:如上图所示，自变量矩阵中“1”代表对应的博士领导对应的项目，其中米凯博士领导Up项目与Hope项目两个项目。（四）问题四（一人可以领导多个项目的指派问题）：如果朱诺博士被告知她和米凯博士都有机会来同时领导两个项目，她决定要改变好的投标。朱诺博士对每一个项目的投标的情况如下所示：Up项目：20Stable项目：450Choice项目：451Hope项目：39Release项目：40在只有4个科学家的情况下，让哪一个科学家领导哪一个项目才能使得对项目的热情最大？1.目标：博士的总满意度最大化2.Excel求解过程：如下图3.解释：本题中存在4位博士和5个项目，其中朱诺博士或者米凯博士可以同时领导两个项目。项目约束与之前的题目类似，表示一个项目只能由一位博士领导。投标约束则与之前的题目中不同，本题中克瓦尔博士与特塞博士的投标约束仍然是对应一列数字加和为1。另外，约束要求朱诺博士与米凯博士的自变量总和为3且两人的对应列数字和均小于等于2。4.结论:如上图所示，自变量矩阵中“1”代表对应的博士领导对应的项目，其中米凯博士领导Up项目与Hope项目两个项目，博士的总满意度为2169。（五）问题五：你是否支持从d得出的指派？为什么？答：不支持。我们可以从已给出的数据问题得知，朱诺博士在尚未得知他本人有机会领导两个项目时对Stable项目的投标点数为200，对Choice项目的投标点数为800。而在得知他有机会领导两个项目后，他为了领导两个项目，将Choice项目的投标点数降低到451，将Stable的点数升高到450。然而最后我们的指派结果朱诺博士只领导了一个项目，为Choice项目，并且Stable项目由科瓦尔博士领导，他对Stable项目投标点数为400，小于朱诺博士随Stable的投标点数。故这种指派结果很有可能引起朱诺博士的不满。这样的指派结果并没有考虑博士的个人情绪。（对于问题的改进，我们会在后续优化中予以介绍）（六）问题六（某人不能领导某项目的指派问题）：现在我们还是来分析拥有5位科学家的情况。但是，你决定有几个科学家不能领导几个特定的项目。具体来说米凯博士在免疫系统的研究方面没有什么经验，所以他不能领导Hope项目。而且他的家族有着躁狂抑郁病的病史，所以你觉得他作为一个项目的领导者参与到Stable项目的研究中是不太合适的。于是米凯博士也不能领导Stable项目。克瓦尔博士由于在免疫系统的研究方面没有什么经验，也不能领导Hope项目。还有克瓦尔博士由于在心血管系统的研究方面没有什么经验，不能领导Release项目。罗林斯博士由于家族有低血压的病史，所以你觉得她作为一个项目的领导者参加到Up项目中是不太合适的，所以罗林斯博士不能领导Up项目。因为米凯博士和克瓦尔博士都有两个项目不能进行领导，所以他们每人的投标点就只剩下600点。罗林斯博士由于有一个项目不能进行领导，所以她的投标点剩下800点。下表显示了米凯博士、克瓦尔博士和罗林斯博士投标情况：在这种情况下，让哪一个科学家领导哪一个项