1

デカルト積を計算するためのより良い方法はありますか？デカルト積は特殊なケースであるため、ケースごとに異なります。何を達成する必要があるのか​​、なぜデカルト積を実行するのかを説明する必要があると思います。デカルト積が私の問題の唯一の解決策である場合は、私を助けてください。もしそうなら、どのようにパフォーマンスを向上させるのですか？

バックグラウンド：

私たちは、お客様がより安く製品を購入できるように支援しようとしています。

顧客が5つの製品（prod1、prod2、prod3、prod4、prod5）を注文したとします。

注文した各製品は、さまざまなベンダーから提供されています。

表現形式1：

  • ベンダー1-prod1、prod2、prod4を提供します
  • ベンダー2-prod1、prod5を提供します
  • ベンダー3-prod1、prod2、prod5を提供
  • ベンダー4-prod1を提供
  • ベンダー5-prod2を提供
  • ベンダー6-prod3、prod4を提供

言い換えると

表現形式2：

  • 製品1-vendor1、vendor2、vendor3、vendor4によって提供されます
  • 製品2-vendor5、vendor3、vendor1によって提供されます
  • prod3-vendor6が提供
  • 製品4-vendor1、vendor6によって提供されます
  • 製品5-vendor3、vendor2によって提供されます

次に、価格に基づいて最適なベンダーを選択します。価格で商品を並べ替えて、最初の商品を購入することができます。

その場合、

  • ベンダー1の製品1
  • ベンダー5の製品2
  • ベンダー6の製品3
  • ベンダー1の製品4
  • ベンダー3の製品5

複雑：

4つのユニークなベンダーを選んだので、4つの送料を支払う必要があります。

また、各ベンダーには最小の発注書があります。それを満たさない場合は、その料金も支払うことになります。

製品の最適な組み合わせを選択するには、提供された製品のデカルト積を使用して合計価格を計算する必要があります。

total price computation algorithm:

foreach unique vendor 
if (sum (product price offered by specific vendor * quantity) < minimum purchase order limit specified by specific vendor)
totalprice += sum (product price * quantity) + minimum purchase charge + shipping price
else
totalprice += sum (product price * quantity) + shipping price
end foreach

私たちの場合には

  • {vendor1、vendor2、vendor3、vendor4}
  • {vendor1、vendor3、vendor5}
  • {vendor6}
  • {vendor1、vendor6}
  • {vendor2、vendor3}

4 * 3 * 1 * 2 * 2 = 48の組み合わせを計算して、最適な組み合わせを見つける必要があります。

  • {vendor1、vendor1、vendor6、vendor1、vendor2} = totalprice1
  • {vendor1、vendor3、vendor6、vendor1、vendor2} = totalprice2、
    • *
  • {vendor4、vendor5、vendor6、vendor6、vendor3} = totalprice48

次に、計算された合計価格を並べ替えて、最適な組み合わせを見つけます。

実際の問題：

顧客が15を超える製品を注文し、各製品が8つの固有のベンダーによって提供されていると仮定すると、8 ^ 15 = 35184372088832の組み合わせを計算することになり、数時間以上かかります。顧客が20を超える製品を注文した場合、数日以上かかります。

この問題に別の角度で取り組むための解決策はありますか？

4

1 に答える 1

1

問題はさらに複雑になる可能性があります。簡単な例:

   Product   1     2     3
Vendor 1    10    20    40
Vendor 2    20    10    40
--------------------------
needed cnt 100   100    25

100エルが必要です。P1 の 100、P2 の 100、および P3 の 25。

P1 は V1 で 1000 で、P2 は V2 で 1000 で、P3 は V1 または V3 で 1000 で購入できます。

1500 で購入した場合、送料は無料になりますが、他のベンダーでは 200 かかります。

したがって、V1 ですべてを注文すると、4000を支払うことになります。

1000+2000+1000+0 (shipping) = or for the same sum   
2000+1000+1000+0 at V2, or splitted

1000+0+0+200  = 1200 at V1 plus 
0+1000+1000+0 = 2000 at V2,

これは合計で3200になり、あなたの方法で見つけることができます。

ただし、製品 3 の購入を次のように分割できます。

1000+0+500+0 = 1500 at V1 plus 
0+1000+500+0 = 1500 at V2

これは3000までしか合計されず、あなたの方法では見つかりません。

確かに、そのようなトピックには確立された研究があり、キーワードは行列と連立方程式です。

あなたの問題を次のように説明できます

f(c11, p11) + f(c22, p12) + f(c13, p13) = c1 => dc1
f(c21, p21) + f(c22, p22) + f(c23, p23) = c2 => dc2
...
f(c31, p31) + f(c32, p32) + f(c13, p33) = c3 => dc3

ここで、cij はベンダー i での製品 j の個数、pij はベンダー i での製品 j の価格ですが、f(c11,p11) は単に個数 * 価格ではなく、個数と価格の関数です。数量割引。右側はベンダー i の購入合計です。

これは、上にモデル化する必要がある購入割引なしです。配送料の割引が総コストのみに依存する場合は、ci => dci からモデル化できます。

合計 (dc1+dc2+...+dcm) を最小化しようとします。

于 2012-04-26T09:00:22.620 に答える