数学建模指派问题论文设计

1、标准文档目录1 问题重述 22 模型假设 23 匈牙利法陈述 24 问题分析 35 问题实现 51 问题重述 52 问题求解 52.1 由匈牙利法构造目标函数 52.2 模型建立 63 模型解析 64 程序实现 76 结果显示及min 求解 177 模型深入1 71 模型建立 182 进行求解 183 程序分析 208 模型检验 209 整体总结 20十参考文献 21问题重述指派问题亦称平衡指派问题仅研究人数与事数相等、一人一事及一事一人的情形。 现有的不平衡指派问题将研究范围扩大到人数与事数可以不等、一人一事或一人多事及一事一人的情形。日常活动中也不乏人数与事数可以不等、一人多事及一事多人的

2、情形，这类事务呈现了广义指派问题的实际背景。平衡指派问题是特殊形式的平衡运输问题，可运用匈亚利法、削高排除法和缩阵分析法等特殊方法求解。另一方面，正是平衡指派问题的这种特殊性，使得不平衡指派问题不能按常规技术转化为平衡指派问题。因此， 各种不平衡指派问题需要确立相应的有效解法1问题的提出及其数学模型广义指派问题并非奇特和抽象的构想，相反,该问题可以从司空见惯的日常事务中引出。现在我们就运用匈牙利法，去实现n 个人， n 件工作的指派问题。二 模型假设1 假设一共有n 个人， n 件工作，即人数与工作数相等。2 假设每个人的都能从事某项工作，但是付出的代价不同。3 假设求解代价最小的解。4甲乙丙

3、丁四个人，ABCD四项工作，要求每人只能做一项工作，每项工作只由一人完成，问如何指派总时间最短？三 匈牙利法陈述第一步：找出矩阵每行的最小元素，分别从每行中减去这个最小元素；第二步：再找去矩阵每列的最小元素，分别从各列减去这个最小元素；第三步：经过这两步变换后，矩阵的每行每列至少都有了一个零元素，接着根据以下准则进行试指派，找出覆盖上面矩阵中所有零元素至少需要多少条直线；（ 1）从第一行开始，若该行只有一个零元素打上（）号。对打（）号零元素所在列划一条直线。若该行没有零元素或有两个以上零元素（已划去的不计在内），则转下一行，一直到最后一行为止；（ 2）从第一列开始，若该列只有一个零元素就对这个

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

5、个打（）的零元素，就要继续对矩阵进行变换；（ 1）从矩阵未被直线覆盖的元素找出最小元素k；（ 2） 对矩阵的每行，当该行有直线覆盖时，令 ui =0， 无直线覆盖的，令 ui =k；（ 3） 对矩阵的每列，当该列有直线覆盖时，令 vj =-k， 无直线覆盖的，令 vj =0；（ 4） 列一个变换后的矩阵，其中每个元素bij =aij - ui- vj。第五步：回到第三步，反复进行，一直到矩阵中每一行都有一个打（）的零元素为止，即找到最优分配方案为止。四 问题分析指派问题的标准形式（以人和事为例）如下。有n 个人和 n 项任务，已知第i 个人做第j 件事的费用为cij，要求确定人和事之间的一一对

6、应的指派方案，使完成这 n 项任务的费用最少。一般把目标函数的系数写为矩阵形式，称矩阵实用文案标准文档c11 c12 . c1nC21 C22 . c2nC = (cij ) nM =cn1cn2 . cnn实用文案为系数矩阵（Coefficient Matrix）,也称为效益矩阵或价值矩阵。矩阵的元素cij （i,j=1,2, ）表示分配第i个人去完成第j项任务时的效益。一般地，以xij表示给定的资源分配用于给定活动时的有关效益（时间，费用，价值等），且xj°不分配第印位资源用于第j项活动 “ n 1,分配第i单位资源用于第j项活动', ）代价和模型,（1）然后我们求解最小

