科目分野	理工学部
選必区分	選択
担当教員 ［ローマ字表記］	池田　建司　[Kenji Ikeda]
授業形態	講義

授業の目的

本講義は2つの部分からなる. 前半は線形計画法であり，その理論と計算法について 解説する. 後半では，ネットワーク上の最適化を論じる. 基礎理論を厳密に展開し， 理解させることを目的としているが，同時に，理解をより容易にするため，理論の 意味を幾何学的に把握できるよう配慮している. また，例題を取り上げ，演習を 実施している.

授業概要

線形計画法とネットワーク最適化について講義している. 線形計画法では，その定式 化の方法，シンプレックス解法を中心とした計算法，シンプレックス法の有効性を保 証する基本定理，理論的背景であり，かつ線形計画法の幾何学的解釈を示している 双対定理とファーカスの補題などについて述べる. ネットワーク最適化では，代表的な問題として，最短経路問題，最小木問題，最大流問題を扱う.

到達目標

1. 数理モデルにもとづくシステマティックな解析・設計能力を養い， 最適化理論やシステム工学といった学問体系の基礎となす．


2. シンプレックス法によって線形計画問題を解くことができる．


3. 主問題と双対問題との関係を述べることができる．


4. 最短経路問題，最小木問題，最大流問題を解くことができる．


5. 最大流・最小カット問題の双対性を説明できる．

授業計画

第１回：線形計画法の導入
第２回：図的解法から代数的解法へ
第３回：線形計画法の基本定理とシンプレックス法
第４回：2段階法
第５回：行列表現と改訂シンプレックス法
第６回：双対問題，双対定理，ファーカスの補題
第７回：演習1（シンプレックス法と双対理論）
第８回：グラフ理論の復習
第９回：最短経路問題(Dijkstra法)
第１０回：最小木問題(Krukal 法)
第１１回：最小木問題(Prim 法)
第１２回：最大流・最小カット問題
第１３回：最大マッチング・最小カバー定理
第１４回：演習2（ネットワーク上の最適化問題）
第１５回：演習3（模擬試験，線形計画法）
定期試験

教科書

特に指定しない. 配布資料とスライドによって講義を進める.

キーワード

線形計画法, 双対性, ネットワーク最適化