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

image

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

問題の分離

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

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

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

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

数式化

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

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

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

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

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

グループ変数定義

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

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

i=20200gi=9\sum_{i=20}^{200} g_i = 9

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

g200=1g_{200} = 1

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

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

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

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

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

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

immのグループがjmm幅の製品に該当する    gi=1gk=0k[j,i1]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の無駄が発生するかどうかの変数m44m_{44}、 44㎜-45㎜の無駄が発生するかどうかの変数m45m_{45}など、{miiが無駄の幅}\{m_i | i\text{が無駄の幅}\}でどうでしょう。 例の43mm幅の製品と60mmグループの組み合わせで考えれば、 mi=1i[44,60],mj=0j[61,200]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は塗る部分になり無駄が発生しているわけではないので、 mi=0i[21,43]m_i = 0 \forall i \in [21, 43]でいけるのかもしれません。 でも、60mmグループが該当しない製品の場合はどうでしょう。

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

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

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

無駄の変数定義

この変数を使えば幅のグルーピングで発生する無駄の計算式が定義できます。 例の43mm幅、158㎜長さの製品の無駄が以下の式で表現できます。

i=44200158m43,i\sum_{i=44}^{200} 158 * m_{43, i}

60mmグループがこの製品に該当すると m43,i=1i[44,60],m43,j=0j[61,200]m_{43, i} = 1 \forall i \in [44, 60], m_{43, j} = 0 \forall j \in [61, 200]になるから、

i=4460(1581)+i=61200(1580)=158(6044+1)+0(20061+1)=2686mm2\begin{aligned} & &\sum_{i=44}^{60} (158 * 1) + \sum_{i=61}^{200} (158 * 0) \\ &= &158 * (60 - 44 + 1) + 0 * (200 - 61 + 1) \\ &= &2686mm^2 \end{aligned}

上と同じ結果ですね、よかった!

全ての製品の無駄の和をとると、最小値を求める表現が定義できます。

次は、この無駄の変数とグループの変数の関係を表す関数を定義する必要があります。 上出題したところを見返すと、以下のパターンが出てきます。

m43,44=1    g43=0m43,45=1    g43=0g44=0...m43,60=1    gk=0k[43,59]...m43,200=1    gk=0k[43,199]一般的な無駄の幅ですとm43,j=1    gk=0k[43,j1]一般的な製品幅ですとmi,j=1    gk=0k[i,j1]\begin{alignedat}{3} &m_{43, 44} &= 1 &\iff &g_{43} &= 0 \\ &m_{43, 45} &= 1 &\iff &g_{43} &= 0 \land g_{44} = 0 \\ &... \\ &m_{43, 60} &= 1 &\iff &g_k &= 0 \forall k \in [43, 59] \\ &... \\ &m_{43, 200} &= 1 &\iff &g_k &= 0 \forall k \in [43, 199] \\[1em] &\rlap{一般的な無駄の幅ですと} \\ &m_{43, j} &= 1 &\iff &g_k &= 0 \forall k \in [43, j - 1] \\[1em] &\rlap{一般的な製品幅ですと} \\ &m_{i, j} &= 1 &\iff &g_k &= 0 \forall k \in [i, j - 1] \end{alignedat}

数式に直すと

0<m43,44+g43<=10<2m43,45+g43+g44<=2...0<17m43,60+k=4359gk<=17...0<157m43,200+k=43199gk<=157一般的な無駄の幅ですと0<(j43)m43,j+k=43j1gk<=(j43)一般的な製品幅ですと0<(ji)mi,j+k=ij1gk<=(ji)\begin{alignedat}{5} 0 &< &&m_{43, 44} &+ &g_{43} &<= &&1 \\ 0 &< &2 * &m_{43, 45} &+ &g_{43} + g_{44} &<= &&2 \\ ... \\ 0 &< &17 * &m_{43, 60} &+ &\sum_{k=43}^{59} g_k &<= &&17 \\ ... \\ 0 &< &157 * &m_{43, 200} &+ &\sum_{k=43}^{199} g_k &<= &&157 \\[1em] \rlap{一般的な無駄の幅ですと} \\ 0 &< &(j - 43) * &m_{43, j} &+ &\sum_{k=43}^{j-1} g_k &<= &&(j - 43) \\[1em] \rlap{一般的な製品幅ですと} \\ 0 &< &(j - i) * &m_{i, j} &+ &\sum_{k=i}^{j-1} g_k &<= &&(j - i) \end{alignedat}

