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

### Problem Data

We want to Minimize the following problem:

- Objective Function
- Z = 8X
_{1}+ 6X_{2} - Subject to the following constraints
- X
_{1}+ X_{2}≥ 20 - X
_{1}+ 0X_{2}≤ 12 - X
_{1}+ 0X_{2}≥ 5 - 0X
_{1}+ X_{2}≤ 10 - 0X
_{1}+ X_{2}≥ 6

X

_{1}, X_{2}≥ 0- X
- Description
**Minimization Exercise - John works in two stores**John must work at least 20 hours a week to supplement his income while attending school. He has the opportunity to work in two retail stores. In store 1, he can work between 5 and 12 hours a week, and in store 2, he is allowed between 6 and 10 hours. Both stores pay the same hourly wage. In deciding how many hours to work in each store, John wants to base his decision on work stress. Based on interviews with present employees, John estimates that, on an ascending scale of 1 to 10, the stress factors are 8 and 6 at stores 1 and 2, respectively. Because stress mounts by the hour, he assumes that the total stress for each store at the end of the week is proportional to the number of hours he works in the store. How many hours should John work in each store?

## 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 “**≤**” (least equal), therefore the slack variable**S**. This variable will be placed at the base in the initial matrix._{2}**Constraint 3:**It has sign “**≥**” (greatest equal), therefore the excess variable**S**will be subtracted and the artificial variable_{3}**A**will be added. In the initial matrix,_{2}**A**will be in the base._{2}**Constraint 4:**It has sign “**≤**” (least equal), therefore the slack variable**S**. This variable will be placed at the base in the initial matrix._{4}**Constraint 5:**It has sign “**≥**” (greatest equal), therefore the excess variable**S**will be subtracted and the artificial variable_{5}**A**will be added. In the initial matrix,_{3}**A**will be in the base._{3}

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:

Objective Function:

Minimize Z = 0X_{1} + 0X_{2} + 0S_{1} + 0S_{2} + 0S_{3} + 0S_{4} + 0S_{5} + A_{1} + A_{2} + A_{3}

Subject to:

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

### Initial Matrix Phase One

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

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

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

1 | A_{1} | 1 | 1 | -1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 20 |

0 | S_{2} | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 12 |

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

0 | S_{4} | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 10 |

1 | A_{3} | 0 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 6 |

Z | 2 | 2 | -1 | 0 | -1 | 0 | -1 | 0 | 0 | 0 | 31 |

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

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

_{1}**A**row =

_{2}**1**.

Enter the variable **X _{1}** 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.