【作者】 邓键；

【导师】 易英飞； 李勇；

【作者基本信息】 吉林大学 ， 应用数学， 2009， 博士

【摘要】 本文主要研究双层规划若干问题的解法.全文共分四章,第一章是绪论,从第二章到第四章为论文主体部分.在第二章,我们主要提出了边界搜索法、改进的边界搜索法、改进的K最好方法、内点法这几个解线性双层规划问题的新算法.其中边界搜索法、改进的边界搜索法以及改进的K最好方法都是让迭代点在约束域边界进行迭代,而内点法是根据内点思想让迭代点在可行域内部进行迭代.在第三章,我们进一步考虑了几种特殊类型的双层规划问题,包括:多跟随者的双层规划问题,线性分数型的双层规划问题.这两类双层规划问题都是在实际问题中根据一般的双层规划问题演变而来的,有很强的应用价值.对于这两类问题我们也给出了他们的求解算法,这些算法都是基于第二章中介绍的方法而进行的改进.在第四章中,我们讨论了关于双层规划的一些其它问题.一个是无解的双层规划问题.根据在实际问题中的需要,我们针对无解的双层规划问题提出了一种新的定义的解,并给出了求解的算法.另一个是关于极大极小值问题与双层规划之间关系的问题.将极大极小值问题转化为一类特殊的双层规划问题,并用解双层规划问题的方法来求解极大极小值问题.在本章最后我们还提出了作者以后关于双层规划问题的研究方向.更多还原

