4.2 Maximization by the Simplex Method
Learning Objectives
- Identify and set up a linear program in standard maximization form
- Convert inequality constraints to equations using slack variables
- Set up the initial simplex tableau using the objective function and slack equations
- Find the optimal simplex tableau by performing pivoting operations
- Identify the optimal solution from the optimal simplex tableau
Why the Simplex Method?
In the last chapter, we used the geometrical method to solve linear programming problems, but the geometrical approach will not work for problems that have more than two variables. In real life situations, linear programming problems consist of literally thousands of variables and are solved by computers.
Why can't we use graphs for bigger problems? A graph with two variables (\(x\) and \(y\)) is two-dimensional—easy to visualize. Add a third variable (\(z\)), and you need a 3D graph. Add a fourth variable, and you'd need a four-dimensional space, which humans cannot visualize. By the time you have 10 or 100 variables, graphing becomes impossible.
We can solve these problems algebraically, but that will not be very efficient. Suppose we were given a problem with, say, 5 variables and 10 constraints. By choosing all combinations of five equations with five unknowns, we could find all the corner points, test them for feasibility, and come up with the solution, if it exists. But the trouble is that even for a problem with so few variables, we will get more than 250 corner points, and testing each point will be very tedious.
So we need a method that has a systematic algorithm and can be programmed for a computer. The method has to be efficient enough so we wouldn't have to evaluate the objective function at each corner point. We have just such a method, and it is called the simplex method.
History of the Simplex Method
The simplex method was developed during the Second World War by Dr. George Dantzig. His linear programming models helped the Allied forces with transportation and scheduling problems.
In 1979, a Soviet scientist named Leonid Khachian developed a method called the ellipsoid algorithm which was supposed to be revolutionary, but as it turned out it is not any better than the simplex method. In 1984, Narendra Karmarkar, a research scientist at AT&T Bell Laboratories, developed Karmarkar's algorithm which has been proven to be four times faster than the simplex method for certain problems. But the simplex method still works the best for most problems.
The simplex method is like a smart hiker climbing a mountain. Instead of checking every possible path, it always moves uphill (improving the objective function) and never backtracks. It's guaranteed to reach the summit (optimal solution) efficiently.
How the Simplex Method Works
The simplex method uses an approach that is very efficient. It does not compute the value of the objective function at every point; instead, it begins with a corner point of the feasibility region where all the main variables are zero and then systematically moves from corner point to corner point, while improving the value of the objective function at each stage. The process continues until the optimal solution is found.
To learn the simplex method, we try a rather unconventional approach. We first list the algorithm, and then work a problem. We justify the reasoning behind each step during the process. (A thorough mathematical justification is beyond the scope of this course.)
We start out with an example we solved in the last chapter by the graphical method. This will provide us with some insight into the simplex method and at the same time give us the chance to compare a few of the feasible solutions we obtained previously by the graphical method.
But first, we list the algorithm for the simplex method.
The Simplex Algorithm
THE SIMPLEX METHOD
- Set up the problem. That is, write the objective function and the inequality constraints.
- Convert the inequalities into equations. This is done by adding one slack variable for each inequality.
- Construct the initial simplex tableau. Write the objective function as the bottom row.
- The most negative entry in the bottom row identifies the pivot column.
- Calculate the quotients. The smallest quotient identifies a row. The element in the intersection of the column identified in step 4 and the row identified in this step is identified as the pivot element.
- The quotients are computed by dividing the far right column by the identified column in step 4.
- A quotient that is zero, negative, or that has a zero in the denominator, is ignored.
- Perform pivoting to make all other entries in this column zero. This is done the same way as we did with the Gauss-Jordan method.
- When there are no more negative entries in the bottom row, we are finished; otherwise, we start again from step 4.
- Read off your answers. Get the variables using the columns with 1 and 0s. All other variables are zero. The maximum value you are looking for appears in the bottom right-hand corner.
Source: Applied Finite Mathematics 3rd Edition
Now, we use the simplex method to solve Example 1 solved geometrically in section 3.1 (also known as Example 4.2.1).
Problem Statement:
Niki holds two part-time jobs, Job I and Job II. She never wants to work more than a total of 12 hours a week. She has determined that for every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation. If she makes $40 an hour at Job I, and $30 an hour at Job II, how many hours should she work per week at each job to maximize her income?
Example 4.2.1 Solution
In solving this problem, we will follow the algorithm listed above.
STEP 1. Set up the problem
Write the objective function and the constraints.
Note on Notation: Since the simplex method is used for problems that consist of many variables, it is not practical to use the variables \(x\), \(y\), \(z\), etc. We use symbols \(x_1\), \(x_2\), \(x_3\), and so on.
Let \(x_1 =\) The number of hours per week Niki will work at Job I.
and \(x_2 =\) The number of hours per week Niki will work at Job II.
It is customary to choose the variable that is to be maximized as \(Z\).
The problem is formulated the same way as we did in the last chapter.
Maximize \(Z = 40x_{1} + 30x_{2}\)
Subject to: \(x_1 + x_2 \leq 12\)
\[2x_{1} + x_{2} \leq 16\] \[x_{1} \geq 0; \quad x_{2} \geq 0\]STEP 2. Convert the inequalities into equations
This is done by adding one slack variable for each inequality.
For example, to convert the inequality \(x_1 + x_2 \leq 12\) into an equation, we add a non-negative variable \(y_1\), and we get
\[x_1 + x_2 + y_1 = 12\]What is a slack variable? It represents the "unused" or "leftover" amount. If Niki works 10 hours total when she could work up to 12, the slack variable \(y_1 = 2\) represents the 2 unused hours. When we find the optimal solution, slack variables tell us which resources are fully used (slack = 0) and which have leftovers (slack > 0).
Here the variable \(y_1\) picks up the slack, and it represents the amount by which \(x_1 + x_2\) falls short of 12. In this problem, if Niki works fewer than 12 hours, say 10, then \(y_1\) is 2. Later when we read off the final solution from the simplex table, the values of the slack variables will identify the unused amounts.
We rewrite the objective function \(Z = 40x_{1} + 30x_{2}\) as \(-40x_{1} - 30x_{2} + Z = 0\).
After adding the slack variables, our problem reads:
Objective function: \(-40x_1 - 30x_2 + Z = 0\)
Subject to constraints: \(x_1 + x_2 + y_1 = 12\)
\[2x_{1} + x_{2} + y_{2} = 16\] \[x_{1} \geq 0; \quad x_{2} \geq 0\]STEP 3. Construct the initial simplex tableau
Each inequality constraint appears in its own row. (The non-negativity constraints do not appear as rows in the simplex tableau.) Write the objective function as the bottom row.
Now that the inequalities are converted into equations, we can represent the problem into an augmented matrix called the initial simplex tableau as follows.
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(Z\) | C |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 12 |
| 2 | 1 | 0 | 1 | 0 | 16 |
| −40 | −30 | 0 | 0 | 1 | 0 |
Here the vertical line separates the left-hand side of the equations from the right side. The horizontal line separates the constraints from the objective function. The right side of the equation is represented by the column C.
The reader needs to observe that the last four columns of this matrix look like the final matrix for the solution of a system of equations. If we arbitrarily choose \(x_1 = 0\) and \(x_2 = 0\), we get
| \(y_1\) | \(y_2\) | \(Z\) | C |
|---|---|---|---|
| 1 | 0 | 0 | 12 |
| 0 | 1 | 0 | 16 |
| 0 | 0 | 1 | 0 |
which reads
\[y_{1} = 12 \quad y_{2} = 16 \quad Z = 0\]The solution obtained by arbitrarily assigning values to some variables and then solving for the remaining variables is called the basic solution associated with the tableau. So the above solution is the basic solution associated with the initial simplex tableau. We can label the basic solution variables to the right of the last column as shown in the table below.
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(Z\) | C | |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 12 | \(y_1\) |
| 2 | 1 | 0 | 1 | 0 | 16 | \(y_2\) |
| −40 | −30 | 0 | 0 | 1 | 0 | \(Z\) |
STEP 4. The most negative entry in the bottom row identifies the pivot column
The most negative entry in the bottom row is \(-40\); therefore column 1 is identified.
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(Z\) | C | |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 12 | \(y_1\) |
| 2 | 1 | 0 | 1 | 0 | 16 | \(y_2\) |
| −40 | −30 | 0 | 0 | 1 | 0 | \(Z\) |
Question: Why do we choose the most negative entry in the bottom row?
Answer: The most negative entry in the bottom row represents the largest coefficient in the objective function—the coefficient whose entry will increase the value of the objective function the quickest.
The simplex method begins at a corner point where all the main variables (the variables that have symbols such as \(x_1\), \(x_2\), \(x_3\), etc.) are zero. It then moves from a corner point to the adjacent corner point always increasing the value of the objective function. In the case of the objective function \(Z = 40x_1 + 30x_2\), it makes more sense to increase the value of \(x_1\) rather than \(x_2\). The variable \(x_1\) represents the number of hours per week Niki works at Job I. Since Job I pays $40 per hour as opposed to Job II which pays only $30, the variable \(x_1\) will increase the objective function by $40 for a unit of increase in the variable \(x_1\).
STEP 5. Calculate the quotients
The smallest quotient identifies a row. The element in the intersection of the column identified in step 4 and the row identified in this step is identified as the pivot element.
Following the algorithm, in order to calculate the quotient, we divide the entries in the far right column by the entries in column 1, excluding the entry in the bottom row.
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(Z\) | C | Quotient | |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 12 | \(y_1\) | \(12 \div 1 = 12\) |
| 2 | 1 | 0 | 1 | 0 | 16 | \(y_2\) | \(16 \div 2 = 8\) ← |
| −40 | −30 | 0 | 0 | 1 | 0 | \(Z\) |
The smallest of the two quotients, 12 and 8, is 8. Therefore row 2 is identified. The intersection of column 1 and row 2 is the entry 2, which has been highlighted. This is our pivot element.
Question: Why do we find quotients, and why does the smallest quotient identify a row?
Answer:
When we choose the most negative entry in the bottom row, we are trying to increase the value of the objective function by bringing in the variable \(x_1\). But we cannot choose any value for \(x_1\).
Can we let \(x_1 = 100\)? Definitely not! That is because Niki never wants to work for more than 12 hours at both jobs combined: \(x_1 + x_2 \leq 12\).
Can we let \(x_1 = 12\)? Again, the answer is no because the preparation time for Job I is two times the time spent on the job. Since Niki never wants to spend more than 16 hours for preparation, the maximum time she can work is \(16 \div 2 = 8\).
Now you see the purpose of computing the quotients: using the quotients to identify the pivot element guarantees that we do not violate the constraints. The smallest quotient tells us the tightest constraint—the one that will be "used up" first if we increase this variable.
Question: Why do we identify the pivot element?
Answer:
As we have mentioned earlier, the simplex method begins with a corner point and then moves to the next corner point always improving the value of the objective function. The value of the objective function is improved by changing the number of units of the variables. We may add the number of units of one variable, while throwing away the units of another. Pivoting allows us to do just that.
The variable whose units are being added is called the entering variable, and the variable whose units are being replaced is called the departing variable. The entering variable in the above table is \(x_1\), and it was identified by the most negative entry in the bottom row. The departing variable \(y_2\) was identified by the lowest of all quotients.
STEP 6. Perform pivoting to make all other entries in this column zero
In Chapter 2, we used pivoting to obtain the row echelon form of an augmented matrix. Pivoting is a process of obtaining a 1 in the location of the pivot element, and then making all other entries zeros in that column.
So now our job is to make our pivot element a 1 by dividing the entire second row by 2. The result follows.
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(Z\) | C |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 12 |
| 1 | 1/2 | 0 | 1/2 | 0 | 8 |
| −40 | −30 | 0 | 0 | 1 | 0 |
To obtain a zero in the entry first above the pivot element, we multiply the second row by \(-1\) and add it to row 1. We get
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(Z\) | C |
|---|---|---|---|---|---|
| 0 | 1/2 | 1 | −1/2 | 0 | 4 |
| 1 | 1/2 | 0 | 1/2 | 0 | 8 |
| −40 | −30 | 0 | 0 | 1 | 0 |
To obtain a zero in the element below the pivot, we multiply the second row by 40 and add it to the last row.
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(Z\) | C | |
|---|---|---|---|---|---|---|
| 0 | 1/2 | 1 | −1/2 | 0 | 4 | \(y_1\) |
| 1 | 1/2 | 0 | 1/2 | 0 | 8 | \(x_1\) |
| 0 | −10 | 0 | 20 | 1 | 320 | \(Z\) |
We now determine the basic solution associated with this tableau. By arbitrarily choosing \(x_2 = 0\) and \(y_2 = 0\), we obtain \(x_1 = 8\), \(y_1 = 4\), and \(Z = 320\).
If we write the augmented matrix, whose left side is a matrix with columns that have one 1 and all other entries zeros, we get the following matrix stating the same thing.
| \(x_1\) | \(y_1\) | \(Z\) | C |
|---|---|---|---|
| 0 | 1 | 0 | 4 |
| 1 | 0 | 0 | 8 |
| 0 | 0 | 1 | 320 |
We can restate the solution associated with this matrix as \(x_1 = 8\), \(x_2 = 0\), \(y_1 = 4\), \(y_2 = 0\), and \(Z = 320\).
At this stage of the game, it reads that if Niki works 8 hours at Job I, and no hours at Job II, her profit \(Z\) will be $320. Recall from Example 4.2.1 (Niki's Part-Time Jobs) that (8, 0) was one of our corner points. Here \(y_1 = 4\) and \(y_2 = 0\) mean that she will be left with 4 hours of working time and no preparation time.
STEP 7. When there are no more negative entries in the bottom row, we are finished; otherwise, we start again from step 4
Since there is still a negative entry, \(-10\), in the bottom row, we need to begin, again, from step 4. This time we will not repeat the details of every step, instead, we will identify the column and row that give us the pivot element, and highlight the pivot element. The result is as follows.
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(Z\) | C | Quotient | |
|---|---|---|---|---|---|---|---|
| 0 | 1/2 | 1 | −1/2 | 0 | 4 | \(y_1\) | \(4 \div 1/2 = 8\) ← |
| 1 | 1/2 | 0 | 1/2 | 0 | 8 | \(x_1\) | \(8 \div 1/2 = 16\) |
| 0 | −10 | 0 | 20 | 1 | 320 | \(Z\) |
We make the pivot element 1 by multiplying row 1 by 2, and we get
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(Z\) | C |
|---|---|---|---|---|---|
| 0 | 1 | 2 | −1 | 0 | 8 |
| 1 | 1/2 | 0 | 1/2 | 0 | 8 |
| 0 | −10 | 0 | 20 | 1 | 320 |
Now to make all other entries as zeros in this column, we first multiply row 1 by \(-1/2\) and add it to row 2, and then multiply row 1 by 10 and add it to the bottom row.
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(Z\) | C | |
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | −1 | 0 | 8 | \(x_2\) |
| 1 | 0 | −1 | 1 | 0 | 4 | \(x_1\) |
| 0 | 0 | 20 | 10 | 1 | 400 | \(Z\) |
We no longer have negative entries in the bottom row, therefore we are finished.
Question: Why are we finished when there are no negative entries in the bottom row?
Answer: The answer lies in the bottom row. The bottom row corresponds to the equation:
\[0x_{1} + 0x_{2} + 20y_{1} + 10y_{2} + Z = 400\]or
\[Z = 400 - 20y_{1} - 10y_{2}\]Since all variables are non-negative, the highest value \(Z\) can ever achieve is 400, and that will happen only when \(y_1\) and \(y_2\) are zero.
This is the key insight of the simplex method! When there are no negative coefficients in the bottom row, increasing any variable would only decrease \(Z\). We've reached the peak—the maximum value.
STEP 8. Read off your answers
We now read off our answers, that is, we determine the basic solution associated with the final simplex tableau. Again, we look at the columns that have a 1 and all other entries zeros. Since the columns labeled \(y_1\) and \(y_2\) are not such columns, we arbitrarily choose \(y_1 = 0\), and \(y_2 = 0\), and we get
| \(x_1\) | \(x_2\) | \(Z\) | C |
|---|---|---|---|
| 0 | 1 | 0 | 8 |
| 1 | 0 | 0 | 4 |
| 0 | 0 | 1 | 400 |
The matrix reads \(x_1 = 4\), \(x_2 = 8\), and \(Z = 400\).
Final Solution:
If Niki works 4 hours at Job I and 8 hours at Job II, she will maximize her income to $400.
Since both slack variables are zero, it means that she would have used up all the working time, as well as the preparation time, and none will be left.
Problem Set 4.2
Source: Applied Finite Mathematics 3rd Edition
Solve the following linear programming problems using the simplex method.
1. Maximize \(z = x_1 + 2x_2 + 3x_3\)
subject to \(x_1 + x_2 + x_3 \leq 12\)
\[2x_{1} + x_{2} + 3x_{3} \leq 18\] \[x_{1}, x_{2}, x_{3} \geq 0\]Problem 1 Solution
Step 1: Set up the problem and convert to standard form
Add slack variables \(y_1\) and \(y_2\):
- Objective: \(-x_1 - 2x_2 - 3x_3 + z = 0\)
- Constraints:
- \(x_1 + x_2 + x_3 + y_1 = 12\)
- \(2x_1 + x_2 + 3x_3 + y_2 = 18\)
Step 2: Construct initial simplex tableau
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(Z\) | C |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 | 0 | 12 |
| 2 | 1 | 3 | 0 | 1 | 0 | 18 |
| −1 | −2 | −3 | 0 | 0 | 1 | 0 |
Step 3: First pivot operation
Most negative entry in bottom row: \(-3\) (column \(x_3\))
Calculate quotients: \(12 \div 1 = 12\) and \(18 \div 3 = 6\)
Smallest quotient is 6, so pivot on row 2, column \(x_3\) (pivot element = 3)
Divide row 2 by 3, then eliminate \(x_3\) from rows 1 and 3:
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(Z\) | C |
|---|---|---|---|---|---|---|
| 1/3 | 2/3 | 0 | 1 | −1/3 | 0 | 6 |
| 2/3 | 1/3 | 1 | 0 | 1/3 | 0 | 6 |
| 1 | −1 | 0 | 0 | 1 | 1 | 18 |
Step 4: Second pivot operation
Most negative entry in bottom row: \(-1\) (column \(x_2\))
Calculate quotients: \(6 \div (2/3) = 9\) and \(6 \div (1/3) = 18\)
Smallest quotient is 9, so pivot on row 1, column \(x_2\) (pivot element = 2/3)
Multiply row 1 by 3/2, then eliminate \(x_2\) from rows 2 and 3:
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(Z\) | C |
|---|---|---|---|---|---|---|
| 1/2 | 1 | 0 | 3/2 | −1/2 | 0 | 9 |
| 1/2 | 0 | 1 | −1/2 | 1/2 | 0 | 3 |
| 3/2 | 0 | 0 | 3/2 | 1/2 | 1 | 27 |
Step 5: Check for optimality
All entries in the bottom row are non-negative, so we have reached the optimal solution.
Answer: \(x_1 = 0\), \(x_2 = 9\), \(x_3 = 3\), \(z = 27\)
Verification:
- Constraint 1: \(0 + 9 + 3 = 12 \leq 12\) ✓
- Constraint 2: \(2(0) + 9 + 3(3) = 18 \leq 18\) ✓
- Objective: \(z = 0 + 2(9) + 3(3) = 18 + 9 = 27\) ✓
2. Maximize \(z = x_1 + 2x_2 + x_3\)
subject to \(x_1 + x_2 \leq 3\)
\[x_{2} + x_{3} \leq 4\] \[x_1 + x_3 \leq 5\] \[x_{1}, x_{2}, x_{3} \geq 0\]Problem 2 Solution
Step 1: Set up the problem and convert to standard form
Add slack variables \(y_1\), \(y_2\), and \(y_3\):
- Objective: \(-x_1 - 2x_2 - x_3 + z = 0\)
- Constraints:
- \(x_1 + x_2 + y_1 = 3\)
- \(x_2 + x_3 + y_2 = 4\)
- \(x_1 + x_3 + y_3 = 5\)
Step 2: Construct initial simplex tableau
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 3 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 4 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 5 |
| −1 | −2 | −1 | 0 | 0 | 0 | 1 | 0 |
Step 3: First pivot — Pivot column \(x_2\), pivot row 1 (quotient 3). After pivoting:
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 3 |
| −1 | 0 | 1 | −1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 5 |
| 1 | 0 | −1 | 2 | 0 | 0 | 1 | 6 |
Step 4: Second pivot — Pivot column \(x_3\) (\(-1\) in bottom row), pivot row 2 (quotient 1). After pivoting:
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 3 |
| −1 | 0 | 1 | −1 | 1 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | −1 | 1 | 0 | 4 |
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 7 |
Step 5: Check for optimality
All entries in the bottom row are non-negative, so we have reached the optimal solution.
Answer: \(x_1 = 0\), \(x_2 = 3\), \(x_3 = 1\), \(z = 7\)
Verification:
- Constraint 1: \(0 + 3 = 3 \leq 3\) ✓
- Constraint 2: \(3 + 1 = 4 \leq 4\) ✓
- Constraint 3: \(0 + 1 = 1 \leq 5\) ✓
- Objective: \(z = 0 + 2(3) + 1 = 7\) ✓
3. A farmer has 100 acres of land on which she plans to grow wheat and corn. Each acre of wheat requires 4 hours of labor and $20 of capital, and each acre of corn requires 16 hours of labor and $40 of capital. The farmer has at most 800 hours of labor and $2400 of capital available. If the profit from an acre of wheat is $80 and from an acre of corn is $100, how many acres of each crop should she plant to maximize her profit?
Problem 3 Solution
Step 1: Set up the problem
Let \(x_1 =\) acres of wheat, \(x_2 =\) acres of corn
Maximize \(z = 80x_1 + 100x_2\)
Subject to:
- Land: \(x_1 + x_2 \leq 100\)
- Labor: \(4x_1 + 16x_2 \leq 800\)
- Capital: \(20x_1 + 40x_2 \leq 2400\)
- \(x_1, x_2 \geq 0\)
Step 2: Convert to standard form with slack variables \(y_1, y_2, y_3\)
Step 3: Initial tableau
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C | |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 | 100 | \(y_1\) |
| 4 | 16 | 0 | 1 | 0 | 0 | 800 | \(y_2\) |
| 20 | 40 | 0 | 0 | 1 | 0 | 2400 | \(y_3\) |
| −80 | −100 | 0 | 0 | 0 | 1 | 0 | \(Z\) |
Step 4: First pivot — Column \(x_2\) (most negative: \(-100\)). Quotients: 100, 50, 60. Pivot R2, element = 16.
After pivoting (R2/16, then eliminate \(x_2\) from R1, R3, R4):
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C | |
|---|---|---|---|---|---|---|---|
| 3/4 | 0 | 1 | −1/16 | 0 | 0 | 50 | \(y_1\) |
| 1/4 | 1 | 0 | 1/16 | 0 | 0 | 50 | \(x_2\) |
| 10 | 0 | 0 | −5/2 | 1 | 0 | 400 | \(y_3\) |
| −55 | 0 | 0 | 25/4 | 0 | 1 | 5000 | \(Z\) |
Step 5: Second pivot — Column \(x_1\) (\(-55\)). Quotients: 200/3, 200, 40. Pivot R3, element = 10.
After pivoting:
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1/8 | −3/40 | 0 | 20 | \(y_1\) |
| 0 | 1 | 0 | 1/8 | −1/40 | 0 | 40 | \(x_2\) |
| 1 | 0 | 0 | −1/4 | 1/10 | 0 | 40 | \(x_1\) |
| 0 | 0 | 0 | −15/2 | 11/2 | 1 | 7200 | \(Z\) |
Step 6: Third pivot — Column \(y_2\) (\(-15/2\)). Quotients: 160, 320; R3 negative (skip). Pivot R1, element = 1/8.
After pivoting:
| \(x_1\) | \(x_2\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 8 | 1 | −3/5 | 0 | 160 | \(y_2\) |
| 0 | 1 | −1 | 0 | 1/20 | 0 | 20 | \(x_2\) |
| 1 | 0 | 2 | 0 | −1/20 | 0 | 80 | \(x_1\) |
| 0 | 0 | 60 | 0 | 1 | 1 | 8400 | \(Z\) |
Step 7: Check for optimality
All entries in the bottom row are non-negative, so we have reached the optimal solution.
Answer: The farmer should plant \(x_1 = 80\) acres of wheat and \(x_2 = 20\) acres of corn for a maximum profit of \(z = \$8{,}400\).
Verification:
- Land: \(80 + 20 = 100 \leq 100\) ✓
- Labor: \(4(80) + 16(20) = 320 + 320 = 640 \leq 800\) ✓
- Capital: \(20(80) + 40(20) = 1600 + 800 = 2400 \leq 2400\) ✓
- Objective: \(z = 80(80) + 100(20) = 6400 + 2000 = 8400\) ✓
4. A factory manufactures chairs, tables and bookcases each requiring the use of three operations: Cutting, Assembly, and Finishing. The first operation can be used at most 600 hours; the second at most 500 hours; and the third at most 300 hours. A chair requires 1 hour of cutting, 1 hour of assembly, and 1 hour of finishing; a table needs 1 hour of cutting, 2 hours of assembly, and 1 hour of finishing; and a bookcase requires 3 hours of cutting, 1 hour of assembly, and 1 hour of finishing. If the profit is $20 per unit for a chair, $30 for a table, and $25 for a bookcase, how many units of each should be manufactured to maximize profit?
Problem 4 Solution
Step 1: Set up the problem
Let \(x_1 =\) chairs, \(x_2 =\) tables, \(x_3 =\) bookcases
Maximize \(z = 20x_1 + 30x_2 + 25x_3\)
Subject to:
- Cutting: \(x_1 + x_2 + 3x_3 \leq 600\)
- Assembly: \(x_1 + 2x_2 + x_3 \leq 500\)
- Finishing: \(x_1 + x_2 + x_3 \leq 300\)
- \(x_1, x_2, x_3 \geq 0\)
Step 2: Initial tableau with slack variables \(y_1, y_2, y_3\)
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 3 | 1 | 0 | 0 | 0 | 600 |
| 1 | 2 | 1 | 0 | 1 | 0 | 0 | 500 |
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 300 |
| −20 | −30 | −25 | 0 | 0 | 0 | 1 | 0 |
Step 3: First pivot — Column \(x_2\) (\(-30\)). Quotients: 600, 250, 300. Pivot R2, element = 2.
After pivoting:
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C |
|---|---|---|---|---|---|---|---|
| 1/2 | 0 | 5/2 | 1 | −1/2 | 0 | 0 | 350 |
| 1/2 | 1 | 1/2 | 0 | 1/2 | 0 | 0 | 250 |
| 1/2 | 0 | 1/2 | 0 | −1/2 | 1 | 0 | 50 |
| −5 | 0 | −10 | 0 | 15 | 0 | 1 | 7500 |
Step 4: Second pivot — Column \(x_3\) (\(-10\)). Quotients: 140, 500, 100. Pivot R3, element = 1/2.
After pivoting:
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C |
|---|---|---|---|---|---|---|---|
| −2 | 0 | 0 | 1 | 2 | −5 | 0 | 100 |
| 0 | 1 | 0 | 0 | 1 | −1 | 0 | 200 |
| 1 | 0 | 1 | 0 | −1 | 2 | 0 | 100 |
| 5 | 0 | 0 | 0 | 5 | 20 | 1 | 8500 |
Step 5: Check for optimality
All entries in the bottom row are non-negative (\(5, 0, 0, 0, 5, 20\)), so we have reached the optimal solution.
Answer: The factory should manufacture \(x_1 = 0\) chairs, \(x_2 = 200\) tables, and \(x_3 = 100\) bookcases for a maximum profit of \(z = \$8{,}500\).
Verification:
- Cutting: \(0 + 200 + 3(100) = 500 \leq 600\) ✓
- Assembly: \(0 + 2(200) + 100 = 500 \leq 500\) ✓
- Finishing: \(0 + 200 + 100 = 300 \leq 300\) ✓
- Objective: \(z = 20(0) + 30(200) + 25(100) = 0 + 6000 + 2500 = 8500\) ✓
5. The Acme Apple company sells its Pippin, Macintosh, and Fuji apples in mixes. Box I contains 4 apples of each kind; Box II contains 6 Pippin, 3 Macintosh, and 3 Fuji; and Box III contains no Pippin, 8 Macintosh and 4 Fuji apples. At the end of the season, the company has altogether 2800 Pippin, 2200 Macintosh, and 2300 Fuji apples left. Determine the maximum number of boxes that the company can make.
Problem 5 Solution
Step 1: Set up the problem
Let \(x_1 =\) number of Box I, \(x_2 =\) number of Box II, \(x_3 =\) number of Box III
Maximize \(z = x_1 + x_2 + x_3\) (total boxes)
Subject to:
- Pippin: \(4x_1 + 6x_2 + 0x_3 \leq 2800\)
- Macintosh: \(4x_1 + 3x_2 + 8x_3 \leq 2200\)
- Fuji: \(4x_1 + 3x_2 + 4x_3 \leq 2300\)
- \(x_1, x_2, x_3 \geq 0\)
Step 2: Initial tableau with slack variables \(y_1, y_2, y_3\)
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C | |
|---|---|---|---|---|---|---|---|---|
| 4 | 6 | 0 | 1 | 0 | 0 | 0 | 2800 | \(y_1\) |
| 4 | 3 | 8 | 0 | 1 | 0 | 0 | 2200 | \(y_2\) |
| 4 | 3 | 4 | 0 | 0 | 1 | 0 | 2300 | \(y_3\) |
| −1 | −1 | −1 | 0 | 0 | 0 | 1 | 0 | \(Z\) |
Step 3: First pivot — All three columns tied at \(-1\); choose \(x_1\). Quotients: 700, 550, 575. Pivot R2, element = 4.
After pivoting:
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C | |
|---|---|---|---|---|---|---|---|---|
| 0 | 3 | −8 | 1 | −1 | 0 | 0 | 600 | \(y_1\) |
| 1 | 3/4 | 2 | 0 | 1/4 | 0 | 0 | 550 | \(x_1\) |
| 0 | 0 | −4 | 0 | −1 | 1 | 0 | 100 | \(y_3\) |
| 0 | −1/4 | 1 | 0 | 1/4 | 0 | 1 | 550 | \(Z\) |
Step 4: Second pivot — Column \(x_2\) (\(-1/4\)). Quotients: 200, 733.33; R3 has 0 (skip). Pivot R1, element = 3.
After pivoting:
| \(x_1\) | \(x_2\) | \(x_3\) | \(y_1\) | \(y_2\) | \(y_3\) | \(Z\) | C | |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | −8/3 | 1/3 | −1/3 | 0 | 0 | 200 | \(x_2\) |
| 1 | 0 | 4 | −1/4 | 1/2 | 0 | 0 | 400 | \(x_1\) |
| 0 | 0 | −4 | 0 | −1 | 1 | 0 | 100 | \(y_3\) |
| 0 | 0 | 1/3 | 1/12 | 1/6 | 0 | 1 | 600 | \(Z\) |
Step 5: Check for optimality
All entries in the bottom row are non-negative (\(1/3, 1/12, 1/6\)), so we have reached the optimal solution.
Answer: The company should make \(x_1 = 400\) of Box I, \(x_2 = 200\) of Box II, and \(x_3 = 0\) of Box III, for a maximum of \(z = 600\) boxes.
Verification:
- Pippin: \(4(400) + 6(200) + 0 = 1600 + 1200 = 2800 \leq 2800\) ✓
- Macintosh: \(4(400) + 3(200) + 0 = 1600 + 600 = 2200 \leq 2200\) ✓
- Fuji: \(4(400) + 3(200) + 0 = 1600 + 600 = 2200 \leq 2300\) ✓
- Objective: \(z = 400 + 200 + 0 = 600\) ✓