【線型計画法】問題を線型計画法の問題に分離、数式化

塗料の無駄を削減するためライン改善を行っています。前回にこの無駄が数値化ができたから、製品の様々なグループ分けのなかで最適なグループ分けが検出が可能です。いくつかのテクニックが使えそうですが、最適化問題にもなるためなんとなく線型計画法が使えるかもしれないと思いました。続いて、まず問題を分割し、制約の数式化を行う必要があります。

問題の分離

製品を塗装するときに横幅（①）、上限位置（②）、塗装長さ（③）の3つのパラメータがあり、これらのパラメータごとに無駄が最も少ないグルーピングを探します。グルーピングを同時に決めて、総合的に評価するとかなり大変な作業になりますが、もしパラメータの最適なグルーピングを1つずつ見つけて固定することができれば、既に決めたグルーピングの定義を次のパラメータグルーピングの最適化に使えるから、まずはパラメータごとにグルーピングを決める方法を検討します。方針が決まったから、今度は最小にしたい無駄の定義に対して各パラメータの影響を確認します。

パラメータで問題分離を検討する

縦軸に上限位置、塗装長さの2つのパラメータが関わることに対し、横軸に横幅のパラメータだけになるためまずはそちらから攻めた方が簡単そうです。横幅の設定を評価するため、製品の横幅より広くなる部分（上の図の黄色い領域）の無駄を最低限になる設定を採用したいです。

残りのパラメータグルーピングを決める順番は自然と決定されます。上限位置が分からないと塗装範囲内に入ってしまうハンガーの部分が分からないため、塗装長さを決めた状態でないと上限位置が決めれなくなる可能性があります。そのため、先に上限位置のパラメータを製品の上の部分（上の図の赤いとオレンジの領域）の無駄を最低限にし、最後に塗装長さのパラメータを製品の下の部分（上の図の青いと緑の領域）の無駄を最低限にします。

数式化

問題の分離ができたので、次は横幅パラメータのグルーピングを線型計画法で決定するための変数と制約関数、最適化したい表現を考える必要があります。最適化したい表現にどんな変数を定義しなければならないことを考えながら、その変数の関係を制御するための関数を洗い出します。

まず、最適化したい値は先ほど話に出いているの塗料の無駄になります。つまり、製品に該当する横幅設定と実際の製品横の差を計算して製品の長さと掛けると横幅パラメータによりその製品を塗装する際に発生する無駄がわかります。

例えば、158mm長さの製品の横幅が43mmに対して横幅グループの幅が60mmなら 2686mm²分の無駄になりますが、 80mmの横幅グループの場合、5846mm²分の無駄になります。

\begin{aligned} (60 - 43) * 158 = 2686mm^2 \\ (80 - 43) * 158 = 5846mm^2 \end{aligned}

横幅のグルーピングで発生する無駄

グループ変数定義

上の式のグループ幅を変数にして、9グループがあるためグループ1の幅を表す変数の $g_1$ からグループ9の幅を表す変数の $g_9$ まで、9つの変数を用意する考えもあるかもしれません。しかし、60mmのグループがあれば、それはグループ1なのか、グループ2なのかは特に関係ありません。また、どのグルーブがどの製品に該当するかはこの変数の値次第になってしまうため、数式がピンときません。そんな思考よりも、少なくとも自分にとってはブーリアン変数を使うことがより考えやすいです。

例えば、 $g_{60}$ を定義して、幅60mmのグループがあると $g_{60}$ の値が1、幅60mmのグループがないと $g_{60}$ の値が0になります。 20mmから200mmまでの幅を網羅するため、 $g_{20}, g_{21}, ..., g_{199}, g_{200}$ （ $\{g_i | i \in [20, 200]\}$ ）を定義します。 9グルーブが欲しので、これらの変数の中で9つが1になり、それ以外の変数が0にならないといけないので、その制御を数式で表します。

$\sum_{i=20}^{200} g_i = 9$

また、200mmのグルーブがないと200mm幅の製品が対応できないので、 $g_{200}$ が必ず存在するように数式を用意します。

$g_{200} = 1$

例えば、前回の一定幅で分けたグルーピング、 (40mm, 60mm, 80mm, 100mm, 120mm, 140mm, 160mm, 180mm, 200mm)であれば $g_{40}$ , $g_{60}$ , $g_{80}$ , $g_{100}$ , $g_{120}$ , $g_{140}$ , $g_{160}$ , $g_{180}$ , $g_{200}$ が1になり、それ以外の $g_i$ が0になります。そのため、 $g_i$ の和が9になり、 $g_{200}$ が1ので以上の数式を満たします。

