运筹学指派问题实验报告Word下载.docx
《运筹学指派问题实验报告Word下载.docx》由会员分享，可在线阅读，更多相关《运筹学指派问题实验报告Word下载.docx（35页珍藏版）》请在冰点文库上搜索。
开发一种治疗躁狂抑郁病的新药。
Choice项目：
为女性开发一种副作用更小的节育方法。
Hope项目：
开发一种预防HIV的疫苗。
Release项目：
开发一种更有效的降压药。
对于这5个项目之中的任何一个来说，由于在进行研究之前你并不知道使用的配方以及哪种配方是有效的，所以你只能明确研究所要解决的疾病。
你还有5位资深的科学家来领导进行这5个项目。
有一点你十分清楚，那就是科学家都是一些喜怒无常的人，而且他们只有在受到项目所带来的挑战和激励的时候才会努力工作。
为了保证这些科学家都能够到他们感兴趣的项目中去，你为这个项目建立了一个投标系统。
这5位科学家每个人都有1000点的投标点。
他们向每一个项目投标，并且把较多的投标点投向自己最感兴趣的项目之中。
下表显示了这5位科学家进行投标的情况。
项目
克瓦尔博士
朱诺博士
特塞博士
米凯博士
罗林斯博士
Up项目
100
267
Stable项目
400
200
153
33
Choice项目
800
99
Hope项目
451
34
Release项目
600
30
第二部分指派问题的标准形式与建模
指派问题（Assignment
problem）的定义：
在满足特定指派要求条件下，使指派方案总体效果最佳。
在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。
由于每人的专长不同，各人完成任务不同，效率也不同。
于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高。
这类问题称为指派问题。
指派问题的标准形式是：
有n个人和n件事，已知第i个人做第j件事的费用为
（i,j=1,2,…，n），要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最小。
设n2个0-1变量
数学模型为
第三部分不同类型的指派问题
我们将指派问题分为几个不同的类型，解决不同指派问题的基本理念是将其转化为标准型，之后再求解。
（一）最大化指派问题
生活中有许多问题是需要我们求目标函数的最大值的，例如本题中我们需要求解使科学家的满意度最大化。
这时，我们就需要了解与掌握最大化指派问题的解法。
最大化指派问题的解法同标准型指派问题类似，只是将目标函数取最小值改为目标函数取最大值。
其余的建模与求解过程均与标准型相同。
（以下几种类型的问题，我们默认均以最大化问题为前提。
）
（二）人数与项目数不等的指派问题
这里默认一人只能领导一个项目。
将问题转化为标准指派问题是求解问题的主体思路。
人数与项目数不等的指派问题分为两种情况，一种是人数小于项目数的指派问题，另一种是人数大于项目数的指派问题。
我们将原问题默认为最大化指派问题，即求目标为目标函数的最大值。
首先，关于人数小于项目数的指派问题的解法，我们需要添加虚拟的人，虚拟人的个数与人数和项目数之间的差额确定，并将虚拟人对应的系数矩阵中的系数设置为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求解过程：
如下图
如上图所示，自变量矩阵中“1”代表对应的博士领导对应的项目，4位博士的总投标点数即总满意度为2251。
虚拟博士所领导的Up项目则是需要抛弃的项目。
（三）问题三（一人可以领导多个项目的指派问题）：
当然你并不愿意放弃任何一个项目，因为如果放弃一个项目而只剩下4个项目的话，会大大降低找到突破性新药的概率。
你决定让朱诺博士或者米凯博士同时领导两个项目。
大只有4个科学家的情况下，让哪一个科学家领导哪一个项目才能使得对项目的热情最大？
博士的总满意度最大化
本题中存在4位博士和5个项目，其中朱诺博士或者米凯博士可以同时领导两个项目。
项目约束与之前的题目类似，表示一个项目只能由一位博士领导。
投标约束则与之前的题目中不同，本题中克瓦尔博士与特塞博士的投标约束仍然是对应一列数字加和为1。
另外，约束要求朱诺博士与米凯博士的自变量总和为3且两人的对应列数字和均小于等于2。
如上图所示，自变量矩阵中“1”代表对应的博士领导对应的项目，其中米凯博士领导Up项目与Hope项目两个项目。
（四）问题四（一人可以领导多个项目的指派问题）：
如果朱诺博士被告知她和米凯博士都有机会来同时领导两个项目，她决定要改变好的投标。
朱诺博士对每一个项目的投标的情况如下所示：
20
450
39
40
在只有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点。
下表显示了米凯博士、克瓦尔博士和罗林斯博士投标情况：
300
86
不能领导
343
50
125
171
175
在这种情况下，让哪一个科学家领导哪一个项目才能使得对项目的热情最大？
本题同样利用0-1整数规划求解，但与之前不同的是本题中存在博士不能领导项目的情况，因为我们的目标为总满意度最大化，故我们在系数矩阵中将不能领导转化为一个负无穷大，本题求解过程中我们将其设置为-10000。
2.目标：
4.结论:
如上图所示，自变量矩阵中“1”代表对应的博士领导对应的项目，4位博士的总投标点数即总满意度为2143。
（七）问题七（项目数小于人数的指派问题）：
你觉得Release项目和Hope项目太复杂了，各让一位科学家分别进行领导是不太合适的。
因此，这两个项目都要指派两位科学家进行领导。
现在你需要雇用更多的科学家来领导所有的项目：
阿利加博士和桑托斯博士。
由于宗教的原因，这两个新加入的科学家都不能领导Choice项目。
下表显示了所有的项目、科学家以及他们的投标情况。
阿加利博士
桑托斯博士
250
111
1
333
555
1.解题思路：
与问题六类似，“不能领导”在系数矩阵中体现为对应的系数为-10000。
因为本题中项目数小于博士人数，所以我们自行加入两个虚拟项目，把本题转化为标准指派问题。
由于Release项目和Hope项目都要由2位博士来领导，故将Hope项目变为Hope项目1与Hope项目2，Release项目变为Release项目1与Release项目2。
这样就将题目转化成了7个项目对应7位博士的标准型指派问题。
结果中求出的领导Release项目1与Release项目2的博士则是领导Release项目的两位博士，求出的领导Hope项目1和Hope项目2的两位博士则是领导Hope项目的博士。
如上图所示，自变量矩阵中“1”代表对应的博士领导对应的项目，4位博士的总投标点数即总满意度为3226。
其中，Hope项目由阿加利博士与桑托斯博士领导，Release项目由特塞博士与罗林斯博士领导。
第五部分后期优化改进
（一）解法缺陷
在对问题的初步研究求解之后我们发现了原有解法的两点缺陷：
第一，原目标函数设置是要求所求总满意度最大化，这种目标设置只是站在了决策者的角度考虑问题，没有充分考虑博士的感受，有可能会影响其做项目的积极性，从而对项目推进产生阻碍，进而影响公司利益；
第二，题目中原先只给出了一个指标，即个人满意度，这仅仅考虑了博士个人的兴趣，但并未考虑到其能力是否与兴趣匹配，致使可能产生这样一种情况：
某个博士很倾向于领导某个项目，但实际上他并没有足够的能力来完成这个项目。
针对上述两个弊端，我们从以下三个方面进行一些改进：
（1）将总满意度最大化目标改为最小满意度最大化。
（2）在原题单一指标（兴趣度指数）基础上再引进另一个指标（项目适应度指数），做到既考虑博士个人兴趣，又考虑他对这个项目的适应性。
（3）变更角度，利用博弈论相关知识进行新一轮的思考。
（二）优化改进
1.最小满意度最大化
在博弈论中，有极大化极小策略：
一种选择所有最小收益中的最大值的策略。
依据这样的思路，类似地，我们可以得到最小满意度最大化：
一种选择所有最小满意度中的最大值的策略。
以警匪问题为例来说明这种思想：
有n名警察和n名小偷，每个警察对应追一个小偷，由于n名警察和n名小偷个人能力及素质不同，因此分配不同的警察去最追捕不同的小偷，每个人追到小偷所花费的时间是不同的。
在原有解法中，我们希望最终的分配方案可以使得这n名警察所花费的总时间最短，但是应用最小满意度最大化思想，我们希望最终方案使得花费时间最长的那个警察所花费的时间是在所有方案中的最长时间中最短的。
最小满意度最大化是一种保守策略，它不追求最大利益，而是避免比较大的风险和亏损。
我们选择最小满意度最大化策略，也是出于保守考虑，使得泰泽制药公司在新项目研究开发时避免过大的风险。
现在我们将最小满意度最大化方法应用在本题中，即给定一种方案，使得每个博士所领导的项目对应的最小满意度是所有可选方案中的最小满意度之中最大的。
下面我们以这种方法重新依次解一遍原题的第1、2、3、4、6、7问：
（一）问题一（最大化指派问题）：
注：
①自变量设置与前期设法一致；
②约束条件与前期一致：
两个约束分别为投标约束和项目约束；
③新解法新增个人满意度行：
这行的数据来源是对应的自变量列乘以对应的满意度系数列
④目标函数：
目标函数为Min{个人满意度行}，在求解时使得目标函数取得最大值；
⑤总满意度：
总满意度为自变量矩阵与满意度系数矩阵对应相乘；
⑥对比：
同一道题应用原解法得出总满意度为3226，新解法也为2351，由此我们可以看到两种求解方法并不一定会得到不同的解。
（二）问题二（人数小于项目数的指派问题）：
求解：
同一道题应用原解法得出总满意度为2251，新解法也为2251，由此我们可以看到两种求解方法并不一定会得到不同的解。
（三）问题三（一人可以领导多个项目的指派问题）：
同一道题应用原解法得出总满意度为2518，新解法也为2518，由此我们可以看到两种求解方法并不一定会得到不同的解。
（四）问题四（一人可以领导多个项目的指派问题）：
同一道题应用原解法得出总满意度为2169，新解法也为2169，由此我们可以看到两种求解方法并不一定会得到不同的解。
（六）问题六（某人不能领导某项目的指派问题）：
同一道题应用原解法得出总满意度为2143，新解法也为2143，由此我们可以看到两种求解方法并不一定会得到不同的解。
升级会员 