精华内容
下载资源
问答
  • v=[ ];x=[ ];a=[ ]; ...对于大型阵列,MATLAB必须分配一个新块内存和年长数组内容复制到新数组,因为它使每个任务。程序,以这种方式改变一个变量大小可以花大部分运行时间在这种低效率的活动。
  • 大致看了看MPI的一些函数,勉强写出这两个程序,这两个程序的效率不高(这个问题很严重),而且对输入的鲁棒性非常不好(可能并行程序不太需要关注这个)。 只是实现了功能,有非常多优化的空间,如果有时间的话再优化...

    大致看了看MPI的一些函数,勉强写出这两个程序,这两个程序的效率不高(这个问题很严重),而且对输入的鲁棒性非常不好(可能并行程序不太需要关注这个)。

    只是实现了功能,有非常多优化的空间,如果有时间的话再优化吧。

    要求一个行向量和一个方阵的乘积,乘积结果也是一个行向量,用MPI编写并行程序。假设子任务数目总是能被进程数均匀划分。

    ①方阵按列分配任务

    在输入时转置输入,则按列分配就变成了按行分配,只要直接分发给各个进程。

    MPI程序

    #include<stdio.h>
    #include<mpi.h>
    #include<stdlib.h>
    
    int main()
    {
        int comm_sz;//进程数
        int my_rank;//本进程的编号
        int i,j;//游标
        int allsum=0;//所有进程加和,给0号进程用
        int N;//待用户键入的数,表示阶数
        int *mat=NULL;//存矩阵数组
        int *subMat=NULL;//子矩阵数组
        int sum;//保存暂时和
        int *result=NULL;//结果
        int *allResult=NULL;//总结果
    
        /*****************************************/
        MPI_Init(NULL,NULL);//初始化MPI
        MPI_Comm_size(MPI_COMM_WORLD,&comm_sz);//获取进程数
        MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);//获取本进程号
    
        //读入和广播阶数N
        if(my_rank==0)//如果是0号进程
        {
            printf("Input N:");
            scanf("%d",&N);//只有0号进程能接受标准输入
    
            //构建矩阵数组
            mat=malloc(N*N*sizeof(int));
        }
        //将0号进程收到的N广播给所有进程
        MPI_Bcast(&N,1,MPI_INT,0,MPI_COMM_WORLD);
    
        //构建向量数组
        int *vec=malloc(N*sizeof(int));
    
        //读入和广播向量vec
        if(my_rank==0)
        {
            printf("Input the Vec:\n");
            for(i=0;i<N;i++)
                scanf("%d",&vec[i]);
        }
        //将0号进程收到的vec广播给所有进程
        MPI_Bcast(vec,N,MPI_INT,0,MPI_COMM_WORLD);
    
    
        //每个进程构建自己的子矩阵数组
        subMat=malloc(N*N/comm_sz*sizeof(int));
        //转置地读入和散射矩阵
        if(my_rank==0)
        {
            printf("Input the Mat:\n");
            //转置地读入,外循环是列
            for(j=0;j<N;j++)
                for(i=0;i<N;i++)
                    scanf("%d",&mat[i*N+j]);
        }
        //把矩阵的各个列散射到各个向量
        MPI_Scatter(mat,
            N/comm_sz*N,
            MPI_INT,
            subMat,
            N/comm_sz*N,
            MPI_INT,
            0,
            MPI_COMM_WORLD);
    
        //计算本进程的任务,得到N/comm_sz个数
        result=malloc(N/comm_sz*sizeof(int));//存放这些数
        for(i=0;i<N/comm_sz;i++)
        {
            sum=0;
            for(j=0;j<N;j++)
            {
                sum+=vec[j]*subMat[i*N+j];      
            }
            result[i]=sum;
            //printf("PID:%d,sum=%d\n",my_rank,sum);
        }
    
        if(my_rank==0)
        {
            allResult=malloc(N*sizeof(int));
            //聚集
            MPI_Gather(result,
            N/comm_sz,
            MPI_INT,
            allResult,
            N/comm_sz,
            MPI_INT,
            0,
            MPI_COMM_WORLD
            );
        }
        else
            //聚集
            MPI_Gather(result,
            N/comm_sz,
            MPI_INT,
            allResult,
            N/comm_sz,
            MPI_INT,
            0,
            MPI_COMM_WORLD
            );
    
        //仅在0号进程上统计最后的加和
        if(my_rank==0)
        {
            printf("Final Result:[");
            for(i=0;i<N-1;i++)
                printf("%d,",allResult[i]);
            printf("%d]\n",allResult[i]);
        }
    
        MPI_Finalize();//使用完释放为MPI分配的资源
        /*****************************************/
    
        free(mat);
        free(subMat);
        free(result);
        free(allResult);
    
        return 0;
    }

    运行结果

    这里写图片描述

    这里写图片描述

    ②方阵按块分配任务

    这里要求进程数一定是一个完全平方数,而且正好能够把方阵分成这么多的小方阵。做法是先把读入进来的方阵按块子块展开到一行行,然后再分发给各个进程。

    MPI程序

    #include<mpi.h>
    #include<stdio.h>
    #include<stdlib.h>
    //#include<math.h>
    
    //自己的求平方根的函数,因为math里的sqrt报错
    int mysqrt(int k)
    {
        int i;
        for(i=0;i*i<k;i++)
            ;
        if(i*i==k)
            return i;
        return -1;
    }
    
    //重排:将正常的矩阵a按块划分排列后给b
    //N:大矩阵阶数,t:子阵维度,blks:每行能放的块数
    void reSet(int *a,int *b,int N,int blks)
    {
        int t=N/blks;//子阵维度
        int i,j,k,r;
        for(i=0;i<N;i++)//每行(每个进程号)
        {
            //k为原分块矩阵的左上角位置
            //只和进程号i有关
            k=(i/blks)*N*t+(i%blks)*t;
            for(j=0;j<N;j++)//每列
            {
                //r为从左上角位置到该位置的偏移值
                //只和块内编号j有关
                r=j/t+(j%t)*N;
                b[i*(t*t)+j]=a[k+r];//k+r即是在原数组中的位置
            }
        }
    }
    
    //输出数组
    void printMat(int *a,int n)
    {
        int i,j;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
                printf("%d ",a[i*n+j]);
            printf("\n");
        }
    }
    
    
    int main()
    {
        int i,j;//游标
        int N;//大矩阵的阶数
        int comm_sz;//总的进程数
        int my_rank;//本进程号
        int *big_mat=NULL;//大矩阵(方阵)
        int *new_mat=NULL;//新的,按分块重排至行的方阵
        int *vec=NULL;//整个向量
        int numline;//用来记录这个进程在处理的是分块后的第几行
        int *myRst=NULL;//用来记录本进程处理的,子向量乘这一块矩阵的结果
        int *subMat=NULL;//用来记录本进程要处理的这一块分块矩阵
        int blks;//blks:每行能放的块数
        int t;//t:子阵维度
        int allsum;//总和,给0号进程用
        int *allResult=NULL;//总结果向量
    
        /******************************************************/
        MPI_Init(NULL,NULL);//初始化MPI
        MPI_Comm_size(MPI_COMM_WORLD,&comm_sz);//获取进程数
        MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);//获取本进程号
    
        /*①对阶数N的处理(读入和广播)*/
    
        //读入和广播阶数N
        if(my_rank==0)//如果是0号进程
        {
            printf("Input N:");
            scanf("%d",&N);//只有0号进程能接受标准输入
    
            //只为0号进程构建大的矩阵数组
            big_mat=malloc(N*N*sizeof(int));
        }
        //将0号进程收到的N广播给所有进程
        MPI_Bcast(&N,1,MPI_INT,0,MPI_COMM_WORLD);
    
        //blks:每行能放的块数
        blks=mysqrt(comm_sz);
        if(blks==-1)
        {
            printf("Not the total square number!Bye!\n");
            return 0;
        }
        //t:子阵维度
        t=N/blks;
    
        /*②构建各个进程的向量和结果数组*/
    
        //为每个进程分配向量数组
        vec=malloc(N*sizeof(int));
        //读入和广播向量vec
        if(my_rank==0)
        {
            printf("Input the Vec:\n");
            for(i=0;i<N;i++)
                scanf("%d",&vec[i]);
        }
        //将0号进程收到的vec广播给所有进程
        MPI_Bcast(vec,N,MPI_INT,0,MPI_COMM_WORLD);
    
        //用来记录这个进程在处理的是分块后的第几行
        numline=my_rank/blks;
        //保存自己计算的结果的向量,阶数就是子矩阵的阶数t
        myRst=malloc(t*sizeof(int));
        //清空
        for(i=0;i<t;i++)
            myRst[i]=0;
    
        /*③读入总的矩阵,
        然后把分块变换成行,
        分发给不同的进程*/
    
        //读入矩阵,变换分块矩阵为分行
        if(my_rank==0)
        {
            printf("Input the Mat:\n");
            //读入
            for(i=0;i<N;i++)
                for(j=0;j<N;j++)
                    scanf("%d",&big_mat[i*N+j]);
            //new_mat存变换后的矩阵
            //实际上是每行t*t个元素!但是总元素数还是N*N
            new_mat=malloc(N*N*sizeof(int));
            //对其进行块划分重排
            reSet(big_mat,new_mat,N,blks);
            //输出看一下
            printf("After change:\n");
            printMat(new_mat,N);
        }
    
        //为每个进程计算时用到的子矩阵分配空间
        //每个子矩阵是t*t的,所以要分配t*t的空间
        //只要把变换后的矩阵的一行行传入即可(每行t*t个元素)
        subMat=malloc(t*t*sizeof(int));
        //把划分后的矩阵(new_mat)的各个行散射到各个进程的subMat中
        MPI_Scatter(new_mat,
            t*t,
            MPI_INT,
            subMat,
            t*t,
            MPI_INT,
            0,
            MPI_COMM_WORLD);
    
        /*④每个进程各自计算结果
        每个进程拿到的子矩阵是一列列排到一行上,
        所以只要按子矩阵的维度遍历之,
        但应注意不同进程使用的子向量可能不同*/
    
        //p是这个进程子向量在列向量上的开始位置
        int p=my_rank/blks;
        //子矩阵一共有t列
        for(i=0;i<t;i++)
        {
            //对于每一列上的每个元素
            for(j=0;j<t;j++)
            {
                //vec[p]:子向量在向量中的起始位置
                //把每一列的向量和子向量内积放入myRst的对应位置
                myRst[i]+=vec[p*t+j]*subMat[i*t+j];/*p+j*/
            }
        }
    
        /*
        printf("My id:%d,my result:\n",my_rank);
        for(i=0;i<t;i++)
            printf("%d ",myRst[i]);
        printf("\n");
        */
    
        /*⑤聚集到0号进程上
        实际上是开了comm_sz个t长度组成的总向量作聚集*/
        if(my_rank==0)
        {
            //结果向量一共是comm_sz个长度为t的子向量
            allResult=malloc(t*comm_sz*sizeof(int));
            //聚集
            MPI_Gather(myRst,
            t,
            MPI_INT,
            allResult,
            t,
            MPI_INT,
            0,
            MPI_COMM_WORLD
            );
        }
        else
            //聚集
            MPI_Gather(myRst,
            t,
            MPI_INT,
            allResult,
            t,
            MPI_INT,
            0,
            MPI_COMM_WORLD
            );
    
        /*⑥从结果长向量中计算结果
        把后面的分量加到0~t-1分量上去*/
        if(my_rank==0)
        {
            //后面的分量加上来
            for(i=N;i<t*comm_sz;i++)
                //printf("%d,",allResult[i]);
                allResult[i%N]+=allResult[i];
            //输出看一下
            printf("Finally Result:[");
            for(i=0;i<N-1;i++)
                printf("%d,",allResult[i]);
            printf("%d]\n",allResult[i]);
    
        }
    
    
        MPI_Finalize();//使用完释放为MPI分配的资源
        /******************************************************/
    
        //因为它们都初始设置成NULL
        //所以完全可以安全的对所有进程free掉
        free(big_mat);
        free(new_mat);
        free(vec);
        free(myRst);
        free(subMat);
        free(allResult);
    
        return 0;
    }
    
    

    运行结果

    这里写图片描述

    这里写图片描述

    展开全文
  • 已知每人完成每项任务所需时间效率矩阵C[i,j]如下。问如何分配任务,使完成所有工作所用总时间最少?例如:任务为1,2,3,4,人员为1,2,3,4,时间效率矩阵C[i,j]为:任务1任务2任务3任务4人员1215134人员...

    1. 指派问题

    n项任务要分配给n个人去做,每人只完成一项任务,每个任务也只由一个人完成。已知每人完成每项任务所需的时间效率矩阵C[i,j]如下。问如何分配任务,使完成所有工作所用的总时间最少?

    例如:任务为1234,人员为1234,时间效率矩阵C[i,j]为:

    任务1

    任务2

    任务3

    任务4

    人员1

    2

    15

    13

    4

    人员2

    10

    4

    14

    5

    人员3

    9

    14

    16

    13

    人员4

    7

    8

    11

    9

     2. 模型建立

    引入决策变量x[i,j],如果让第i个人去完成第j项任务,则x[i,j] =1,否则x[i,j] = 0,则指派问题的数学模型为:

    9567f2b69d58c5e31fd8741ed7b169b2.png

    3. Matlab求解

    MATLAB求解线性规划或混合整数规划时,决策变量只能是向量(即一维数组),所以需要把上述数学模型中的双下标常量和决策变量都转化成单下标变量,同时约束也需要进行相应的转换。最终求解代码如下。

    Matlab代码:

    f=[2,10,9,7,15,4,14,8,13,14,16,11,4,5,13,9];intcon = 1:16;Aeq=[1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1;1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1]beq = ones(8,1);lb=zeros(1,16);ub=ones(1,16);[Y,fval,exitflag] = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);x=reshape(Y,4,4)fval

    Matlab结果输出:

    ans =     0     0      0     1     0     1      0     0     1     0      0     0     0     0      1     0Fval = 28

    新版MATLAB提供了更具可读性的问题描述及解决方法。

    新版Matlab求解代码:

    c = [2 15 13 4; 10 4  14 5; 9 14 16 13; 7 8 11 9];prob =  optimproblem('ObjectiveSense', 'min');x = optimvar('x', 4,  4, 'Type', 'integer', 'LowerBound', 0, 'UpperBound', 1);prob.Objective =  sum(sum(c .* x));prob.Constraints.cond1  = sum(x, 1) == 1;prob.Constraints.cond2  = sum(x, 2) == 1;% prob.showproblemsol = prob.solve;sol.x

    Matlab结果输出:

    LP:                Optimal  objective value is 28.000000.                                           Optimal solution found.Intlinprog stopped at the root node because theobjective value is within a gap tolerance of the optimal value,options.AbsoluteGapTolerance = 0 (the default value). The intcon  variables areinteger within tolerance, options.IntegerTolerance = 1e-05 (the  default value).ans =     0     0      0     1     0     1      0     0     1     0      0     0     0     0      1     0

    4. Lingo求解

          LINGO来求解这个指派问题,只需要会建立集合及其属性,其它就基本上是对数学模型的直接翻译,无需复杂的转换。

    Lingo求解代码:

    MODEL:DATA:N = 4;ENDDATASETS:AGENTS/1..N/;TASKS/1..N/;MATRIX(AGENTS,TASKS):COST, X;ENDSETSDATA:COST =2,15,13,4,10,4,14,5,9,14,16,137,8,11,9;ENDDATAMIN = @SUM(AGENTS(I) :    @SUM(TASKS(J):  COST(I,J)*X(I,J)));@FOR(AGENTS(I):    @SUM(TASKS(J):X(I,J)) =  1);@FOR(TASKS(J):    @SUM(AGENTS(I):X(I,J)) =  1);@FOR(AGENTS(I):    @FOR(TASKS(J) :  @GIN(X(I,J))));END

    Lingo结果输出

    Global optimal solution  found.

      Objective value:                     28.00000000000000  Objective bound:                     28.00000000000000  Infeasibilities:                     0.000000000000000  Extended solver  steps:                               0  Total solver  iterations:                              0  Elapsed runtime  seconds:                          0.03  Model Class:                                      PILP  Total variables:                     16  Nonlinear variables:                  0  Integer variables:                   16  Total constraints:                    9  Nonlinear  constraints:                0  Total nonzeros:                      48  Nonlinear nonzeros:                   0              Variable                    Value                 Reduced Cost                     N        4.000000000000000            0.000000000000000           COST( 1, 1)        2.000000000000000            0.000000000000000           COST( 1, 2)        15.00000000000000            0.000000000000000           COST( 1, 3)        13.00000000000000            0.000000000000000           COST( 1, 4)        4.000000000000000            0.000000000000000           COST( 2, 1)        10.00000000000000            0.000000000000000           COST( 2, 2)        4.000000000000000            0.000000000000000           COST( 2, 3)        14.00000000000000            0.000000000000000           COST( 2, 4)        5.000000000000000            0.000000000000000           COST( 3, 1)        9.000000000000000            0.000000000000000           COST( 3, 2)        14.00000000000000            0.000000000000000           COST( 3, 3)        16.00000000000000            0.000000000000000           COST( 3, 4)        13.00000000000000            0.000000000000000           COST( 4, 1)        7.000000000000000            0.000000000000000           COST( 4, 2)        8.000000000000000            0.000000000000000           COST( 4, 3)        11.00000000000000            0.000000000000000           COST( 4, 4)        9.000000000000000            0.000000000000000              X( 1, 1)        0.000000000000000            2.000000000000000              X( 1, 2)        0.000000000000000            15.00000000000000              X( 1, 3)        0.000000000000000            13.00000000000000              X( 1, 4)        1.000000000000000            4.000000000000000              X( 2, 1)        0.000000000000000            10.00000000000000              X( 2, 2)        1.000000000000000            4.000000000000000              X( 2, 3)        0.000000000000000            14.00000000000000              X( 2, 4)        0.000000000000000            5.000000000000000              X( 3, 1)        1.000000000000000            9.000000000000000              X( 3, 2)        0.000000000000000            14.00000000000000              X( 3, 3)        0.000000000000000            16.00000000000000              X( 3, 4)        0.000000000000000            13.00000000000000              X( 4, 1)        0.000000000000000            7.000000000000000              X( 4, 2)        0.000000000000000            8.000000000000000              X( 4, 3)        1.000000000000000            11.00000000000000              X( 4, 4)        0.000000000000000            9.000000000000000                   Row             Slack or Surplus               Dual Price                     1        28.00000000000000           -1.000000000000000                     2        0.000000000000000            0.000000000000000                     3        0.000000000000000            0.000000000000000                     4        0.000000000000000            0.000000000000000                     5        0.000000000000000            0.000000000000000                     6        0.000000000000000            0.000000000000000                     7        0.000000000000000            0.000000000000000                     8        0.000000000000000            0.000000000000000                     9        0.000000000000000            0.000000000000000

    5. Mathematica求解

    首先进行初始化:

    mat = Table[Subscript[a, i, j], {i, 1, 4}, {j, 1, 4}];Cmat = {{2, 15, 13, 4}, {10, 4, 14, 5}, {9, 14, 16, 13}, {7, 8,  11,    9}};

    之后使用Minimize函数

    Minimize[{Flatten[mat].Flatten[Cmat],   Table[Sum[mat[[k, i]],  {i, 1, 4}], {k, 1, 4}] == {1, 1, 1, 1},   Table[Sum[mat[[i, k]],  {i, 1, 4}], {k, 1, 4}] == {1, 1, 1, 1}}~  Join~Flatten@   Table[0 <=  Subscript[a, i, j] <= 1, {i, 1, 4}, {j, 1, 4}], Flatten[mat], Integers]

    Mathematica结果输出:

    {28, {a1.1 -> 0, a1.2 -> 0, a1.3 -> 0, a1.4 -> 1, a2.1  -> 0, a2.2 -> 1, a2.3 -> 0, a2.4 -> 0,a3.1 -> 1, a3.2 -> 0, a3.3 -> 0, a3.4 -> 0, a4.1 ->  0, a4.2 -> 0, a4.3 -> 1, a4.4 -> 0}}

    Mathematica结果列为矩阵:

    In[67]:= mat /.({28, {a1.1  -> 0, a1.2 -> 0, a1.3 -> 0, a1.4 -> 1, a2.1 -> 0, a2.2 -> 1, a2.3 -> 0, a2.4  -> 0,a3.1 -> 1,  a3.2 -> 0, a3.3 -> 0, a3.4 -> 0,a4.1 ->  0, a4.2 -> 0, a4.3 -> 1, a4.4 -> 0}} [[2]] //MatrixFormOut[67]//MatrixForm(0     0      0     1     0     1      0     0     1     0      0     0     0     0      1     0)

    6. 1stOpt求解

    1stOpt求解代码:

    Constant n=4, c(n,n)=[2,15,13,4,10,4,14,5,9,14,16,13,7,8,11,9];IntParameter x(n,n);Algorithm = LP;MinFunction Sum(i=1:n)(Sum(j=1:n)(c[i,j]*x[i,j]));             For(i=1:n)(Sum(j=1:n)(x[i,j])=1);             For(j=1:n)(Sum(i=1:n)(x[i,j])=1);

    1stOpt结果输出:

    Objective Function(Min.): 28Best Estimated Parameters:x[1,1]: 0x[1,2]: 0x[1,3]: 0x[1,4]: 1x[2,1]: 0x[2,2]: 1x[2,3]: 0x[2,4]: 0x[3,1]: 1x[3,2]: 0x[3,3]: 0x[3,4]: 0x[4,1]: 0x[4,2]: 0x[4,3]: 1x[4,4]: 0

         对于指派问题,四种软件均可获得相同结果的解。

    对不同的版本的Matlab,提供了两种求解方式,第一种比较繁琐,需要进行一些转换工作才能进行求解,第二种相对简单些,两种方式都需要掌握特定命令语句;

    Lingo求解,需要熟知Lingo语言中关于集合及其属性的定义,总体上是对数学模型的直接翻译,无需复杂的转换;

    Mathematica代码简短,但命令高度抽象,生涩难懂;

    1stOpt代码最为直观简洁,与模型公式完全一样。

    本文参照知乎贴:https://www.zhihu.com/question/49319704

    展开全文
  • 已知每人完成每项任务所需时间效率矩阵C[i,j]如下。问如何分配任务,使完成所有工作所用总时间最少?例如:任务为1,2,3,4,人员为1,2,3,4,时间效率矩阵C[i,j]为:任务1任务2任务3任务4人员1215134人员...

    1. 指派问题

    n项任务要分配给n个人去做,每人只完成一项任务,每个任务也只由一个人完成。已知每人完成每项任务所需的时间效率矩阵C[i,j]如下。问如何分配任务,使完成所有工作所用的总时间最少?

    例如:任务为1234,人员为1234,时间效率矩阵C[i,j]为:

    任务1

    任务2

    任务3

    任务4

    人员1

    2

    15

    13

    4

    人员2

    10

    4

    14

    5

    人员3

    9

    14

    16

    13

    人员4

    7

    8

    11

    9

     2. 模型建立

    引入决策变量x[i,j],如果让第i个人去完成第j项任务,则x[i,j] =1,否则x[i,j] = 0,则指派问题的数学模型为:

    ecbd4b9e9e5d9eb8968eea6119b8924e.png

    3. Matlab求解

    MATLAB求解线性规划或混合整数规划时,决策变量只能是向量(即一维数组),所以需要把上述数学模型中的双下标常量和决策变量都转化成单下标变量,同时约束也需要进行相应的转换。最终求解代码如下。

    Matlab代码:

    f=[2,10,9,7,15,4,14,8,13,14,16,11,4,5,13,9];intcon = 1:16;Aeq=[1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1;1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1]beq = ones(8,1);lb=zeros(1,16);ub=ones(1,16);[Y,fval,exitflag] = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);x=reshape(Y,4,4)fval

    Matlab结果输出:

    ans =     0     0      0     1     0     1      0     0     1     0      0     0     0     0      1     0Fval = 28

    新版MATLAB提供了更具可读性的问题描述及解决方法。

    新版Matlab求解代码:

    c = [2 15 13 4; 10 4  14 5; 9 14 16 13; 7 8 11 9];prob =  optimproblem('ObjectiveSense', 'min');x = optimvar('x', 4,  4, 'Type', 'integer', 'LowerBound', 0, 'UpperBound', 1);prob.Objective =  sum(sum(c .* x));prob.Constraints.cond1  = sum(x, 1) == 1;prob.Constraints.cond2  = sum(x, 2) == 1;% prob.showproblemsol = prob.solve;sol.x

    Matlab结果输出:

    LP:                Optimal  objective value is 28.000000.                                           Optimal solution found.Intlinprog stopped at the root node because theobjective value is within a gap tolerance of the optimal value,options.AbsoluteGapTolerance = 0 (the default value). The intcon  variables areinteger within tolerance, options.IntegerTolerance = 1e-05 (the  default value).ans =     0     0      0     1     0     1      0     0     1     0      0     0     0     0      1     0

    4. Lingo求解

          LINGO来求解这个指派问题,只需要会建立集合及其属性,其它就基本上是对数学模型的直接翻译,无需复杂的转换。

    Lingo求解代码:

    MODEL:DATA:N = 4;ENDDATASETS:AGENTS/1..N/;TASKS/1..N/;MATRIX(AGENTS,TASKS):COST, X;ENDSETSDATA:COST =2,15,13,4,10,4,14,5,9,14,16,137,8,11,9;ENDDATAMIN = @SUM(AGENTS(I) :    @SUM(TASKS(J):  COST(I,J)*X(I,J)));@FOR(AGENTS(I):    @SUM(TASKS(J):X(I,J)) =  1);@FOR(TASKS(J):    @SUM(AGENTS(I):X(I,J)) =  1);@FOR(AGENTS(I):    @FOR(TASKS(J) :  @GIN(X(I,J))));END

    Lingo结果输出

    Global optimal solution  found.

      Objective value:                     28.00000000000000  Objective bound:                     28.00000000000000  Infeasibilities:                     0.000000000000000  Extended solver  steps:                               0  Total solver  iterations:                              0  Elapsed runtime  seconds:                          0.03  Model Class:                                      PILP  Total variables:                     16  Nonlinear variables:                  0  Integer variables:                   16  Total constraints:                    9  Nonlinear  constraints:                0  Total nonzeros:                      48  Nonlinear nonzeros:                   0              Variable                    Value                 Reduced Cost                     N        4.000000000000000            0.000000000000000           COST( 1, 1)        2.000000000000000            0.000000000000000           COST( 1, 2)        15.00000000000000            0.000000000000000           COST( 1, 3)        13.00000000000000            0.000000000000000           COST( 1, 4)        4.000000000000000            0.000000000000000           COST( 2, 1)        10.00000000000000            0.000000000000000           COST( 2, 2)        4.000000000000000            0.000000000000000           COST( 2, 3)        14.00000000000000            0.000000000000000           COST( 2, 4)        5.000000000000000            0.000000000000000           COST( 3, 1)        9.000000000000000            0.000000000000000           COST( 3, 2)        14.00000000000000            0.000000000000000           COST( 3, 3)        16.00000000000000            0.000000000000000           COST( 3, 4)        13.00000000000000            0.000000000000000           COST( 4, 1)        7.000000000000000            0.000000000000000           COST( 4, 2)        8.000000000000000            0.000000000000000           COST( 4, 3)        11.00000000000000            0.000000000000000           COST( 4, 4)        9.000000000000000            0.000000000000000              X( 1, 1)        0.000000000000000            2.000000000000000              X( 1, 2)        0.000000000000000            15.00000000000000              X( 1, 3)        0.000000000000000            13.00000000000000              X( 1, 4)        1.000000000000000            4.000000000000000              X( 2, 1)        0.000000000000000            10.00000000000000              X( 2, 2)        1.000000000000000            4.000000000000000              X( 2, 3)        0.000000000000000            14.00000000000000              X( 2, 4)        0.000000000000000            5.000000000000000              X( 3, 1)        1.000000000000000            9.000000000000000              X( 3, 2)        0.000000000000000            14.00000000000000              X( 3, 3)        0.000000000000000            16.00000000000000              X( 3, 4)        0.000000000000000            13.00000000000000              X( 4, 1)        0.000000000000000            7.000000000000000              X( 4, 2)        0.000000000000000            8.000000000000000              X( 4, 3)        1.000000000000000            11.00000000000000              X( 4, 4)        0.000000000000000            9.000000000000000                   Row             Slack or Surplus               Dual Price                     1        28.00000000000000           -1.000000000000000                     2        0.000000000000000            0.000000000000000                     3        0.000000000000000            0.000000000000000                     4        0.000000000000000            0.000000000000000                     5        0.000000000000000            0.000000000000000                     6        0.000000000000000            0.000000000000000                     7        0.000000000000000            0.000000000000000                     8        0.000000000000000            0.000000000000000                     9        0.000000000000000            0.000000000000000

    5. Mathematica求解

    首先进行初始化:

    mat = Table[Subscript[a, i, j], {i, 1, 4}, {j, 1, 4}];Cmat = {{2, 15, 13, 4}, {10, 4, 14, 5}, {9, 14, 16, 13}, {7, 8,  11,    9}};

    之后使用Minimize函数

    Minimize[{Flatten[mat].Flatten[Cmat],   Table[Sum[mat[[k, i]],  {i, 1, 4}], {k, 1, 4}] == {1, 1, 1, 1},   Table[Sum[mat[[i, k]],  {i, 1, 4}], {k, 1, 4}] == {1, 1, 1, 1}}~  Join~Flatten@   Table[0 <=  Subscript[a, i, j] <= 1, {i, 1, 4}, {j, 1, 4}], Flatten[mat], Integers]

    Mathematica结果输出:

    {28, {a1.1 -> 0, a1.2 -> 0, a1.3 -> 0, a1.4 -> 1, a2.1  -> 0, a2.2 -> 1, a2.3 -> 0, a2.4 -> 0,a3.1 -> 1, a3.2 -> 0, a3.3 -> 0, a3.4 -> 0, a4.1 ->  0, a4.2 -> 0, a4.3 -> 1, a4.4 -> 0}}

    Mathematica结果列为矩阵:

    In[67]:= mat /.({28, {a1.1  -> 0, a1.2 -> 0, a1.3 -> 0, a1.4 -> 1, a2.1 -> 0, a2.2 -> 1, a2.3 -> 0, a2.4  -> 0,a3.1 -> 1,  a3.2 -> 0, a3.3 -> 0, a3.4 -> 0,a4.1 ->  0, a4.2 -> 0, a4.3 -> 1, a4.4 -> 0}} [[2]] //MatrixFormOut[67]//MatrixForm(0     0      0     1     0     1      0     0     1     0      0     0     0     0      1     0)

    6. 1stOpt求解

    1stOpt求解代码:

    Constant n=4, c(n,n)=[2,15,13,4,10,4,14,5,9,14,16,13,7,8,11,9];IntParameter x(n,n);Algorithm = LP;MinFunction Sum(i=1:n)(Sum(j=1:n)(c[i,j]*x[i,j]));             For(i=1:n)(Sum(j=1:n)(x[i,j])=1);             For(j=1:n)(Sum(i=1:n)(x[i,j])=1);

    1stOpt结果输出:

    Objective Function(Min.): 28Best Estimated Parameters:x[1,1]: 0x[1,2]: 0x[1,3]: 0x[1,4]: 1x[2,1]: 0x[2,2]: 1x[2,3]: 0x[2,4]: 0x[3,1]: 1x[3,2]: 0x[3,3]: 0x[3,4]: 0x[4,1]: 0x[4,2]: 0x[4,3]: 1x[4,4]: 0

         对于指派问题,四种软件均可获得相同结果的解。

    对不同的版本的Matlab,提供了两种求解方式,第一种比较繁琐,需要进行一些转换工作才能进行求解,第二种相对简单些,两种方式都需要掌握特定命令语句;

    Lingo求解,需要熟知Lingo语言中关于集合及其属性的定义,总体上是对数学模型的直接翻译,无需复杂的转换;

    Mathematica代码简短,但命令高度抽象,生涩难懂;

    1stOpt代码最为直观简洁,与模型公式完全一样。

    本文参照知乎贴:https://www.zhihu.com/question/49319704

    展开全文
  • 你必须知道495个C语言问题

    千次下载 热门讨论 2015-05-08 11:09:25
    第1章 声明和初始化 基本类型 1.1 我该如何决定使用哪种整数类型? 1.2 为什么不精确定义标准类型大小?...基本内存分配问题 7.1 为什么这段代码不行?char*answer;printf("Typesomething...
  • 3.12 我不想学习那些复杂规则,怎样才能避免这些未定义求值顺序问题呢? 38 其他表达式问题 39 *3.13 ++i和i++有什么区别? 39 3.14 如果我不使用表达式值,那我应该用i++还是++i来做自增呢? 39 ...
  • 《你必须知道495个C语言问题

    热门讨论 2010-03-20 16:41:18
    你难免会遇到各种各样的问题,有些可能让你百思不得其解,甚至翻遍图书馆,也找不到问题的答案。 《你必须知道的495个C语言问题》的出版填补了这一空白。许多知识点的阐述都是其他资料中所没有的,弥足珍贵。 涵盖...
  • 你必须知道495个C语言问题(PDF)

    热门讨论 2009-09-15 10:25:47
    1.12 这样初始化有什么问题?char *p = malloc(10); 编译器提示“非 法初始式” 云云。. . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.13 以下初始化有什么区别?char a[] = "string literal"; ...
  • 1,1]^n 其中乘方运算使用 霍纳法则 第三章 蛮力法 凸包问题 链接任意两点检查剩余点是否都在连线同侧效率 O(n^3) 分配问题 n 个任务分配给 n 个人其中将第 j 个任务分配给第 i 个人成本为
  • o 2.12 这样初始化有什么问题?char *p = malloc(10); 编译器提示 ``非法初始式" 云云。 o 2.13 以下初始化有什么区别?char a[] = "string literal"; char *p = "string literal"; 当我向 p[i] 赋值时候, ...
  • 分配问题分配问题涉及将机器分配给任务,将工人分配给工作,将足球运动员分配给职位等。 目标是确定最佳分配,例如,使总成本最小化或使团队效率最大化。 分配问题是组合优化领域中一个基本问题。例如,假设我们有...

    本文介绍了匈牙利算法的计算流程和代码实现,欢迎各位抛砖。原理部分正在整理中...

    分配问题

    分配问题涉及将机器分配给任务,将工人分配给工作,将足球运动员分配给职位等。 目标是确定最佳分配,例如,使总成本最小化或使团队效率最大化。 分配问题是组合优化领域中的一个基本问题。

    例如,假设我们有四个工作需要由四个工作人员执行。 因为每个工人都有不同的技能,所以执行工作所需的时间取决于分配给它的工人。

    下面的矩阵显示了工人和工作的每种组合所需的时间(以分钟为单位)。 作业用J1,J2,J3和J4表示,工人用W1,W2,W3和W4表示。

    34278ce78e38032f698cda4258b86097.png

    每个工人应仅执行一项工作,目标是最大程度地减少执行所有工作所需的总时间。

    事实证明,将工人1分配给作业3,将工人2分配给作业2,将工人3分配给作业1,将工人4分配给作业4是最佳选择。总时间为69 + 37 + 11 + 23 = 140分钟。 所有其他任务导致需要更多时间。

    21043c60096a24eaec3310113dab56b0.png

    匈牙利算法可用于找到此最佳分配。

    匈牙利算法

    匈牙利算法是一种易于理解且易于使用的算法,可以解决分配问题。匈牙利算法包括以下四个步骤。前两个步骤执行一次,而步骤3和4重复执行,直到找到最佳分配。该算法的输入是仅包含非负元素n×n方阵

    • 步骤1:减去行最小值
      • 对于每一行,找到最低的元素,然后从该行的每个元素中减去它。
    • 步骤2:减去列最小值
      • 同样,对于每一列,找到最低的元素,然后从该列的每个元素中减去它。
    • 步骤3:用最少的行数覆盖所有零
      • 使用最少数量的水平和垂直线覆盖结果矩阵中的所有零。如果需要n行,则零之间存在最佳分配。算法停止。
      • 如果少于n行,请继续执行步骤4。
    • 步骤4:生成额外的零
      • 在步骤3中找到一条线未覆盖的最小元素(称为k)。从所有未发现的元素中减去k,然后将k添加到所有覆盖两次的元素中。

    代码实现

    sklearn里的linear_assignment()函数以及scipy里的linear_sum_assignment()函数都实现了匈牙利算法,两者的返回值的形式不同:

    import 

    参考

    An Assignment Problem solved using the Hungarian Algorithmwww.hungarianalgorithm.com求索:目标跟踪初探(DeepSORT)zhuanlan.zhihu.com
    f2742bb164c5c566c4f17bae204d5b19.png
    展开全文
  • 当 任务矩阵Tasks和节点矩阵Nodes确定下来之后,那么所有任务分配给所有节点任务处理时间都可以确定了,我们用矩阵timeMatrix表示,它是一个二维数组: 1 2 2 4 3 6 4 8 timeMatrix[i][j]表示将任务i分配给节点...
  • 第二章 算法效率分析基础2.5 计算斐波那契数列O(log n)算法:利用矩阵, 当 n >= 1时, [F(n-1), F(n);...效率O(n^3)分配问题:n个任务分配给n个人,其中将第j个任务分配给第i个人成本为C[i,j],找出成...
  • 然后我们在GPU上完毕了这个程序,当然是非常单纯任务分配给各个线程。也没有经过优化。终于我们看到,执行效率相当低下,可是更重要是出现了一个我们之前做整数立方和没遇到的问题,那就是浮点数精度损失...
  • excel使用

    2012-11-25 17:06:01
    #_k"克"” 可以看到,使用条件格式,千分符和均匀间隔指示符组合,不用增加公式数目就可以改进工作表可读性和效率。另外,我们还可以运用自定义格式来达到隐藏输入数据目的,比如格式";##;0"只显示...
  • 2.5 集群计算算法的效率问题 2.5.1 集群计算的通信开销模型 2.5.2 实耗通信开销 2.5.3 多路连接 2.5.4 习题 2.6 小结 2.7 参考文献 第3章 相似项发现 3.1 近邻搜索的应用 3.1.1 集合的Jaccard相似度 3.1.2...
  • 2.5 集群计算算法的效率问题 2.5.1 集群计算的通信开销模型 2.5.2 实耗通信开销 2.5.3 多路连接 2.5.4 习题 2.6 小结 2.7 参考文献 第3章 相似项发现 3.1 近邻搜索的应用 3.1.1 集合的Jaccard相似度 3.1.2...
  • 10.2.4 指针变量几个问题的进一步说明 140 810.3 数组指针和指向数组的指针变量 141 10.3.1 指向数组元素的指针 142 10.3.2 通过指针引用数组元素 143 10.3.3 数组名作函数参数 146 10.3.4 指向多维数组的指针和指针...
  • 10.2.4 指针变量几个问题的进一步说明 140 810.3 数组指针和指向数组的指针变量 141 10.3.1 指向数组元素的指针 142 10.3.2 通过指针引用数组元素 143 10.3.3 数组名作函数参数 146 10.3.4 指向多维数组的指针和指针...

空空如也

空空如也

1 2
收藏数 40
精华内容 16
关键字:

任务分配问题的效率矩阵