Transcript
MODIFICA MODIFICATION TION OF SIMPLEX SIMPLEX METHOD METHOD AND ITS IMPLEMEN IMPLEMENT TATION IN VISUAL VISUAL BASIC BASIC
´, Predrag S. Nebojˇ sa sa V. Stojkovic, c ´ and Marko D. Petkovi c ´ Stanimirovic
We investigate the problem of finding the first basic solution in the simplex algorithm. algorithm. A modification modification of two two phases simplex simplex method is presented and its implementation in programming language Visual Basic is described. A few Netlib examples are presented. Key words: words: Linear programming, simplex method, Visual Basic .
Abstract.
1. Introduc Introduction tion
Consider the linear program n
c x −d Maximize f ( f (x) = f ( f (x , . . . , x ) = a x ≤ b (i = 1, . . . , p)p) subject to N | a x ≥ b (i = p + 1,1, . . . , q) N | a x = b (i = q + J | q + 1, 1, . . . , m) m) 1
n
i i
i=1
n
(1) i
(1.1)
ij N,j
i
ij N,j
i
j =1 n
(2) i
j =1
n
i
ij N,j
i
j =1
x i ≥ 0,
(i = 1, . . . , m) m).
1991 Mathematics Subject Classification . 90C05. 90C05. Typeset by
1
AMS -T -TEX
2
Nebojˇsa V. Stojkovi´ c, Predrag S. Stanimirovi´c and Marko D. Petkovi´ c
We can transform constraints (1.1) in the following way. Every inequality of the form N i(1) we change with the equality n
(1) N i |
a x
ij N,j
− bi = xB,i
(i = 1, . . . , p),
j =1
and every inequality of the form N i(2) we change with the equality n
N i(2) |
a x
ij N,j
− bi = xB,i
(i = p + 1, . . . , q ) .
j =1
In a such way we get the linear program Max c1 x1 + · · · + cn xn − d Ax = b,
(1.2)
b = (b1 , . . . , bm ),
xi ≥ 0, (i = 1, . . . , n + q ), where the matrix A is in Rm×(n+q) . We suppose that the system is of full rank ( rank(A) = m). After the substitution n + q − m = n, the canonical form of problem (1.2) is written in the following tableau form [1], [6]
(1.3)
xN,1 xN, 2 . . . a11 a12 . . . a21 a22 . . . ... ... ... am1 am2 . . . c1
c2
...
xN,n 1 a1n = b1 a2n = b2 ... ... amn = bm cn
d
= xB, 1 = xB, 2 ... = xB,m = f
where xN,1 , . . . , xN,n is the set of nonbasic variables and xB, 1 , . . . , xB,m are basic variables. Transformed coefficients of the matrix A and the vector c are denoted by aij and cj , respectively, for the sake of simplicity. The paper is organized as follows. In the second section we introduce the modification of two phases simplex method and investigate the problem of finding the first basic solution in the simplex algorithm. In order to accelerate the process for generating the first basic feasible solution we investigate two problems: - the problem of the first choice of basic and nonbasic variables, and - the problem of the replacement of a basic and a nonbasic variable in the general simplex method. In the third section we describe an implementation of the two phases simplex method and its modification in the programming language Visual Basic . Several numerical examples are reported in the last section.
Modification of simplex method and its implementation in visual basic
3
2. Modification
For the sake of completeness we restate one version of the classical two phases maximization algorithms from [3] and [7] with respect to linear problem (1.1), which is presented in the tableau form (1.3). Algorithm 1. Replacing a basis variable xB,p and nonbasis variable xN,j . 1 , a pj a pl b p = = j, b p1 = , l , a pj a pj aqi =− , q = p, a pj a pl aqj = aql − , q = p, l = j, a pj cj a pl = cl − , l = j, a pj cj =− , a pj b p cj =d− . a pj
1 a pj = 1 a pl
a1ql a1ql c1l c1j d1
Algorithm 2. (Simplex method for basic feasible solution). Step S1A. If c1 , . . . , cn ≤ 0, then the basic solution is an optimal solution. Step S1B. Choose an arbitrary cj > 0. (We use the maximal cj ). Step S1C. If a1j , . . . , amj ≤ 0, stop the algorithm. Maximum is + ∞.
Otherwise, go to the next step. Step S1D. Compute min
1≤i≤m
b
i
aij
| aij > 0 =
b p a pj
and replace nonbasic and basic variables xN,j and xB,p , respectively, applying Algorithm 1. If the condition b1 , . . . , bm ≥ 0 is not satisfied, then we use the following steps to search for the first basic feasible solution Algorithm 3. Step S2. Select the last bi < 0.
4
Nebojˇsa V. Stojkovi´ c, Predrag S. Stanimirovi´c and Marko D. Petkovi´ c
Step S3. If ai1 , . . . , ain ≥ 0 then STOP. Linear program can not be solved. Step S4. Otherwise, find aij < 0, compute
min k>i
b b i
aij
k
∪
akj
| akj > 0
=
b p a pj
and replace nonbasic and basic variables xN,j and xB,p , respectively. We use the last aij < 0. In the begining we suppose that the matrix A is of full rank ( rank(A) = m). This is valid if the equalities in J i are lineary independent. Otherwise, we apply Gauss-Jordan algorithm for the elimination of dependent equalities. After that, we apply the next algorithm to obtain the canonical form (1.3). Algorithm 4. Step 1. If J i = ∅, perform Algorithm 3. Step 2. Find the first i such that ith constraint is a equality and choose the
0 for the pivot element. (If there not exists aij last aij = = 0 and bi = 0, the problem is not feasible; if bi = 0, then we can drop ith constraint.) Step 3. Apply Algorithm 1 and drop the jth column. Step 4. Find the next i such that the ith constraint is an equality and perform Step 2. Otherwise, apply Algorithm 3. The problem of the replacement of a basic and a nonbasic variable in the general simplex method is contained in Step S 1D and Step S 4. We observed two drawbacks of Step S 4. 1. If p = i and if there exists index t < i = p such that bt b p < , atj a pj
bt > 0, atj > 0
in the next iteration xB,t becomes negative: xB,t = b1t = bt −
b p atj < 0. a pj
2. If p > i, in the next iteration b1i is negative, but there may exists bt < 0, t < i such that min k>t
b
t
atj
b
, −atj > 0 ∪
k
akj
| − akj < 0, bk > 0
=
bt . atj
Modification of simplex method and its implementation in visual basic
5
In this case, it is possible to choose atj for the pivot element and obtain xB,t = b1t =
bt ≥ 0. atj
Also, since
bt bk ≤ , atj akj each bk > 0 remains convenient for the basic feasible solution: xB,k = b1k = bk −
bt akj ≥ 0. atj
For this purpose, we propose a modification of Step S4 . This modification follows from the following lemma. Lemma 2.1. Let the problem (1.1) be feasible and let x be the basic infeasible solution with bi , . . . , biq < 0. Denote I = {i1 , . . . , iq }. 1
In the following two cases a) q = m, and
b) q < m and there exists r ∈ I and s ∈ { 1, . . . , n} such that (2.1)
min h∈ / I
b
h
ahs
| ahs > 0 ≥
br , ars < 0, ars
it is possible to produce the new basic solution x1 = {x1B, 1 , . . . , x1B,m } with at most q − 1 negative coordinates in only one iterative step of the simplex method, if we choose ars for the pivot element, i.e. replace nonbasic variable xN,s with the basic variable xB,r . Proof. a) If q = m, choose an arbitrary coefficient ams < 0 for the pivot
element. Applying the simplex method we get a new solution with at least one coordinate positive. For example, we have x1B,m = b1m =
bm ≥ 0. ams
b) Assume now that the conditions q < m and (2.1) are satisfied. Choose ars for the pivot element. In this case the coordinates of the new basic solution are br x1B,i = b1i = bi − ais , i = r, ars br x1B,r = b1r = . ars
6
Nebojˇsa V. Stojkovi´ c, Predrag S. Stanimirovi´c and Marko D. Petkovi´ c
For k = r, k ∈ / I and aks < 0 it is obvious that x1B,k = bk −
br aks ≥ 0. ars
For aks > 0 and k ∈ / I , using bk br ≥ aks ars we conclude immediately x1B,k = b1k = bk −
br aks ≥ 0 ars
which completes the proof.
/ I Remark 2.1. If there is no r such that the condition (2.1) is valid, let r ∈ and s ∈{1, . . . , n} be such that min h∈ / I
b
h
ahs
| − ahs < 0 =
br . ars
For such r and s we use ars for the pivot element. Applying the simplex transformation we get the new solution x1 with nonnegative coordinates x1B,i = b1i = bi −
br ais , i ∈ / I. ars
As the set of the basic solutions is finite, after finitely many transformations, applying anticycling rules if it is necessary, condition (2.1) will be valid. In accordance with these considerations, we propose the following improvement of Algorithm 3 . Algorithm 5 . Step 1. If b1 , . . . , bm ≥ 0 perform Algorithm 2 . Otherwise, construct the set
B = {bi , . . . , biq } = {bik | bik < 0, k = 1, . . . , q} . 1
Step 2. Select the first bis < 0. Step 3. If ais ,1 , . . . , ais ,n ≥ 0 then STOP. Linear program is not solvable.
Modification of simplex method and its implementation in visual basic
7
Otherwise, construct the set Q = {ais ,jp < 0, p = 1, . . . , t }, set p = 1 and continue. Step 4. Compute min
1≤k≤m
Step 5. If
b
k
ak,jp
| ak,jp > 0, bk > 0 =
bis ais ,jp
≤
bh . a p,jp
bh a p,jp
then replace nonbasic and basic variables xN,jp and xB,is , else go to Step 6. Step 6. If p > t replace xN,jp and xB,h and go to Step 2. Otherwise, put p = p + 1 and go to Step 3. In the sequel we propose an improvement of Algorithm 1. Observe that in the real problems the matrix A is very sparse, so the number of coeficients needed to transform is not very great. Algorithm 6. (The modification of Algortihm 1.) Step 1. Form the sets V = {a pl |a pl = 0, l = 1, . . . , n + 1}, K = {aqj |aqj = 0, q = 1, . . . , m + 1}. Step 2. Apply Algorithm 1 only for a pl , aqj and aql satisfying a pl ∈ V and
aqj ∈ K. The next improvement is in Algorithm 4. Instead dropping columns, we will mark this column. In other words, we introduce logical sequence outc with values outc(i) = true if the ith column is not dropped, and outc(i) = false otherwise. Similary, outr is an indicator for rows. Algorithm 7. The improvement of Algorithm 4. Step 1. Set outc(i) = true, i = 1, . . . , n , and outr( j) = true, i = 1, . . . , m . Step 2. If J i = ∅, go to Step 7. Step 3. If the ith constraint is the equality, continue. = 0 such that outc( j) = true. (If there not exists aij =0 Step 4. Find aij with outc( j) = true and bi = 0, the problem is not feasible; if bi = 0, then we can drop the ith constraint and set outr(i) = false.)
8
Nebojˇsa V. Stojkovi´ c, Predrag S. Stanimirovi´c and Marko D. Petkovi´ c
Step 5. Put aij for a pivot element and perform Algortihm 1. Step 6. Go to Step 2. Step 7. Drop all columns and rows with outc(i) = false and outr( j) = false,
respectively, set outc(i) = true and outr( j) = true for all i, j and perform Algortihm 3. 3. Implementation
Simplex algorithm (Algorithms 1, 2, 3 and 4), modification (Algorithm 5) and both improvements (Algorithms 6 and 7) are implemented in the code MarPlex written in the programming language Visual Basic [5]. 4. Numerical experience Example 4.1. We tested the code MarPlex on some Netlib test problems.
We compare our results with the popular robust code P Cx [2]. From Table 1. we can see that our results are in accordance with the results obtained by P Cx. Let us mentioned that the code P Cx is not based on the simplex method. Instead the simplex algorithm, the interior point primal dual method is implemented in PCx. Problem —P Cx — MarPlex — Algorithm5—Algorithm2—No5—No2 Adlittle —2.25494963×105 —225494.963162 —18 —100—436—272Afiro —-4.64753143×102 —-464.753142 —- ——17—17Agg — 3.59917673×107 —-35991767.286576—62 —186 —109—249 Agg3 —1.03121159×107 —10312115.933596 —- —- —393—393Blend —-3.08121498×101 —-30.812150 —- —-—189—189 Lotfi —2.5264706062×101 —-25.264706 —155 —7—559—634Sc105 —-5.2202061212×101 —-52.202061 —- —-—63—63Sc205 —-5.22020612×101 —-52.202061 —- —-—179—179 Sc50a —-6.4575077059×101 —64.575077 —- —-—30—30Sc50b —-7.000000000×101 —-70 —-—-—32—32Scagr25 —1.47534331×107 —-14753433.060769—136—234—480—1234Scagr7 —-2.33138982×106 —2331389.824330—23—51—125—123 Scorpion—1.87812482×103 —1878.124822—60 —68—191—142 Sctap1 —1.41225000×103 —1412.250000—47—154—793—897 Share2b —-4.1573224074×102 —415.732241 —- —-—86—86Stocfor1 —-4.1131976219×104 —-41131.976219 —- — -—47—47LitVera —1.999992×10−2 —0 —-—- —3—3 Table 1.
Note that our result for the ill-conditioned problem LitV era from [4] is correct and that code P Cx is unable to give better precision in that case. In the next two columns we give the number of iterations needed for the first basis feasible solution. As we can see, Algorithm 5 is faster then Algorithm 2 almost in all casses. In the last two columns the number of all iterations are given. References [1] B.D. Bounday, Basic linear programming , Edvard Arnold, Baltimore, 1984.
Modification of simplex method and its implementation in visual basic [2]
9
J. Czyzyk, S. Mehrotra and S.J. Wright, PCx User Guide , Optimization Thechnology Center, Technical Report 96/01, 1996. [3] J.P. Ignizio, Linear programming in single-multiple-objective systems, Englewood Cliffs:Prentice Hall, 1982. [4] V. Kovaˇcevi´c-Vujˇci´c, Ill conditioness and interior point method , Technical Report 901-98, Laboratory of Operations Research, Faculty of Organizational Sciences, November 1998. [5] Microsoft Developer Network , Microsoft Corporation Inc.1998. [6] M. Sakarovitch, Linear programming , Springer-Verlag, New York, 1983. cko programiranje , Univerzitet u Priˇ [7] S. Vukadinovi´c, S. Cveji´c, Matematiˇ stini, Priˇstina 1996., 1983. (In Serbian)