当前位置：文档之家 › 运筹学__指派问题

运筹学__指派问题

  • 格式：ppt
  • 大小：1.82 MB
  • 文档页数：121

下载文档原格式

  / 121

合集下载

运筹学指派问题

运筹学指派问题

n
n
总成本最小
每项任务由一人完成 每人只承担一项任务
解矩阵的特征
• 全部元素仅取0或1 • 每行有且仅有一个1 • 每列有且仅有一个1
0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0
例如，n=5时， X xij
数学模型 : m in z cij xij j 1 i 1
n xij 1, j 1,2 ,...,n i 1 n s .t . xij 1, i 1,2 ,...,n j 1 x 0 ,1 i , j 1,2 ,...,n ij
在C中找出最多独立0的步骤
• 设Wi表示第i行0的数目,Lj表示第i列0的数目.
• 1.统计Wi和Lj（i,j=1,2,…n）.
• 2.按W1，W2，…,Wn,L1,L2,…,Ln顺序找出 第一个最小正数，选中该行（列）首个0. • 3.删除该0所在的行与列,对应的Wi=0,Lj=0. • 4.重复步骤1~3，直到全部Wi=0为止.
0
0
这样就找到 4个独立0
如果按自上而下从左到右顺序找
0 0 0 0 0 0 C 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
• 这样，4条线就覆盖了全部0
0 0 0 0 0 0
0
0 0
0 0 0 0

运筹学-0-1规划指派问题PPT课件

运筹学-0-1规划指派问题PPT课件
在0-1规划问题中，遗传算法通过模拟生物进化过程中的基因突变、交叉 和选择等过程来寻找最优解。算法从一个初始种群出发，通过不断迭代 进化，最终找到最优解。
遗传算法的优点是能够处理大规模、复杂的优化问题，且具有较强的鲁 棒性和全局搜索能力。缺点是算法实现较为复杂，需要较高的计算资源 和时间，且在某些情况下可能会陷入局部最优解。
指派问题通常具有整数约束和 0-1约束，即每个工人只能被分 配一项任务，且每个任务只能 由一个工人完成。
指派问题的解通常具有最优子 结构和局部最优解的特性。
变量定义
• $x{ij}$：如果第i个工人被分配第j项任务，则$x{ij}=1$； 否则$x_{ij}=0$。
目标函数
• $min \sum{i=1}^{n} \sum{ j=1}^{n} c{ij} x{ij}$： 最小化总成本。
04
指派问题在0-1规划中的应用
指派问题的定义
• 指派问题是一种组合优化问题，旨在将一组任务分配给一组工 人，使得总成本最小化。每个工人只能完成一项任务，每项任 务只能由一个工人完成。目标是找到一种最优的分配方式，使 得总成本最低。
指派问题的特点
指派问题具有NP难解的特点， 即没有已知的多项式时间算法 来解决该问题。
04
总结词：整数规划
பைடு நூலகம்
案例三：旅行商问题
总结词：旅行商问题
总结词：图论
详细描述：旅行商问题是一个经典的组合优 化问题，涉及到寻找一条最短路径，使得一 个旅行商能够访问一系列城市并返回出发城 市，同时最小化总旅行距离。
详细描述：图论是研究图形和图形结构的数 学分支，提供了解决旅行商问题和其他优化 问题的理论基础。
在0-1规划问题中，分支定界法将问题分解为多个子问题，每个子问题对应一种指派 方案。算法通过不断排除不可能的解来缩小搜索范围，最终找到最优解。

运筹学运输问题和指派问题

运筹学运输问题和指派问题

A1 A2 A3 销量
B1
B2
B3
B4
1
32
11 4 3
3 10
3 1 3 9 1 2 -1 8
4
7
6 4 12 10 3 5
3
6
5
6
产量
7 4 9 20
检验数<0表示：例如（A2,B4）如果增加A2到B4的1单 位产品，将会降低1单位的运费，所以，该解不是最优解。
解的改进
（1）以 xij 为换入变量，找出它在运输表中的闭回路；
工厂1 工厂2 工厂3 需求量
产品产1品1 41 41 40 40 37 37 20 20
单位成本
产品产2品2 27 27
产品产3品3 28 28
29 29
30 30
27 27
30 30
30 30
产品产4品4 24 24 23 23 21 21 40 40
生产能力
75 75 75 75 45 45
问题分析
第四章 运输问题和指派问题
运输问题
提到运输问题，想到什么？ 实际生活中有哪些方面涉及运输问题
快递业的运输问题 服装专卖店的转运问题等
运输问题的提出
某公司经销甲产品，它下设三个工厂和四个销售点。各工厂每日的产 量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如下表。 问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费 为最小。
总运费 =4*3+3*10+ 3*1+1*2+6*4+3*5=86（元）
最优解的检验——闭回路法
要判定运输问题的某个解是否为最优解，可仿照一般单纯 形法，检验这个解的各非基变量（对应于运输表格中的空 格）的检验数，若有某空格 (Ai, B的j ) 检验数为负，则说明将 变为xi j 基变量将使运费减少，故当前这个解不是最优解；若 所有空格的检验数全非负，则不管怎样变换解均不能使运 输费用减少，即为最优解。

