数学建模作业-动态规划求解指派问题

《动态规划求解指派问题》————————————数学模型作业2——————————班级：计算机四班小组成员：zhongchuanzhaoyi＆jayla＆LJY学号：3010216-3010216-3010216指导教师：孙晓晨时间：2013年1月指派问题的动态规划求解1问题重述本文中利用动态规划模型的主要思想解决一类经典问题——指派问题。指派问题一般被分为标准指派问题和非标准指派问题。本文中为刻画问题的普遍性，选择对非标准指派问题做了代码实现。本文中首先分析了非标准指派问题，其次说明了动态规划模型的算法实现，并用实例验证了算法的正确性，最后，附录中是实现了该问题求解的代码。2问题分析在企业经营管理和实际决策过程中，决策者经常会遇到如下问题：有m项工作，每一项工作必须由一人完成，同时有n个人，每一个人可以完成一项工作。第i个人做第j个事件的费用为0ijc(i,j=1,2,⋯,n)，现在要确定完成m项工作总工时最小的分配工作方案。当人数与工作数目不等是分为以下两种情况：（1）若mn，即人多事少，则虚设m-n项工作，使人和工作数目相同，同时取虚设的工作所需完成的费用为0ijc；此时，目标函数值的大小不受影响。（2）若mn，即人少事多，则虚设n-m个人，使人和工作数目相同，同时取虚设的人完成某项工作的费用为0ijc；此时，目标函数值的大小不受影响。本文中解决的指派问题以使得目标函数最大化为目标。解题用到的数学规划模型如下：（1）状态变量：ks(ks为整数)对于m个人n个事件(m=n)的标准指派问题而言,定义人或工作为状态均可。我们定义工作为状态，即ks(k=1,2,⋯,n)表示第k阶段初剩余的工作数，亦即给第k个人指派工作前剩余的工作数。（2）决策变量:：kx(kx为整数)表示指派给第k(k=1,2,⋯,n)阶段的工作;即kx为指派给第k个人的工作；此时；当第k个人做第j个工作时，kx取值为1,当第k个人不做第j个工作时，kx取值为0。因此，我们定义0-1变量kjx如下：kjx=1,第k个人做第j个工作；kjx=0,第k个人不做第j个工作；.,...,2,1,njk（3）状态转移方程：),(111kkkxsgs由决策变量和允许决策集合的定义可得),(11kkxsg的表达式为:}.{),(11111jxsxsgskkkkk，其中“-”表示集合的差运算。（4）指派问题指标递归方程：}|),(min{)(kkkkkkkXxxsfsf，)),((),(),(1111kkkkkkkkkxsgfdsdxsf，.,...,2,1,0)(00nksf3问题的伪代码实现1设k的初始值为1；2写出kX，即第k阶段决策变量可能的取值，特别地，1X={1,2，。。。，n}。3对每一个ks，计算}.{),(11111jxsxsgskkkkk，及),(kkxsd；4计算)(kksf；5若kX为空，转到第6步，否则，k++，转回执行第2步。6最优指派决策为)(kksf，根据)(kksf写出最优指派方案{kjx}。7程序算法复杂度：是O(V*E*E)4实例分析m=n=4，收益矩阵为：152081136222518201016212151210。程序运行结果如下：5附录/********************************************************************指派问题的动态规划算法*********************************************************************/#includestdio.h#includeiostreamusingnamespacestd;typedefstructmatrix{floatcost[101][101];intzeroelem[101][101];floatcostforout[101][101];intmatrixsize;intpersonnumber;intjobnumber;}matrix;matrixsb;intresult[501][2];voidtwozero(matrix&sb);voidjudge(matrix&sb,intresult[501][2]);voidrefresh(matrix&sb);voidcirclezero(matrix&sb);matrixinput();voidoutput(intresult[501][2],matrixsb);voidzeroout(matrix&sb);matrixinput(){matrixsb;intm;intpnumber,jnumber;inti,j;floatk;charw;printf(指派问题的动态规划解法:\n\n);printf(按最大价值分配请输入1;最小价值分配请输入0:\n);scanf(%d,&m);while(m!=1&&m!=0){printf(请输入1或0:\n);scanf(%d,&m);}printf(请输入可分配总人数(介于1和100之间):\n);scanf(%d,&pnumber);while(pnumber1||pnumber100){printf(请输入合法数据:\n);scanf(%d,&pnumber);}printf(请输入工作数(介于1和100之间):\n);scanf(%d,&jnumber);while(jnumber1||jnumber100){printf(请输入合法数据:\n);scanf(%d,&jnumber);}printf(请输入%d行%d列的矩阵,同一行内以空格间隔,不同行间以回车分隔:\n,pnumber,jnumber);for(i=1;i=pnumber;i++)for(j=1;j=jnumber;j++){scanf(%f,&sb.cost[i][j]);sb.costforout[i][j]=sb.cost[i][j];}scanf(%c,&w);if(jnumberpnumber)for(i=pnumber+1;i=jnumber;i++)for(j=1;j=jnumber;j++){sb.cost[i][j]=0;sb.costforout[i][j]=0;}else{if(pnumberjnumber)for(i=1;i=pnumber;i++)for(j=jnumber+1;j=pnumber;j++){sb.cost[i][j]=0;sb.costforout[i][j]=0;}}sb.matrixsize=pnumber;if(pnumberjnumber)sb.matrixsize=jnumber;sb.personnumber=pnumber;sb.jobnumber=jnumber;if(m==1){k=0;for(i=1;i=sb.matrixsize;i++)for(j=1;j=sb.matrixsize;j++)if(sb.cost[i][j]k)k=sb.cost[i][j];for(i=1;i=sb.matrixsize;i++)for(j=1;j=sb.matrixsize;j++)sb.cost[i][j]=k-sb.cost[i][j];}returnsb;}voidcirclezero(matrix&sb){inti,j;floatk;intp;for(i=0;i=sb.matrixsize;i++)sb.cost[i][0]=0;for(j=1;j=sb.matrixsize;j++)sb.cost[0][j]=0;for(i=1;i=sb.matrixsize;i++)for(j=1;j=sb.matrixsize;j++)if(sb.cost[i][j]==0){sb.cost[i][0]++;sb.cost[0][j]++;sb.cost[0][0]++;}for(i=0;i=sb.matrixsize;i++)for(j=0;j=sb.matrixsize;j++)sb.zeroelem[i][j]=0;k=sb.cost[0][0]+1;while(sb.cost[0][0]k){k=sb.cost[0][0];for(i=1;i=sb.matrixsize;i++){if(sb.cost[i][0]==1){for(j=1;j=sb.matrixsize;j++)if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0)break;sb.zeroelem[i][j]=1;sb.cost[i][0]--;sb.cost[0][j]--;sb.cost[0][0]--;if(sb.cost[0][j]0)for(p=1;p=sb.matrixsize;p++)if(sb.cost[p][j]==0&&sb.zeroelem[p][j]==0){sb.zeroelem[p][j]=2;sb.cost[p][0]--;sb.cost[0][j]--;sb.cost[0][0]--;}}}for(j=1;j=sb.matrixsize;j++){if(sb.cost[0][j]==1){for(i=1;i=sb.matrixsize;i++)if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0)break;sb.zeroelem[i][j]=1;sb.cost[i][0]--;sb.cost[0][j]--;sb.cost[0][0]--;if(sb.cost[i][0]0)for(p=1;p=sb.matrixsize;p++)if(sb.cost[i][p]==0&&sb.zeroelem[i][p]==0){sb.zeroelem[i][p]=2;sb.cost[i][0]--;sb.cost[0][p]--;sb.cost[0][0]--;}}}}if(sb.cost[0][0]0)twozero(sb);elsejudge(sb,result);}voidtwozero(matrix&sb){inti,j;intp,q;intm,n;floatk;matrixst;for(i=1;i=sb.matrixsize;i++)if(sb.cost[i][0]0)break;if(i=sb.matrixsize){for(j=1;j=sb.matrixsize;j++){st=sb;if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0){sb.zeroelem[i][j]=1;sb.cost[i][0]--;sb.cost[0][j]--;sb.cost[0][0]--;for(q=1;q=sb.matrixsize;q++)if(sb.cost[i][q]==0&&sb.zeroelem[i][q]==0){sb.zeroelem[i][q]=2;sb.cost[i][0]--;sb.cost[0][q]--;sb.cost[0][0]--;}for(p=1;p=sb.matrixsize;p++)if(sb.cost[p][j]==0&&sb.zeroelem[p][j]==0){sb.zeroelem[p][j]=2;sb.cost[p][0]--;sb.cost[0][j]--;sb.cost[0][0]--;}k=sb.cost[0][0]+1;while(sb.cost[0][0]k){k=sb.cost[0][0];for(p=i+1;p=sb.matrixsize;p++){if(sb.cost[p][0]==1){for(q=1;q=sb.matrixsize;q++)if(sb.cost[p][q]==0&&sb.zeroelem[p][q]==0)break;sb