離散および非線形システム最適化のためのソフトウエア作成に関する研究

点击翻译按钮获取中文摘要

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