三类指派问题

三类指派问题

三类指派问题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)，适用于小规模问题。

线性规划方法则通过将任务分配问题转化为线性规划模型，并利用线性规划求解器进行求解。

指派问题(经典运筹学)

指派问题(经典运筹学)
c 11 c 取 C 21 c n1 c 12 c 22 cn2 c1n c 2n c nn
1 1 c 11 2 c 21 … i c i1 … n c n1 2
c 12 c 22 ci2 cn2
…

1 2 3 4
6 20 10
21
25 14 0
5
x6
解：x i
1
2
0
不在第i个地区建站
i=1,2, …,6
Z表示全区消防站总数
2 6 1 x3 x4 1 s.t x3 x4 x5 1 x x x 1 4 5 6 x i 0 ,1 i 1, 2 , , 6
一、决策问题与0-1变量
决策变量
xi
x i 是否做第
i 件事 i 1, 2 , , n
1 0
做第i件事 不做第i件事
x1 x 2 x n k
n件事中必须做k件并只做k件事 n件事中最多做k件事 n件事中至少做k件事
x1 x 2 x n k x1 x 2 x n k
当n=4时， 有16变量，8个约束方程
例：现有4份工作，4个人应聘，由 于各人技术专长不同，他们承担 各项工作所需费用如下表所示， 且规定每人只能做一项工作，每 一项工作只能由一人承担，试求 使总费用最小的分派方案。
工作
Z表示总费用
max Z 3 x11 5 x12 4 x13 5 x14 6 x 21 7 x 22 6 x 23 8 x 24 8 x 31 9 x 32 8 x 33 10 x 34 10 x 41 10 x 42 9 x 43 11 x 44

运筹学运输与指派问题 ppt课件

运筹学运输与指派问题 ppt课件
a1 a2
am
18
设xk（ =0或1）表示第k个中转站启用次数，xik表示从第i个仓库运到第k个中转站的 物资数量，ykj表示从第k个中转站运到第j个单位的物资数量，则
p
mp
pn
z f k x k
d ik x ik
e kj y kj
k 1
i1 k 1
k 1 j1
p
x ik a i
… … … …… …
Am cm1 cm2 … cmn am
Am+1 0
0 … 0 am+1
销量 b1 b2 … bn
mn
minz
cij xij
n
i1
xij ai
j1
i 1, 2,..., m
j1
s.t. m xij bj j 1, 2,..., n
i1
xij 0 i 1, 2,..., m; j 1, 2,..., n
mn
minz
cij xij
n
i1 j1
xij ai
i 1, 2,..., m
s.t.
j 1 m
xij
bj
j 1, 2,..., n
i1
xij 0 i 1, 2,..., m; j 1, 2,..., n
若用表上作业法求之,可设一个假想销地, 使其销
量为bn+1=∑ai-∑bj,ci,n+1=0.
已知该厂的生产能力与生产成本如下表。若生产出的产品当季不交货，则需
储存、维护等费用1500元。要求在完成合同的情况下，做出全年生产费用最
小的决策。
生产能力与生产成本
季度
1 2 3 4
生产的能力（台）

运筹学指派问题课件

运筹学指派问题课件

