Example: Consider the following maximization problem.
Initial construction stages:
For the above problem —
Matrix A — at iteration 0
Table explanation
B: The base and contains the main variables. The simplex algorithm starts with those variables that form the identity matrix. For example, in the above example, x4 and x3 form the 2 × 2 identity matrix.
CB: are the coefficients of the main variables in the objective function. The target functions do not contain x4 and x3, so they are equal to 0.
XB: the amount of resources, or we can say RHS from the limits.
yi: full matrix A.
Simplex Algorithm 1. Start with the initial basis associated with identity matrix. 2. Calculate the relative profits. For MAX problem If all the relative profits are less than or equal to 0, then the current basis is the optimal one. STOP. Else contniue to 3. For MIN problem If all the relative profits are greater than or equal to 0, then the current basis is the optimal one. STOP. Else contniue to 3. 3. Find the column corresponding to max relative profit. Say column k has the max Rel. profit. So xk will enter the basis. 4. Perform a min ratio test to determine which variable will leave the basis.Index of the min element ie `r` will determine the leaving variable. The basic variable at index r, will leave the basis. NOTE: Min ratio test is always performed on positive elements. 5. It`s evident that the entered variable will not form an identity matrix, so we will have to perform row operations to make it identity again. Find the pivot element. The element at index (r, k) will be the pivot element and row r will be the pivot row. 6. Divide the rth row by pivot to make it 1. And subtract c * (rth row) from other rows to make them 0, where c is the coefficient required to make that row 0.
Table at iteration 1
Calculation of relative profit — (Cj — Zj), where Cj — coefficient in Z, and Zj — yi * CB
C1 — Z1 = 1 — (1 * 0 + 2 * 0)
C2 — Z2 = 1 — (1 * 0 + 1 * 0)
C3 — Z3 = 0 — (0 * 0 + 1 * 0)
C4 — Z4 = 0 — (1 * 0 + 0 * 0)
So the Relative Profit — 1, 1, 0, 0 (as shown in the table)
It is clear that not all relative profits are less than or equal to 0. Therefore, we will perform the next iteration.
Defining an input variable and an output variable.
Maximum relative profit 1 for index 1. Thus, x1 will be included in the base.
The minimum value (8, 5) is 5, which corresponds to index 2. So x3 will leave the base .
Since the x1 entered does the necessary row operations to create the identity matrix.
Summary index = [2, 4]
Pivot = 2
Divide the 2nd row by the pivot element i.e. 2 to make it 1.
And subtract 1 * R2 from R1 to make it 0
See the following table.
Table at iteration 2
Relative profit = 0, 1/2, 1/2, 0
Composite index = [1, 5]
Pivot element = 1/2
Perform the necessary operations with the strings.
See the following table
Relative profit = 0, 0, 0, 1
Since all relative profits are less than or equal to 0. Thus, the optimality is achieved.
This will be the final simplex table and the optimal one.
Z value for optimality = 6 * 1 + 2 * 1 = 8
The following cases may occur when this algorithm is executed.
Example 2
The above example was a case of equality where we were able to find an initial basis. Now let`s run a simplex for an example where there is no identity formation.
Convert the above issue to standard form i.e.
where x3, x4 and x5 — weak variables . They will form the identity and therefore the original foundation.
Table at iteration 0
Now continue as in the previous example.
Table at iteration 1
Relative profit = 2, 5, 0, 0, 0
Composite index = [2, 5]
Pivot element = 1
Table in iteration 2
Relative profit = 2, 0, 0, 5, 0
Composite index = [1, 4]
Spread element = 1
Table at iteration 3
Relative profit = 0, 0, 0, 2, 3, 0
Since all relative profits are less than equal to 0. Optimality is achieved.
This is the last simplex table and optimal.
Z value for optimality = 3 * 2 + 3 * 5 + 0 * 0 = 21
Code implementation of the simplex algorithm
