Research On Model And Algorithm About Uncertanin Optimization Problems

Today we are facing an information time and the information is knowledge headspring from which people know and rebuild world. All kinds of information may be certain but more is uncertain. It induces the research about scientific decision-making system that how to judge , analysis and deal with information. The background involved by this system shows uncertain of multi-dimension, which is different such is randomness, fuzziness, roughness, intervalness, etc. The classical methods is not capable to the multi-dimension uncertain system, although some stochastic or fuzzy programming can deal some optimization problems, which is far from the goal of solving optimization problems about multi-dimension uncertain system. So it has significate application foreground to establish and consummate optimization theory with method in uncertain environment. The systemic optimization method in uncertain environment comes into being under the background above. As the bridge contacting uncertain theory and application, uncertain programming affords the way of modeling to decision-making problems. The main characteristic of uncertain problems is the method colligation and large-scale. The basic algorithm is mixed intelligence algorithm, which combines the genetic algorithm, algorithm simulation and neural network, basing on the mathematic frame character, or using existing programming algorithm to solve large-scale problems.The main work of this article is: discussing the basic models of stochastic programming and the relations between them; researching the character and algorithm about integrated chance constraints model (ICC(β)) and two-stage model with recourse(2S-SP); studying interval optimization and rough optimization combined with location problem and reduction problems.In the first chapter, we review the background, class of uncertain programs and the existing work. Subsequently in § 1.2 the basic models of stochastic programming are induced according to the modeling mechanism and the relations between them are consummated, which is given as:When making decision after the relation of random variable, distributing problem is produced; otherwise the state can be partition as:Firstly, assuming random variable is involved only in constrains set, there are: (a) Chance Constrains model; (b) Publishing model; (c) Recourse model.Secondly, assuming random variable is involved only in goal function, there are: (d)E-model; (e)Variance model;(f)Minimize the probability of bankruptcy model; (h)Minimize the supreme bound model; (g)Maximize the expected utility model.Proposition 13.1 2S-SP modek Chance Constrains modek E-modek P-model and Utility model have the unified form as following:minXs.t. ,(,￡)U ,,Proposition 133 [44] Publishing model is a special Recourse model.Proposition 13.4 Utility model is the extending of E-model and P-model.Propositions above show that stochastic programming is relevant to certain programming, but the equivalence of certain state often has complex form. They can be translated only in some special case and examples can be seen Proposition 13.2.As a basic stochastic model, chance constrains model has two difficult. One is that it only paid attention to the probability of feasibility from the qualitative, not referring the quantity such as recourse model. The other is about the math character that the solution set is convex only when the random variables satisfy some fine conditions. The examples in [8,44] show the convex is not kept yet, while which is important to solving the problem. So for the sake of disadvantage, some investigator proposed integrated chance constraints model in 1970 [38]. But the relevant research is little and only [44,45] are consulted, the reason of which may be the complexity of computing. On the other hand, this model has very good character and is important to the risk research, economy decision control. So we give emphases to it in chapter2.Some kinds of definition expand of integrated chance constraints model are given in §2.1.Definition 2.13 considers the surplus and shortage together. Definition the resource surplus is: rj*(x,q>) = msa.{0,Tfi}, then the average surplus￡7* satisfy ￡7; + Erj* = E\rjt | .The individual integrated chance constraints is: Etj~ < a,E\rj,\, i = \,2,--,m, and the joint integrated chance constraints is: E{tj~ ,i = \-m)￡a. This definition overcomes the difficulty of taking value for/?,. In definition 2.1.4 [7], ^e[0,?) is introduced to represent the maximum accept value of conditionexpectation E[(tj~ )\tj < 0] , defining Etj~ < y ■ P(tj,:< 0) and solution set is X* (/) := {x e R", Erft <, y ? E\Tjt |}. It's rationality is given in this article.Subsequently the character of this model is discussed in § 2.2, which including the convexity of solution set, continuum and differentiability of restriction function under the precondition that restriction function is convex about variable. As the expanding of linear condition in [44], the main result is:Theorem 2.23 For stochastic programming: min{/(x): g(x,a)) > 0,x € D}, D is a fixed, closed, finite set,g(x,o)is convex about xand each random variable satisfying E(a)j )<, then:g(x) = E[g(x,a>)~] is finite> nonnegative, convex and Lipschits continuous. For finite discrete distribution of (a(o)),b(o))), g(x) is piecewisely convex function, and for continuous distribution of (a(fl>),6(o)), g(x) is continuous and differentiable . SoX(0) = {x e R": g(x) < P) is convex set. For g(x,a>) = ￡a, (,x,,*2((been known. This case will bring more uncertain element for decision maker so we introduce interval variable to describe the location problem. Interval programming is introduced firstly, then some interval programming about location are established which includes: optimize model, pessimism model, expectation model, uncertain degree model, losing model, robust model and multi-objective programming.The other problem is about the reduction in decision table based on rough set. Due to its practical use in knowledge discovery and data mining, reduction is becoming more important aspect of computer science. Now there are some attribute reduction methods [86-91]: such as based on distinguish matrix in algebra view and using entropy in information view. At the same time, for it's character of NP-Hard, people often introduce suggesting intelligent algorithm as genetic algorithm and parallel cooperating algorithm in large-scale problem. Based on the relationship between attribute reduction and logic operations, an integer programming algorithm 4.2 to finding minimal size reduction is proposed in § 4.2, which can avoid complicated logic operations, and becomes more effectively in dynamic environment. The experiments analysis is given to show the efficiency of algorithms in chapter 4.The innovate viewpoints of this dissertation are as follows:1. We coordinate the basic models of stochastic programming and perfect the definition of optimal value and solution in random model. What's more, the relations between them are discussed and the equivalence forms are reinforced.2. In integrated chance constraints model, the character of subjective linear function is expanded to that of convex function. We get good character which including the convexity of solution set, continuum and differentiability of restriction function and design two algorithms to computer problems with discrete or continues variable.3. By applying bilever programming to study the two-stage model with recourse, we find that 2S-SP is equal formally to bilever programming and give the existing condition of optimal solution in 2S-SI^ 2S-SNLP. At the same time we research the dual theory of 2S-SP and propose the dual problem, which covers the dual expressing of LP and BP. It is the innovation about theory and method.4. Basing on interval programming and rough optimization, we propose effective algorithms to solve two important problems: location and reduction. It is the innovation about application and method.