Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
最適化数学についてー線形計画ー
Search
yujikawa
September 20, 2017
Technology
0
1.1k
最適化数学についてー線形計画ー
線形計画法についての勉強会資料
yujikawa
September 20, 2017
Tweet
Share
More Decks by yujikawa
See All by yujikawa
大問題を解決する
yujikawa
1
160
Airflowの話/about airflow
yujikawa
0
230
FastAPIに入門してみた/fastAPI
yujikawa
0
520
Jupyterでダッシュボードを簡単に作る!
yujikawa
2
830
私がUXの大切さを知った瞬間/uxjam_kitaq_1
yujikawa
0
82
AngularDart
yujikawa
1
290
Introduce Flutter
yujikawa
0
340
グロースハック完全読本を読んでみた
yujikawa
0
540
rumpsを使って簡単な常駐アプリを作る
yujikawa
0
350
Other Decks in Technology
See All in Technology
Platform Engineering for Software Developers and Architects
syntasso
1
520
飲食店データの分析事例とそれを支えるデータ基盤
kimujun
0
210
CysharpのOSS群から見るModern C#の現在地
neuecc
2
3.6k
個人でもIAM Identity Centerを使おう!(アクセス管理編)
ryder472
4
240
[CV勉強会@関東 ECCV2024 読み会] オンラインマッピング x トラッキング MapTracker: Tracking with Strided Memory Fusion for Consistent Vector HD Mapping (Chen+, ECCV24)
abemii
0
230
iOSチームとAndroidチームでブランチ運用が違ったので整理してます
sansantech
PRO
0
150
Application Development WG Intro at AppDeveloperCon
salaboy
0
200
日経電子版のStoreKit2フルリニューアル
shimastripe
1
150
Security-JAWS【第35回】勉強会クラウドにおけるマルウェアやコンテンツ改ざんへの対策
4su_para
0
190
CDCL による厳密解法を採用した MILP ソルバー
imai448
3
180
心が動くエンジニアリング ── 私が夢中になる理由
16bitidol
0
100
マルチプロダクトな開発組織で 「開発生産性」に向き合うために試みたこと / Improving Multi-Product Dev Productivity
sugamasao
1
310
Featured
See All Featured
Navigating Team Friction
lara
183
14k
How GitHub (no longer) Works
holman
310
140k
YesSQL, Process and Tooling at Scale
rocio
169
14k
Measuring & Analyzing Core Web Vitals
bluesmoon
4
130
What's new in Ruby 2.0
geeforr
343
31k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
356
29k
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
Fireside Chat
paigeccino
34
3k
Building Adaptive Systems
keathley
38
2.3k
Scaling GitHub
holman
458
140k
Designing Experiences People Love
moore
138
23k
Building Applications with DynamoDB
mza
90
6.1k
Transcript
最適化数学について - 線形計画法 -
参考図書 これなら分かる最適化数学 基礎原理から計算手法まで 金谷 健一 (著)
目次 線形計画とは 可能領域 線形計画の基本定理 スラック変数 シンプレックス法 おまけ:PULPによる線形計画
線形計画とは 問題P0:次の形の最適化問題を考える 11 1 + 12 2 ⋯ + 1
≤ 1 21 1 + 22 2 ⋯ + 2 ≤ 2 ⋮ 1 1 + 2 2 ⋯ + ≤ 1 ≥ 0, 2 ≥ 0 ⋯ ≥ 0 = 1 1 + 2 2 + ⋯ + → 特徴② 1 , 2 ⋯ はすべて非負 特徴① 個の制約条件は 1 , 2 ⋯ の 1次式の不等式 (制約不等式) 特徴③ 最大化する関数は 1 , 2 ⋯ の1次関数 (目的関数) 線形計画の 標準形という
この3つの特徴を持つ問題を 線形計画 線形計画を解く手法が 線形計画法 線形計画とは 特徴② 1 , 2 ⋯
はすべて非負 特徴① 個の制約条件は 1 , 2 ⋯ の 1次式の不等式 (制約不等式) 特徴③ 最大化する関数は 1 , 2 ⋯ の1次関数 (目的関数)
線形計画とは- 例題 - 2種類の商品A,Bを作るのに2台の機械1 , 2 を使う。商品Aを1個作るのに機械1 を2分、機械2 を4分使う必要がある。一方商品Bを1個作るのに機械1 を8分、機械2
を4分使う必要がある。商 品をA,Bを作る利益は一つあたりそれぞれ29円、45円である。1時間あたりで利益を最大にするに はどのように計画すればよいでしょうか? 1 2 商品A 29円/個 2分 4分 1 2 商品B 45円/個 8分 4分
線形計画とは- 例題 - 1 2 商品A 29円/個 2分 4分 1
2 商品B 45円/個 8分 4分 時間の制約条件 ቊ 2 + 8 ≤ 60 4 + 4 ≤ 60 ≥ 0, ≥ 0 利益を求める関数 = 29 + 45 → 1時間(60分)のうちに商品Aを x個、商品Bをy個作るとすると・・
可能領域 n次元空間内で下記の不等式を満たす点の集合を可能領域といい、それに属する 点を可能解とよぶ。可能解の中で目的関数を最大にする点を最適解という。 11 1 + 12 2 ⋯ +
1 ≤ 1 21 1 + 22 2 ⋯ + 2 ≤ 2 ⋮ 1 1 + 2 2 ⋯ + ≤ 1 ≥ 0, 2 ≥ 0 ⋯ ≥ 0 = 1 1 + 2 2 + ⋯ + →
可能領域-例題- 次の不等式で表される可能領域は? ቊ + 3 ≤ 9 2 + ≤
8 ≥ 0, ≥ 0 + 3 = 9 2 + = 8 可能領域
可能領域-例題- 下記のような可能領域は最適解は存在しない(可能領域が発散)
線形計画の基本定理 線形計画問題の解を求める最も基本的な原理は、目的関数を最大にする最適解 があるとすれば、可能領域を表す凸多面体の頂点のみを調べればよい。 問題P0に最適解( 1 ∗, 2 ∗ ⋯ ∗
)が存在すれば、目的関数は可能領域の頂点で最大値をとる + 3 = 9 2 + = 8
線形計画の基本定理 n次元多面体の頂点ではn個の境界面が交わっている。可能領域の各境界面は条 件のm+n個の不等式で不等号を等式に置き換えたもののどれかである 問題P0のある最適解( 1 ∗, 2 ∗ ⋯ ∗
)において、m+n個の不等式のうちn個が等号で成立する + 3 = 9 2 + = 8 個 ቊ + 3 ≤ 9 2 + ≤ 8 個ሼ ≥ 0, ≥ 0 この例だとn=2 下記の2式 x+3y=9と2x+y=8
スラック変数 不等式は小さい方の変に非負の数(λ)を加えて等式にすることができる。 ≤ λ + λ =
スラック変数-例題- 次の線形計画を等式の制約条件に書き直せ。 ቊ 2 + 8 ≤ 60 4 +
4 ≤ 60 ≥ 0, ≥ 0 = 29 + 45 → ቊ 2 + 8 + λ1 = 60 4 + 4 + λ2 = 60 ≥ 0, ≥ 0, λ1 ≥ 0, λ2 ≥ 0 = 29 + 45 →
スラック変数-境界面- + 3 = 9 2 + = 8 ቊ
+ 3 + λ1 = 9 2 + + λ2 = 8 ≥ 0, ≥ 0 λ1 ≥ 0, λ2 ≥ 0 n次元空間の可能領域のi番目の境界面でλ = 0である。 λ2 = 0 λ1 = 0
スラック変数 問題P1:問題P0にスラック変数を使う 11 1 + 12 2 ⋯ + 1
+ λ1 = 1 21 1 + 22 2 ⋯ + 2 + λ2 = 2 ⋮ 1 1 + 2 2 ⋯ + + λ = 1 ≥ 0, 2 ≥ 0 ⋯ ≥ 0 λ1 ≥ 0, λ2 ≥ 0 ⋯ λ ≥ 0 = 1 1 + 2 2 + ⋯ + → 問題P1のある最適解( 1 ∗, 2 ∗ ⋯ ∗, λ1 ∗, λ2 ∗ ⋯ λ ∗ )において、 m+n個の値1 ∗, 2 ∗ ⋯ ∗, λ1 ∗, λ2 ∗ ⋯ λ ∗ のうちn個は0である
スラック変数-例- (0, ∗, 0, λ2 ∗ ) 2 + =
8 λ2 = 0 λ1 = 0 (0,0, λ1 ∗, λ2 ∗ ) (∗, 0, λ1 ∗, 0) (∗, ∗, 0,0) ቊ + 3 + λ1 = 9 2 + + λ2 = 8 ≥ 0, ≥ 0 λ1 ≥ 0, λ2 ≥ 0 各点のときの各値を次のように表現する(∗, ∗, λ1 ∗, λ2 ∗) 下記の例ではn=2、m=2である。m+n=4の値のうち2つは0になる。
問題P1の解き方 1. m+n個の変数1 , … , λ1 , … λ
のうちからn個選んで0とおいてできる連立1次 方程式を残りのm個の変数について解く 2. その解がすべて非負かどうか調べる 3. そうであれば目的関数の値を計算する 4. これをすべての可能性について行い、 の値が最大になるものを選ぶ しかし、m+n個の変数を選んで0とする方法はm+n個が大きくなるにつれ、現実的 に難しい。なるべく早く最適解に到達する方法として考えられた方法がシンプレック ス法である。
シンプレックス法-その①- シンプレックス法の原理を例題を使ってやってみよう。スラック変数を導入した下記 の式を解いてみる。説明のために, , λ1 , λ2 をそれぞれ1 , 2
, 3 , 4 とします。 ቊ 2 + 8 + λ1 = 60 4 + 4 + λ2 = 60 ≥ 0, ≥ 0, λ1 ≥ 0, λ2 ≥ 0 = 29 + 45 → ቊ 21 + 82 + 3 = 60 41 + 42 + 4 = 60 1 ≥ 0, 2 ≥ 0, 3 ≥ 0, 4 ≥ 0 = 291 + 452 →
シンプレックス法-その②- 1 , 2 , 3 , 4 のうちから2つ選んで左辺に移し、右辺を残りの変数で表す。例えば 3
, 4 を選べば次のように書ける。 3 = 60 − 21 − 82 ⋯ (1) 4 = 60 − 41 − 42 ⋯ (2) = 291 + 452 ⋯ (3) 右辺の変数をすべて0と置くと、次の解を得る。 1 = 0, 2 = 0, 3 = 60, 4 = 60 この解はすべて非負であるが、最適解ではない。(1)と(2)で1 , 2 を少しだけ増やしても 3 , 4 は正のままであるが、(3)よりの値が増加するからである。(まだ最大値ではない) そこで3 , 4 が非負である限り、できるだけ大きく1 , 2 を増やすことを考える。
シンプレックス法-その③- まず1 を増やすことを考える。( 2 = 0 とする) 3 = 60
− 21 ⋯ (1) 4 = 60 − 41 ⋯ (2) = 291 ⋯ (3) (1)によれば 1 が増えれば3 が減り、非負を保つ限界は1 = 30, 3 = 0となる。 (2)によれば1 = 15, 4 = 0となる。 したがって1 は最大で 1 = 15まで増やせる。 その結果(3)は∆ = 29 × 15 = 435だけ増加する。
シンプレックス法-その④- 3 = 60 − 82 ⋯ (1) 4 =
60 − 42 ⋯ (2) = 452 ⋯ (3) 次に2 を増やすことを考える。( 1 = 0 とする) (1)によれば非負を保つ限界は2 = 7.5, 3 = 0となる。 (2)によれば2 = 15, 4 = 0となる。 したがって2 は最大で 2 = 7.5まで増やせる。 その結果(3)は∆ = 45 × 7.5 = 337.5だけ増加する。
シンプレックス法-その⑤- 以上により1 を増やしたほうがの値がより増加する。そして1 を限度いっぱいに 増やすと(2)の左辺の4 が0になる。そこで(2)の左辺4 を右辺に移し、右辺の1 を 左辺に移す 3
= 60 − 21 − 82 ⋯ (1) 1 = 15 − 2 − 1 4 4 ⋯ (2) = 291 + 452 ⋯ (3) 3 = 30 − 62 + 1 2 4 ⋯ (4) 1 = 15 − 2 − 1 4 4 ⋯ (5) = 435 + 162 − 7.254 ⋯ (6) (2)を(1)と(3)に代入
シンプレックス法-その⑤- 右辺の変数をすべて0と置くと 3 = 30 − 62 + 1 2
4 ⋯ (4) 1 = 15 − 2 − 1 4 4 ⋯ (5) = 435 + 162 − 7.254 ⋯ (6) 1 = 15, 2 = 0, 3 = 30, 4 = 0 しかし、これも最適解ではない。(4),(5)で2 を少しだけ増やしても1 , 3 は正のままであるが (6)が増加するからである。
シンプレックス法-その⑥- そこで2 を増やす( 4 = 0とする) 3 = 30 −
62 ⋯ (4) 1 = 15 − 2 ⋯ (5) = 435 + 162 ⋯ (6) (4)によれば非負を保つ限界は2 = 5, 3 = 0となる。 (5)によれば2 = 15, 1 = 0となる。 したがって2 は最大で 2 = 5まで増やせる。 そして∆ = 16 × 5 = 80だけ増加し、その結果左辺の3 は0になる。
シンプレックス法-その⑦- 次に(4)の左辺の3 を右辺に移し、右辺の2 を左辺に移す。すると(4)は 3 = 30 − 62 +
1 2 4 ⋯ (4) 1 = 15 − 2 − 1 4 4 ⋯ (5) = 435 + 162 − 7.254 ⋯ (6) 2 = 5 − 1 6 3 + 1 12 4 ⋯ (7) 1 = 10 + 1 6 3 − 1 3 4 ⋯ (8) = 515 − 2.6673 − 5.9174 ⋯ (9) (7)を(5)と(6)に代入
シンプレックス法-その⑧- 右辺の変数をすべて0と置くと、次の解を得る。 2 = 5 − 1 6 3 +
1 12 4 ⋯ (7) 1 = 10 + 1 6 3 − 1 3 4 ⋯ (8) = 515 − 2.6673 − 5.9174 ⋯ (9) 1 = 10, 2 = 5, 3 = 0, 4 = 0 これは最適解である。(9)の3 ,4 の係数が負のため。少しでも3 , 4 を0から増やす との値が減ってしまうためである。したがって最大値は = 515である
シンプレックス法-幾何学的解釈- 幾何学的解釈をすると、シンプレックス法は可能領域のある頂点を出発点とし、目 的関数の値が最も大きくぞうかするように辺に沿って移動し、 が増加しなくなる 頂点で終了する仕組み。
シンプレックス法-幾何学的解釈- = 0 λ2 = 0 λ1 = 0 =
0 A C B D E 15 7.5 15 30 ①原点(0,0)を考える。 そこからx軸またはy軸に沿って移動するとfは増加する ため原点は最適解ではない。 ②原点からx軸に沿って移動することを考える。 可能領域の範囲内で移動できるのは点Bまで、そしてf は435だけ増加する。 ③原点からy軸に沿って移動することを考える。 可能領域の範囲内で移動できるのは点Cまで、そしてf は337.5だけ増加する。 ②と③よりx軸に沿って移動するほうが増加量が多いた め原点からx軸方向に移動する。 ④点Bからλ2 = 0軸に沿って移動することを考える。 可能領域の範囲内で移動できるのは点Eまで、そしてf は80だけ増加する。(この後はどこ移動しても減少) ቊ 2 + 8 + λ1 = 60 4 + 4 + λ2 = 60 ≥ 0, ≥ 0, λ1 ≥ 0, λ2 ≥ 0 = 29 + 45 → 最適解
おまけ-PULPによる線形計画- プログラム 実行結果
ご清聴ありがとうございました。