The Maximum Weighted Matching Models in Uncertain Environment

摘要：

　　A matching in an undirected graph is a sub set of edges set such that no pair of edges in it have common endpoint.With respect to a weighted graph, the maximum weighted matching problem is to find a matching for which the weight of the matching is as large as possible.This paper employs uncertainty the ory to deal with maximum weighted matching problem in uncertain environment in which the weights are un certain variables.According to various decision criteria, the concepts of expected maximum weighted matching and α-maximum weighted matching are proposed.Af ter that, expected value model and chance-constrained programming model are constructed.Taking advantage of properties of uncertainty theory, the models can be turned into their deterministic forms.Finally, a numer ical example is given.

关键词： Matching Expected maximum weighted matching α-maximum weighted matching Uncertainty theory Uncertain variable

作者: Bo Zhang Jin Peng

作者单位: School of Mathematics and Statistics,Huazhong Normal University,Hubei 430079,China Institute of Uncertain Systems,Huanggang Normal University,Hubei 438000,China

会议类型: 国内会议

会议名称: 第十一届中国不确定系统年会、第十五届中国青年信息与管理学者大会

会议地点: 河北邯郸

会议语种:英文

页码: 7-16

在线出版日期: 2013-07-27（万方平台首次上网日期，不代表论文的发表时间）