7、(最大(这里不再讨论) n nmin (max) z = £ £ qxj i T j 3nstZ xij =1, i =1,2,., nj 1n.二.xj = 1, j = 1,2,., ni 1xij - 0或 1,i, j = 1,2,., n当然，作为可行解，矩阵的每列元素中都有且只有一个 1,以满足约束条 件式（3）。每行元素中也有且只有一个1,以满足约束条件（2）0指派问题n! 个可行解。n n如果要求解最大值max z = ZZ cjxj时，我们将构造一个新的矩阵（qjj ）, i 1 j 1使q； =M -q ,其中M是一个足够大的常数。一般取cj中最大的元素

8、作为M ,n n求解min z' = £ Z (M -cj xj ,所得的解(看 )就是原问题的解。 i =1 j =1事实上，由n nn n,二二 qxj -M -cj %i T j Ti m j Tn nn n- - M xj - - cij xij i m j mi 3 j=1n n=Mn .，= cij xij可的此结论五问题实现1问题重述已知问题甲乙丙丁四个人，ABCD四项工作，要求每人只能做一项工作, 每项工作只由一人完成，问如何指派总时间最短？每个人的对每项工作的代价如下：河711CD甲35SL654丙25SP 5TJ152 _2问题求解开始求解2.1由匈牙利法

9、构造目标函数92 20min - ' dj* Xji 1 j 1引入0-1变量Xj ,xj =1:第i人做第j项工作Xj =0：第i人不做第j项工作约束条件：=1第i个工作从事第j个工作Xij -0第i个工作不能被从事(i=1,2,92 j=1,2,20)2.2模型建立即一项任务只由一个人完成XllX21X31X41:1X12x22X32X42=1X13X23X33X43=1Xl4X24X34X44=1一人只能完成一项任务X11X12X13X14 = 1X21X22X23X24=1V + V + V + V=dX31X32X33X34X41X42X43X44=1求出目标函数minZ =

10、 3Ml5%28-4%46%8%25%34&42X315X328X335X349X412X425X432X443模型解析根据指派问题的最优性定理，求最优解的问题可以转换为求效益矩阵的大1元素组的问题。匈牙利法的一般计算步骤为：步骤1：对效益矩阵进行初等变换，使每行每列都出现 0元素。1. 从效益矩阵A中每一行减去该行的最小元素；2. 再在所得矩阵中每一列减去该列的最小元素，得矩阵D;将矩阵D中0元素置为1元素，非0元素置为0元素，得矩阵E步骤2:标准文档步骤3：确定独立1 元素组。1. 在矩阵 E 中含有 1 元素的各行中选择1 元素最少的行，比较该行中各 1 元素所在的列中1 元素的

11、个数，选择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. 在没有被直线覆盖的部分找出最小元素，在没有被直

12、线覆盖的各行减去此最小元素，在没有被直线覆盖的各列上加上此最小元素，得到一个新的矩阵，返回第二步。4 程序实现这里我们运用C+语言进行编程进行求解/*/* zhipai2.CppAuthor: 路遥Date:2012-12-1DesCription:需要在同样的目录下建立一个input.txt 的文件夹在里面写入每个人从事不同的工作代价，首行要写入几阶方程，然后是每个人的不同工作代价，用空格隔开。每人一行，见下面数字形式。用匈牙利法，实现n 个人， n 件工作的指派问题。Input:input.txt格式为代价矩阵维度n,和矩阵内容，例如：43 5 8 46 8 5 42 5 8 59 2 5

13、 2Output:控制台输出指派矩阵，例如0 0 0 10 0 1 01 0 0 00 1 0 0*/* */#include <iostream>#include <fstream>using namespace std;#define MAX_N 100int nn;/ 输入矩阵的维度nnvoid printMatrix(int aMAX_NMAX_N)int i,j;for(i=0;i<nn;i+)for(j=0;j<nn;j+)cout<<aij<<" "cout<<endl;int main(

14、)int cMAX_NMAX_N,bMAX_NMAX_N;int quanMAX_NMAX_N,chaMAX_NMAX_N;int rowZeroMAX_N,colZeroMAX_N;int rowCheckMAX_N,colCheckMAX_N;int i,j,k;ifstream input("input.txt");if(!input)cout<<"Open input file failed."<<endl;system("pause");exit(1);实用文案标准文档)/读取输入文件 input&g

