# Solved Exercise of Minimization of 2 variables with the 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} - Subject to the following constraints
- X
_{1}+ X_{2}≥ 2 - -X
_{1}+ X_{2}≥ 1 - 0X
_{1}+ X_{2}≤ 3

X

_{1}, X_{2}≥ 0- X
- Description
**Solved Exercise of Minimization of 2 variables with the 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 “**≥**” (greatest equal), therefore the excess variable**S**will be subtracted and the artificial variable_{1}**A**will be added. In the initial matrix,_{1}**A**will be in the base._{1}**Constraint 2:**It has sign “**≥**” (greatest equal), therefore the excess variable**S**will be subtracted and the artificial variable_{2}**A**will be added. In the initial matrix,_{2}**A**will be in the base._{2}**Constraint 3:**It has sign “**≤**” (least equal), therefore the slack variable**S**. This variable will be placed at the base in the initial matrix._{3}

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} + 0S_{1} + 0S_{2} + 0S_{3} + MA_{1} + MA_{2}

Subject to:

- X
_{1}+ X_{2}- S_{1}+ 0S_{2}+ 0S_{3}+ A_{1}+ 0A_{2}= 2 - -X
_{1}+ X_{2}+ 0S_{1}- S_{2}+ 0S_{3}+ 0A_{1}+ A_{2}= 1 - 0X
_{1}+ X_{2}+ 0S_{1}+ 0S_{2}+ S_{3}+ 0A_{1}+ 0A_{2}= 3

### Initial Matrix

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

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

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

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

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

0 | S_{3} | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 3 |

Z | -1 | 2M + 2 | -M | -M | 0 | 0 | 0 | 3M |

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

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

_{2}**A**row =

_{2}**1**.

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

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

_{2}**1**

## 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.