【線型計画法】問題の背景と分割

線型計画法はいくつかの線形不等式（変数と変数の掛け算がない不等式）の解の中で、 ある線形表現の最大・小値となる解を見つける方法です。違う言い方をしてみれば、 数式で制御された変数の値の中で最適な値を見つける方法です。なんとなくの理解で問題ないですが、 もっと知りたい人はウィキペディアに参考してください。

線型計画法みたいな抽象的なテックニックをなかなか使う機会が出ないですが、 最近会社（株式会社東和製作所）で使えたおかげで塗装ラインの改善に貢献出来ました。

その背景と線型計画法を使うための問題分別を紹介します。 分かりやすくするため、一部のデータや状況を変更していますが、 流れ的には実際にぶつかった問題やその対策には変更がありません。

背景：塗装ラインの塗料無駄使い消滅

会社で製品を塗装していますが、少量多品種生産で色々な大きさのものをコンベアに掛けて 順番に自動塗装吹き付け機が塗装します。製品はコンベアに直接かけることができなくて、 ハンガーの治具を利用して塗装機の前を通させる必要があります。 製品の横幅や長さがバラバラで、作業者が掛け・下ろししやすくするためハンガーの長さもいくつかあります。

下の図の通り、現在は製品の寸法に関係なく塗装機が動くため、 製品以外の場所にも塗料を噴射し、無駄（赤い枠）が発生しています。

製品があまりにも多く、各製品の最適な塗装量を使うように塗装範囲を調整することも非現実的です。 ただし、製品をグルーピングして、そのグループ番号で塗装機の動きを制御すると現状より無駄を減らすことが可能です。 具体的に、製品の横幅、上限位置（ハンガーの長さ）、塗装長さ（製品の長さ）で塗装したい範囲が定義できるので、 それぞれの製品とハンガーから、3つのグループ番号を算出して、そのグループ番号から塗装範囲を決めます。

単純に考えると、各パラメータの値の範囲を一定の幅で分けてグルーピングを決めることができます。 例えば、横幅が20mmから200mmまでであれば、各グルーピングを20mmずつにすると全ての製品が対応できます。 同じく、他のパラメータのグルーピングを決めると以下のようなグルーピングが出来上がります。

最適化問題の定義

それぞれの製品・ハンガーの組み合わせから各パラメータのグループが算出できます。

例えば、横幅43mm、長さ158mmの製品を120mmのハンガーに掛けるとします。上記のグルーピングを使えば、 横幅43mmが横幅グループ2（~60mm）に該当し、ハンガー120mmが上限位置グループ5（110mm~）に該当します。 上限位置グループ5は110mmのため、溢れたハンガー長さの10mmも塗装範囲内に入ります。 そのため、製品長さ158mmが塗装長さグループ6（~160）に該当しているが、製品がはみ出してしまいます。 上限位置を下回ったハンガーの10㎜を製品の長さ158mmと合わせて168mmの塗装長さとなり、 塗装長さグループ6（~190mm）に該当します。

そのグルーピングの組み合わせで、塗装範囲が分かりますので、その面積で使用する塗料が推理できます。 同じように、製品の寸法から理想の塗装範囲の面積と比較することが可能で、その差異で無駄も表現できます。 先の例ですと、グルーピングの塗装範囲が60mm x 190mm = 11,400mm²に対して、 理想の塗装範囲が43mm x 158mm = 6,794mm²になり、4,606mm²の無駄があります。

各製品に対して発生する無駄を計算するとグルーピング結果の評価ができ、違うグルーピング結果と比較することも考えられます。 つまり、違うふうにグループ分けをすれば、そのグルーピングの無駄も計算して、無駄が低いほうがよりいいグルーピングです。 このように、全ての製品を対応するグルーピングの中で無駄値が一番低いグルーピングが見つければ、 最適なグルーピングが見つかったことになります。これは最適化の問題で、答えを出す方法の１つが線型計画法です。

線型計画法を分かっている方はちょっとした違和感を覚えるかと思います。 それは、面積を計算するには横幅と製品長さの掛け算になるため、線形計画法の対象となるかが疑わしいからです。 確かに、今のままですと対象ではないため、次回に問題を変換する必要になります。