Upgrade to Pro — share decks privately, control downloads, hide ads and more …

数理最適化ことはじめ / Introduction to Mathematical Optim...

数理最適化ことはじめ / Introduction to Mathematical Optimization

本スライドでは、数理最適化を概観し、基本的な問題とその解き方を分かりやすく解説することを目標にしています。数理最適化に興味を持っていただければ嬉しいです。

【目次】
1 章 数理最適化とは(p.2~20)
2 章 連続最適化問題(p.21~133)
3 章 離散最適化問題(p.134~238)
4 章 まとめ(p.239~248)

E869120

March 29, 2022
Tweet

More Decks by E869120

Other Decks in Programming

Transcript

  1. 248 1-0 自己紹介 2 米田 優峻(よねだ まさたか) • 2002年生まれ •

    2015年筑波大学附属駒場中学校入学 • 2021年東京大学入学 主な実績 • AtCoder には E869120 として参加(レッドコーダー) • 国際情報オリンピック‘18,‘19,‘20 金メダル • 著書「アルゴリズム×数学」2 万部突破
  2. 248 1-0 目次 4 1 章 2 章 1.0 はじめに

    1.1 数理最適化とは 1.2 連続最適化と離散最適化 2.0 線形計画問題とは 2.1 単体法のイメージ 2.2 単体法の計算過程 2.3 線形計画の応用例 2.4 その他の連続最適化問題 ・・・・・・・・・ ・・・・・・・・・・・ ・・・・・・ ・・ 2 4 5 17 ・・・・・ ・・・・・ ・・・・・ ・・・・・ ・・ 21 36 64 96 119 3 章 3.0 離散最適化とは 3.1 解ける問題に落とす 3.2 山登り法と焼きなまし法 3.3 近似アルゴリズム 3.4 整数計画問題 ・・・・ ・・ ・・・ ・・・・・ 134 140 175 205 221 4 章 4.0 まとめ 4.1 参考文献 ・・・・・・・・ ・・・・・・・ 239 247 目次
  3. 248 1-1 最適化問題の例 9 たとえば、10×10 の正方形に 6 個の円を敷き詰める問題を考えま しょう。できるだけ直径が大きくなるようにしたいです。 10

    10 直径 3.33 普通にやると… 10 10 直径 3.75 最適解! (これを求めたい) このように、目的関数の値(スコア)を 最大(or 最小)にする答えを求める問題を 数理最適化問題といいます
  4. 248 1-1 事例 1:最短経路問題 11 問題概要 目的関数(スコア) 始点から終点まで、できる限り短い時間 で行く方法を求める問題 東京

    新宿 渋谷 上野 羽田 空港 品川 5分 5分 17分 13分 5分 12分 11分 19分 8分 池袋 行くのにかかった時間(分)
  5. 248 1-1 事例 2:カロリー最大化 12 問題概要 目的関数(スコア) 500 円以内の買い物で、できる限り多く のカロリーを得る方法を求める問題

    摂取したカロリー(kcal) 200円 160kcal 150円 240kcal 300円 400kcal 食パンとラーメンで 最適解 640kcal が得られます
  6. 248 1-1 事例 3:工場の売上最大化 13 問題概要 目的関数(スコア) できる限り多くの売上を得るように、製 品を作る方法を求める問題 売上金額(万円)

    ×1kg 製品A 1kg当たり 製品B 1kg当たり ×3kg 在庫量 ×4kg ×2kg ×1kg ×1kg 製品 A を 1kg、製品 B を 2kg 作るのが最適 (売上は 20 万円)
  7. 248 1-1 事例 4:箱詰めの問題 14 問題概要 目的関数(スコア) 重さ 10kg まで入れられる箱がいくつか

    あり、出来るだけ少ない数の箱を使って 荷物を詰める 必要な箱の数(個数) 9 7 3 6 4 4 3 2 2 3 3 4 4 6 7 9
  8. 248 1-1 事例 6:最適なクラス分け 16 問題概要 目的関数(スコア) 仲が悪い組が同じクラスにならないよう に、同じ人数のクラス 2

    つに分ける 同じクラスにいる 「仲が悪い組」の数 1 3 4 2 5 7 8 2 組 1 組 6 同じクラスの 仲の悪い組
  9. 248 1-2 数理最適化問題の分類 最適化問題は主に 2 つに分類されます 連続最適化問題 離散最適化問題 A の生産量

    B の生産量 品物 A の個数 品物 B の個数 条件を満たす範囲 条件を満たす解 18 変数が連続的な実数である 「1.5kg 生産する」などが許される 変数がとびとび(整数など)である 「1.5 個買う」などが許されない
  10. 248 1-2 変数がとびとび(整数など)である 「1.5 個買う」などが許されない 数理最適化問題の分類 最適化問題は主に 2 つに大別されます 連続最適化問題

    離散最適化問題 A の生産量 B の生産量 品物 A の個数 品物 B の個数 変数が連続的な実数である 「1.5kg 生産する」などが許される 条件を満たす範囲 条件を満たす解 19 代表的な問題 • 線形計画問題(事例 3:売上最大化) • 非線形計画問題(円の敷詰め問題など) 2 章で扱います
  11. 248 1-2 変数が連続的な実数である 「1.5kg 生産する」などが許される 数理最適化問題の分類 最適化問題は主に 2 つに大別されます 連続最適化問題

    離散最適化問題 A の生産量 B の生産量 品物 A の個数 品物 B の個数 変数がとびとび(整数など)である 「1.5 個買う」などが許されない 条件を満たす範囲 条件を満たす解 20 代表的な問題 • 最短経路問題(事例 1) • ナップザック問題(事例 2) • ビンパッキング問題(事例 4) • 巡回セールスマン問題(事例 5) 3 章で扱います
  12. 248 2-0 線形計画問題とは 23 制約条件とスコア※ が一次関数(線形 関数)で与えられる最適化問題を 線形計画問題 といいます ※スコアは目的関数ともいう。

    • 2𝑥1 + 3𝑥2 ≤ 8 • 4𝑥1 + 3𝑥2 ≤ 10 を満たす中で 𝑥1 + 𝑥2 の最大値は? ※ただし、𝑥1 , 𝑥2 は非負
  13. 248 2-0 線形計画問題とは 24 制約条件とスコア※ が一次関数(線形 関数)で与えられる最適化問題を 線形計画問題 といいます ※スコアは目的関数ともいう。

    • 2𝑥1 + 3𝑥2 ≤ 8 • 4𝑥1 + 3𝑥2 ≤ 10 を満たす中で 𝑥1 + 𝑥2 の最大値は? ※ただし、𝑥1 , 𝑥2 は非負 まずはこの問題を解いてみよう!
  14. 248 2-0 線形計画問題とは 25 𝑥1 𝑥2 • 2𝑥1 + 3𝑥2

    ≤ 8 • 4𝑥1 + 3𝑥2 ≤ 10 を満たす中で 𝑥1 + 𝑥2 の最大値は? 1 2 3 4 1 2 3 4 グラフ を描いて みよう ※ただし、𝑥1 , 𝑥2 は非負
  15. 248 2-0 線形計画問題とは 26 𝑥1 𝑥2 1 2 3 4

    1 2 3 4 2𝑥1 + 3𝑥2 = 8 を追加 条件を 満たす領域 • 2𝑥1 + 3𝑥2 ≤ 8 • 4𝑥1 + 3𝑥2 ≤ 10 を満たす中で 𝑥1 + 𝑥2 の最大値は? ※ただし、𝑥1 , 𝑥2 は非負 グラフ を描いて みよう
  16. 248 2-0 線形計画問題とは 27 𝑥1 𝑥2 1 2 3 4

    1 2 3 4 4𝑥1 + 3𝑥2 = 10 を追加 条件を 満たす領域 • 2𝑥1 + 3𝑥2 ≤ 8 • 4𝑥1 + 3𝑥2 ≤ 10 を満たす中で 𝑥1 + 𝑥2 の最大値は? ※ただし、𝑥1 , 𝑥2 は非負 グラフ を描いて みよう
  17. 248 2-0 線形計画問題とは 28 𝑥1 𝑥2 1 2 3 4

    1 2 3 4 B D C A • 2𝑥1 + 3𝑥2 ≤ 8 • 4𝑥1 + 3𝑥2 ≤ 10 を満たす中で 𝑥1 + 𝑥2 の最大値は? ※ただし、𝑥1 , 𝑥2 は非負 グラフ を描いて みよう 重要な考察 2 直線の交点 A~D の どれかが最適解
  18. 248 2-0 線形計画問題とは 29 𝑥1 𝑥2 1 2 3 4

    1 2 3 4 B D C A スコア 𝑥1 + 𝑥2 = 5 • 2𝑥1 + 3𝑥2 ≤ 8 • 4𝑥1 + 3𝑥2 ≤ 10 を満たす中で 𝑥1 + 𝑥2 の最大値は? ※ただし、𝑥1 , 𝑥2 は非負 グラフ を描いて みよう 重要な考察 理由:スコアを下げていくと分かる 2 直線の交点 A~D の どれかが最適解
  19. 248 2-0 線形計画問題とは 30 𝑥1 𝑥2 1 2 3 4

    1 2 3 4 B D C A スコア 𝑥1 + 𝑥2 = 4 • 2𝑥1 + 3𝑥2 ≤ 8 • 4𝑥1 + 3𝑥2 ≤ 10 を満たす中で 𝑥1 + 𝑥2 の最大値は? ※ただし、𝑥1 , 𝑥2 は非負 グラフ を描いて みよう 重要な考察 理由:スコアを下げていくと分かる 2 直線の交点 A~D の どれかが最適解
  20. 248 2-0 線形計画問題とは 31 𝑥1 𝑥2 1 2 3 4

    1 2 3 4 B D A スコア 𝑥1 + 𝑥2 = 3 C 交点で初めて 接する! • 2𝑥1 + 3𝑥2 ≤ 8 • 4𝑥1 + 3𝑥2 ≤ 10 を満たす中で 𝑥1 + 𝑥2 の最大値は? ※ただし、𝑥1 , 𝑥2 は非負 グラフ を描いて みよう 重要な考察 理由:スコアを下げていくと分かる 2 直線の交点 A~D の どれかが最適解
  21. 248 2-0 線形計画問題とは 32 この考察を使うと、交点を全 探索するだけで解ける 座標 スコア 交点 A

    (0, 0) 0 交点 B 0, 8/3 8/3 交点 C (1, 2) 3 交点 D (5/2, 0) 5/2 最適解 𝑥1 𝑥2 1 2 3 4 1 2 3 4 B D C A
  22. 248 2-0 線形計画問題とは 33 この考察を使うと、交点を全 探索するだけで解ける 座標 スコア 交点 A

    (0, 0) 0 交点 B 0, 8/3 8/3 交点 C (1, 2) 3 交点 D (5/2, 0) 5/2 最適解 𝑥1 𝑥2 1 2 3 4 1 2 3 4 B D C A 問題設定は 分かりましたか?
  23. 248 2-0 線形計画問題の定式化 34 問題 変数(次元)が 𝑛 個、制約条件が 𝑚 個のとき

    𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 の最大値を求めよ 条件 • 𝑎1,1 𝑥1 + 𝑎1,2 𝑥2 + ⋯ + 𝑎1,𝑛 𝑥𝑛 ≤ 𝑏1 : • 𝑎𝑚,1 𝑥1 + 𝑎𝑚,2 𝑥2 + ⋯ + 𝑎𝑚,𝑛 𝑥𝑛 ≤ 𝑏𝑚 • (𝑥1 , 𝑥2 , … , 𝑥𝑛 は負の数ではない)
  24. 248 2-0 線形計画問題のイメージ 35 文字の種類が多くて混乱すると思うので、具体例を挙げます 以下の条件を満たす中で、𝑥1 + 2𝑥2 + 3𝑥3

    の最大値は? • 4𝑥1 + 3𝑥2 + 5𝑥3 ≤ 25 • 2𝑥1 + 9𝑥2 + 2𝑥3 ≤ 26 • 7𝑥1 + 7𝑥2 + 7𝑥3 ≤ 42 • 8𝑥1 + 9𝑥2 + 9𝑥3 ≤ 53 制約条件の数 𝑚 = 4 変数の数 𝑛 = 3 こういう問題を 高速に解きたい ※ただし、𝑥1 , 𝑥2 , 𝑥3 は非負
  25. 248 2-1 線形計画問題を解くには…? まず、「交点の位置」を全探索する方針が考えられる 変数が 2 個、制約条件が 4 個の場合は…? 40

    交点は 15 通り 変数と制約条件が少なければ コンピュータならば一瞬で探索できるが…?
  26. 248 2-1 線形計画問題を解くには…? • 変数が 𝑛 個、制約条件が 𝑚 個の場合を考える •

    𝑥𝑖 = 0 などを含めたら 𝑛 + 𝑚 本の直線(or 平面)があるが、𝑛 次元なの でこのうち 𝑛 本を選んだときの共通部分が点になる 41 • 3𝑥1 + 4𝑥2 ≤ 8 • 5𝑥1 + 6𝑥2 ≤ 20 • 7𝑥1 + 8𝑥2 ≤ 30 • 3𝑥1 + 4𝑥2 ≤ 8 • 5𝑥1 + 6𝑥2 ≤ 20 • 7𝑥1 + 8𝑥2 ≤ 30 • 𝑥1 = 0 • 𝑥2 = 0 5 個の直線のうち 2 個を選べば交点 ※ 𝑥1 , 𝑥2 は非負
  27. 248 2-1 線形計画問題を解くには…? 42 • 変数が 𝑛 個、制約条件が 𝑚 個の場合を考える

    • 𝑥𝑖 = 0 などを含めたら 𝑛 + 𝑚 本の直線(or 平面)があるが、𝑛 次元なの でこのうち 𝑛 本を選んだときの共通部分が点になる • すなわち、交点の数は二項係数 𝐶(𝑛 + 𝑚, 𝑛) 個となる
  28. 248 2-1 線形計画問題を解くには…? 43 • 変数が 𝑛 個、制約条件が 𝑚 個の場合を考える

    • 𝑥𝑖 = 0 などを含めたら 𝑛 + 𝑚 本の直線(or 平面)があるが、𝑛 次元なの でこのうち 𝑛 本を選んだときの共通部分が点になる • すなわち、交点の数は二項係数 𝐶(𝑛 + 𝑚, 𝑛) 個となる (𝑛, 𝑚) (10, 10) (20, 20) (30, 30) 交点の数 184,756 かかる時間 一瞬 PC の計算速度は 10~100億回/秒
  29. 248 2-1 線形計画問題を解くには…? 44 (𝑛, 𝑚) (10, 10) (20, 20)

    (30, 30) 交点の数 184,756 137,846,528,820 かかる時間 一瞬 2 分 PC の計算速度は 10~100億回/秒 • 変数が 𝑛 個、制約条件が 𝑚 個の場合を考える • 𝑥𝑖 = 0 などを含めたら 𝑛 + 𝑚 本の直線(or 平面)があるが、𝑛 次元なの でこのうち 𝑛 本を選んだときの共通部分が点になる • すなわち、交点の数は二項係数 𝐶(𝑛 + 𝑚, 𝑛) 個となる
  30. 248 2-1 線形計画問題を解くには…? 45 (𝑛, 𝑚) (10, 10) (20, 20)

    (30, 30) 交点の数 184,756 137,846,528,820 118,264,581,564,861,424 かかる時間 一瞬 2 分 3 年 PC の計算速度は 10~100億回/秒 • 変数が 𝑛 個、制約条件が 𝑚 個の場合を考える • 𝑥𝑖 = 0 などを含めたら 𝑛 + 𝑚 本の直線(or 平面)があるが、𝑛 次元なの でこのうち 𝑛 本を選んだときの共通部分が点になる • すなわち、交点の数は二項係数 𝐶(𝑛 + 𝑚, 𝑛) 個となる
  31. 248 2-1 線形計画問題を解くには…? 46 (𝑛, 𝑚) (10, 10) (20, 20)

    (30, 30) 交点の数 184,756 137,846,528,820 118,264,581,564,861,424 かかる時間 一瞬 2 分 3 年 PC の計算速度は 10~100億回/秒 • 変数が 𝑛 個、制約条件が 𝑚 個の場合を考える • 𝑥𝑖 = 0 などを含めたら 𝑛 + 𝑚 本の直線(or 平面)があるが、𝑛 次元なの でこのうち 𝑛 本を選んだときの共通部分が点になる • すなわち、交点の数は二項係数 𝐶(𝑛 + 𝑚, 𝑛) 個となる 30 変数まで増えると、コンピュータでも無理! ※画像は「フカシギの数え方」より引用
  32. 248 2-1 単体法のイメージ 47 そこで、次のような 単体法 を使うと、効率的に探索が行える。 単体法の手続き 1. 初期解を適当にセットする※

    [例: 𝑥1 , 𝑥2 , … , 𝑥𝑛 = (0, 0, … , 0)] 2. 隣接する「交点」のうち、解が改善するものを適当に選んで移動 3. 解が改善する方向がなくなったら、これが最適解 ※初期解は、𝑚 個の制約条件すべてを満たしていることが望ましい。
  33. 248 2-1 単体法のイメージ(具体例) 49 適当に初期解をセット 隣接する交点へ移動 解が改善しなければ これが最適解 𝑥1 𝑥2

    1 2 3 4 1 2 3 現 + + どちらに行って も改善する 例:𝑥1 + 𝑥2 の最大値を求めたい!
  34. 248 2-1 単体法のイメージ(具体例) 50 適当に初期解をセット 隣接する交点へ移動 解が改善しなければ これが最適解 𝑥1 𝑥2

    1 2 3 4 1 2 3 現 とりあえず上へ 𝑥1 , 𝑥2 = (0.0, 3.3) 例:𝑥1 + 𝑥2 の最大値を求めたい!
  35. 248 2-1 例:𝑥1 + 𝑥2 の最大値を求めたい! 単体法のイメージ(具体例) 51 適当に初期解をセット 隣接する交点へ移動

    解が改善しなければ これが最適解 𝑥1 𝑥2 1 2 3 4 1 2 3 現 - + 右に行かないと 解が改善しない
  36. 248 2-1 単体法のイメージ(具体例) 53 適当に初期解をセット 隣接する交点へ移動 解が改善しなければ これが最適解 𝑥1 𝑥2

    1 2 3 4 1 2 3 現 + - 右に行かないと 解が改善しない 例:𝑥1 + 𝑥2 の最大値を求めたい!
  37. 248 2-1 単体法のイメージ(具体例) 55 適当に初期解をセット 隣接する交点へ移動 解が改善しなければ これが最適解 𝑥1 𝑥2

    1 2 3 4 1 2 3 現 どちらに行っても 改善できない - - 例:𝑥1 + 𝑥2 の最大値を求めたい!
  38. 248 2-1 単体法のイメージ(具体例) 56 適当に初期解をセット 隣接する交点へ移動 解が改善しなければ これが最適解 𝑥1 𝑥2

    1 2 3 4 1 2 3 現 どちらに行っても 改善できない - - 例:𝑥1 + 𝑥2 の最大値を求めたい! 最適解は 𝑥1 , 𝑥2 = (3.0, 2.5) 最大スコアは 5.5 三次元 の場合はどうなるか?
  39. 248 2-1 単体法のイメージ(具体例) 58 適当に初期解をセット 隣接する交点へ移動 解が改善しなければ これが最適解 1 𝑥1

    𝑥2 𝑥3 1 1 現 + 改善する方向を 1 つ選び移動 例:𝑥1 + 𝑥2 + 𝑥3 の最大値を求めたい!
  40. 248 2-1 単体法のイメージ(具体例) 59 適当に初期解をセット 隣接する交点へ移動 解が改善しなければ これが最適解 1 𝑥1

    𝑥2 𝑥3 1 1 現 + 改善する方向を 1 つ選び移動 例:𝑥1 + 𝑥2 + 𝑥3 の最大値を求めたい!
  41. 248 2-1 単体法のイメージ(具体例) 60 適当に初期解をセット 隣接する交点へ移動 解が改善しなければ これが最適解 1 𝑥1

    𝑥2 𝑥3 1 1 現 + 改善する方向を 1 つ選び移動 例:𝑥1 + 𝑥2 + 𝑥3 の最大値を求めたい!
  42. 248 2-1 単体法のイメージ(具体例) 61 適当に初期解をセット 隣接する交点へ移動 解が改善しなければ これが最適解 1 𝑥1

    𝑥2 𝑥3 1 1 現 これ以上 改善できない - - - 例:𝑥1 + 𝑥2 + 𝑥3 の最大値を求めたい!
  43. 248 2-1 単体法のイメージ(具体例) 62 適当に初期解をセット 隣接する交点へ移動 解が改善しなければ これが最適解 1 𝑥1

    𝑥2 𝑥3 1 1 現 これ以上 改善できない - - - 例:𝑥1 + 𝑥2 + 𝑥3 の最大値を求めたい! 最適解は 𝑥1 , 𝑥2 , 𝑥3 = (1, 1, 1) 最大スコアは 3 単体法のイメージはつかめましたか?
  44. 248 2-2 単体法の計算:ステップ 1 68 𝑥1 𝑥2 1 2 3

    4 1 2 3 最大化 数式 𝑥1 + 𝑥2 条件 2𝑥1 + 3𝑥2 ≤ 8 4𝑥1 + 3𝑥2 ≤ 10 ※ 𝑥1 , 𝑥2 は非負 グラフ 以下のような線形計画問題を解きたいとします
  45. 248 2-2 単体法の計算:ステップ 1 69 𝑥1 𝑥2 1 2 3

    4 1 2 3 最大化 数式 𝑥1 + 𝑥2 条件 2𝑥1 + 3𝑥2 + 𝑥3 = 8 4𝑥1 + 3𝑥2 + 𝑥4 = 10 ※ 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 は非負 グラフ 以下のような線形計画問題を解きたいとします まず、スラック変数(余裕を表す)を導入して等式にします 負になったらダメ
  46. 248 2-2 単体法の計算:ステップ 2 71 𝑥1 𝑥2 1 2 3

    4 1 2 3 最大化 数式 𝑥1 + 𝑥2 条件 2𝑥1 + 3𝑥2 + 𝑥3 = 8 4𝑥1 + 3𝑥2 + 𝑥4 = 10 ※ 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 は非負 グラフ 初期位置を原点 𝑥1 = 0, 𝑥2 = 0 に設定し、隣接交点に動かしましょう 現 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 = (0, 0, 8, 10)
  47. 248 2-2 単体法の計算:ステップ 2 72 最大化 数式 𝑥1 + 𝑥2

    条件 ※ 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 は非負 計算しやすいように、𝑥1 , 𝑥2 を右辺に移動します なお、右辺にあるゼロのものを非基底変数、そうでないものを基底変数といいます 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥4 = 10 − 4𝑥1 − 3𝑥2 非基底変数 𝑥1 𝑥2 1 2 3 4 1 2 3 グラフ 現 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 = (0, 0, 8, 10)
  48. 248 2-2 単体法の計算:ステップ 2 73 𝑥1 𝑥2 1 2 3

    4 1 2 3 最大化 数式 𝑥1 + 𝑥2 条件 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥4 = 10 − 4𝑥1 − 3𝑥2 ※ 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 は非負 グラフ 現在右辺の 𝑥1 , 𝑥2 はゼロですが、どちらを増やしてもスコアは上がります ですので、適当に 𝑥1 を選んでギリギリまで増やすことを考えます 現 + 𝑥1 増加
  49. 248 2-2 単体法の計算:ステップ 2 74 最大化 数式 𝑥1 + 𝑥2

    条件 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥4 = 10 − 4𝑥1 − 3𝑥2 ※ 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 は非負 𝑥2 を固定して 𝑥1 だけを増やすと、𝑥1 = 2.5 まで増えます ※ 2 番目の条件がボトルネック 𝑥1 𝑥2 1 2 3 4 1 2 3 グラフ 現 + 𝑥1 増加
  50. 248 2-2 単体法の計算:ステップ 2 75 𝑥1 𝑥2 1 2 3

    4 1 2 3 最大化 数式 𝑥1 + 𝑥2 条件 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥4 = 10 − 4𝑥1 − 3𝑥2 ※ 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 は非負 グラフ 点を移動させると 𝑥4 = 0 になるので、非基底変数が {𝑥2 , 𝑥4 } に変わります 現 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 = (2.5, 0, 3, 0)
  51. 248 2-2 単体法の計算:ステップ 2 76 点を移動させると 𝑥4 = 0 になるので、非基底変数が

    {𝑥2 , 𝑥4 } に変わります ですので、数式の右辺も 𝑥2 , 𝑥4 になるように変えます
  52. 248 2-2 単体法の計算:ステップ 2 77 点を移動させると 𝑥4 = 0 になるので、非基底変数が

    {𝑥2 , 𝑥4 } に変わります ですので、数式の右辺も 𝑥2 , 𝑥4 になるように変えます 数式 最大化 𝑥1 + 𝑥2 条件 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥4 = 10 − 4𝑥1 − 3𝑥2
  53. 248 2-2 単体法の計算:ステップ 2 78 点を移動させると 𝑥4 = 0 になるので、非基底変数が

    {𝑥2 , 𝑥4 } に変わります ですので、数式の右辺も 𝑥2 , 𝑥4 になるように変えます 数式 まずは新しい 𝑥4 を 右辺に持ってきます 最大化 条件 𝑥1 + 𝑥2 𝑥3 = 8 − 2𝑥1 − 3𝑥2 4𝑥1 = 10 − 3𝑥2 − 𝑥4 数式 最大化 𝑥1 + 𝑥2 条件 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥4 = 10 − 4𝑥1 − 3𝑥2
  54. 248 2-2 単体法の計算:ステップ 2 79 点を移動させると 𝑥4 = 0 になるので、非基底変数が

    {𝑥2 , 𝑥4 } に変わります ですので、数式の右辺も 𝑥2 , 𝑥4 になるように変えます 数式 数式 最大化 𝑥1 + 𝑥2 条件 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥4 = 10 − 4𝑥1 − 3𝑥2 𝑥1 + 𝑥2 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥1 = 2.5 − 0.75𝑥2 − 0.25𝑥4 左辺の係数を 1 にします 最大化 条件
  55. 248 2-2 単体法の計算:ステップ 2 80 点を移動させると 𝑥4 = 0 になるので、非基底変数が

    {𝑥2 , 𝑥4 } に変わります ですので、数式の右辺も 𝑥2 , 𝑥4 になるように変えます 数式 数式 最大化 𝑥1 + 𝑥2 条件 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥4 = 10 − 4𝑥1 − 3𝑥2 最大化 条件 𝑥1 を代入 𝑥3 = 8 − 2(2.5 − 0.75𝑥2 − 0.25𝑥4 ) − 3𝑥2 𝑥1 = 2.5 − 0.75𝑥2 − 0.25𝑥4 (2.5 − 0.75𝑥2 − 0.25𝑥4 ) + 𝑥2 𝑥1 を代入
  56. 248 2-2 単体法の計算:ステップ 2 81 点を移動させると 𝑥4 = 0 になるので、非基底変数が

    {𝑥2 , 𝑥4 } に変わります ですので、数式の右辺も 𝑥2 , 𝑥4 になるように変えます 数式 数式 最大化 𝑥1 + 𝑥2 条件 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥4 = 10 − 4𝑥1 − 3𝑥2 最大化 条件 𝑥3 = 8 − (5 − 1.5𝑥2 − 0.5𝑥4 ) − 3𝑥2 𝑥1 = 2.5 − 0.75𝑥2 − 0.25𝑥4 (2.5 − 0.75𝑥2 − 0.25𝑥4 ) + 𝑥2
  57. 248 2-2 単体法の計算:ステップ 2 82 点を移動させると 𝑥4 = 0 になるので、非基底変数が

    {𝑥2 , 𝑥4 } に変わります ですので、数式の右辺も 𝑥2 , 𝑥4 になるように変えます 数式 数式 最大化 𝑥1 + 𝑥2 条件 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥4 = 10 − 4𝑥1 − 3𝑥2 最大化 条件 𝑥3 = 3 − 1.5𝑥2 + 0.5𝑥4 𝑥1 = 2.5 − 0.75𝑥2 − 0.25𝑥4 2.5 + 0.25𝑥2 − 0.25𝑥4 式を整理 式を整理
  58. 248 2-2 単体法の計算:ステップ 3 84 最大化 数式 条件 ※ 𝑥1

    , 𝑥2 , 𝑥3 , 𝑥4 は非負 現在の状況は以下のようになります スコアが増えるように(現在ゼロの)𝑥2 を増やすことを考えましょう 2.5 + 0.25𝑥2 − 0.25𝑥4 𝑥3 = 3 − 1.5𝑥2 + 0.5𝑥4 𝑥1 = 2.5 − 0.75𝑥2 − 0.25𝑥4 𝑥1 𝑥2 1 2 3 4 1 2 3 グラフ 現 + 𝑥2 増加
  59. 248 2-2 単体法の計算:ステップ 3 85 最大化 数式 条件 ※ 𝑥1

    , 𝑥2 , 𝑥3 , 𝑥4 は非負 2.5 + 0.25𝑥2 − 0.25𝑥4 𝑥3 = 3 − 1.5𝑥2 + 0.5𝑥4 𝑥1 = 2.5 − 0.75𝑥2 − 0.25𝑥4 𝑥4 を固定して 𝑥2 だけを増やすと、𝑥2 = 2 まで増えます ※ 1 番目の条件がボトルネック 𝑥1 𝑥2 1 2 3 4 1 2 3 グラフ 現 + 𝑥2 増加
  60. 248 2-2 単体法の計算:ステップ 3 86 最大化 数式 条件 ※ 𝑥1

    , 𝑥2 , 𝑥3 , 𝑥4 は非負 点を移動させると 𝑥3 = 0 になるので、非基底変数が {𝑥3 , 𝑥4 } に変わります 2.5 + 0.25𝑥2 − 0.25𝑥4 𝑥3 = 3 − 1.5𝑥2 + 0.5𝑥4 𝑥1 = 2.5 − 0.75𝑥2 − 0.25𝑥4 𝑥1 𝑥2 1 2 3 4 1 2 3 グラフ 現 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 = (1, 2, 0, 0)
  61. 248 2-2 単体法の計算:ステップ 2 87 点を移動させると 𝑥3 = 0 になるので、非基底変数が

    {𝑥3 , 𝑥4 } に変わります ですので、数式の右辺も 𝑥3 , 𝑥4 になるように変えます
  62. 248 2-2 単体法の計算:ステップ 2 88 点を移動させると 𝑥3 = 0 になるので、非基底変数が

    {𝑥3 , 𝑥4 } に変わります ですので、数式の右辺も 𝑥3 , 𝑥4 になるように変えます 数式 最大化 2.5 + 0.25𝑥2 − 0.25𝑥4 条件 𝑥3 = 3 + 1.5𝑥2 − 0.5𝑥4 𝑥1 = 2.5 − 0.75𝑥2 − 0.25𝑥4
  63. 248 2-2 単体法の計算:ステップ 2 89 点を移動させると 𝑥3 = 0 になるので、非基底変数が

    {𝑥3 , 𝑥4 } に変わります ですので、数式の右辺も 𝑥3 , 𝑥4 になるように変えます 数式 数式 最大化 2.5 + 0.25𝑥2 − 0.25𝑥4 条件 𝑥3 = 3 + 1.5𝑥2 − 0.5𝑥4 𝑥1 = 2.5 − 0.75𝑥2 − 0.25𝑥4 最大化 3 − 0.17𝑥3 − 0.17𝑥4 条件 𝑥2 = 2 − 0.67𝑥3 + 0.33𝑥4 𝑥1 = 1 + 0.5𝑥3 − 0.5𝑥4
  64. 248 2-2 単体法の計算:ステップ 4 91 最大化 数式 条件 ※ 𝑥1

    , 𝑥2 , 𝑥3 , 𝑥4 は非負 現在の状況は以下のようになります どの変数を増やしてもスコアは減ってしまいます! 𝑥1 𝑥2 1 2 3 4 1 2 3 グラフ 現 - - 3 − 0.17𝑥3 − 0.17𝑥4 𝑥2 = 2 − 0.67𝑥3 + 0.33𝑥4 𝑥1 = 1 + 0.5𝑥3 − 0.5𝑥4 𝑥3 増加 𝑥4 増加
  65. 248 2-2 単体法の計算:ステップ 4 92 最大化 数式 条件 ※ 𝑥1

    , 𝑥2 , 𝑥3 , 𝑥4 は非負 現在の状況は以下のようになります どの変数を増やしてもスコアは減ってしまいます! 𝑥1 𝑥2 1 2 3 4 1 2 3 グラフ 現 - - 3 − 0.17𝑥3 − 0.17𝑥4 𝑥2 = 2 − 0.67𝑥3 + 0.33𝑥4 𝑥1 = 1 + 0.5𝑥3 − 0.5𝑥4 𝑥3 増加 𝑥4 増加 これが最適解! 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 = (1, 2, 0, 0)、スコアは 3
  66. 248 2-2 単体法まとめ 93 ここまで長くなりましたが、まとめると以下のようになります。 非基底変数(ゼロのもの)を少しずつ変えていくイメージです。 手順 A 手順 B

    手順 C 𝑥3 = 8 − 2𝑥1 − 3𝑥2 𝑥4 = 10 − 4𝑥1 − 3𝑥2 初期解を設定した上で スラック変数を導入する スコアが改善する 非基底変数を増やして移動 現 新しい非基底変数を 右辺に持ってくる 𝑥3 = 3 − 1.5𝑥2 − 0.5𝑥4 𝑥1 = 2.5 − 0.8𝑥2 − 0.2𝑥4 存在しなければ最適解
  67. 248 2-3 補足:単体法の問題点 • これまでは、暗黙のうちに初期解を 𝑥1 , 𝑥2 , …

    , 𝑥𝑛 = (0, 0, … , 0) に設定していた • しかし、この初期解が制約条件を満たさず、 単体法が成立しないことも多い 𝑥1 𝑥2 1 2 3 1 2 3 現 94 条件を 満たす領域
  68. 248 2-3 補足:単体法の問題点 • これまでは、暗黙のうちに初期解を 𝑥1 , 𝑥2 , …

    , 𝑥𝑛 = (0, 0, … , 0) に設定していた • しかし、この初期解が制約条件を満たさず、 単体法が成立しないことも多い 𝑥1 𝑥2 1 2 3 1 2 3 現 95 条件を 満たす領域 最初に「条件を満たす初期解」を見つける 二段階単体法を使うと解決! 二段階単体法は、別の線形計画問題を 解いて初期解を見つけてから、元の問 題を解く手法です。 初期解を見つける際には「どれくらい の制約違反までなら許されるか」を表 すパラメータ 𝑥0 を追加することがあ ります。 なお、本スライドでは枚数の都合上、 詳しい説明は割愛させていただきます。
  69. 248 2-3 線形計画問題の応用例 97 1 2 3 4 工場の売上最大化 栄養問題

    最適な価格設定 日程計画問題 世の中の様々な問題は 線形計画問題に帰着することができます
  70. 248 2-3 事例 1:工場の売上最大化 98 木材が 3kg、石材が 4kg あります。以 下の

    2 つの製品を作れるとき、売上は最 大何万円になりますか? ×10kg 製品A 1kg当たり ×20kg ×10kg 製品B 1kg当たり ×10kg
  71. 248 2-3 事例 1:工場の売上最大化 99 各製品を作る量を 𝑥1 , 𝑥2 とする

    木材が 3kg、石材が 4kg あります。以 下の 2 つの製品を作れるとき、売上は最 大何万円になりますか? ×10kg 製品A 1kg当たり ×20kg ×10kg 製品B 1kg当たり ×10kg
  72. 248 2-3 事例 1:工場の売上最大化 100 線形計画 各製品を作る量を 𝑥1 , 𝑥2

    とする 最大化 条件 80𝑥1 + 60𝑥2 売上 木材が 3kg、石材が 4kg あります。以 下の 2 つの製品を作れるとき、売上は最 大何万円になりますか? ×10kg 製品A 1kg当たり ×20kg ×10kg 製品B 1kg当たり ×10kg
  73. 248 2-3 事例 1:工場の売上最大化 101 木材が 3kg、石材が 4kg あります。以 下の

    2 つの製品を作れるとき、売上は最 大何万円になりますか? 線形計画 各製品を作る量を 𝑥1 , 𝑥2 とする 最大化 条件 80𝑥1 + 60𝑥2 売上 10𝑥1 + 10𝑥2 ≤ 3 木材 ×10kg 製品A 1kg当たり ×20kg ×10kg 製品B 1kg当たり ×10kg
  74. 248 2-3 事例 1:工場の売上最大化 102 木材が 3kg、石材が 4kg あります。以 下の

    2 つの製品を作れるとき、売上は最 大何万円になりますか? 線形計画 各製品を作る量を 𝑥1 , 𝑥2 とする 最大化 条件 80𝑥1 + 60𝑥2 売上 10𝑥1 + 10𝑥2 ≤ 3 20𝑥1 + 10𝑥2 ≤ 4 木材 石材 ×10kg 製品A 1kg当たり ×20kg ×10kg 製品B 1kg当たり ×10kg
  75. 248 2-3 事例 1:工場の売上最大化 103 木材が 3kg、石材が 4kg あります。以 下の

    2 つの製品を作れるとき、売上は最 大何万円になりますか? 線形計画 各製品を作る量を 𝑥1 , 𝑥2 とする 最大化 条件 80𝑥1 + 60𝑥2 売上 10𝑥1 + 10𝑥2 ≤ 3 20𝑥1 + 10𝑥2 ≤ 4 木材 石材 ×10kg 製品A 1kg当たり ×20kg ×10kg 製品B 1kg当たり ×10kg 線形計画問題に 帰着できた
  76. 248 2-3 事例 2:栄養問題 104 大学の食堂には以下の 3 つの食品が売ら れています。最小何円で、目標値(赤3/ 緑1/黄5)を稼げますか。

    赤 ¥450 ¥250 ¥150 緑 黄 1.5 点 0.5 点 2.5 点 赤 緑 黄 3.0 点 0.1 点 1.0 点 赤 緑 黄 0.1 点 1.5 点 0.5 点 ※値段と栄養素の点数は 100g 当たり
  77. 248 2-3 事例 2:栄養問題 105 大学の食堂には以下の 3 つの食品が売ら れています。最小何円で、目標値(赤3/ 緑1/黄5)を稼げますか。

    パスタ・肉・野菜の量を 𝑥1 , 𝑥2 , 𝑥3 と する(単位は 100 グラム) 赤 ¥450 ¥250 ¥150 緑 黄 1.5 点 0.5 点 2.5 点 赤 緑 黄 3.0 点 0.1 点 1.0 点 赤 緑 黄 0.1 点 1.5 点 0.5 点 ※値段と栄養素の点数は 100g 当たり
  78. 248 2-3 事例 2:栄養問題 106 大学の食堂には以下の 3 つの食品が売ら れています。最小何円で、目標値(赤3/ 緑1/黄5)を稼げますか。

    線形計画 条件 450𝑥1 + 250𝑥2 + 150𝑥3 赤 ¥450 ¥250 ¥150 緑 黄 1.5 点 0.5 点 2.5 点 赤 緑 黄 3.0 点 0.1 点 1.0 点 赤 緑 黄 0.1 点 1.5 点 0.5 点 ※値段と栄養素の点数は 100g 当たり 最小化 パスタ・肉・野菜の量を 𝑥1 , 𝑥2 , 𝑥3 と する(単位は 100 グラム)
  79. 248 2-3 事例 2:栄養問題 107 大学の食堂には以下の 3 つの食品が売ら れています。最小何円で、目標値(赤3/ 緑1/黄5)を稼げますか。

    線形計画 最小化 条件 450𝑥1 + 250𝑥2 + 150𝑥3 1.5𝑥1 + 3.0𝑥2 + 0.1𝑥3 ≥ 3 赤 緑 黄 1.5 点 0.5 点 2.5 点 赤 緑 黄 3.0 点 0.1 点 1.0 点 赤 緑 黄 0.1 点 1.5 点 0.5 点 ※値段と栄養素の点数は 100g 当たり ¥450 ¥250 ¥150 パスタ・肉・野菜の量を 𝑥1 , 𝑥2 , 𝑥3 と する(単位は 100 グラム) 赤
  80. 248 2-3 事例 2:栄養問題 108 大学の食堂には以下の 3 つの食品が売ら れています。最小何円で、目標値(赤3/ 緑1/黄5)を稼げますか。

    線形計画 条件 450𝑥1 + 250𝑥2 + 150𝑥3 1.5𝑥1 + 3.0𝑥2 + 0.1𝑥3 ≥ 3 0.5𝑥1 + 0.1𝑥2 + 1.5𝑥3 ≥ 1 赤 緑 黄 1.5 点 0.5 点 2.5 点 赤 緑 黄 3.0 点 0.1 点 1.0 点 赤 緑 黄 0.1 点 1.5 点 0.5 点 ※値段と栄養素の点数は 100g 当たり 最小化 ¥450 ¥250 ¥150 パスタ・肉・野菜の量を 𝑥1 , 𝑥2 , 𝑥3 と する(単位は 100 グラム) 緑 赤
  81. 248 2-3 事例 2:栄養問題 109 大学の食堂には以下の 3 つの食品が売ら れています。最小何円で、目標値(赤3/ 緑1/黄5)を稼げますか。

    線形計画 条件 450𝑥1 + 250𝑥2 + 150𝑥3 1.5𝑥1 + 3.0𝑥2 + 0.1𝑥3 ≥ 3 0.5𝑥1 + 0.1𝑥2 + 1.5𝑥3 ≥ 1 2.5𝑥1 + 1.0𝑥2 + 0.5𝑥3 ≥ 5 赤 ¥450 ¥250 ¥150 緑 黄 1.5 点 0.5 点 2.5 点 赤 緑 黄 3.0 点 0.1 点 1.0 点 赤 緑 黄 0.1 点 1.5 点 0.5 点 ※値段と栄養素の点数は 100g 当たり 最小化 黄 緑 赤 パスタ・肉・野菜の量を 𝑥1 , 𝑥2 , 𝑥3 と する(単位は 100 グラム)
  82. 248 2-3 事例 2:栄養問題 110 大学の食堂には以下の 3 つの食品が売ら れています。最小何円で、目標値(赤3/ 緑1/黄5)を稼げますか。

    線形計画 条件 450𝑥1 + 250𝑥2 + 150𝑥3 1.5𝑥1 + 3.0𝑥2 + 0.1𝑥3 ≥ 3 0.5𝑥1 + 0.1𝑥2 + 1.5𝑥3 ≥ 1 2.5𝑥1 + 1.0𝑥2 + 0.5𝑥3 ≥ 5 赤 ¥450 ¥250 ¥150 緑 黄 1.5 点 0.5 点 2.5 点 赤 緑 黄 3.0 点 0.1 点 1.0 点 赤 緑 黄 0.1 点 1.5 点 0.5 点 ※値段と栄養素の点数は 100g 当たり 最小化 黄 緑 赤 パスタ・肉・野菜の量を 𝑥1 , 𝑥2 , 𝑥3 と する(単位は 100 グラム) 線形計画問題に 帰着できた
  83. 248 2-3 事例 3:最適な価格設定 113 3 人の店員が「リンゴ〇個とミカン△個 で□ドルがいい!」と言いました。最大 誤差を最小にする価格設定は? リンゴ

    ミカン 価格 店員A 2個 3個 $1.00 店員B 3個 4個 $1.20 店員C 5個 1個 $1.50 リンゴを 𝑥1 ドル、ミカンを 𝑥2 ドル 許される誤差の最大を 𝑥3 ドルとする 線形計画 条件 𝑥3 最小化
  84. 248 2-3 事例 3:最適な価格設定 114 3 人の店員が「リンゴ〇個とミカン△個 で□ドルがいい!」と言いました。最大 誤差を最小にする価格設定は? リンゴ

    ミカン 価格 店員A 2個 3個 $1.00 店員B 3個 4個 $1.20 店員C 5個 1個 $1.50 リンゴを 𝑥1 ドル、ミカンを 𝑥2 ドル 許される誤差の最大を 𝑥3 ドルとする 線形計画 条件 𝑥3 最小化 2𝑥1 + 3𝑥2 ≥ 1.00 − 𝑥3 2𝑥1 + 3𝑥2 ≤ 1.00 + 𝑥3
  85. 248 2-3 事例 3:最適な価格設定 115 3 人の店員が「リンゴ〇個とミカン△個 で□ドルがいい!」と言いました。最大 誤差を最小にする価格設定は? リンゴ

    ミカン 価格 店員A 2個 3個 $1.00 店員B 3個 4個 $1.20 店員C 5個 1個 $1.50 リンゴを 𝑥1 ドル、ミカンを 𝑥2 ドル 許される誤差の最大を 𝑥3 ドルとする 線形計画 条件 𝑥3 最小化 2𝑥1 + 3𝑥2 ≥ 1.00 − 𝑥3 2𝑥1 + 3𝑥2 ≤ 1.00 + 𝑥3 3𝑥1 + 4𝑥2 ≥ 1.20 − 𝑥3 3𝑥1 + 4𝑥2 ≤ 1.20 + 𝑥3
  86. 248 2-3 事例 3:最適な価格設定 116 3 人の店員が「リンゴ〇個とミカン△個 で□ドルがいい!」と言いました。最大 誤差を最小にする価格設定は? リンゴ

    ミカン 価格 店員A 2個 3個 $1.00 店員B 3個 4個 $1.20 店員C 5個 1個 $1.50 リンゴを 𝑥1 ドル、ミカンを 𝑥2 ドル 許される誤差の最大を 𝑥3 ドルとする 線形計画 条件 𝑥3 最小化 2𝑥1 + 3𝑥2 ≥ 1.00 − 𝑥3 2𝑥1 + 3𝑥2 ≤ 1.00 + 𝑥3 3𝑥1 + 4𝑥2 ≥ 1.20 − 𝑥3 3𝑥1 + 4𝑥2 ≤ 1.20 + 𝑥3 5𝑥1 + 𝑥2 ≥ 1.50 − 𝑥3 5𝑥1 + 𝑥2 ≤ 1.50 + 𝑥3
  87. 248 2-3 事例 3:最適な価格設定 117 3 人の店員が「リンゴ〇個とミカン△個 で□ドルがいい!」と言いました。最大 誤差を最小にする価格設定は? リンゴ

    ミカン 価格 店員A 2個 3個 $1.00 店員B 3個 4個 $1.20 店員C 5個 1個 $1.50 リンゴを 𝑥1 ドル、ミカンを 𝑥2 ドル 許される誤差の最大を 𝑥3 ドルとする 線形計画 条件 𝑥3 最小化 2𝑥1 + 3𝑥2 ≥ 1.00 − 𝑥3 2𝑥1 + 3𝑥2 ≤ 1.00 + 𝑥3 3𝑥1 + 4𝑥2 ≥ 1.20 − 𝑥3 3𝑥1 + 4𝑥2 ≤ 1.20 + 𝑥3 5𝑥1 + 𝑥2 ≥ 1.50 − 𝑥3 5𝑥1 + 𝑥2 ≤ 1.50 + 𝑥3 線形計画問題に 帰着できた
  88. 248 2-3 その他の応用例 日程計画問題 • 仕事が 𝑁 個あり、仕事 𝑖 (1

    ≤ 𝑖 ≤ 𝑁) には 𝑝𝑖 日かかる。 • 仕事 𝑖 (1 ≤ 𝑖 ≤ 𝑁) を早く終わらせるには、1 日当たり 𝑔𝑖 円必要。 • 全部の仕事を 𝑇 日間で終わらせるには、何円必要か? • ただし「仕事〇〇をしてから仕事△△をする」といった依存関係も与えられる。 その他の有名な問題も線形計画に帰着できる • 最短経路問題、最大フロー問題、輸送問題、回帰問題、etc. 118
  89. 248 2-4 制約なし最適化問題 120 関数 𝑓(𝑥) の最小値を求めてください。 ※関数は二変数関数 𝑓(𝑥1 ,

    𝑥2 ) や多変数関数 𝑓(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) になることもあります 最小値(これを求めたい) 𝑥 𝑓(𝑥)
  90. 248 2-4 方法 1:微分法を使う 121 まず、𝑓′ 𝑥 = 0 を満たす

    𝑥 を列挙する方法が考えられる しかし関数が複雑な場合、列挙するのは難しい(特に多変数関数のとき) 𝑥 𝑓(𝑥) 傾き=0 で 最小値 例: 𝑓 𝑥 = 𝑥4 − 2𝑥2 + 1 の最小値は? • 微分すると 𝑓′ 𝑥 = 4𝑥3 − 4𝑥 • 𝑓′ 𝑥 = 0 の解は 𝑥 = −1, ±0, +1 最小値の候補は 𝑥 = −1, ±0, 1 なので… • 𝑥 = −1 のとき: 𝑓 𝑥 = 0 • 𝑥 = ±0 のとき: 𝑓 𝑥 = 1 • 𝑥 = +1 のとき: 𝑓 𝑥 = 0 →求める最小値は 1 です!
  91. 248 2-4 方法 2:勾配降下法を使う 123 勾配降下法のアルゴリズムは以下の通り: 1. 定数 𝛼 と初期位置

    𝑥 を決める。 2. その後、𝑥 の値に 𝛼 ×(地点 𝑥 における傾き)を減算する、という操作を繰り返す。
  92. 248 2-4 方法 2:勾配降下法を使う 124 勾配降下法のアルゴリズムは以下の通り: 1. 定数 𝛼 と初期位置

    𝑥 を決める。 2. その後、𝑥 の値に 𝛼 ×(地点 𝑥 における傾き)を減算する、という操作を繰り返す。 𝑓 𝑥 = 𝑥4 − 𝑥 + 1 の場合 • 𝛼 = 0.1 に設定すると… • 0 回目: 𝑥 = 1.00, 𝑓 𝑥 = 1.00 𝑥 𝑓(𝑥) 1.00 0.60 0.20 0.20 0.60 1.00 1.40 初期解を適当に 1.00 に設定
  93. 248 2-4 方法 2:勾配降下法を使う 125 勾配降下法のアルゴリズムは以下の通り: 1. 定数 𝛼 と初期位置

    𝑥 を決める。 2. その後、𝑥 の値に 𝛼 ×(地点 𝑥 における傾き)を減算する、という操作を繰り返す。 𝑓 𝑥 = 𝑥4 − 𝑥 + 1 の場合 • 𝛼 = 0.1 に設定すると… • 0 回目: 𝑥 = 1.00, 𝑓 𝑥 = 1.00 𝑥 𝑓(𝑥) 1.00 0.60 0.20 0.20 0.60 1.00 1.40 傾き 3.00 → 0.30 減少 -0.30
  94. 248 2-4 方法 2:勾配降下法を使う 126 勾配降下法のアルゴリズムは以下の通り: 1. 定数 𝛼 と初期位置

    𝑥 を決める。 2. その後、𝑥 の値に 𝛼 ×(地点 𝑥 における傾き)を減算する、という操作を繰り返す。 𝑓 𝑥 = 𝑥4 − 𝑥 + 1 の場合 • 𝛼 = 0.1 に設定すると… • 0 回目: 𝑥 = 1.00, 𝑓 𝑥 = 1.00 • 1 回目: 𝑥 = 0.70, 𝑓 𝑥 = 0.54 𝑥 𝑓(𝑥) 1.00 0.60 0.20 0.20 0.60 1.00 1.40 𝑥 = 0.70 に 移動 -0.30
  95. 248 2-4 方法 2:勾配降下法を使う 127 勾配降下法のアルゴリズムは以下の通り: 1. 定数 𝛼 と初期位置

    𝑥 を決める。 2. その後、𝑥 の値に 𝛼 ×(地点 𝑥 における傾き)を減算する、という操作を繰り返す。 𝑓 𝑥 = 𝑥4 − 𝑥 + 1 の場合 • 𝛼 = 0.1 に設定すると… • 0 回目: 𝑥 = 1.00, 𝑓 𝑥 = 1.00 • 1 回目: 𝑥 = 0.70, 𝑓 𝑥 = 0.54 𝑥 𝑓(𝑥) 1.00 0.60 0.20 0.20 0.60 1.00 1.40 傾き 0.38 → 0.04 減少 -0.30 -0.04
  96. 248 2-4 方法 2:勾配降下法を使う 128 勾配降下法のアルゴリズムは以下の通り: 1. 定数 𝛼 と初期位置

    𝑥 を決める。 2. その後、𝑥 の値に 𝛼 ×(地点 𝑥 における傾き)を減算する、という操作を繰り返す。 𝑓 𝑥 = 𝑥4 − 𝑥 + 1 の場合 • 𝛼 = 0.1 に設定すると… • 0 回目: 𝑥 = 1.00, 𝑓 𝑥 = 1.00 • 1 回目: 𝑥 = 0.70, 𝑓 𝑥 = 0.54 • 2 回目: 𝑥 = 0.66, 𝑓 𝑥 = 0.53 𝑥 𝑓(𝑥) 1.00 0.60 0.20 0.20 0.60 1.00 1.40 𝑥 = 0.66 に 移動 -0.30 -0.04
  97. 248 2-4 方法 2:勾配降下法を使う 129 勾配降下法のアルゴリズムは以下の通り: 1. 定数 𝛼 と初期位置

    𝑥 を決める。 2. その後、𝑥 の値に 𝛼 ×(地点 𝑥 における傾き)を減算する、という操作を繰り返す。 𝑓 𝑥 = 𝑥4 − 𝑥 + 1 の場合 • 𝛼 = 0.1 に設定すると… • 0 回目: 𝑥 = 1.00, 𝑓 𝑥 = 1.00 • 1 回目: 𝑥 = 0.70, 𝑓 𝑥 = 0.54 • 2 回目: 𝑥 = 0.66, 𝑓 𝑥 = 0.53 𝑥 𝑓(𝑥) 1.00 0.60 0.20 0.20 0.60 1.00 1.40 傾き 0.14 → 0.01 減少 -0.30 -0.04 -0.01
  98. 248 2-4 方法 2:勾配降下法を使う 130 勾配降下法のアルゴリズムは以下の通り: 1. 定数 𝛼 と初期位置

    𝑥 を決める。 2. その後、𝑥 の値に 𝛼 ×(地点 𝑥 における傾き)を減算する、という操作を繰り返す。 𝑓 𝑥 = 𝑥4 − 𝑥 + 1 の場合 • 𝛼 = 0.1 に設定すると… • 0 回目: 𝑥 = 1.00, 𝑓 𝑥 = 1.00 • 1 回目: 𝑥 = 0.70, 𝑓 𝑥 = 0.54 • 2 回目: 𝑥 = 0.66, 𝑓 𝑥 = 0.53 • 3 回目: 𝑥 = 0.65, 𝑓 𝑥 = 0.53 𝑥 𝑓(𝑥) 1.00 0.60 0.20 0.20 0.60 1.00 1.40 𝑥 = 0.65 に 移動 -0.30 -0.04 -0.01
  99. 248 2-4 方法 2:勾配降下法を使う 131 勾配降下法のアルゴリズムは以下の通り: 1. 定数 𝛼 と初期位置

    𝑥 を決める。 2. その後、𝑥 の値に 𝛼 ×(地点 𝑥 における傾き)を減算する、という操作を繰り返す。 𝑓 𝑥 = 𝑥4 − 𝑥 + 1 の場合 • 𝛼 = 0.1 に設定すると… • 0 回目: 𝑥 = 1.00, 𝑓 𝑥 = 1.00 • 1 回目: 𝑥 = 0.70, 𝑓 𝑥 = 0.54 • 2 回目: 𝑥 = 0.66, 𝑓 𝑥 = 0.53 • 3 回目: 𝑥 = 0.65, 𝑓 𝑥 = 0.53 𝑥 𝑓(𝑥) 1.00 0.60 0.20 0.20 0.60 1.00 1.40 𝑥 = 0.65 に 移動 -0.30 -0.04 -0.01 急速に最小値に 近づいていく
  100. 248 2-4 制約付き最適化問題 133 • 最後に、制約なし最適化問題(関数の最大値を求める問題)に制約を付けた以 下のような問題を 制約付き最適化問題 という。 •

    かなり難しいが、ペナルティ関数法などを使うと解ける 問題例 1 最小化 条件 2𝑥2 + 2𝑦2 + 𝑥𝑦 𝑥 + 2𝑦 ≤ −1 制約を 満たす範囲 最小値
  101. 248 3-0 離散最適化問題の例 137 たとえば、カードをいくつか選んで合計を 100 にできるだけ近づ ける問題を考える 10 30

    57 38 75 「0.5 枚選ぶ」 は許されない とびとびの値しか選べないので 離散最適化問題
  102. 248 3-0 離散最適化問題の代表的解法 139 1 2 3 4 有名なアルゴリズム で効率的に解く

    山登り法などを 利用する 近似解法で 妥協する 整数計画 ソルバーに頼る 本講義では、代表的な解法として 4 つを紹介します 𝜋 = 3
  103. 248 3-1 例 1:紙幣の問題 146 そこで、次のようなアルゴリズムを考える • 残額が 10000 円を下回るまで、10000

    円札を使う。 • 残額が 5000 円を下回るまで、5000 円札を使う • 最後に、残った金額を 1000 円札で支払う
  104. 248 3-1 例 1:紙幣の問題 147 そこで、次のようなアルゴリズムを考える(下図は 29000 円の例) • 残額が

    10000 円を下回るまで、10000 円札を使う。 • 残額が 5000 円を下回るまで、5000 円札を使う • 最後に、残った金額を 1000 円札で支払う 残額 29000円
  105. 248 3-1 例 1:紙幣の問題 148 そこで、次のようなアルゴリズムを考える(下図は 29000 円の例) • 残額が

    10000 円を下回るまで、10000 円札を使う。 • 残額が 5000 円を下回るまで、5000 円札を使う • 最後に、残った金額を 1000 円札で支払う 残額 19000円 10000円
  106. 248 3-1 例 1:紙幣の問題 149 そこで、次のようなアルゴリズムを考える(下図は 29000 円の例) • 残額が

    10000 円を下回るまで、10000 円札を使う。 • 残額が 5000 円を下回るまで、5000 円札を使う • 最後に、残った金額を 1000 円札で支払う 残額 9000円 10000円 10000円 10000 円を下回った!
  107. 248 3-1 例 1:紙幣の問題 150 そこで、次のようなアルゴリズムを考える(下図は 29000 円の例) • 残額が

    10000 円を下回るまで、10000 円札を使う。 • 残額が 5000 円を下回るまで、5000 円札を使う • 最後に、残った金額を 1000 円札で支払う 残額 4000円 10000円 10000円 5000円 5000 円を下回った!
  108. 248 3-1 例 1:紙幣の問題 151 そこで、次のようなアルゴリズムを考える(下図は 29000 円の例) • 残額が

    10000 円を下回るまで、10000 円札を使う。 • 残額が 5000 円を下回るまで、5000 円札を使う • 最後に、残った金額を 1000 円札で支払う 残額 3000円 10000円 10000円 5000円 1000円
  109. 248 3-1 例 1:紙幣の問題 152 そこで、次のようなアルゴリズムを考える(下図は 29000 円の例) • 残額が

    10000 円を下回るまで、10000 円札を使う。 • 残額が 5000 円を下回るまで、5000 円札を使う • 最後に、残った金額を 1000 円札で支払う 残額 2000円 10000円 10000円 5000円 1000円 1000円
  110. 248 3-1 例 1:紙幣の問題 153 そこで、次のようなアルゴリズムを考える(下図は 29000 円の例) • 残額が

    10000 円を下回るまで、10000 円札を使う。 • 残額が 5000 円を下回るまで、5000 円札を使う • 最後に、残った金額を 1000 円札で支払う 残額 1000円 10000円 10000円 5000円 1000円 1000円 1000円
  111. 248 3-1 例 1:紙幣の問題 154 そこで、次のようなアルゴリズムを考える(下図は 29000 円の例) • 残額が

    10000 円を下回るまで、10000 円札を使う。 • 残額が 5000 円を下回るまで、5000 円札を使う • 最後に、残った金額を 1000 円札で支払う 残額 0円 10000円 10000円 5000円 1000円 1000円 1000円 1000円
  112. 248 3-1 例 1:紙幣の問題 155 そこで、次のようなアルゴリズムを考える(下図は 29000 円の例) • 残額が

    10000 円を下回るまで、10000 円札を使う。 • 残額が 5000 円を下回るまで、5000 円札を使う • 最後に、残った金額を 1000 円札で支払う 残額 0円 10000円 10000円 5000円 1000円 1000円 1000円 1000円 最適解(7 枚)で 支払えた!
  113. 248 3-1 何故この方法で上手くいく? 156 • 1000 円札を 5 枚以上使っている •

    5000 円札を 2 枚以上使っている • 上記のいずれかを満たすとき、明らかに枚数を減らせる
  114. 248 3-1 何故この方法で上手くいく? 157 • 1000 円札を 5 枚以上使っている •

    5000 円札を 2 枚以上使っている • 上記のいずれかを満たすとき、明らかに枚数を減らせる 10000円 10000円 1000円 1000円 1000円 1000円 1000円 10000円 10000円 5000円 -4 枚 1000 円札 2 枚を 5000 円札に交換!
  115. 248 3-1 何故この方法で上手くいく? 158 • 1000 円札を 5 枚以上使っている •

    5000 円札を 2 枚以上使っている • 上記のいずれかを満たすとき、明らかに枚数を減らせる 10000円 10000円 5000円 5000円 1000円 10000円 10000円 10000円 -1 枚 5000 円札 2 枚を 10000 円札に交換! 1000円
  116. 248 3-1 何故この方法で上手くいく? 159 • 1000 円札を 5 枚以上使っている •

    5000 円札を 2 枚以上使っている • 上記のいずれかを満たすとき、明らかに枚数を減らせる • 一方で、1000 円札 4 枚以下、5000 円札 1 枚以下で支払う方法は 1 通り しかない(+ 貪欲法はその条件を満たす) 貪欲法こそが最適!
  117. 248 3-1 アルゴリズム 2:動的計画法 • 小さい問題に分解し、前の結 果を利用して答えを求める設 計技法 • イメージとしては、フィボ

    ナッチ数列などを、規則性に 従って 1 つずつ求めていくよ うな感じ 161 1 1 1 1 2 1 1 2 3 1 1 2 3 5 1 1 2 3 5 8 1 1 2 3 5 8 13 1 + 1 = 2 1 + 2 = 3 2 + 3 = 5 3 + 5 = 8 5 + 8 = 13
  118. 248 3-1 例 2:最適な移動経路 162 以下のような地図が与えられます。 地点 1 から地点 5

    まで、最短何分で移動できますか? 地点 2 地点 1 地点 3 地点 4 地点 5 2 分 3 分 1 分 6 分 4 分 7 分 9 分
  119. 248 3-1 例 2:最適な移動経路 163 以下のような地図が与えられます。 地点 1 から地点 5

    まで、最短何分で移動できますか? 地点 2 地点 1 地点 3 地点 4 地点 5 2 分 3 分 1 分 6 分 4 分 7 分 9 分 この経路で行くと 13 分かかる
  120. 248 3-1 例 2:最適な移動経路 165 いきなり答えを求めるのは難しいので、以下の順番で 1 つずつ考える • 地点

    1→1 に移動するための最短時間 dp[1] • 地点 1→2 に移動するための最短時間 dp[2] • 地点 1→3 に移動するための最短時間 dp[3] • 地点 1→4 に移動するための最短時間 dp[4] • 地点 1→5 に移動するための最短時間 dp[5]
  121. 248 3-1 例 2:最適な移動経路 166 いきなり答えを求めるのは難しいので、以下の順番で 1 つずつ考える • 地点

    1→1 に移動するための最短時間 dp[1] • 地点 1→2 に移動するための最短時間 dp[2] • 地点 1→3 に移動するための最短時間 dp[3] • 地点 1→4 に移動するための最短時間 dp[4] • 地点 1→5 に移動するための最短時間 dp[5] 地点 2 dp 2 = ? 地点 1 dp 1 = 0 地点 3 dp 3 = ? 地点 4 dp 4 = ? 地点 5 dp 5 = ? 2 分 3 分 1 分 6 分 4 分 7 分 9 分 移動しなくても たどり着けるので 最短 0 分
  122. 248 3-1 例 2:最適な移動経路 167 いきなり答えを求めるのは難しいので、以下の順番で 1 つずつ考える • 地点

    1→1 に移動するための最短時間 dp[1] • 地点 1→2 に移動するための最短時間 dp[2] • 地点 1→3 に移動するための最短時間 dp[3] • 地点 1→4 に移動するための最短時間 dp[4] • 地点 1→5 に移動するための最短時間 dp[5] 地点 2 dp 2 = 2 地点 1 dp 1 = 0 地点 3 dp 3 = ? 地点 4 dp 4 = ? 地点 5 dp 5 = ? 2 分 3 分 1 分 6 分 4 分 7 分 9 分 1→2 に直接行く しかないので 必要な時間は 2 分
  123. 248 3-1 例 2:最適な移動経路 168 いきなり答えを求めるのは難しいので、以下の順番で 1 つずつ考える • 地点

    1→1 に移動するための最短時間 dp[1] • 地点 1→2 に移動するための最短時間 dp[2] • 地点 1→3 に移動するための最短時間 dp[3] • 地点 1→4 に移動するための最短時間 dp[4] • 地点 1→5 に移動するための最短時間 dp[5] 地点 2 dp 2 = 2 地点 1 dp 1 = 0 地点 3 dp 3 = 4 地点 4 dp 4 = ? 地点 5 dp 5 = ? 2 分 3 分 1 分 6 分 4 分 7 分 9 分 2→3 を通る: 2+3=5分 1→3 を通る: 0+4=4分
  124. 248 3-1 例 2:最適な移動経路 169 いきなり答えを求めるのは難しいので、以下の順番で 1 つずつ考える • 地点

    1→1 に移動するための最短時間 dp[1] • 地点 1→2 に移動するための最短時間 dp[2] • 地点 1→3 に移動するための最短時間 dp[3] • 地点 1→4 に移動するための最短時間 dp[4] • 地点 1→5 に移動するための最短時間 dp[5] 地点 2 dp 2 = 2 地点 1 dp 1 = 0 地点 3 dp 3 = 4 地点 4 dp 4 = 5 地点 5 dp 5 = ? 2 分 3 分 1 分 6 分 4 分 7 分 9 分 3→4 を通る: 4+1=5分 2→4 を通る: 2+7=9分
  125. 248 3-1 例 2:最適な移動経路 170 いきなり答えを求めるのは難しいので、以下の順番で 1 つずつ考える • 地点

    1→1 に移動するための最短時間 dp[1] • 地点 1→2 に移動するための最短時間 dp[2] • 地点 1→3 に移動するための最短時間 dp[3] • 地点 1→4 に移動するための最短時間 dp[4] • 地点 1→5 に移動するための最短時間 dp[5] 地点 2 dp 2 = 2 地点 1 dp 1 = 0 地点 3 dp 3 = 4 地点 4 dp 4 = 5 地点 5 dp 5 = 11 2 分 3 分 1 分 6 分 4 分 7 分 9 分 4→5 を通る: 5+6=11分 3→5 を通る: 4+9=13分
  126. 248 3-1 例 2:最適な移動経路 171 いきなり答えを求めるのは難しいので、以下の順番で 1 つずつ考える • 地点

    1→1 に移動するための最短時間 dp[1] • 地点 1→2 に移動するための最短時間 dp[2] • 地点 1→3 に移動するための最短時間 dp[3] • 地点 1→4 に移動するための最短時間 dp[4] • 地点 1→5 に移動するための最短時間 dp[5] 地点 2 dp 2 = 2 地点 1 dp 1 = 0 地点 3 dp 3 = 4 地点 4 dp 4 = 5 地点 5 dp 5 = 11 2 分 3 分 1 分 6 分 4 分 7 分 9 分 4→5 を通る: 5+6=11分 3→5 を通る: 4+9=13分 最短 11 分で移動できる! ※最適な移動経路は、地点 1→3→4→5
  127. 248 3-2 アルゴリズムの限界 177 分割問題 整数 𝐴1 , 𝐴2 ,

    … , 𝐴𝑁 を 2 つのグループに分割してください。 ただし、各グループの総和の差をできる限り小さくしてください。 1 2 3 4 5 1 2 3 4 5 赤の総和 = 8 青の総和 = 7
  128. 248 3-2 アルゴリズムの限界 178 分割問題 整数 𝐴1 , 𝐴2 ,

    … , 𝐴𝑁 を 2 つのグループに分割してください。 ただし、各グループの総和の差をできる限り小さくしてください。 1 2 3 4 5 1 2 3 4 5 赤の総和 = 8 青の総和 = 7 このような問題は NP 完全 効率的に最適解を出すのが難しいとされている
  129. 248 3-2 例 1:分割問題 181 差 = 90 5 8

    14 28 30 23 48 44 合計 55 合計 145 「異なるグループにある 2 つの整数をランダムに選び、解が良くなれば交 換する」という操作を繰り返すと…?
  130. 248 3-2 例 1:分割問題 182 差 = 90 5 8

    14 28 30 23 48 44 合計 55 合計 145 交換すると改善 →採用 「異なるグループにある 2 つの整数をランダムに選び、解が良くなれば交 換する」という操作を繰り返すと…?
  131. 248 3-2 例 1:分割問題 183 差 = 12 44 8

    14 28 30 23 48 5 合計 94 合計 106 「異なるグループにある 2 つの整数をランダムに選び、解が良くなれば交 換する」という操作を繰り返すと…?
  132. 248 3-2 例 1:分割問題 184 差 = 12 44 8

    14 28 30 23 48 5 合計 94 合計 106 交換すると悪化 →不採用 「異なるグループにある 2 つの整数をランダムに選び、解が良くなれば交 換する」という操作を繰り返すと…?
  133. 248 3-2 例 1:分割問題 185 差 = 12 44 8

    14 28 30 23 48 5 合計 94 合計 106 「異なるグループにある 2 つの整数をランダムに選び、解が良くなれば交 換する」という操作を繰り返すと…?
  134. 248 3-2 例 1:分割問題 186 差 = 12 44 8

    14 28 30 23 48 5 合計 94 合計 106 交換すると改善 →採用 「異なるグループにある 2 つの整数をランダムに選び、解が良くなれば交 換する」という操作を繰り返すと…?
  135. 248 3-2 例 1:分割問題 187 差 = 6 44 8

    23 28 30 14 48 5 合計 103 合計 97 「異なるグループにある 2 つの整数をランダムに選び、解が良くなれば交 換する」という操作を繰り返すと…?
  136. 248 3-2 例 1:分割問題 188 差 = 6 44 8

    23 28 30 14 48 5 合計 103 合計 97 交換すると改善 →採用 「異なるグループにある 2 つの整数をランダムに選び、解が良くなれば交 換する」という操作を繰り返すと…?
  137. 248 3-2 例 1:分割問題 189 差 = 0 44 5

    23 28 30 14 48 8 合計 100 合計 100 「異なるグループにある 2 つの整数をランダムに選び、解が良くなれば交 換する」という操作を繰り返すと…?
  138. 248 3-2 例 2:巡回セールスマン問題 194 1 2 6 3 5

    4 赤い辺を 付け替える 「解が良くなるように 2 つの辺を付け替える」という操作を繰り返すと…? (このような方法は 2-opt と呼ばれる)
  139. 248 3-2 例 2:巡回セールスマン問題 195 1 2 6 3 5

    4 1 2 6 3 5 4 「解が良くなるように 2 つの辺を付け替える」という操作を繰り返すと…? (このような方法は 2-opt と呼ばれる)
  140. 248 3-2 例 2:巡回セールスマン問題 196 1 2 6 3 5

    4 1 2 6 3 5 4 赤い辺を 付け替える 「解が良くなるように 2 つの辺を付け替える」という操作を繰り返すと…? (このような方法は 2-opt と呼ばれる)
  141. 248 3-2 例 2:巡回セールスマン問題 197 1 2 6 3 5

    4 1 2 6 3 5 4 1 2 6 3 5 4 「解が良くなるように 2 つの辺を付け替える」という操作を繰り返すと…? (このような方法は 2-opt と呼ばれる)
  142. 248 3-2 例 2:巡回セールスマン問題 198 1 2 6 3 5

    4 1 2 6 3 5 4 1 2 6 3 5 4 赤い辺を 付け替える 「解が良くなるように 2 つの辺を付け替える」という操作を繰り返すと…? (このような方法は 2-opt と呼ばれる)
  143. 248 3-2 例 2:巡回セールスマン問題 199 1 2 6 3 5

    4 1 2 6 3 5 4 1 2 6 3 5 4 1 2 6 3 5 4 「解が良くなるように 2 つの辺を付け替える」という操作を繰り返すと…? (このような方法は 2-opt と呼ばれる)
  144. 248 3-2 例 2:巡回セールスマン問題 200 1 2 6 3 5

    4 1 2 6 3 5 4 1 2 6 3 5 4 1 2 6 3 5 4 赤い辺を 付け替える 「解が良くなるように 2 つの辺を付け替える」という操作を繰り返すと…? (このような方法は 2-opt と呼ばれる)
  145. 248 3-2 例 2:巡回セールスマン問題 201 1 2 6 3 5

    4 1 2 6 3 5 4 1 2 6 3 5 4 1 2 6 3 5 4 1 2 6 3 5 4 「解が良くなるように 2 つの辺を付け替える」という操作を繰り返すと…? (このような方法は 2-opt と呼ばれる)
  146. 248 3-3 例 1:ビンパッキング問題 209 この問題に対して、次のアルゴリズム(First Fit 法)を考える: • 1

    つずつ順番に荷物を詰めていく。 • 荷物は、詰められる中で最も番号が小さい箱に詰める。
  147. 248 3-3 例 1:ビンパッキング問題 210 1 2 3 4 5

    2 3 3 4 4 6 7 9 2 この問題に対して、次のアルゴリズム(First Fit 法)を考える: • 1 つずつ順番に荷物を詰めていく。 • 荷物は、詰められる中で最も番号が小さい箱に詰める。
  148. 248 3-3 例 1:ビンパッキング問題 211 1 2 3 4 5

    2 3 3 4 4 6 7 9 2 9 箱 1 には 詰められない この問題に対して、次のアルゴリズム(First Fit 法)を考える: • 1 つずつ順番に荷物を詰めていく。 • 荷物は、詰められる中で最も番号が小さい箱に詰める。
  149. 248 3-3 例 1:ビンパッキング問題 212 1 2 3 4 5

    2 3 3 4 4 6 7 9 2 9 6 この問題に対して、次のアルゴリズム(First Fit 法)を考える: • 1 つずつ順番に荷物を詰めていく。 • 荷物は、詰められる中で最も番号が小さい箱に詰める。
  150. 248 3-3 例 1:ビンパッキング問題 213 1 2 3 4 5

    2 3 3 4 4 6 7 9 2 9 6 3 箱 2 には 詰められない この問題に対して、次のアルゴリズム(First Fit 法)を考える: • 1 つずつ順番に荷物を詰めていく。 • 荷物は、詰められる中で最も番号が小さい箱に詰める。
  151. 248 3-3 例 1:ビンパッキング問題 214 1 2 3 4 5

    2 3 3 4 4 6 7 9 2 9 6 3 4 この問題に対して、次のアルゴリズム(First Fit 法)を考える: • 1 つずつ順番に荷物を詰めていく。 • 荷物は、詰められる中で最も番号が小さい箱に詰める。
  152. 248 3-3 例 1:ビンパッキング問題 215 1 2 3 4 5

    2 3 3 4 4 6 7 9 2 9 6 3 4 3 この問題に対して、次のアルゴリズム(First Fit 法)を考える: • 1 つずつ順番に荷物を詰めていく。 • 荷物は、詰められる中で最も番号が小さい箱に詰める。
  153. 248 3-3 例 1:ビンパッキング問題 216 1 2 3 4 5

    2 3 3 4 4 6 7 9 2 9 6 3 4 3 7 この問題に対して、次のアルゴリズム(First Fit 法)を考える: • 1 つずつ順番に荷物を詰めていく。 • 荷物は、詰められる中で最も番号が小さい箱に詰める。
  154. 248 3-3 例 1:ビンパッキング問題 217 1 2 3 4 5

    2 3 3 4 4 6 7 9 2 9 6 3 4 3 7 4 5 個の箱で 詰められた! この問題に対して、次のアルゴリズム(First Fit 法)を考える: • 1 つずつ順番に荷物を詰めていく。 • 荷物は、詰められる中で最も番号が小さい箱に詰める。
  155. 248 3-3 近似アルゴリズムの精度 219 実は、半分以下しか詰まっていない箱は高々 1 つしか存在しない → 2-近似が保証できる! 7

    9 4 5 3 2 2 7 9 4 5 3 2 2 もし半分以下の箱が 2 つあったら… First Fit 法では 全部左側に 入っているはず!
  156. 248 3-3 この節のまとめ • このように、アルゴリズムによっては 2 倍などの近似精度が保証 できる場合がある • また、2-近似だからといって全てのケースで

    2 倍になるとは限ら ず、平均的なケースでは遥かに良い近似精度になることも 220 少ない計算量である程度の解が出せる!
  157. 248 3-4 整数計画問題とは 222 次のような問題を整数計画問題という 線形計画問題(→2章)について、𝑥1 , 𝑥2 , …

    , 𝑥𝑛 を整数に限定したもの 最大化 𝑥1 + 𝑥2 条件 3𝑥1 + 8𝑥2 ≤ 40 5𝑥1 + 4𝑥2 ≤ 35 𝑥1 , 𝑥2 は非負整数 𝑥1 𝑥2 4 2 2 4 6 8 最適解
  158. 248 3-4 整数計画ソルバーについて • 世界では商用・非商用含め、様々なソルバーがある • 商用:Gurobi, CPLEX など •

    非商用:SCIP, CBC など • 変数と制約条件の数が数千オーダーでも解けるものも • NP 困難なのに… とても実用的! 224
  159. 248 3-4 SCIP について 226 以下のような簡単なプログラム(.lp ファイル)を書くだけで、整数 計画問題の答えが得られる maximize x

    + y subject to c1: 3 x + 8 y <= 80 c2: 5 x + 4 y <= 70 general x y end 目的関数 スコア 制約条件 一般の非負整数 [0/1 ではない] 𝑥, 𝑦 = (8, 7) のとき 目的関数は最大値 15
  160. 248 3-4 SCIP について 227 以下のような簡単なプログラム(.lp ファイル)を書くだけで、整数 計画問題の答えが得られる maximize x

    + y subject to c1: 3 x + 8 y <= 80 c2: 5 x + 4 y <= 70 general x y end 目的関数 スコア 制約条件 一般の非負整数 [0/1 ではない] 𝑥, 𝑦 = (8, 7) のとき 目的関数は最大値 15 ぜひ使ってみよう! 詳しい使い方は以下を参照: http://web.tuat.ac.jp/~miya/ipmemo.html
  161. 248 3-4 整数計画問題の応用 228 1 2 3 4 最大独立集合 分割問題

    k-センター問題 数独ソルバー 世の中の様々な問題は 整数計画問題に帰着することができます 10 33 57 38 62
  162. 248 3-4 事例 1:最大独立集合 229 各頂点を選ぶかどうかを 𝑥1 , 𝑥2 ,

    𝑥3 , 𝑥4 とする(0 または 1) 以下のようなグラフについて、隣接する 頂点を両方選ばないように、できるだけ 多くの頂点を選択してください。 1 2 3 4
  163. 248 3-4 事例 1:最大独立集合 230 各頂点を選ぶかどうかを 𝑥1 , 𝑥2 ,

    𝑥3 , 𝑥4 とする(0 または 1) 1 2 3 4 1 2 3 4 頂点 3, 4 は隣接 以下のようなグラフについて、隣接する 頂点を両方選ばないように、できるだけ 多くの頂点を選択してください。
  164. 248 3-4 事例 1:最大独立集合 231 整数計画 各頂点を選ぶかどうかを 𝑥1 , 𝑥2

    , 𝑥3 , 𝑥4 とする(0 または 1) 最大化 条件 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 1 2 3 4 以下のようなグラフについて、隣接する 頂点を両方選ばないように、できるだけ 多くの頂点を選択してください。
  165. 248 3-4 事例 1:最大独立集合 232 整数計画 各頂点を選ぶかどうかを 𝑥1 , 𝑥2

    , 𝑥3 , 𝑥4 とする(0 または 1) 最大化 条件 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 𝑥1 + 𝑥2 ≤ 1 1 2 3 4 一方しか 選べない 以下のようなグラフについて、隣接する 頂点を両方選ばないように、できるだけ 多くの頂点を選択してください。
  166. 248 3-4 事例 1:最大独立集合 233 整数計画 各頂点を選ぶかどうかを 𝑥1 , 𝑥2

    , 𝑥3 , 𝑥4 とする(0 または 1) 最大化 条件 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 𝑥1 + 𝑥2 ≤ 1 𝑥2 + 𝑥4 ≤ 1 1 2 3 4 一方しか 選べない 以下のようなグラフについて、隣接する 頂点を両方選ばないように、できるだけ 多くの頂点を選択してください。
  167. 248 3-4 事例 1:最大独立集合 234 整数計画 各頂点を選ぶかどうかを 𝑥1 , 𝑥2

    , 𝑥3 , 𝑥4 とする(0 または 1) 最大化 条件 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 𝑥1 + 𝑥2 ≤ 1 𝑥2 + 𝑥4 ≤ 1 𝑥4 + 𝑥3 ≤ 1 1 2 3 4 一方しか 選べない 以下のようなグラフについて、隣接する 頂点を両方選ばないように、できるだけ 多くの頂点を選択してください。
  168. 248 3-4 事例 1:最大独立集合 235 整数計画 各頂点を選ぶかどうかを 𝑥1 , 𝑥2

    , 𝑥3 , 𝑥4 とする(0 または 1) 最大化 条件 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 𝑥1 + 𝑥2 ≤ 1 𝑥2 + 𝑥4 ≤ 1 𝑥4 + 𝑥3 ≤ 1 𝑥3 + 𝑥1 ≤ 1 1 2 3 4 一方しか 選べない 以下のようなグラフについて、隣接する 頂点を両方選ばないように、できるだけ 多くの頂点を選択してください。
  169. 248 3-4 事例 1:最大独立集合 236 整数計画 各頂点を選ぶかどうかを 𝑥1 , 𝑥2

    , 𝑥3 , 𝑥4 とする(0 または 1) 最大化 条件 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 𝑥1 + 𝑥2 ≤ 1 𝑥2 + 𝑥4 ≤ 1 𝑥4 + 𝑥3 ≤ 1 𝑥3 + 𝑥1 ≤ 1 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 は 0 以上 1 以下の整数 1 2 3 4 以下のようなグラフについて、隣接する 頂点を両方選ばないように、できるだけ 多くの頂点を選択してください。
  170. 248 3-4 以下のようなグラフについて、隣接する 頂点を両方選ばないように、できるだけ 多くの頂点を選択してください。 事例 1:最大独立集合 237 整数計画 各頂点を選ぶかどうかを

    𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 とする(0 または 1) 最大化 条件 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 𝑥1 + 𝑥2 ≤ 1 𝑥2 + 𝑥4 ≤ 1 𝑥4 + 𝑥3 ≤ 1 𝑥3 + 𝑥1 ≤ 1 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 は 0 以上 1 以下の整数 1 2 3 4 変数 𝑛 個、制約 𝑚 個※ の 整数計画問題に落ちた! 頂点数・辺数が 1000 程度でも解ける ※グラフの頂点数を 𝑛、辺数を 𝑚 としている。 ※各変数が 0 以上 1 以下であることは、制約の個数に含めていない。
  171. 248 4-0 スライドのまとめ • 与えられた制約条件を満たす中で、目的関数(スコア)が最大/ 最小になる解を求める問題を数理最適化問題といいます • 数理最適化問題は、以下の 2 つに分類されます

    • 連続最適化問題: 変数 𝑥1 , … , 𝑥𝑛 が連続的な値(実数)をとる • 離散最適化問題: 変数 𝑥1 , … , 𝑥𝑛 がとびとびの値(整数等)をとる 240
  172. 248 4-0 スライドのまとめ • また、離散最適化問題の代表的な解法として 4 つ紹介しました • 特に山登り法などは、競プロの AHC

    などでも利用されます 243 有名なアルゴリズム で効率的に解く 山登り法などを 利用する 近似解法で 妥協する 整数計画 ソルバーに頼る 𝜋 = 3
  173. 248 4-0 スライドのまとめ • 実社会でも、数理最適化で解ける問題はたくさんあります 244 工場の売上最大化 栄養問題 最適な価格設定 日程計画問題

    最大独立集合 紙幣の払い方 ナップザック問題 ビンパッキング 巡回セールスマン 分割問題 10 33 57 38 62
  174. 248 4-1 参考文献 1. 梅谷俊治:「しっかり学ぶ数理最適化」、講談社(2020) 2. 梅谷俊治:「60分で学ぶ数理最適化」(https://speakerdeck.com/umepon/mathematical-optimization-in-60-minutes) 3. 岩永二郎、石原響太、西村直樹、田中一樹:「Python ではじめる数理最適化」、オーム社(2021)

    4. 大槻兼資:「問題解決力を鍛える!アルゴリズムとデータ構造」、講談社(2020) 5. 米田優峻:「「アルゴリズム×数学」が基礎からしっかり身につく本」、技術評論社(2021) 6. 米田寛峻:「アルゴリズムの世界地図」(https://qiita.com/square1001/items/6d414167ca95c97bd8b2) 7. 宮代隆平:整数計画ソルバー入門(http://web.tuat.ac.jp/~miya/miyashiro_ORSJ.pdf) 8. 宮代隆平:整数計画法メモ(http://web.tuat.ac.jp/~miya/ipmemo.html) 9. 日本オペレーションズ・リサーチ学会:「ORを探せ!ポスター」(http://www.orsj.or.jp/members/poster.html) 10. SCIP Optimization Suite(https://www.scipopt.org/) 11. いらすとやの画像を利用 247