# 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 = -X
_{1}+ 2X_{2}- X_{3} - Subject to the following constraints
- X
_{1}+ X_{2}+ X_{3}= 6 - -X
_{1}+ X_{2}+ 2X_{3}= 4 - 0X
_{1}+ 2X_{2}+ 3X_{3}= 10

X

_{1}, X_{2}X_{3}≥ 0- X
- Description
**Solved exercise of Minimization of three variables with artificial in the base with zero value. Big M Method**Solve 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**A**. This variable will be placed at the base in the initial matrix._{1}**Constraint 2:**It has sign “**=**” (equal), therefore the artificial variable**A**. This variable will be placed at the base in the initial matrix._{2}**Constraint 3:**It has sign “**=**” (equal), therefore the artificial variable**A**. This variable will be placed at the base in the initial matrix._{3}

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 = -X_{1} + 2X_{2} - X_{3} + MA_{1} + MA_{2} + MA_{3}

Subject to:

- X
_{1}+ X_{2}+ X_{3}+ A_{1}+ 0A_{2}+ 0A_{3}= 6 - -X
_{1}+ X_{2}+ 2X_{3}+ 0A_{1}+ A_{2}+ 0A_{3}= 4 - 0X
_{1}+ 2X_{2}+ 3X_{3}+ 0A_{1}+ 0A_{2}+ A_{3}= 10

### Initial Matrix

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

Table 1 | C_{j} | -1 | 2 | -1 | M | M | M | |
---|---|---|---|---|---|---|---|---|

C_{b} | Base | X_{1} | X_{2} | X_{3} | A_{1} | A_{2} | A_{3} | R_{} |

M | A_{1} | 1 | 1 | 1 | 1 | 0 | 0 | 6 |

M | A_{2} | -1 | 1 | 2 | 0 | 1 | 0 | 4 |

M | A_{3} | 0 | 2 | 3 | 0 | 0 | 1 | 10 |

Z | 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:

- Z
_{1}= (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) + (M×0) - (-1) = 1 - Z
_{2}= (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) + (M×2) - (2) = 4M − 2 - Z
_{3}= (C_{b,1}×X_{3,1}) + (C_{b,2}×X_{3,2}) + (C_{b,3}×X_{3,3}) - C_{j,3}= (M×1) + (M×2) + (M×3) - (-1) = 6M + 1 - Z
_{4}= (C_{b,1}×A_{1,1}) + (C_{b,2}×A_{1,2}) + (C_{b,3}×A_{1,3}) - C_{j,4}= (M×1) + (M×0) + (M×0) - (M) = 0 - Z
_{5}= (C_{b,1}×A_{2,1}) + (C_{b,2}×A_{2,2}) + (C_{b,3}×A_{2,3}) - C_{j,5}= (M×0) + (M×1) + (M×0) - (M) = 0 - Z
_{6}= (C_{b,1}×A_{3,1}) + (C_{b,2}×A_{3,2}) + (C_{b,3}×A_{3,3}) - C_{j,6}= (M×0) + (M×0) + (M×1) - (M) = 0 - Z
_{7}= (C_{b,1}×R_{1}) + (C_{b,2}×R_{2}) + (C_{b,3}×R_{3}) = (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 **X _{3}** 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 _{3}**. 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_{1}_{1}/ X_{3,1}= 6 / 1 = 6**Row A**→ R_{2}_{2}/ X_{3,2}= 4 / 2 =**2 (The Lowest Value)****Row A**→ R_{3}_{3}/ X_{3,3}= 10 / 3 = 3.333

The **lowest value** corresponds to the **A _{2}** row. This variable will come from the base. The pivot element corresponds to the value that crosses the

**X**column and the

_{3}**A**row =

_{2}**2**.

Enter the variable **X _{3}** and the variable

**A**leaves the base. The pivot element is

_{2}**2**

## Learn with step-by-step explanations

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

### Membership

With access to our membership you will have access to 13 applications to learn projects, linear programming, statistics, among others.

#### What calculators are included?

Critical Path PERT and CPM

Linear Programming Methods

Normal Distribution

Break-even and more

Purchase our monthly subscription from

Learn more and save with semi-annual, annual and lifetime plans.