Solve using the Simplex method the following problem:
Maximize | Z = f(x,y) = 3x + 2y |
subject to: | 2x + y ≤ 18 |
2x + 3y ≤ 42 | |
3x + y ≤ 24 | |
x ≥ 0 , y ≥ 0 |
Consider the following steps:
A change is made to the variable naming, establishing the following correspondences:
As the independent terms of all restrictions are positive no further action is required. Otherwise there would be multiplied by "-1" on both sides of the inequality (noting that this operation also affects the type of restriction).
The inequalities become equations by adding slack, surplus and artificial variables as the following table:
Inequality type | Variable that appears |
≥ | - surplus + artificial |
= | + artificial |
≤ | + slack |
In this case, a slack variable (X3, X4 and X5) is introduced in each of the restrictions of ≤ type, to convert them into equalities, resulting the system of linear equations:
2·X1 + X2 + X3 = 18 |
2·X1 + 3·X2 + X4 = 42 |
3·X1 + X2 + X5 = 24 |
The initial tableau of Simplex method consists of all the coefficients of the decision variables of the original problem and the slack, surplus and artificial variables added in second step (in columns, with P0 as the constant term and Pi as the coefficients of the rest of Xi variables), and constraints (in rows). The Cb column contains the coefficients of the variables that are in the base.
The first row consists of the objective function coefficients, while the last row contains the objective function value and reduced costs Zj - Cj.
The last row is calculated as follows: Zj = Σ(Cbi·Pj) for i = 1..m, where if j = 0, P0 = bi and C0 = 0, else Pj = aij. Although this is the first tableau of the Simplex method and all Cb are null, so the calculation can simplified, and by this time Zj = -Cj.
Tableau I . 1st iteration | |||||||
---|---|---|---|---|---|---|---|
3 | 2 | 0 | 0 | 0 | |||
Base | Cb | P0 | P1 | P2 | P3 | P4 | P5 |
P3 | 0 | 18 | 2 | 1 | 1 | 0 | 0 |
P4 | 0 | 42 | 2 | 3 | 0 | 1 | 0 |
P5 | 0 | 24 | 3 | 1 | 0 | 0 | 1 |
Z | 0 | -3 | -2 | 0 | 0 | 0 |
If the objective is to maximize, when in the last row (indicator row) there is no negative value between discounted costs (P1 columns below) the stop condition is reached.
In that case, the algorithm reaches the end as there is no improvement possibility. The Z value (P0 column) is the optimal solution of the problem.
Another possible scenario is all values are negative or zero in the input variable column of the base. This indicates that the problem is not limited and the solution will always be improved.
Otherwise, the following steps are executed iteratively.
First, input base variable is determined. For this, column whose value in Z row is the lesser of all the negatives is chosen. In this example it would be the variable X1 (P1) with -3 as coefficient.
If there are two or more equal coefficients satisfying the above condition (case of tie), then choice the basic variable.
The column of the input base variable is called pivot column (in green color).
Once obtained the input base variable, the output base variable is determined. The decision is based on a simple calculation: divide each independent term (P0 column) between the corresponding value in the pivot column, if both values are strictly positive (greater than zero). The row whose result is minimum score is chosen.
If there is any value less than or equal to zero, this quotient will not be performed. If all values of the pivot column satisfy this condition, the stop condition will be reached and the problem has an unbounded solution (see Simplex method theory).
In this example: 18/2 [=9] , 42/2 [=21] and 24/3 [=8]
The term of the pivot column which led to the lesser positive quotient in the previous division indicates the row of the slack variable leaving the base. In this example, it is X5 (P5), with 3 as coefficient. This row is called pivot row (in green).
If two or more quotients meet the choosing condition (case of tie), other than that basic variable is chosen (wherever possible).
The intersection of pivot column and pivot row marks the pivot value, in this example, 3.
The new coefficients of the tableau are calculated as follows:
So the pivot is normalized (its value becomes 1), while the other values of the pivot column are canceled (analogous to the Gauss-Jordan method).
Calculations for P4 row are shown below:
Previous P4 row | 42 | 2 | 3 | 0 | 1 | 0 |
- | - | - | - | - | - | |
Previous value in pivot column | 2 | 2 | 2 | 2 | 2 | 2 |
x | x | x | x | x | x | |
New value in pivot row | 8 | 1 | 1/3 | 0 | 0 | 1/3 |
= | = | = | = | = | = | |
New P4 row | 26 | 0 | 7/3 | 0 | 1 | -2/3 |
The tableau corresponding to this second iteration is:
Tableau II . 2nd iteration | |||||||
---|---|---|---|---|---|---|---|
3 | 2 | 0 | 0 | 0 | |||
Base | Cb | P0 | P1 | P2 | P3 | P4 | P5 |
P3 | 0 | 2 | 0 | 1/3 | 1 | 0 | -2/3 |
P4 | 0 | 26 | 0 | 7/3 | 0 | 1 | -2/3 |
P1 | 3 | 8 | 1 | 1/3 | 0 | 0 | 1/3 |
Z | 24 | 0 | -1 | 0 | 0 | 1 |
Tableau III . 3rd iteration | |||||||
---|---|---|---|---|---|---|---|
3 | 2 | 0 | 0 | 0 | |||
Base | Cb | P0 | P1 | P2 | P3 | P4 | P5 |
P2 | 2 | 6 | 0 | 1 | 3 | 0 | -2 |
P4 | 0 | 12 | 0 | 0 | -7 | 1 | 4 |
P1 | 3 | 6 | 1 | 0 | -1 | 0 | 1 |
Z | 30 | 0 | 0 | 3 | 0 | -1 |
Tableau IV . 4th iteration | |||||||
---|---|---|---|---|---|---|---|
3 | 2 | 0 | 0 | 0 | |||
Base | Cb | P0 | P1 | P2 | P3 | P4 | P5 |
P2 | 2 | 12 | 0 | 1 | -1/2 | 1/2 | 0 |
P5 | 0 | 3 | 0 | 0 | -7/4 | 1/4 | 1 |
P1 | 3 | 3 | 1 | 0 | 3/4 | -1/4 | 0 |
Z | 33 | 0 | 0 | 5/4 | 1/4 | 0 |
It is noted that in the last row, all the coefficients are positive, so the stop condition is fulfilled.
The optimal solution is given by the val-ue of Z in the constant terms column (P0 column), in the example: 33. In the same column, the point where it reaches is shown, watching the corresponding rows of input decision variables: X1 = 3 and X2 = 12.
Undoing the name change gives x = 3 and y = 12.
PHPSimplex
Version 0.9
Copyright ©2006-2015. All rights reserved.
Developed by:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz
English translation by:
Luciano Miguel Tobaria
French translation by:
Ester Rute Ruiz