运筹学作业-----关于指派问题的求解算法设计学院:计算机科学与技术学院班级:信息与计算科学1202班学号:1208060220姓名:韩雪平2014、7、31.问题描述与数学模型:在现实生活中,有各种各样的指派问题。
例如,有若干项工作(或者任务,事情)需要分配给若干人(或者部门,设备等)来完成;有若干项合同需要选择若干个投标者来承包;有若干条交通线(如航空线,航海线,公路线等)需要配置若干交通运输工具(如飞机,船只,汽车等)来运营;有若干班级需要安排在不同的教师里上课;等等/诸如此类问题,它们的基本要求就是来满足特定的指派要求时,使指派方案的总体效果最佳。
由于指派总就是多样性的,有必要定义指派的特定问题的标准形式。
指派问题的标准形式(以人与事为例):设有n个人与n件事,已知第i个人做第j件事的费用为cij(i,j=1,2,、、、、n),求人与事之间一一对应的指派方案,使完成的这n件事的总费用最少。
一般称矩阵c11 c12 c13 c14 (1)c21 c22 c23 c24 (2)c31 c32 c33 c34 (3)C= 、、、、、、、、、、、、、、、cn1 cn2 cn3 cn4……cn5为指派问题的系数矩阵。
在实际问题中,根据cij的具体意义,矩阵C可以有不同的名称,如费用矩阵,成本矩阵,时间矩阵等。
系数矩阵C中,第i行各元素表示第i人做各事的费用,第j列各元素表示第j件事由各个人做的费用。
为建立标准的指派问题的数学模型,引入n^2个0-1变量1 当指派第i人去做第i件事时Xij=｛ (i,j=1,2,3……,n)0 当不指派第i人去做第j件事时然后对矩阵进行化解,当然作为可行解,矩阵中每一列都有且只有一个1,每行有且仅有一个1,以满足约束条件2.算法思想:标准的指派问题就是特殊的整数规划问题,也就是特殊的0—1规划问题与特殊的运输问题。
因此它可以用很多相应的解法来求解。
匈牙利解法的依据就是指派问题的最优解的一下性质:设指派问题的系数矩阵C=(cij)n*n、若将C的一行或列分别减去一个常数K,则得到一个新的矩阵C'=(c'ij)n*n,那么C’为系数矩阵的指派问题与以C为系数矩阵的原指派问题有相同的最优解。
虽然不要求指派问题系数矩阵中无负元素,但就是匈牙利解法求解指派问题时,为了从已变换后的系数矩阵中判别能否得到最优指派方案,要求此时的矩阵中无负元素因为只有这样,才能使用总费用为零这一特征来判断指派问题就是否为最优方案。
3、算法流程或步骤:步骤1 变换系数矩阵,使各行与各列皆出现零元素。
如各行各列分别减去本行及本列最小元素,这样可以保证每行及每列都有零元素,同时也避免出现负元素。
步骤2 求能覆盖所有零元素的最少数目的直线集合。
若直线数等于n,则可得出最优解。
否则,转步骤3。
步骤3 变换系数矩阵,使未被直线覆盖的元素中出现零元素。
回到步骤2。
4、算法源程序:/*设计算法用匈牙利法求解指派问题:比如:4 8 7 15 127 9 17 14 10C= 6 9 12 8 76 7 14 6 106 9 12 10 6求出它的最优指派问题////////*////////////////////////////////////////////////////////////////////////////////////#include<stdio、h>int main(void){int i,j,min,a[5][5],m=0,cnt1=0,cnt2=0;printf("请输入一个二维数组:\n");for(i=0;i<5;i++) //输入目标矩阵for(j=0;j<5;j++)scanf("%d",&a[i][j]);for(i=0;i<5;i++)//对每行进行减去行中最小值处理{min=a[i][0];for(j=1;j<5;j++){if(a[i][j]<min)min=a[i][j];}for(j=0;j<5;j++)//对列进行减去减去列中最小值处理a[i][j]=a[i][j]-min;}for(j=0;j<5;j++){min=a[0][j];for(i=1;i<5;i++){if(a[i][j]<min)min=a[i][j];}for(i=0;i<5;i++)a[i][j]=a[i][j]-min;}//while(m!=5)//{/* for(i=0;i<5;i++)//记录每行的零个数{for(j=0;j<5;j++){if(a[i][j]==0)// i1++;cnt1++;//记录输入的每行元素个数}c[i]=cnt1;cnt1=0;//清零}for(j=0;j<5;j++)//记录每列的零个数{for(i=0;i<5;i++){ if(a[i][j]==0)// j1++;cnt2++;}d[j]=cnt2;cnt2=0;//清零}*///}printf("输出变换后的矩阵:\n");for(i=0;i<5;i++){ for(j=0;j<5;j++)printf("%3d",a[i][j]);printf("\n");}printf("\n");/* for(i=0;i<5;i++)printf("%5d",c[i]);printf("\n");for(i=0;i<5;i++)printf("%5d",d[i]);printf("\n");*////////通过边算边验证,此时给第二行与第三行减去它们行中除零的最小值////////printf("给第二行与第三行减去它们行中除零最小的数得:\n");for(j=0;j<5;j++)a[1][j]=a[1][j]-1;for(j=0;j<5;j++)a[2][j]=a[2][j]-1;printf("输出变换后的矩阵:\n");for(i=0;i<5;i++){ for(j=0;j<5;j++)printf("%3d",a[i][j]);printf("\n");}printf("\n");///继续通过边求边验证,此时给第一列加上1///printf("再给第一列加上1后的矩阵如下:\n");for(i=0;i<5;i++)a[i][0]=a[i][0]+1;printf("输出变换后的矩阵:\n");for(i=0;i<5;i++){ for(j=0;j<5;j++)printf("%3d",a[i][j]);printf("\n");}printf("\n");//此时圈零进行调整让每行每列都保有一个零//for(i=0;i<5;i++){ for(j=0;j<5;j++){ if(a[i][j]!=0)a[i][j]=0;elsea[i][j]=1;}}printf("输出变换后的矩阵:\n");for(i=0;i<5;i++){ for(j=0;j<5;j++)printf("%3d",a[i][j]);printf("\n");}printf("\n");//此时继续验证继续调整舍去第二行第一个的数与第四行第二列的数使它们等于0//a[1][0]=0;a[3][1]=0;a[2][4]=0;printf("输出变换后的矩阵:\n");for(i=0;i<5;i++){ for(j=0;j<5;j++)printf("%3d",a[i][j]);printf("\n");}printf("\n");return 0;}////////////////////////////////5、算例与结果:目标矩阵:进行行列变换后处理的矩阵截图如下:对没覆盖的行进行减去行中最小值处理截图://///////////////////////////////////// ////////////////////////对列中的负数进行加上负数最小值处理截图://////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////对行列中不为零与就是零的元素进行处理,使不为零变0,为零变1:///////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////// 调整1的个数,使每行每列都保持有一个1://///////////////////////////////////////////////////////////////////////////////////////////////////6、结论与总结:本次课程设计主要运用了C语言去编写与实现它,通过本次的课程设计,使我在运用C 语言的过程中更加体会到了运筹学这一本课程的实用性,运筹学主要的设计方向就是使一个普通问题变为最优化问题,它就是在研究在有限种或无限中可行方案中选择最优方案,构造寻求最优的计算方法。
![运筹学课件ch5指派问题[全文]](https://img.taocdn.com/s1/m/76c0dd89b9f3f90f77c61b19.png)