ここで問題：最終的に最低限にしたい無駄を計算するために各製品に該当するグループが特定しないといけません。これらの $g$ 変数があれば、例の43mm幅の製品に該当するグループはどう特定しますか？

まずは、 $g_{43}$ が1の場合、43mmのグループがあり、ピッタリなのでそのグループが例の製品に該当します。 $g_{43}$ が0なら、今度 $g_{44}$ が1なら44mmのグループになります。逆に、 $g_{42}$ が1だとしても例の43mm幅の製品に対して幅が足りません。つまり、

$i\text{mmのグループが43mm幅の製品に該当する} \iff g_i = 1 \land (\text{且つ}) g_k = 0 \forall (\text{任意の}) k \in [43, i - 1]$
（もし $g_i$ が1 且つ任意の $[43, i - 1]$ の範囲の整数 $k$ に対して $g_k$ が0 のであれば、 $i$ mmのグループが43mm幅の製品に該当する）

例えば、結果の9グループに60mmのグループがあり（ $g_{60} = 1$ ）、 43mm、 44mm、...、 59mmのグループがない（ $g_{43} = 0, g_{44} = 0, ..., g_{59} = 0$ ）のであれば（ $g_{60} = 1 \land g_i = 0 \forall i \in [43, 59]$ ）60mmのグループが例の43mm幅の製品に該当します。代わりに $g_{80} = 1 \land g_i = 0 \forall i \in [43, 79]$ であれば、80mmのグループがあり、そのグループが例の43mm製品に該当します。

これを一般的な製品を対応するルールにすると以下になります。

$i\text{mmのグループが}j\text{mm幅の製品に該当する} \iff g_i = 1 \land g_k = 0 \forall k \in [j, i - 1]$

無駄変数定義

この思考をたどって、無駄の有無も刻んでみてはどうでしょうか。もし43mm幅の製品が60mmグループに該当すれば、43mm-60mmの無駄が発生します。これを刻むと43mm-44mmの無駄、44mm-45mmの無駄、...、58mm-59mmの無駄、59mm-60mmの無駄が発生します。逆に、グループ幅は60mmなのでそれ以上の幅を塗装しなく、60mm-200mmの無駄（60mm-61mmの無駄、...、199mm-200mmの無駄）が発生しません。

これらの無駄発生変数を定義してみましょう。43mm-44mmの無駄が発生するかどうかの変数 $m_{44}$ 、 44㎜－45㎜の無駄が発生するかどうかの変数 $m_{45}$ など、 $\{m_i | i\text{が無駄の幅}\}$ でどうでしょう。例の43mm幅の製品と60mmグループの組み合わせで考えれば、 $m_i = 1 \forall i \in [44, 60], m_j = 0 \forall j \in [61, 200]$ になるといいです。

ここで問題は気づくでしょうか？違う幅の製品を加えてみるとどうなるでしょう。

まず、20mm-43mmの無駄（20mm-21mmの無駄、...、42mm-43mmの無駄）の話は一切出てません。 43mm幅の製品のであれば、20mm-43mmは塗る部分になり無駄が発生しているわけではないので、 $m_i = 0 \forall i \in [21, 43]$ でいけるのかもしれません。でも、60mmグループが該当しない製品の場合はどうでしょう。

例えば、他に42mm幅の製品が43㎜幅の製品と同じく60mmのグループに該当すれば、その製品に対して42mm-43mmの無駄が発生し、 $m_{43}$ は1にならなければなりません。厳密言えば、この $m_i$ の変数はあくまでも最小化したい無駄の計算式のために定義しているのです。 42mm-43mmの無駄は43㎜幅の製品に発生しないため、43㎜幅の製品に対する無駄は $m_{43}$ の係数に加算されないので、これは何とかなりそうです。

しかし、70mm幅の製品があると60mmのグループに該当せず、 43幅の製品に対して70mm-71mmの無駄が発生しない（ $m_{71}=0$ ）が 70mmのグループがない限り、70mm幅の製品に対してこの無駄が発生する（ $m_{71}=1$ ）ことになります。 $m_{71}$ が同時に0でも1でもなることができないので、今の変数定義では物足りません。

こうなると、製品毎に無駄有無の変数を定義するとどうでしょう。厳密言うとこの変数は製品毎にというより製品の幅毎に定義したいと思います。そうすると、43mm幅の製品の変数を $\{m_{i, j} | i \in {\text{製品の幅}}, j \in [i+1, 200](\text{無駄の幅})\}$ を定義し直します。例えば、 $m_{43, 44}$ が43mm幅の製品に対して43mm-44mmの無駄が発生するかどうか、 $m_{43, 45}$ が43mm幅の製品に対して44mm-45mmの無駄が発生するかどうかを表します。