第4回 線形計画 2000年11月 第4回 線形計画.

Slides:



Advertisements
Similar presentations
<最適化の概念> 最適化すべき問 題 数学モデル 変数,数式 数理計画法 定められた計算手 順を用いて解くた めの方法論.
Advertisements

Excel ソルバー練習 *ツール → アドイン → ソルバーアド インにチェックを入れて、ソルバー を使えるようにしてから、作業を行 うこと。
MS-EXCEL、 OpenCalcを 用いた表計算
第6回 線形計画法の解法(4) 混合最小値問題 山梨大学.
データ解析
情報処理実習 第05回 Excelマクロ機能入門 操作マクロ入門.
線形計画 追加問題 ジュースを売って儲けよう!
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp
「基礎OR」/「OR演習」 第2回 10/06/2009 森戸 晋.
第八回  シンプレックス表の経済的解釈 山梨大学.
コンパイラ 2011年10月17日
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
Pattern Recognition and Machine Learning 1.5 決定理論
情報処理 第13回の教材 プレゼンテーションソフト PowerPoint 高知大学 共通教育 理学部 対象 担当:塩田 ここはメモを書く欄。
ファーストイヤー・セミナーⅡ 第8回 データの入力.
第三回 線形計画法の解法(1) 標準最大値問題 山梨大学.
最短路問題をGurobiで解こう! 流通最適化工学 補助資料.
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
Q q 情報セキュリティ 第6回:2005年5月20日(金) q q.
第四回 線形計画法(2) 混合最大値問題 山梨大学.
マルチエージェント・シミュレーション(2)
最適化ソルバーのための Python言語入門
マルチエージェント・シミュレーション(2)
土木計画学 第11回(12月21日) 土木計画と説明責任 計画における代替案の作成1 担当:榊原 弘之.
「基礎OR」/「OR演習」 第3回 10/13/2009 森戸 晋.
第二回 連立1次方程式の解法 内容 目標 連立1次方程式の掃出し法 初期基底を求める 連立1次方程式を掃出し法を用いてExcelで解析する
第5回 双対問題 テキストp 内容 双対問題の導出 式を足しあわせる方法 Lagrange緩和 相補性条件 双対辞書
第 七 回 双対問題とその解法 山梨大学.
1章前半.
第3回:ボールを上下に動かそう! (オブジェクトの移動、一次元)
線形計画法 スケールフリーネットワーク 須藤 孝秀.
コンパイラ 2012年10月15日
第7回 条件による繰り返し.
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
Linear Relaxation for Hub Network Design Problems
サポートベクターマシン によるパターン認識
ORの手法(組合せ最適化) 社会情報特講Ⅲ 大堀隆文(非常勤講師).
第4章 組合せ論理回路 (4) Quine McCluskeyの方法.
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
AMPLについて 2011年12月2日(金) 経営システム工学科 森戸 晋.
混合ガウスモデルによる回帰分析および 逆解析 Gaussian Mixture Regression GMR
人工知能特論 9.パーセプトロン 北陸先端科学技術大学院大学 鶴岡 慶雅.
第7回 条件による繰り返し.
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
ファジィ制約充足問題への 連続領域の導入 Introducing continuous domains to
ex-8. 平均と標準偏差 (Excel 実習シリーズ)
4. システムの安定性.
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
第3章 線形回帰モデル 修士1年 山田 孝太郎.
サポートベクターマシン Support Vector Machine SVM
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
第9章 学習アルゴリズムとベイズ決定側 〔3〕最小2乗法とベイズ決定側 発表:2003年7月4日 時田 陽一
プログラミング入門 電卓を作ろう・パートI!!.
Solver for COnstraint Programming:スコープ Pythonモジュールの使い方
土木計画学 第12回(1月14日) 計画における代替案の作成2 担当:榊原 弘之.
情報工学概論 (アルゴリズムとデータ構造)
精密工学科プログラミング基礎 第7回資料 (11/27実施)
ex-8. 平均と標準偏差 (Excel を演習で学ぶシリーズ)
アルゴリズム入門 (Ver /10/07) ・フローチャートとプログラムの基本構造 ・リスト ・合計の計算
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
プログラミング基礎a 第3回 C言語によるプログラミング入門 データ入力
Cプログラミング演習 ニュートン法による方程式の求解.
精密工学科プログラミング基礎Ⅱ 第2回資料 今回の授業で習得してほしいこと: 配列の使い方 (今回は1次元,次回は2次元をやります.)
情報処理Ⅱ 2005年11月25日(金).
プログラミング基礎a 第3回 C言語によるプログラミング入門 データ入力
東京工業大学情報理工学研究科 小島政和 第1回横幹連合コンファレンス 2005年11月25,26日 JA 長野県ビル
各種荷重を受ける 中空押出形成材の構造最適化
Presentation transcript:

