Solve using the Graphical 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 |
Extreme point | Coordinates (x,y) | Objective value (Z) |
---|---|---|
O | (0,0) | 0 |
C | (0,14) | 28 |
G | (3,12) | 33 |
H | (6,6) | 30 |
F | (8,0) | 24 |
Successive constructed tableaux in the Simplex method will provide the value of the objective function at the vertices of the feasible region, adjusting simultaneously, the coefficients of initial and slack variables.
In the initial tableau the value of the objective function at the O-vertex is calculated, the coordinates (0,0) correspond to the value which have the basic variables, being the result 0.
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 |
The input base variable in the Simplex method determines towards what new vertex is performed the displacement. In this example, as P1 (corresponding to 'x') enters, the displacement is carried out by the OF-edge to reach the F-vertex, where the Z-function value is calculated. This step occurs in the second iteration of the Simplex method, as shown in tableau II. The corresponding value to F-vertex is calculated in it, and Z = 24 is the obtained value for the function.
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 |
A new displacement by the FH-edge is made, up to H-vertex (data in Table III). In the third iteration, the value of the function at the H-vertex is calculated to obtain Z = 30.
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 |
The process goes on through the HG-edge up to G-vertex, obtained data are shown in tableau IV. At this point, the process ends, being able to check that the solution does not improve moving along GC-edge up to C-vertex (the current value of the Z-function is not increased).
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 |
The maximum value of the objective function is 33, and it corresponds to the values x = 3 and y = 12 (G-vertex coordinates).
In Graphical method is necessary to calculate the value of the objective function at each vertex of feasible region, while the Simplex method ends when the optimum value is found.
PHPSimplex
Version 0.81
Copyright ©2006-2021. All rights reserved.
Developed by:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz
English translation by:
Luciano Miguel Tobaria
French translation by:
Ester Rute Ruiz
Portuguese translation by:
Rosane Bujes