Simplex method

SimplexMethod. it is based on an algebraic procedure and its geometric explanation can be interpreted through the graphical method.

Summary

[ hide ]

  • 1 Basic Concepts of the Simplex Method
  • 2 To make the Simplex Method Table
  • 3 Simplex Method computational procedure
  • 4 Maximum Case
  • 5 Minimum Case
  • 6 Source

Basic Concepts of the Simplex Method

  • The application of the simplex method assumes that you have a system of linear constraints formed only by linear equations. This transformation can be carried out in a very simple way by introducing some additional variables, which are called slack variables. These variables are defined one for each constraint and if it has the sign ≤ the slack variable is added and the sign was ≥ the slack variable is subtracted.
  • After having a standard Linear Programming problem , that is, all the constraints have equal signs, it is necessary to determine the initial feasible basic solution (SBFI).
  • Given a system of m linear equations with n variables (AX = b) with m <n and range r (A) = m. If we choose any non-singular matrix of order mxm and if all the (nm) variables not associated with these columns of the matrix are equal to zero, then the solution to the resulting system of equations is called a basic solution. Since matrix A consists of n columns, we can define matrix B formed by m linearly independent columns of A, we will call this matrix basic matrix. With the remaining (nm) columns of A another matrix can be constructed that will be called a non-basic matrix and we will denote it by W. Then matrix A can be written as follows: A = (B, W).
  • The variables that are part of matrix B are called basic variables (XB) and those that are part of matrix W are called non-basic variables (XW), so vector X is made up of the set of basic and non-basic variables , that is, X = (XB, XW).
  • Then the constraint system of the Linear Programming problem AX = b can be written as: AX = BXB + WXW = b. If we assume that the non-basic variables will take a value of zero, the previous expression would be BXB = b. The expression XB = B-1 b that is obtained from the previous one, would allow us to calculate the initial feasible basic solution.

To make the Simplex Method Table

The simplex method is developed in the simplex table. Each iteration requires a table.

In the first column the coefficients of the objective function corresponding to the basic variables will be written, writing in the second column said variables. The third column indicates the values ​​that the basic variables take in the solution that is being represented by the simplex table. The rest of the columns represent the vectors Pj corresponding to each of the vectors aj of the matrix A (Pj is the coordinate vector of each vector aj with respect to the considered base). The values ​​Zj -Cj corresponding to each vector aj appear in the last row of the table. Zj coefficients are determined using the following expression: Zj = CBPj

Simplex Method computational procedure

The iterative procedure on which the simplex method is based can be summarized in the following steps:

  • Step1: Convert the inequalities into equations using the slack variables.
  • Step 2: Determine the initial feasible basic solution XB *, the values ​​Z *, Pj and Zj – Cj and construct the simplex table that summarizes all the information about this initial solution. The initial basic solution must have the characteristic that the basic matrix must be unitary. This makes it easier to calculate the inverse matrix.
  • Step 3: Examine in the simplex table the values ​​of the coefficients Zj – Cj.

The following situations may arise: Maximum Case and Minimum Case.

Maximum Case

  • All Zj – Cj ≥ 0. In this case the optimal solution has been reached. (optimality criterion)
  • One or more Zj – Cj <0. In this case, a new basic solution must be calculated by determining the vector ak that enters the base using the following expression:

ZK –CK = MIN (Zj – Cj) for all aj with Zj – Cj <0 (1)

If this minimum value is obtained for one or more vectors, any one can be chosen as the incoming vector. Once the vector ak has been chosen, two cases can occur:

  • Case 1: The Pik≤0 values ​​for each i. This indicates the existence of an unbounded solution.
  • Case 2: We have Pik> 0 for at least one i. In this case, a new basic solution can be found in which the value of Z improves or is optimal.

Minimum Case

  • All Zj – Cj ≤ 0. In this case the optimal solution has been reached. (Optimality criterion)
  • One or more Zj – Cj> 0. In this case, a new basic solution must be calculated by determining the vector ak that enters the base using the following expression (1).

Step 4: If we have Pik> 0 for at least one i, we determine the vector that comes out using the expression:

Θ = XBr / Prk = MIN {X * Bi / Pik, Pik> 0}

Vector ar must be extracted from the base and replaced by vector ak. If the same value of obtienen is obtained for 2 or more vectors, any one can be chosen as the outgoing vector.

Step 5: The new XB, Z, Pj and Zj-Cj values ​​are calculated by inserting these values ​​in the new simplex table. After completing this step, return to step 3 by repeating the procedure until the optimal solution is reached.

 

Leave a Comment