15、t;>nn;for(i=0;i<nn;i+)(for(j=0;j<nn;j+)(input>>cij; bij=cij;)input.close();/每行减去该行最小for(i=0;i<nn;i+)(int min=bi0;for(j=1;j<nn;j+)(if(bij<min) min=bij;)for(j=0;j<nn;j+) bij -= min;)/每列减去该列最小for(j=0;j<nn;j+)(int min=b0j;for(i=1;i<nn;i+)(if(bij<min) min=bij;)for(i=0;

16、i<nn;i+) bij -= min;)/开始尝试进行试指派assign:/ 初始化标记数组和计数数组for(i=0;i<nn;i+)rowZeroi=colZeroi=0;rowChecki=colChecki=0;for(j=0;j<nn;j+)quanij=chaij=0;/ 计算每行每列0 元素个数for(i=0;i<nn;i+)for(j=0;j<nn;j+)if(bij=0)rowZeroi+; colZeroj+;bool flag;/ 直到尽可能多的0 元素都被圈出和划掉为止doflag=false;/ 寻找只有一个0 元素的行，加圈划叉for(

17、i=0;i<nn;i+)if(rowZeroi=1)/ 该行只有一个0 元素/cout<<"rowZero found: "<<i<<endl; flag=true;/ 找到 0 元素 , 加圈划叉 for(j=0;j<nn;j+)if(bij=0 && quanij=0 && chaij=0) quanij=1;rowZeroi-; colZeroj-;for(k=0;k<nn;k+) if(bkj=0&&quankj=0&&chakj=0)chakj=1

18、;rowZerok-;colZeroj-;break;/break;/ 寻找只有一个0 元素的列，加圈划叉for(j=0;j<nn;j+)if(colZeroj=1)/ 该列只有一个0 元素flag=true;/ 找到 0 元素 , 加圈划叉for(i=0;i<nn;i+)if(bij=0 && quanij=0 && chaij=0)quanij=1;rowZeroi-;colZeroj-;for(k=0;k<nn;k+) if(bik=0&&quanik=0&&chaik=0)chaik=1;rowZeroi

19、-;colZerok-; break;/break; while (flag);/ 判断是否还有0 元素未被标记int zeroNotMarked = 0;for(i=0;i<nn;i+)zeroNotMarked += rowZeroi;while(zeroNotMarked != 0)/*从剩有 0 元素最少的行( 列 ) 开始，比较这行各0 元素所在列中0 元素的数目，选择 0 元素少的那列的这个0 元素加圈 ( 表示选择性多的要 “礼让” 选择性少的 ) 。然后划掉同行同列的其它0 元素。可反复进行，直到所有0 元素都已圈出和划掉为止。*/int leastZeroRow=0;w

20、hile(rowZeroleastZeroRow=0)leastZeroRow+;for(i=leastZeroRow+1;i<nn;i+)if(rowZeroi!=0 && rowZeroi<rowZeroleastZeroRow) leastZeroRow=i;i=leastZeroRow;/ 得到 0 元素最少的行标int leastZeroCol=0;while(colZeroleastZeroCol=0)leastZeroCol+;for(j=0;j<nn;j+)if(bij=0&& quanij=0&& chaij=

21、0&&colZeroj<colZeroleastZeroCol)leastZeroCol=j;j=leastZeroCol;/ 得到 0 元素最少的列标/ 圈出 bij, 划掉 i 行和 j 列其余 0元素quanij=1;rowZeroi-;colZeroj-;zeroNotMarked-;for(k=0;k<nn;k+)if(bik=0 && quanik=0 && chaik=0)chaik=1;rowZeroi-;colZerok-;zeroNotMarked-;for(k=0;k<nn;k+)if(bkj=0 &

22、;& quankj=0 && chakj=0)chakj=1;rowZerok-;colZeroj-;zeroNotMarked-;/printMatrix(quan);若quan元素的数目countQuan等于矩阵的阶数nn,则得出最优解，否则画 线int countQuan=0;for(i=0;i<nn;i+)for(j=0;j<nn;j+)countQuan += quanij;if(countQuan < nn)/ 需要作直线覆盖0 元素/ 对没有 quan 的行打勾for(i=0;i<nn;i+)int temp=0;for(k=0;k

23、<nn;k+)temp+=quanik;if(temp=0)rowChecki=1;/*重复执行 (1)(2) ，直到打不出新的勾为止：(1)对已打勾的行中含cha的元素的列打勾(2) 对已打勾的列中含quan 的元素的行打勾*/int newCheck=0;int check;docheck=newCheck;/(1)for(i=0;i<nn;i+)if(rowChecki=1)for(j=0;j<nn;j+)if(chaij=1 && colCheckj=0)colCheckj=1;newCheck+;/(2)for(j=0;j<nn;j+)if(c

24、olCheckj=1)for(i=0;i<nn;i+)if(quanij=1 && rowChecki=0)rowChecki=1;newCheck+; while (check!=newCheck);/(5) 对 rowCheck=0 的行画横线，colCheck=1 的列画纵线/ 这就得到覆盖所有0 元素的最少直线数numLinesint numLines=0;for(i=0;i<nn;i+)if(rowChecki=0)numLines+;for(j=0;j<nn;j+)if(colCheckj=1)numLines+;if(numLines != co

25、untQuan)cout<<" 直线个数不等于画圈0元素个数，试指派有误"<<endl;/ 若 numLines = countQuan < nn ，须再变换当前的系数矩阵，以找到nn 个独立的0元素if(numLines=countQuan && numLines < nn)/*变换矩阵bij 以增加 0 元素：设没有被直线覆盖(rowChecki=1 && colCheckj=0)的有所有元素中的最小元素为min2，然后打勾各行都减去 min2；打勾各列都加上min2,将得到的矩阵重新进行试指派*/i=

26、0;while(rowChecki=0) i+;j=0;while(colCheckj=1) j+;int min2=bij;for(i=0;i<nn;i+)for(j=0;j<nn;j+)if(bij<min2 && rowChecki=1 && colCheckj=0) min2=bij;for(i=0;i<nn;i+)if(rowChecki=1)for(j=0;j<nn;j+)bij -= min2;for(j=0;j<nn;j+)if(colCheckj=1)for(i=0;i<nn;i+)bij += min

27、2;/ 将变换后的矩阵bij 重新试指派goto assign;/此时countQuan=nn,输出指派结果cout<<" 指派结果如下："<<endl;printMatrix(quan);system("pause");return 0;实用文案标准文档H制台希出拚襁阵,笆M 00D1nn1ai(1。Urielude Cia£trejR> likludte CfLcejiiii jLAL. rVjq|itiiiri««ri,P-ri.G*faLigiJn pi 2'一六 结果显示及 m

28、in求解ulngi 即f印3e £td;Miitf B if HAK_Hi 1IH! 1、一 。-C*nf igiiatioiwzhifMilSee - error Cs)>>h B urnLiMin (z) =4+5+2+2=13即求出最小代价。完成假设要求七模型深入将约束条件由整数数据变为小数数据且目标函数由最小值化为最大值问题 的求解。假设有4件工作分派给4个人来做，每项工作只能由一人来做，每个人只能 做一项工作。下表为各人对各项工作所具有的工作效率。问应该如何安排人选， 及发挥个人特长又能使总的效率最大。每个人完成各项任务需要的时间ABCD甲0.60.20.30.

29、1乙0.70.40.30.2丙0.81.00.70.31丁0.70.70.50.41模型建立数学模型为max z =0.6x11 0.2x12 0.3x13 0.1x14 0.7x21 0.4x22 0.3x23 0.2x24 - 0.8x31T.0x32 0.7x33 0.3x34 0.7x41 0.7x42 0.5x43 0.4x44 实用文案标准文档ub=ones(n*n,1);s.t.x11x21x31x41x12x13x14 = 1x22x23x24x32x33x34x42x43x44xiix21x31x41=1二1=1二1x12 ' x22 ' x32 . x42

30、: 1x13x23 ' x33 x43 = 1Ax24x34x44 = 1xij=0 或 1, i, j=1, 2, 3, 42进行求解本次我们使用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);for i=1:nAeq(1:n,1+(i-1)*n:i*n)=eye(n,n);endfor i=1:nAeq(n+i,1+(i-1)*n:i*n)=ones(1,n);endbeq=ones(2*n,1);lb=zeros(n*n,1);x=linprog(f,Aeq,beq,lb,ub); y=reshape(x,n,n);y=y'y=round(y);sol=zeros(n,n);for i=1:nfor j=1:nif y(i,j)=1so