1

すべての要素をカバーしながら、要素の合計が最小になる最大のサブセットを見つけることができる最適なアルゴリズムを見つけようとしています。

例:- ABC が小売業者で、WXYZ が製品であると想像してください。目標は訪問を最小限に抑え、価格を下げることです。

    A    B    C
W   4    9    2  
X   1    3    4 
Y   9    3    9
Z   7    1    1 

So it appears my top two choices are 
a) B:{XYZ} - 7   C:{W} - 2
b) C:{WXZ} - 7   B:{Y} - 3 

So a) is picked because since it has a lower cost, i.e 9.

この問題は、頂点カバーやその他の線形計画法のアルゴリズムに似ているように見えますが、正しいものを見つけ出すことができません。

アップデート：

追加の変数を追加する必要があるようです。T.をご紹介します。訪問する小売業者の数が最も少なく、次に少ない小売業者の費用が > t の場合、次の前者が選択されます。 

Continuing with the example.

say t = 5,

The largest subset containing all elements would be B:{WXYZ} with a cost of 16. 
The next largest subset(s) is B:{XYZ} - 7   C:{W} - 2 with a cost of 9. 

t = 16 - 9 > 5. So we pick B:{XYZ} - 7   C:{W} - 2 

but if we did A:{X}, B:{Y}, C:{WZ} - 5, t = 9 - 5 < 5. 

So B:{XYZ} - 7   C:{W} - 2 is picked

このパターンに適合するアルゴリズムが既に存在するかどうか、本当に興味があります。この種の最適化を必要とする最初の人になることはできません。

4

1 に答える 1

1

1. 製品の総低コストを最小化することと、2. 訪問する店舗の数を最小化することの 2 つの目的に問題があります。(@btilly によるコメントは、2 つの競合するソリューションを正しく示しています。)

これらの種類の整数計画問題では、複数の目的がかなり一般的です。MCDM を参照してください。これを解決するには、2種類のコストが必要です (現在は 1 つしかありません)。

  1. (指定した) 小売業者 r から製品 p を購入するコストC_rp
  2. 小売店を訪問する費用:C_r

直感: C_r が非常に高い場合、すべての製品を 1 つの小売業者から購入します。C_r が小さい場合は、複数の小売店に行き、最も安価に販売している小売店から購入します。

あなたの問題は、「代入問題」の変形としてモデル化できます。fixed-charge transportation problemsまた、さらに参照が必要な場合は、いわゆる(FCTP) を参照してください。（1回の販売店訪問には定額料金がかかります。）

整数計画法の定式化に進みます。

決定変数

  Binary
  X_rp = if product p is purchased from retailer r, 0 otherwise 
  Y_r = 1 if retailer r is visited, 0 otherwise

目的関数

 Min C_rp X_rp + C_r Y_r

制約 

(Sum over r) X_rp = 1 for all p (Every product must be bought from some retailer)

次に、その小売業者の X_rp の 1 つでも 1 である場合、Y_r が 1 であることを確認する必要があります。通常は Big M 法を使用しますが、この問題では Big M 法の方が簡単です。

X_rp <= Y_r  for all p, for all r.

X 変数のいずれかが 1 になると、Y_r が強制的に 1 になります。モデルは価格 C_r を支払います。

解決するには、任意の LP ソルバーを使用できます。良いニュースは、問題には整数性があるということです。つまり、線形計画法の解法を使用した場合でも整数解が自然に発生するということです。

それが役立つことを願っています。

于 2013-06-26T18:22:13.240 に答える