数学建模指派问题论文设计Word文档下载推荐.docx
《数学建模指派问题论文设计Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数学建模指派问题论文设计Word文档下载推荐.docx（26页珍藏版）》请在冰点文库上搜索。
回到第三步，反复进行，一直到矩阵中每一行都有一个打（）的零元素为止，即找到最优分配方案为止。
四问题分析
指派问题的标准形式（以人和事为例）如下。
有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元素组。
在矩阵E中含有1元素的各行中选择1元素最少的行，比较该行中各1元素所在的列中1元素的个数，选择1元素的个数最少的那一列中的1元素；
将所选的1元素所在的行和列的元素置为0；
3.
重复第2步和第3步，直到没有1元素为止，即得到一个独立1元素组。
步骤4：
判断是否为最大独立1元素组。
如果所得独立1元素组为原效益矩阵的最大独立1元素组（即1元素的个数等于矩阵的阶数），则已得到最优解，停止计算；
如果所得独立1元素组还不是原效益矩阵的最大独立1元素组，那么继续寻找可扩路的方法对其进行扩张，进行下一步；
步骤5：
利用寻找可扩路方法确定最大独立1元素组。
做最少的直线覆盖矩阵D的所有0元素；
在没有被直线覆盖的部分找出最小元素，在没有被直线覆盖的各行减去此最小元素，在没有被直线覆盖的各列上加上此最小元素，得到一个新的矩阵，返回第二步。
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<
iostream>
fstream>
usingnamespacestd;
#defineMAX_N100
intnn;
//输入矩阵的维度nn
voidprintMatrix（inta[MAX_N][MAX_N]）
{
inti,j;
for（i=0;
i<
nn;
i++）
{
for（j=0;
j<
j++）
cout<
<
a[i][j]<
"
"
;
cout<
endl;
}
}
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）
Openinputfilefailed."
system（"
pause"
exit
（1）;
//读取输入文件
input>
>
{
input>
c[i][j];
b[i][j]=c[i][j];
}
input.close（）;
//每行减去该行最小
intmin=b[i][0];
for（j=1;
if（b[i][j]<
min）
min=b[i][j];
b[i][j]-=min;
//每列减去该列最小
for（j=0;
intmin=b[0][j];
for（i=1;
for（i=0;
//开始尝试进行试指派
assign:
//初始化标记数组和计数数组
rowZero[i]=colZero[i]=0;
rowCheck[i]=colCheck[i]=0;
quan[i][j]=cha[i][j]=0;
//计算每行每列0元素个数
if（b[i][j]==0）
{
rowZero[i]++;
colZero[j]++;
}
boolflag;
//直到尽可能多的0元素都被圈出和划掉为止
do
flag=false;
//寻找只有一个0元素的行，加圈划叉
if（rowZero[i]==1）//该行只有一个0元素
//cout<
rowZerofound:
flag=true;
//找到0元素,加圈划叉
for（j=0;
{
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<
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元素的列，加圈划叉
if（colZero[j]==1）//该列只有一个0元素
for（i=0;
if（b[i][k]==0&
quan[i][k]==0&
cha[i][k]==0）
cha[i][k]=1;
rowZero[i]--;
colZero[k]--;
}while（flag）;
//判断是否还有0元素未被标记
intzeroNotMarked=0;
zeroNotMarked+=rowZero[i];
while（zeroNotMarked!
=0）
/*
从剩有0元素最少的行（列）开始，比较这行各0元素所在列中0元素的数目，
选择0元素少的那列的这个0元素加圈（表示选择性多的要“礼让”选择性少的）。
然后划掉同行同列的其它0元素。
可反复进行，直到所有0元素都已圈出和划掉为止。
*/
intleastZeroRow=0;
while（rowZero[leastZeroRow]==0）
leastZeroRow++;
for（i=leastZeroRow+1;
if（rowZero[i]!
=0&
rowZero[i]<
rowZero[leastZeroRow]）
leastZeroRow=i;
i=leastZeroRow;
//得到0元素最少的行标
intleastZeroCol=0;
while（colZero[leastZeroCol]==0）
leastZeroCol++;
if（b[i][j]==0&
cha[i][j]==0&
colZero[j]<
colZero[leastZeroCol]）
leastZeroCol=j;
j=leastZeroCol;
//得到0元素最少的列标
//圈出b[i][j],划掉i行和j列其余0元素
quan[i][j]=1;
rowZero[i]--;
colZero[j]--;
zeroNotMarked--;
for（k=0;
if（b[i][k]==0&
cha[i][k]=1;
rowZero[i]--;
colZero[k]--;
zeroNotMarked--;
if（b[k][j]==0&
cha[k][j]=1;
rowZero[k]--;
colZero[j]--;
}
//printMatrix（quan）;
//若quan元素的数目countQuan等于矩阵的阶数nn,则得出最优解，否则画线
intcountQuan=0;
countQuan+=quan[i][j];
if（countQuan<
nn）//需要作直线覆盖0元素
//对没有quan的行打勾
inttemp=0;
for（k=0;
temp+=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;
if（rowCheck[i]==1）
for（j=0;
if（cha[i][j]==1&
colCheck[j]==0）
colCheck[j]=1;
newCheck++;
//
（2）
for（j=0;
if（colCheck[j]==1）
for（i=0;
if（quan[i][j]==1&
rowCheck[i]==0）
rowCheck[i]=1;
}while（check!
=newCheck）;
//（5）对rowCheck[]==0的行画横线，colCheck[]==1的列画纵线
//这就得到覆盖所有0元素的最少直线数numLines
intnumLines=0;
if（rowCheck[i]==0）
numLines++;
if（colCheck[j]==1）
if（numLines!
=countQuan）
直线个数不等于画圈0元素个数，试指派有误"
//若numLines=countQuan<
nn，须再变换当前的系数矩阵，以找到nn个独立的0元素
if（numLines==countQuan&
numLines<
nn）
/*
变换矩阵b[i][j]以增加0元素：
设没有被直线覆盖（rowCheck[i]==1&
的有所有元素中的最小元素为min2，
然后打勾各行都减去min2；
打勾各列都加上min2，
将得到的矩阵重新进行试指派
*/
i=0;
while（rowCheck[i]==0）i++;
j=0;
while（colCheck[j]==1）j++;
intmin2=b[i][j];
if（b[i][j]<
min2&
rowCheck[i]==1&
min2=b[i][j];
b[i][j]-=min2;
b[i][j]+=min2;
//将变换后的矩阵b[i][j]重新试指派
gotoassign;
//此时countQuan==nn,输出指派结果
cout<
指派结果如下：
printMatrix（quan）;
system（"
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.8
1.0
丁
0.5
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
Aeq（n+i,1+（i-1）*n:
i*n）=ones（1,n）;
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）;
forj=1:
ify（i,j）==1
sol（i,j）=C（j,i）;
fval=sum（sol
升级会员 