运筹学指派问题实验报告(共33页).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项目1000100267100Stable项目40020010015333Choice项目2008001009933Hope项目200010045134Release项目100060030800第二部分 指派问题的标准形式与建模指派问题（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)数学模型为第三部分 不同类型的指派问题 我们将指派问题分为几个不同的类型，解决不同指派问题的基本理念是将其转化为标准型，之后再求解。（一） 最大化指派问题 生活中有许多问题是需要我们求目标函数的最大值的，例如本题中我们需要求解使科学家的满意度最大化。这时，我们就需要了解与掌握最大化指派问题的解法。 最大化指派问题的解法同标准型指派问题类似，只是将目标函数取最小值改为目标函数取最大值。其余的建模与求解过程均与标准型相同。（以下几种类型的问题，我们默认均以最大化问题为前提。）（二） 人数与项目数不等的指派问题这里默认一人只能领导一个项目。将问题转化为标准指派问题是求解问题的主体思路。人数与项目数不等的指派问题分为两种情况，一种是人数小于项目数的指派问题，另一种是人数大于项目数的指派问题。我们将原问题默认为最大化指派问题，即求目标为目标函数的最大值。首先，关于人数小于项目数的指派问题的解法，我们需要添加虚拟的人，虚拟人的个数与人数和项目数之间的差额确定，并将虚拟人对应的系数矩阵中的系数设置为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点。下表显示了米凯博士、克瓦尔博士和罗林斯博士投标情况：项目米凯博士克瓦尔博士罗林斯博士Up项目30086不能领导Stable项目不能领导34350Choice项目12517150Hope项目不能领导不能领导100Release项目175不能领导600在这种情况下，让哪一个科学家领导哪一个项目才能使得对项目的热情最大？1.解题思路：本题同样利用0-1整数规划求解，但与之前不同的是本题中存在博士不能领导项目的情况，因为我们的目标为总满意度最大化，故我们在系数矩阵中将不能领导转化为一个负无穷大，本题求解过程中我们将其设置为-10000。2.目标：博士的总满意度最大化3.Excel求解过程：如下图 4.结论:如上图所示，自变量矩阵中“1”代表对应的博士领导对应的项目，4位博士的总投标点数即总满意度为2143。 （七）问题七（项目数小于人数的指派问题）： 你觉得Release项目和Hope项目太复杂了，各让一位科学家分别进行领导是不太合适的。因此，这两个项目都要指派两位科学家进行领导。现在你需要雇用更多的科学家来领导所有的项目：阿利加博士和桑托斯博士。由于宗教的原因，这两个新加入的科学家都不能领导Choice项目。下表显示了所有的项目、科学家以及他们的投标情况。项目克瓦尔博士朱诺博士特塞博士米凯博士罗林斯博士阿加利博士桑托斯博士Up项目860100300不能领导250111Stable项目343200100不能领导502501Choice项目17180010012550不能领导不能领导Hope项目不能领导0100不能领导100250333Release项目不能领导0600175600250555 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项目的博士。2.目标：博士的总满意度最大化3.Excel求解过程：如下图 4.结论:如上图所示，自变量矩阵中“1”代表对应的博士领导对应的项目，4位博士的总投标点数即总满意度为3226。其中，Hope项目由阿加利博士与桑托斯博士领导，Release项目由特塞博士与罗林斯博士领导。第五部分 后期优化改进 （一）解法缺陷 在对问题的初步研究求解之后我们发现了原有解法的两点缺陷：第一，原目标函数设置是要求所求总满意度最大化，这种目标设置只是站在了决策者的角度考虑问题，没有充分考虑博士的感受，有可能会影响其做项目的积极性，从而对项目推进产生阻碍，进而影响公司利益；第二，题目中原先只给出了一个指标，即个人满意度，这仅仅考虑了博士个人的兴趣，但并未考虑到其能力是否与兴趣匹配，致使可能产生这样一种情况：某个博士很倾向于领导某个项目，但实际上他并没有足够的能力来完成这个项目。针对上述两个弊端，我们从以下三个方面进行一些改进：（1） 将总满意度最大化目标改为最小满意度最大化。（2） 在原题单一指标（兴趣度指数）基础上再引进另一个指标（项目适应度指 数），做到既考虑博士个人兴趣，又考虑他对这个项目的适应性。（3） 变更角度，利用博弈论相关知识进行新一轮的思考。 （二）优化改进 1.最小满意度最大化 在博弈论中，有极大化极小策略：一种选择所有最小收益中的最大值的策略。依据这样的思路，类似地，我们可以得到最小满意度最大化：一种选择所有最小满意度中的最大值的策略。以警匪问题为例来说明这种思想：有n名警察和n名小偷，每个警察对应追一个小偷，由于n名警察和n名小偷个人能力及素质不同，因此分配不同的警察去最追捕不同的小偷，每个人追到小偷所花费的时间是不同的。在原有解法中，我们希望最终的分配方案可以使得这n名警察所花费的总时间最短，但是应用最小满意度最大化思想，我们希望最终方案使得花费时间最长的那个警察所花费的时间是在所有方案中的最长时间中最短的。最小满意度最大化是一种保守策略，它不追求最大利益，而是避免比较大的风险和亏损。我们选择最小满意度最大化策略，也是出于保守考虑，使得泰泽制药公司在新项目研究开发时避免过大的风险。现在我们将最小满意度最大化方法应用在本题中，即给定一种方案，使得每个博士所领导的项目对应的最小满意度是所有可选方案中的最小满意度之中最大的。下面我们以这种方法重新依次解一遍原题的第1、2、3、4、6、7问：（一） 问题一（最大化指派问题）：根据所给出的投标情况，你需要为每一个项目指派一位资深的科学家并且使得这位科学家的满意度最高。那么应当怎样进行指派？注：自变量设置与前期设法一致；约束条件与前期一致：两个约束分别为投标约束和项目约束；新解法新增个人满意度行：这行的数据来源是对应的自变量列乘以对应的满意度系数列目标函数：目标函数为Min个人满意度行，在求解时使得目标函数取得最大值；总满意度：总满意度为自变量矩阵与满意度系数矩阵对应相乘；对比：同一道题应用原解法得出总满意度为3226，新解法也为2351，由此我们可以看到两种求解方法并不一定会得到不同的解。（二） 问题二（人数小于项目数的指派问题）：罗林斯博士接到了哈佛医学院的邀请去完成一个教学任务，而你却非常想把她留下来。但是哈佛的声望会使她离开公司。如果这种情况真的发生的话，公司就只有放弃那个最缺乏热情的项目。公司应当放弃哪一个项目？ 求解： 注：自变量设置与前期设法一致；约束条件与前期一致：两个约束分别为投标约束和项目约束；新解法新增个人满意度行：这行的数据来源是对应的自变量列乘以对应的满意度系数列目标函数：目标函数为Min个人满意度行，在求解时使得目标函数取得最大值；总满意度：总满意度为自变量矩阵与满意度系数矩阵对应相乘；对比：同一道题应用原解法得出总满意度为2251，新解法也为2251，由此我们可以看到两种求解方法并不一定会得到不同的解。（三） 问题三（一人可以领导多个项目的指派问题）：当然你并不愿意放弃任何一个项目，因为如果放弃一个项目而只剩下4个项目的话，会大大降低找到突破性新药的概率。你决定让朱诺博士或者米凯博士同时领导两个项目。大只有4个科学家的情况下，让哪一个科学家领导哪一个项目才能使得对项目的热情最大？注：自变量设置与前期设法一致；约束条件与前期一致：两个约束分别为投标约束和项目约束；新解法新增个人满意度行：这行的数据来源是对应的自变量列乘以对应的满意度系数列目标函数：目标函数为Min个人满意度行，在求解时使得目标函数取得最大值；总满意度：总满意度为自变量矩阵与满意度系数矩阵对应相乘；对比：同一道题应用原解法得出总满意度为2518，新解法也为2518，由此我们可以看到两种求解方法并不一定会得到不同的解。（四）问题四（一人可以领导多个项目的指派问题）：如果朱诺博士被告知她和米凯博士都有机会来同时领导两个项目，她决定要改变好的投标。朱诺博士对每一个项目的投标的情况如下所示：Up项目：20Stable项目：450Choice项目：451Hope项目：39Release项目：40在只有4个科学家的情况下，让哪一个科学家领导哪一个项目才能使得对项目的热情最大？求解：注：自变量设置与前期设法一致；约束条件与前期一致：两个约束分别为投标约束和项目约束；新解法新增个人满意度行：这行的数据来源是对应的自变量列乘以对应的满意度系数列目标函数：目标函数为Min个人满意度行，在求解时使得目标函数取得最大值；总满意度：总满意度为自变量矩阵与满意度系数矩阵对应相乘；对比：同一道题应用原解法得出总满意度为2169，新解法也为2169，由此我们可以看到两种求解方法并不一定会得到不同的解。（六） 问题六（某人不能领导某项目的指派问题）： 现在我们还是来分析拥有5位科学家的情况。但是，你决定有几个科学家不能领导几个特定的项目。具体来说米凯博士在免疫系统的研究方面没有什么经验，所以他不能领导Hope项目。而且他的家族有着躁狂抑郁病的病史，所以你觉得他作为一个项目的领导者参与到Stable项目的研究中是不太合适的。于是米凯博士也不能领导Stable项目。克瓦尔博士由于在免疫系统的研究方面没有什么 经验，也不能领导Hope项目。还有克瓦尔博士由于在心血管系统的研究方面没有什么经验，不能领导Release项目。罗林斯博士由于家族有低血压的病史，所以你觉得她作为一个项目的领导者参加到Up项目中是不太合适的，所以罗林斯博士不能领导Up项目。因为米凯博士和克瓦尔博士都有两个项目不能进行领导，所以他们每人的投标点就只剩下600点。罗林斯博士由于有一个项目不能进行领导，所以她的投标点剩下800点。下表显示了米凯博士、克瓦尔博士和罗林斯博士投标情况：项目米凯博士克瓦尔博士罗林斯博士Up项目30086不能领导Stable项目不能领导34350Choice项目12517150Hope项目不能领导不能领导100Release项目175不能领导600在这种情况下，让哪一个科学家领导哪一个项目才能使得对项目的热情最大？求解：注：自变量设置与前期设法一致；约束条件与前期一致：两个约束分别为投标约束和项目约束；新解法新增个人满意度行：这行的数据来源是对应的自变量列乘以对应的满意度系数列目标函数：目标函数为Min个人满意度行，在求解时使得目标函数取得最大值；总满意度：总满意度为自变量矩阵与满意度系数矩阵对应相乘；对比：同一道题应用原解法得出总满意度为2143，新解法也为2143，由此我们可以看到两种求解方法并不一定会得到不同的解。（七）问题七（项目数小于人数的指派问题）： 你觉得Release项目和Hope项目太复杂了，各让一位科学家分别进行领导是不太合适的。因此，这两个项目都要指派两位科学家进行领导。现在你需要雇用更多的科学家来领导所有的项目：阿利加博士和桑托斯博士。由于宗教的原因，这两个新加入的科学家都不能领导Choice项目。下表显示了所有的项目、科学家以及他们的投标情况。项目克瓦尔博士朱诺博士特塞博士米凯博士罗林斯博士阿加利博士桑托斯博士Up项目860100300不能领导250111Stable项目343200100不能领导502501Choice项目17180010012550不能领导不能领导Hope项目不能领导0100不能领导100250333Release项目不能领导0600175600250555注:满意度-10000代表不能领导的项目求解：首先将原题系数矩阵转化如下：注：自变量设置与前期设法一致；约束条件与前期一致：两个约束分别为投标约束和项目约束；新解法新增个人满意度行：这行的数据来源是对应的自变量列乘以对应的满意度系数列目标函数：目标函数为Min个人满意度行，在求解时使得目标函数取得最大值；总满意度：总满意度为自变量矩阵与满意度系数矩阵对应相乘；对比：同一道题应用原解法得出总满意度为3226，新解法为2101，由此我们可以看到选取保守策略会在牺牲一定程度的总满意度，显然这种最小满意度最大化方法不能得到最大的总满意度。 2.双目标策略双目标策略的应用是为了改进原有的第二个缺陷，使得判断标准从原先的单一指标即兴趣度指数转为双指标：兴趣度和项目适应度。其中，兴趣度作为主观指标，项目适应度作为客观指标。项目适应度的数据来源于博士个人能力和以往项目经验两个方面，综合起来产生博士对项目的适应度。关于具体数据来源：主观指标数据由题目中给出，是以每一位博士为主体，每一个人分配1000个投标点，其中每有一个博士不能领导的项目，该博士的投标点减少200；客观指标数据由我们自行给出，以每一个项目为主体，给每一个项目分配700个投标点，其中每有一个博士不能领导这个项目，该项目的投标点减少100。如此我们可以得出如下两张系数矩阵（以第六题为例）：注：表格中阴影部分代表博士不能领导的项目我们将表格中的原数据归一化后，设为主观指标，表示第i个博士对第j项工作的兴趣点， 为客观指标，表示第 j项工作由第i个博士完成的合适性，【0,1】，【0,1】。建模过程如下：可以看到约束条件和自变量设置都与前面一致，唯一不同的在于目标函数的设置。我们给出两种目标函数的设置方法将这两个指标综合考虑：将两个指标直接相乘：为两个指标分配不同权重并相加：这里我们假设比例为4:6至此建模过程结束，下面是excel的求解过程：注：自变量设置与前期设法一致；约束条件与前期一致：两个约束分别为投标约束和项目约束；新增：归一化个人满意度行：这行的数据来源是对应的自变量列乘以对应的满意度系数列之后归一归一化项目适应性列：这列的数据来源是对应的自变量行乘以对应的适应度系数行之后归一个人最小满意度：Min归一化个人满意度行项目最小适应性：Min归一化项目最小适应性列目标函数：目标函数一：个人最小满意度*项目最小适应性目标函数二：0.4*项目最小适应性+0.6*个人最小满意度最终结果如下表所示： 3.从博弈论的角度思考指派问题 传统指派方法体现的集体理性。而从博弈论的角度，体现的是个体理性。在实际中，被指派人往往是理性的，即每个人都想承担自己效率最大的任，为组织创造最大 的效用，并获得最多的收人。在这种情况下，常常出现 n 个人中存在 2人或多人争抢同一任务的情况。对于这种情况，传统指派问题均以整体效率最大化为目标化解冲突。然而，从博弈论的角度看，这种冲突化解方法不符合个体理性。事实上，指派问题是一个被指派人追求效率最大化的完全信息静态博弈过程。因此，本文从博弈论的角度研究指派问题，即在被指派人是理性的且理性是被指派人的共同知识的情况下，求解每个参与人的最优选择。从另一个角度来理解，假设指派问题是一个被指派人选择任务的博弈，所有被指派人事先达成一项协议，规定每个人的选择。那么，在没有外在约束力的情况下，当事人是否会自觉遵守这个协议?如果当事人会自觉遵守这个协议，那么这个协议构成一个纳什均衡:给定别人遵守协议的情况下，没有人有积极性偏离协议中规定的自己的选择。为了寻找这种协议，提出一个求解指派问题纳什均衡的简化方法，并证明了不存在冲突的指派问题的最优解一定为纯纳什均衡解，存在冲突的指派问题的纳什均衡解小于等于指派问题的最优解，且有限指派问题有且仅有纯纳什均衡解。问题一（2人4项任务的指派问题）：如图所示 ，一个2人4项任务的指派问题。与本题对应的博弈问题是，在每个参与人追求最大效率的工作的假设下，构成纳什均衡的指派方案是什么?为了求解这个方案，需要将指派问题转化为博弈问题的形式，见表2。其中，甲、乙的目标为追求各自效率最大的任务。表格中的数字代表着支付，其中支付的含义为每个人创造的效用。将上表打来得到以下表格。 表格中数字仍然代表着支付，其中左侧的数字为甲的支付，右侧的数字为乙的支付。由于同一个任务不能由同一人领导，故主对角线上的数字均为(-，-)。利用划线法求纳什均衡解：（其中，划线法的基本步骤：依据策略之间的相对优劣关系，分别寻找行和列的最优解：固定其中一个量，在另一个量收益大的下面划线；然后固定另一个量，对另外一个量收益大的划线。两者都有线的就是纯策略纳什均衡。）使用划线法求解纳什均衡，存在两个纯纳什均衡解： (1)甲承担任务G，乙承担任务E，目标值25。 (2)甲承担任务J，乙承担任务G，目标值27。以上的两个解都是充分考虑了个体理性得到的解，同时我们也可以在其中选择目标值最大的第二个方案，这样选择出的方案就是既考虑了集体理性，又考虑了个体理性后得到的解，也就是我们想要得到的最优方案。利用同样的方法，我们可以将二人的问题拓展到更多人的情况。问题二（3人4项任务的指派问题）：表格中的数字代表着支付，其中支付的含义为每个人创造的效用。将上表打来得到以下表格。使用划线法求解纳什均衡，存在四个纯纳什均衡解： (1)甲承担任务G，乙承担任务R，丙承担任务J，目标值35。 (2)甲承担任务R，乙承担任务G，丙承担任务J，目标值39。(3)甲承担任务R，乙承担任务J，丙承担任务G，目标值40。(4)甲承担任务G，乙承担任务J，丙承担任务R，目标值37。以上的四个解都是充分考虑了个体理性得到的解，同时我们也可以在其中选择目标值最大的第三个方案，这样选择出的方案就是既考虑了集体理性，又考虑了个体理性后得到的解，也就是我们想要得到的最优方案。第六部分 组员感想与收获 经过做这次的运筹学实践大作业，我有许多感受，也得到了许多收获。 1.认识“指派问题”首先，最直接的就是我认识并熟知了一个新的问题指派问题。指派问题是运筹学课上老师没有讲授过的内容，对我们来说也算是一个全新的知识。而这个全新的问题对于我们来说是一个挑战，它从很大程度上考察我们学以致用、举一反三、查阅资料的能力。我们从理解问题入手，将我们学到的与指派问题有联系的知识一点点运用到指派问题的解决中。同时，我们也从网络中查阅了大量的论文和资料来更好地理解和深刻的了解指派问题。经过了大半个学期对指派问题的研究，现在我已经深刻地理解了指派问题的内涵与不同类型的指派问题的解决方法。 2.深入思考问题运筹学实践的汇报分为了中期与末期答辩，这也就给了我们一个很好的深入思考问题的机会。中期答辩的时候，我们只是简单的介绍了指派问题的含义、类型以及布置的实际问题的基本解题思路、步骤与结果。而我们之后对这些问题进行了更深一层次的思考，例如在中期答辩时，我们只考虑了总体满意度最大化，也就是集体理性。而之后我们由想到了实际生活中，不能单单只考虑科学家的总体满意度，还要顾及到科学家个人的心理和情绪。于是，我们之后将总满意度最大化改为最小满意度最大化，其实只是简单地修改了一下目标函数，但却得到了完全与之前不同的答案。另外，之前的题目中只给出了一个指标，即个人满意度，这仅仅考虑了博士个人的兴趣，但并未考虑到其能力是否与兴趣匹配，致使可能产生这样一种情况：某个博士很倾向于领导某个项目，但实际上他并没有足够的能力来完成这个项目。于是，我们在后期改进中又引入了适应性系数这一指标，利用双目标决策的方法重新求解问题，得到了更符合实际的答案。 3.多学科融合在做运筹学实践大作业期间，我们不仅仅使用了运筹学这一门学科的理论与知识，还利用了管理学、微观经济学的一部分知识。我们从管理学的角度对这个实际问题进行考量，分别站在管理者与被雇佣者的角度去思考指派问题，使我们最终得到的方案在实际中可以得到最好的效果。另外，我们也从博弈论的角度对指派问题进行了深入的思考，利用划线法求解纳什均衡解，使我们得到的方案既满足集体理性，又满足个体理性。其实，在我们解决许多其他问题时，我们也要学会将多学科融合，利用我们所学到的不同方面的知识，这样可以从一个更广泛的角度去对问题有一个全新的认识。 4.理论联系实际理论联系实际正是运筹学实践这门课的意义所在。我们学习了这么多不同学科甚至不同专业的知识，如果不能将我们学到的理论学以致用，那么学习这些知识的意义就不存在了。这次运筹学实践课程让我认识到了学以致用的重要性。我们不能仅仅纸上谈兵，而是要将学到的知识用到我们的生活与学习之中。 5.团队合作通过这次大作业，也让我意识到了团队合作的重要性以及团队合作的高效性，每个人做每个人擅长的部分，把每个人的优点加总就可以把任务完成得准确且高效。每个人在团队里都扮演着不同的角色，每个角色也都发挥着自己必不可少的作用，良好的合作才可以产生一加一大于二的效果。