基础OR第回.PPT

* 制約条件あれこれ 個別の変数に上下限制約がついている ｘ 1　≦　50 流量（水、エネルギー、交通量等）に制限がある Supply1 + Supply2 + Supply3　≦　100 資源が限られている 6?Product1 + 9?Product2　≦　300　（原料供給制約） 一定品質を守らなければならない 6?Iron1 + 9?Iron2　≧　7　（原料品質制約） 流量がバランスしなければならない Stockt＝ Stockt-1 + Productiont － Salest（期末在庫量） * 整数計画問題（ＩＰ）(Integer Programming Problem) 整数計画問題　＝　線形計画問題　＋　変数の整数条件 多くの、重要な、組み合わせ「最適化問題」(Combinatorial Optimization Problem)が整数計画問題として表現可能 一般に、線形計画問題より解きにくい * 数理計画法（数理計画問題）あれこれ 線形計画法(Linear Programming) 数理計画の基本 非線形計画法（NonLinear Programming) 2次計画法（Quadratic Programming) ネットワーク計画法（Network Programming) 整数（線形）計画法（Integer Programming) 確率計画法（Stochastic Programming) 動的計画法（Dynamic Programming) ??? * 数理計画モデルをどう解くか 解析解　→　ほとんど期待できない　例：根の公式、連立方程式のクラメルの公式 最適解法　→　反復的アルゴリズムによる求解　与えられた問題（モデル）に対して最適性を保証する解法　（この授業では最適解法を扱う） 近似解法、ヒューリスティックス解法　→　実用的、どれぐらい最適に近いかは分からない場合が多い；最適性の保証はないが、そこそこの解を出してくれる解法 * （３製品版）生産計画問題 早稲田工場では、３つの製品、製品１、製品２、製品３を生産） 原料として、鉄鋼、電力、労働力を使用 １個当たり　製品１　製品２　 製品３　保有量利益　　　　 ２万円　 ３万円 ４万円鉄鋼　　　　　１　　　　　２　　　　３　　　　１４電力　　　　　１　　　　　１　　　　２　 　　　８労働力 　 ３ １　　　　２　　　　１８ * 生産計画問題の定式化 変数（決めること）　→　変化させるセル 製品１、２、３の生産量 ｘ１，ｘ２，ｘ３ 最大化 ｚ＝２ ｘ１＋３ ｘ ２＋４ ｘ ３ （目的関数：利益）　　　　　　　　　　　　　　　　　　　　　　　　　→　目的セル 制約条件 ｘ１＋２ ｘ ２＋３ ｘ ３ ≦ １４（鉄鋼） ｘ１＋ ｘ ２＋２ ｘ ３ ≦ ８ （電力） ３ ｘ１＋ ｘ ２＋２ ｘ ３ ≦ １８（労働力） ｘ１，ｘ２ ，ｘ３≧０ * ソルバーの求解手順（１）シート設定 ０．問題を定式化 １a．係数行列作成 １b．変数セルと目的セルの位置決定 １c．その他説明用の文字列等入力 １d．制約左辺の値と目的関数値の計算式定義（SUMPRODUCT利用） 　 製品1　製品2　製品3 　　　　　　 ｚ＝２ ｘ１＋３ ｘ ２＋４ ｘ ３ 　　（鉄鋼）　　　１ ｘ１＋２ ｘ ２＋３ ｘ ３ ≦ １４ （電力） 　　 １ ｘ１＋１ ｘ ２＋２ ｘ ３ ≦ ８ （労働力） 　３ ｘ１＋１ ｘ ２＋２ ｘ ３ ≦ １８ * ソルバーの求解手順（２）　ソルバー設定 ２a．目的セル定義 ２b．変数セル定義 ２c．制約条件定義 ３．オプション設定（「線形モデル」と「非負数」にチェック） （４．実行） 手順１　EXCELシートの設定 変数（変化させるセル） 目的関数値（目的セル） 計算式の設定 SUMPRODUCT 手順２　ソルバーパラメータ設定 手順２　ソルバーパラメータ設定 手順３　ソルバーオプション設定 手順４　実行とレポート生成(1) 手順４　実行とレポート生成(2) 手順４　実行とレポート生成(3) 手順４　実行とレポート生成(4) * ソルバー使用上の留意点 「変化させるセル」（変数セル）はなるべく一箇所にまとめる 複数の部分に分かれている場合はコンマ区切り 式をコピーする場