运筹学指派问题

c1n c2 n cnn
关于模型的讨论
指派问题是运输问题的特殊情况 当n=m时，平衡指派问题 当 n m 时，不平衡指派问题，此时， 可设置虚工作或虚工作人员，将其化为 平衡指派问题。 对指派矩阵C，任意行（列）减去它的最 小元素后，所构成的指派问题最优解与 原指派问题相同。

45 0 40 65 45 55 55 0 0 5 0 45 0 55 60 55 45 45 0 45

0 20 40 60 95
45 0 40 65 45 55 55 0 0 5 0 45 0 55 60 55 45 45 0 45
回到第一步：圈零得新最优解
4 0 2 0 2 2 0 0 0 1 2 1 0 0 0 1 0 1 ( xij ) 0 0 0 0 0 1 1 0 0 0 0 0 1 0
最小的总工作时间：z=7+5+5+3=20。该问 题有多个最优解，请求出其它的最优解。
第八节 工作指派问题
工作指派问题及其数学模型 求解工作指派问题的匈牙利法 工作指派问题的应用举例
工作指派问题的数学模型
•例1-12
•指派问题数学模型 •指派矩阵 •对数学模型的讨论
匈牙利法
•匈牙利法的基本原理
•匈牙利法的计算步骤
•减数得零—求最优匹配
•圈零划线—查是否最大匹配
•找数调整—求新的最优匹配
ห้องสมุดไป่ตู้
指派问题一般模型
min z cij xij
j 1 i 1 n n
n xij 1, j 1,2, , n i n1 s.t. xij 1, i 1,2, , n j 1 xij 0,1

作业：作业：问题1：书本P100第6题效率矩阵效率矩阵码头1 码头2 码头3 码头4货船A货船B货船C货船D目标函数：使总运输成本最小目标函数：使总运输成本最小约束条件约束条件: :码头1 码头2 码头3 码头4货船A 1 0 0 0 1 = 1 货船B 0 0 0 1 1 = 1 货船C 0 0 1 0 1 = 1 货船D 0 1 0 0 1= 11 1 1 1 ====1 1 1 1最少成本最少成本2100问题问题 2: 2: 2: 书本书本书本P101P101P101第第7题效率矩阵效率矩阵A B C D E甲乙丙丁目标函数：使总花费时间最小目标函数：使总花费时间最小约束条件约束条件: :方案矩阵方案矩阵AB C D E甲 2.22E-16 1 0 0 0 1 <= 1 <= 2 乙 0 0 1 1 2.22E-16 1 <=2 <= 2 丙 0 1.11E-16 0 0 1 1 <=1 <=2 丁 1 0 0 4.44E-16 0 1 <=1 <=2 1 11 1 1= == ==11 1 1 1时间最少时间最少131问题3：五人翻译五种外文的速度（印刷符号：五人翻译五种外文的速度（印刷符号//小时）如下表所示：小时）如下表所示： 语种语种语种 人 英 俄俄 日日 德德 法法 甲甲乙 丙 丁 戊900 400 600 800 500 800 500 900 1000 600 900 700 300 500 800400 800 600 900 5001000 500 300 600 800若规定每人专门负责一个语种的翻译工作，那么，试解答下列问题：若规定每人专门负责一个语种的翻译工作，那么，试解答下列问题： （1）应如何指派，使总的翻译效率最高？应如何指派，使总的翻译效率最高？效率矩阵效率矩阵英俄 日 德 法 甲 乙 丙 丁目标函数：使翻译效率最高目标函数：使翻译效率最高约束条件约束条件: :方案矩阵方案矩阵英俄 日 德 法甲0 011 =1乙0 1 0 0 0 1 = 1 丙0 0 0 1 0 1 = 1丁 1 0 0 0 0 1 = 1 戊0 0 1 0 0 1 = 11 1 1 1 1= = = = =1 1 1 1 1效率最高 2200效率最高若甲不懂德文，乙不懂日文，其他数字不变，则应如何指派？（2）若甲不懂德文，乙不懂日文，其他数字不变，则应如何指派？方案矩阵方案矩阵英俄日德法甲0 1 0 0 0 1 = 1 乙0 0 0 0 1 1 = 1 丙0 0 0 1 0 1 = 1 丁 1 0 0 0 0 1 = 1 戊0 0 1 0 0 1 = 11 1 1 1 1= = = = =1 1 1 1 1。