第4回 線形計画 2000年11月 第4回 線形計画

内容 線形計画と図式解法 辞書と単体法 番外編 Excelによる線形計画 2000年11月 第4回 線形計画

線形計画法の大まかな歴史 1947年 単体法 Dantzig 比較的単純な方法 1979年 楕円体法 Khachian 多項式時間解法,非実際的 1984年 内点法 Karmarkar 理論的には多項式時間解法,実際的に効率的 2000年11月 第4回 線形計画

丼チェーン店長の悩み トンコケ丼,コケトン丼,ミックス丼の3種類 トンコケ丼を1杯作るには,200グラムの豚肉と100グラムの鶏肉コケトン丼を1杯作るには,100グラムの豚肉と200グラムの鶏肉ミックス丼は,豚肉,鶏肉,牛肉を100グラムずつミックス 豚,鶏,牛の肉は,最大1日あたり6キログラム,6キログラム,3キログラム 販売価格は,トンコケ丼1杯1500円,コケトン丼1杯1800円,ミックス丼1杯3000円 お店の利益を最大にするためには,あなたは丼を何杯ずつ作るように指示を出せばよいのだろうか? 2000年11月 第4回 線形計画

丼チェーン店長の悩み(図) 種類 トンコケ丼 コケトン丼 ミックス丼 使用可能量 (百グラム) 豚 2 1 60 鶏 牛 30 利益 30 利益 (百円) 15 18 2000年11月 第4回 線形計画

定式化 トンコケ丼の数:x1(杯) 変数 コケトン丼の数:x2 (杯) ミックス丼の数:x3 (杯) 目的関数 制約式 材料の使用可能量の上限 (百グラム) 丼の数は非負 2000年11月 第4回 線形計画

定式化 線形 変数の加減算より構成 すべての式が線形な問題 線形計画問題 解 変数の組 実行可能解 全ての制約式を満たす解 最適解 目的関数を最大にする実行可能解 最適目的関数値(最適値) 最適解における目的関数値 2000年11月 第4回 線形計画

定式化 豚肉の使用可能量を表す制約式 制約式を等号で満たすような集合 {(x1, x2, x3) | 2x1 + x2 + x3 = 60} (3次元の場合)平面 (4次元以上の場合)→超平面 半空間 全ての制約式を満たす領域→半空間の共通部分 実行可能領域 2000年11月 第4回 線形計画

直感的理解 平面 2x1 + x2 + x3 = 60 2000年11月 第4回 線形計画

直感的理解 平面 x1 + 2x2 + x3 = 60 2000年11月 第4回 線形計画

直感的理解 平面 x3 = 30 2000年11月 第4回 線形計画

直感的理解 丼チェーン店の例題の 実行可能領域 多面集合 2000年11月 第4回 線形計画

多面集合 数式による表現 有界な多面集合→多面体 2000年11月 第4回 線形計画

多面集合 線形計画問題の目的 ↓ 実行可能領域の中で目的関数が最大の点を求めること 目的関数を等式に直す z = 15x1 + 18x2 + 30x3 zを固定したとき,この制約は平面 実行可能領域との共通部分が なくならないように zを大きくする 端点 2000年11月 第4回 線形計画

定理1:多面集合の端点 端点でない 多面集合が有界である 必ず端点を持つ P 多面集合が直線を含まない (直線と半直線・線分は異なることに注意) 端点 2000年11月 第4回 線形計画

端点を持たない多面集合の例 有界でない多面集合 2000年11月 第4回 線形計画

最適解が端点でない例 直線上は全て最適解 P 目的関数の方向ベクトル 直線上の両端は端点なので 端点の中に最適解が存在することは 保証される 2000年11月 第4回 線形計画

定理2 線形計画問題に最適解が存在し,線形計画問題の制約からなる多面集合が少なくとも1つの端点を持つならば,多面集合の端点の中に最適解が存在する. 2000年11月 第4回 線形計画

ちょっと練習 丼チェーン店の例題の制約を表す多面体の全ての端点 (8つ)を求めてみよう. それぞれの平面の式は 2x1 + x2 + x3 = 60 x1 + 2x2 + x3 = 60 x3 = 30 x1 = x2 = x3 = 0 2000年11月 第4回 線形計画

さらに練習 丼チェーン店の例題の制約を表す多面体の全ての端点 (8つ)に対応する目的関数値を求めてみよう. 2000年11月 第4回 線形計画

最適解 最適解 目的関数値:1230(対応する端点は(10,10,30)) 丼チェーンの店長は,トンコケ丼を10杯,コケトン丼を10杯,ミックス丼を30杯作るよう指示すればよい. 1日あたり123000円の利益をあげることができる. 2000年11月 第4回 線形計画

実際には 実際には,全ての端点を数え上げてその目的関数を計算することは非効率的. 効率的に最適解を算出したほうがよい. 2000年11月 第4回 線形計画

単体法 適当な端点から出発して目的関数値を改良する端点に移動 ↓ 最小木問題で勉強した改善法の考え方 1947年 Dantzigが単体法を考案 太陽(目的関数)の暖かさに誘われた蟻さんが多面体の縁をたどって移動 2000年11月 第4回 線形計画

余裕変数 制約式を等式に直すために余裕(スラック)変数を導入 標準形 2000年11月 第4回 線形計画

余裕変数を含めた端点と目的関数値 x1 x2 x3 s1 s2 s3 目的関数値(百円) 60 30 450 540 20 660 900 60 30 450 540 20 660 900 15 1125 1170 10 1230 いずれもちょうど3つの変数が0になっている 2000年11月 第4回 線形計画

基底変数 0に固定した変数→非基底変数 それ以外の変数→基底変数 基底解 m本の等式制約,n個の変数 m個の変数が基底変数 2000年11月 第4回 線形計画

基底解 基底解 端点解 丸が基底解 黒丸は端点解 全ての変数が非負である基底解 →実行可能基底解 2000年11月 第4回 線形計画

単体法 実行可能基底解を次々と生成することによって 最適解を得る方法 基底解を表すには色々な流儀 今回は辞書による方法を採用 モダン 2000年11月 第4回 線形計画

初期辞書 非基底変数(=0) 初期辞書 z =0 +15x1 +18x2 +30x3 s1=60 -2x1 -x2 -x3 辞書表現 平たく言えば等式の集合 x1=x2=x3=0 s1=60, s2=60, s3=30 z=0 を表す これを改善する 2000年11月 第4回 線形計画

改善 改善=zの値を増加 x3を1大きくすれば zは30増加 z =0 +15x1 +18x2 +30x3 x1を1大きくすれば 2000年11月 第4回 線形計画

改善 x1, x2を固定しx3をどこまで大きくできる? s1=60 -x3 s1,s2,s3は非負より s2=60 -x3 2000年11月 第4回 線形計画

辞書の変形 初期辞書 z =0 +15x1 +18x2 +30x3 s1=60 -2x1 -x2 -x3 次の辞書 z =?? +??x1 +??x2 +??s3 s1=?? +??x1 +??x2 +??s3 s2=?? +??x1+??x2 +??s3 x3=?? +??s3 どうなる? 等式変形を使う 2000年11月 第4回 線形計画

辞書の変形 次はここに注目 1反復後の辞書 z =900+15x1+18x2-30s3 s1=30 -2x1 -x2 +s3 2000年11月 第4回 線形計画

ちょっと練習 x2を基底変数としてみよう. どれを非基底変数とする? 改善後の辞書は? 2000年11月 第4回 線形計画

辞書を用いた単体法の法則 法則1:非基底変数のうち最も改善効果の大きい変数を選び, それを基底変数にするように辞書を変形する 法則2:最も改善効果の大きい変数が複数ある場合には, 添え字の最も小さいものを選ぼう(巡回対策) 法則3:辞書の変形の際に,基底変数から非基底変数にできるものが複数ある場合には,やっぱり添え字の最も小さいものを選ぼう(退化対策) わかりづらい場合には 非基底変数→=の右側の変数 基底変数→=左側の変数 と読み替えても可 2000年11月 第4回 線形計画

さらに練習 3反復後の辞書を作ってみよう 2000年11月 第4回 線形計画

最終辞書 もう改善できそうにないので終了 2000年11月 第4回 線形計画

番外編 Excelによる線形計画 2000年11月 第4回 線形計画

Excelに書く 次は変数を導入 2000年11月 第4回 線形計画

変数を導入 トンコケ丼の生産量x1を表す コケトン丼の生産量x2を表す ミックス丼の生産量x3を表す 次は目的関数の設定 2000年11月 第4回 線形計画

目的関数の設定 次は制約条件の設定 2000年11月 第4回 線形計画

豚肉の使用量の制約 2000年11月 第4回 線形計画

鶏肉の使用量の制約 2000年11月 第4回 線形計画

