Simplex method is a solving problem analytic method of linear programming, able to resolve complex models than the resolved through graphic method.
Simplex method is an iterative method that improves the solution on each step. The mathematical reason of this improvement is that the method consists in walking through a neighbor vertex in such a way that raises or decreases (according to the context of the objective’s function, whether it is maximize or minimize), given that the number of vertex that a solution polyhedron is finite, there always be a solution.
¿What is an identity matrix?
A matrix can be defined as a rectangular arrangement of elements, (o finite list of elements), which can be real numbers or complex numbers, disposed in rows and columns.
The Identity matrix or a sometimes ambiguously called a is square (it has the same number of rows, as it has the same number of columns), of order n that has all the diagonal elements equal to one (1) and all other components equal to zero (0), it’s called Identical matrix or Order “n” Identity, and it is denoted by:
The importance of this matrix theory in the Simplex Method is fundamental, given that the algorithm is based on said theory for itself problem resolution.
Important considerations when using the simplex method
Slack and Surplus Variables
The Simplex Method works based on equations and initial restrictions that are model trough lineal programing are not,, for this you have to convert this inequalities in equations using some type of variables called: Slack and Surplus Variables that are related with the resource on which the restrictions makes reference, and that on the final tabulate represents the “Slack or Surplus”, which many resolution of operation programs make reference, this variables get a great added value in the analysis of sensitivity and play a key role in the creation of the Simplex base Identity Matrix.
These variables are usually represented by the letter “S”, they add if the restriction is «<= », and they subtract if the restriction is «>=».
For example:
Artificial variable / “M” method:
An artificial variable is a math trick to turn «>=» inequalities, into equations, or when equalities appear in the original problem to resolve, the main characteristic of this variables is that they should not be part of the solution, given that they do not represent any resource. The main objective of this variables is the formation of the identity matrix.
These variables are represented by the letter “A”, constraints are always added, their coefficient is M (this is why it is called M Method, where M means a number way too big, and very less attractive to the objective’s function), and the sign in the objective’s function goes counter-wise of itself, that is to say, in problems of maximization it sign is minus (-), and on minimization problems it sign is plus (+), repeat with the objective that it’s value on the solution is zero (0).
Step by step: Simplex Method
The problem
Company SAMAN Limited. Dedicated to the manufacture of furniture, it has expanded its production in two more lines. Thus currently manufactures tables, chairs, beds and libraries. Each table requires 2 rectangular pieces of 8 pins each, and two square pieces of 4 pins each. Each chair requires 1 rectangular piece of 8 pins and 2 square pieces of 4 pins each; each bed requires 1 square piece of 8 pins, 1 square piece of 4 pins and 2 trapezoidal bases of 2 pins each; and finally each library requires 2 rectangular pieces of 8 pins each, 2 trapezoidal bases of 2 pins each and 4 rectangular pieces of 2 pins each.
Each table’s manufacture cost is $10000, and are sold in $30000; each chair’s manufacture cost is $8000, and are sold in $28000; each bed’s manufacture cost is $20000, and are sold in $40000; each library’s manufacture cost is $40000, and are sold in $60000. The main goal of the Company is to maximize profits.
Step 1: Modeling trough lineal programing:
Variables:
X1 = Quantity of tables to manufacture(units)
X2 = Quantity of chairs (units)
X3 = Quantity of bed to manufacture (Units)
X4 = Quantity of libraries to manufacture (units)
Constraints:
2X1 + 1X2 + 1X3 + 2X4 <= 24
2X1 + 2X2 + 1X3 <= 20
2X3 + 2X4 <= 20
4X4 <= 16
Objective function:
ZMAX = 20000X1 + 20000X2 + 20000X3 + 20000X4
Step 2: To convert inequalities in equations
The goal in this step is to assign a Slack Variable to each resource, given that all constraints are «<=».
2X1 + 1X2 + 1X3 + 2X4 + 1S1 + 0S2 + 0S3 + 0S4 = 24
2X1 + 2X2 + 1X3 + 0X4 + 0S1 + 1S2 + 0S3 + 0S4 = 20
0X1 + 0X2 + 2X3 + 2X4 + 0S1 + 0S2 + 1S3 + 0S4 = 20
0X1 + 0X2 + 0X3 + 4X4 + 0S1 + 0S2 + 0S3 + 1S4 = 16
This way we can see an identity matrix (n=4), form by the Slack Variables which only have a 1 coefficient on their respective resource; for example, the Slack Variable “S1” only has a 1 coefficient on the constraint corresponding to resource 1.
The Objective Function does not suffer any kind of variations:
ZMAX = 20000X1 + 20000X2 + 20000X3 + 20000X4
Step 3: Define the initial basic solution
The simplex method from an initial basic solution to make all its iterations, this solution is formed with the variables of coefficient different from zero (0) on the identity matrix.
1S1 = 24
1S2 = 20
1S3 = 20
1S4 = 16
Solution (second term): In this row is set the second term of the solution, that is to say, the correct way to do it would it be to set them organized, just as in the definition of constraints.
Cj: This row makes reference to the coefficient that each of this variables of the row “Solution” in the Objective Function.
Variable Solution: In this column is set the initial basic solution, and from this column on each iteration includes variables that will be part of the final solution.
Zj: In this row is set the total contribution, that is to say the addition of the products from the term and Cb.
Cj-Zj: In this row is made the subtraction between the row Cj and the row Zj, it’s meaning is a “Shadow Price”, that is to say, the unearned earnings for each unit of the corresponding variable that does not make part of the solution.
Solución inicial:
Step 4 : Make the necessary iterations
This is the definitive step through the Simplex Method, consists in trying while the polyhedron goes from a vertex to the other.
The following is the procedure:
1. To evaluate which variable is going in, a what’s the optimal solution.
2. The fact that a variable different is a part of the solution variables implies a series of changes in the Simplex tabulate. The change is the following:
- First thing is not to forget the value of a, corresponding to the variables going in, in this case is “a = 4”..
- The next thing is to start filling in the rest of the table, row by row.
- Repeat this procedure with the two remaining rows.
Once set the values of the matrix, you can calculate until filling the table corresponding to the first iteration.
On this way ends the first iteration, this step will repeat as any times is necessary, and only will be ended according the following criteria.
| Maximize | Minimize | |
| Optimal Solution | When all the Cj – Zj are <= 0 | When all the Cj – Zj are >= 0 |
- Continue with the iterations, so we have to repeat the anterior cases:
In this last iteration we can observe that the slogan Cj-Zj <= 0, is met; for exercise which objective function is Maximize, thus que have reached an optimal response.
X1 = 0
X2 = 7
X3 = 6
X4 = 4
With a profit of: $ 340000
Nevertheless, one the Simplex Method has ended, we can observe an identity matrix in the rectangle determine by the decision variables, the fact that in this case is not shown an identity matrix tells us that exists another optimal solution.
The way of reaching the other solution consists in altering the order on which each of the variables gets into the basic solution, remember that this process was decided by random due to Cj-Zj equality of the initial tabulate. The following is a way to reach the other solution.
We can observe that there is an alternative optimal solution.
X1 = 3 (Cantidad de mesas a producir = 3)
X2 = 4 (Cantidad de sillas a producir = 4)
X3 = 6 (Cantidad de camas a producir = 6)
X4 = 4 (Cantidad de bibliotecas a producir = 4)
Con una utilidad de: $ 340000
Minimization problems with the Simplex Method
To resolve minimization problems there are two types of procedures:
- The first, which I personally recommend, is based on an artifice applicable to the algorithm founded in the following mathematical logic: for any function f (x), any point that minimizes f (x) will also maximize a – f (x). Therefore, the procedure to follow is multiply by the negative factor (-1) the whole objective function.
The algorithm is then solved as a maximization problem.
- The second procedure which intends to preserve the minimization consists in applying the decision criteria that we have discussed, in the cases where the variable goes in, goes out and in the case that the optimal solution is found. Let’s remember:
