Modification of Simplex Method and Its Implementation in Visual Basic Simplexfol

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