以前の機械学習ＳＶＭ（サポートベクターマシン）のブログ「識別式設定の原理」の添付資料内に「ラグランジュの緩和法 双対問題」という最適化手法を説明しましたが、この「双対問題」の意味が分からず悶々としていました。今回少し理解できてきましたので、説明します。 次の資料をご覧ください。
資料はこちら → 双対問題
p.1 「製品A及びBを製造する際に利益最大となる生産計画は？」という最適化問題です。これは「双対問題」を利用しなくとも解けるのですが、説明を簡単にするために用います。 製品ＡあるいはＢを製造するために、原薬ＡあるいはＢの１日に使える使用量に制限があり、製品ＡとＢでは原薬ＡあるいはＢの使用量及び利益が異なります。
p.2 製品AあるいはBの製造量をｘ１とｘ２とおきます。６ｘ１+４ｘ２が最大になる条件を求めます。制限は不等式３つで表してあります。これは制限の不等式の範囲をグラフで描いて、ｚ＝６ｘ１+４ｘ２の直線がこの範囲（黄色の塗り潰しエリア）に接するポイントのｘ１（20）、ｘ２（30）及びｚ（240）が解になります。 先日説明したラグランジュ未定乗数法に似ていますね。
p.3 上述が変数が２つですので、2次元のグラフで簡単に描けますが、変数が多次元になると解くのが困難になります。 その場合「シンプレックス法」という解き方があります。行列を解く際の「掃き出し法（ガウスージョルダン法）」に似ています。不等式では扱いにくいので、等号にするために「スラック変数」S1、S2を加えます。６X1+４ｘ２は、未定乗数法のようにｚ－６ｘ１－４ｘ２＝０と書き直します。左上の表がスタートです。ｚの行を見ると、ｘ１及びｘ２がマイナスなので、正の条件を満たしていません。そこでｘ１列の「２」で「ｓ１」の行（①）の数値を割ります。割った結果が右上の表です。表の最右欄に計算の仕方を書いておきます。最左欄の「ｓ１」は「ｘ１」に変えます。「ｓ２」（②）及び「ｚ」（③）の行は変更していません。 次は「ｘ１＝１」の下にある「３」や「−６」を「０」にするためにｘ１の行に３を掛けて引いたり、６を掛けて足したりします。その結果が左中央の表です。 次はｘ２列の「2.5」を「１」にするように、「ｓ２」の行の数値を2.5で割ります。その結果が、右中央の表です。 最後は、ｘ２列の「１」の上下が「０」になるようにｘ２行（⑦）に0.5を掛けて引いたり、そのまま足したりして左下表になります。定数項の数値が（ｘ１、ｘ２、ｚ）の解答（20、30、240）になっています。
p.4 「双対問題」にするには、①にｙ１、②にｙ２を掛けて、ｘ１とｘ２で整理します。左辺は６ｘ１＋４ｘ２より大きいはずですので、ｙ１とｙ２の不等号が得られます。右辺は最小になる値を求めます。
p.5 ｘの関連式を主問題、ｙの関連式を双対問題と呼びます。集合で考えると集合AとBは各々の補集合になっています。 主問題の最大値は、双対問題の最小値となります。 どちらか解きやすい方で算出していくようです。p.4のようにして双対問題の式を作成してもよいのですが、係数をご覧ください。主問題と双対問題の式の係数は、転置行列のように行と列の係数が入れ替わっています。求めたい式の係数と不等号の右にある定数項も入れ替わっています。不等号は反対になっています。 機械的に置き換えられそうです。
p.6 双対問題にして、p.3同様にシンプレックス法で計算した結果です。手順はまったく同じです。この時、「ーｚ」として計算していきます。得られた結果よりｚ＝240が得られ、p.3の主問題と同じ結果が得られました。
いかがでしたか、p.5のところを見ると、次数が多くなった時は行列で対応できそうな予感がします。 とりあえず、双対問題はここまでにしておきますが、上述のような「線形計画法」を用いて最適問題を解けば、適正な生産計画を作成できるようですね。