Another exact approach for solving Linear programming is Simplex Method. This technique is applicable for any variables and constraints size hence it is more flexible compared to Graphical Solution Method. Simplex method utilizes the linear transformation of equations and interactively moves a solution from one point to another with the goal of improving the objective function value.
To solve using Simplex methods, the model has to be in a canonical form and it comprises of four characteristics:
Objective function is in implicit form : Implicit form means that all variables are on one side of equation and the constants are on the opposite side with the objective function value (x0) has coefficient of 1.
All constraints are equalities
All variables are non-negative
Each constraint contains a basic variable : Basic variable is a variable with coefficient of 1 and only occur once in all constraints and objective functions.
Let us use the same example of Indemy Coffee Shop and construct a canonical form based on the mathematical model below.
(OF) max𝑥0 = 6𝑥𝑎 + 3𝑥𝑐
(1) 9𝑥𝑎 + 5𝑥𝑐 ≤ 450
(2) 50𝑥𝑎 ≤ 2000
(3) 0.1𝑥𝑐 ≤ 5
(4) 𝑥𝑎 + 𝑥𝑐 ≤ 70
(5) 𝑥𝑎 ≥ 0
(6) 𝑥𝑐 ≥ 0
Step 1: Change the objective function to implicit form
With this objective function, both 𝑥𝑎 and 𝑥𝑐 variables are moved to left side and the constant stays on the right side.
𝑥0 = 6𝑥𝑎 + 3𝑥𝑐
𝑥0 − 6𝑥𝑎 − 3𝑥𝑐 = 0
Step 2: Change all constraints are equalities
To change from inequalities to equalities, a slack variable is necessary to compensate the inequalities itself. If it is a “less than equal to” constraint, add a slack variable on the left side of equation and if it is a “more than equal to”, subtract a slack variable. For example:
(1) 9𝑥𝑎 + 5𝑥𝑐 ≤ 450, since this is a “less than equal to” constraint then the constraint changes to: (1) 9𝑥𝑎 + 5𝑥𝑐 + 𝑠1 = 450
Applying this method to other constraints, we have:
(2) 50𝑥𝑎 + 𝑠2 = 2000
(3) 0.1𝑥𝑐 + 𝑠3 = 5
(4) 𝑥𝑎 + 𝑥𝑐 + 𝑠4 = 70
Note that each constraint has their own unique slack variables and it is unnecessary to change constraint (5) and (6) to equalities since they are only logical constraints. Moreover, adding these slack variables also fulfill the fourth requirements of implicit form
Step 3: Transform all variables coefficient such that they are non-negatives Since every coefficient is already non-negatives, no transformation is needed.
Here is the complete canonical form:
(OF) 𝑥0 − 6𝑥𝑎 − 3𝑥𝑐 = 0
(1) 9𝑥𝑎 + 5𝑥𝑐 + 𝑠1 = 450
(2) 50𝑥𝑎 + 𝑠2 = 2000
(3) 0.1𝑥𝑐 + 𝑠3 = 5
(4) 𝑥𝑎 + 𝑥𝑐 + 𝑠4 = 70
(5) 𝑥𝑎 ≥ 0
(6) 𝑥𝑐 ≥ 0
(7) 𝑠1 ≥ 0
(8) 𝑠2 ≥ 0
(9) 𝑠3 ≥ 0
(10) 𝑠4 ≥ 0
Note that constraints (5) to (10) are only logical constraints. In the next part, we cover the simplex method procedure as well as how to interpret the solution properly.
Comments