問題解決の数理(’17)

放送大学教養学部専門科目(情報) 共用科目(自然と環境) 科目コード:1570242 主任講師:大西 仁

第1章・第1回 線形最適化法(1):一次式による問題の定式化

概要
線形最適化法(線形計画法)は、目的と制約条件を一次式で記述し、制約を満たす最適解を求める手法である。制約のある資源で最大の効果を得たり、最小のコストで目的を達成するために用いられる。線形最適化問題について応用例を交え解説する。

【キーワード】
線形最適化問題、生産計画問題、食事問題、輸送問題
放送授業スライド,台本(字幕代りにどうぞ)
スライド
スライド A4版背景なし
台本
このページのトップへ
Excelソルバーによる線形最適化法
Excelソルバーアドインのインストール法はこちら
Excel 2013版 基本編 (315 kB)
Excel 2013版 感度分析編 (130 kB)
生産計画問題
輸送問題
演習問題 1.2
R (lpSolveパッケージ)による線形最適化法
インストール法と基本的な使い方はこちら
輸送問題
演習問題 1.2
GLPKによる線形最適化法
インストール法と基本的な使い方はこちら
生産計画問題
輸送問題
演習問題 1.2
このページのトップへ

第2章・第2回 線形最適化法(2):線形最適化問題の解法

概要
線形最適化問題の最適解を求める代表的なアルゴリズムであるシンプレックス法について解説する.

【キーワード】
線形最適化法,標準形,シンプレックス法
今回のポイント
  1. 線形最適化問題の最適解は実行可能領域の端点にある.
  2. 最適解は標準形の問題の制約(連立一次方程式)のうち,幾つかの変数を0に固定した解の中にある.
  3. 変数が多い場合,次々と0に固定する変数を変えて連立一次方程式を解くのは計算が大変である.
  4. シンプレックス法は,適当な実行可能解(実行可能領域の端点)から,隣接する端点で,より良い解に解を更新することを繰り返すことにより,効率的に解を得られる方法である.
  5. シンプレックス法の手続きでは,隣接する端点のうちどの端点に移るかを決定し(ピボット項の決定),ピボット操作により隣接する端点に移る.これは,0に固定する変数(非基底変数)を変えることである.
放送で取り上げなかった2段階シンプレックス法は,とりあえずは「こういう問題にはこういう方法がある」ということを認識しておけばよい.

計算の手続きは,実際に手を動かすと理解しやすい.いきなり講義を聴いて,即分かるというものではない.

このページのトップへ
放送授業スライド,台本(字幕代りにどうぞ)
スライド
スライド A4版背景なし
台本
このページのトップへ