生産システム設計への組合せ凸解析の応用

组合凸分析在生产系统设计中的应用

• 批准号: 11878069
• 负责人: 室田 一雄
• 金额: $ 0.9万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Exploratory Research
• 财政年份: 1999
• 资助国家: 日本
• 起止时间: 1999 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-11878069/
• 关键词: 組合せ最適化; 凸解析; アルゴリズム; 離散凸関数

本研究の目的は,組合せ凸解析の理論に基づいて,生産システム設計に現れる最適化問題の組合せ構造を明確にすると共に,最適な生産システムを設計するための実用的な解法を構築することである.この目的を実現するため,本年度は以下の研究を行った.・スケーリング技法によるM凸関数最小化アルゴリズムの研究.M凸関数の最小化問題に対しては,最急降下法や領域縮小法が提案されているが,本研究においては,組合せ最適化のアルゴリズムにおいて基本的な技法であるスケーリング技法をM凸関数最小化に用いる可能性を研究した.一般にM凸関数はスケーリングに関して閉じていないが,ツリー型M凸関数や2次のM凸関数などのクラスのM凸関数がスケーリングに関して閉じていることを示すとともに,スケーリング技法と最急降下法とを組み合わせた効率的な算法を提案した.・M凸関数の運搬経路問題への応用.時間枠制約つき運搬経路問題とは,各顧客への訪問時間枠制約をなるべく満たし,かつ運搬費用を最小にする経路及びスケジュールを求める問題である.経路決定とスケジューリングを分離するタイプのヒューリスティックにおいて,最適なスケジュールを求める問題がツリー型M凸関数の最小化問題として定式化できることを示した.・2次のM凸関数・L凸関数の特徴付け.一般に2次の凸関数は半正定値対称行列で表現されるが,本研究では,どのような付加的条件がM凸性・L凸性を特徴づけかという問題意識をもち,この問題に対して完全な解答を与えた.その副産物として,確率過程論などで研究されてきたディリクレ形式との関連が明らかとなった.

The purpose of this study is to integrate the basic theory of theoretical analysis and the design of the optimization problem. in this study, the purpose of this study is to analyze the basic theory of theoretical analysis and the design of the optimization problem. the purpose of this study is to analyze the basic theory of theoretical analysis and the design of the optimization problem. The purpose of this study is to make a study of the following projects this year. This study aims to minimize the number of convexities in the field of law. This study combines the basic techniques of minimizing the number of convexations and minimizing the number of bumps in the field of law. In general, the number of bulges, the number of bulges, the number of M convex number is not suitable for the problem of moving the road. The time agreement is related to the transportation problem, and the customer schedule is used to solve the problem, and the minimum route is used to solve the problem. The way to determine the number of problems is to minimize the number of convex problems in order to minimize the problem. 2 times M convex number L convex number special payment. In general, the ranks of quadratic convex numbers and positive semidefinite numbers show that there is a problem. In this study, the condition of convexity, convexity, convex, convexity, convexity, Please make sure that you can make sure that you can learn more about the process of study and study.

项目成果

S.T.McCormick and A.Shioura: "Minimum Ratio Canceling is Oracle Polynomial for Linear Programming, but Not Strongly Polynomial, Even for Networks"Operations Research Letters. 27. 199-207 (2000)

S.T.McCormick 和 A.Shioura：“最小比率取消是线性规划的 Oracle 多项式，但不是强多项式，即使对于网络也是如此”运筹学快报。

V.Danilov,G.Koshevoy and K.Murota: "Discrete Convexity and Equilibria in Economies with Indivisible Goods and Money"Mathematical Social Sciences. (発表予定).

V.Danilov、G.Koshevoy 和 K.Murota：“不可分割商品和货币经济中的离散凸性和均衡”数学社会科学（待出版）。

A.Shioura: "Level Set Characterization of M-convex Functions"IEICE Transactions. (掲載予定). (2000)

A. Shioura：“M 凸函数的水平集表征”IEICE Transactions（即将出版）。

A.Shioura: "Level Set Characterization of M-convex Functions"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. E83-A. 586-589 (2000)

A.Shioura：“M-凸函数的水平集表征”IEICE Transactions on Fundamentals of Electronics、Communications and Computer Sciences。

K.Murota: "Discrete convex analysis - Exposition on conjugacy and duality, In Graph Theory and Combinatorial Biology, (eds.L.Lovasz,et al.)"Bolyai Society Mathematical Studies. 7. 253-278 (1999)

K.Murota：“离散凸分析 - 关于共轭性和对偶性的阐述，图论和组合生物学，（L.Lovasz 等编辑）”Bolyai 学会数学研究。