c
i 1 j 1
n
n
ij
xij
n xij 1 i 1 n st . xij 1 (i , j 1, 2, ..., n) j 1 x 1or 0 ij
运筹学教程
例1：某商业公司计划开5家新商店，商业公司决定由5家建筑 公司分别承建。已知建筑公司Ai(i=1,2…5)对新商店Bj(j=1…5) 的建筑费用报价Cij.问题：商业公司对5家建筑公司如何分配任 务，才能使总的建筑费用最少？ Cij Ai Bj
运筹学教程
指派问题解法：匈牙利解法 解法思想：
若从系数矩阵C的任何一行（列）各元素中分别减去 一个常数K（K可正可负）得到新矩阵C’,则以C’为系 数矩阵的指派问题与原问题有相同的解，但最优值 比原问题最优值小K。
匈牙利法条件： MIN、i=j 、Cij≥0
运筹学教程
匈牙利法的主要步骤： 步骤1：变换系数矩阵，使在各行各列都出现零元素。 （1）从矩阵C的每行元素减去该行的最小元素；
0 11 8 7 7 3 3 2 1 C ' 5 0 4 3 4 0
第二步 圈0 寻找不同行不同列的0元素，圈之。 所在行和列其它0元素划掉
0 0 0 0 0 3 0 11 8 第三步 打 无的行打，打行上0列打 ， 1 7 7 3 打列上行打，打行上0列打 ' 2 3 2 1 C 0 5 0 4 0 3 0 11 8 0 1 7 7 3 2 3 4 0 C ' 0 2 3 2 1 第四步 确定方案划线 0 0 5 0 4 没有打行上画一条横线； 0 2 3 4 0 有打列上画一条竖线；
15 120 15 12 0 14 100 14 100 8 7 0 0 8 7

运筹学 工作指派问题

运筹学 工作指派问题

n
n
n
n
ij
) xij
n n
= M ∑∑ xij − ∑∑ cij xij = nM − ∑∑ cij xij
i =1 j =1
14
1 甲 乙 丙 丁 10 5 5 2 2 9 8 4 3 3 7 7 6 4 4 8 7 5 5
12
例1-15 求最大效率问题
上海港务局装卸队安排五个班组进行五条作 业线的配工，以往各班组完成某项作业的实 际效率的具体数据如下表所示。
项目 班组 甲 乙 丙 丁 戊 400 435 505 495 450 315 295 370 310 320 220 240 320 250 310 120 220 200 180 190 145 160 165 135 100 13 1 2 3 4 5
9
(4)画0元素的最少覆盖线：要用最少的覆盖线将矩 阵表格中的所有0元素都覆盖住。如果覆盖线的条 数少于矩阵的阶数，说明找不到最优解，要转下 步（继续变换矩阵，使0元素增加）。如果覆盖线 的条数等于矩阵的阶数，则说明可以从矩阵表格 的0元素中找出最优解。 画最少覆盖线的具体方法： ①对没有◎的行打√； ②对打√的行中，所有有0元素的列打√； ③对打√的列中，对有◎的行打√； ④重复②、③步直到得不出新的打√的行和列； ⑤对没有打√的行画横线，对打√的列画纵线，这 些横线和纵线就是能把全部0元素都覆盖的最少覆 盖线。
第一章 线性规划的基本 理论及其应用
1
第九节
工作指派问题
工作指派问题是这样一类问题： 有n个人和n件事，已知第i个人做第j件事的 费用为 cij (i, j = 1, 2, , n),要求确定人和事之间的 一一对应的指派方案，使完成这n件事的总 费用最少。

运筹学 指派问题

运筹学 指派问题

ij
ij

cij xij i xij j xij
ij
i
j
j
i
z i j
i
j
即z和 z’只相差一个常数,故它们有相同的最优解.
• 利用这个性质，可使原效率矩阵变换为含有很
多0元素的新效率矩阵，而最优解保持不变，在
效率矩阵(bij)中，我们关心位于不同行不同列
(显然z(x*)=0)
0*
如效率矩阵为

9
23
14 20 0*
9 0* 3
3 23 8


令(
xij
)


1 0 0
0 0 1
0 1 0
0
0

则xij是最 优解
0

0
12 14 0* ,


0 0 0 1
因此需对效率矩阵作变换,使变换后效率矩阵 (bij )nn
可行解矩阵
n
xij 1, j 1, 2, , n ②
i1
表明各列之和为1 。
n
xij 1, i 1, 2, , n ③
j1
表明各行之和为1 。
满足约束条件②～④的可行解xij构成的可行解矩阵，
矩阵中有n个为1,其余都为0,而且这n个1必位于矩阵的不
同行不同列上。对应于可行解xij的目标值是这n个cij之和.
如

2
3
0*
0
0

条位,于不同行不同列的”0”元素
0 * 10
5
7
2
的最大个数也为4.
9 8 0 0* 4

