Minimization Exercise - John works in two storesExample of the Simplex Method - Two-Phase

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 “≤” (least equal), therefore the slack variable S₂. This variable will be placed at the base in the initial matrix.
• Constraint 3: 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 4: It has sign “≤” (least equal), therefore the slack variable S₄. This variable will be placed at the base in the initial matrix.
• Constraint 5: 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.

Since the problem has artificial variables, the two-phase method will be used. In the first phase, the objective function will be modified to minimize the sum of the artificial variables.

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 Phase One

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_b,4×X_1,4) + (C_b,5×X_1,5) - C_j,1 = (1×1) + (0×1) + (1×1) + (0×0) + (1×0) - (0) = 2
• Z₂ = (C_b,1×X_2,1) + (C_b,2×X_2,2) + (C_b,3×X_2,3) + (C_b,4×X_2,4) + (C_b,5×X_2,5) - C_j,2 = (1×1) + (0×0) + (1×0) + (0×1) + (1×1) - (0) = 2
• Z₃ = (C_b,1×S_1,1) + (C_b,2×S_1,2) + (C_b,3×S_1,3) + (C_b,4×S_1,4) + (C_b,5×S_1,5) - C_j,3 = (1×-1) + (0×0) + (1×0) + (0×0) + (1×0) - (0) = -1
• Z₄ = (C_b,1×S_2,1) + (C_b,2×S_2,2) + (C_b,3×S_2,3) + (C_b,4×S_2,4) + (C_b,5×S_2,5) - C_j,4 = (1×0) + (0×1) + (1×0) + (0×0) + (1×0) - (0) = 0
• Z₅ = (C_b,1×S_3,1) + (C_b,2×S_3,2) + (C_b,3×S_3,3) + (C_b,4×S_3,4) + (C_b,5×S_3,5) - C_j,5 = (1×0) + (0×0) + (1×-1) + (0×0) + (1×0) - (0) = -1
• Z₆ = (C_b,1×S_4,1) + (C_b,2×S_4,2) + (C_b,3×S_4,3) + (C_b,4×S_4,4) + (C_b,5×S_4,5) - C_j,6 = (1×0) + (0×0) + (1×0) + (0×1) + (1×0) - (0) = 0
• Z₇ = (C_b,1×S_5,1) + (C_b,2×S_5,2) + (C_b,3×S_5,3) + (C_b,4×S_5,4) + (C_b,5×S_5,5) - C_j,7 = (1×0) + (0×0) + (1×0) + (0×0) + (1×-1) - (0) = -1
• Z₈ = (C_b,1×A_1,1) + (C_b,2×A_1,2) + (C_b,3×A_1,3) + (C_b,4×A_1,4) + (C_b,5×A_1,5) - C_j,8 = (1×1) + (0×0) + (1×0) + (0×0) + (1×0) - (1) = 0
• Z₉ = (C_b,1×A_2,1) + (C_b,2×A_2,2) + (C_b,3×A_2,3) + (C_b,4×A_2,4) + (C_b,5×A_2,5) - C_j,9 = (1×0) + (0×0) + (1×1) + (0×0) + (1×0) - (1) = 0
• Z₁₀ = (C_b,1×A_3,1) + (C_b,2×A_3,2) + (C_b,3×A_3,3) + (C_b,4×A_3,4) + (C_b,5×A_3,5) - C_j,10 = (1×0) + (0×0) + (1×0) + (0×0) + (1×1) - (1) = 0
• Z₁₁ = (C_b,1×R₁) + (C_b,2×R₂) + (C_b,3×R₃) + (C_b,4×R₄) + (C_b,5×R₅) = (1×20) + (0×12) + (1×5) + (0×10) + (1×6) = 31

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: [2, 2, -1, 0, -1, 0, -1, 0, 0, 0]. The highest value is = 2 which corresponds to the X₁ variable. This variable will enter the base and its values in the table will form our pivot column.

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_1,1 = 20 / 1 = 20
• Row S₂ → R₂ / X_1,2 = 12 / 1 = 12
• Row A₂ → R₃ / X_1,3 = 5 / 1 = 5 (The Lowest Value)
• Row S₄ → R₄ / X_1,4 = 10 / 0 = NA
• Row A₃ → R₅ / X_1,5 = 6 / 0 = NA

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.