# Solved exercise of Minimization of three variables with artificial in the base with zero value. Big M MethodExample of Linear Programming - Big M Method

### Problem Data

We want to Minimize the following problem:

Objective Function
Z = -X1 + 2X2 - X3
Subject to the following constraints
• X1 + X2 + X3 = 6
• -X1 + X2 + 2X3 = 4
• 0X1 + 2X2 + 3X3 = 10

X1, X2 X3 ≥ 0

Description
Solved exercise of Minimization of three variables with artificial in the base with zero value. Big M MethodSolve the linear programming problem shown above using the Big M method.

## Solution

To solve the problem, the iterations of the simplex method will be performed until the optimal solution is found.

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 “=” (equal), therefore the artificial variable A1. This variable will be placed at the base in the initial matrix.
• Constraint 2: It has sign “=” (equal), therefore the artificial variable A2. This variable will be placed at the base in the initial matrix.
• Constraint 3: It has sign “=” (equal), therefore the artificial variable A3. This variable will be placed at the base in the initial matrix.

Since the problem has artificial variables, the Big M method will be used. As the problem is a minimization problem, the artificial variables will be added to the objective function multiplied by a very large number (represented by the letter M) in this way the simplex algorithm will penalize and eliminate them from the base.

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

Objective Function:

Minimize Z = -X1 + 2X2 - X3 + MA1 + MA2 + MA3

Subject to:

• X1 + X2 + X3 + A1 + 0A2 + 0A3 = 6
• -X1 + X2 + 2X3 + 0A1 + A2 + 0A3 = 4
• 0X1 + 2X2 + 3X3 + 0A1 + 0A2 + A3 = 10

### Initial Matrix

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

Table 1 Cj Cb Base X1 X2 X3 A1 -1 2 -1 M M M M 1 1 1 1 0 0 6 M -1 1 2 0 1 0 4 M 0 2 3 0 0 1 10 1 4M − 2 6M + 1 0 0 0 20M

a) Reduced Cost Vector Calculation (Z):

The values recorded in row Z were obtained as follows:

• Z1 = (Cb,1×X1,1) + (Cb,2×X1,2) + (Cb,3×X1,3) - Cj,1 = (M×1) + (M×-1) + (M×0) - (-1) = 1
• Z2 = (Cb,1×X2,1) + (Cb,2×X2,2) + (Cb,3×X2,3) - Cj,2 = (M×1) + (M×1) + (M×2) - (2) = 4M − 2
• Z3 = (Cb,1×X3,1) + (Cb,2×X3,2) + (Cb,3×X3,3) - Cj,3 = (M×1) + (M×2) + (M×3) - (-1) = 6M + 1
• Z4 = (Cb,1×A1,1) + (Cb,2×A1,2) + (Cb,3×A1,3) - Cj,4 = (M×1) + (M×0) + (M×0) - (M) = 0
• Z5 = (Cb,1×A2,1) + (Cb,2×A2,2) + (Cb,3×A2,3) - Cj,5 = (M×0) + (M×1) + (M×0) - (M) = 0
• Z6 = (Cb,1×A3,1) + (Cb,2×A3,2) + (Cb,3×A3,3) - Cj,6 = (M×0) + (M×0) + (M×1) - (M) = 0
• Z7 = (Cb,1×R1) + (Cb,2×R2) + (Cb,3×R3) = (M×6) + (M×4) + (M×10) = 20M

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, 4M − 2, 6M + 1, 0, 0, 0]. The highest value is = 6M + 1 which corresponds to the X3 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 X3. 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 A1 → R1 / X3,1 = 6 / 1 = 6
• Row A2 → R2 / X3,2 = 4 / 2 = 2 (The Lowest Value)
• Row A3 → R3 / X3,3 = 10 / 3 = 3.333

The lowest value corresponds to the A2 row. This variable will come from the base. The pivot element corresponds to the value that crosses the X3 column and the A2 row = 2.

Enter the variable X3 and the variable A2 leaves the base. The pivot element is 2

## Learn with step-by-step explanations

At PM Calculators we strive to help you overcome those tricky subjects in an easier way.