線形計画法を拡大係数行列を使って解く方法をコンテナ積載率を例に解説
線形計画法とは？
線形計画法とはOR（オペレーションズ・リサーチ）という学問分野の１つの手法で、例えば次のような制約条件付き最適化問題を解くことができます。
―――――――――――――――――――――――――――――
容積勝ちの商品Aと、重量勝ちの商品Bがあります。
商品A
１箱の重量：12kg
１箱の容積：0.05m3
比重：240kg/m3
売値：2,500円／箱
商品B
１箱の重量：10kg
１箱の容積：0.01m3
比重：1,000kg/m3
売値：1,000円／箱
これらの商品をコンテナに積めて輸出しようとしています。
コンテナには容積ベースで50m3、重量ベースでは25tしか積めません。
売値の合計を最大にするには、商品AとBをそれぞれ何箱ずつ積めばよいでしょうか？
―――――――――――――――――――――――――――――
商品Aは軽くて容積勝ちの商品ですので、商品Aだけを積むとすれば
50m3÷0.05 m3／箱＝1,000箱
積めます。
売値でいうと
2,500円／箱×1,000箱＝2,500,000円
です。
一方、商品Bは重くて重量勝ちの商品ですので、商品Bだけを積むとすれば
25,000kg÷10 kg／箱＝2,500箱
積めます。
売値でいうと
1,000円／箱×2,500箱＝2,500,000円
です。
結局、どちらの場合も2,500,000円分しか積めないことになります。
このような場合、両商品を混ぜる方が多く積めることは明らかです。
しかし、それぞれ何個ずつ積むのが良いかは自明ではありません。
このような問題は物流の世界では至るところにあり、大抵は「経験と勘」で決めています。
しかし、その「経験と勘」による答えが最適とは限らず、日常の意思決定でこれが積み重なると、企業の競争力にも差が付いてきます。
ORは第二次世界大戦中に英米で大活躍しました。
例えば、輸送船を取り囲む護送船団の規模の決定にORが使われました。
英米の輸送船はドイツの潜水艦Uボートの攻撃から守るために、護送船団方式を取っていました。
この船団が進むスピードは一番遅い船のスピードに合わせる必要があるため、船団の規模が大きいほどスピードが遅くなり、潜水艦に見つかる確率も高くなります。
一方、護衛船の数を増やして船団の規模を大きくするほど、護衛し易くなります。
一見、どちらの方が効率的なのか分かりにくいのですが、被害の大きさは船団の大きさよりも、護衛船の数に比例していることがデータによって示されました。
これによって船団の最適な大きさを決めていたそうです。
この例でも、長い戦争期間中では損害額に大きな差が出てきます。
このように戦争で大きく進歩したORですが、戦後はあらゆる分野のビジネスで用いられるようになりました。
有名なところではメーカーにおける生産計画や、サービス業における待ち時間の最適化等があります。
物流では配車ソフトにおける最短経路検索問題が有名ですが、それ以外のちょっとした日常オペレーションの意思決定にも広く適用することができます。
冒頭で紹介した線形計画法は、ORの中でもメジャーな問題です。
線形計画法の問題を連立不等式で表す
冒頭の問題に戻ります。
この問題は商品Aの箱数をx、商品Bの箱数をyとすることにより、次のような最適化問題に帰着できます。
12x + 10y ≦ 25,000
0.05x + 0.01y ≦ 50
x ≧ 0、y ≧ 0
の条件下で、
2,500x + 1,000yが最大になるようなxとyを求める。
この時、2,500x + 1,000yを目的関数と呼びます。
連立不等式を連立方程式に変換する
しかし、これでは不等式が含まれているので、下記のようにs1、s2、zという新しい変数を追加して連立方程式に変えます。
12x + 10y + s1 = 25,000
0.05x + 0.01y + s2 = 50
2,500x + 1,000y = z
但し、x, y, z, s1, s2 ≧0
ちたみに、この連立方程式には変数が５個ありますが式は３つしかないため、解は１つに決まりません。
沢山ある解の組み合わせの中から、目的関数zが一番大きくなる解の組み合わせを求める最大化問題になります。
例えば、(x, y, z, s1, s2)=(0, 0, 0, 25000, 50)が１つの解の組み合わせになりますが、これではzが０ですね。
もっとzが大きくなるような解の組み合わせを求めたいということです。
線形計画法における拡大係数行列への目的関数の入れ方
ここで掃き出し法による連立方程式の解き方を復習しておきます。
例えば、
2x + 3y = 19
8x + 6y = 46
という連立方程式を解くために、まずは下記のような拡大係数行列を定義しました。
そしてこの行列を下記のように行基本変形します。
すると、右側に計算された２と５が、それぞれxとyの答えになるというものでした。
詳しくはこちらを参照して下さい。
掃き出し法を使って連立方程式が解けて、逆行列も計算できる理由をわかりやすく
次に、この連立方程式にx+y=zを付け加えます。
つまり、
2x + 3y = 19
8x + 6y = 46
x + y = z
の連立方程式をx、y、zについて解くのです。
x + y = zを移項してz – x -y = 0のように書き直すと、拡大係数行列は次のようになります。
そして、これを行基本変形すると次のようになります。
拡大係数行列を元の連立方程式に戻すと次のようになり、x、y、zの答えが求まります。
このz=7というのはx=2とy=5が求まれば自動的に求まるのですが、上のようにあえてzを第三の変数として導入しても同じように計算することができます。
線形計画法には目的関数がありますが、この目的関数をzとして拡大係数行列に加える点が、少しだけ普通の連立方程式と異なる点です。
掃き出し法で連立方程式を解く
それでは冒頭の線形計画法の問題を掃き出し法で解くために、まずは拡大係数行列を作ります。
（２式目は係数の値が小さすぎて計算しにくいので、両辺を１００倍しています）
後は、この行列を下記のような形になるように行基本変形すれば、一番右の列にx、y、zの値が計算されるはずです。
これは、先ほどの「必要な前知識」の章で見た通りです。
それでは行基本変形をやっていきましょう。
下記のようになります。
これで最適解が求まりました。
x=657、y=1,710、z=3,352,500なので、商品Aを657箱、商品Bを1,710箱コンテナに積めば、その時の合計商品価格は3,352,500円となり、これが最大に積める商品価格になります。
最適解は制約条件で囲まれる図形の頂点
これをグラフに描くと、次のようになります。
２つの制約条件は青色の２本の直線の下側とx軸、y軸で囲まれた四角形の内側になります。
一方、最大化する目的関数は赤色の点線です。
この目的関数の傾きは決まっていますが（-2.5）、y切片は目的関数の値で決まるため決まっていません。
この目的関数が座標（0,0）を通る位置にある場合には、目的関数の値は０です。
この目的関数の直線を、制約条件の四角形に接するギリギリまで上に平行移動すると、その時の目的関数の値は3,352,500になります。
これが、まさしく先ほどの連立方程式で求めたzに相当します。
このように見てみると、わざわざ連立方程式にして掃き出し法で求める方が面倒くさいやり方に思えるかもしれません。
しかし、これは制約条件が２つしかないためグラフで簡単に表すことができますが、制約条件が増えてくるとそうはいきません。
実務ではこの制約条件が数百、数千に上ることも珍しくはなく、やはり行列を使って機械的に計算しないと無理なのです。
おまけ：シンプレックス法とは？
この例題では制約条件を表す領域が四角形で、頂点が４つしかありません。（最適解は頂点のどこかにあります）
このくらい単純な制約条件であれば、どのように行基本変形しても簡単に最適解に辿り着くことができます。
しかし制約条件が増えてくるとこの頂点が無数にあり、効率良く最適解のある頂点に辿り着く方法が必要になります。
そのために、どういう順番で行基本変形をしていけば良いかを教えてくれるのが有名なシンプレックス法のアルゴリズムです。
これについてはこちらで解説しています。
【線形計画法②】シンプレックス法でトラックの積載率が最大になる条件を求めてみた