下载文档原格式
![运筹学课件ch5指派问题[全文]](https://img.taocdn.com/s1/m/76c0dd89b9f3f90f77c61b19.png)
运筹学课件ch5指派问题[全文] 指派问题assignment problem 运筹学课件一种特殊的线性规划问题，我们也经常遇到指派人员做某项工作的情况。
指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。
其他的一些应用如为一项任务指派机器、设备或者是工厂。
指派问题运筹学课件指派问题的形式表述:给定了一系列所要完成的任务(tasks)以及一系列完成任务的被指派者(assignees)，所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务。
指派问题模型运筹学课件指派问题的假设:被指派者的数量和任务的数量是相同的每一个被指派者只完成一项任务每一项任务只能由一个被指派者来完成每个被指派者和每项任务的组合有一个相关成本目标是要确定怎样进行指派才能使得总成本最小指派问题模型运筹学课件指派问题assignment problem 【例51></a>.14】人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人(经考核四人在不同岗位的成绩(百分制)如表5-34所示，如何安排他们的工作使总成绩最好。
88809086丁90798382丙95788795乙90739285甲DCBA工作人员表5-34【解】设1 数学模型运筹学课件数学模型为:甲乙丙丁ABCD图5. 3指派问题assignment problem运筹学课件假设m个人恰好做m项工作，第i个人做第j项工作的效率为cij?0，效率矩阵为[cij](如表5-34)，如何分配工作使效率最佳(min或max)的数学模型为指派问题assignment problem运筹学课件2 解指派问题的匈牙利算法匈牙利法的条件是:问题求最小值、人数与工作数相等及效率非负【定理5.1】如果从分配问题效率矩阵[cij]的每一行元素中分别减去(或加上)一个常数ui(被称为该行的位势)，从每一列分别减去(或加上)一个常数vj(称为该列的位势)，得到一个新的效率矩阵[bij]，其中bij=cij,ui,vj,则[bij]的最优解等价于[cij]的最优解，这里cij、bij均非负(指派问题assignment problem【证】运筹学课件【定理5.2】若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素(称为独立元素)的最大个数( 如果最少直线数等于m，则存在m个独立的“0”元素，令这些零元素对应的xij等于1，其余变量等于0，这时目标函数值等于零，得到最优解(两个目标函数相差一个常数 u+v,约束条件不变,因此最优解不变。
三类指派问题1. 简介三类指派问题是运筹学中的一类经典问题，它的目标是找到一种最优分配方案，将若干个任务分配给若干个执行者，使得总体成本或效益达到最小或最大。
这类问题通常可以用线性规划模型来描述和求解。
三类指派问题包括： - 任务分配问题：将若干个任务分配给若干个执行者，使得总体成本最小或效益最大。
- 作业调度问题：将若干个作业安排在若干台机器上进行处理，使得总体完成时间最短或机器利用率最高。
- 设备调度问题：将若干个任务安排在若干台设备上进行处理，使得总体完成时间最短或设备利用率最高。
2. 任务分配问题2.1 模型描述假设有n个任务和n个执行者，每个任务只能由一个执行者完成，并且每个执行者只能处理一个任务。
每个任务与每个执行者之间都有一个成本或效益值。
我们的目标是找到一种分配方案，使得总体成本最小或效益最大。
可以使用二维数组C表示各任务与各执行者之间的成本或效益值，其中C[i][j]表示第i个任务分配给第j个执行者的成本或效益值。
定义一个二进制变量X[i][j]，如果第i个任务分配给第j个执行者，则X[i][j]=1，否则X[i][j]=0。
任务分配问题可以用下面的线性规划模型来描述：minimize ∑(i=1 to n)∑(j=1 to n) C[i][j] * X[i][j]subject to∑(i=1 to n) X[i][j] = 1, for j = 1,2,...,n∑(j=1 to n) X[i][j] = 1, for i = 1,2,...,nX[i][j] ∈ {0, 1}, for i,j = 1,2,...,n2.2 求解方法常用的求解任务分配问题的方法有匈牙利算法和线性规划方法。
匈牙利算法是一种经典的图论算法，它通过构建增广路径来找到最优分配方案。
该算法的时间复杂度为O(n^3)，适用于小规模问题。
线性规划方法则通过将任务分配问题转化为线性规划模型，并利用线性规划求解器进行求解。
运筹学指派问题实验报告书运筹学实践报告指派问题第⼀部分问题背景泰泽公司（Tazer）是⼀家制药公司。
它进⼊医药市场已经有12年的历史了，并且推出了6种新药。
这6种新药中5种是市场上已经存在药物的同类产品，所以销售的情况并不是很乐观。
然⽽，主治⾼⾎压的第6种药物却获得了巨⼤的成功。
由于泰泽公司拥有⽣产治疗⾼⾎压药物的专利权，所以公司并没有遇到什么竞争对⼿。
仅仅从第6种药物中所获得的利润就可以使泰泽公司正常运营下去。
在过去的12年中，泰泽公司不断地进⾏适量的研究和发展⼯作，但是却并没有发现有哪⼀种药物能够获得像⾼⾎压药物⼀样的成功。
⼀个原因是公司没有⼤量投资进⾏创新研究开发的动⼒。
公司依赖⾼⾎压药物，觉得没有必要花费⼤量的资源寻找新药物的突破。
但是现在泰泽公司不得不⾯对竞争的压⼒了。
⾼⾎压药物的专利保护期还有5年1。
泰泽公司知道只要专利期限⼀到，⼤量药品制造公司就会像秃鹰⼀样涌进市场。
历史数据表明普通药物会降低品牌药物75%的销售量。
今年泰泽公司投⼊⼤量的资⾦进⾏研究和开发⼯作以求能够取得突破，给公司带来像⾼⾎压药物⼀样的巨⼤成功。
泰泽公司相信如果现在就开始进⾏⼤量的研究和开发⼯作，在⾼⾎压药物专利到期之后能够发明⼀种成功药物的概率是很⾼的。
作为泰泽公司研究和开发的负责⼈，你将负责选择项⽬并为每⼀个项⽬指派项⽬负责⼈。
在研究了市场的需要，分析了当前药物的不⾜并且拜会了⼤量在有良好前景的医药领域进⾏研究的科学家之后，你决定你的部门进⾏五个项⽬，如下所⽰：1⼀般来说，专利权保护发明的期限为17年。
在1995年，GATT⽴法拓展专利权的保护期限到20年。
在本案例之中，泰泽公司的⾼⾎压药物的注册时间是在1995年之前，所以专利权只能够保护这种药物17年。
Up项⽬：开发⼀种更加有效的抗忧郁剂，这种新药并不会带来使⽤者情绪的急剧变化。
Stable项⽬：开发⼀种治疗躁狂抑郁病的新药。
Choice项⽬：为⼥性开发⼀种副作⽤更⼩的节育⽅法。
