福田 公明, 田村 明久 　著

内容

目次

第1章　線形最適化の紹介 1.1 線形最適化の重要性 1.2 例 1.3 線形計画問題 1.4 線形計画問題を解く：これは何を意味するのか 1.5 線形計画法／線形最適化の歴史 1.6 演習問題 第2章　線形計画問題の基礎：その1 2.1 最適性の判定法 2.2 双対問題 2.3 実行不可能性の判定法 2.4 非有界性の判定法 2.5 いくつかの形式の双対問題 2.6 演習問題 第3章　線形計画問題の基礎：その2 3.1 双対問題の解釈 3.2 演習（感度分析の準備） 3.3 感度分析 3.4 演習問題 第4章　アルゴリズム 4.1 行列表記法 4.2 線形計画問題の辞書形式 4.3 ピボット演算 4.4 ピボットアルゴリズムと構成的証明 4.5 ピボット演算の実行例 4.6 ピボットアルゴリズムの図解 4.7 演習問題 第5章　線形計画問題：発展 5.1 ピボット演算の実装 5.2 感度分析の計算法 5.3 ピボットアルゴリズムの双対化 5.4 単体法のピボット規則 5.5 ピボット演算の幾何学的理解 5.6 演習問題 第6章　組合せ最適化と計算量 6.1 例 6.2 計算の効率性 6.3 グラフ理論の基本概念 6.4 演習問題 第7章　多項式可解問題 7.1 最小全域木問題 7.2 2部完全マッチング問題 7.3 割当問題 7.4 最適マッチング問題 7.5 最大流問題 7.6 最小費用流問題 7.7 演習問題 第8章　しらみつぶし探索と分枝限定法 8.1 分枝限定法 8.2 演習問題 第9章　板取り問題と列生成 9.1 板取り問題 9.2 単体法の復習 9.3 列生成 9.4 演習問題 第10章　近似アルゴリズム 10.1 集合被覆問題 10.2 貪欲法 10.3 主双対法 10.4 LP丸め法 第11章　線形計画問題に対する内点法 11.1 記号の準備 11.2 ニュートン法 11.3 主双対内点法 第12章　フリーソフトウエアを使ってみよう 12.1 LP_solveのインストール 12.2 LP_solveでの問題の記述 12.3 LP_solveで線形計画問題を解く 12.4 LP_solveで整数計画問題を解く 付録　最適化に関する有益なリンクとソフトウエアサイト