Simplex method transforms equations linearly and moves a solution to different point iteratively with the goal of improving the objective function value and a model with canonical form is necessary for solving the problem. Based on previous example, we now have a complete canonical form (simplified):
(OF) 𝑥0 − 6𝑥𝑎 − 3𝑥𝑐 = 0
(1) 9𝑥𝑎 + 5𝑥𝑐 + 𝑠1 = 450
(2) 50𝑥𝑎 + 𝑠2 = 2000
(3) 0.1𝑥𝑐 + 𝑠3 = 5
(4) 𝑥𝑎 + 𝑥𝑐 + 𝑠4 = 70
(5) 𝑥𝑎,𝑥𝑐,𝑠1,𝑠2,𝑠3,𝑠4 ≥ 0
Solving the problem with simplex method requires four steps in each iteration:
1. Optimality Check
2. Choosing a pivot Column
3. Choosing a pivot Row
4. Exchange variables
Step 1: Optimality Check.
Another way to represent a canonical form is with a simplex tableau. This tableau contains rows for both objective function and constraints with each column for each variable and the right-hand sides. Each element of the tableau is the coefficient from each variable. Here is the simplex tableau for the canonical form.
This canonical model is also considered as a solution of the problem; However, it is still unknown whether this solution is already optimal. Solutions are considered optimal when all objective functions coefficients are non-negative for maximization problem or non-positive for minimization problem. Here two coefficients in objective functions are still negative, hence the model is not optimal.
Step 2: Choosing a pivot column.
The goal of this step is choosing a non-basic variable that will be converted into a basic variable. Pivot column is selected from a non-basic variable with a negative objective coefficient function (maximization problem) or positive objective coefficient function (minimization problem). Based on the example, two variables meet these requirements: 𝑥𝑎 and 𝑥𝑐 (𝑠1,𝑠2,𝑠3 and 𝑠4 are basic variables). For this example, let 𝑥𝑎 be the pivot column (highlighted in blue).
Step 3: Choosing a pivot row.
As oppose to step 2, this step aims to choose a basic variable that will be changed into a non-basic variable. Pivot row is selected based on a value called quotient, which is the ratio of Right-hand Sides value and the coefficient from the selected pivot column. The row that has the lowest quotient value becomes the pivot row. Here is the quotient value for each row from the example.
It is shown on the table that row (2) has the lowest value, hence it becomes the pivot row (highlighted in blue) and basic variable 𝑠2 will be converted. The intersection between pivot row and pivot column is called pivot element (highlighted in green).
Step 4: Exchange variables.
This is the part where the exchange of non-basic (𝑥𝑎) and basic variable (𝑠2) happens. To exchange variables, transforms all equations linearly such that, the current non-basic variable has a coefficient of 1 in the pivot row and coefficient of 0 for other rows.
It is possible in linear transformations to multiply a row by arbitrary number or adding a multiple of pivot row to another row. Let us see the pivot row, the equation of constraint (2) (in canonical form) is the following:
50𝑥𝑎 + 𝑠2 = 2000
To change the current 𝑥𝑎 coefficient to 1, multiply the equation by 0.02, hence:
𝑥𝑎 + 0.02𝑠2 = 40
For the other row, we use the constraint (1) as an example:
9𝑥𝑎 + 5𝑥𝑐 + 𝑠1 = 450
To change the current 𝑥𝑎 coefficient to 0, subtract this equation by 9/50 times the pivot row equation, hence:
Apply the same method to other remaining rows, then we have our second simplex tableau:
This is the end of one iteration in simplex method. These steps repeats iteratively until they obtain optimal solution. Applying the same method to the second simplex tableau results the third simplex tableau:
Note that in the third simplex tableau, all objective function coefficients are non-negative, hence this solution is optimal and the iteration stops.
The right-hand sides of simplex tableau represent the value of each basic variables in each row. In the first row, value of right-hand side is 294 with the basic variable 𝑥0, hence 𝑥0 equals to 294. This applies also to other rows, thus the value of 𝑥𝑐 is 18 and 𝑥𝑎 is 40.
This means the number of affogato and café latte sold must be 40 and 18 respectively to achieve the optimal revenue of €294. Note that Simplex Method provides the same result as the graphical solution method discussed in the previous part and this method is easily applicable with more constraints and variables.
Comments