Bounded Variable Simplex Algorithm

We know that in linear programming, there are plenty of algorithms we could use to solve a linear programming problem according to different scenarios. In this article, we are going to discuss the Bounded Variable simplex algorithm.

Frequently, in developing a linear programming model, constraints of the form

 xj ≥ lj

xj ≤ uj

are encountered. In this context, lj and uj represent simple lower and upper bounds on the variable xj. Now, letting

 a linear program with bounded variables can be written as follows:

(BVLP)        maximize    z = ct x

subject to   Ax = bt

  l ≤ x ≤ u

Where A is mxn matrix and l ≤ X ≤ u; u and l are called an upper and a lower bound of x respectively.

The above inequality constraints can be converted into equality constraints by introducing some slack and surplus variables.

i.e. The mathematical model can be represented as follows: 

                     Maximize z =ct x

                     Subject to    Ax =bt

                                                x+s=u

                                             x,s ≥0

The basic idea of the bounded-variables simplex method is to handle the simple bounds of the variables in an implicit manner (in a manner analogous to handling the non-negativity restrictions in the standard simplex method). This allows us to maintain a standard m×m basis matrix, which is generally referred to as the working basis.

Bounded variable Simplex Algorithm in step-wise form

Step 01: If any of the variables are at a positive lower bound, make it zero by

introducing a new variable. If any of bi’s negative, multiply the

corresponding constraint by -1.

Step 02: Convert the mathematical model into the standard form and obtain the

         initial basic feasible solution.

Step 03: Compute the net evaluations (ci – zi) and examine their sign. Identify the

entering variable for the primal feasible and dual infeasible simplex table. Go to the Step 04. Otherwise (if the simplex table is primal feasible and dual feasible) stop.

Step 04: Determine the leaving variable using the following quantities;

• If q = q1 , which corresponds to the aij, then the coefficient aij is called the pivot element and

  • • i th row                  pivot row  

    • j th column            pivot column

Apply the pivoting method to obtain the new simplex table.

• If q = q2 , which corresponds to − aij, then aij is called the pivot element.

Note: (i) If one of the decision variables is selected as a leaving variable, then the corresponding variable leaves with its upper bound and replace the decision variable with the difference between the upper bound and decision variable value [  x ¢j = (uj – xj) ].

(ii) Use the following expression to calculate the new bi values (bi’) after obtaining the new simplex table by applying pivoting method with (-ve) pivot element

bi ¢ = bi – (aij)uj   where i − leaving variable according ( ) to the (-ve) pivot element. 

(iii) Multiply the elements in the leaving variable according to the (-ve) pivot element by (-1).

•  If q = uj, change the simplex table according to the following   conditions:

(i)  No pivoting method

(ii)  Compute the bi values using the expression given below:

bi ¢ = bi – (aij)uj   where j− pivot column

(iii) Replace the decision variable with a new variable with the difference between the upper bound and the value of the decision variable.

xj ¢ = (uj – xj)

(iv)  Multiply the elements in the pivot column by (-1)

Go to Step 03 (Repeat the procedure until an optimal solution is reached).

Applications of Bounded Variable Simplex Algorithm.

Networking is one of the most important branches of Operations Research. Most of the real-world methods can be formulated as network models. One such model is the Maximal flow algorithm.

The Maximum Flow Algorithm is one of the most important methods to obtain maximum flow in a network. The algorithm is based on finding breakthrough paths with net positive flow between the source and sink nodes. Each path commits part of all the capacities of its arcs to the total flow in the network.

We can formulate the Maximal Flow problem as a linear programming problem and solve it using Bounded Variable Simplex Algorithm.

Conclusion

The bounded variable Simplex Algorithm is efficient computationally because it accounts for the bounds implicitly. It makes a large system of constraint set a small one. If there are upper bounds for decision variables it takes less time to solve a problem than the simplex method.