运筹学指派问题实验报告.doc

运筹学指派问题实验报告
———————————————————————————————— 作者：
———————————————————————————————— 日期：

运筹学实践报告
指派问题
第一部分 问题背景
泰泽公司（Tazer）是一家制药公司。它进入医药市场已经有12年的历史了，并且推出了6种新药。这6种新药中5种是市场上已经存在药物的同类产品，所以销售的情况并不是很乐观。然而，主治高血压的第6种药物却获得了巨大的成功。由于泰泽公司拥有生产治疗高血压药物的专利权，所以公司并没有遇到什么竞争对手。仅仅从第6种药物中所获得的利润就可以使泰泽公司正常运营下去。
在过去的12年中，泰泽公司不断地进行适量的研究和发展工作，但是却并没有发现有哪一种药物能够获得像高血压药物一样的成功。一个原因是公司没有大量投资进行创新研究开发的动力。公司依赖高血压药物，觉得没有必要花费大量的资源寻找新药物的突破。
但是现在泰泽公司不得不面对竞争的压力了。高血压药物的专利保护期还有5年 一般来说，专利权保护发明的期限为17年。在1995年，GATT立法拓展专利权的保护期限到20年。在本案例之中，泰泽公司的高血压药物的注册时间是在1995年之前，所以专利权只能够保护这种药物17年。
。泰泽公司知道只要专利期限一到，大量药品制造公司就会像秃鹰一样涌进市场。历史数据表明普通药物会降低品牌药物75%的销售量。
今年泰泽公司投入大量的资金进行研究和开发工作以求能够取得突破，给公司带来像高血压药物一样的巨大成功。泰泽公司相信如果现在就开始进行大量的研究和开发工作，在高血压药物专利到期之后能够发明一种成功药物的概率是很高的。作为泰泽公司研究和开发的负责人，你将负责选择项目并为每一个项目指派项目负责人。在研究了市场的需要，分析了当前药物的不足并且拜会了大量在有良好前景的医药领域进行研究的科学家之后，你决定你的部门进行五个项目，如下所示：
Up项目：开发一种更加有效的抗忧郁剂，这种新药并不会带来使用者情绪的急剧变化。
Stable项目：开发一种治疗躁狂抑郁病的新药。
Choice项目：为女性开发一种副作用更小的节育方法。
Hope项目：开发一种预防HIV的疫苗。
Release项目：开发一种更有效的降压药。
对于这5个项目之中的任何一个来说，由于在进行研究之前你并不知道使用的配方以及哪种配方是有效的，所以你只能明确研究所要解决的疾病。
你还有5位资深的科学家来领导进行这5个项目。有一点你十分清楚，那就是科学家都是一些喜怒无常的人，而且他们只有在受到项目所带来的挑战和激励的时候才会努力工作。为了保证这些科学家都能够到他们感兴趣的项目中去，你为这个项目建立了一个投标系统。这5位科学家每个人都有1000点的投标点。他们向每一个项目投标，并且把较多的投标点投向自己最感兴趣的项目之中。
下表显示了这5位科学家进行投标的情况。
项目
克瓦尔博士
朱诺博士
特塞博士
米凯博士
罗林斯博士
Up项目
100
0
100
267
100
Stable项目
400
200
100
153
33
Choice项目
200
800
100
99
33
Hope项目
200
0
100
451
34
Release项目
100
0
600
30
800
第二部分 指派问题的标准形式与建模
指派问题（Assignment problem）的定义：在满足特定指派要求条件下，使指派方案总体效果最佳。在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高。这类问题称为指派问题。
指派问题的标准形式是：有n个人和n件事，已知第i个人做第j件事的费用为(i,j=1,2,…，n)，要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最小。
若指派第i个人做第j件事
设n2个0-1变量
若不指派第i个人做第j件事
(i,j=1,2,...,n)
数学模型为
第三部分 不同类型的指派问题
我们将指派问题分为几个不同的类型，解决不同指派问题的基本理念是将其转化为标准型，之后再求解。
最大化指派问题
生活中有许多问题是需要我们求目标函数的最大值的