Research on Value of Information to Combinatorial Optimization

信息对组合优化的价值研究

• 批准号: 10680428
• 负责人: ISHII Hiroaki
• 金额: $ 1.86万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10680428/
• 关键词: Fuzzy random variable; Variational inequality problem; Mollifier; Fuzzy duedate; Fuzzy processing time; Fuzzy random facility location problem; Fuzzy random knapsack problem; Fuzzy random spanning problem; ファジィ関数; ファジィ微分; 配置問題; スケジューリング; 情報の価値

This research is to investigate value of information to combinatorial optimization. The aim of this research is to clarify the effects of random and fuzzy factors in the combinatorial optimization models. Especially the solutions are changed according to the existence of uncertainty and/or ambiguity. First we considered linear programming problems under both random and fuzzy factors. Based on the results on so called these fuzzy random linear programming problems, we considered scheduling problems with fuzzy data and fuzzy constraint, spanning tree problems with fuzzy random edge costs, knapsack problem with fuzzy and random coefficients and facility location problem with fuzzy distance and fuzzy goal. In order to find the difference between the solution of ordinary problem and that of fuzzy random version, we introduced fuzzy random variables to above problems of combinatorial optimization and proposed efficient algorithms for solving their deterministic equivalent problems. We obtained some results on solutions of these problems. Further we investigated also basic mathematical analysis of value of information by considering functional analysis, especially variational inequality and introduced a new concept of fuzzy derivatives to apply optimization under ambiguity.

本研究旨在探讨信息对组合优化的价值。本研究的目的是阐明随机因素和模糊因素在组合优化模型中的作用。特别是，根据不确定性和/或模糊性的存在而改变解。首先，我们考虑了随机因素和模糊因素下的线性规划问题。在这些模糊随机线性规划问题的基础上，我们考虑了具有模糊数据和模糊约束的调度问题、具有模糊随机边成本的生成树问题、具有模糊随机系数的背包问题和具有模糊距离和模糊目标的设施选址问题。为了找出普通问题的解与模糊随机问题解的不同之处，我们将模糊随机变量引入到上述组合优化问题中，并提出了求解其确定性等价问题的有效算法。我们在这些问题的解上得到了一些结果。此外，我们还利用泛函分析，特别是变分不等式，研究了信息价值的基本数学分析，并引入了模糊导数的新概念，以应用于模糊优化。

项目成果

Hideki Katagiri: "Chance Constrained Bottleneck Spanning Tree Problem with Fuzzy Random Edge costs"Journal of the Operations Research Society of Japan. Vol.43,no.1. 128-137 (2000)

Hideki Katagiri：“具有模糊随机边缘成本的机会约束瓶颈生成树问题”日本运筹学会杂志。

小出武,新森修一,石井博昭: "直並列グラフによるネットワーク信頼度の下界" 応用数理学会誌. (掲載予定).

Takeshi Koide、Shuichi Shinmori、Hiroaki Ishii：“使用串并联图的网络可靠性下限”日本应用数学学会杂志（待出版）。

Kyo-Won Lee: "Fuzzy Scheduling Problem on a Multiprocessor System with Memories"Mathematica Japonica. 49,1. 139-144 (1999)

Kyo-Won Lee：“带有存储器的多处理器系统上的模糊调度问题”Mathematica Japonica。

Shintaro Mohri, Hiroaki Ishii and Teruo Masuda: "Bi-criteria MPM Open Shop Scheduling Problem"Mathematica Japonica. Vol.49 no.3. 411-415 (1999)

Shintaro Mohri、Hiroaki Ishii 和 Teruo Masuda：“Bi-criteria MPM Open Shop Scheduling Problem”Mathematica Japonica。

Tutomu Konno and Hiroaki Ishii: "An Open Shop Scheduling Problem with Fuzzy Allowable Time and Fuzzy Resource Constraint"Fuzzy Sets and Systems. Vol.109, no.1. 141-147 (2000)

Tutomu Konno 和 Hiroaki Ishii：“具有模糊允许时间和模糊资源约束的开放车间调度问题”模糊集和系统。