权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

離散凸解析による資源配分問題の研究

基于离散凸分析的资源分配问题研究

基本信息

批准号：
20K11697
负责人：
室田一雄
金额：
$ 1.91万
依托单位：
The Institute of Statistical Mathematics (2021-2022)Tokyo Metropolitan University (2020)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本研究の目的は，離散凸解析の双対理論を軸に据えて，離散資源の公平配分問題に関する理論とアルゴリズムを構築することである．この目的に沿って，以下の成果を得た．Ｍ凸集合上の辞書式最適化問題は，基多面体上の辞書式最適化問題において，変数に整数制約を課した問題と位置付けることができる．後者については，1980年頃に構造定理やアルゴリズムを含む包括的な理論が構築されている．これに関して詳細な文献調査を行い，連続変数の場合と離散変数の場合の構造定理とアルゴリズムの比較を行い，離散変数理論と連続変数理論の構造的な対応関係を解明して論文を完成させた．これにより，基多面体上の資源公平配分問題に関する理論とアルゴリズムの全体像が明確となった．離散資源の公平配分問題のより一般的問題設定として，劣モジュラ制約をもつネットワークフローを扱った．従来知られていた線形関数を目的関数とする劣モジュラ制約フロー問題の解法と整合する形で，公平配分の成す集合の記述と効率的なアルゴリズムの設計に成功し，論文として公表した．離散凸解析の理論と多面体的組合せ論を繋ぐためには，離散凸集合の不等式表現を明らかにする必要がある．離散凸解析において，今まで，Ｍ凸系統の集合の不等式表現は十分解明されてきたが，Ｌ２凸集合の不等式による記述は明らかにされていなかった．本研究においては，Ｌ凸集合が有向グラフの最短路に関係した不等式系で記述されることに着目し，Ｌ２凸集合の不等式表現を導出した．ここで得られた定理は，離散資源の公平配分問題とは独立に，離散凸解析の基本定理として重要な成果である．

The purpose of this study is to construct a theory for the fair allocation of discrete resources based on the two-axis theory of discrete convex analysis. For this purpose, the following results are obtained. Lexicographic optimization problems on M-convex sets are lexicographic optimization problems on base polyhedra. Since 1980, the construction theorem has been included in the theory of construction. This paper is completed by investigating the literature in detail, comparing the construction theorem of discrete variable number theory with discrete variable number theory, and explaining the construction relation between discrete variable number theory and continuous variable number theory. The problem of fair allocation of resources on a basic polyhedron is related to the theory and the whole picture of the problem. The fair allocation of discrete resources is a general problem. To know the linear relationship between the number of target and the number of poor constraints on the solution of the problem of integration, fair distribution of the composition of the set of description and efficiency of the design of success. Theory of discrete convex analysis and combinatorial theory of polyhedra Discrete-time convex analytic solutions are presented in this paper. The inequalities of sets of M-convex systems are very clear. The inequalities of L2 convex sets are described in detail. In this paper, the inequality system of L2 convex sets is described and the inequality representation of L2 convex sets is derived. The fundamental theorem of discrete convex analysis is an important result of the problem of fair allocation of discrete resources.