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

-
z.
运筹学实践报告
指派问题
-
z.
第一局部 问题背景
泰泽公司〔Tazer〕是一家制药公司。它进入医药市场已经有12年的历史了，并且推出了6种新药。这6种新药中5种是市场上已经存在药物的同类产品，所以销售的情况派问题分为两种情况，一种是人数小于工程数的指派问题，另一种是人数大于工程数的指派问题。我们将原问题默认为最大化指派问题，即求目标为目标函数的最大值。
首先，关于人数小于工程数的指派问题的解法，我们需要添加虚拟的人，虚拟人的个数与人数和工程数之间的差额确定，并将虚拟人对应的系数矩阵中的系数设置为0。添加虚拟人后，就将原问题转化为人数与工程数相等的标准型指派问题，接着按标准型指派问题的建模和求解步骤求解。得到结果后，虚拟人对应的工程就是我们应该放弃的工程。
另外，关于人数大于工程数的指派问题的解法，我们需要添加虚拟的工程，虚拟工程的个数与人数和工程数之间的差额确定，并将虚拟工程对应的系数矩阵中的系数与其对应的工程的系数一样。〔例如，A工程可以由两个人领导，则我们将A工程变为A1工程，并添加A2虚拟工程，使得A1与A2对应的系数相等。〕添加虚拟工程后，就将原问题转化为人数与工程数相等的标准型指派问题，接着按标准型指派问题的建模和求解步骤求解。得到结果后，分别领导一样系数工程的人即为共同领导同一工程的人。〔即求得分别领导A1与A2工程的人为共同领导A工程的人。〕
一人可以领导多个工程的指派问题
一人领导多个工程的指派问题其实与人数大于工程数的指派问题的解法类似，只是将虚拟工程改为虚拟人。
关于一人领导多个工程的指派问题的解法，我们需要添加虚拟的人，虚拟人的个数与人数和工程数之间的差额确定，并将虚拟人对应的系数矩阵中的系数与其对应的人的系数一样。〔例如，甲可以同时领导两个工程，则我们将甲变为甲1，并添加甲2虚拟人，使得甲1与甲2对应的系数相等。〕添加虚拟人后，就将原问题转化为人数与工程数相等的标准型指派问题，接着按标准型指派问题的建模和求解步骤求解。得到结果后，一样系数的人领导的工程则是这个人同时领导的工程。〔即求得甲1和甲2领导的工程即为甲所领导的两个工程。〕
*人不能领导*工程的指派问题
*人不能领导*工程，我们可以直接将对应于人和工程的穿插项的系数设置为一个负的无穷大的数，因为这里我们是要求目标函数的最大值。在后面的实际问题求解中，我们将系数设置为-10000。其余建模与求解过程与标准型指派问题一样。
-
z.
第四局部 实际问题分析
〔一〕问题一〔最大化指派问题〕：根据所给出的投标情况，你需要为每一个工程指派一位资深的科学家并且使得这位科学家的满意度最高。则应当怎样进展指派？
：选择一种方案使得5位博士的总满意度最大化。
*cel求解过程：如下列图
：投标约束表示一个博士只能领导一个约束。工程约束表示一个工程只能由一个博士领导。
:如上图所示，自变量矩阵中“1〞代表对应的博士领导对应的工程，5位博士的总投标点数即总满意度为2551。
〔二〕问题二〔人数小于工程数的指派问题〕：罗林斯博士接到了哈佛医学院的邀请去完成一个教学任务，而你却非常想把她留下来。但是哈佛的声望会使她离开公司。如果这种情况真的发生的话，公司就只有放弃那个最缺乏热情的工程。公司应当放弃哪一个工程？
：将问题转化为标准指派问题是求解问题的主体思路。因为此题目中存在5个工程和4位博士，所以添加一个虚拟博士，使得博士数目与工程数目相等。将虚拟博士的满意度系数均设置为0，求解出结果后虚拟博士所领导的工程则是泰泽公司需要抛弃的工程。
:博士总满意度最高。
*cel求解过程：如下列图
结论:如上图所示，自变量矩阵中“1〞代表对应的博士领导对应的工程，4位博士的总投标点数即总满意度为2251。虚拟博士所领导的Up工程则是需要抛弃的工程。
〔三〕问题三〔一人可以领导多个工程的指派问题〕：当然你并不愿意放弃任何一个工程，因为如果放弃一个工程而只剩下4个工程的话，会大大降低找到突破性新药的概率。你决定让朱诺博士或者米凯博士同时领导两个工程。大只有4个科学家的情况下，让哪一个科学家领导哪一个工程才能使得对工程的热情最大？
：博士的总满意度最大化
*cel求解过程：如下列图
：此题中存在4位博士和5个工程，其中朱诺博士或者米凯博士可以同时领导两个工程。工程约束与之前的题目类似，表示一个工程只能由一位博士领导。投标约束则与之前的题目中不同，此题中克瓦尔博士与特塞博士的投标约束仍然是对应一列数字加和为1。另外，约束要求朱诺博士与米凯博士的自变量总和为3且两人的对应列数字和均小于等于2。
-
z.
:如上图