The **Big M Method** is a widely used approach to solving linear programming exercises using the simplex algorithm. Our post presents you with the **5 Big M Method examples**.

We have included maximization and minimization problems as well as the step-by-step to reach the final solution. It is important to mention that all solutions were obtained using our premium version of the Big M method online calculator.

## Example 1:

**Maximize** Z = 2X_{1} + 5X_{2} + 3X_{3}

subject to

X_{1} + 2X_{2} – X_{3} β€ 7

-X_{1} + X_{2} – 2X_{3} β€ 5

X_{1} + 4X_{2} + 3X_{3} β₯ 1

2X_{1} – X_{2} + 4X_{3} = 6

X_{1}, X_{2}, X_{3} β₯ 0

### Solution 1:

The problem will be adapted to the standard linear programming model, adding the slack, surplus and / or artificial variables in each of the constraints:

**Constraint 1:**It has a sign “β€” (less than or equal) so the slack variable will be added S_{1}.**Constraint 2:**It has a sign “β€” (less than or equal) so the slack variable will be added S_{2}.**Constraint 3:**It has a sign “β₯” (greater than or equal) so the surplus variable S_{3}will be subtracted and the artificial variable A_{1}will be added.**Constraint 4:**It has an “=” sign (equal) so the artificial variable A_{2}will be added.

The problem has artificial variables so we will use the **Big M method**. As the problem is one of **maximization, the artificial variables will be subtracted from the objective function multiplied by a very large number** (represented by the letter **M**) in this way the simplex algorithm will penalize them and eliminate them from the base.

The problem is shown below in standard form. The coefficient 0 (zero) will be placed where it corresponds to create our table:

#### Objective Function:

Maximize: Z = 2X_{1} + 5X_{2} + 3X_{3} + 0S_{1} + 0S_{2} + 0S_{3} – MA_{1} – MA_{2}

#### Subject to:

1X_{1} + 2X_{2} – 1X_{3} + 1S_{1} + 0S_{2} + 0S_{3} + 0A_{1} + 0A_{2} = 7

-1X_{1} + 1X_{2} – 2X_{3} + 0S_{1} + 1S_{2} + 0S_{3} + 0A_{1} + 0A_{2} = 5

1X_{1} + 4X_{2} + 3X_{3} + 0S_{1} + 0S_{2} – 1S_{3} + 1A_{1} + 0A_{2} = 1

2X_{1} – 1X_{2} + 4X_{3} + 0S_{1} + 0S_{2} + 0S_{3} + 0A_{1} + 1A_{2} = 6

X_{1}, X_{2}, X_{3}, S_{1}, S_{2}, S_{3}, A_{1}, A_{2} β₯ 0

The letters in the tables correspond to:

**C**Cost vector. Contains the coefficients of the objective function variables._{j}:**C**Coefficients of the variables that make up the solution vector._{b}:**Base:**Variables forming the solution vector.**Z:**In this row you will find the values of the reduced cost vector. It is calculated by multiplying the solution vector by the constraint coefficients and subtracting the vector of costs.**X**Each column displays the coefficients of the corresponding variable._{n}, S_{n}and A_{n}:**R:**This column contains the independent term of each equation.- An additional numerical subscript will be added to the equations to identify their position in the table. Example:
**X**Coefficient of X_{1,2}:_{1}in row 2. For**C**and_{j}**Z**the subscripts will indicate their position in the column. Example:**C**I would indicate the coefficient of_{j,3}:**C**in column 3._{j}

### Iteration 1

For this table, the value of **row Z** will be calculated as follows:

