スケジューリング問題を解く④
今までは時間という概念を考えず、ネットワーク流を解いてきました。
復習すると、
１）最大流問題 ： ネットワークには必ず細い箇所があって、
スループットはそこがボトルネックになるので
最大流はボトルネックの容量（太さ）に依存する。
２）最小費用最大流問題：
最大流問題を考えつつ経路を通る費用（コスト）
を最小化する。
という２つの問題がありました。
※最小経路問題もMathematicaでは専用の関数が用意されていますが、
費用も容量も１にするという、２）の変形ですね。
今回は、物理的なネットワークに時間の概念を入れます。
少しづつ、抽象的にしていきます。
「A地点からB地点に本１冊を１日かけて運ぶ」
という例題を考えてみます。
時間をTとして現在をT=0、明日をT=1…とします。
今、運ぶなら話は簡単です。（添字をTとして）
A0
↘
B1
です。（運ぶのに１日かかるので、Tが増えます）
A👉Bに本を運びはするんですが、いつ運ぶのかは分かっていません。
すると少々面倒ですが、「今日は運ばない」ことも考慮に入れる必要が出てきます。そして、「Bに運んだ物は、Bに居続ける」ことになります。
それを考慮すると、
A0→A1→A2→A3→…
↘ ↘ ↘ …
B1→B2→B3→…
となります。
このままでは、本が1冊どころか何冊も運ばれてしまいそうです。
拡張しましょう。StartとGoalの小計をそれぞれ1にします。
Start=1
↙ ↙↘ ↘…
A0→A1→A2→A3→…
↘ ↘ ↘ …
B1→B2→B3→…
↘ ↘ ↙…
Goal＝1
そして、Goalは3日後までには欲しいとすると、
B1+B2+B3＝1
です。
（この例ではわかりやすいですが、Start→A3まで引っ張ると遅延です）
Aの倉庫は只だけど、Bの倉庫は保管料が高いんだよな…
という時は、
A0→A1→…の費用を0に
B0→B1→…の費用は100にでもしましょう。
なるべく早く欲しいなら
B1→Goalの費用を0にして、B2→Goalの費用は100にするなど
少しづつ高くしていきます。
現実世界の問題に合わせて、各エッジの容量と費用を設定します。
「でも、A0とかA1で0.3冊づつ運ばれても困るんだよね…」
そうですね、このネットワーク流は実数ではなく整数にしたいです。
なので、各エッジの流れを全て整数に指定する必要があります。
これが最適化のツールを最も限定する要素です。
MathematicaはOK。
PythonはNetworkXが不可（他の記述は簡単なのに…）
PythonのPuLPはOK。
PythonのSageMathは整数型と実数型を混在できたかどうか微妙。
ExcelソルバーもOKです。
私は一番短く書けるのでMathematicaを選択します。
（短く書ければバグも少ないからです）
どうですか？ここまで来ると、
１種類の品物の運搬スケジュール 👉 最小費用最大コスト問題
になりました。
「そうはいっても、実際には
・異なる量と
・異なる能率（負荷、単位あたり効率）
・異なる運賃
・異なる着手開始可能日
・異なる納期
・複数工程
を持った複数種類の品目があるんだが？」
ですよね。
それは、⑤で片付けましょう。
実際にMathematicaで書いてみましょう。
最小費用最大コスト問題と全く同じですけど。
やり方はMathematicaのグラフ理論の機能を利用する方法です。
楽ですから。（これはPythonのNetworkXを利用するのと同じです）
確認すると
答えを求めると
ここまできてちょっと疑問が湧きますね。
着手可能日を設定するにはどうするの？
その場合はSA0の容量を0にしたりすると、SA1に流れて翌日着手になったりします。この辺りの単一品目までは、単純な書き方で何とかいけそうです。
ですが、⑤でやろうとしている複数品目では無理そうですね。。。
それには自分でキルヒホッフの法則をチクチク使った面倒な方法で書かないとダメそうです。そうするとグラフを描画してくれないのでデバッグが大変です。この辺り、もっと何とかしたいなぁと思っています。
今回くらいまでの内容は全てここに書いてあります。
次回くらいまでの内容は全てここに書いてあります。
間違っても、ご自分で０から考えたりする事の無いように！
（私はフリーレンじゃないのに、それをやっちゃったんですよ…）
他の参考書はこちらに。
この記事が気に入ったらサポートをしてみませんか？