計算による最適化入門

計算による最適化入門
著者 福田 公明 著・ 田村 明久 著・ 高山 信毅 編・ 濱田 龍義
分野 数学  > OR  > 最適問題
数学  > 離散数学  > 最適化問題
数学  > OR  > 線形計画法
シリーズ 数学  > コンピュータが育む数学の展開 全10巻
発売日 2022/07/25
ISBN 9784320115217
体裁 A5・218頁
定価 3,630円 (本体3,300円 + 税10%)
  • この本の
    内容
  • 目次
  • 関連情報

最適化問題とは、「ある場所をスタートし、指定されたすべての場所を通って再び戻る最短時間はどうなるか」といった、いくつかの制約の下である種の目的尺度を最小化(あるいは最大化)する問題である。本書はその最適化問題に関して具体的な例の計算を取り扱いながら、主に線形最適化と組合せ最適化という二つの主題を中心に解説していく。
前半では線形最適化の基本理論を最小限の数学用語を用いて与え、また、十文字法と単体法という線形最適化に対する二つのアルゴリズムを、その有限終了性の議論を含めて与える。後半では、まずクラスP、NP、co-NPおよびNP完全という計算量理論の概念を議論し、それぞれのクラスに属する組合せ最適化問題を扱う。さらに非線形最適化の技法にも触れ、最後には本書の解説でも使用されるフリーソフトウエアLP_solveの利用例にも触れる。最適化を学びたい多くの人にとって大変有用な書籍となろう。

第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で整数計画問題を解く

付録 最適化に関する有益なリンクとソフトウエアサイト

Shopping
ご注文

3,630円
(本体3,300円 + 税10%)

ネット書店で購入