指派问题的算法分析与实现

《指派问题的算法分析与实现》由会员分享，可在线阅读，更多相关《指派问题的算法分析与实现（11页珍藏版）》请在金锄头文库上搜索。

1、1 运运 筹筹 学学 课课 程程 设设 计计题 目：指派问题的算法分析与实现院 系： 理学院 专 业： 数学与应用数学 学 号： 1101020127 姓 名： 梁 州 日期： 2014 年 1 月 10 日2摘 要在企业、公司的运营与管理中，管理者总是希望把人员最佳分派以发挥其最大工作效率，从而降低成本、提高效益。然而，如果没有科学的方法是很难实现优化管理的，由此我们引入了指派问题。指派问题多是求项目的工时最少，而很多情况下人们并不关心项目总工时的多少，而只关心项目能否在最短的时间内完成，即历时最少的指派问题。这类问题研究的是 n 个人执行 n 项任务，执行每项任务的人数以及总的指派人项数均

2、有限制，要求最优指派。在运筹学中求解整数规划的指派问题通常是通过匈牙利算法来求解，但指派问题也可以归结为一个 0-1 整数规划问题，本文先对指派问题进行陈述，引出对实际问题的求解。在指派问题的背景、描述中充分理解该问题，先运用匈牙利算法实现指派问题，然后再建立一个 0-1 整数规划模型，并运用 matlab 编译程序对问题进行编译，运用软件解决模型问题，最终实现指派问题在实际问题中的运用。通过运用匈牙利算法和 0-1 整数规划同时对指派问题求解，我们发现用 0-1 整数规划的方法来求解可以更简单，也更方便程序的阅读和理解。与此同时，我们还对 0-1 整数规划问题由整数数据深入研究到小数数据。最

3、后通过实例来说明运用 matlab 编译程序来解决整数规划问题的简便和有效性。问题陈述指派问题又称分配问题，其用途非常广泛，比如某公司指派 n 个人去做 n件事，各人做不同的事，如何安排人员使得总费用最少？若考虑每个职工对工作效率（如熟练程度等） ，怎样安排会使总销量达到最大？这些都是一个企业经营管理者必须考虑的问题，所以该问题有重要的应用价值。假设有 n 件工作分派给 n 个人来做，每项工作只能由一人来做，每个人只能做一项工作。若给出各人对各项工作所具有的工作效率。问应该如何安排人选，及发挥个人特长又能使总的效率最大。为此用 0-1 整数规划来实现指派问题即如何安排人选。指派问题的背景3在现

4、实生活中，有各种性质的指派问题（Assignment Problem） 。例如，在生产管理中，总希望把人员进行最佳分配，以发挥最大的工作效率；某部门有 n 项任务要完成，而该部门正好有 n 个人可以分别去完成其中任何一项，但由于任务性质和个人的专长不同，因此各人完成各项不同任务的效益（所费时间或所花费用）也有差别，如果分配每个人完成一项任务且仅为一项任务，则把每项任务分配给哪个人去完成，使完成所有 n 项任务的总效益为最高（总时间、总费用为最小或创造的价值最大）？这是典型的分配问题或指派问题。又如有 n 项加工任务，怎样指定 n 台机器分别去完成，以使总的加工时间最少或总收入最大；有 n 条航

