《一种求解阶梯状结构线性规划问题的原始对偶分解算法》由会员分享，可在线阅读，更多相关《一种求解阶梯状结构线性规划问题的原始对偶分解算法（30页珍藏版）》请在金锄头文库上搜索。
1、河北工业大学 硕士学位论文 一种求解阶梯状结构线性规划问题的原始-对偶分解算法 姓名：高俊玉 申请学位级别：硕士 专业：计算数学 指导教师：刘新为 20070601 ? ? ? ? ? ? ?-? ? ? ? ? lib.org? ? ? ? ?D-W?Benders? ? i ? A Primal-Dual Decomposition Method For Staircase Linear Programming Problems ABSTRACT The staircase linear programs as a class of linear programming prob- lem
2、s with special structure, have important practical backgrand. We fi rst review the development of decomposition algorithms, and then consider a primal-dual decomposition method for such staircase linear programs. The algorithm splits the problem into a sequence of sub-problems. They are co-ordinated
3、 by primal and dual information passing forward and back- ward. To fi nd the optimal solution, the algorithm approaches the primary problem in primal and dual direction, depending on the convex combina- tion of vertices. The test examples are taken from the famous optimization website lib.org and so
4、me changes have been done for our method. Although the sizes of the problems are not so large, the numerical results may still be helpful for us to understand the method. KEY WORDS:D-W decomposition, Benders decomposition, nested decomposition method, cross decomposition, primal-dual decomposition i
5、i ? ? 1-1? ? ? ?29? 30? ? ? ? ? ? Ho?Loute13? ? ?Dantzig?Wolfe7?D-W?Benders4 ?14? D-W?Benders? ? ?Dantzig8 (1963), Cobb?Cord6 (1970), Ament1?(1981)?Dantzig9 (1980), Wittrock24 (1984)?Beale3 (1963), Kornai-Liptak18 (1965), Aonuma2 (1981)?Benders? Geoff rion11 (1972), Wolsey25 (1981)?Benders?Van Roy23
6、 (1983) ?Holmberg16 (1990)?D-W? Benders?Holmberg15 (1990,1991),? ? ?kortanek, Huang5(1993)?-? ?26,27? ?Berkelaar,Zhang5 (2002) ,Kojima, Megiddo, Mizuno17 (1993)?Lustig21 (1990), Mehrotra22 (1992), Liu, Sun 19 (2004), 20 (2006)?-? ? ?Dirickx10 (1979) ?Ho12 (1987)? ? 1 ? ? ? 1-2? ? ? ? ? ? 2 ? ? ?D-W?
7、Benders? ? 2-1D-W? ? minc1x1+ . + clxl s.t. A1x1+ . + Alxl=b D1x1r1(2.1.1) . Dlxlrl x1 0,xl 0 ?c1,cl;x1,xl?b,r1,rl?A1,Al?D1,Dl? ? ?l? ? ?LP? ? ? min cx s.t. Ax=b(2.1.2) x X ?c = (c1,cl),x = (xT 1,xTl )T,A = (A1,Al),? X = (xT 1,x T l )T| Dixi ri,xi 0,i = 1,l = X1 X2 Xl ? Xi= xi| Dixi ri,xi 0 3 ? ?X?X
8、i? ?X?y1,yt,?X? ? X = l X j=i jyj| l X j=i j= 1,j 0,j = 1,t. ?X?2.1.2?1,t? ? min l X j=i (cyj)j s.t. l X j=i (Ayj)j= b(2.1.3) l X j=i j= 1 j 0,j = 1,2,t ? ? max (A c)x + ?D-W? ? ? ? 2-2Benders? Benders? ? mincx + f(y) s.t. Ax + F(y) = b(2.2.1) x 0 y Y 4 ? ?c,x Rm,y Rl, A?m n?Y?Rl?f(y) : Y Rl? ?F(y)
9、: Y Rm? ? min yY f(y) + min Ax = b F(y) x 0 cx ? (Py)mincx s.t. Ax = b F(y) x 0 ?x?LP?y? (Dy)maxw(b F(y) s.t. wA c ? min yY f(y) + max wAc w(b F(y)(2.2.2) ? ?1(b x, b y)?(2.2.1)?b y?b w?(2.2.2)? ?b x?(Pb y)? ?2?y Y?(Dy)?(2.2.1)? ? ?(Dy)?(2.2.2)? minz s.t. z f(y) + w(b F(y)w W(2.2.3) y Y ?W?w1,wt?d1,dt
