再分配算法

Question

我有一千个不同大小的水桶.每个桶由不同重量的红色和蓝色球组成.我知道60%的球重来自红球,40%来自蓝球.每个桶都有一个随机数量的球,一个随机分布的红色和蓝色球,以及随机分配的球重量.

我需要对球进行重新分配,因此每个球桶由红球的59-61%球重和蓝球的39-41%球重组成.每个铲斗应具有与重新分配之前完全相同的重量,但每个铲斗中的球数不必与之前的数量相匹配.分割球是可能的,但每次分割都有成本.

有人能指出我的算法方向吗？

谢谢.

Answer 1

一种可能的方法是按以下方式制定混合整数规划问题。我不确定，可能还有其他更有效的解决方案。

假设总共有 R 个红球和 B 个蓝球，每个球的重量分别为 r1、r2、..rR 和 b1、b2、...bB。

假设 Rij 是分配给桶 j 的红球 i 的分数。RBINij 是一个二进制数，如果 Rij > 0，则为 1，否则为 0。我们希望尽可能多地生成 Rij 的 0（和 RBINij 的 0），以实现最少的切割次数。

类似地，Bij 是分配给桶 j 的蓝色球 i 的分数。BBINij 是一个二进制数，如果 Bij > 0，则为 1，否则为 0。我们希望尽可能多地生成 Bij 的 0（和 BBINij 的 0），以实现最少的切割次数。

Constraints:
summation over i( wi*Rij ) <= 1.564*summation over i( wi*Bij ) (61-39 ratio) { for all j buckets }
summation over i( wi*Rij ) >= 1.439*summation over i( wi*Bij ) (59-41 ratio) { for all j buckets }
RBINij >= Rij
BBINij >= Bij
+ maybe more constraints like the total weight etc.

Objective Function:
Minimize( Ci*summation over i(RBINij + BBINij) )