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|
Are considered the following phases:
1. Turning the inequalities into equalities
Introduce a slack variable for each constraint of the type ≤ to turn them into equalities, giving the following linear equation system:
|2x + y + r = 18|
|2x + 3y + s = 42|
|3x + y + t = 24|
2. Equaling the objective function to zero
|Z - 3x - 2y = 0|
3. Writing the initial board simplex
In columns will appear all basic variables of the problem and the slack/surplus variables. In rows you can observe, for each constraint the slack variables with its coefficients of obtained equalities, and the last row with the values resulting of substitute the value of every variable at function objective, and operate just as was explained in the theory to get the left values from the row:
|Board I . 1st iteration|
4. Halt condition
When at the Z row there aren't negative values, the optimal solution of the problem has been reached. In such a case, the algorithm has finished. If it were not so, the following steps must be executed.
5. Input-output base condition
6. Calculating the coefficients of the new board.
The new coefficients of the pivot row , t (P5), are obtained dividing all of the coefficients from such row among the pivot element, 3, that is the one necessary to turn into 1.
Following, with Gaussian reduction we do zeros the remainders terms of that column, with it we get the new coefficients from the other rows including that belong to the objective function row Z.
Also, it can be done in the following way:
New pivot row = (Old pivot row) / (Pivot)
New row = (Old row) - (Coefficients from old row placed at incoming variable's colum) x (New pivot row)
Lets see an example, once the pivot row has been calculated (x's (P1) row at Board II):
|Board II . 2nd iteration|
Can be noticed that we have not attained the halt condition because at Z row, there is one negative, -1. We must do another iteration:
Working of analogous form that before, we obtain the board:
|Board III . 3rd iteration|
As you can see, there is a element with minus sign in Z row, - 1, it means that we have not come still to the optimal solution. It is necessary to repeat the process:
We get the board:
|Board IV . 4th iteration|
As in the last row, all the coefficients are positive, then the halt condition is obey, getting the optimal solution.
The optimal solution is given by the Z value, at the column of the solution values, in this case: 33. In the same column, you can notice the point where it is reached, watching the rows correspondents to the decision variables that come at base: (x,y) = (3,12)