Z_{1} = (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_{j1} = (0*1) + (0*-1) + (-M*1) + (-M*2) – (2) = -3M-2

Z_{2} = (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_{j2} = (0*2) + (0*1) + (-M*4) + (-M*-1) – (5) = -3M-5

Z_{3} = (C_{b,1}*X_{3}_{,1}) + (C_{b,2}*X_{3}_{,2}) + (C_{b,3}*X_{3}_{,3}) + (C_{b,4}*X_{3}_{,4}) – C_{j3} = (0*-1) + (0*-2) + (-M*3) + (-M*4) – (3) = -7M-3

Z_{4} = (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_{j4} = (0*1) + (0*0) + (-M*0) + (-M*0) – (0) = 0

Z_{5} = (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_{j5} = (0*0) + (0*1) + (-M*0) + (-M*0) – (0) = 0

Z_{6} = (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_{j6} = (0*0) + (0*0) + (-M*-1) + (-M*0) – (0) = M

Z_{7} = (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_{j7} = (0*0) + (0*0) + (-M*1) + (-M*0) – (-M) = 0

Z_{8} = (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_{j8} = (0*0) + (0*0) + (-M*0) + (-M*1) – (-M) = 0

Z_{9} = (C_{b,1}*R_{,1}) + (C_{b,2}*R_{,2}) + (C_{b,3}*R_{,3}) + (C_{b,4}*R_{,4}) = (0*7) + (0*5) + (-M*1) + (-M*6) = -7M

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

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

0 | S_{1} |
1 | 2 | -1 | 1 | 0 | 0 | 0 | 0 | 7 |

0 | S_{2} |
-1 | 1 | -2 | 0 | 1 | 0 | 0 | 0 | 5 |

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

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

Z | -3M-2 | -3M-5 | -7M-3 | 0 | 0 | M | 0 | 0 | -7M |

**reduced cost vector (Z)**we have negative values, so we must select the

**most negative**one for the pivot column (maximization).

**[-3M-2, -3M-5, -7M-3, 0, 0, M, 0, 0]**. The

**most negative**is =

**-7M-3**which corresponds to the

**X**variable. This variable will enter the base and its values in the table will form our pivot column.

_{3}If it is not clear to you why **-7M-3** is the **most negative value**, you can replace the variable M by high number as 1000000 in the vector of reduced costs and re-evaluate the results.

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 S _{1}** β R

_{1}/ X

_{3}

_{,1}= 7 / -1 =

**N/A**

**Row S**β R

_{2}_{2}/ X

_{3}

_{,2}= 5 / -2 =

**N/A**

**Row A**β R

_{1}_{3}/ X

_{3}

_{,3}= 1 / 3 =

**0.(3) (The Lowest Value)**

**Row A**β R

_{2}_{4}/ X

_{3}

_{,4}= 6 / 4 =

**1.5**

The numbers in parentheses represent repeating decimals. Example: 1.(3) = 1.33333…

The **lowest value** corresponds to the **A _{1}** 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 =

_{1}**3**.

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

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

_{1}**3**

### Iteration 2

For this table, the value of **row Z** will be calculated as follows:

Z_{1} = (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_{j1} = (0*4/3) + (0*-1/3) + (3*1/3) + (-M*2/3) – (2) = -2/3M-1

Z_{2} = (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_{j2} = (0*10/3) + (0*11/3) + (3*4/3) + (-M*-19/3) – (5) = 19/3M-1

Z_{3} = (C_{b,1}*X_{3}_{,1}) + (C_{b,2}*X_{3}_{,2}) + (C_{b,3}*X_{3}_{,3}) + (C_{b,4}*X_{3}_{,4}) – C_{j3} = (0*0) + (0*0) + (3*1) + (-M*0) – (3) = 0

Z_{4} = (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_{j4} = (0*1) + (0*0) + (3*0) + (-M*0) – (0) = 0

Z_{5} = (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_{j5} = (0*0) + (0*1) + (3*0) + (-M*0) – (0) = 0

Z_{6} = (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_{j6} = (0*-1/3) + (0*-2/3) + (3*-1/3) + (-M*4/3) – (0) = -4/3M-1

Z_{7} = (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_{j7} = (0*1/3) + (0*2/3) + (3*1/3) + (-M*-4/3) – (-M) = 7/3M+1

Z_{8} = (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_{j8} = (0*0) + (0*0) + (3*0) + (-M*1) – (-M) = 0

Z_{9} = (C_{b,1}*R_{,1}) + (C_{b,2}*R_{,2}) + (C_{b,3}*R_{,3}) + (C_{b,4}*R_{,4}) = (0*22/3) + (0*17/3) + (3*1/3) + (-M*14/3) = -14/3M+1

Each value in the table will be iterated considering the following:

- New Value Pivot Row = Current Value Pivot Row / Pivot Element
- New Value Other Rows = Current Value – (Pivot Column Row Element * New Value Pivot Row)

Pivot row calculations (Row NΒ° 3):

Current Value Pivot Row | 1 | 4 | 3 | 0 | 0 | -1 | 1 | 0 | 1 |
---|---|---|---|---|---|---|---|---|---|

Pivot Element | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |

New Value Pivot Row | 1 / 3 = 1/3 | 4 / 3 = 4/3 | 3 / 3 = 1 | 0 / 3 = 0 | 0 / 3 = 0 | -1 / 3 = -1/3 | 1 / 3 = 1/3 | 0 / 3 = 0 | 1 / 3 = 1/3 |

Next, we'll calculate the new values for all other rows of the table:

Row 1:

Current Value | 1 | 2 | -1 | 1 | 0 | 0 | 0 | 0 | 7 |
---|---|---|---|---|---|---|---|---|---|

Pivot Column Row Element | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |

New Value Pivot Row | 1/3 | 4/3 | 1 | 0 | 0 | -1/3 | 1/3 | 0 | 1/3 |

New Value | 1 – (-1Γ1/3) = 4/3 | 2 – (-1Γ4/3) = 10/3 | -1 – (-1Γ1) = 0 | 1 – (-1Γ0) = 1 | 0 – (-1Γ0) = 0 | 0 – (-1Γ-1/3) = -1/3 | 0 – (-1Γ1/3) = 1/3 | 0 – (-1Γ0) = 0 | 7 – (-1Γ1/3) = 22/3 |

Row 2:

Current Value | -1 | 1 | -2 | 0 | 1 | 0 | 0 | 0 | 5 |
---|---|---|---|---|---|---|---|---|---|

Pivot Column Row Element | -2 | -2 | -2 | -2 | -2 | -2 | -2 | -2 | -2 |

New Value Pivot Row | 1/3 | 4/3 | 1 | 0 | 0 | -1/3 | 1/3 | 0 | 1/3 |

New Value | -1 – (-2Γ1/3) = -1/3 | 1 – (-2Γ4/3) = 11/3 | -2 – (-2Γ1) = 0 | 0 – (-2Γ0) = 0 | 1 – (-2Γ0) = 1 | 0 – (-2Γ-1/3) = -2/3 | 0 – (-2Γ1/3) = 2/3 | 0 – (-2Γ0) = 0 | 5 – (-2Γ1/3) = 17/3 |

Row 4:

Current Value | 2 | -1 | 4 | 0 | 0 | 0 | 0 | 1 | 6 |
---|---|---|---|---|---|---|---|---|---|

Pivot Column Row Element | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |

New Value Pivot Row | 1/3 | 4/3 | 1 | 0 | 0 | -1/3 | 1/3 | 0 | 1/3 |

New Value | 2 – (4Γ1/3) = 2/3 | -1 – (4Γ4/3) = -19/3 | 4 – (4Γ1) = 0 | 0 – (4Γ0) = 0 | 0 – (4Γ0) = 0 | 0 – (4Γ-1/3) = 4/3 | 0 – (4Γ1/3) = -4/3 | 1 – (4Γ0) = 1 | 6 – (4Γ1/3) = 14/3 |

Table 2 | C_{j} |
2 | 5 | 3 | 0 | 0 | 0 | -M | -M | |
---|---|---|---|---|---|---|---|---|---|---|

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

0 | S_{1} |
4/3 | 10/3 | 0 | 1 | 0 | -1/3 | 1/3 | 0 | 22/3 |

0 | S_{2} |
-1/3 | 11/3 | 0 | 0 | 1 | -2/3 | 2/3 | 0 | 17/3 |

3 | X_{3} |
1/3 | 4/3 | 1 | 0 | 0 | -1/3 | 1/3 | 0 | 1/3 |

-M | A_{2} |
2/3 | -19/3 | 0 | 0 | 0 | 4/3 | -4/3 | 1 | 14/3 |

Z | -2/3M-1 | 19/3M-1 | 0 | 0 | 0 | -4/3M-1 | 7/3M+1 | 0 | -14/3M+1 |

**reduced cost vector (Z)**we have negative values, so we must select the

**most negative**one for the pivot column (maximization).

**[-2/3M-1, 19/3M-1, 0, 0, 0, -4/3M-1, 7/3M+1, 0]**. The

**most negative**is =

**-4/3M-1**which corresponds to the

**S**variable. This variable will enter the base and its values in the table will form our pivot column.

_{3}If it is not clear to you why **-4/3M-1** is the **most negative value**, you can replace the variable M by high number as 1000000 in the vector of reduced costs and re-evaluate the results.

The feasibility condition will be verified by dividing the values of **column R** by the **pivot column S _{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 S _{1}** β R

_{1}/ S

_{3}

_{,1}= 22/3 / -1/3 =

**N/A**

**Row S**β R

_{2}_{2}/ S

_{3}

_{,2}= 17/3 / -2/3 =

**N/A**

**Row X**β R

_{3}_{3}/ S

_{3}

_{,3}= 1/3 / -1/3 =

**N/A**

**Row A**β R

_{2}_{4}/ S

_{3}

_{,4}= 14/3 / 4/3 =

**3.5 (The Lowest Value)**

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

**S**column and the

_{3}**A**row =

_{2}**4/3**.

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

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

_{2}**4/3**

### Iteration 3

For this table, the value of **row Z** will be calculated as follows:

Z_{1} = (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_{j1} = (0*3/2) + (0*0) + (3*1/2) + (0*1/2) – (2) = -1/2

Z_{2} = (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_{j2} = (0*7/4) + (0*1/2) + (3*-1/4) + (0*-19/4) – (5) = -23/4

Z_{3} = (C_{b,1}*X_{3}_{,1}) + (C_{b,2}*X_{3}_{,2}) + (C_{b,3}*X_{3}_{,3}) + (C_{b,4}*X_{3}_{,4}) – C_{j3} = (0*0) + (0*0) + (3*1) + (0*0) – (3) = 0

Z_{4} = (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_{j4} = (0*1) + (0*0) + (3*0) + (0*0) – (0) = 0

Z_{5} = (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_{j5} = (0*0) + (0*1) + (3*0) + (0*0) – (0) = 0

Z_{6} = (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_{j6} = (0*0) + (0*0) + (3*0) + (0*1) – (0) = 0

Z_{7} = (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_{j7} = (0*0) + (0*0) + (3*0) + (0*-1) – (-M) = M

Z_{8} = (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_{j8} = (0*1/4) + (0*1/2) + (3*1/4) + (0*3/4) – (-M) = M+3/4

Z_{9} = (C_{b,1}*R_{,1}) + (C_{b,2}*R_{,2}) + (C_{b,3}*R_{,3}) + (C_{b,4}*R_{,4}) = (0*17/2) + (0*8) + (3*3/2) + (0*7/2) = 9/2

Each value in the table will be iterated considering the following:

- New Value Pivot Row = Current Value Pivot Row / Pivot Element
- New Value Other Rows = Current Value – (Pivot Column Row Element * New Value Pivot Row)

Pivot row calculations (Row NΒ° 4):

Current Value Pivot Row | 2/3 | -19/3 | 0 | 0 | 0 | 4/3 | -4/3 | 1 | 14/3 |
---|---|---|---|---|---|---|---|---|---|

Pivot Element | 4/3 | 4/3 | 4/3 | 4/3 | 4/3 | 4/3 | 4/3 | 4/3 | 4/3 |

New Value Pivot Row | 2/3 / 4/3 = 1/2 | -19/3 / 4/3 = -19/4 | 0 / 4/3 = 0 | 0 / 4/3 = 0 | 0 / 4/3 = 0 | 4/3 / 4/3 = 1 | -4/3 / 4/3 = -1 | 1 / 4/3 = 3/4 | 14/3 / 4/3 = 7/2 |

Next, we'll calculate the new values for all other rows of the table:

Row 1:

Current Value | 4/3 | 10/3 | 0 | 1 | 0 | -1/3 | 1/3 | 0 | 22/3 |
---|---|---|---|---|---|---|---|---|---|

Pivot Column Row Element | -1/3 | -1/3 | -1/3 | -1/3 | -1/3 | -1/3 | -1/3 | -1/3 | -1/3 |

New Value Pivot Row | 1/2 | -19/4 | 0 | 0 | 0 | 1 | -1 | 3/4 | 7/2 |

New Value | 4/3 – (-1/3Γ1/2) = 3/2 | 10/3 – (-1/3Γ-19/4) = 7/4 | 0 – (-1/3Γ0) = 0 | 1 – (-1/3Γ0) = 1 | 0 – (-1/3Γ0) = 0 | -1/3 – (-1/3Γ1) = 0 | 1/3 – (-1/3Γ-1) = 0 | 0 – (-1/3Γ3/4) = 1/4 | 22/3 – (-1/3Γ7/2) = 17/2 |

Row 2:

Current Value | -1/3 | 11/3 | 0 | 0 | 1 | -2/3 | 2/3 | 0 | 17/3 |
---|---|---|---|---|---|---|---|---|---|

Pivot Column Row Element | -2/3 | -2/3 | -2/3 | -2/3 | -2/3 | -2/3 | -2/3 | -2/3 | -2/3 |

New Value Pivot Row | 1/2 | -19/4 | 0 | 0 | 0 | 1 | -1 | 3/4 | 7/2 |

New Value | -1/3 – (-2/3Γ1/2) = 0 | 11/3 – (-2/3Γ-19/4) = 1/2 | 0 – (-2/3Γ0) = 0 | 0 – (-2/3Γ0) = 0 | 1 – (-2/3Γ0) = 1 | -2/3 – (-2/3Γ1) = 0 | 2/3 – (-2/3Γ-1) = 0 | 0 – (-2/3Γ3/4) = 1/2 | 17/3 – (-2/3Γ7/2) = 8 |

Row 3:

Current Value | 1/3 | 4/3 | 1 | 0 | 0 | -1/3 | 1/3 | 0 | 1/3 |
---|---|---|---|---|---|---|---|---|---|

Pivot Column Row Element | -1/3 | -1/3 | -1/3 | -1/3 | -1/3 | -1/3 | -1/3 | -1/3 | -1/3 |

New Value Pivot Row | 1/2 | -19/4 | 0 | 0 | 0 | 1 | -1 | 3/4 | 7/2 |

New Value | 1/3 – (-1/3Γ1/2) = 1/2 | 4/3 – (-1/3Γ-19/4) = -1/4 | 1 – (-1/3Γ0) = 1 | 0 – (-1/3Γ0) = 0 | 0 – (-1/3Γ0) = 0 | -1/3 – (-1/3Γ1) = 0 | 1/3 – (-1/3Γ-1) = 0 | 0 – (-1/3Γ3/4) = 1/4 | 1/3 – (-1/3Γ7/2) = 3/2 |

Table 3 | C_{j} |
2 | 5 | 3 | 0 | 0 | 0 | -M | -M | |
---|---|---|---|---|---|---|---|---|---|---|

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

0 | S_{1} |
3/2 | 7/4 | 0 | 1 | 0 | 0 | 0 | 1/4 | 17/2 |

0 | S_{2} |
0 | 1/2 | 0 | 0 | 1 | 0 | 0 | 1/2 | 8 |

3 | X_{3} |
1/2 | -1/4 | 1 | 0 | 0 | 0 | 0 | 1/4 | 3/2 |

0 | S_{3} |
1/2 | -19/4 | 0 | 0 | 0 | 1 | -1 | 3/4 | 7/2 |

Z | -1/2 | -23/4 | 0 | 0 | 0 | 0 | M | M+3/4 | 9/2 |

**reduced cost vector (Z)**we have negative values, so we must select the

**most negative**one for the pivot column (maximization).

**[-1/2, -23/4, 0, 0, 0, 0, M, M+3/4]**. The

**most negative**is =

**-23/4**which corresponds to the

**X**variable. This variable will enter the base and its values in the table will form our pivot column.

_{2}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 S _{1}** β R

_{1}/ X

_{2}

_{,1}= 17/2 / 7/4 =

**4.(857142) (The Lowest Value)**

**Row S**β R

_{2}_{2}/ X

_{2}

_{,2}= 8 / 1/2 =

**16**

**Row X**β R

_{3}_{3}/ X

_{2}

_{,3}= 3/2 / -1/4 =

**N/A**

**Row S**β R

_{3}_{4}/ X

_{2}

_{,4}= 7/2 / -19/4 =

**N/A**

The numbers in parentheses represent repeating decimals. Example: 1.(3) = 1.33333…

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

**X**column and the

_{2}**S**row =

_{1}**7/4**.

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

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

_{1}**7/4**

### Iteration 4

For this table, the value of **row Z** will be calculated as follows:

Z_{1} = (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_{j1} = (5*6/7) + (0*-3/7) + (3*5/7) + (0*32/7) – (2) = 31/7

Z_{2} = (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_{j2} = (5*1) + (0*0) + (3*0) + (0*0) – (5) = 0

Z_{3} = (C_{b,1}*X_{3}_{,1}) + (C_{b,2}*X_{3}_{,2}) + (C_{b,3}*X_{3}_{,3}) + (C_{b,4}*X_{3}_{,4}) – C_{j3} = (5*0) + (0*0) + (3*1) + (0*0) – (3) = 0

Z_{4} = (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_{j4} = (5*4/7) + (0*-2/7) + (3*1/7) + (0*19/7) – (0) = 23/7

Z_{5} = (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_{j5} = (5*0) + (0*1) + (3*0) + (0*0) – (0) = 0

Z_{6} = (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_{j6} = (5*0) + (0*0) + (3*0) + (0*1) – (0) = 0

Z_{7} = (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_{j7} = (5*0) + (0*0) + (3*0) + (0*-1) – (-M) = M

Z_{8} = (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_{j8} = (5*1/7) + (0*3/7) + (3*2/7) + (0*10/7) – (-M) = M+11/7

Z_{9} = (C_{b,1}*R_{,1}) + (C_{b,2}*R_{,2}) + (C_{b,3}*R_{,3}) + (C_{b,4}*R_{,4}) = (5*34/7) + (0*39/7) + (3*19/7) + (0*186/7) = 227/7

Each value in the table will be iterated considering the following:

- New Value Pivot Row = Current Value Pivot Row / Pivot Element
- New Value Other Rows = Current Value – (Pivot Column Row Element * New Value Pivot Row)

Pivot row calculations (Row NΒ° 1):

Current Value Pivot Row | 3/2 | 7/4 | 0 | 1 | 0 | 0 | 0 | 1/4 | 17/2 |
---|---|---|---|---|---|---|---|---|---|

Pivot Element | 7/4 | 7/4 | 7/4 | 7/4 | 7/4 | 7/4 | 7/4 | 7/4 | 7/4 |

New Value Pivot Row | 3/2 / 7/4 = 6/7 | 7/4 / 7/4 = 1 | 0 / 7/4 = 0 | 1 / 7/4 = 4/7 | 0 / 7/4 = 0 | 0 / 7/4 = 0 | 0 / 7/4 = 0 | 1/4 / 7/4 = 1/7 | 17/2 / 7/4 = 34/7 |

Next, we'll calculate the new values for all other rows of the table:

Row 2:

Current Value | 0 | 1/2 | 0 | 0 | 1 | 0 | 0 | 1/2 | 8 |
---|---|---|---|---|---|---|---|---|---|

Pivot Column Row Element | 1/2 | 1/2 | 1/2 | 1/2 | 1/2 | 1/2 | 1/2 | 1/2 | 1/2 |

New Value Pivot Row | 6/7 | 1 | 0 | 4/7 | 0 | 0 | 0 | 1/7 | 34/7 |

New Value | 0 – (1/2Γ6/7) = -3/7 | 1/2 – (1/2Γ1) = 0 | 0 – (1/2Γ0) = 0 | 0 – (1/2Γ4/7) = -2/7 | 1 – (1/2Γ0) = 1 | 0 – (1/2Γ0) = 0 | 0 – (1/2Γ0) = 0 | 1/2 – (1/2Γ1/7) = 3/7 | 8 – (1/2Γ34/7) = 39/7 |

Row 3:

Current Value | 1/2 | -1/4 | 1 | 0 | 0 | 0 | 0 | 1/4 | 3/2 |
---|---|---|---|---|---|---|---|---|---|

Pivot Column Row Element | -1/4 | -1/4 | -1/4 | -1/4 | -1/4 | -1/4 | -1/4 | -1/4 | -1/4 |

New Value Pivot Row | 6/7 | 1 | 0 | 4/7 | 0 | 0 | 0 | 1/7 | 34/7 |

New Value | 1/2 – (-1/4Γ6/7) = 5/7 | -1/4 – (-1/4Γ1) = 0 | 1 – (-1/4Γ0) = 1 | 0 – (-1/4Γ4/7) = 1/7 | 0 – (-1/4Γ0) = 0 | 0 – (-1/4Γ0) = 0 | 0 – (-1/4Γ0) = 0 | 1/4 – (-1/4Γ1/7) = 2/7 | 3/2 – (-1/4Γ34/7) = 19/7 |

Row 4:

Current Value | 1/2 | -19/4 | 0 | 0 | 0 | 1 | -1 | 3/4 | 7/2 |
---|---|---|---|---|---|---|---|---|---|

Pivot Column Row Element | -19/4 | -19/4 | -19/4 | -19/4 | -19/4 | -19/4 | -19/4 | -19/4 | -19/4 |

New Value Pivot Row | 6/7 | 1 | 0 | 4/7 | 0 | 0 | 0 | 1/7 | 34/7 |

New Value | 1/2 – (-19/4Γ6/7) = 32/7 | -19/4 – (-19/4Γ1) = 0 | 0 – (-19/4Γ0) = 0 | 0 – (-19/4Γ4/7) = 19/7 | 0 – (-19/4Γ0) = 0 | 1 – (-19/4Γ0) = 1 | -1 – (-19/4Γ0) = -1 | 3/4 – (-19/4Γ1/7) = 10/7 | 7/2 – (-19/4Γ34/7) = 186/7 |

Table 4 | C_{j} |
2 | 5 | 3 | 0 | 0 | 0 | -M | -M | |
---|---|---|---|---|---|---|---|---|---|---|

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

5 | X_{2} |
6/7 | 1 | 0 | 4/7 | 0 | 0 | 0 | 1/7 | 34/7 |

0 | S_{2} |
-3/7 | 0 | 0 | -2/7 | 1 | 0 | 0 | 3/7 | 39/7 |

3 | X_{3} |
5/7 | 0 | 1 | 1/7 | 0 | 0 | 0 | 2/7 | 19/7 |

0 | S_{3} |
32/7 | 0 | 0 | 19/7 | 0 | 1 | -1 | 10/7 | 186/7 |

Z | 31/7 | 0 | 0 | 23/7 | 0 | 0 | M | M+11/7 | 227/7 |

**reduced cost vector (Z) = [31/7, 0, 0, 23/7, 0, 0, M, M+11/7]**, this means that we are at the

**optimal point (maximization)**.

The optimal solution is Z = 227/7

X_{1}= 0, X_{2}= 34/7, X_{3}= 19/7, S_{1}= 0, S_{2}= 39/7, S_{3}= 186/7, A_{1}= 0, A_{2}= 0

## Example 1: