いかに古典的な素材を話題にしているかがわかろうというものですが、 「集合被覆」の話は初回とその続編の間にじつに一年以上が経過してしまいました。 このような「最適化の実例」の記事は読んで頂いている方々の 手元で最適化ツールの動作を具体的に見なが…

車両 1 ～ 5 と、それらが巡回する部品工場 A～F の対応は同じで、今度は下の表が示すように毎日、 消耗品を所定のケース数だけ届けねばならない、という状況を考えます。 前回のように「とにかく届ければ(車が行きさえすれば)よい」というわけではなく、 車…

車両 1～5 と、部品工場A ～ F との対応を示している表があります。 どんな状況が想定されるでしょうか？ ここはあるメーカーの本社組み立て工場。 操業には部品工場(A～F)からの部品を仕入れて来る必要があって、 この表は仕入れをしている 5台の車のそれぞ…

前回は Excel による集計表をベースに数理最適化のモデルを記述して、 という表を得るところまで進みました。 丸で囲った「生産量」のところの数字が数理最適化の答です。 タイトル通り、面倒な解説は抜きで、どんどん数字を変えて数理最適化の応答を見てみ…

「数理最適化は表に始まり表に終わる」というのは私が勝手に作った言葉ですが、 我々が普通に Excel などを使って作る集計表を数理最適化にかけると、集計結果が意図した感じになるよう都合良く数字を書き込んでくれたりします。ここから始まるちょっとした…

倉庫には容量以上の在庫は入らない。 納期を守るには先立って一定のリソースを割く必要があるし、 休暇は所定の数だけ必ず取ってもらわねばならない。 数理最適化はそんなビジネスの「ロジック」を取り出して記述し、 その枠内で良さげな答を探しださせる手…

「最適化」という言葉を Web で探すと スマホ最適化、ディスク最適化、画像最適化・・ といった感じのものがひっかかってきます。 「今よりも良い状態」を実現する手段といったニュアンスですね。 じつは学術的な数理最適化の分野の「最適」はもっと杓子定規…

「一筆書き」のように、 答を見せられれば正しいかどうかはすぐにわかるけれど、 「白紙」の状態からそれを見つけるのはかなり難しい、 というタイプの問題は世の中には数多くあります。 数学的な話で有名なのは大きな数の素因数分解ですが、 ここまで抽象的…

「メンバーは5人、勤務は日勤と夜勤の二種類しかありません」 今、小さな病院の担当の方に勤務シフト作りについて伺っています。 「毎日日勤は2人、夜勤は1人は必要です。夜勤空けは休み。それとは別に各人週に1日は休みを入れ、夜勤の担当回数は週あたり1日…

厳密に言おうとすると、答えが「ある」ということより「ない」ということの方が難しい。 「ある」ことは答を一個見つけてくればよいのに対して「ない」は網羅的に確認する必要があるから。そういえばあのフェルマーの大定理やリーマン予想もこのタイプの命題…

判断材料を増やす 例えばスマートフォンを買うとして、契約プランの決定をする段になったとしましょう。 「利用量が 1G を超えないのならば基本料金お安め従量制のこのプランでしょうかね。 けど沢山使う方でしたらちょっと高いけど定額の契約もこんなにお得…

最適化でいろいろやった結果何が実現できているのか、という話の続きです。 どんどん行きましょう。 実行可能性チェックによる安心感 数理最適化という手法のメリットの一つに、出た結果は少なくとも制約式を満たしている、 ということが挙げられます。 実務…

最適化で「何をしているのか」と問われれば、 「運転計画」「スケジューリング」「配送計画」「ポートフォリオ最適化」 といった月並な答になってしまいますが、 ここでは数理最適化にこれらをさせることによって、 結局「何を実現しようとしているのか」と…

前回は数理最適化を使って、利便性と安全性を共に追求する地点を探そうとして目的関数を (利便性重み)×(地点の利便性) + (安全性重み)×(地点の安全性) という「重み付き平均」にしたは良いのですが、 候補になる土地の形が直線的なときにちゃんと「按分」さ…

エネルギー最適化における、CO2排出量とエネルギーコスト。 積み付けにおける、作業効率とスペース効率。 はたまた生産計画問題における在庫切れリスクと商品廃棄コスト、 そうかと思うとポートフォリオのリスクとリターン、といった具合に 実務的な数理最適…

