【しっかり学ぶ数理最適化】4.1.3~4.1.4

2025年後期輪読会#8(2025/12/04) しっかり学ぶ数理最適化 4.1.3～4.1.4 京都大学大学院 理学研究科 M2 佐藤海里 0

アジェンダ ◼ 4.1.3 固定費付き目的関数 ◼ 4.1.4 隣接した制約条件 1

4.1.3 固定費付き目的関数 ・現実の問題では総費用=固定費(初期費用)+変動費を目的関数とすることが多い. （例:(賃貸の総費用)=(敷金・礼金)+(家賃)×(期間(月))) ・一般化すると次のように表せる(𝑓 𝑥 はコスト, 𝑥は導入期間,生産量など). 0 𝑥=0 𝑓 𝑥 =ቊ 𝑐1 𝑥 + 𝑐2 0<𝑥≤𝐶 ・左の例は、企業経営における総費用を表している. 固定費は人件費等,変動費は材料費等を指す. 2

4.1.3 整数計画問題への帰着 ・この目的関数は,整数値の変数𝑦を用いて,次のように表すことができる. 𝑓 𝑥, 𝑦 = ൛𝑐1 𝑥 + 𝑐2 𝑦|𝑥 ≤ 𝐶𝑦, 0 ≤ 𝑥 ≤ 𝐶, 𝑦 ∈ 0, 1 } 𝑦 = 1の場合,初期費用を支払い(契約を履行する), 𝑦 = 0の場合,初期費用を支払わない(未契約). ・このように、意思決定の仕方を表す整数値のパラメータを用いることで, 現実のあらゆる問題を以下のような整数計画問題に定式化できる. Minimize 𝑓 𝑥, 𝑛 Subject to 𝜑𝑖 𝑥, 𝑛 = 0, 𝛹𝑗 𝑥, 𝑛 ≤ 0 𝑥 ∈ ℝ𝑑 , 𝑛𝜖 0,1, ⋯ 𝑚 𝑑, 𝑚 はある自然数. 3

4.1.3 施設配置問題 ・いくつかの候補地の中から工場を選んで建設し,そこから物を運ぶ問題を考える. 工場の総建設費+輸送費を最小化したい.以下のように定式化できる. 𝑛 𝑚 σ σ minimize σ𝑚 𝑐 𝑥 + 𝑖=1 𝑗=1 𝑖𝑗 𝑖𝑗 𝑖=1 𝑓𝑖 𝑦𝑖 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ・ σ𝑛𝑗=1 𝑥𝑖𝑗 ≤ 𝑎𝑖 𝑦𝑖 , 生産条件 ・ σm 需要条件 i=1 𝑥𝑖𝑗 = 𝑏j , ・ 𝑥𝑖𝑗 ≥ 0, 𝑦𝑖 ∈ {0,1} ・ 𝑐𝑖𝑗 :輸送費, 𝑓𝑖 :建設費, 𝑎𝑖 :生産上限, 𝑏j :需要 ・ 𝑥𝑖𝑗 :生産量, 𝑦𝑖 :工場を建設するか否か ・工場の建て方の組み合わせは2𝑚 通り. 4

4.1.3 ピンパッキング問題 ・十分多くある箱に荷物𝑗(1 ≤ 𝑗 ≤ 𝑛)を入れていく. 箱の重さの上限をCとする. 𝑗の重さをwj < Cとした場合,箱は最低何個必要?という問題の定式化を考える. minimize σn𝑖=1 𝑦𝑖 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 ・ σ𝑛𝑗=1 wj 𝑥𝑖𝑗 ≤ C𝑦𝑖 , 箱の重さ制約 ・ σni=1 𝑥𝑖𝑗 = 1, jはどっかの箱に入る ・ 𝑥𝑖𝑗 ∈ {0,1}, 𝑦𝑖 ∈ {0,1} ・ wj : 𝑗の重さ, C:箱の重さの上限 ・ 𝑥𝑖𝑗 :箱iにjが入るか, 𝑦𝑖 :箱iを使うか 2 +𝑛 𝑛 ・ 𝑥𝑖𝑗 , 𝑦𝑖 の組み合わせは2 通り. 5

