Solved Exercise of Minimization of 2 variables with the Big M MethodExample of Linear Programming - Big M Method

Next, the problem will be adapted to the standard linear programming model, adding the slack, excess and/or artificial variables in each of the constraints and converting the inequalities into equalities:

• Constraint 1: It has sign “≥” (greatest equal), therefore the excess variable S₁ will be subtracted and the artificial variable A₁ will be added. In the initial matrix, A₁ will be in the base.
• Constraint 2: It has sign “≥” (greatest equal), therefore the excess variable S₂ will be subtracted and the artificial variable A₂ will be added. In the initial matrix, A₂ will be in the base.
• Constraint 3: It has sign “≤” (least equal), therefore the slack variable S₃. This variable will be placed at the base in the initial matrix.

Now we will show the problem in the standard form. We will place the coefficient 0 (zero) where appropriate to create our initial matrix:

Initial Matrix

We will use the coefficients of the equations to elaborate our first table:

a) Reduced Cost Vector Calculation (Z):

The values recorded in row Z were obtained as follows:

• Z₁ = (C_b,1×X_1,1) + (C_b,2×X_1,2) + (C_b,3×X_1,3) - C_j,1 = (M×1) + (M×-1) + (0×0) - (1) = -1
• Z₂ = (C_b,1×X_2,1) + (C_b,2×X_2,2) + (C_b,3×X_2,3) - C_j,2 = (M×1) + (M×1) + (0×1) - (-2) = 2M + 2
• Z₃ = (C_b,1×S_1,1) + (C_b,2×S_1,2) + (C_b,3×S_1,3) - C_j,3 = (M×-1) + (M×0) + (0×0) - (0) = -M
• Z₄ = (C_b,1×S_2,1) + (C_b,2×S_2,2) + (C_b,3×S_2,3) - C_j,4 = (M×0) + (M×-1) + (0×0) - (0) = -M
• Z₅ = (C_b,1×S_3,1) + (C_b,2×S_3,2) + (C_b,3×S_3,3) - C_j,5 = (M×0) + (M×0) + (0×1) - (0) = 0
• Z₆ = (C_b,1×A_1,1) + (C_b,2×A_1,2) + (C_b,3×A_1,3) - C_j,6 = (M×1) + (M×0) + (0×0) - (M) = 0
• Z₇ = (C_b,1×A_2,1) + (C_b,2×A_2,2) + (C_b,3×A_2,3) - C_j,7 = (M×0) + (M×1) + (0×0) - (M) = 0
• Z₈ = (C_b,1×R₁) + (C_b,2×R₂) + (C_b,3×R₃) = (M×2) + (M×1) + (0×3) = 3M

b) Optimality Condition (Incoming Variable):

In the reduced cost vector (Z) we have positive values, so we must select the highest value for the pivot column (minimization).

In the vector Z (excluding the last value), we have the following numbers: [-1, 2M + 2, -M, -M, 0, 0, 0]. The highest value is = 2M + 2 which corresponds to the X₂ variable. This variable will enter the base and its values in the table will form our pivot column.

Note: To check the chosen value, simply replace the variable M by a large number (e.g. M = 1000000) in the vector of reduced costs.

d) Feasibility Condition (Outgoing Variable):

The feasibility condition will be verified by dividing the values of column R by the pivot column X₂. To process the division, the denominator must be strictly positive (If it's negative or zero, it'll display N/A = Not applicable). The lowest value will define the variable that will exit from the base:

• Row A₁ → R₁ / X_2,1 = 2 / 1 = 2
• Row A₂ → R₂ / X_2,2 = 1 / 1 = 1 (The Lowest Value)
• Row S₃ → R₃ / X_2,3 = 3 / 1 = 3

The lowest value corresponds to the A₂ row. This variable will come from the base. The pivot element corresponds to the value that crosses the X₂ column and the A₂ row = 1.