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 areconsummated, 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.Propositionl.3.1 2S-SP modeh Chance Constrains modeh E- modeh P-model and Utility model have the unified form as following:min EF{x,￡,)xs.t.Proposition 1.3.3[44] Publishing model is a special Recourse model.Proposition 1.3.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 1.3.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 o So for the sake of disadvantage, some investigator proposed integrated chance constraints model in 1970 [38] o 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.1.3 considers the surplus and shortage together. Definition the resource surplus is: rj*(x,a>) = max{0,77,} . then the average surplus Erj* satisfyE?]~ + Etj* = E\rjt\ .The individual integrated chance constraints is: Erj~ < a,E\ril\, i = 1,2,? ? ? ,m , and the joint integrated chance constraints is: E(ji~,/ = 1 ? ? ? 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 condition expectation E[(tj~)\tj <0] , defining Etj~ < y ■ P{r]l < 0) and solution setisX4 (y) := {x e R", Et]~ < y ■ E\rj,|}. 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.2.3 For stochastic programming: min{/(x) :g(x,co) > 0,x e D}, D is a fixed, closed, finite set, g(x,co) is convex about xand each random variable satisfying E(o)j) < °o, then:g(x) = E[g(x,6))~] is finite> nonnegative, convex and Lipschits continuous. For finite discrete distribution of (a(co),b(co)), g(x)is piecewisely convex function, and for continuous distribution of (a(co),b(co)), g(x) is continuous and differentiable . So X(/3) = {x € R" : g(x) < (5) is convex set. For g{x,co) - ^]a;(cy)xy2 -b(co), there isdxJlim= E\-2a1xj sgn(g(x)~)], moreover,The theorem above is basing for algorithm later, then theorem 2.2.5 gives the Lagrange problem of this model, indicating that L(X) is equivalent to(simple) recourse or publishing model.? In research about risk finance[45,47], the equivalence is gotten by translating the evaluating way of risk value, which is consistent with that of our work. When the recourse coefficient is hard to determinate, (ICC( J3)) can describe the word more accurately and offer a new method for computing.In § 2.3, § 2.4, assuming the random variables obey finite discrete or continuous distribution respectively we have designed the algorithms. The hybrid intelligent algorithm 2.3 is given, based on the structure character of solution set (theorem2.3.1,theorem 2.3.2) and comparing example about random problem shows the validity of algorithm 2.3. The algorithm 2.4 is given with complexity of O(n3L), based on the character of problem and interior algorithm with decomposing.In chapter3 the two-stage model with recourse (2S-SP) is researched. In § 3.1, by contrasting the modeling idea, we get the conclusion that (2S-SP) is equal formally to bilever programming. Proposition 3.1.1 and 3.1.2 show: 2S-SP is a class of random bilever programming, moreover random value-type bilever programming with one sub-system in the low-lever. As an NP-Hard problem, research work about (2S-SP) mainly focuses on the computing and realization of solution. However, bilever programming has gotten detailed development on theory, optimization method and algorithm. So propositions above make out that we can study (2S-SP) using for reference. Theorem 3.1.4, theorem 3.1.5 discuss the existing condition of optimal solution in 2S-SIi\ 2S-SNLP.Then we consider the dual theory of 2S-SP in § 3.2. For complexity and variety, the dual theory of stochastic programming is only a small quantity of, in some references just as [44,99] discussed the dual using certain programming after translating stochastic programming into determined form, also did in [70] to designing aggregation method for large-scale random problem by using the dual of determined equivalence form.Considering 2S-SP such as (3.2.1), which has convex functions. Basing onperturb theory, the dual problem is got as follows:sup D = sup inf L(x, v).y y xWhere,L(x,y) = inf{uIy + F(x,u)} = Ll(x,y) + f I2(a>,x,,x2{co))p{dco).ueU Jo 'Especially when all functions are linear about x, the dual programming of 2S-SLP which has the form (3.2.4) is:maxvb+ \K{(o)H{co)p{dco)v,/r( 0 s.t.'C2(co)-7r(o))W(co)>0 (3.2.5)V,7T(CO)>0We can see at once that if delete the random functions in primal problem (3.2.4)and dual problem (3.2.5) then we can get traditional primal-dual form about certain problem. What's more, the conclusion above is consistent with that in [74]. (3.2.5) extends the dual of linear programming to 2S-SLP , which not only consummates the theory but also bring new idea for computing this model.In the view of application, other two uncertain optimization problems are studied in chapter 4. One is location problem in uncertain environment studied in § 4.1. By now it only have appeared in little references such as applying fuzzy judge and considering the random demand. But the former has the different subjection function by different experts and the latter often suppose distribution function has 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-value model> losing model-, robust model and multi-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 avcrid 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 anddesign two algorithms to computer random 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-SLP, 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.