2

私がパン屋で、限られた量の材料で生産できるパイの数を最大化しようとしていると想像してください。

次の各パイ レシピA, B, C, and Dは、正確に 1 つのパイを生成します。

A = i + j + k
B = t + z
C = 2z
D = 2j + 2k

※上記のように、レシピは必ず直線になります。

私は次の成分を持っています：

4 of i
5 of z
4 of j
2 of k
1 of t

限られた量の材料を使用して、パイの生産を最大化するアルゴリズムが必要です。

これらの入力例の最適解は、次の量のパイを生成します。

2 x A
1 x B
2 x C
0 x D
= a total of 5 pies

これは、すべての組み合わせの中で最大の生産者を求めることで簡単に解決できますが、材料の量が増えると、組み合わせの数が法外なものになります。このタイプの最適化問題の一般化が必要なように感じますが、どこから始めればよいかわかりません。

私はパイ全体を焼くことしかできませんが、整数以外の結果を生成する可能性のある方法を見たいと思っています。

4

2 に答える 2

3

線形計画問題を定義できます。例で使用法を示しますが、もちろん、任意のデータに一般化できます。

パイを変数 (x1 = A、x2 = B、...) として表すと、LP 問題は次のようになります。

maximize x1 + x2 + x3 + x4
s.t. x1 <= 4  (needed i's)
     x1 + 2x4 <= 4 (needed j's)
     x1 + 2x4 <= 2 (needed k's)
     x2 <= 1 (needed t's)
     x2 + 2x3 <= 5 (needed z's)
and x1,x2,x3,x4 >= 0

この問題の分数解は多項式で解くことができますが、整数線形計画法は NP 完全です。

問題は確かにNP-Completeです。整数線形計画問題が与えられた場合、同じアプローチを使用して問題を「パイの数を最大化する」ように減らすことができるためです。ここで、各制約はパイの成分であり、変数はの数ですパイ。

整数の問題の場合 - 「特定の境界に近づく」ことができる場合 (たとえば、局所比率法や主双対法がよく使用される場合)、または必要な場合は、問題の文献に多くの近似法があります。正確な解 - 指数解はおそらくあなたのベストショットです。(もちろん、P=NPの場合を除きます)

于 2012-10-24T23:05:44.413 に答える
1

すべての関数が線形であるため、線形計画法(連続値が許容される場合) または整数計画法(変数を整数にする必要がある場合)のいずれかを探しているように思えます。

線形計画法は標準的な手法であり、効率的に解くことができます。これを行う従来のアルゴリズムはシンプレックス法です。

整数計画法は一般に扱いにくいです。なぜなら、整数制約を追加することで扱いにくい組み合わせ問題を記述できるからです。多数の近似手法があるようですが (たとえば、通常の線形計画法を使用して何が得られるかを確認することもできます)、もちろん問題の特定の性質によって異なります。

于 2012-10-24T23:09:52.070 に答える