7

私はさまざまなサイズのバケツを1000個持っています。各バケツは、重さの異なる赤と青のボールで構成されています。ボールの総重量の 60% が赤いボールで、40% が青いボールであることがわかっています。各バケットには、ランダムな数のボール、ランダムな赤と青のボールの分布、およびボールの重量のランダムな分布があります。

各バケットが赤いボールの 59 ～ 61 パーセントのボール重量と、青いボールのボール重量の 39 ～ 41 パーセントで構成されるように、ボールの再分配を行う必要があります。各バケツの重量は、再配分前とまったく同じである必要がありますが、各バケツのボールの数は、以前の数と一致する必要はありません。ボールを分割することは可能ですが、各分割にはコストがかかります。

誰かがアルゴリズムの方向性を教えてくれますか?

ありがとう。

4

1 に答える 1

1

考えられる 1 つの方法は、混合整数計画問題を次のように定式化することです。他にもっと効率的な解決策があるかもしれません。

全部で R 個の赤いボールと B 個の青いボールがあり、それぞれの重みがそれぞれ r1、r2、..rR と b1、b2、...bB であるとします。

Rij は、バケット j に割り当てられた赤いボール i の割合であるとします。RBINij は 2 進数で、Rij > 0 の場合は 1、それ以外の場合は 0 です。カット数を最小限に抑えるために、できるだけ多くの Rij の 0 (および RBINij の 0) を作成したいと考えています。

同様に、Bij はバケット j に割り当てられた青いボール i の割合です。BBINij は 2 進数で、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) )
于 2013-10-01T13:53:55.820 に答える