4.1.3 ロットサイズ決定問題 ・製品を生産して出荷,余った在庫を倉庫に入れるのを𝑇 ∈ ℕ期繰り返す. 生産,出荷,倉庫に持ち越すのにはお金がかかる. 出費を最小限抑えて毎期の需要𝑑𝑡 , (𝑡 ∈ 1,2, … 𝑇 )を満たすようにするために どうすればいいだろうか？ 𝑇 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ෍ 𝑓𝑡 𝑦𝑡 + 𝑐𝑡 𝑥𝑡 + 𝑔𝑡 𝑠𝑡 𝑡=1 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜・𝑠𝑡-1 + 𝑥𝑡 －𝑠𝑡 = 𝑑𝑡 , (余りは在庫へ) ・𝑥𝑡 ≤ 𝐶𝑦𝑡 , (生産上限制約) ・𝑠0 = 0, 𝑥𝑡 ≥ 0 ・𝑠𝑡 ≥ 0, 𝑦𝑡 ∈ {0,1} 𝑡 = 1, … , 𝑇 ・𝑓𝑡 :段取り替え費, 𝑐𝑡 :生産費, 𝑔𝑡 :在庫費用, 𝐶:生産上限 ・𝑦𝑡 :生産するかどうか, 𝑥𝑡 :生産量, 𝑠𝑡 :在庫量 ・生産するかどうかの組み合わせは2T 通り. 6

4.1.4 隣接した制約条件 ・普通は,最適化問題で、全ての制約条件を満たすような最適解を考える. 制約条件のうちからちょうど何本かだけを満たす場合のみを考えることも. このことを,隣接した制約条件とよぶ. ・ σ𝑛𝑗=1 𝑎1𝑗 𝑥𝑗 ≤ 𝑏1 or σ𝑛𝑗=1 𝑎1𝑗 𝑥𝑗 ≤ 𝑏1 という条件は変数𝑦1 ,𝑦2 によって ・ σ𝑛𝑗=1 𝑎1𝑗 𝑥𝑗 ≤ 𝑏1 + 𝑀 1 − 𝑦1 ・ σ𝑛𝑗=1 𝑎2𝑗 𝑥𝑗 ≤ 𝑏2 + 𝑀 1 − 𝑦2 , ・𝑦1 + 𝑦2 = 1 ・𝑦1 , 𝑦2 ∈ {0,1} と言い換えることができる.ここで, 𝑀は十分に大きな定数で,big-Mと呼ばれる. 7

4.1.4 1機械スケジューリング問題 ・1台の機械がn個の仕事をこなす.同時に2個以上の仕事はこなせない. 仕事iの処理にかかる時間をpi,納期をdiとする.開始時刻をsiとする. 仕事の納期遅れの合計を最小化する以下の最適化問題を考える. minimize σ𝑛𝑖=1 max 𝑠𝑖 + 𝑝𝑖 − 𝑑𝑖 , 0 subject to ・𝑠𝑖 + 𝑝𝑖 ≤ 𝑠𝑗 + 𝑀 1 − 𝑥𝑖𝑗 (j ≠ i) ・𝑥𝑖𝑗 + 𝑥𝑗𝑖 = 1,(j > i) ・𝑥𝑖𝑗 ∈ {0,1}, 𝑠𝑖 ≥ 0,(j ≠ i) (ここで, 𝑥𝑖𝑗 は,iがjより先行するなら1,そうでないなら0とする変数.) ・𝑡𝑖 = 𝑚𝑎𝑥 𝑠𝑖 + 𝑝𝑖 －𝑑𝑖 , 0 とおくと、𝑡𝑖 ≥ 𝑠𝑖 + 𝑝𝑖 －𝑑𝑖 という条件が追加され,簡単になる. ・1行目に先行の条件は, jに先行するiに対して, jが始まる前にiが終わるという意味. 8

4.1.4 長方形詰め込み問題 ・長方形をしきつめていく.以下のような容器の高さを最小化する問題を考える. （制約条件） ・荷物iは容器内にある ・i,jはたがいに重ならない （iがjの上下左右いずれかにある） 長方形詰込み問題をPythonで解く #アルゴリズム – Qiitaより引用 9

• https://qiita.com/chikurin66/items/e76e3c93ec969898ed8d