数理最適化を勉強する話②
前回
数理最適化の種類
そもそも数理最適化の種類には
の３パターンがある。らしい。
線形最適化
目的関数が線形で表せるもの。
線形最適化問題を解くことを"線形計画"というらしい。
世の中にはこれらの計算をやってくれるモジュールがちゃんとある。
#数理モデルの作成
ml = model_min()
#変数の設定
vl = {(i):LpVariable('v%d'%(i), cat='Integer', lowBound=0)for i in pr}
ml += lpSum(df_p.iloc[0][i]*vl[i] for i in pr) #合計金額
for j in range(nn):
#制約条件
ml += lpSum(vl[i]*df_n.iloc[i][j] for i in range(np)) >= 100
#解く
ml.solve()
非線形最適化
目的関数が非線形で表せるもの
目的関数f(x)で
二分探索
一定の範囲x1,x2を指定して、f(x)>0ならx1を、<0ならx2を狭めていく方法
ニュートン法
- 制約条件を満たすxを適当に設定
- 接戦を引く
- 接戦とx軸が交わる新たなxを設定
- 2に戻る
組み合わせ最適化
そのままの意味で、組み合わせの問題を線形最適化問題に落とし込んで解く方法
データ構造としてグラフネットワークを使うと良いらしい。
そして、グラフネットワークを水路として考える"最大流問題"として考える。
一番左の点をsource、一番右の点をsink、辺をcapacity
このsourceとsinkの間に組み合わせのノードを組み込めばflowの流れで最適化ができるということらしい。
最大流問題を解くアルゴリズムには色々種類があるみたい。
そのうちの一つ"Dinicのアルゴリズム"をとりあえず勉強した。
Dinicのアルゴリズム
- 幅優先探索(BFS)を使ってフローの流し方を決める
- sinkに流れる方法がない時、処理を終了し、それまでsinkに流れた合計を最適解とする
- 深さ優先探索(DFS)を使って1の方法でsourceからsinkにフローを流す。流れた分だけcapacityを減らし、逆向きで同じcapacityの辺を張る
- 1に戻る
幅優先探索(BFS)
sourceをレベル0
sourceから1辺で繋がるノードをレベル1、レベル1から1辺で繋がるノードをレベル2、、、という感じでレベルを設定
アルゴリズムは以下の通り
- sourceをレベル0とする
- レベルが確定した頂点であり、かつまだ探索していない頂点のうち最もレベルが低い頂点と繋がる辺を探索する。全ての頂点が探索済みになったら終了
- すでに子ノードnのレベルが確定している場合は"非アクティブ"とする。確定していない場合はレベルを設定する
- 2に戻る
深さ優先探索(DFS)
- sourceからsinkに辿り着くまで任意の頂点にフローを流す。アクティブな辺がなければフローを0とする
- sinkへの流入量が確定したらcapacityをフロー分減らす。
- 全ての辺で実施しフローが流せなくなったら終了
最終的なsinkへの流量が最大流になり、組み合わせの場合どれだけ条件にあった組み合わせになったかを示す。っぽい。
こういうの頑張れば当直表作るのとか自動化できるのかな、できるんだろなぁ。
