質問

金属製品工場の話です。長い鉄の棒を細かく切断してさまざまな製品を作る機械があります。

たとえば、次の長さと数量のバーを作成する必要があるとします。248mmの2枚、1150mmの5つ、2843mmの6つ、3621mmの3つ。

それがパーティショニング出力です。

入力側には、（たとえば）2500mmの3バー、5000mmの2 bar、8000mmの6バー、10000mmの3 barがあります。

入力バーを最適にカットする方法を見つける必要があります。カット後の残り（小さすぎて使用できない残りの部分）はできるだけ小さくする必要があります。

私は、考えられるすべての組み合わせを単純に作成し、その中から最適なものを選択するアルゴリズムを作成しました。コードは機能しますが、入力と出力が少し大きくなると、計算が非常に長く続く可能性があるため、問題に対する新しいアプローチを見つける必要があります。

何かヒントはありますか？

役に立ちましたか？

解決

あなたの問題は、オペレーションズ リサーチでは非常に一般的な問題です。見るカット在庫の問題. 。あなたが自分で考え出したように、この問題は本質的に NP 困難です。スケールがあまり良くありません。

どうすれば解決できますか？モデルを理解できたら、混合整数計画法ソルバーを呼び出すのが最善です。以前に使用したことがある LPソルブ5.5

特にこの問題に対処するためにコード化できる、より単純なアルゴリズムがあるかもしれません。これらのアルゴリズムの問​​題は通常、作成者が思いつかなかったいくつかの側面制約を追加する必要があるときに発生します。MIP ソルバーは、より汎用的なツールです。

他のヒント

これは、可変サイズのビンのパッキング問題と呼ばれます。これはNPハードです。つまり、入力が大きい場合、ソリューションは必ず失敗します。この記事、こちらは、残念ながら私もアクセスできません。アドレスこの問題は、例として金属切削産業を使用しています。

線形プログラミングはあなたの友人です。一般的に、特に、 http://en.wikipedia.org/wiki/Linear_programming を参照してください。 、 http://en.wikipedia.org/wiki/Linear_programming#Uses 、< a href = "http://en.wikipedia.org/wiki/Linear_programming#Algorithms" rel = "nofollow noreferrer"> http://en.wikipedia.org/wiki/Linear_programming#Algorithms 。

>

ナップザック問題（本当に厄介なことを知っている）に似ているようです.nist.gov / div897 / sqg / dads / HTML / binpacking.html "rel =" nofollow noreferrer ">ビン詰め

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top