離散システム論 [2012年度後期]

• シラバス (PDF)
• 担当教官
  • 安藤和敏 (静岡大学工学部)
• テキスト
  • V. フバータル: 「線形計画法(上)」 啓学出版, 1986年.
  • W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver: Combinatorial Optimization . John Wiley & Sons, 1997.
• 参考書
  • 藤重悟: グラフ・ネットワーク・組合せ論. 共立出版, 2002年. [著者によるサポートのページ]
• 講義内容
  • 第01回 [2012.04.12] ガイダンス, 線形計画法(第1章 p. 3--8).
  • 第02回 [2012.04.19] シンプレックス法 (第2章 第1の例, p.17--22を丁寧にやった. 第2の例はとばして, p.26までの用語の説明: 字引の定義, 可能字引, 基底変数, 非基底変数. 入る変数, 出る変数, ピボット行, ピボット演算)
    可能基底解の話をするのを忘れた.
  • 第03回 [2012.04.26] おとし穴とその対策 (循環, 最小添字規則, p.34--40)
    先週話し忘れた可能基底解の話が長すぎて, 循環が最後まで説明できなかった.
  • 第04回 [2012.05.10] おとし穴とその対策 (初期化, 線形計画法の基本定理 p.49--54)
  • 第05回 [2012.05.17] 双対定理(1) (双対問題, 双対定理とその証明)
    動機づけの節はとばしたけど, そこににある例を用いて, 双対問題の作り方, 双対の双対が主, 及び, 双対問題弱双対性を示した. 弱双対性は一般的にやっても良かったと思った.双対定理は一般的に示した.
  • 第06回 [2012.05.24] 双対定理(2) (主問題と双対問題の関係, 相補性)
  • 第07回 [2012.05.31] 一般LPの双対定理と相補定理
  • 第08回 [2012.06.07] 中間試験
  • 第09回 [2012.06.14] 最大フロー問題 (1)
  • 第10回 [2012.06.21] 最大フロー問題 (2)
  • 第11回 [2012.06.28] 最短路問題 (可能ポテンシャルとフォードのアルゴリズム)
  • 第12回 [2012.07.05] 最短路問題 (可能ポテンシャルの存在と負の有向閉路の存在)
  • 第13回 [2012.07.12] 最小費用フロー問題(プライマルアルゴリズム, 相補性条件)
    配布資料(PDF)
  • 第14回 [2012.07.19] 最小費用フロー問題(最適性の条件, プライマルデュアルアルゴリズム)
    配布資料(PDF)
  • 第15回 [2012.07.26] (休講)
  • 期末試験 [2012.08.02]
• 課題
  • 課題1 (提出期限 2012.04.19)
    テキスト第1章章末(p.11-12)の問題1.1, 問題1.2.
    ただし1.1については, 標準形でない問題を標準形に直しなさい.
  • 課題2 (提出期限 2012.04.26)
    テキスト第2章章末の問題2.1.
  • 課題3 (提出期限 2012.05.10)
    p. 35の第5反復の字引を初期字引として出発し, 最小添字規則を用いるシンプレックス法の反復を繰り返して最適解を求めよ.
  • 課題4 (提出期限 2012.05.17)
    テキスト第3章章末の問題3.9.
  • 課題5 (提出期限 2012.05.31)
    テキスト第5章章末の問題5.3.
  • 課題6 (提出期限 2012.06.28)
    最大フロー問題の演習. プリントを配布した.
  • 課題7 (提出期限 2012.07.19)
    プライマル法の演習問題. プリントを配布した.