运筹学作业-----关于指派问题的求解算法设计学院：计算机科学与技术学院班级：信息与计算科学1202班学号：20姓名：韩雪平1.问题描述与数学模型：在现实生活中，有各种各样的指派问题。

例如，有若干项工作（或者任务，事情）需要分配给若干人（或者部门，设备等）来完成；有若干项合同需要选择若干个投标者来承包；有若干条交通线（如航空线，航海线，公路线等）需要配置若干交通运输工具（如飞机，船只，汽车等）来运营；有若干班级需要安排在不同的教师里上课；等等/诸如此类问题，它们的基本要求是来满足特定的指派要求时，使指派方案的总体效果最佳。

由于指派总是多样性的，有必要定义指派的特定问题的标准形式。

指派问题的标准形式（以人和事为例）：设有n个人和n件事，已知第i个人做第j 件事的费用为cij(i,j=1,2,....n),求人与事之间一一对应的指派方案，使完成的这n件事的总费用最少。

一般称矩阵c11 c12 c13 c14 (1)c21 c22 c23 c24 (2)c31 c32 c33 c34 (3)C= . . . . .. . . . .. . . . .cn1 cn2 cn3 cn4……cn5为指派问题的系数矩阵。

在实际问题中，根据cij的具体意义，矩阵C可以有不同的名称，如费用矩阵，成本矩阵，时间矩阵等。

系数矩阵C中，第i行各元素表示第i人做各事的费用，第j列各元素表示第j件事由各个人做的费用。

为建立标准的指派问题的数学模型，引入n^2个0-1变量1 当指派第i人去做第i件事时Xij=｛（i，j=1,2,3……,n）0 当不指派第i人去做第j件事时然后对矩阵进行化解，当然作为可行解，矩阵中每一列都有且只有一个1，每行有且仅有一个1，以满足约束条件2．算法思想：标准的指派问题是特殊的整数规划问题，也是特殊的0—1规划问题和特殊的运输问题。

因此它可以用很多相应的解法来求解。

匈牙利解法的依据是指派问题的最优解的一下性质：设指派问题的系数矩阵C=（cij）n*n.若将C的一行或列分别减去一个常数K，则得到一个新的矩阵C'=（c'ij）n*n,那么C’为系数矩阵的指派问题和以C为系数矩阵的原指派问题有相同的最优解。

文 家 。汉 族 ，东 晋 浔阳 柴桑 人 （今 江西 九江 ） 。曾 做过 几 年小 官， 后辞 官 回家 ，从 此 隐居 ，田 园生 活 是陶 渊明 诗 的主 要题 材， 相 关作 品有 《饮 酒 》 、 《 归 园 田 居 》 、 《 桃花 源 记 》 、 《 五 柳先 生 传 》 、 《 归 去来 兮 辞 》 等 。
运筹学 指派问题
6
、
露
凝
无
游
氛
，
天
高
风
景
澈
。
7、翩翩新 来燕，双双入我庐 ，先巢故尚在，相 将还旧居。
8
、
吁
嗟
身
后
名
，
于
我
若
浮
烟
。
9、 陶渊 明（ 约 365年 —427年 ），字 元亮， （又 一说名 潜，字 渊明 ）号五 柳先生 ，私 谥“靖 节”， 东晋 末期南 朝宋初 期诗 人、文 学家、 辞赋 家、散
1
0
、
Байду номын сангаас
倚
南
窗
以
寄
傲
，
审
容
膝
之
易
安
。
1、最灵繁的人也看不见自己的背脊。——非洲 2、最困难的事情就是认识自己。——希腊 3、有勇气承担命运这才是英雄好汉。——黑塞 4、与肝胆人共事，无字句处读书。——周恩来 5、阅读使人充实，会谈使人敏捷，写作使人精确。——培根