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

• シラバス (PDF)
• 担当教官
  • 安藤和敏 (静岡大学工学部)
• テキスト
  • V. フバータル: 「線形計画法(上)」 啓学出版, 1986年.
  • W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver: Combinatorial Optimization . John Wiley & Sons, 1997.
• 参考書
  • 藤重悟: グラフ・ネットワーク・組合せ論. 共立出版, 2002年. [著者によるサポートのページ]
• 講義内容
  • 第01回 [2011.10.05] ガイダンス, 線形計画法(第1章 p. 3--8).
  • 第02回 [2011.10.12] シンプレックス法(1) (第2章 第1の例, p.17--22)
  • 第03回 [2011.10.19] シンプレックス法(2) (第2章 字引, 第2の例, 用語について, 第2の例(つづき) p.22--27)
  • 第04回 [2011.10.26] おとし穴とその対策 (p.34--40)
  • 第05回 [2011.11.02] おとし穴とその対策 (最小添字規則, 初期化, 線形計画法の基本定理 p.49--54)
  • 第06回 [2011.11.09] 双対定理(1)
  • 第07回 [2011.11.16] 双対定理(2)
  • 第08回 [2011.11.22] 中間試験
  • 第09回 [2011.11.30] 相補性定理、一般LPの双対性と相補性
  • 第10回 [2011.12.07] 最大フロー問題 (フローとカット,最大フロー最小カット定理の証明)
  • 第11回 [2011.12.14] 最大フロー問題 (最小カットと線形計画法)
  • 第12回 [2012.01.11] 最短路問題 (可能ポテンシャルとフォードのアルゴリズム)
  • 第13回 [2012.01.18] 最小費用フロー問題(プライマルアルゴリズム, 相補性条件)
  • 第14回 [2012.01.25] 最小費用フロー問題(最適性の条件)
  • 第15回 [2012.02.01] (休講)
  • 期末試験 [2012.02.08]
• 課題
  • 課題1 (提出期限 2011.10.12)
    テキスト第1章章末(p.11-12)の問題1.1, 問題1.2.
    ただし1.1については, 標準形でない問題を標準形に直しなさい.
  • 課題2 (提出期限 2011.10.19)
    テキスト第2章の章末(p.33)の問題2.1.
  • 課題3 (提出期限 2011.11.09)
    
    1. p.39の第5反復後の字引を初期字引として出発し, 最小添字規則を 用いたシンプレックス法の反復を繰り返して, 最適解を求めよ。
    2. テキスト第3章の章末(p.56)の問題3.9.
  • 課題4 (提出期限 2012.01.11)
    最大フロー,最小カット,線形計画法 (PDF)