运筹学指派问题实验报告书

运筹学指派问题实验报告书

运筹学指派问题实验报告书运筹学实践报告指派问题第⼀部分问题背景泰泽公司（Tazer）是⼀家制药公司。

它进⼊医药市场已经有12年的历史了，并且推出了6种新药。

这6种新药中5种是市场上已经存在药物的同类产品，所以销售的情况并不是很乐观。

然⽽，主治⾼⾎压的第6种药物却获得了巨⼤的成功。

由于泰泽公司拥有⽣产治疗⾼⾎压药物的专利权，所以公司并没有遇到什么竞争对⼿。

仅仅从第6种药物中所获得的利润就可以使泰泽公司正常运营下去。

在过去的12年中，泰泽公司不断地进⾏适量的研究和发展⼯作，但是却并没有发现有哪⼀种药物能够获得像⾼⾎压药物⼀样的成功。

⼀个原因是公司没有⼤量投资进⾏创新研究开发的动⼒。

公司依赖⾼⾎压药物，觉得没有必要花费⼤量的资源寻找新药物的突破。

但是现在泰泽公司不得不⾯对竞争的压⼒了。

⾼⾎压药物的专利保护期还有5年1。

泰泽公司知道只要专利期限⼀到，⼤量药品制造公司就会像秃鹰⼀样涌进市场。

历史数据表明普通药物会降低品牌药物75%的销售量。

今年泰泽公司投⼊⼤量的资⾦进⾏研究和开发⼯作以求能够取得突破，给公司带来像⾼⾎压药物⼀样的巨⼤成功。

泰泽公司相信如果现在就开始进⾏⼤量的研究和开发⼯作，在⾼⾎压药物专利到期之后能够发明⼀种成功药物的概率是很⾼的。

作为泰泽公司研究和开发的负责⼈，你将负责选择项⽬并为每⼀个项⽬指派项⽬负责⼈。

在研究了市场的需要，分析了当前药物的不⾜并且拜会了⼤量在有良好前景的医药领域进⾏研究的科学家之后，你决定你的部门进⾏五个项⽬，如下所⽰：1⼀般来说，专利权保护发明的期限为17年。

在1995年，GATT⽴法拓展专利权的保护期限到20年。

在本案例之中，泰泽公司的⾼⾎压药物的注册时间是在1995年之前，所以专利权只能够保护这种药物17年。

Up项⽬：开发⼀种更加有效的抗忧郁剂，这种新药并不会带来使⽤者情绪的急剧变化。

Stable项⽬：开发⼀种治疗躁狂抑郁病的新药。

Choice项⽬：为⼥性开发⼀种副作⽤更⼩的节育⽅法。

运筹学 指派问题课件 PPT

运筹学 指派问题课件 PPT
产品1 产品2 产品3 产品4
效率表
工厂1 工厂2
58 75
69 50
180 150
260 230
工厂3 工厂4
65 82
70 55
170 200
250 280
2
返回总目录
例1 某公司拟将四种新产品配置到四个工厂生产，四 个工厂的单位产品成本（元/件）如下表所示。求最 优生产配置方案使得单位产品成本总和为最小。
15
返回总目录
第三步：用最少的直线覆盖所有0：
0 0 11 22 22 25 25 0 0 0 0 0 5 5 5 27 27 0 45 45 6 17 17 0 30 0 0 0 0 0 0 0 0 45 45 32 6 17 17 0 0 0 0 0 0 0 45 45
回到第三步，用最少的直线覆盖所有0。 此时最少直线数=4，表明矩阵中存在4个不同行不 同列的零元素，于是得到最优解。 第五步：找出4个独立的0元：
( 0 ) 30 0 32 6 17 17 0 ( 0) 0 0 0 ( 0 ) (0 ) 45 45 ( 0 ) 30 0 32 6 17 17 0 0 ( 0 ) 0 ( 0) 0 (0 ) 45 45
x14 x24 x34 x44
工厂2 x21 工厂3 x31 工厂4 x41
1 1 1 1
1
1
1
1
产品1 产品2 产品3 产品4
工厂1 工厂2 工厂3 工厂4 58 75 65 82 69 50 70 55 180 150 170 200 260 230 250
5280
返回总目录
数学模型 匈牙利算法 其他变异的指派问题

运筹学指派问题

