4.3 Minimization by the Simplex Method
4.3.1 Learning Objectives
- Identify and set up a linear program in standard minimization form
- Formulate a dual problem in standard maximization form
- Use the simplex method to solve the dual maximization problem
- Identify the optimal solution to the original minimization problem from the optimal simplex tableau
4.3.2 The Dual Problem Concept
In this section, we will solve the standard linear programming minimization problems using the simplex method. Once again, we remind the reader that in the standard minimization problems all constraints are of the form \(ax + by \geq c\).
Why can't we just use the simplex method directly on minimization problems? The simplex method as we learned it in Section 4.2 was designed for maximization with \(\leq\) constraints. Minimization problems with \(\geq\) constraints would require a different approach—or we can use a clever mathematical trick called the dual problem.
The procedure to solve these problems was developed by Dr. John Von Neumann. It involves solving an associated problem called the dual problem. To every minimization problem there corresponds a dual problem. The solution of the dual problem is used to find the solution of the original problem. The dual problem is a maximization problem, which we learned to solve in the last section. We first solve the dual problem by the simplex method. From the final simplex tableau, we then extract the solution to the original minimization problem.
Think of the dual problem as a mirror image of the original problem. Minimizing cost in one scenario is equivalent to maximizing efficiency in the mirror scenario. The mathematics guarantees that solving either problem gives you the answer to both.
Before we go any further, however, we first learn to convert a minimization problem into its corresponding maximization problem called its dual.
Source: Applied Finite Mathematics 3rd Edition
Problem Statement:
Convert the following minimization problem into its dual.
Minimize \(Z = 12x_{1} + 16x_{2}\)
Subject to: \(x_{1} + 2x_{2} \geq 40\)
\[x_{1} + x_{2} \geq 30\]
\[x_{1} \geq 0; \quad x_{2} \geq 0\]
Solution
To achieve our goal, we first express our problem as the following matrix.
| 1 | 2 | 40 |
| 1 | 1 | 30 |
| 12 | 16 | 0 |
Observe that this table looks like an initial simplex tableau without the slack variables.
Next, we write a matrix whose columns are the rows of this matrix, and the rows are the columns. Such a matrix is called a transpose of the original matrix. We get:
| 1 | 1 | 12 |
| 2 | 1 | 16 |
| 40 | 30 | 0 |
The following maximization problem associated with the above matrix is called its dual.
Maximize \(Z = 40y_{1} + 30y_{2}\)
Subject to: \(y_1 + y_2 \leq 12\)
\[2y_1 + y_2 \leq 16\]
\[y_1 \geq 0; \quad y_2 \geq 0\]
Note on Notation: We have chosen the variables as \(y\)'s, instead of \(x\)'s, to distinguish the two problems. This helps avoid confusion between the original (minimization) and dual (maximization) problems.
Source: Applied Finite Mathematics 3rd Edition
Problem Statement:
Solve graphically both the minimization problem and its dual maximization problem.
Solution
Our minimization problem is as follows.
Minimize \(Z = 12x_{1} + 16x_{2}\)
Subject to: \(x_1 + 2x_2 \geq 40\)
\[x_{1} + x_{2} \geq 30\]
\[x_{1} \geq 0; \quad x_{2} \geq 0\]
We now graph the inequalities:
We have plotted the graph, shaded the feasibility region, and labeled the corner points. The corner point (20, 10) gives the lowest value for the objective function and that value is 400.
Now its dual is:
Maximize \(Z = 40y_{1} + 30y_{2}\)
Subject to: \(y_1 + y_2 \leq 12\)
\[2y_1 + y_2 \leq 16\]
\[y_{1} \geq 0; \quad y_{2} \geq 0\]
We graph the inequalities:
Again, we have plotted the graph, shaded the feasibility region, and labeled the corner points. The corner point (4, 8) gives the highest value for the objective function, with a value of 400.
The reader may recognize that Example 4.3.2 above is the same as Example 1 in Section 3.1. It is also the same problem as Example 1 in Section 4.2, where we solved it by the simplex method. We're seeing the same problem from different angles—like looking at a sculpture from different sides.
We observe that the minimum value of the minimization problem is the same as the maximum value of the maximization problem; in Example 4.3.2 the minimum and maximum are both 400. This is not a coincidence. We state the duality principle.
4.3.3 The Duality Principle
THE DUALITY PRINCIPLE:
The objective function of the minimization problem reaches its minimum if and only if the objective function of its dual reaches its maximum. And when they do, they are equal.
Why is this principle so powerful? It means we never actually have to learn a separate algorithm for minimization problems. We just convert to the dual, solve the maximization problem (which we already know how to do), and extract the minimization answer from the same solution. Two problems for the price of one!
Source: Applied Finite Mathematics 3rd Edition
Our next goal is to extract the solution for our minimization problem from the corresponding dual. To do this, we solve the dual by the simplex method.
Problem Statement:
Find the solution to the minimization problem in Example 4.3.1 by solving its dual using the simplex method. We rewrite our problem.
Minimize \(Z = 12x_{1} + 16x_{2}\)
Subject to: \(x_1 + 2x_2 \geq 40\)
\[x_{1} + x_{2} \geq 30\]
\[x_{1} \geq 0; \quad x_{2} \geq 0\]
Solution
The dual is:
Maximize \(Z = 40y_{1} + 30y_{2}\)
Subject to: \(y_1 + y_2 \leq 12\)
\[2y_1 + y_2 \leq 16\]
\[y_1 \geq 0; \quad y_2 \geq 0\]
Recall that we solved the above problem by the simplex method in Example 1, Section 4.2. Therefore, we only show the initial and final simplex tableau.
The initial simplex tableau is:
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(Z\) | C |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 12 |
| 2 | 1 | 0 | 1 | 0 | 16 |
| −40 | −30 | 0 | 0 | 1 | 0 |
Observe an Important Change: Here our main variables are \(y_1\) and \(y_2\) and the slack variables are \(x_1\) and \(x_2\). This is the key to extracting the minimization solution—the slack variables in the dual are the decision variables in the original problem!
The final simplex tableau reads as follows:
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(Z\) | C |
|---|---|---|---|---|---|
| 0 | 1 | 2 | −1 | 0 | 8 |
| 1 | 0 | −1 | 1 | 0 | 4 |
| 0 | 0 | 20 | 10 | 1 | 400 |
A closer look at this table reveals that the \(x_1\) and \(x_2\) values along with the minimum value for the minimization problem can be obtained from the last row of the final tableau.
Why do the answers appear in the bottom row under the slack variable columns? Because of the mathematical relationship between a problem and its dual. The shadow prices (slack variable coefficients) in the dual's optimal solution are precisely the optimal values of the decision variables in the original minimization problem.
We restate the solution as follows:
The minimization problem has a minimum value of 400 at the corner point (20, 10).
4.3.4 Minimization Algorithm Summary
We now summarize our discussion.
MINIMIZATION BY THE SIMPLEX METHOD
- Set up the problem. Write the objective function and constraints.
- Write a matrix whose rows represent each constraint with the objective function as its bottom row.
- Write the transpose of this matrix by interchanging the rows and columns.
- Now write the dual problem associated with the transpose.
- Solve the dual problem by the simplex method learned in Section 4.2.
- The optimal solution is found in the bottom row of the final matrix in the columns corresponding to the slack variables, and the minimum value of the objective function is the same as the maximum value of the dual.
Problem Set 4.3
Source: Applied Finite Mathematics 3rd Edition
In problems 1–2, convert each minimization problem into a maximization problem, the dual, and then solve by the simplex method.
1. Minimize \(z = 6x_{1} + 8x_{2}\)
subject to \(2x_1 + 3x_2 \geq 7\)
\[4x_1 + 5x_2 \geq 9\]
\[x_{1}, x_{2} \geq 0\]
Problem 1 Solution
Step 1: Set up the minimization matrix
Arrange constraint coefficients and objective function in matrix form (constraints as rows, objective as bottom row):
\[\begin{bmatrix} 2 & 3 & 7 \\ 4 & 5 & 9 \\ 6 & 8 & 0 \end{bmatrix}\]
Step 2: Transpose the matrix to form the dual
Interchange rows and columns:
\[\begin{bmatrix} 2 & 4 & 6 \\ 3 & 5 & 8 \\ 7 & 9 & 0 \end{bmatrix}\]
Step 3: Write the dual maximization problem
Maximize \(Z = 7y_1 + 9y_2\)
Subject to: \(2y_1 + 4y_2 \leq 6\)
\[3y_1 + 5y_2 \leq 8\]
\[y_1 \geq 0; \quad y_2 \geq 0\]
Step 4: Set up initial simplex tableau
Add slack variables \(x_1, x_2\) (which correspond to the original primal decision variables):
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(Z\) | RHS |
|---|---|---|---|---|---|
| 2 | 4 | 1 | 0 | 0 | 6 |
| 3 | 5 | 0 | 1 | 0 | 8 |
| \(-7\) | \(-9\) | 0 | 0 | 1 | 0 |
Step 5: First pivot operation
Most negative entry in objective row: \(-9\) (column \(y_2\)).
Minimum ratio test: \(6 \div 4 = 1.5\), \(8 \div 5 = 1.6\). Minimum is \(1.5\) → Pivot element is \(4\) (Row 1, \(y_2\) column).
\(R_1 \leftarrow \dfrac{R_1}{4}\):
\[R_1 = \left[\frac{1}{2},\; 1,\; \frac{1}{4},\; 0,\; 0,\; \frac{3}{2}\right]\]
\(R_2 \leftarrow R_2 - 5R_1\):
\[R_2 = \left[\frac{1}{2},\; 0,\; -\frac{5}{4},\; 1,\; 0,\; \frac{1}{2}\right]\]
\(R_3 \leftarrow R_3 + 9R_1\):
\[R_3 = \left[-\frac{5}{2},\; 0,\; \frac{9}{4},\; 0,\; 1,\; \frac{27}{2}\right]\]
Tableau after first pivot:
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(Z\) | RHS |
|---|---|---|---|---|---|
| \(1/2\) | 1 | \(1/4\) | 0 | 0 | \(3/2\) |
| \(1/2\) | 0 | \(-5/4\) | 1 | 0 | \(1/2\) |
| \(-5/2\) | 0 | \(9/4\) | 0 | 1 | \(27/2\) |
Step 6: Second pivot operation
Most negative entry in objective row: \(-5/2\) (column \(y_1\)).
Minimum ratio test (only positive entries): \((3/2) \div (1/2) = 3\), \((1/2) \div (1/2) = 1\). Minimum is \(1\) → Pivot element is \(1/2\) (Row 2, \(y_1\) column).
\(R_2 \leftarrow 2R_2\):
\[R_2 = \left[1,\; 0,\; -\frac{5}{2},\; 2,\; 0,\; 1\right]\]
\(R_1 \leftarrow R_1 - \dfrac{1}{2}R_2\):
\[R_1 = \left[0,\; 1,\; \frac{3}{2},\; -1,\; 0,\; 1\right]\]
\(R_3 \leftarrow R_3 + \dfrac{5}{2}R_2\):
\[R_3 = \left[0,\; 0,\; -4,\; 5,\; 1,\; 16\right]\]
Tableau after second pivot:
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(Z\) | RHS |
|---|---|---|---|---|---|
| 0 | 1 | \(3/2\) | \(-1\) | 0 | 1 |
| 1 | 0 | \(-5/2\) | 2 | 0 | 1 |
| 0 | 0 | \(-4\) | 5 | 1 | 16 |
Not yet optimal — the objective row has \(-4\) under column \(x_1\).
Step 7: Third pivot operation
Most negative entry in objective row: \(-4\) (column \(x_1\)).
Minimum ratio test (only positive entries in \(x_1\) column): Row 1 has \(3/2 > 0\). Quotient: \(1 \div (3/2) = 2/3\). Row 2 has \(-5/2 < 0\) — skip. → Pivot element is \(3/2\) (Row 1, \(x_1\) column).
\(R_1 \leftarrow \dfrac{2}{3}R_1\):
\[R_1 = \left[0,\; \frac{2}{3},\; 1,\; -\frac{2}{3},\; 0,\; \frac{2}{3}\right]\]
\(R_2 \leftarrow R_2 + \dfrac{5}{2}R_1\):
\[R_2 = \left[1,\; \frac{5}{3},\; 0,\; \frac{1}{3},\; 0,\; \frac{8}{3}\right]\]
\(R_3 \leftarrow R_3 + 4R_1\):
\[R_3 = \left[0,\; \frac{8}{3},\; 0,\; \frac{7}{3},\; 1,\; \frac{56}{3}\right]\]
Final optimal tableau:
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(Z\) | RHS |
|---|---|---|---|---|---|
| 0 | \(2/3\) | 1 | \(-2/3\) | 0 | \(2/3\) |
| 1 | \(5/3\) | 0 | \(1/3\) | 0 | \(8/3\) |
| 0 | \(8/3\) | 0 | \(7/3\) | 1 | \(56/3\) |
All entries in the objective row are non-negative (\(8/3 \geq 0\), \(0\), \(7/3 \geq 0\)) → Optimal solution reached.
Step 8: Extract the primal (minimization) solution
From the bottom row of the final tableau, read the values under the slack variable columns:
- Under \(x_1\): \(0\) → \(x_1 = 0\)
- Under \(x_2\): \(7/3\) → \(x_2 = 7/3\)
- Maximum dual value \(Z = 56/3\) = Minimum primal value \(z\)
Answer: Minimum \(z = \dfrac{56}{3} \approx 18.67\) at \((x_1, x_2) = \left(0,\; \dfrac{7}{3}\right)\)
Verification: Substitute into original constraints and objective:
- Constraint 1: \(2(0) + 3\!\left(\dfrac{7}{3}\right) = 7 \geq 7\) ✓
- Constraint 2: \(4(0) + 5\!\left(\dfrac{7}{3}\right) = \dfrac{35}{3} \approx 11.67 \geq 9\) ✓
- Objective: \(z = 6(0) + 8\!\left(\dfrac{7}{3}\right) = \dfrac{56}{3} \approx 18.67\) ✓
- Duality check: dual maximum \(= 56/3 =\) primal minimum ✓
2. Minimize \(z = 5x_1 + 6x_2 + 7x_3\)
subject to \(3x_1 + 2x_2 + 3x_3 \geq 10\)
\[4x_{1} + 3x_{2} + 5x_{3} \geq 12\]
\[x_1, x_2, x_3 \geq 0\]
Problem 2 Solution
Step 1: Set up the minimization matrix
\[\begin{bmatrix} 3 & 2 & 3 & 10 \\ 4 & 3 & 5 & 12 \\ 5 & 6 & 7 & 0 \end{bmatrix}\]
Step 2: Transpose to form the dual
\[\begin{bmatrix} 3 & 4 & 5 \\ 2 & 3 & 6 \\ 3 & 5 & 7 \\ 10 & 12 & 0 \end{bmatrix}\]
Step 3: Write the dual maximization problem
Maximize \(Z = 10y_1 + 12y_2\)
Subject to: \(3y_1 + 4y_2 \leq 5\)
\[2y_1 + 3y_2 \leq 6\]
\[3y_1 + 5y_2 \leq 7\]
\[y_1 \geq 0; \quad y_2 \geq 0\]
Step 4: Set up initial simplex tableau
Add slack variables \(x_1, x_2, x_3\) (corresponding to the primal decision variables):
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(x_3\) | \(Z\) | RHS |
|---|---|---|---|---|---|---|
| 3 | 4 | 1 | 0 | 0 | 0 | 5 |
| 2 | 3 | 0 | 1 | 0 | 0 | 6 |
| 3 | 5 | 0 | 0 | 1 | 0 | 7 |
| \(-10\) | \(-12\) | 0 | 0 | 0 | 1 | 0 |
Step 5: First pivot operation
Most negative entry in objective row: \(-12\) (column \(y_2\)).
Minimum ratio test: \(5/4 = 1.25\), \(6/3 = 2\), \(7/5 = 1.4\). Minimum is \(1.25\) → Pivot element is \(4\) (Row 1, \(y_2\) column).
After row operations:
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(x_3\) | \(Z\) | RHS |
|---|---|---|---|---|---|---|
| \(3/4\) | 1 | \(1/4\) | 0 | 0 | 0 | \(5/4\) |
| \(-1/4\) | 0 | \(-3/4\) | 1 | 0 | 0 | \(9/4\) |
| \(-3/4\) | 0 | \(-5/4\) | 0 | 1 | 0 | \(3/4\) |
| \(-1\) | 0 | 3 | 0 | 0 | 1 | 15 |
Step 6: Second pivot operation
Most negative entry in objective row: \(-1\) (column \(y_1\)).
Minimum ratio test (only positive entries in \(y_1\) column): Row 1 has \(3/4 > 0\), quotient: \((5/4) \div (3/4) = 5/3 \approx 1.67\). Rows 2 and 3 have negative entries — skip. → Pivot element is \(3/4\) (Row 1, \(y_1\) column).
Final optimal tableau:
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(x_3\) | \(Z\) | RHS |
|---|---|---|---|---|---|---|
| 1 | \(4/3\) | \(1/3\) | 0 | 0 | 0 | \(5/3\) |
| 0 | \(1/3\) | \(-2/3\) | 1 | 0 | 0 | \(8/3\) |
| 0 | 1 | \(-1\) | 0 | 1 | 0 | 2 |
| 0 | \(4/3\) | \(10/3\) | 0 | 0 | 1 | \(50/3\) |
All entries in the objective row are non-negative → Optimal solution reached.
Step 7: Extract the primal (minimization) solution
- Under \(x_1\): \(10/3\) → \(x_1 = 10/3\)
- Under \(x_2\): \(0\) → \(x_2 = 0\)
- Under \(x_3\): \(0\) → \(x_3 = 0\)
Answer: Minimum \(z = \dfrac{50}{3} \approx 16.67\) at \((x_1, x_2, x_3) = \left(\dfrac{10}{3},\; 0,\; 0\right)\)
Verification:
- Constraint 1: \(3\!\left(\dfrac{10}{3}\right) + 2(0) + 3(0) = 10 \geq 10\) ✓
- Constraint 2: \(4\!\left(\dfrac{10}{3}\right) + 3(0) + 5(0) = \dfrac{40}{3} \approx 13.33 \geq 12\) ✓
- Objective: \(z = 5\!\left(\dfrac{10}{3}\right) + 6(0) + 7(0) = \dfrac{50}{3} \approx 16.67\) ✓
- Duality check: dual maximum \(= 50/3 =\) primal minimum ✓
3. Minimize \(z = 4x_1 + 3x_2\)
subject to \(x_1 + x_2 \geq 10\)
\[3x_1 + 2x_2 \geq 24\]
\[x_{1}, x_{2} \geq 0\]
Problem 3 Solution
Step 1: Set up the minimization matrix
\[\begin{bmatrix} 1 & 1 & 10 \\ 3 & 2 & 24 \\ 4 & 3 & 0 \end{bmatrix}\]
Step 2: Transpose to form the dual
\[\begin{bmatrix} 1 & 3 & 4 \\ 1 & 2 & 3 \\ 10 & 24 & 0 \end{bmatrix}\]
Step 3: Write the dual maximization problem
Maximize \(Z = 10y_1 + 24y_2\)
Subject to: \(y_1 + 3y_2 \leq 4\)
\[y_1 + 2y_2 \leq 3\]
\[y_1 \geq 0; \quad y_2 \geq 0\]
Step 4: Set up initial simplex tableau
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(Z\) | RHS |
|---|---|---|---|---|---|
| 1 | 3 | 1 | 0 | 0 | 4 |
| 1 | 2 | 0 | 1 | 0 | 3 |
| \(-10\) | \(-24\) | 0 | 0 | 1 | 0 |
Step 5: First pivot — Pivot on \(3\) (Row 1, \(y_2\) column).
After row operations:
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(Z\) | RHS |
|---|---|---|---|---|---|
| \(1/3\) | 1 | \(1/3\) | 0 | 0 | \(4/3\) |
| \(1/3\) | 0 | \(-2/3\) | 1 | 0 | \(1/3\) |
| \(-2\) | 0 | 8 | 0 | 1 | 32 |
Step 6: Second pivot — Pivot on \(1/3\) (Row 2, \(y_1\) column).
Final optimal tableau:
| \(y_1\) | \(y_2\) | \(x_1\) | \(x_2\) | \(Z\) | RHS |
|---|---|---|---|---|---|
| 0 | 1 | 1 | \(-1\) | 0 | 1 |
| 1 | 0 | \(-2\) | 3 | 0 | 1 |
| 0 | 0 | 4 | 6 | 1 | 34 |
All entries in the objective row are non-negative → Optimal solution reached.
Step 7: Extract the primal (minimization) solution
- Under \(x_1\): \(4\) → \(x_1 = 4\)
- Under \(x_2\): \(6\) → \(x_2 = 6\)
Answer: Minimum \(z = 34\) at \((x_1, x_2) = (4, 6)\)
Verification:
- Constraint 1: \(4 + 6 = 10 \geq 10\) ✓
- Constraint 2: \(3(4) + 2(6) = 12 + 12 = 24 \geq 24\) ✓
- Objective: \(z = 4(4) + 3(6) = 16 + 18 = 34\) ✓
- Duality check: dual maximum \(= 34 =\) primal minimum ✓
4. Diet Problem: A diet is to contain at least 8 units of vitamins, 9 units of minerals, and 10 calories.
Three foods, Food A, Food B, and Food C are to be purchased. Each unit of Food A provides 1 unit of vitamins, 1 unit of minerals, and 2 calories. Each unit of Food B provides 2 units of vitamins, 1 unit of minerals, and 1 calorie. Each unit of Food C provides 2 units of vitamins, 1 unit of minerals, and 2 calories. If Food A costs $3 per unit, Food B costs $2 per unit and Food C costs $3 per unit, how many units of each food should be purchased to keep costs at a minimum?
Problem 4 Solution
Step 1: Define variables and set up the minimization problem
Let \(x_1 =\) units of Food A, \(x_2 =\) units of Food B, \(x_3 =\) units of Food C.
| Vitamins | Minerals | Calories | Cost | |
|---|---|---|---|---|
| Food A (\(x_1\)) | 1 | 1 | 2 | $3 |
| Food B (\(x_2\)) | 2 | 1 | 1 | $2 |
| Food C (\(x_3\)) | 2 | 1 | 2 | $3 |
| Minimum needed | 8 | 9 | 10 |
Minimize \(z = 3x_1 + 2x_2 + 3x_3\) (total cost)
Subject to:
- Vitamins: \(x_1 + 2x_2 + 2x_3 \geq 8\)
- Minerals: \(x_1 + x_2 + x_3 \geq 9\)
- Calories: \(2x_1 + x_2 + 2x_3 \geq 10\)
- \(x_1, x_2, x_3 \geq 0\)
Step 2: Set up the minimization matrix
\[\begin{bmatrix} 1 & 2 & 2 & 8 \\ 1 & 1 & 1 & 9 \\ 2 & 1 & 2 & 10 \\ 3 & 2 & 3 & 0 \end{bmatrix}\]
Step 3: Transpose to form the dual
\[\begin{bmatrix} 1 & 1 & 2 & 3 \\ 2 & 1 & 1 & 2 \\ 2 & 1 & 2 & 3 \\ 8 & 9 & 10 & 0 \end{bmatrix}\]
Step 4: Write the dual maximization problem
Maximize \(Z = 8y_1 + 9y_2 + 10y_3\)
Subject to: \(y_1 + y_2 + 2y_3 \leq 3\)
\[2y_1 + y_2 + y_3 \leq 2\]
\[2y_1 + y_2 + 2y_3 \leq 3\]
\[y_1, y_2, y_3 \geq 0\]
Step 5: Set up initial simplex tableau
| \(y_1\) | \(y_2\) | \(y_3\) | \(x_1\) | \(x_2\) | \(x_3\) | \(Z\) | RHS |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 1 | 0 | 0 | 0 | 3 |
| 2 | 1 | 1 | 0 | 1 | 0 | 0 | 2 |
| 2 | 1 | 2 | 0 | 0 | 1 | 0 | 3 |
| \(-8\) | \(-9\) | \(-10\) | 0 | 0 | 0 | 1 | 0 |
Step 6: First pivot — Pivot on \(2\) (Row 1, \(y_3\) column).
After row operations:
| \(y_1\) | \(y_2\) | \(y_3\) | \(x_1\) | \(x_2\) | \(x_3\) | \(Z\) | RHS |
|---|---|---|---|---|---|---|---|
| \(1/2\) | \(1/2\) | 1 | \(1/2\) | 0 | 0 | 0 | \(3/2\) |
| \(3/2\) | \(1/2\) | 0 | \(-1/2\) | 1 | 0 | 0 | \(1/2\) |
| 1 | 0 | 0 | \(-1\) | 0 | 1 | 0 | 0 |
| \(-3\) | \(-4\) | 0 | 5 | 0 | 0 | 1 | 15 |
Step 7: Second pivot — Pivot on \(1/2\) (Row 2, \(y_2\) column).
Final optimal tableau:
| \(y_1\) | \(y_2\) | \(y_3\) | \(x_1\) | \(x_2\) | \(x_3\) | \(Z\) | RHS |
|---|---|---|---|---|---|---|---|
| \(-1\) | 0 | 1 | 1 | \(-1\) | 0 | 0 | 1 |
| 3 | 1 | 0 | \(-1\) | 2 | 0 | 0 | 1 |
| 1 | 0 | 0 | \(-1\) | 0 | 1 | 0 | 0 |
| 9 | 0 | 0 | 1 | 8 | 0 | 1 | 19 |
All entries in the objective row are non-negative (\(9 \geq 0\), \(1 \geq 0\), \(8 \geq 0\)) → Optimal solution reached.
Step 8: Extract the primal (minimization) solution
- Under \(x_1\): \(1\) → \(x_1 = 1\) (units of Food A)
- Under \(x_2\): \(8\) → \(x_2 = 8\) (units of Food B)
- Under \(x_3\): \(0\) → \(x_3 = 0\) (units of Food C)
Answer: Purchase 1 unit of Food A, 8 units of Food B, and 0 units of Food C for a minimum cost of \(z = \$19\).
Verification:
- Vitamins: \(1 + 2(8) + 2(0) = 1 + 16 = 17 \geq 8\) ✓
- Minerals: \(1 + 8 + 0 = 9 \geq 9\) ✓
- Calories: \(2(1) + 8 + 2(0) = 2 + 8 = 10 \geq 10\) ✓
- Cost: \(z = 3(1) + 2(8) + 3(0) = 3 + 16 = \$19\) ✓
- Duality check: dual maximum \(= 19 =\) primal minimum ✓