Variants of the Simplex Method
Besides the simplex method and dual simplex method, a number of their variants have been proposed in the past. To take advantages of both types, attempts were made to combine them. At first, two important variants will be presented in the following two se
- PDF / 388,805 Bytes
- 35 Pages / 439.36 x 666.15 pts Page_size
- 92 Downloads / 207 Views
Variants of the Simplex Method
Besides the simplex method and dual simplex method, a number of their variants have been proposed in the past. To take advantages of both types, attempts were made to combine them. At first, two important variants will be presented in the following two sections respectively, both of which prefixed by “primal-dual” because they execute primal as well as dual simplex steps, though they are based on different ideas. More recent variants of such type will be presented later in Chap. 18. In the other sections, the primal and dual simplex methods are generalized to handle bounded-variable LP problems, which are commonly used in practice.
7.1 Primal-Dual Simplex Method The primal-dual method (Dantzig et al. 1956) will be presented in this section, which is an extension of the same named method (Ford and Fulkerson 1956) for solving transportation problems. Just like the dual simplex method, this method proceeds toward primal feasibility while maintaining dual feasibility and complementarity. However, they pursue primal feasibility in different ways. The former attempts to fulfil x 0 while maintaining Ax D b, whereas the latter attempts to get rid of artificial variables in the auxiliary Phase-I program to fulfil Ax D b while keeping x 0. We are concerned with the standard LP problem (1.8), whose dual problem is (4.2). Let .y; N zN/ be the current dual feasible solution, satisfying AT yN C zN c. To obtain a primal solution matching .y; N zN/, consider the auxiliary program (3.16), written as min s:t:
D e T xa ; Ax C xa D b;
x; xa 0;
P.-Q. PAN, Linear Programming Computation, DOI 10.1007/978-3-642-40754-3__7, © Springer-Verlag Berlin Heidelberg 2014
(7.1)
169
170
7 Variants of the Simplex Method
where xa D .xnC1 ; : : : ; xnCm /T is an artificial variable vector. It would be well to assume b 0. Introducing index set Q D fj 2 A j zNj D 0g;
(7.2)
define the so-called “restricted program”: min D e T xa ; xa 0; s:t: Ax C xa D b; j 2 Q; xj 0; xj D 0; j 62 Q:
(7.3)
Since b 0, it is clear that the feasible region of the preceding program is nonempty, and hence there is an optimal solution to it. The restricted program may be viewed as one formed by all artificial columns and columns indexed by j belonging to Q. N and that Assume that .x; N xN a / is an optimal solution to (7.3) with optimal value , wN is the associated optimal simplex multiplier. Theorem 7.1.1. If the optimal value N vanishes, xN and .y; N zN/ are a pair of primal and dual optimal solutions. Proof. N D e T xN a D 0 and xN a 0 together imply that xN a D 0. Thus, xN is a feasible solution to the original problem (4.1). By the definition of Q, moreover, it holds that xN T zN D 0, as exhibits complementarity. Therefore, xN and .y; N zN/ are a pair of primal and dual optimal solutions. t u When N > 0, otherwise, xN could be regarded as the closest one to feasibility among all those complementary with .y; N zN/. Nevertheless, the xN is not feasible to the original problem because it does not satisfy
Data Loading...