运筹学指派问题
• 一个人可做几件事的指派问题
若某个人可做几件事，则可将该人看做相同的几个人来接受指派。这 几个人作同一件事的费用系数当然都一样。
• 某事一定不能由某人作的指派问题
若某事一定不能由某个人做，则可将相应的费用系数取做足够大的数 M。
例3：对于例2的指派问题，为了保证工程质量，经研究决定，舍 弃建筑公司A4和A5，而让技术力量较强的建设公司A1，A2，A3参加 招标承建，根据实际情况，可允许每家建设公司承建一项或二项工程。 求使总费用最少的指派方案。
步2：在变换后的系数矩阵中确定独立0元素（试指派）。若独立0元 素已有n个，则已得出最优解；若独立0元素的个数少于n个，转步3。
确定独立0元素的方法：当n较小时，可用观察法、或试探法；当n较 大时，可按下列顺序进行 • 从只有一个0元素的行（列）开始，给这个0元素加圈，记作，然后划 去所在的列（行）的其它0元素，记作。 •给只有一个0元素的列（行）的0加圈，记作，然后划去所在行的0元 素，记作。 •反复进行，直到系数矩阵中的所有0元素都被圈去或划去为止。 •如遇到行或列中0元素都不只一个（存在0元素的闭回路），可任选其中 一个0元素加圈，同时划去同行和同列中的其它0元素。被划圈的0元素即 是独立的0元素。
第二步：确定独立0元素, 即加圈 元素的个数m=4，而n=5，进 行第三步。
第三步：作最少的直线覆盖所有的0元素，目的是确定系数矩阵 的下一个变换。
第四步：对上述矩阵进行变换，目的是增加独立0元素个数。方法是在 未被直线覆盖的元素中找出一个最小元素，然后在打“”行各元素中 都减去这一元素，而在打“”列的各元素都加上这一最小元素，以保 持原来0元素不变（消除负元素）。得到新的系数矩阵。（它的最优解 和原问题相同，为什么？因为仅在目标函数系数中进行操作）

运筹学-0-1规划 指派问题

运筹学-0-1规划 指派问题

0
0 0
第三步：在矩阵[Cij]中，若不能得到m个（0）， 则进行第四步；若能得到m个（0），则令
[Cij]中与（0）相对应的xij=1，其余的决策 变量等于0。这时，[xij]便是最优解。将最 优解代入目标函数 y 的表达式，即得最优
值。 3.9 8.0 2.2 (0)
ci j
2.3 (40.3)
i1 j1
37.3 43.4 33.3 29.2
bij
333732...089
33.1 28.5 26.4
42.2 34.7
38.9 30.4
2289..56
4
xi j 1
i1
4
xi j 1
j1
x
i
j
0,
1
例11称为最小化指派问题。
j 1, 2, 3, 4 i 1, 2, 3, 4 i , j 1, 2, 3, 4
0
0.2 0.2
0 0 0 1
xi j
0 10
0 0 1
1 0 0
0
0 0
已得到4个（0），则令[Cij]中与（0）相对应的xij=1， 其余的决策变量等于0。这时，[xij]便是最优解。将最优解代 入目标函数 y 的表达式，即得最优值 ymin = 126.2 (分) 。
( 0 )’ 0 5 1 6 3 8 4 9 6 11 7 12 9 14 10 15
( 1 )’ 是(√ )
小于4 上面的目√ 标值8，所以 此解5 非最优。√
6
( 5)
√
8
6
9
7
10
8
11
否(× ) × × ×
×
× ×
× × × × × × ×

运筹学_指派问题

运筹学_指派问题

