如何找到最佳和 [英] How to find the optimal sum

问题描述

想象一下这组值:

      A B C
LINE1 2 1 1
LINE2 1 4 1
LINE3 3 1 3
LINE4 6 5 4

我可以从1到3的每一行中选择一个值.如果我从特定列中选择一个值，则需要对第4行中的值求和.

I can choose one value per line from 1 to 3. If I choose a value from a specific column, I need to sum the value from line 4.

示例:

2 (LINE1, COLUMN A)
1 (LINE2, COLUMN A)
3 (LINE3, COLUMN C)

因此，当我从A列中选择值时，我需要将这两个值都与LINE 4的值相加.最终结果:

So, as I chose values from COLUMN A, I need to sum both of them with the value of LINE 4. Final result:

      A B C
LINE1 2 - -
LINE2 1 - -
LINE3 - - 3
LINE4 6 - 4 

2 + 1 + 6 = 9
3 + 4 = 7
TOTAL: 16

事实是:我需要从组合中检索较小的总数.我是在示例中随机选择数字，但是我的算法需要选择总数较小的数字.

The fact is: I need to retrieve the smaller possible total from the combination. I chose the numbers in the example randomly, but my algorithm need to choose numbers that give me the smaller total.

我认为最佳的解决方案是从C列中选择所有数字(总计:9)，但是在某些情况下，我需要从不同的列中选择数字.

I think the optimal solution is to pick all numbers from COLUMN C (TOTAL: 9), but will be situations that I need to pick numbers from different columns.

我认为这是一个优化问题，我想使用单纯形法，但是我不知道如何开始开发.

I think it is a optimization problem and I thought to use simplex but I don't know how to start the development.

谢谢！

推荐答案

这是我在GNU MathProg建模语言中使用GLPK提出的解决方案.注意:这实际上是我在MathProg中编写的第一件事，因此非常欢迎反馈.

This is the solution I came up with using GLPK in GNU MathProg modeling language. Note: This is literally the first thing I ever wrote in MathProg, so feedback is very welcome.

具体来说，我不确定链接x []和s []的方式是否有效(我更习惯于SAT CNF编码而不是ILP).

Specifically I'm not sure if the way I linked x[] and s[] is efficient (I'm more used to SAT CNF encodings than to ILP).

将代码另存为test.mod，并使用glpsol --math test.mod执行.

Save the code as test.mod and execute with glpsol --math test.mod.

set A, dimen 3;
set B, dimen 2;

set I := setof{(i,j,v) in A} i;
set J := setof{(i,j,v) in A} j;

var x{I, J}, binary;
var s{J}, binary;

s.t. lines {i in I}:
  sum{j in J} x[i, j] = 1;

s.t. rows {j in J, i in I}:
  x[i, j] <= s[j];

minimize obj:
  (sum{(i,j,v) in A} x[i, j]*v) + (sum{(j,v) in B} s[j]*v);

solve;

printf "Result:\n";
printf {(i,j,v) in A : x[i, j] == 1} " %3d %3d %5d\n", i, j, v;
printf {(j,v) in B : s[j] == 1} " --- %3d %5d\n", j, v;
printf " --- --- %5d\n", (sum{(i,j,v) in A} x[i, j]*v) + (sum{(j,v) in B} s[j]*v);
printf "\n";

data;

set A :=
# Line 1
  1 1 2
  1 2 1
  1 3 1
# Line 2
  2 1 1
  2 2 4
  2 3 1
# Line 3
  3 1 3
  3 2 1
  3 3 3;

set B :=
# Line 4
  1 6
  2 5
  3 4;

end;

感谢罗伯特(Robert)建议GLPK并在他的回答中提供了解决方案的概述.

Thanks to Robert for suggesting GLPK and providing an outline for the solution in his answer.

这篇关于如何找到最佳和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！