COSC5313                             Simplex Algorithm

 

1. Original Method.

 

1. Find a basis B such that

      X_B = B^-1  b  >= 0

 

      2.   Solve   B^t l  =   C_B

            for the vector of Simplex Multipliers  l (with m elements)

           

      3.   Select a column   a _k  of  N such that

            p_k  =   C_Nk   -  l^t  a_k   <  0

            (Note Relative Cost vector p^t  =  C_N^t  -   C_B^t B^-1 N)

            We may select the  a_k  which gives the smallest negative value of  p_k.

                If   p_k   >= 0 for every k (m+1 <= k <= n) then stop.

            The current solution is optimal.

 

4. Solve for y the system of equations:

B y =  a_k

            (Note X_B  =  B^-1 b  -   B^-1 N X_N  so y  =  B^-1 a_k  )

 

      5.   Find   q  =   X_Bl / y_l  =   min    x_Bi /y_i  for  y_i  > 0

                                                1<=i<=m                           

            If no  y_i  is positive, then the set of solutions to  Ax = b, x>=0

            is unbounded and the objective function can be made an arbitrarily large

            negative number. Terminate the computation in this case.

 

6. Update the basic solution.

            x_i   =   x_i   - q y_i , for  1 <=  i <= m , i  <> l

And,    x_k =   q    becomes a new basic variable and  x_l becomes a new

non-basic variable.                               

 

            For the new basis, we can compute its inverse instead from the inverse of

the current basis as follows:

 

            (B’)^-1  =   E   B^-1  where the matrix E is the identity matrix except that                                 its l-th column has the following:

                        ( - y₁/y_l ,   -y₂/y_l   ,  -y₃/y_l ,  +1/y_l,  …, -y_m/y_l)   

 

B.   2-Phase Method.: To ensure a basic solution

 

1. Assume that b>=0
2. Problem formulation

Max x_m+n+1   =  -(  c₁x₁  +  c₂x₂  +  c₃x₃  +… + c_nx_n )

subject to

(i)                 (A+I_m)x = b where x is an (m+n)-vector

(ii)               cx + x_m+n+1   =  0  where x is the original n-vector.

(iii)               n

          S    A_m+2,j  x_j  +  x_m+n+2   =   b_m+2 

  j=1         

  where    b_m+2   = -(b1+b2+…+bm) and

                                  m   

    A_m+2,j  =  - S    A_i,j  for j=1,2,…,n.

                      i=1                                           

(iv)             x_j >= 0 for j=1,2,3,…, m+n  

  

    c.  Example

 

Original Problem:

           

min 12 x1+3x2+4x3

            subject to

                        x1+x2 - 2x3 = 10

                        x1-2x2+3x3 = 20

                        x1,x2,x3>=0

 

            New Problem:

 

            maximize x6

            subject to

                        x1 + x2 –   2x3  + x4                          =  10

                        x1 – 2x2 + 3x3         + x5                   =  20

                    12x1 +3x2 + 4x3                   + x6          =   0

                     -2x1 +x2   -x3                                +x7  =  -30

                        x1,x2,x3,x4,x5 >= 0

                        (In general,  x_m+n+1  = -cx and   

                              x_m+n+2 = - (x_n+1 +  x_n+2 +   … +  x_n+m)  )

 

 

  In this revised problem,  we have m+2 equations in m+n+2 variables.

During phase-1, we maximize  x_m+n+2.

If this max is zero, we begin phase-2 to maximixe  x_m+n+1      

while keeping  x_m+n+2   at zero.