Document

計画数学第２
－授業の目的と流れ－
• 数理計画と組み合わせ最適化を、
応用を中心として解説
宇野毅明
情報学研究所＆総合研究大学院大学
復習：数理計画とは
数理計画・最適化（数理計画問題・最適化問題）：
数理的に表現された、数多くのもの（集合）の中から、最も
良いものを選び出すこと
数理計画法・最適化法：
数理計画問題を解く、数理的な方法のこと
例：
線形計画：線形制約を満たす n次元ベクトルの中で、目的
関数値が最も良いものを見つける問題
シンプレックス法（単体法）：線形計画を解く、数理的な方法
数理計画の特徴
コンピュータで数理計画を解くと
＋大きな問題が解ける
（決定する項目の数がときに１万を超える）
＋正確に解ける
（あるいは、精度の保証をする）
＋短時間でたくさん解ける
（１秒間に何百回も解く）
－数理的にしっかり定義された問題しか解けない
－問題の条件がちょっとでも変わると解けない
－構造が悪いと、密な問題でも解けない
－直感的に、ひらめきで解くようなことはできない
大きな問題が解ける利点
＋大きな問題が解ける
• 人間が解ける問題の大きさは、せいぜい 100 ~ 1000程度
• 「解ける」とはいえ、とても時間がかかる上に、
最適性の保証も無い
• たっぷり時間をかけて最適化する仕事は、非常に非人間的
対して、解きたい問題は、大きいことが多い
• 人間が最適化するのは、無理
巨大データ
• 近年のIT技術の発達により、半自動的に巨大なデータが収
集されている
－ POSデータ
10万 ~
－ソーシャルネットワーク
10万~
－文書データ、辞書データ 100万 ~
－ウェブネットワーク
1000万 ~
－ウェブアクセス
1000万 ~
－通信パケットのログ
1000万 ~ …
データ
データ
ベース
ベース
経営戦略やマーケッティングにおいて、これら巨大
データをいかに使うかが大きな鍵となってきている
正確に解けることの利点
＋正確に解ける
• 人間が、「正確である事」を保証して問題を解くのは、非常に
手間がかかる（パズルの証明をするようなもの）
• 「人間系によるエラー」もあるかもしれない
• 数理計画法だと、「最適」である解が得られる
• 近似アルゴリズムで、「最適解から誤差○○以内」である解
が得られる
• 列挙アルゴリズムで「条件にあう解」が全てもらさず見つけら
れる
正確な解が必要な場面
• 「○○の性質を持つものの値は○○以下」というような定理
証明を行うとき
• 行政での政策決定など、正確な解を証拠として用いたいとき
• データの分析など、解の正確な数が必要なとき
• 科学分野で、実験結果から得られるデータを証拠として使い
たいとき
短時間で解けることの利点
＋短時間でたくさん
• 人間はいくら速くても、処理には限界がある（10秒はかかる）
• たくさん解くのは、疲れる
• 対話型の最適化システムでは、同じような問題を短時間で何
回も解かなければならない
• オンラインサービス（路線検索、ナビ）などは、瞬時に答えを
返す、という作業を、何千回と行う
• 製造工場などでのリスケジューリングは、オーダーの変更に
伴い、短時間で繰り返し解く必要がある
数理計画の位置づけ
オペレーションズ･リサーチ
計算機アルゴリズム
数理計画
数学
自然科学・社会科学・
産業・行政など応用分野
数理計画の位置づけ (2)
組合せ最適化
近似
アルゴリズム
数理計画
線形計画
非線形計画
授業の内容
１．線形計画の使い方
（実際問題をどのようにして線形計画で解くか）
２．組合せ最適化問題
（世の中の問題を中心にして、
いくつかの組合せ最適化問題を解説）
３．近傍探索、動的計画
（線形計画以外の、最適化問題の解法を紹介）
授業の内容 (2)
• 非線形計画
• 組合せ最適化
• 生産計画を立てる
• 割り当て問題
• クラス編成をする
• 最短路とナビゲーション
• 施設配置
• 配送計画
• スケジューリング
• 動的計画
• 列挙
• データマイニング
• データベース比較
授業のねらい
数理計画を勉強するには、少なくとも3つの視点が必要
１．数学的な視点
２．オペレーションズ・リサーチ的な視点
３．アルゴリズム的な視点
いろいろな問題や解法を題材にして、これらの視点から物事
を見るセンスを磨く
計算機アルゴリズム
アルゴリズム：
物事をするときの、手順のこと
普通は、コンピューターに計算をさせる（プログラム）の手順
コンピュータの、効率の良いプログラムを書くにはどうするか、と
いうプログラム設計の理論と考えても良い
１から１００の数字を足したい：
・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. ほかの問題を線形計画で解く
練習問題：
それなりに実用的な問題で、線形計画になる問題を考
えてみよう
軽く練習問題１
用語の定義：
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
軽く練習問題１－２
新しい変数 t を導入する
最小化：
制約条件：
t
t ≧ xi
∑ ai xi ≦ b
xi ≧ 0
問題：
これで正しいことを証明しましょう
軽く練習問題１－３
証明：実行可能な xi に対して
制約条件より t ≧ max xi は明らか。
ここで、 t ＞ max xi であるとすると、
t ＞ t' ≧ max xi となる t' が存在する
t' と xi の組は実行可能解なので、t は最適解でない。
対偶を取ると、「 t が最適解ならば、 t ≦ max xi 」
よって、２つの問題の最適解は同じ目的関数値を持つ
q.e.d
では問題。最小化 min xi とした問題は、線形計画になるで
しょうか、ならないでしょうか
軽く練習問題１－４
問題：以下の問題を線形計画問題に直しなさい
最小化：
制約条件：
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
軽く練習問題２
問題：以下の問題を線形計画問題に直しなさい
最小化：
制約条件：
| ∑ ci xi |
∑ ai xi ≦ b
xi ≧ 0
軽く練習問題２－２
max を使った問題に直してみる
最小化：
制約条件：
max { －∑ ci xi , ∑ ci xi }
∑ ai xi ≦ b
xi ≧ 0
ということは、
最小化：
制約条件：
t
t
ai xi
xi
t
≧ －∑ ci xi
≧ ∑ ci xi
≦ b
≧ 0
問題：これで正しいことを証明しなさい
軽く練習問題２－３
証明：
∑ 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 |
だとどうなるでしょうか？
軽く練習問題２－４
問題：以下の問題を線形計画問題に直しなさい
最小化：
制約条件：
| ∑ xi | + | ∑ yi |
∑ ai yi ≦ b
∑ ai xi ≦ b
最小化：
制約条件：
∑ ( ci xi + ei yi )
| ∑ xi | + | ∑ y i | ≦ b
∑ ai xi ≦ f
∑ di xi ≦ f
軽く練習問題３
問題：以下の問題を線形計画問題に直しなさい
最小化：
制約条件：
∑ ci2 xi2
∑ ai2 xi2 ≦ b2
xi ≧ 0
軽く練習問題３－２
xi2 = yi とおくと
最小化：
制約条件：
∑ ci2 yi
∑ ai2 yi ≦ b2
yi ≧ 0
となる。
問題：２つの問題が等価であることを証明せよ
軽く練習問題３－３
• 元の問題の解と、変換した問題の解が、
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
軽く練習問題４
問題：以下の問題を線形計画問題に直しなさい
最小化：
制約条件：
Π xici
Π xiai ≦ b
xi ≧ 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

Download Report