【Abstract】 Bilevel programming problem is an important optimization problem in operational research. It can be applied in economy, engineering, management and military affairs which has an hierachical structure system. Von Stackelberg published a monograph[44] about game theory in unbalanced economic markets in 1934. In this monograph he built Von Stackelberg competition model named by his name first （also called double oligarch model）. Von Stackelberg competition model describes two big competitor in finance. When one person makes a decision, he should considers both optimize his objective function and the other person’s reflection. So he should changes his decision. Von Stackelberg competition model is a special model of bilevel programming problem. Because in World WarⅡNazification Germany implemented anti-competitive economic policy, it can not attract people’s attention. After World WarⅡ,Von Stackelberg competition model caught the attention of researchers in game theory. In the mid-1970s, bilevel programming problem was introduced into optimization and made a rapid development. In recent years, bilevel programming problem attracts researchers’ attention in many region （applied mathe-matic,operational research, management science, decision-making science, system science and economics）, because of its comprehensive application. Bilevel programming problem is an optimization problem whose constraint is another optimization problem. It can be showed in the following form:where x∈X （?） Rⁿ,y∈Y （?） R^m,F,f:X×Y→R¹,G:X×Y→R^p,g:X×Y→R^q.In this paper we consider the algorithms of some bilevel programming problem, and mainly obtain the following results:1,We present boundary search method for solving linear bilevel programming problem.Firstly, we solve the following problem （2）by the following boundary search method: Step 1 Let i←1.Using the simplex method, we can obtain the optimal solution x₁=（x₁¹,x₁²,…,x₁ⁿ）^T from problem （2.1.3）.Go to step 2.Step 2 Let current iterative point be x₂=（x₂¹,x₂²,…,x₂ⁿ）^T.Using the simplex method, we can obtain the optimal solution x’₂ of problem （1.2.3）. If x₂=x’₂,x₂ is the solution of problem （2）. Otherwise, go to step 3.Step 3 Let current iterative point be x₃=（x₃¹,x₃²,…,x₃ⁿ）^T.Assume x₃ satisfy p constraint conditions, and let they are first p. Let d = （d₁,d₂,…,d_n）^T be search direction. Choose min{p,n-1} constraint conditions from p constraint conditions arbitrarily, then d is the solution of the following equations:the step length of search direction is: For the point x₃,search direction d and the step length t,x₃+td is a adjacent extreme point of x₃.We can obtain other extreme points of x₃ like this. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region.If not exist, choose the point which minimize the upper-level objective function as new iterative point, go to step 4. Otherwise, choose the point which maximize the upper-level objective function as new iterative point, go to step 5.Step 4 Let current iterative point be x₄={x₄¹,x₄²,x₄ⁿ)^T.Choose n-1 constraint conditions from p constraint conditions arbitrarily that x₄ satisfy:and let them take "=". From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x₄ is still iterative point, go to step 3.Step 5 Let current iterative point be x₅=（x₅¹,x₅²,?x₅ⁿ）^T.Choose n-1 constraint conditions from p constraint conditions arbitrarily that x₅ satisfy: and let them take "=".From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x₅ is the optimal solution of problem （2）.Then choose the optimal solution of problem （2） as initial iterative point to solve the linear bilevel programming problem （3）:Boundary search method for solving linear bilevel programming problemis presented in the following:Step 1 Let F =+∞is upper-level objective funciton value, T=（?） is the set of iterative points that we have known, W=（?） is the set of feasible extreme points. By the method in [27] and [28], we can obtiain the solution x₁ of problem （2）. Check x\ whether satisfy upper-level constraint conditions. If satisfy, then the solution x₁ of problem （2） is also the problem （3）’s solution. If not satisfy, choose x₁ as iterative point, update T = T∪{x₁},W=（?）,F=c²x₁,go to step 2.Step 2 Let x₂ ={x₂¹,x₂²,…,x₂ⁿ)^T is current iterative point. The search direction isAssume x₂ satisfy p constraint conditions, and let they are first p. Choose min{p,n-1} constraint conditions from p constraint conditions arbitrarily, and consider the following problem:We can obtain the search direction d. Because the choosen are different,we can obtain q search directions and denote asTakeinto all the constraint conditions to solve the step length max{t} respectively.So we can obtain q adjacent extreme points of x₂.If there exists a point both satisfy the lower-level optimality condition and in the feasible region, go to step 3. Otherwise, T = T∪{x₂},F=c²x₂,W=（W∪W’）\T, （W’ is the set of x₂’s adjacent extreme points which satisfy lower-level optimality condition）. Choose the point which maximize the upper-level objective function from W as new iterative point, go to step 2.Step 3 Let x₃ = （x₃¹,x₃²,?x₃ⁿ）^T is current iterative point. Denote the points which both satisfy the lower-level optimality condition and in the upper-level constraint conditions in step 2 as x_j’（j’ =1,2,?p’）,the corresponding search direction are d_j’.UpdateTake x’_j’=x_j’-d_j’t （t≥0） into all the constraint conditions to solve the step length max{t} respectively. So we can obtain x’_j’（j’=1,2,…,p’）. Then solve the following problem:Let （?） is the solution of problem （4）.If c²（?）>F,update F=c²（?）.Otherwise,not change F. Choose the point which maximize the upper-level objective function from W and denote as x’.If F > c²x’,then x^* which is corresponding to F is the solution of problem （3）.Otherwise, choose x’ as iterative point, go to step 2.2,We present Kth-best approach for solving linear bilevel programming problem which is in the following:Step 1 Let x₀=（x₀¹,x₀²,…,x₀ⁿ）^T be a feasible point arbitrarily.Step 2 Fix (x₀^s+1,…,x₀ⁿ) in the lower-level problem, then the problem is transformed to: Using the simplex method, we obtain the solution of the problemwhereand make it is new iterative point. For x₁ and optimal search direction c²=(c²¹,c²²,?c²ⁿ),we should guarantee that the new iterative point is in the feasible region, namely:If t≠0, we can obtain a new iterative point （x₁ + （c²）^Tt）,update x₀ = （x₁ + （c²）^Tt）,repeat step 2. Otherwise, go to step 3.Step 3 Let current iterative point beAssume x₂ makes i constraint conditions take "=",let they are first i constraint conditions. Then: （i） If i≤n-1,d^* is the solution of the following problem:We can obtain the suboptimal search direction d^*,go to step 4.（ii） If i≥n,we solve the following problem:where constraint conditions are n-1 constraint conditions from i constraint conditions arbitrarily. So we can obtain p solution, denote as d_j （j = 1,2,…,p）.Go to step 5.Step 4 For the current iterative point and suboptimal search directionwe should guarantee that the new iterative point is in the feasible region, namely:We can obtain a new iterative point x₃=（x²+（d^*）^Tt）.Take (x₃^s+1,?x₃ⁿ) into lower-level problem, it is transformed to: Using the simplex method, we can obtain a new iterative point, denote aswhereGo to step 3.Step 5 Let the current iterative point be x₅ = （x₅¹,x₅²,?x₅ⁿ）^T.d_j（j = 1,2,…,p） is the suboptimal search direction. Takeinto the lower-level constraint conditions to solve the step length max{t} respectively. If there exist t > 0 such that the new iterative point satisfy lower-level optimality condition, then choose the point which maximize the upper-level objective function as new iterative point, go to step 3. Otherwise,x₅ is still iterative point, go to step 6.Step 6 Let the current iterative point be x₆ = （x₆¹,x₆²,…,x₆ⁿ）^T.Choose n-1 constraint conditions from m constraint conditions arbitrarily that x₆ satisfy: and let them take "=".From these n-1 equations and the new added constraintwe can obtain some new boundary points. Check whether there exists a point both satisfy the lower-level optimality condition and in the feasible region. If exist, choose it as new iterative point, go to step 3. Otherwise, x₆ is the optimal solution of problem （3）.3,We present interior point method for solving linear bilevel programming problem which is in the following:Step 1 Let x₁ be initial iterative point which is in feasible region. Let the upper and lower boundary of iterative direction is d_u=c²,d_ι=c¹.Choose d₁=d_u=c² as initial iterative direction. Take x₁ + d₁t into constraint conditions and obtain step length t and x’₁ =x₁+ d₁t.If x’₁ satisfy lower-level optimality condition, then use boundary search method or extend Kth-best approach. If x’₁ do not satisfy lower-level optimality condition, go to step 2.Step 2 Let the current iterative point be x₂,update iterative direction d₂=（?）（d_u+d_ι）.Take x₂+d₂t into constraint conditions and obtain step length t and x’₂=x₂+d₂t.If x’₂ do not satisfy lower-level optimality condition, iterative point do not change, update d_u=d₂,d_ι=d_ι.Repeat step 2. If x’₂ satisfy lower-level optimality condition, the new iterative point is x₃ = x₂ + （?）d₂t,update d_u= d_u,d_ι= d₂.If step length t >ε（εis prior fixed）, repeat step 2. Otherwise, go to step 3. Step 3 Let the current iterative point be x₃.Add a new plane c²x= c²x₃.Choose n-1 constraint conditions arbitrarily from the constraint conditions that x₃ satisfy. Prom these n-1 equations and the new plane, we can obtain some new boundary points. Check whether there exists a point satisfy the lower-level optimality condition. If there do not exist,x₃ is the optimal solution of the problem （3）. If there exist, choose one and denote as x’₃,update d_u= d_u,d_ι=x’₃-x₃,and x₃ is still iterative point. Go to step 2.4,We also consider the following two problem, such as, multi-followers bilevel programming problem, fractional bilevel programming problems. These two problem are all derived from normal bilevel programming problem in practical problem and have important application.We give the method for solving these two problem which are based on the method above.5,We give a new definition of the optimal solution for no solution bilevel programming problem.Definition 6.0.1 We call the optimal solution of problem （5） is the feasible optimal solution of problem （1）. where u_max and u_min are objective function value of problem （6） and （7）.6, We transform max-min problems to a special type bilevel programming problem and give the following theorem:Theorem 6.0.1 max-min problem （8）is equivalent to the bilevel programming problem （9） And we also solve max-min problems via solving this bilevel programming problem.更多还原