运筹学指派问题.doc

《运筹学指派问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学作业-----关于指派问题的求解算法设计学院：计算机科学与技术学院班级：信息与计算科学1202班学号：1208060220姓名：韩雪平2014.7.31.问题描述与数学模型：在现实生活中，有各种各样的指派问题。例如，有若干项工作（或者任务，事情）需要分配给若干人（或者部门，设备等）来完成；有若干项合同需要选择若干个投标者来承包；有若干条交通线（如航空线，航海线，公路线等）需要配置若干交通运输工具（如飞机，船只，汽车等）来运营；有若干班级需要安排在不同的教师里上课；等等/诸如此类问题，它们的基本要求是来满足特定的指派要

2、求时，使指派方案的总体效果最佳。由于指派总是多样性的，有必要定义指派的特定问题的标准形式。指派问题的标准形式（以人和事为例）：设有n个人和n件事，已知第i个人做第j件事的费用为cij(i,j=1,2,....n),求人与事之间一一对应的指派方案，使完成的这n件事的总费用最少。一般称矩阵c11c12c13c14……c1nc21c22c23c24……c2nc31c32c33c34……c3nC=...............cn1cn2cn3cn4……cn5为指派问题的系数矩阵。在实际问题中，根据cij的具体意义，矩阵C可以有不

3、同的名称，如费用矩阵，成本矩阵，时间矩阵等。系数矩阵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规划问题和特殊的运输问题。因此它可以用很多相应的解法来求解。匈牙利解法的依

4、据是指派问题的最优解的一下性质：设指派问题的系数矩阵C=（cij）n*n.若将C的一行或列分别减去一个常数K，则得到一个新的矩阵C'=（c'ij）n*n,那么C’为系数矩阵的指派问题和以C为系数矩阵的原指派问题有相同的最优解。虽然不要求指派问题系数矩阵中无负元素，但是匈牙利解法求解指派问题时，为了从已变换后的系数矩阵中判别能否得到最优指派方案，要求此时的矩阵中无负元素因为只有这样，才能使用总费用为零这一特征来判断指派问题是否为最优方案。3.算法流程或步骤:步骤1变换系数矩阵，使各行和各列皆出现零元素。如各行各列分别减去本行

5、及本列最小元素，这样可以保证每行及每列都有零元素，同时也避免出现负元素。步骤2求能覆盖所有零元素的最少数目的直线集合。若直线数等于n，则可得出最优解。否则，转步骤3。步骤3变换系数矩阵，使未被直线覆盖的元素中出现零元素。回到步骤2。4.算法源程序：/*设计算法用匈牙利法求解指派问题：比如：487151279171410C=69128767146106912106求出它的最优指派问题////////*///////////////////////////////////////////////////////////////

6、/////////////////////#includeintmain(void){inti,j,min,a[5][5],m=0,cnt1=0,cnt2=0;printf("请输入一个二维数组:");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]

7、or(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]

8、素个数}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("输出变换后的矩阵:");for(