まとめ

長くなってしましましたが、 これで制御の式と最小化した式が全て定義しました。次回はやっとこれをプログラムにします。 ただその前に、変数が結構多くなり、少なくできると処理速度の短縮が可能です。 何か変数を減らす方法が思いつくのでしょうか。これも次回検討しましょう。

お知らせ

可茂IT塾ではFlutterインターンを募集しています!

可茂IT塾ではFlutterインターンを募集しています!

可茂IT塾ではFlutterインターンを募集しています!可茂IT塾のエンジニアの判断で、一定以上のスキルをを習得した方には有給でのインターンも受け入れています。

Read More
U30可茂ITインターンハッカソン

U30可茂ITインターンハッカソン

12月28,29日開催。2日間でアプリ開発の企画から完成までを目指す!U30可茂ITインターンハッカソンを開催します。

Read More

タグ

Flutter (109)初心者向け (28)イベント (18)Google Apps Script (15)Nextjs (12)可茂IT塾 (8)Firebase (7)riverpod (6)React (6)ChatGPT (5)デザイン (5)新卒 (4)就活 (4)vscode (4)Figma (4)Dart (4)JavaScript (4)お知らせ (4)FlutterWeb (3)Prisma (3)NestJS (3)Slack (3)TypeScript (3)ワーケーション (3)インターン (3)設計 (2)線型計画法 (2)事例 (2)Git (2)Image (2)File (2)Material Design (2)画像 (2)iOS (2)アプリ開発 (2)React Hooks (2)tailwindcss (2)社会人 (2)大学生 (2)RSS (1)Google (1)Web (1)CodeRunner (1)個人開発 (1)Android (1)Unity (1)WebView (1)Twitter (1)フルリモート (1)TextScaler (1)textScaleFactor (1)学生向け (1)supabase (1)Java (1)Spring Boot (1)shell script (1)正規表現 (1)パワーポイント (1)趣味 (1)モンスターボール (1)CSS (1)SCSS (1)Cupertino (1)ListView (1)就活浪人 (1)既卒 (1)保守性 (1)iPad (1)シェアハウス (1)スクレイピング (1)PageView (1)画面遷移 (1)flutter_hooks (1)Gmail (1)GoogleWorkspace (1)ShaderMask (1)google map (1)Google Places API (1)GCPコンソール (1)Google_ML_Kit (1)Vercel (1)Google Domains (1)DeepLeaning (1)深層学習 (1)Google Colab (1)オンラインオフィス (1)オブジェクト指向 (1)クラスの継承 (1)ポリモーフィズム (1)LINE (1)Bitcoin (1)bitFlyer (1)コミュニティー (1)文系エンジニア (1)Freezed (1)permission_handler (1)flutter_local_notifications (1)markdown (1)GlobalKey (1)ValueKey (1)Key (1)アイコン (1)go_router (1)debug (1)datetime_picker (1)Apple Store Connect (1)FlutterGen (1)デバッグ (1)Widget Inspector (1)検索機能 (1)Shader (1)Navigator (1)メール送信 (1)Firebase App Distribution (1)Fastlane (1)Dio (1)CustomClipper (1)ClipPath (1)カスタム認証 (1)アニメーション (1)Arduino (1)ESP32 (1)経験談 (1)フリーランス (1)mac (1)csv (1)docker (1)GithubActions (1)Dialog (1)BI (1)LifeHack (1)ショートカット (1)Chrome (1)高校生 (1)キャリア教育 (1)非同期処理 (1)生体認証 (1)BackdropFilter (1)レビュー (1)getAuth (1)Algolia (1)コンサルティング (1)Symbol (1)

お知らせ

可茂IT塾ではFlutterインターンを募集しています!

可茂IT塾ではFlutterインターンを募集しています!

可茂IT塾ではFlutterインターンを募集しています!可茂IT塾のエンジニアの判断で、一定以上のスキルをを習得した方には有給でのインターンも受け入れています。

Read More
U30可茂ITインターンハッカソン

U30可茂ITインターンハッカソン

12月28,29日開催。2日間でアプリ開発の企画から完成までを目指す!U30可茂ITインターンハッカソンを開催します。

Read More