2

我正在尝试为目标建模。

这是分配问题的一个特例，我想最小化完成所有工作所需的工人。因此，所有工作都必须完成，但并非所有工人都必须做某事。

约束：

s.t. AllJobsHaveToBeDone {j in Jobs}:
    sum {w in Workers} WhichWorkerDoWhichJob[w,j]=1; 


s.t. JustDoWhatHeCanDo {w in Worker, j in Jobs}:
    WhichWorkerDoWhichJob[w,j] <= WhatCanHeDo[e, j];

但我就是不能尽量减少目标中的工人数量。有没有办法计算变量中实际从事工作的工人，然后最小化该变量？

我对它很新，有什么建议吗？

    set Jobs;
    set Workers;

    param WhatCanHeDo{w in Workers, j in Jobs}, binary;
    param M;

    var WhichWorkerDoWhichJob {w in Workers, j in Jobs}, binary;
    var Y{w in Workers}, binary;


    s.t. AllJobsHaveToBeDone {j in Jobs}:
    sum {w in Workers} WhichWorkerDoWhichJob[w,j]=1;

    s.t. JustDoWhatHeCanDo {w in Workers, j in Jobs}:
    WhichWorkerDoWhichJob[w,j] <= WhatCanHeDo[w, j];

    s.t. Newrule{w in Workers, j in Jobs}:
    WhichWorkerDoWhichJob[w,j] >= M * Y[w];

    minimize target: sum{w in Workers} Y[w];

    solve;


    printf "------------------------------------------\n"  ;

    #To check the values of each Y[w] -> but all will be zeros.
    for{w in Workers}
    printf "%s %s\n",w,Y[w];

    for{w in Workers, j in Jobs:
    WhichWorkerDoWhichJob[w,j]=1}
    printf "%s do %s job. \n",w,j;

    data;

    set Jobs:= j1 j2 j3 j4 j5 j6 j7 j8;
    set Workers:=w1 w2 w3 w4 w5;

    param WhatCanHeDo: j1 j2 j3 j4 j5 j6 j7 j8 :=
            w1 1 0 0 0 1 1 1 0
            w2 1 1 0 1 0 1 0 0
            w3 1 0 1 0 1 0 1 0
            w4 1 1 1 0 0 0 1 1
            w5 1 0 1 0 0 1 0 0
            ;

    param M:=10000;

    end;

有什么新的提示或建议吗？

4

2 回答 2

0

您可以按如下方式最小化工人数量

minimize NumWorkers:
  sum {w in Workers, j in Jobs} WhichWorkerDoWhichJob[w, j];

whereWhichWorkerDoWhichJob是一个二进制变量，表示1workerw是否工作j。您还需要对 进行限制WhichWorkerDoWhichJob，但这取决于问题的具体情况（一名工人是否可以做多项工作等）。

于 2015-05-29T16:27:02.503 回答
0

所以我认为有多种方法可以完成这项工作。大 M 方法很好，但在这里不是绝对必要的，因为您已经定义了二进制变量，而 glpk 可以解决由此产生的混合整数问题。

因此，对于您的示例代码的两个小改动，GLPK 给了我令人满意的结果。首先，我删除了大 M 和新规则。其次，我将二进制 Y 变量添加到您的 JustDoWhatHeCanDo 约束中：

s.t. JustDoWhatHeCanDo {w in Workers, j in Jobs}:
WhichWorkerDoWhichJob[w,j] <= WhatCanHeDo[w, j] * Y[w];

这将告诉我 w2、w3 和 w4 正在完成所有工作。

于 2015-06-19T12:38:29.403 回答