離散最適化における準凸性の理論の構築と社会工学への応用

离散优化半凸理论构建及其在社会工程中的应用

基本信息

批准号：
13874016
负责人：
室田一雄
金额：
$ 1.34万
依托单位：
The University of Tokyo (2002-2003)Kyoto University (2001)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Exploratory Research
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2003
项目状态：
已结题

项目摘要

まず,数理経済学における離散凸関数の応用について研究を進めた.不可分な財を含む経済均衡モデルにおいて,供給者の費用関数がM凸関数かつ消費者の効用関数がM凹関数の場合に競争均衡が存在することが,研究代表者らの昨年度までの研究において証明されていた.本年度はさらにこの研究を進めて,競争均衡を実際に求める方法について検討し,多項式時間で競争均衡が求められることを示した.具体的には,競争均衡を求める問題を元にしてM凸劣モジュラ流問題をつくり,これを既存の多項式時間アルゴリズムで解いて得られた出力を適切に変換することで競争均衡が得られる,という手法である.これはM凸劣モジュラ流問題の応用としても興味深い結果である.次に,最適配分問題に対する効率的な解法の研究を行った.生産ラインでのバッファ配分や労働力・資源の配分など,生産システム設計の際に頻繁に現れる最適配分問題は,離散準凸性の理論を適用しやすい問題の一つである.離散準凸関数の理論を踏まえて,現実に現れる最適配分問題を定式化し,その離散構造を明らかにすると共に効率的な解法を提案した,具体的には,劣モジュラ制約の元での最適配分問題に対するHochbaumの高速解法がなぜうまく働くのかを離散凸性の視点から検討し,その結果を元にM凸関数に対する高速な最小化アルゴリズムを提案した.また,dial-a-ride transit system, isotone regressionなどに応用をもつ,双対最小費用流問題について研究を進めた.この問題が準L凸関数最小化問題の特殊ケースである,という事実を踏まえ,既存の解法を見直し,準L凸関数に対する解法へと拡張した.

首先，我们对离散凸函数在数理经济学中的应用进行了研究。在包含不可分割商品的经济均衡模型中，当供应商的成本函数为M-凸、消费者的效用函数为M-凹时，竞争就存在。截至去年，主要研究人员的研究已经证明了竞争均衡。今年，我们将进一步推进这项研究，力争实现竞争均衡。我们研究了在多项式时间内寻找竞争平衡的方法，并证明可以在多项式时间内找到竞争平衡。具体来说，我们基于寻找竞争平衡的问题创建了一个 M 凸子模流问题，并使用现有的多项式时间对其进行了求解这是一种通过对算法求解得到的输出进行适当转换来获得竞争平衡的方法。这是一种求解M凸子模流问题的方法。这些结果对于应用也很有趣。接下来，我们对最优分配问题的有效解决方案进行了研究。优化问题在设计生产系统时经常出现，例如生产线的缓冲区分配以及劳动力和资源的分配问题就是其中之一。基于离散半凸函数理论，我们可以解决现实中出现的最优分配问题。我们制定了该方法，阐明了其离散结构，并提出了一种有效的求解方法。具体来说，我们通过研究离散凸性来研究为什么 Hochbaum 的快速求解方法能够很好地解决子模约束下的最优分配问题。基于结果，我们提出了一种快速最小化方法。 M 凸函数的算法。我们对对偶最小成本流问题进行了研究，该问题在交通系统、等色调回归等方面都有应用。基于该问题是拟L凸函数最小化问题的特例，我们回顾了现有的求解方法该方法已扩展到求解 L 凸函数。