（xij）是n×n矩阵,对应于效率矩阵(cij).
工作
x11 人 x i1 xn1
x1n xij xin xnj xnn x1 j
可行解矩阵
x
i 1
n
ij
1,
j 1, 2, , n ②
指派问题的最优解有这样性质，若从效率矩 阵(cij)的一行(列)各元素中分别减去该行(列)的 最小元素，得到新矩阵(bij)，那么以(bij)为效率 矩阵求得的最优解和用原效率矩阵求得的最优解 相同 。即 定理2 设给定了以C = (cij)为效率矩阵指派问题G， 现将C的元素cij 改变为 bij cij i j , i 与 j 为常数 则以B= ( bij )为效率矩阵指派问题G’与G有相同的最 优解。
第四节 指 派 问 题
assignment problem
在生活中经常遇到这样的问题，某 单位需完成n项任务，恰好有n个人可承 担这些任务。由于每人的专长不同，各 人完成任务不同(或所费时间)，效率也 不同。于是产生应指派哪个人去完成哪 项任务，使完成n项任务的总效率最高 (或所需总时间最小)。这类问题称为指 派问题或分派问题。
行列都有 零元素
7 6 3 0*
0 * 9 (b ) ij 2 0
0 0 最优解为 ( xij ) 1 0
0 1 0 0
0 0 0 1
1 0 0 0
定理3 若矩阵C可分成”0”与非”0”两部分,则覆 盖”0”元素的最少直线等于位于不同行不同列的”0” 元素的最大个数.
如
5 0* 2 0 2 2 3 0* 0 0 0* 10 5 7 2 -2 9 8 0 0* 4 0 6 3 6 5 -2 5 0* 2 0 2 2 3 0* 0 0 2 8 3 5 0 9 8 0 0* 4 2 4 1 4 3

运筹学整数规划指派问题

运筹学整数规划指派问题

