Mathematical Programming Model Of Uncertainty Coverage Problem

Covering problem is not only one of classical network optimization problems, but also have many applications in real life decision making. In the applications, the weight may denote cost,time, etc., which are usually uncertainty in practice. In this dissertation, we use the uncertainty theory, which is a new branch of axiomatic mathematics, to study the uncertain covering problem.Covering problem usually including the vertex covering problem and the edge covering problem.This dissertation mainly investigates the uncertain vertex covering problem and the uncertain edge covering problem by using the uncertainty theory.In uncertain vertex covering problem aspect, it firstly puts forward the concept of minimum weight function of vertex cover, and it gives the uncertainty distribution of the minimum weight function of vertex cover. Secondly, it constructs the expected value model by minimizing the sum weight of all vertices, and establishes a belief degree-constrained programming model when the sum weight of all vertices should not more than the predetermined weight with the confidence level. Finally, it investigates the crisp equivalent forms of the proposed models and it gives a numerical example by using the operational law of uncertain variables.In uncertain edge covering problem aspect, we establish the expected value model by minimizing the sum weight of all edges, and construct a belief degree-constrained programming model when the sum weight of all edges should not exceed the predetermined weight with the confidence level within the framework of uncertain network optimization. And then, we use the operational law of uncertain variables to discuss the crisp equivalence of the proposed models. At last, we give some numerical examples to illustrate the application of the proposed models.The contributions of this dissertation includes:1. It puts forward the concept of minimum weight function of vertex cover, and gives the uncertainty distribution of the minimum weight function of vertex cover when we assume the vertex weights are all uncertain variables.2. It constructs the expected value model and the belief degree-constrained programming model for the uncertain vertex covering problem and the uncertain edge covering problem, respectively. It enriches the content of the uncertain network optimization.3. It investigates the crisp equivalence and discusses some properties of the proposed models based on the operational law of uncertain variables, and it also gives some numerical examples to illustrate the application of the proposed models.