数学建模指派问题论文.docx
《数学建模指派问题论文.docx》由会员分享，可在线阅读，更多相关《数学建模指派问题论文.docx（26页珍藏版）》请在冰点文库上搜索。
数学建模指派问题论文
一问题重述
指派问题亦称平衡指派问题仅研究人数与事数相等、一人一事及一事一人的情形。
现有的不平衡指派问题将研究范围扩大到人数与事数可以不等、一人一事或一人多事及一事一人的情形。
日常活动中也不乏人数与事数可以不等、一人多事及一事多人的情形，这类事务呈现了广义指派问题的实际背景。
平衡指派问题是特殊形式的平衡运输问题，可运用匈亚利法、削高排除法和缩阵分析法等特殊方法求解。
另一方面，正是平衡指派问题的这种特殊性，使得不平衡指派问题不能按常规技术转化为平衡指派问题。
因此，各种不平衡指派问题需要确立相应的有效解法１问题的提出及其数学模型广义指派问题并非奇特和抽象的构想，相反，该问题可以从司空见惯的日常事务中引出。
现在我们就运用匈牙利法，去实现n个人，n件工作的指派问题。
二模型假设
1假设一共有n个人，n件工作，即人数与工作数相等。
2假设每个人的都能从事某项工作，但是付出的代价不同。
3假设求解代价最小的解。
4甲乙丙丁四个人，ABCD四项工作，要求每人只能做一项工作，每项工作只由一人完成，问如何指派总时间最短？
三匈牙利法陈述
第一步：
找出矩阵每行的最小元素，分别从每行中减去这个最小元素；
第二步：
再找去矩阵每列的最小元素，分别从各列减去这个最小元素；
第三步：
经过这两步变换后，矩阵的每行每列至少都有了一个零元素，接着根据以下准则进行试指派，找出覆盖上面矩阵中所有零元素至少需要多少条直线；
（1）从第一行开始，若该行只有一个零元素打上（）号。
对打（）号零元素所在列划一条直线。
若该行没有零元素或有两个以上零元素（已划去的不计在内），则转下一行，一直到最后一行为止；
（2）从第一列开始，若该列只有一个零元素就对这个零元素打上（）号（同样不考虑已划去的零元素），对打（）号零元素所在行划一条直线。
若该列没有零元素或还有两个以上零元素，则转下一列，并进行到最后一列；
（3）重复
（1）、
（2）两个步骤，可能出现三种情况：
1矩阵每行都有一个打（）号零元素，很显然，按照上述步骤得到的打（）的零元素都位于不同行不同列，因此就找到了问题的答案；
2有多于两行或两列存在两个以上零元素，即出现了零元素的闭回路，这个时候可顺着闭回路的走向，对每个间隔的零元素打上（）号，然后对所有打（）号零元素或所有列或所在行划一条直线。
3矩阵中所有零元素或打上（）号，或被划去，但打（）号零元素个数小于m。
第四步：
为了设法使每行都有一个打（）的零元素，就要继续对矩阵进行变换；
（1）从矩阵未被直线覆盖的元素找出最小元素k；
（2）对矩阵的每行，当该行有直线覆盖时，令
=0，无直线覆盖的，令
=k；
（3）对矩阵的每列，当该列有直线覆盖时，令
=-k，无直线覆盖的，令
=0；
（4）得列一个变换后的矩阵，其中每个元素
=
-
-
。
第五步：
回到第三步，反复进行，一直到矩阵中每一行都有一个打（）的零元素为止，即找到最优分配方案为止。
四问题分析
指派问题的标准形式（以人和事为例）如下。
有n个人和n项任务，已知第i个人做第j件事的费用为
，要求确定人和事之间的一一对应的指派方案，使完成这n项任务的费用最少。
一般把目标函数的系数写为矩阵形式，称矩阵
为系数矩阵（CoefficientMatrix），也称为效益矩阵或价值矩阵。
矩阵的元素
（i,j=1,2,…n）表示分配第i个人去完成第j项任务时的效益。
一般地，以
表示给定的资源分配用于给定活动时的有关效益（时间，费用，价值等），且
然后我们求解最小（最大（这里不再讨论））代价和模型，
当然，作为可行解，矩阵的每列元素中都有且只有一个1，以满足约束条件式（3）。
每行元素中也有且只有一个1，以满足约束条件
（2）。
指派问题n!
个可行解。
如果要求解最大值
时，我们将构造一个新的矩阵
，使
，其中
是一个足够大的常数。
一般取
中最大的元素作为
，求解
，所得的解
就是原问题的解。
事实上，由
可的此结论。
五问题实现
1问题重述
已知问题甲乙丙丁四个人，ABCD四项工作，要求每人只能做一项工作，每项工作只由一人完成，问如何指派总时间最短？
每个人的对每项工作的代价如下：
2问题求解
开始求解
2.1由匈牙利法构造目标函数
引入0-1变量xij，
xij=1：
第i人做第j项工作
xij=0：
第i人不做第j项工作
约束条件：
（i=1,2,…,92j=1,2,…,20）
2.2模型建立
即一项任务只由一个人完成
一人只能完成一项任务
求出目标函数
3模型解析
根据指派问题的最优性定理，求最优解的问题可以转换为求效益矩阵的
大1元素组的问题。
匈牙利法的一般计算步骤为：
步骤1：
对效益矩阵进行初等变换，使每行每列都出现0元素。
1. 从效益矩阵A中每一行减去该行的最小元素；
2. 再在所得矩阵中每一列减去该列的最小元素，得矩阵D；
步骤2：
将矩阵D中0元素置为1元素，非0元素置为0元素，得矩阵E。
步骤3：
确定独立1元素组。
1. 在矩阵E中含有1元素的各行中选择1元素最少的行，比较该行中各1元素所在的列中1元素的个数，选择1元素的个数最少的那一列中的1元素；
2. 将所选的1元素所在的行和列的元素置为0；
3. 重复第2步和第3步，直到没有1元素为止，即得到一个独立1元素组。
步骤4：
判断是否为最大独立1元素组。
1. 如果所得独立1元素组为原效益矩阵的最大独立1元素组（即1元素的个数等于矩阵的阶数），则已得到最优解，停止计算；
2. 如果所得独立1元素组还不是原效益矩阵的最大独立1元素组，那么继续寻找可扩路的方法对其进行扩张，进行下一步；
步骤5：
利用寻找可扩路方法确定最大独立1元素组。
1. 做最少的直线覆盖矩阵D的所有0元素；
2. 在没有被直线覆盖的部分找出最小元素，在没有被直线覆盖的各行减去此最小元素，在没有被直线覆盖的各列上加上此最小元素，得到一个新的矩阵，返回第二步。
4程序实现
这里我们运用c++语言进行编程进行求解
/************************************************************************/
/*zhipai2.cpp
Author:
路遥
Date:
2012-12-1
Description:
需要在同样的目录下建立一个input.txt的文件夹在里面写入每个人从事不同的工作代价，首行要写入几阶方程，然后是每个人的不同工作代价，用空格隔开。
每人一行，见下面数字形式。
用匈牙利法，实现n个人，n件工作的指派问题。
Input:
input.txt格式为代价矩阵维度n，和矩阵内容，例如：
4
3584
6854
2585
9252
Output:
控制台输出指派矩阵，例如
0001
0010
1000
0100
*/
/************************************************************************/
#include
#include
usingnamespacestd;
#defineMAX_N100
intnn;//输入矩阵的维度nn
voidprintMatrix（inta[MAX_N][MAX_N]）
{
inti,j;
for（i=0;i{
for（j=0;jcout<cout<}
}
intmain（）
{
intc[MAX_N][MAX_N],b[MAX_N][MAX_N];
intquan[MAX_N][MAX_N],cha[MAX_N][MAX_N];
introwZero[MAX_N],colZero[MAX_N];
introwCheck[MAX_N],colCheck[MAX_N];
inti,j,k;
ifstreaminput（"input.txt"）;
if（!
input）
{
cout<<"Openinputfilefailed."<system（"pause"）;
exit
（1）;
}
//读取输入文件
input>>nn;
for（i=0;i{
for（j=0;j{
input>>c[i][j];
b[i][j]=c[i][j];
}
}
input.close（）;
//每行减去该行最小
for（i=0;i{
intmin=b[i][0];
for（j=1;j{
if（b[i][j]min=b[i][j];
}
for（j=0;jb[i][j]-=min;
}
//每列减去该列最小
for（j=0;j{
intmin=b[0][j];
for（i=1;i{
if（b[i][j]min=b[i][j];
}
for（i=0;ib[i][j]-=min;
}
//开始尝试进行试指派
assign:
//初始化标记数组和计数数组
for（i=0;i{
rowZero[i]=colZero[i]=0;
rowCheck[i]=colCheck[i]=0;
for（j=0;jquan[i][j]=cha[i][j]=0;
}
//计算每行每列0元素个数
for（i=0;ifor（j=0;jif（b[i][j]==0）
{
rowZero[i]++;
colZero[j]++;
}
boolflag;
//直到尽可能多的0元素都被圈出和划掉为止
do
{
flag=false;
//寻找只有一个0元素的行，加圈划叉
for（i=0;i{
if（rowZero[i]==1）//该行只有一个0元素
{
//cout<<"rowZerofound:
"<flag=true;
//找到0元素,加圈划叉
for（j=0;j{
if（b[i][j]==0&&quan[i][j]==0&&cha[i][j]==0）
{
quan[i][j]=1;
rowZero[i]--;
colZero[j]--;
for（k=0;k{
if（b[k][j]==0&&quan[k][j]==0&&cha[k][j]==0）
{
cha[k][j]=1;
rowZero[k]--;
colZero[j]--;
}
}
break;
}
}
//break;
}
}
//寻找只有一个0元素的列，加圈划叉
for（j=0;j{
if（colZero[j]==1）//该列只有一个0元素
{
flag=true;
//找到0元素,加圈划叉
for（i=0;i{
if（b[i][j]==0&&quan[i][j]==0&&cha[i][j]==0）
{
quan[i][j]=1;
rowZero[i]--;
colZero[j]--;
for（k=0;k{
if（b[i][k]==0&&quan[i][k]==0&&cha[i][k]==0）
{
cha[i][k]=1;
rowZero[i]--;
colZero[k]--;
}
}
break;
}
}
//break;
}
}
}while（flag）;
//判断是否还有0元素未被标记
intzeroNotMarked=0;
for（i=0;izeroNotMarked+=rowZero[i];
while（zeroNotMarked!
=0）
{
/*
从剩有0元素最少的行（列）开始，比较这行各0元素所在列中0元素的数目，
选择0元素少的那列的这个0元素加圈（表示选择性多的要“礼让”选择性少的）。
然后划掉同行同列的其它0元素。
可反复进行，直到所有0元素都已圈出和划掉为止。
*/
intleastZeroRow=0;
while（rowZero[leastZeroRow]==0）
leastZeroRow++;
for（i=leastZeroRow+1;i{
if（rowZero[i]!
=0&&rowZero[i]leastZeroRow=i;
}
i=leastZeroRow;//得到0元素最少的行标
intleastZeroCol=0;
while（colZero[leastZeroCol]==0）
leastZeroCol++;
for（j=0;j{
if（b[i][j]==0&&quan[i][j]==0&&cha[i][j]==0&&colZero[j]leastZeroCol=j;
}
j=leastZeroCol;//得到0元素最少的列标
//圈出b[i][j],划掉i行和j列其余0元素
quan[i][j]=1;
rowZero[i]--;
colZero[j]--;
zeroNotMarked--;
for（k=0;k{
if（b[i][k]==0&&quan[i][k]==0&&cha[i][k]==0）
{
cha[i][k]=1;
rowZero[i]--;
colZero[k]--;
zeroNotMarked--;
}
}
for（k=0;k{
if（b[k][j]==0&&quan[k][j]==0&&cha[k][j]==0）
{
cha[k][j]=1;
rowZero[k]--;
colZero[j]--;
zeroNotMarked--;
}
}
}
//printMatrix（quan）;
//若quan元素的数目countQuan等于矩阵的阶数nn,则得出最优解，否则画线
intcountQuan=0;
for（i=0;ifor（j=0;jcountQuan+=quan[i][j];
if（countQuan{
//对没有quan的行打勾
for（i=0;i{
inttemp=0;
for（k=0;ktemp+=quan[i][k];
if（temp==0）
{
rowCheck[i]=1;
}
}
/*
重复执行
（1）
（2），直到打不出新的勾为止：
（1）对已打勾的行中含cha的元素的列打勾
（2）对已打勾的列中含quan的元素的行打勾
*/
intnewCheck=0;
intcheck;
do
{
check=newCheck;
//
（1）
for（i=0;i{
if（rowCheck[i]==1）
{
for（j=0;j{
if（cha[i][j]==1&&colCheck[j]==0）
{
colCheck[j]=1;
newCheck++;
}
}
}
}
//
（2）
for（j=0;j{
if（colCheck[j]==1）
{
for（i=0;i{
if（quan[i][j]==1&&rowCheck[i]==0）
{
rowCheck[i]=1;
newCheck++;
}
}
}
}
}while（check!
=newCheck）;
//（5）对rowCheck[]==0的行画横线，colCheck[]==1的列画纵线
//这就得到覆盖所有0元素的最少直线数numLines
intnumLines=0;
for（i=0;i{
if（rowCheck[i]==0）
numLines++;
}
for（j=0;j{
if（colCheck[j]==1）
numLines++;
}
if（numLines!
=countQuan）
{
cout<<"直线个数不等于画圈0元素个数，试指派有误"<}
//若numLines=countQuanif（numLines==countQuan&&numLines{
/*
变换矩阵b[i][j]以增加0元素：
设没有被直线覆盖（rowCheck[i]==1&&colCheck[j]==0）
的有所有元素中的最小元素为min2，
然后打勾各行都减去min2；打勾各列都加上min2，
将得到的矩阵重新进行试指派
*/
i=0;
while（rowCheck[i]==0）i++;
j=0;
while（colCheck[j]==1）j++;
intmin2=b[i][j];
for（i=0;ifor（j=0;j{
if（b[i][j]min2=b[i][j];
}
for（i=0;i{
if（rowCheck[i]==1）
{
for（j=0;j{
b[i][j]-=min2;
}
}
}
for（j=0;j{
if（colCheck[j]==1）
{
for（i=0;i{
b[i][j]+=min2;
}
}
}
//将变换后的矩阵b[i][j]重新试指派
gotoassign;
}
}
//此时countQuan==nn,输出指派结果
cout<<"指派结果如下：
"<printMatrix（quan）;
system（"pause"）;
return0;
}
六结果显示及min求解
Min（z）=4+5+2+2=13
即求出最小代价。
完成假设要求
七模型深入
将约束条件由整数数据变为小数数据且目标函数由最小值化为最大值问题的求解。
假设有4件工作分派给4个人来做，每项工作只能由一人来做，每个人只能做一项工作。
下表为各人对各项工作所具有的工作效率。
问应该如何安排人选，及发挥个人特长又能使总的效率最大。
每个人完成各项任务需要的时间
工人
人
A
B
C
D
甲
0.6
0.2
0.3
0.1
乙
0.7
0.4
0.3
0.2
丙
0.8
1.0
0.7
0.3
丁
0.7
0.7
0.5
0.4
1模型建立
数学模型为
s.t.
或1，i，j=1，2，3，4
2进行求解
本次我们使用matlab求解具体程序如下：
function[y,fval]=maxzp（M,C）%M为C中元素的最大值
[m,n]=size（C）;
C=M+zeros（n）-C;%将求极小值的目标函数系数矩阵转换成求极大值的系
数矩阵
M=1.0;
C=C';
f=C（:
）;
Aeq=zeros（2*n,n*n）;
fori=1:
n
Aeq（1:
n,1+（i-1）*n:
i*n）=eye（n,n）;
end
fori=1:
n
Aeq（n+i,1+（i-1）*n:
i*n）=ones（1,n）;
end
beq=ones（2*n,1）;
lb=zeros（n*n,1）;
ub=ones（n*n,1）;
x=linprog（f,[],[],Aeq,beq,lb,ub）;
y=reshape（x,n,n）;
y=y';
y=round（y）;
sol=zeros（n,n）;
fori=1:
n
forj=1:
n
ify（i,j）==1
sol（i,j）=C（j,i）;
end
end
end
fval=sum（sol
升级会员 