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