Document

計画数学第2
- 授業の目的と流れ -
• 数理計画と組み合わせ最適化を、
応用を中心として解説
宇野 毅明
情報学研究所 & 総合研究大学院大学
復習:数理計画とは
数理計画・最適化(数理計画問題・最適化問題):
数理的に表現された、数多くのもの(集合)の中から、最も
良いものを選び出すこと
数理計画法・最適化法:
数理計画問題を解く、数理的な方法のこと
例:
線形計画: 線形制約を満たす n次元ベクトルの中で、目的
関数値が最も良いものを見つける問題
シンプレックス法(単体法): 線形計画を解く、数理的な方法
数理計画の特徴
コンピュータで数理計画を解くと
+ 大きな問題が解ける
(決定する項目の数がときに1万を超える)
+ 正確に解ける
(あるいは、精度の保証をする)
+ 短時間でたくさん解ける
(1秒間に何百回も解く)
- 数理的にしっかり定義された問題しか解けない
- 問題の条件がちょっとでも変わると解けない
- 構造が悪いと、密な問題でも解けない
- 直感的に、ひらめきで解くようなことはできない
大きな問題が解ける利点
+ 大きな問題が解ける
• 人間が解ける問題の大きさは、せいぜい 100 ~ 1000程度
• 「解ける」とはいえ、とても時間がかかる上に、
最適性の保証も無い
• たっぷり時間をかけて最適化する仕事は、非常に非人間的
対して、解きたい問題は、大きいことが多い
• 人間が最適化するのは、無理
巨大データ
• 近年のIT技術の発達により、半自動的に巨大なデータが収
集されている
- POSデータ
10万 ~
- ソーシャルネットワーク
10万~
- 文書データ、辞書データ 100万 ~
- ウェブネットワーク
1000万 ~
- ウェブアクセス
1000万 ~
- 通信パケットのログ
1000万 ~ …
データ
データ
ベース
ベース
経営戦略やマーケッティングにおいて、これら巨大
データをいかに使うかが大きな鍵となってきている
正確に解けることの利点
+ 正確に解ける
• 人間が、「正確である事」を保証して問題を解くのは、非常に
手間がかかる(パズルの証明をするようなもの)
• 「人間系によるエラー」もあるかもしれない
• 数理計画法だと、「最適」である解が得られる
• 近似アルゴリズムで、「最適解から誤差○○以内」である解
が得られる
• 列挙アルゴリズムで「条件にあう解」が全てもらさず見つけら
れる
正確な解が必要な場面
• 「○○の性質を持つものの値は○○以下」というような定理
証明を行うとき
• 行政での政策決定など、正確な解を証拠として用いたいとき
• データの分析など、解の正確な数が必要なとき
• 科学分野で、実験結果から得られるデータを証拠として使い
たいとき
短時間で解けることの利点
+ 短時間でたくさん
• 人間はいくら速くても、処理には限界がある(10秒はかかる)
• たくさん解くのは、疲れる
• 対話型の最適化システムでは、同じような問題を短時間で何
回も解かなければならない
• オンラインサービス(路線検索、ナビ)などは、瞬時に答えを
返す、という作業を、何千回と行う
• 製造工場などでのリスケジューリングは、オーダーの変更に
伴い、短時間で繰り返し解く必要がある
数理計画の位置づけ
オペレーションズ・リサーチ
計算機アルゴリズム
数理計画
数学
自然科学・社会科学・
産業・行政など応用分野
数理計画の位置づけ (2)
組合せ最適化
近似
アルゴリズム
数理計画
線形計画
非線形計画
授業の内容
1.線形計画の使い方
(実際問題をどのようにして線形計画で解くか)
2.組合せ最適化問題
(世の中の問題を中心にして、
いくつかの組合せ最適化問題を解説)
3. 近傍探索、動的計画
(線形計画以外の、最適化問題の解法を紹介)
授業の内容 (2)
• 非線形計画
• 組合せ最適化
• 生産計画を立てる
• 割り当て問題
• クラス編成をする
• 最短路とナビゲーション
• 施設配置
• 配送計画
• スケジューリング
• 動的計画
• 列挙
• データマイニング
• データベース比較
授業のねらい
数理計画を勉強するには、少なくとも3つの視点が必要
1. 数学的な視点
2. オペレーションズ・リサーチ的な視点
3. アルゴリズム的な視点
いろいろな問題や解法を題材にして、これらの視点から物事
を見るセンスを磨く
計算機アルゴリズム
アルゴリズム:
物事をするときの、手順のこと
普通は、コンピューターに計算をさせる(プログラム)の手順
コンピュータの、効率の良いプログラムを書くにはどうするか、と
いうプログラム設計の理論と考えても良い
1から100の数字を足したい:
・1+2+,...,+100 ‥‥ 99回の足し算
・(1+100) * (100/2) ‥ 演算3回
にんじんを星型の輪切りに切りたい
・輪切りにしてから、それぞれを星型に切る
・ まず星型の切込みを入れてから、輪切りにする
計算機アルゴリズム (2)
計算時間オーダー: O(f(n))
入力した問題の大きさに対して、最悪で、どの程度の時間がか
かるかを、問題の大きさの関数(多項式)であらわしたもの
※ 係数は、機械やプログラマーによるので無視。
※ 最大次数のところのみに着目する
(入力が大きくなると、最大次数しか効いてこない)
n項目ある辞書を引く:
• 最初から順に調べる O(n)
• 2分探索する O(log n)
n 個の数字をソートする
• 普通に挿入、クイックソート O(n2)
• マージソート・ヒープソート O(n log n)
オーダーが小さければ、
機械やプログラマーが
多少悪くても、設計の良
さで圧倒的に速い
オペレーションズ・リサーチ
オペレーションズ・リサーチ(OR)
現実世界に存在するシステムや作業や問題を、数理的なモ
デルとして表現し、その問題を解く数理的な解法を構築する
明日の天気を知りたい:
• 晴れや、曇りなどの天気を分類し、数理化
• 「過去の天気、気象データの履歴は翌日の天気と相関がある」
という観察から、「気象データの履歴から明日の天気を予測」
というモデルを立てる
• このモデルを、統計的手法で解く
オペレーションズ・リサーチ (2)
ここから目的地までの最短ルートが知りたい
• それぞれのルートを、交差点から交差点への道の区分
の組合せとしてモデル化
• 通過時間が最短となる、道の組合せを見つける最適化
問題として解く
議会での各政党の発言力が知りたい
• 「法案を通すには、いくつかの政党が協力しなければな
らない」、という観察から、「どの政党の組合せが過半数
を取れるか」という組合せでモデル化。ゲーム理論の、協
力ゲームのモデルなどに当てはめる
• 発言力を計算する
オペレーションズ・リサーチ (3)
研究・実践では
+ 妥当なモデルが作れるか
+ 数理的に解ける(実用的な時間で解ける)問題に定式化
されるか
+ 効率的な解法か
+ 実用的か(解の性質・求解の時間など)
といった点が重視される
オペレーションズ・リサーチ (4)
研究手法
モデル作り
各々の段階で、数学的、OR的、
アルゴリズム的な視点が必要
解法の構築
アルゴリズムの改良
知識をどのように使うか
おしなべて、物事は応用力が大事
• 現実の問題に出会ったとき、その問題を、自分の知識でどのよ
うに解決するか
• あるいは、自分の知識では解決できそうもないことを、どのよう
に確認するか
• 自分の知識で解決できなかったら、どのような知識を手に入れ
ればいいか
例)線形計画、という道具(知識)があるとき、これを使ってどの
ような問題が解けるか考える。
練習問題
1. 線形計画で解ける問題を考える
2. ほかの問題を線形計画で解く
練習問題:
それなりに実用的な問題で、線形計画になる問題を考
えてみよう
軽く練習問題1
用語の定義:
max {a,b,…,z}: a,…,z の中の最大値
min {a,b,…,z}: a,…,z の中の最小値
max xi, min xi : x1,…, xn の中の最大、最小値
問題: 次の数理計画問題を、線形計画問題に直せ
最小化:
制約条件:
max xi
∑ ai xi ≦ b
xi ≧ 0
軽く練習問題1-2
新しい変数 t を導入する
最小化:
制約条件:
t
t ≧ xi
∑ ai xi ≦ b
xi ≧ 0
問題:
これで正しいことを証明しましょう
軽く練習問題1-3
証明: 実行可能な xi に対して
制約条件より t ≧ max xi は明らか。
ここで、 t > max xi であるとすると、
t > t' ≧ max xi となる t' が存在する
t' と xi の組は実行可能解なので、t は最適解でない。
対偶を取ると、「 t が最適解ならば、 t ≦ max xi 」
よって、2つの問題の最適解は同じ目的関数値を持つ
q.e.d
では問題。最小化 min xi とした問題は、線形計画になるで
しょうか、ならないでしょうか
軽く練習問題1-4
問題: 以下の問題を線形計画問題に直しなさい
最小化:
制約条件:
max xi + max yi
∑ ai yi ≦ b
∑ ai xi ≦ b
xi ≧ 0
最小化:
制約条件:
∑ ( ci xi + ei yi )
max ai xi + max di yi ≦ b
∑ ai xi ≦ f
∑ di xi ≦ f
xi , yi ≧ 0
軽く練習問題2
問題: 以下の問題を線形計画問題に直しなさい
最小化:
制約条件:
| ∑ ci xi |
∑ ai xi ≦ b
xi ≧ 0
軽く練習問題2-2
max を使った問題に直してみる
最小化:
制約条件:
max { -∑ ci xi , ∑ ci xi }
∑ ai xi ≦ b
xi ≧ 0
ということは、
最小化:
制約条件:
t
t
ai xi
xi
t
≧ -∑ ci xi
≧ ∑ ci xi
≦ b
≧ 0
問題: これで正しいことを証明しなさい
軽く練習問題2-3
証明:
∑ ci xi ≧ 0 のとき
| ∑ ci xi | = ∑ ci xi 、 ∑ ci xi ≧ - ∑ ci xi
より | ∑ ci xi | = max { -∑ ci xi , ∑ ci xi }
∑ ci xi ≦ 0 のとき
| ∑ ci xi | = -∑ ci xi 、 ∑ ci xi ≦ - ∑ ci xi
より | ∑ ci xi | = max { -∑ ci xi , ∑ ci xi }
よって両問題の目的関数値は等しい
問題: 最大化:
| ∑ ci xi |
だとどうなるでしょうか?
軽く練習問題2-4
問題: 以下の問題を線形計画問題に直しなさい
最小化:
制約条件:
| ∑ xi | + | ∑ yi |
∑ ai yi ≦ b
∑ ai xi ≦ b
最小化:
制約条件:
∑ ( ci xi + ei yi )
| ∑ xi | + | ∑ y i | ≦ b
∑ ai xi ≦ f
∑ di xi ≦ f
軽く練習問題3
問題: 以下の問題を線形計画問題に直しなさい
最小化:
制約条件:
∑ ci2 xi2
∑ ai2 xi2 ≦ b2
xi ≧ 0
軽く練習問題3-2
xi2 = yi とおくと
最小化:
制約条件:
∑ ci2 yi
∑ ai2 yi ≦ b2
yi ≧ 0
となる。
問題: 2つの問題が等価であることを証明せよ
軽く練習問題3-3
• 元の問題の解と、変換した問題の解が、
xi2 = yi という関係で、1対1対応する。
• 目的関数値も同じ
元の問題の最適解  変換した問題の最適解
問題: 次の問題ではどうでしょうか
最小化:
制約条件:
∑ ci2 xi2 + ∑ ci2 yi2
∑ ai2 xi2 ≦ b2
∑ ai2 xi yi = b2
xi , yi ≧ 0
最小化:
制約条件:
∑ sin xi
∑ ai xi = b
xi , yi ≧ 0
軽く練習問題4
問題: 以下の問題を線形計画問題に直しなさい
最小化:
制約条件:
Π xici
Π xiai ≦ b
xi ≧ 1
軽く練習問題4-1
• 全部、log をとってみる
最小化:
制約条件:
log Π xici
Π log xiai ≦ log b
log xi ≧ log 1
最小化:
∑ log ci log xi
制約条件: ∑ log ci log xi ≦ log b
log xi ≧ 0
yi = log xi とおくと
最小化:
∑ log ci yi
制約条件: ∑ log ci yi ≦ log b
yi ≧ 0