トピックス 数学

適正な生産計画を作る

投稿日:

以前の機械学習SVM(サポートベクターマシン)のブログ「識別式設定の原理」の添付資料内に「ラグランジュの緩和法 双対問題」という最適化手法を説明しましたが、この「双対問題」の意味が分からず悶々としていました。今回少し理解できてきましたので、説明します。 次の資料をご覧ください。

資料はこちら → 双対問題

p.1 「製品A及びBを製造する際に利益最大となる生産計画は?」という最適化問題です。これは「双対問題」を利用しなくとも解けるのですが、説明を簡単にするために用います。 製品AあるいはBを製造するために、原薬Aあるいはの1日に使える使用量に制限があり、製品AとBでは原薬AあるいはBの使用量及び利益が異なります。

p.2 製品AあるいはB製造量とおきます。6x+4xが最大になる条件を求めます。制限は不等式3つで表してあります。これは制限の不等式の範囲をグラフで描いてz=6x+4xの直線がこの範囲(黄色の塗り潰しエリア)に接するポイント(20)、x(30)及びz(240)になります。 先日説明したラグランジュ未定乗数法に似ていますね。

p.3 上述が変数が2つですので、2次元のグラフで簡単に描けますが、変数が多次元になると解くのが困難になります。 その場合「シンプレックス法」という解き方があります。行列を解く際の「掃き出し法(ガウスージョルダン法)」に似ています。不等式では扱いにくいので、等号にするために「スラック変数」S1、S2を加えます。6X1+4xは、未定乗数法のようにz-6x-4x=0と書き直します。左上の表がスタートです。zの行を見ると、及びマイナスなので、正の条件を満たしていません。そこで列の「2」「s」の行(①)の数値を割ります。割った結果が右上の表です。表の最右欄に計算の仕方を書いておきます。最左欄の「s」は「x」に変えます。「」(②)及び「」(③)の行は変更していません。 次は「x=1」の下にある「」や「−6」を「」にするためにの行に3を掛けて引いたり、6を掛けて足したりします。その結果が左中央の表です。 次はの「2.5」を「」にするように、「」の行の数値を2.5で割ります。その結果が、右中央の表です。 最後は、x列の「1」の上下が「0」になるように行(⑦)に0.5を掛けて引いたり、そのまま足したりして左下表になります。定数項の数値が(x1、x2、z)の解答(20、30、240)になっています。

p.4 「双対問題」にするには、①に、②にを掛けて、で整理します。左辺は6x+4xより大きいはずですので、の不等号が得られます。右辺は最小になる値を求めます

p.5 xの関連式を主問題、yの関連式を双対問題と呼びます。集合で考えると集合AとBは各々の補集合になっています。 主問題の最大値は、双対問題の最小値となります。 どちらか解きやすい方で算出していくようです。p.4のようにして双対問題の式を作成してもよいのですが、係数をご覧ください。主問題と双対問題の式の係数は、転置行列のように行と列の係数が入れ替わっています。求めたい式の係数と不等号の右にある定数項も入れ替わっています。不等号は反対になっています。 機械的に置き換えられそうです。

p.6 双対問題にして、p.3同様にシンプレックス法で計算した結果です。手順はまったく同じです。この時、「ーz」として計算していきます。得られた結果よりz=240が得られ、p.3の主問題と同じ結果が得られました。

いかがでしたか、p.5のところを見ると、次数が多くなった時は行列で対応できそうな予感がします。 とりあえず、双対問題はここまでにしておきますが、上述のような「線形計画法」を用いて最適問題を解けば、適正な生産計画を作成できるようですね。

 

-トピックス, 数学

Copyright© 進化するガラクタ , 2020 All Rights Reserved Powered by STINGER.