z5フェーズ I のスラック変数とのみを持つ悲しいマスター LP から始めますz10。
minimize z5 + z10
subject to
z5 >= 1 (y5)
z10 >= 1 (y10)
z5, z10 >= 0
y5は長さ 5 のパイプを十分に切断するy10という制約、 は長さ 10 のパイプを十分に切断するという制約です。主解はz5=1, z10=1であり、最適な双対解はy5=1, y10=1です。別の見方をすると、5 パイプと 10 パイプの両方の現在の価格は 1 です。これはフェーズ I であるため、在庫には費用がかからず、在庫のパイプの長さごとにナップザック問題を解決します (従来の DP は、すべての短い長さのテーブルを生成するため)、最大の利益率は、25 パイプを 5 つの 5 パイプに分割することです。変数x5,5,5,5,5をこのタイプのカット数とします。
minimize z5 + z10
subject to
5 x5,5,5,5,5 + z5 >= 1 (y5)
z10 >= 1 (y10)
x5,5,5,5,5, z5, z10 >= 0
現在、最適な主解はx5,5,5,5,5=0.2, z5=0, z10=1です。5 本のパイプの価格は 0 で、10 本のパイプの価格は 1 です。現在の価格での最適なパターンはx10,10(無駄 5) とx10,10,5です。ムダにならないようにしましょう。
minimize z5 + z10
subject to
5 x5,5,5,5,5 + x10,10,5 + z5 >= 1 (y5)
2 x10,10,5 + z10 >= 1 (y10)
x5,5,5,5,5, x10,10,5, z5, z10 >= 0
最適主解はx5,5,5,5,5=0.1, x10,10,5=0.5, z5=0, z10=0です。すべてのスラック変数が 0 であるため、フェーズ II に進みます。
minimize 25^1.2 x5,5,5,5,5 + 25^1.2 x10,10,5
subject to
5 x5,5,5,5,5 + x10,10,5 >= 1 (y5)
2 x10,10,5 >= 1 (y10)
x5,5,5,5,5, x10,10,5 >= 0
これがデュアルプログラムです。
maximize y5 + y10
subject to
5 y5 <= 25^1.2
y5 + 2 y10 <= 25^1.2
y5, y10 >= 0
最適主解はまだx5,5,5,5,5=0.1, x10,10,5=0.5です。最適な双対解はy5=25^1.2 * 0.2(約 9.5) とy10=25^1.2 * 0.4(約 19.0) です。フェーズ II であるため、12 パイプのコストは 12^1.2 (約 19.7) になり、25 パイプのコストは 25^1.2 (約 47.6) になります。12 本のパイプをカットして 2 本を無駄にすると、コストは 12^1.2 - 2^1.2 (約 17.4) になります。
現在、25 パイプをカットしても利益はありません。ただし、12 パイプを切断する場合、5 パイプを 2 つまたは 10 パイプを 1 つ得るために、約 17.4 を費やします。いずれにせよ、現在の合計価格は約 19.0 で、プラスの利益を意味します。x5,5=0.5, x10=1縦棒の 1 つを入れてもう一度解いてみるのですが、疲れてきたので、最終的な最適原始値は(12 パイプの両方のカット) であることを簡単にお伝えします。
このソリューションは部分的に最適ですが、顧客が文字通り 1 つの 5 パイプと 10 パイプを正確に望んでいる場合は、さらに検討する必要があることに注意してください。実際、顧客が各パイプの数を奇数にしたい場合に限り、LP ソリューション以上の無駄がありますが、顧客の総需要に関係なく、無駄は多くても 5 パイプ 1 つです。この答えは「ほぼ最適」です。