A furniture manufacturing company manufactures dining room tables and chairs. A table takes 8 hours to assemble and 2 hours to finish. A chair takes 2 hours to assemble and 1 hour to finish. The maximum number of labor-hours per day is 400 for the assembly process and 120 for the finishing process. If the profit on a table is $90 and the profit on a chair is $25, how many tables and chairs should be made each day to maximize the profit (assuming that all of the tables and chairs can be sold)?
Let x1 represent the number of tables and x2 the number of chairs. For the assembly process, we have:
x1 tables at 8 hours/table is 8x1 hours x2 chairs at 2 hours/chair is 2x2 hours 8x1 + 2x2 ≤ 400
For the finishing process, we have:
x1 tables at 2 hours/table is 2x1 hours x2 chairs at 1 hour/chair is x2 hours 2x2 + x2 ≤ 120
For the profit, we have:
x1 tables at $90/table is 90x1 dollars x2 chairs at $25/chair is 25x2 dollars P = 90x1 + 25x2
Putting it all together, we obtain the following mathematical model.
8x1 + 2x2 ≤ 400 (assembly) 2x1 + x2 ≤ 120 (finishing) P = 90x1 + 25x2 (profit) x1, x2 ≥ 0 Maximize P
Introducing slack variables and rewriting the objective function leads to this mathematical model:
8x1 + 2x2 + s1 = 400 (assembly) 2x1 + x2 + s2 = 120 (finishing) -90x1 - 25x2 + P = 0 (profit) x1, x2 ,s1, s2 ≥ 0 Maximize P
We can use an augmented matrix to represent the alternate mathematical model. The augmented matrix is indicated by the shaded regions in the table below. The column and row headings help us interpret the matrix. Basic variables correspond to columns in which there is only one nonzero value (typically a value of one). The basic variables have these nonzero values in different rows. The basic variables are listed in the first column of the table.
| Basic Variables | x1 | x2 | s1 | s2 | P | |
| s1 | 8 | 2 | 1 | 0 | 0 | 400 |
| s2 | 2 | 1 | 0 | 1 | 0 | 120 |
| P | -90 | -25 | 0 | 0 | 1 | 0 |
This tableaux corresponds to the basic solution: x1 = 0, x2 = 0, s1 = 400, and s2 = 120. For this basic solution, P = 0. I will display the basic variables in bold to make it a little easier to pick them out.
The explanation below focuses on the Simplex algorithm. You can use your TI-83 calculator to perform the row operations.
Identify the column with the most negative value in the bottom row. The variable that corresponds to this pivot column will become a basic variable. It is called an entering variable because it is entering the set of basic variables. In this example, x1 is the entering variable. Within the context of the original problem, making a table is more profitable than making a chair so the number of tables (x1) has the greatest impact when it comes to maximizing the profit.
| Basic Variables | x1 | x2 | s1 | s2 | P | |
| s1 | 8 | 2 | 1 | 0 | 0 | 400 |
| s2 | 2 | 1 | 0 | 1 | 0 | 120 |
| P | -90 | -25 | 0 | 0 | 1 | 0 |
Divide each value (except the last) in the right-most column by the corresponding value in the pivot column. If the value in the pivot column is negative or zero, skip that row. Identify the row with the smallest quotient. The variable that corresponds to this pivot row will become a non-basic variable. It is called the exiting variable because it is leaving the set of basic variables. The element at the intersection of the pivot column and the pivot row is the pivot element. The exiting variable in this example is s1 and the pivot element has a value of 8:
| Basic Variables | x1 | x2 | s1 | s2 | P | Quotient | |
| s1 | 8 | 2 | 1 | 0 | 0 | 400 | 400 / 8 = 50 |
| s2 | 2 | 1 | 0 | 1 | 0 | 120 | 120 / 2 = 60 |
| P | -90 | -25 | 0 | 0 | 1 | 0 |
Perform row operations until the pivot element has a value of 1 and the remaining values in the pivot column are 0.
| Basic Variables | x1 | x2 | s1 | s2 | P | Operation | |
| s1 | 8 | 2 | 1 | 0 | 0 | 400 | R1 = R1 / 8 |
| s2 | 2 | 1 | 0 | 1 | 0 | 120 | |
| P | -90 | -25 | 0 | 0 | 1 | 0 |
yields
| Basic Variables | x1 | x2 | s1 | s2 | P | Operation | |
| s1 | 1 | 1/4 | 1/8 | 0 | 0 | 50 | |
| s2 | 2 | 1 | 0 | 1 | 0 | 120 | R2 = R2 - 2 * R1 |
| P | -90 | -25 | 0 | 0 | 1 | 0 |
yields
| Basic Variables | x1 | x2 | s1 | s2 | P | Operation | |
| s1 | 1 | 1/4 | 1/8 | 0 | 0 | 50 | |
| s2 | 0 | 1/2 | -1/4 | 1 | 0 | 20 | |
| P | -90 | -25 | 0 | 0 | 1 | 0 | R3 = R3 + 90 * R1 |
yields
| Basic Variables | x1 | x2 | s1 | s2 | P | |
| x1 | 1 | 1/4 | 1/8 | 0 | 0 | 50 |
| s2 | 0 | 1/2 | -1/4 | 1 | 0 | 20 |
| P | 0 | -5/2 | 45/4 | 0 | 1 | 4500 |
Notice that the first row now corresponds to the entering
basic variable x1 rather than the exiting variable s1.
Setting the non-basic variables (x2 and s1) to zero and
solving for x1 and s2 yields the basic solution: x1
= 50, x2 = 0, s1 = 0, and s2 = 20 for which
P =
4500.
Now, repeat this whole process again. The pivot column corresponds to x2 (the entering variable) because that column has the most negative value in the bottom row.
| Basic Variables | x1 | x2 | s1 | s2 | P | |
| x1 | 1 | 1/4 | 1/8 | 0 | 0 | 50 |
| s2 | 0 | 1/2 | -1/4 | 1 | 0 | 20 |
| P | 0 | -5/2 | 45/4 | 0 | 1 | 4500 |
The pivot row is the row corresponding to s2 (the exiting variable) and the value of the pivot element is 1/2.
| Basic Variables | x1 | x2 | s1 | s2 | P | Quotients | |
| x1 | 1 | 1/4 | 1/8 | 0 | 0 | 50 | 50 / (1/4) = 200 |
| s2 | 0 | 1/2 | -1/4 | 1 | 0 | 20 | 20 / (1/2) = 40 |
| P | 0 | -5/2 | 45/4 | 0 | 1 | 4500 |
Perform row operations that result in the pivot element having a value of 1 and all other elements in the pivot column having a value of 0.
| Basic Variables | x1 | x2 | s1 | s2 | P | Operation | |
| x1 | 1 | 1/4 | 1/8 | 0 | 0 | 50 | |
| s2 | 0 | 1/2 | -1/4 | 1 | 0 | 20 | R2 = 2 * R2 |
| P | 0 | -5/2 | 45/4 | 0 | 1 | 4500 |
yields
| Basic Variables | x1 | x2 | s1 | s2 | P | Operation | |
| x1 | 1 | 1/4 | 1/8 | 0 | 0 | 50 | R1 = R1 + (-1/4) * R2 |
| s2 | 0 | 1 | -1/2 | 2 | 0 | 40 | |
| P | 0 | -5/2 | 45/4 | 0 | 1 | 4500 |
yields
| Basic Variables | x1 | x2 | s1 | s2 | P | Operation | |
| x1 | 1 | 0 | 1/4 | -1/2 | 0 | 40 | |
| s2 | 0 | 1 | -1/2 | 2 | 0 | 40 | |
| P | 0 | -5/2 | 45/4 | 0 | 1 | 4500 | R3 = R3 + (5/2) * R2 |
yields
| Basic Variables | x1 | x2 | s1 | s2 | P | |
| x1 | 1 | 0 | 1/4 | -1/2 | 0 | 40 |
| x2 | 0 | 1 | -1/2 | 2 | 0 | 40 |
| P | 0 | 0 | 10 | 5 | 1 | 4600 |
Notice that in the second row, x2 has become the
basic variable. Letting the non-basic variables (s1 and s2)
equal zero and solving for x1 and x2 leads to the basic
solution: x1 = 40,
x2 = 40, s1 = 0, and s2
= 0. For this basic solution, P = 4600.
Since there are no more negative values in the bottom row, the process terminates. We have found the maximum profit of $4,600 which occurs when we make 40 tables and 40 chairs. This production schedule fully utilizes both the assembly department and the finishing department because the slack variables for both have a value of 0.