If a Linear Programming (LP) problem contains only 2 activities (decision variables), then it can be solved using the graphical method, but if it involves more than two activities, the graphical method can no longer be used, so the simplex method is required.
The simplex method is a common method used to determine the optimal combination of 3 or more variables.
Getting to Know the Simplex Method
Simplex Method Steps
1. Changing the Objective Function and Constraints
Example:
Objective function; maximum Z = 6X1 + 8X2
Limitation:
- 3X1 + 5X2 ≤ 260
- 5X1 + 6X2 ≤ 380
- 4X1 + 3X2 ≤ 200
The objective function is changed to an implicit function, meaning all CjXij are shifted to the left. Maximize Z = 6X1 + 8X2, then it becomes Z - 6X1 - 8X2 = 0
In the standard form, all constraints have a ≤ sign, these inequalities must be transformed into equalities. This is done by adding Slack Variables (i.e. additional variables representing the unemployment rate or capacity that are constraints).
These Slack variables are Xn+1, Xn+2, ... Xn+m. Sometimes Slack Variables are given other letter marks, for example S1, S2, ...., and so on.
Limitation functions:
- 3X1 + 5X2 ≤ 260 becomes → 3X1 + 5X2 + X3 = 260
- 5X1 + 6X2 ≤ 380 becomes → 5X1 + 6X2 + X4 = 380
- 4X1 + 3X2 ≤ 200 becomes → 4X1 + 3X2 + X5 = 200
2. Arrange the equations into a table
After the formulation is changed, it is then arranged into a table, the table in symbol form is as follows:
| Variabel Dasar | Z | X1 | X2 | … | Xn | Xn+1 | Xn+2 | … | Xn+m | NK |
|----------------|---|-----|-----|---|-----|------|------|---|------|----|
| Z | 1 | -C1 | -C2 | … | -Cn | 0 | 0 | … | 0 | 0 |
| Xn+1 | 0 | a11 | a12 | … | a1n | 1 | 0 | … | 0 | b1 |
| Xn+2 | 0 | a21 | a22 | … | a2n | 0 | 1 | … | 0 | b2 |
| . | . | . | . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . | . | . | . |
| Xn+m | 0 | am1 | am1 | … | amn | 0 | 0 | … | 1 | bm |NK is the Right Value of the equation, which is the value behind the (=) sign. Basic Variable is a variable whose value is the same as the right side of the equation.
Example using the question above:
| Variabel Dasar | Z | X1 | X2 | X3 | X4 | X5 | NK |
|----------------|---|----|----|----|----|----|-----|
| Z | 1 | -6 | -8 | 0 | 0 | 0 | 0 |
| X3 | 0 | 3 | 5 | 1 | 0 | 0 | 260 |
| X4 | 0 | 5 | 6 | 0 | 1 | 0 | 380 |
| X5 | 0 | 4 | 3 | 0 | 0 | 1 | 200 |3. Selecting Key Columns
The key column is the column that is the basis for changing the table above. Select the column in the objective function row (Z) that has the largest negative value, give a square mark on the column.
Example using the question above:
4. Selecting Key Rows
The key row is the row that is the basis for changing the table above. First, find the index of each row by dividing the values in the NK column by the values in the same row in the key column.
Index = NK Column Value / Key Column Value
Select the row that has a positive index with the smallest number.
Key Row Selection Table
5. Changing Key Row Values
The key row value is changed by dividing it by the key number, replacing the base variable in the selected row with the variable at the top of the key column.
In other words, the value found at the intersection of the key row and key column is selected as the key value.
Table of how to change key row values
6. Change values other than key rows
Row values, other than key rows, can be changed with the following formula:
New Row = Old Row - (Coefficient on key column) x New value of key row
For example, using the above question, the new values of the first row (Z) are as follows:
First table old values and second table new values,
7. Re-Optimization
Repeat the repair/change steps from step 3 to step 6, until the objective function row (first row) is obtained with no negative values. If the Z row is all positive, then the process is stopped.
Key Column and Row Selection Table from the first repair table, and the new values of the key rows resulting from the second repair;
New values other than key rows:
The second table of changes/improvements. The first table is the old value, the second table is the new value.
Table obtained from the first table up to the last fix/change:
Because in the objective function row (Z) there are no negative values (-), it is considered optimal with the values X1 = 20, X2 = 40 and Z max = 440.
Conclusion:
So product P (Z1) is produced as much as 20 units and product Q (X2) is produced as much as 40 units with a maximum profit of 440 x Rp. 10,000,- = Rp. 4,400,000,-
Exercise
Simplex vs. Graphical Method Solution
Reference:
Operations Research Module, (B) "Simplex Method", compiled by Minawarti, ST.