4 8 7 15 12 -4 7 9 17 14 7 -7
0 4 3 11 8 0 2 10 7 3
C
6
9 12
6
10
-6
0
3
6
2
1
6 7 14 8 10 -6
0 1 8 0 4
6
9
6
10
8
-6
0
3
6
4
0
-1 -3
✓
0 0
3 1
0 7
11 7
8 3
✓
C1
0
2
3
2
1
✓
0 0 5 0 4
这样安排能使总的建造费用最少，总的建造费用为 7+9+6+6+6=34（万元）。
三 非标准形式的指派问题
处理方法：化成标准形式，再按匈牙利方法求解。 ⒈ 目标函数最大化指派问题
例 有4名工人A1,A2,A3,A4分别操作4台机床B1,B2,B3,B4。每 人操作每台机床的单位产量见下表。求产值最大的指派方案。
在遇到所有行和列中，零元素都不止一个时，可任选其中 一个加圈，然后划去同行、同列其他未被标记的零元素。
例
5 0 2 0
C
2 0 0
3 0 8
0 6 0
0
7 0
步骤3： 若矩阵所有零元素都被标记的，但圈零的个数m < n ， 作最少直线覆盖当前零元素。
已知5家建筑公司承建5家商店系数矩阵
⒈变换系数矩阵
0 0 0 0 1
X
*
0
0
0
1
0
0 1 0 0 0
0
0
1
0
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
(i 1, ,4; j 1, ,4)
则该指派问题的数学模型为：
min z 2x11 15x12 13x13 4x14 L 11x43 9x44
4
xij
1
(i 1,L
, 4)
∑xij=1 (i=1,2,3,4) 表示第i人只能完成一项任务
j1
s.t.
4
xij
1
( j 1,L
, 4)
i1
xij=1 (j=1,2,3,4) 表示第0或1
(i，j 1,L
, 4)
满足约束条件的解称为可行解， 可写成矩阵形式，叫作解矩阵。
如本例的一个可行解矩阵（但不一定是最优解）
0 1 0 0
xij
0 1
0 0
1 0
0 0
0 0 0 1
指派问题的解矩阵应具有如下特点：
在实际中经常会遇到这样的问题，
有n 项不同的任务， 需要n 个人分别完成其中的一项，
但由于任务的性质和各人的专长不同， 因此各人去完成不同的任务的效率 （或花费的时间或费用）也就不同。 于是产生了一个问题: 应指派哪个人去完成哪项任务，
使完成 n 项任务的总效率最高（或所需时间最少），
这类问题称为指派问题或分派问题。
二 匈牙利算法
思路 算法原理 算法步骤
（一） 思路
匈牙利法基于这样一个明显的事实： 如果在m阶效率矩阵中，所有元素cij≥0， 而其中有m个位于不同行不同列的一组0元素， 则在解矩阵中，只要令对应于这些0元素位置的 xij＝1，其余的xij＝0，就得到最优解。 此时的最优解为０
•如效率矩阵为 •恰有4个不同行 不同列的0系数
2. 指派问题数学模型—一般形式
设[cij]表示指派问题的效率矩阵，令
1, 分配第i个人去完成第j项任务 xij 0, 不分配第i个人去完成第j项任务
(i 1, ,n; j 1, ,m)
则指派问题的数学模型一般形式为： xij 为第 i 个人指派去做
mm
min (或 max)z
cijxij
（1）解矩阵(xij)中各行各列的元素之和都是1； （2）可行解（最优解）中恰含有４个非零元，即4个1；
（3）可行解（最优解）矩阵中的1恰取于不同行不同列。
人 工作
甲
乙
丙
丁 人数
译成英文 2 10 9 7 1
译成日文 15 4 14 8 1
译成德文 13 14 16 11 1
译成俄文 4 15 13 9 1
甲 乙 丙 丁
E
J
G
R
2
15 13
4
10
4
14
15
9
14
16
13
7
8
11
9
❖ 这是一个标准型的指派问题
❖ 类似有：有n项加工任务，怎样指派到n台机床上分别完成；
有n条航线，怎样指定n艘船分别去航行….. 等。
❖ 对应每个指派问题，需有类似上表那样的数表，
表中数据称为效率矩阵或系数矩阵，
❖ 其元素cij>0(i,j=1,2,…n)， ❖ 表示指派第i人去完成第j 项任务时的效率（或时间、成本等）
一、指派问题的数学模型
（一）举例
例7： 有一份中文说明书， 要分别译成英、日、德、俄四种文字， 分别记作E 、 J 、 G 、 R ,交与甲、乙、丙、丁 四个人去完成. 因个人专长不同， 他们完成翻译不同语种的说明书所需的时间(h)如表所示. 应如何指派，使四个人分别完成这四项任务总时间为最小？
任务 人员
（二）算法的基本原理 匈牙利数学家狄·康尼格(D·Konig)证明的两个定理
c11 c12 … c1n
效率
C=(cij)n×n=
c21 c22 … c2n ……………… cn1 cn1 … cnn
矩阵
或
系数 矩阵
C=(cij )４×４=
2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9
求解题时通常需引入0-1变量：
1, 分配第i个人去完成第j项任务 xij 0, 不分配第i个人去完成第j项任务
如果一个指派模型满足以下三个条件： 1)目标要求为min 2)效率矩阵(cij)为m阶方阵 3)效率矩阵中所有元素cij≥0,且为常数
则称上面的数学模型为指派问题的标准形.
4. 指派模型的标准形的特点: 含有m×m个决策变量,均为0-1变量 m+m＝2m个约束方程
给定一个指派问题时，必须给出效率矩阵（系数矩阵） C=(cij)mxm,且cij0，因此必有最优解 。
0 14 9 3
9
20
0
23
23 0 3 8
0
12 14
0
令x11=1，x23=1，x32=1，x44=1，即可得最优解，
其解矩阵为
min Z=Z＊＝0
1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1
问题是如何找到位于不同行、不同列的m个0元素？
匈牙利算法基本思想： 对同一工作i来说， 所有人的效率都提高或降低同一常数， 不会影响最优分配； 同样，对同一人j来说, 做所有工作的效率都提高或降低同一常数， 也不会影响最优分配。
i1 j1
第 j 项任务； cij 为第 i 个人为完成第
m
xij 1 (i 1, ,n) j1
j 项任务时的工时消
耗，或称效率；
s.t.
n
xij 1
(j 1, ,m)
{cij} nm 为效率矩阵
i1
xij 0或1 (i 1, ,n；j 1, ,m)
3. 指派问题数学模型—标准形式
任务
1
1
1
1
可以看到指派问题既是0-1 规划问题，也是运输问题， 所以也可用整数规划，0-1 规划， 或运输问题的解法去求解。
（二）指派问题的数学模型 1. 指派问题的一般提法：
❖ 设m个人被指派去做m件工作， 规定每个人只做一件工作， 每件工作只有一个人去做。
❖ 已知第i个人去做第j 件工作的的效率（ 时间或费用） 为cij (i=1.2…m;j=1.2…m) ，并假设cij ≥0。 问应如何指派才能使总效率最高或总时间﹑ 总费用最低 ？
mm
MinZ
cijxij 0
i1 j1
指派问题有2m个约束条件，
但可行解（即解矩阵）中有且只有m个是非零值，
即m个值取为１，其余取为０, 是自然高度退化的。
指派问题是0-1 规划的特例， 也是运输问题的特例，所以可用整数规划，0-1 规划或运输问题的解法去求解， 但这就如同用单纯形法去求解运输问题一样， 是不合算的。 根据指派问题的特点可以有更简便的解法， 就是匈牙利算法， 其重要依据是： 系数矩阵中独立 0 元素的最多个数等于能覆盖 所有 0 元素的最少直线数。