6000円の予算枠内でできるだけ分量多くビーズを買おうという問題を数理最適化で解いているM君、 「B店からすべて購入」というあんまり面白くない結果になってちょっとがっかり。 まあそれもそのはずで、 店舗 価格/一袋 分量/一袋 A 250円 100個 B 1000円 40…

ここは手作りアクセサリーの店。 ビーズの残りがなくなってきました。良く使うタイプなので多めに、予算 6000 円で調達します。 調達先の候補をネットショップでざっと探してみると次のような感じです。 店舗 価格(一袋あたり） 分量 A 250円 100個 B 1000円…

前回は働き方(シフト)のパターンを列挙して、重ね合わせのモデルを解くことで 必要な人数を手当するために各シフトパターンを割り当てるべき人数を次のように明らかにしました。 あとは、12人のスタッフ A ～ L にどれを割り振るかで、このモデルは 少し前の…

前回は最低限の要件から出発して、「勤務は連続」という「常識」を制約の形で入力し、まともなシフトの導出までたどり着きましたが、今回は発想の方向を変えてそもそもどんなシフトが許されるのか、まずは考えてみましょう。 「連続」という制約が効いて、許…

数理最適化問題のタイプ分けのご紹介が一通り終わったところで、 これらを用いてよく実務で現れる数理最適化のモデルの組み立て方について具体的に解説しましょう。 オフィス街でランチ営業しているある居酒屋のアルバイトスタッフ 12 人の 勤務シフトを決定…

人に仕事をアサインしたり、車に荷物を割りあてたり、 人に商品をおすすめ(レコメンド)したり、といった問題は 数理最適化の重要な応用の一つで、 これらは次の絵のような構造を持つ「対応付け」タイプのモデルで 記述されます。 「人」や「車」が左の○、「…

いわゆる「シフト表」は「人」を行、「日付」を列とするマス目の形をしています。 5人のアルバイトさんＡ，Ｂ，Ｃ，Ｄ、Ｅの一週間のシフト表を数理最適化で作ってみます。 この職場では各人は「レ」(レジ打ち)、「日」(日勤)、「夜」(夜勤)、「休」(休暇) …

「電力自由化」の波に乗って電力契約(プロバイダ)を乗り換えた、学生向けアパートの大家さんの話。 プロバイダのホームページの自分のアカウントを見ると電力使用量の履歴がわかります。 どれどれ、と平均的な一日の様子を見てみると次のような感じになって…

投資すなわちお金を「投ずる」こと、とはよく言ったもので、 例えば株などの資産を購入した途端に自分の手を離れて勝手に価値が上下し出します。 株 A に投資した人がいたとしましょう。株 A はその時点から週単位で 次のような値動きをしたとします。 20週…

ネットワークというと何か面倒そうに聞こえますが、 「双六」に沢山の枝分かれが付いたものをイメージすれば大体合っていて、 駒の止まるマスと、マスを継ぐ線からできているひとまとまりを言います。 とある高校の球技大会でのことです。 2年は「バスケ」の…

「時間」という概念を入れると「セット販売」のパターンが自然に量産できて 「セット販売」のうまい重ね合わせ、という話がぐっと実務性を帯びてきます。 具体的に申しましょう。今度の例は物を買う話ではなくて作る話になります。 ある製品をある日までに出…

欲しいものを「それだけ」手に入れるというのは難しいのが普通です。 「この皿だけ」食べたいと思っても定食を頼まなければならないとか、欲しいのは 2,3 曲なのに結局アルバム 2 枚も買う羽目になってしまったとか。とかくままならないのがこの世の中。 そ…

「この最適化モデルはどんな方法で解いているのですか?」 先日、お客さまに聞かれました。 ええと普通の LP (線形計画問題) に 0-1 整数変数が入った MILP (線形な混合整数計画法)だから 分枝限定法? でもそれは解法フレームワークの名前に過ぎない。 線形性…

数理最適化の壁は最初の「モデル」を書く部分です。 教科書には「簡単な」モデルが書いてありますが、 なんか現実的ではないのが多いですよね。 部品が 3 つしかない 2 種類の製品を作っている工場の最適化、とか。 こんな高いソフト買って、できるのはそん…