0

输入数据

管道或类似库存的东西（长度=库存数量）：

pipe3m = 4 pc  
pipe4m = 1 pc  
pipe5m = 1 pc

需要定制（长度=数量）

cut2m = 4pc  
cut2.5m = 1pc

结果：考虑到库存的剩余数量，实现最少残留量的最佳管道

pipe4m 1pc => cut2m + cut2m => remains 0m (4-2-2)  
pipe5m 1pc => cut2m + cut2.5m => remains 0.5m (5 - 2 - 2.5)  
pipe3m 1pc => cut2m => remains 1m (3-2)

所以我们需要：

pipe4m => 1pc *(if we have 2 pc of pipe4m on stock we can cut it into 2m+2m, but there is only 1)*  
pipe5m => 1pc  
pipe3m => 1pc

我怎样才能为此实现一些最佳算法？
会有5-10个管道长度和10-20个切割，所以我认为它不能用蛮力解决，但我不是算法大师。

谢谢 ：）

4

1 回答 1

2

较小的实例可以通过混合整数线性规划来解决。这是 MiniZinc 中使用问题数据的实现。可用管道已重新排列为平面阵列pipeLength。在模型x中表示每个管道的切口，并z表示是否使用管道。

int: nPipes = 6;
int: nCuts = 2;

set of int: PIPE = 1..nPipes;
set of int: CUT = 1..nCuts;

array[PIPE] of float: pipeLength = [3, 3, 3, 3, 4, 5];
array[CUT] of int: cutQuantity = [4, 1];
array[CUT] of float: cutLength = [2, 2.5];
    
array[PIPE, CUT] of var 0..10: x;
array[PIPE] of var 0..1: z;

% required cuts constraint
constraint forall(k in CUT)
    (sum(i in PIPE)(x[i,k]) = cutQuantity[k]);

% available pipes constraint
constraint forall(i in PIPE)
    (sum(k in CUT)(cutLength[k]*x[i,k]) <= pipeLength[i]);

% pipe used constraint
constraint forall(i in PIPE)
    (max(cutQuantity)*z[i] >= sum(k in CUT)(x[i,k]));

var float: loss = sum(i in PIPE)(pipeLength[i]*z[i] - sum(k in CUT)(cutLength[k]*x[i,k]));

solve minimize loss;

output ["loss=\(show_float(2, 2, loss))\n"] ++
["pipeCuts="] ++ [show2d(x)] ++
["usePipe="] ++ [show(z)];

运行给出：

loss="1.50"
pipeCuts=[| 0, 0 |
   0, 0 |
   0, 0 |
   0, 1 |
   2, 0 |
   2, 0 |]
usePipe=[0, 0, 0, 1, 1, 1]

相同的 MILP 模型也可以在例如 PuLP 中实现。

于 2021-02-19T07:49:11.147 回答