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

离散非线性系统优化软件创建研究

基本信息

批准号：
59400004
负责人：
今野浩
金额：
$ 5.5万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (A)
财政年份：
1984
资助国家：
日本
起止时间：
1984 至 1986
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-59400004/
关键词：
線形計画法 Karmarkar法内点法混合整数計画問題最良階段関数近似制約条件付最短路問題一般化有界変数単体法ポートフォリオ最適化分数双線形計画問題数理計画法 0-1整数計画問題非線形最適化不動点アルゴリズムカーマーカーの方法 (オリエンテッド)マトロイドファセット・カット組合わせ最適化

项目摘要

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

在去年进行了以下研究之后：（1）我们提出了一种修订后的Karmarkar方法，该方法已改进了Karmarkar的内点算法，用于大规模线性编程问题，并对此进行了编程。使用此程序，我们解决了小问题，密集的问题以及中等和人口减少的问题，并且证明了修订后的Karmarkar方法超过了前者的单组分方法的效率。后一个实验目前正在继续。它也是该解决方案的扩展。构建了一种原始的双重内点方法，并证明了其收敛性。（2）我们调查了线性编程的最新理论进步，因此，我们编制了两篇调查论文。基于这些和（1）的结果，我编写了专着线性编程方法。（3）我提出了一种有效的解决方案，以解决与化学植物最佳运行有关的中型整数编程问题，并确认其有效性。此外，作为这项研究的副产品，任意功能的最佳步骤函数近似方法诞生了。这个问题在统计和操作研究领域中具有广泛的应用，而有效的解决方案是一个意外的结果。（4）特殊约束下最短的路径问题被提出为水交易员问题，并提出了有效的解决方案。（5）提出了一种利用广义有界变量单状态方法的概念的算法，用于线性编程问题，该问题在多个目标函数中最大化（小），并通过数值实验确认了其优异的属性。（6）在上一年实施的双线性分数编程方法用于投资组合优化的结果是以论文的形式进行了总结的，并提交给专业期刊。