0

この緩和をどのように計算するか。それを見つけるために何を知っておくべきですか。n 個のアイテムと m 個のナップサックがあるとします。そこで、m緩和の数を知りたいと思いました。誰かが少なくとも私にいくつかのアイデアを与えることができますか. しばらく探していました。インターネット上にいくつかの記事がありますが、あまり明確ではありません。少なくとも誰かが私にこのことを読むべきだと言ってください、あなたはこのことを知っておくべきです.

ありがとうございました

4

1 に答える 1

1

あなたの本当の質問は「線形緩和ナップザック問題の正確な定義は何ですか?」だと思うので、そうであると仮定して答えます。

簡単に言うと、線形緩和KP は 0-1 KP の分数バージョンです [1]。

数学的には、「x_i は {0, 1} セットに属する」という制限を変換し、それを「x_i は 0 と 1 の間の実数でなければならない」に変換するだけです。ここで、x_i は i- の量です。ソリューション バックパックの th アイテム。

この名前は、0-1 KP が整数計画問題であるという事実に由来しています。「線形」という用語は、解変数が連続値を想定できることを意味します。

ただし、すべてのリラクゼーションが直線的であるとは限りません。このウィキペディアのページをチェックしてみてください。

[1] http://en.wikipedia.org/wiki/Linear_programming_relaxation

于 2011-06-23T13:17:21.620 に答える