5、线，怎样指定 n 艘船分别航行，使总收入最大，等等，都属于指派问题。指派问题的一般形式指派问题的标准形式（以人和事为例）如下。有 n 个人和 n 项任务，已知第 i 个人做第 j 件事的费用为 ，要求确定人和事之间的一一对应的指派方案，ijc使完成这 n 项任务的费用最少。一般把目标函数的系数写为矩阵形式，称矩阵 nnnnij cccC.)(212211为系数矩阵（Coefficient Matrix） ，也称为效益矩阵或价值矩阵。矩阵的元素 （i,j=1,2,n ）表示分配第 i 个人去完成第 j 项任务时的效益。一般地，ijc以 表示给定的资源分配用于给定活动时的有关效益（时间，费用，价值

6、等） ，ijx且 njxij ,.21i,ji,10 ，项 活 动单 位 资 源 用 于 第分 配 第 项 活 动单 位 资 源 用 于 第不 分 配 第411minax (1). ,2.2,.(3)01,4nijiijnijijzcxst nxji（ ） 或在模型中，约束条件式（2）表示每个人只能做一件事，约束条件式（3）表示每件事只能由一个人去做。对于问题的每个可行解，可用解矩阵来表示： nnnnij xxxx.)(X212211时，我们将构造一个新的矩阵 ，使 ，其中 是一个足够大的常ijcijijMc数。一般取 中最大的元素作为 ，求解 当然，作为可行解，矩阵的每列元ijc素中都有且只

7、有一个 1，以满足约束条件式（3） 。每行元素中也有且只有一个1，以满足约束条件（2） 。指派问题 n!个可行解。求解 ，所得的解 就是1maxnijizcx1mnijijzcxijx原问题的解。事实上，由 111Mnnnij ijiijnijijijijicxcxcx可的此结论。匈牙利算法的实现步骤第一步：找出矩阵每行的最小元素，分别从每行中减去这个最小元素；第二步：再找去矩阵每列的最小元素，分别从各列减去这个最小元素；第三步：经过这两步变换后，矩阵的每行每列至少都有了一个零元素，接着根5据以下准则进行试指派，找出覆盖上面矩阵中所有零元素至少需要多少条直线；（1）从第一行开始，若该行只有一个

8、零元素打上（）号。对打（）号零元素所在列划一条直线。若该行没有零元素或有两个以上零元素（已划去的不计在内） ，则转下一行，一直到最后一行为止；（2）从第一列开始，若该列只有一个零元素就对这个零元素打上（）号（同样不考虑已划去的零元素） ，对打（）号零元素所在行划一条直线。若该列没有零元素或 还有两个以上零元素，则转下一列，并进行到最后一列；（3）重复（1） 、 （2）两个步骤，可能出现三种情况： 矩阵每行都有一个打（）号零元素，很显然，按照上述步骤得到的打（）的零元素都位于不同行不同列，因此就找到了问题的答案； 有多于两行或两列存在两个以上零元素，即出现了零元素的闭回路，这个时候可顺着闭回路的

9、走向，对每个间隔的零元素打上（）号，然后对所有打（）号零元素或所有列或所在行划一条直线。 矩阵中所有零元素或打上（）号，或被划去，但打（）号零元素个数小于m。第四步：为了设法使每行都有一个打（）的零元素，就要继续对矩阵进行变换；（1）从矩阵未被直线覆盖的元素找出最小元素 k；（2）对矩阵的每行，当该行有直线覆盖时，令 =0，无直线覆盖的，令 =k；iuiu（3）对矩阵的每列，当该列有直线覆盖时，令 =-k，无直线覆盖的，令jv=0；jv（4）得列一个变换后的矩阵，其中每个元素 = - - 。ijbijaiujv第五步：回到第三步，反复进行，一直到矩阵中每一行都有一个打（）的零元素为止，即找到最

10、优分配方案为止。4.1.3 匈牙利算法实现指派问题为了便于对模型进行求解与分析，假设有 4 件事 4 个人去做，各变量对应的数据假设如表 1。每个人完成各项任务需要的时间6任务人A B C D甲 25 29 31 42乙 39 38 26 20丙 34 27 28 40丁 24 42 36 23用匈牙利算法求解过程如下： 247053642873915 0139768740 0139)(7)(80 401293)0(7)(5874-1 -1 -1 -4 -4 108517)(40 )0(7148)(23-1 -1所以最优解为 x11，x23，x32，x44，即甲负责任务 A，乙负责任务 C，丙

11、负责任务 B，丁负责任务 D，可以使总花费时间最少。代入求出目标函数值Z=25+26+27+23=101。4.2 0-1 整数规划0-1 规 划 （ 0-1 Programming） 一 种 特 殊 形 式 的 整 数 规 划 。 这 种 规 划 的决 策 变 量 仅 取 值 0 或 1， 故 称 为 0-1 变 量 或 二 进 制 变 量 ， 因 为 一 个 非 负 整 数都 可 以 用 二 进 制 记 数 法 用 若 干 个 0-1 变 量 表 示 。 0-1 变 量 可 以 数 量 化 地 描述 诸 如 开 与 关 、 取 与 弃 、 有 与 无 等 现 象 所 反 映 的 离 散 变

12、量 间 的 逻 辑 关 系 、 顺序 关 系 以 及 互 斥 的 约 束 条 件 ， 因 此 0-1 规 划 非 常 适 合 描 述 和 解 决 如 线 路 设 计 、 工 厂 选 址 、 生 产 计 划 安 排 、 旅 行 购 物 、 背 包 问 题 、 人 员 安 排 、 代 码 选 取 、可 靠 性 等 人 们 所 关 心 的 多 种 问 题 。 实 际 上 ， 凡 是 有 界 变 量 的 整 数 规 划 都 可 以转 化 为 0-1 规 划 来 处 理 。 当 然 也 包 括 运 筹 学 中 的 指 派 问 题 。74.2.1 模型假设为了便于对模型进行求解与分析，假设有 4 件事 4

13、 个人去做，各变量对应的数据假设如表 1。表 1 每个人完成各项任务需要的时间任务人A B C D甲 25 29 31 42乙 39 38 26 20丙 34 27 28 40丁 24 42 36 23表 2 变量假设i 第 i 个人j 第 j 项任务ijx第 i 个人分配第 j 项任务=1ij 第 i 个人被分配去做第 j 项任务=0ijx第 i 个人不被分配到第 j 项任务根据前面的假设，因此，每个人只完成一项任务的约束条件为： 1434213214312xx每项任务必有一个人负责的约束条件为：1432413241321xx由此，建立的数学模型为：12134223412434min5986

14、07zxx8s.t. 1434213214312xx143241321xx或 1，i，j=1，2，3，40ij用 matlab 求解根据上面建立的模型，代入相应的数据，利用 matlab 软件编程求解，具体程序如下：function y,fval=minzp(C) %y为最佳匹配矩阵，fval为目标函数值，C为目标函数系数矩阵C=C;f=C(:);m,n=size(C);Aeq=zeros(2*n,n*n); %生成2*n行n*n列的等式约束 0系数矩阵for i=1:nAeq(1:n,1+(i-1)*n:i*n)=eye(n,n); %eye表示生成n阶单位阵endfor i=1:nAeq(

15、n+i,1+(i-1)*n:i*n)=ones(1,n); %生成1行n列元素为1的向量endbeq=ones(2*n,1); %生成2*n行1列元素为1的等式约束右端项lb=zeros(n*n,1); %生成n*n行1列元素为0的不等式约束左端项ub=ones(n*n,1); %生成n*n行1列元素为1的不等式约束右端项x=linprog(f,Aeq,beq,lb,ub); %求目标函数达到极小值的x值y=reshape(x,n,n); %将上式求出的x值组成的向量变成 n阶矩阵y=y;y=round(y); %对y中的元素取整，生成匹配矩阵sol=zeros(n,n);for i=1:nfor j=1:nif y(i,j)=1sol(i,j)=C(j,i);endendendfval=sum(sol(:); %求出极小值的目标函数值9其中， C=25 29 31 4239 38 26 2034 27