牛肉の使用量の制約 これでシート上で必要な準備は整った,次はソルバーの使い方 2000年11月 第4回 線形計画

初めてのソルバー 2000年11月 第4回 線形計画

ソルバーとは OKを選択すれば 使えるようになる 2000年11月 第4回 線形計画

ソルバーの起動 2000年11月 第4回 線形計画

ソルバーの設定 2000年11月 第4回 線形計画

ソルバーの設定 2000年11月 第4回 線形計画

ソルバーの設定 2000年11月 第4回 線形計画

ソルバーの設定 2000年11月 第4回 線形計画

ソルバーの実行 準備が整ったら実行 2000年11月 第4回 線形計画

ソルバーの結果 これはどちらでも良い 2000年11月 第4回 線形計画

流通最適化工学 追加資料 Excel 2010でのソルバー起動法 ファイル/(下部の)オプション/アドイン (Excel2007ではOfficeボタン,Excel2003ではツール/アドイン) ソルバーアドインをクリックして,下部の管理でExcelアドインの設定ボタンを押す. 上部リボンのデータの右端にソルバーができているので,それをクリック 2000年11月 第4回 線形計画

GurobiソルバーとPythonで求解!Gurobi (1) MIP solver Developed by: Zonghao Gu, Edward Rothberg,Robert Bixby Free academic license!計算機センターでGurobiを一度起動した後, Python IDLEで記述 “gurobipy” モジュールの読み込み from gurobipy import * モデルオブジェクト model をModelクラスから生成(引数はモデルの名前 model = Model(“Product Mix") 2000年11月 第4回 線形計画

Gurobi (2) 変数オブジェクトをmodelオブジェクトのaddVarメソッドを用いて生成(引数は名前;省略可) x1 = model.addVar(name="x1") x2 = model.addVar(name="x2") x3 = model.addVar(name="x3") モデルの更新(制約を追加する前に必ず呼ぶ) model.update() 2000年11月 第4回 線形計画

Gurobi (3) 目的関数の設定 model.setObjective(15*x1 + 18*x2 + 30*x3, GRB.MAXIMIZE) 制約の追加 model.addConstr(2*x1 + x2 + x3 <= 60) model.addConstr(x1 + 2*x2 + x3 <= 60) model.addConstr(x3 <= 30) 最適化 model.optimize() 2000年11月 第4回 線形計画

Pythonのリストを用いた記述 変数オブジェクトをリストxに追加 x=[] for i in range(3): var=model.addVar() x.append(var) 制約 “x1 + x2 + x3 <= 2”の記述 model.addConstr( sum(x) <= 2 )  もしくは model.addConstr( quicksum(x) <= 2 ) (高速版) 2000年11月 第4回 線形計画

Pythonの辞書を用いた記述 名前(“TonKoke”, “KokeTon”, “Mix”) を変数オブジェクトの写像する辞書 x={} x[“TonKoke”]= model.addVar() x[“KokeTon”]= model.addVar() x[“Mix”]= model.addVar() 制約“2x1 + x2 + x3 <= 30”の追加 model.addConstr( 2*x[“TonKoke”]+ x[“KokeTon”] +x[“Mix”] <=30 ) 2000年11月 第4回 線形計画

辞書を用いたデータ入力 Bowels, Profit = multidict({“TonKoke”:15, “KokeTon”:18, “Mix”:30}) => Bowels=[“TonKoke”, “KokeTon“, “Mix“] キー(丼)のリスト Profit[“TonKoke”]=15, Profit[“KokeTon”]=18, ... 利益の辞書 Meats, Inventory = multidict({“Pork":60, “Chiken":60, “Beef":30}) 肉のリスト Meetsと使用可能量の辞書の同時生成 Use = { (“Pork”,“TonKoke”):2, (“Pork”,“KokeTon”):1, (“Pork”,”Mix“):1, (“Chicken”,“TonKoke”):1, .... } 肉と丼のタプル(組)をキー,使用量を値とした辞書 2000年11月 第4回 線形計画

辞書を用いた最適化 x = {} # 変数を保管する辞書 for j in Bowels: # 丼ごとに変数の生成 x[j] = model.addVar() model.update() #モデルの更新 model.setObjective(quicksum(Profit[j]*x[j] for j in Bowels), GRB.MAXIMIZE) #目的関数の最大化 for i in Meats: model.addConstr(quicksum(Use[i,j]*x[j] for j in Bowels) <= Inventory[i]) #制約の追加 model.optimize() print “Obj=”,model.ObjVal #最適値の表示 2000年11月 第4回 線形計画