離散および非線形システム最適化のためのソフトウエア作成に関する研究
【研究分野】広領域
【研究キーワード】
線形計画法 / Karmarkar法 / 内点法 / 混合整数計画問題 / 最良階段関数近似 / 制約条件付最短路問題 / 一般化有界変数単体法 / ポートフォリオ最適化 / 分数双線形計画問題 / 数理計画法 / 0-1整数計画問題 / 非線形最適化 / 不動点アルゴリズム / カーマーカーの方法 / (オリエンテッド)マトロイド / ファセット・カット / 組合わせ最適化
【研究成果の概要】
昨年度に引続き以下の研究を行なった。
(1)大型線形計画問題に対するKarmarkarの内点アルゴリズムにいくつかの改良を施した改訂Karmarkar法を提案し、これをプログラム化した。このプログラムを用いて小規模かつ稠密な問題と中規模かつ過疎な問題を解いた結果、前者に対しては改訂Karmarkar法が単体法の効率を上廻ることが立証された。後者については現在実験を継続中である。また、この解法の延長線上に位置する。プライマル・デュアル内点法を構成し、その収束性を証明した。
(2)線形計画法に関わる最近の理論的進歩について調査を行い、これをもとにサーベイ論文2編をまとめた。またこれらと(1)の成果等をもとにモノグラフ「線形計画法
を執筆した。
(3)化学プラントの最適運転に関わる中型の整数計画問題に対する効率的な解法を提案し、その妥当性を確かめた。またこの研究の副産物として、任意の関数に対する最良階段関数近似法が生まれた。この問題は統計学、オペレーションズ・リサーチの分野で広い応用をもつものであり、その効率的解法が得られたことは思いがけない成果であった。
(4)ある特別な制約条件の下での最短路問題を「水売行商人
問題として定式化し、その効率的な解法を提案した。
(5)複数の目的関数の中で最小(大)の値をもつものを最大(小)化する線形計画問題に一般化有界変数単体法の思想を利用したアルゴリズムを提案し、そのすぐれた特性を数値実験によって確認した。
(6)過年度に実施したポートフォリオ最適化に関する双線形分数計画法の適用結果を論文の形にまとめ専門誌に投稿した。
【研究代表者】