3.2 Minimization Applications
Learning Objectives
- Formulate minimization linear programming problems
- Graph feasibility regions for minimization linear programming problems
- Determine optimal solutions for minimization linear programming problems
Introduction to Minimization Problems
Minimization linear programming problems are solved in much the same way as maximization problems, but with one key difference: the nature of the constraints and the direction we move the objective function line.
For the standard minimization linear program, the constraints are of the form \(ax + by \geq c\), as opposed to the form \(ax + by \leq c\) for standard maximization problems.
Context Pause: Why does this matter? In maximization, we're usually dealing with resource limits—"We can't use more than X hours" or "We can't spend more than $Y." In minimization, we're often dealing with minimum requirements—"We must produce at least X units" or "We need at least Y calories." This flips the inequality signs and changes the shape of the feasibility region.
As a result, the feasibility region typically extends indefinitely to the upper right of the first quadrant and is unbounded. However, this is not a problem for minimization. To minimize the objective function, we move the objective function line toward the origin, and the critical point that minimizes the function is the corner point closest to the origin.
Source: Applied Finite Mathematics, 3rd Edition
A feasibility region that extends infinitely in one or more directions. While still valid, unbounded regions can sometimes lead to problems with no optimal solution (especially in maximization).
Insight Note: Important warning: In the case of an unbounded feasibility region, the possibility of no optimal solution exists. We'll explore this further at the end of this section.
Source: Applied Finite Mathematics, 3rd Edition
At a university, Professor Symons wishes to employ two people, John and Mary, to grade papers for his classes. John is a graduate student and can grade 20 papers per hour; John earns $15 per hour for grading papers. Mary is a post-doctoral associate and can grade 30 papers per hour; Mary earns $25 per hour for grading papers. Each must be employed at least one hour a week to justify their employment.
If Prof. Symons has at least 110 papers to be graded each week, how many hours per week should he employ each person to minimize the cost?
Example 3.2.1 Solution
Step 1: Define the variables
Let \(x\) = the number of hours per week John is employed.
Let \(y\) = the number of hours per week Mary is employed.
Step 2: Write the objective function
Since John earns $15 per hour and Mary earns $25 per hour, the total cost \(C\) is:
\[C = 15x + 25y\]Our goal is to minimize this cost function.
Step 3: Write the constraints
- Minimum employment for John: "Each must be employed at least one hour a week." \[x \geq 1\]
- Minimum employment for Mary: \[y \geq 1\]
- Papers to be graded: "John can grade 20 papers per hour and Mary 30 papers per hour, and there are at least 110 papers to be graded per week." \[20x + 30y \geq 110\]
- Non-negativity (already implied by constraints 1 and 2, but stated for completeness): \[x \geq 0, \quad y \geq 0\]
Step 4: Complete formulation
Minimize \(C = 15x + 25y\)
Subject to:
\[\begin{align} x &\geq 1 \\ y &\geq 1 \\ 20x + 30y &\geq 110 \\ x &\geq 0 \\ y &\geq 0 \end{align}\]Step 5: Graph the constraints and find the feasibility region
The shaded region shows where all constraints are satisfied.
Test point method for \(\geq\) constraints:
- If we use test point \((0,0)\), we observe that \((0,0)\) does NOT satisfy any of the constraints \(x \geq 1\), \(y \geq 1\), or \(20x + 30y \geq 110\).
- Therefore, all the shading for the feasibility region lies on the opposite side of the constraint lines from the point \((0,0)\).
Alternatively, we could use test point \((4,6)\), which does NOT lie on any constraint lines. We'd find that \((4,6)\) does satisfy all of the inequality constraints. Consequently, all the shading for the feasibility region lies on the same side of the constraint lines as the point \((4,6)\).
Insight Note: Notice that this feasibility region extends infinitely upward and to the right—it's unbounded. But since we're minimizing cost, we only care about the corner points nearest the origin, where cost is lowest.
Step 6: Identify and evaluate critical points
Since the extreme value of the objective function always occurs at a vertex, we identify the critical points: \((1, 3)\) and \((4, 1)\).
| Critical Point | Cost Calculation | Cost |
|---|---|---|
| \((1, 3)\) | \(15(1) + 25(3)\) | $90 |
| \((4, 1)\) | \(15(4) + 25(1)\) | $85 |
Conclusion: The minimum cost is $85, achieved by employing John for 4 hours a week and Mary for 1 hour a week.
Source: Applied Finite Mathematics, 3rd Edition
Professor Hamer is on a low cholesterol diet. During lunch at the college cafeteria, he always chooses between two meals, Pasta or Tofu. The table below lists the amount of protein, carbohydrates, and vitamins each meal provides along with the amount of cholesterol he is trying to minimize. Professor Hamer needs at least 200 grams of protein, 960 grams of carbohydrates, and 40 grams of vitamins for lunch each month. Over this time period, how many days should he have the Pasta meal, and how many days the Tofu meal so that he gets the adequate amount of protein, carbohydrates, and vitamins and at the same time minimizes his cholesterol intake?
| Nutrient | PASTA | TOFU |
|---|---|---|
| PROTEIN | 8g | 16g |
| CARBOHYDRATES | 60g | 40g |
| VITAMIN C | 2g | 2g |
| CHOLESTEROL | 60mg | 50mg |
Example 3.2.2 Solution
Step 1: Define the variables
Let \(x\) = the number of days Professor Hamer eats Pasta.
Let \(y\) = the number of days Professor Hamer eats Tofu.
Step 2: Write the objective function
Since he is trying to minimize his cholesterol intake, our objective function represents the total cholesterol \(C\) (in mg):
\[C = 60x + 50y\]Step 3: Write the constraints
- Protein requirement: "Needs at least 200 grams of protein each month." \[8x + 16y \geq 200\]
- Carbohydrate requirement: "Needs at least 960 grams of carbohydrates each month." \[60x + 40y \geq 960\]
- Vitamin requirement: "Needs at least 40 grams of vitamins each month." \[2x + 2y \geq 40\]
- Non-negativity: \[x \geq 0, \quad y \geq 0\]
Step 4: Complete formulation
Minimize \(C = 60x + 50y\)
Subject to:
\[\begin{align} 8x + 16y &\geq 200 \\ 60x + 40y &\geq 960 \\ 2x + 2y &\geq 40 \\ x &\geq 0 \\ y &\geq 0 \end{align}\]Step 5: Graph the constraints and find the feasibility region
We have shaded the unbounded feasibility region, where all constraints are satisfied.
Context Pause: Why is this a realistic diet problem? In the real world, you want to meet your nutritional needs (the \(\geq\) constraints) while minimizing something undesirable like cholesterol, cost, or calories. This is a classic application of linear programming in healthcare and nutrition planning.
Step 6: Identify and evaluate critical points
The vertices of the feasibility region are: \((0, 24)\), \((8, 12)\), \((15, 5)\), and \((25, 0)\).
| Critical Point | Cholesterol Calculation | Cholesterol (mg) |
|---|---|---|
| \((0, 24)\) | \(60(0) + 50(24)\) | 1200 |
| \((8, 12)\) | \(60(8) + 50(12)\) | 1080 |
| \((15, 5)\) | \(60(15) + 50(5)\) | 1150 |
| \((25, 0)\) | \(60(25) + 50(0)\) | 1500 |
Conclusion: The minimum cholesterol intake is 1080 mg, achieved by eating Pasta 8 days and Tofu 12 days each month (out of 20 meals).
When Linear Programs Have No Solution
We must be aware that in some cases, a linear program may not have an optimal solution. This can happen in two ways:
Case 1: No Feasibility Region
A linear program can fail to have an optimal solution if there is no feasibility region. This occurs when the inequality constraints are incompatible—there's no region in the graph that satisfies all the constraints simultaneously.
Insight Note: Think of it like trying to satisfy contradictory requirements: "I want to spend less than $100 total" and "I need to buy at least $150 worth of materials." There's no solution that satisfies both constraints.
If the linear program does not have a feasible solution satisfying all constraints, then it cannot have an optimal solution.
Case 2: Unbounded Feasibility Region (for Maximization)
A linear program can fail to have an optimal solution if the feasibility region is unbounded and we're trying to maximize.
The two minimization linear programs we examined (Examples 3.2.1 and 3.2.2) had unbounded feasibility regions. The feasibility region was bounded by constraints on some sides but was not entirely enclosed. Both minimization problems had optimal solutions because we were moving the objective function line toward the origin.
However, if we were to consider a maximization problem with a similar unbounded feasibility region, the linear program would have no optimal solution. No matter what values of \(x\) and \(y\) we selected, we could always find other values that would produce a higher value for the objective function.
Source: Applied Finite Mathematics, 3rd Edition
When the value of the objective function can be increased (for maximization) or decreased (for minimization) without limit within the feasibility region. This occurs when the feasibility region is unbounded in the direction that improves the objective function.
Context Pause: In practical terms, if you're trying to maximize profit and there are no real limits on how much you can produce or sell, you'd have an unbounded solution—which usually means you've forgotten to include a realistic constraint (like limited raw materials, time, or market demand).
Summary: Solving Minimization Linear Programming Problems
Although the method of solving minimization problems is similar to that of maximization problems, here's a summary of the steps:
General procedure:
- Write the objective function (the quantity to be minimized).
- Write the constraints:
- For standard minimization problems, constraints are of the form \(ax + by \geq c\)
- All variables must be non-negative: \(x \geq 0\), \(y \geq 0\)
- Graph the constraints.
- Shade the feasibility region (the area where all constraints are satisfied).
- Find the corner points (vertices of the feasibility region).
- Determine the corner point that gives the minimum value:
- Method A: Evaluate the objective function at each corner point.
- Method B: Graph the objective function line and slide it parallel to itself toward the origin to find the nearest corner.
- Method C: Be aware that the problem might have no solution (incompatible constraints or unbounded objective).
Problem Set 3.2
Source: Applied Finite Mathematics, 3rd Edition
For each of the following minimization problems, choose your variables, write the objective function and the constraints, graph the constraints, shade the feasibility region, label all critical points, and determine the solution that optimizes the objective function.
1. A diet is to contain at least 2400 units of vitamins, 1800 units of minerals, and 1200 calories. Two foods, Food A and Food B are to be purchased. Each unit of Food A provides 50 units of vitamins, 30 units of minerals, and 10 calories. Each unit of Food B provides 20 units of vitamins, 20 units of minerals, and 40 calories. Food A costs $2 per unit and Food B costs $1 per unit. How many units of each food should be purchased to keep costs at a minimum?
Problem 1 Solution
Step 1: Define the variables
Let \(x\) = units of Food A to purchase
Let \(y\) = units of Food B to purchase
Step 2: Write the objective function
We want to minimize the total cost. Food A costs $2 per unit and Food B costs $1 per unit:
\[C = 2x + y\]Step 3: Write the constraints
From the problem statement:
- Food A provides 50 units of vitamins per unit; Food B provides 20 units. We need at least 2400 units of vitamins: \[50x + 20y \geq 2400\]
- Food A provides 30 units of minerals per unit; Food B provides 20 units. We need at least 1800 units of minerals: \[30x + 20y \geq 1800\]
- Food A provides 10 calories per unit; Food B provides 40 calories. We need at least 1200 calories: \[10x + 40y \geq 1200\]
- Non-negativity constraints: \[x \geq 0, \quad y \geq 0\]
Step 4: Simplify the constraints
Divide the first constraint by 10:
\[5x + 2y \geq 240\]Divide the second constraint by 10:
\[3x + 2y \geq 180\]Divide the third constraint by 10:
\[x + 4y \geq 120\]Step 5: Find the corner points of the feasibility region
We need to find intersections of the constraint lines:
Intersection of \(5x + 2y = 240\) and \(3x + 2y = 180\):
Subtract the second from the first:
\[5x + 2y - (3x + 2y) = 240 - 180\] \[2x = 60\] \[x = 30\]Substitute into \(3x + 2y = 180\):
\[3(30) + 2y = 180 \implies 90 + 2y = 180 \implies 2y = 90 \implies y = 45\]Corner point: \((30, 45)\)
Intersection of \(5x + 2y = 240\) and \(x + 4y = 120\):
From the second equation: \(x = 120 - 4y\)
Substitute into the first:
\[5(120 - 4y) + 2y = 240 \implies 600 - 20y + 2y = 240 \implies -18y = -360 \implies y = 20\]Then \(x = 120 - 4(20) = 40\)
Corner point: \((40, 20)\)
Intersection of \(3x + 2y = 180\) and \(x + 4y = 120\):
From the second equation: \(x = 120 - 4y\)
Substitute into the first:
\[3(120 - 4y) + 2y = 180 \implies 360 - 12y + 2y = 180 \implies -10y = -180 \implies y = 18\]Then \(x = 120 - 4(18) = 48\)
Corner point: \((48, 18)\)
Intersection of \(5x + 2y = 240\) and \(y = 0\):
\[5x = 240 \implies x = 48\]Corner point: \((48, 0)\)
Intersection of \(3x + 2y = 180\) and \(x = 0\):
\[2y = 180 \implies y = 90\]Corner point: \((0, 90)\)
Intersection of \(x + 4y = 120\) and \(x = 0\):
\[4y = 120 \implies y = 30\]Corner point: \((0, 30)\)
Step 6: Evaluate the objective function at each corner point
We need to check which corner points are actually in the feasibility region (satisfy all three constraints):
- \((30, 45)\): Check \(5(30) + 2(45) = 240\) ✓, \(3(30) + 2(45) = 180\) ✓, \(30 + 4(45) = 210 \geq 120\) ✓
Cost: \(C = 2(30) + 45 = 105\) - \((40, 20)\): Check \(3(40) + 2(20) = 160 \not\geq 180\) ✗ — NOT in the feasibility region.
- \((48, 18)\): Check \(5(48) + 2(18) = 276 \geq 240\) ✓, \(3(48) + 2(18) = 180\) ✓, \(48 + 4(18) = 120\) ✓
Cost: \(C = 2(48) + 18 = 114\) - \((48, 0)\): Check \(3(48) + 0 = 144 \not\geq 180\) ✗ — NOT in the feasibility region.
- \((0, 90)\): Check \(5(0) + 2(90) = 180 \not\geq 240\) ✗ — NOT in the feasibility region.
- \((0, 30)\): Check \(5(0) + 2(30) = 60 \not\geq 240\) ✗ — NOT in the feasibility region.
The valid corner points are \((30, 45)\) with cost \$105 and \((48, 18)\) with cost \$114.
Answer: Purchase 30 units of Food A and 45 units of Food B for a minimum cost of $105.
Verification: Substitute \((30, 45)\) into all constraints:
- Vitamins: \(50(30) + 20(45) = 1500 + 900 = 2400\) ✓
- Minerals: \(30(30) + 20(45) = 900 + 900 = 1800\) ✓
- Calories: \(10(30) + 40(45) = 300 + 1800 = 2100 \geq 1200\) ✓
- Cost: \(C = 2(30) + 45 = 105\) ✓
2. A computer store sells two types of computers, laptops and desktops. The supplier demands that at least 150 computers be sold a month. Experience shows that most consumers prefer laptops, but some business customers require desktops. The result is that the number of laptops sold is at least twice the number of desktops. The store pays its sales staff a $60 commission for each laptop, and a $40 commission for each desktop. Let \(x\) = the number of laptops and \(y\) = the number of desktop computers. How many of each type must be sold to minimize commission to its sales people? What is the minimum commission?
Problem 2 Solution
Step 1: Define the variables
Let \(x\) = number of laptops sold
Let \(y\) = number of desktops sold
Step 2: Write the objective function
We want to minimize the total commission. Laptops earn $60 commission and desktops earn $40:
\[C = 60x + 40y\]Step 3: Write the constraints
- "At least 150 computers be sold a month": \[x + y \geq 150\]
- "The number of laptops sold is at least twice the number of desktops": \[x \geq 2y\]
- Non-negativity constraints: \[x \geq 0, \quad y \geq 0\]
Step 4: Find the corner points of the feasibility region
Intersection of \(x + y = 150\) and \(x = 2y\):
Substitute \(x = 2y\) into the first equation:
\[2y + y = 150 \implies 3y = 150 \implies y = 50\]Then \(x = 2(50) = 100\). Corner point: \((100, 50)\)
Intersection of \(x + y = 150\) and \(y = 0\):
\[x = 150\]Corner point: \((150, 0)\)
Intersection of \(x = 2y\) and \(y = 0\):
\(x = 0\). Corner point: \((0, 0)\) — but this doesn't satisfy \(x + y \geq 150\), so it's not in the feasibility region.
Step 5: Evaluate the objective function at each corner point
- \((100, 50)\): Check \(100 + 50 = 150\) ✓, \(100 \geq 2(50) = 100\) ✓
Cost: \(C = 60(100) + 40(50) = 6000 + 2000 = 8000\) - \((150, 0)\): Check \(150 + 0 = 150\) ✓, \(150 \geq 2(0) = 0\) ✓
Cost: \(C = 60(150) + 40(0) = 9000\)
The minimum cost occurs at \((100, 50)\).
Answer: Sell 100 laptops and 50 desktops for a minimum commission of $8,000.
Verification: Substitute \((100, 50)\) into all constraints:
- Total sales: \(100 + 50 = 150\) ✓
- Laptop constraint: \(100 \geq 2(50) = 100\) ✓
- Commission: \(C = 60(100) + 40(50) = 8000\) ✓
3. An oil company has two refineries. Each day, Refinery A produces 200 barrels of high-grade oil, 300 barrels of medium-grade oil, and 200 barrels of low-grade oil and costs $12,000 to operate. Each day, Refinery B produces 100 barrels of high-grade oil, 100 barrels of medium-grade oil, and 200 barrels of low-grade oil and costs $10,000 to operate. The company must produce at least 800 barrels of high-grade oil, 900 barrels of medium-grade oil, and 1,000 barrels of low-grade oil. How many days should each refinery be operated to meet the goals at a minimum cost?
Problem 3 Solution
Step 1: Define the variables
Let \(x\) = number of days Refinery A operates
Let \(y\) = number of days Refinery B operates
Step 2: Write the objective function
We want to minimize the total operating cost. Refinery A costs $12,000 per day and Refinery B costs $10,000 per day:
\[C = 12{,}000x + 10{,}000y\](We can work in thousands: \(C = 12x + 10y\) in thousands of dollars)
Step 3: Write the constraints
- High-grade oil: \(200x + 100y \geq 800\)
- Medium-grade oil: \(300x + 100y \geq 900\)
- Low-grade oil: \(200x + 200y \geq 1000\)
- Non-negativity: \(x \geq 0, \quad y \geq 0\)
Step 4: Simplify the constraints
\[2x + y \geq 8\] \[3x + y \geq 9\] \[x + y \geq 5\]Step 5: Find the corner points of the feasibility region
Intersection of \(2x + y = 8\) and \(3x + y = 9\):
Subtract: \(x = 1\), then \(y = 6\). Corner point: \((1, 6)\)
Intersection of \(2x + y = 8\) and \(x + y = 5\):
Subtract: \(x = 3\), then \(y = 2\). Corner point: \((3, 2)\)
Intersection of \(3x + y = 9\) and \(x + y = 5\):
Subtract: \(2x = 4 \implies x = 2\), then \(y = 3\). Corner point: \((2, 3)\)
Axis intercepts: \((0, 8)\), \((0, 9)\), \((0, 5)\)
Step 6: Evaluate the objective function at each corner point
Check which points satisfy all three constraints:
- \((1, 6)\): \(2(1)+6=8\) ✓, \(3(1)+6=9\) ✓, \(1+6=7 \geq 5\) ✓
Cost: \(C = 12(1) + 10(6) = 72\) thousand - \((3, 2)\): \(2(3)+2=8\) ✓, \(3(3)+2=11 \geq 9\) ✓, \(3+2=5\) ✓
Cost: \(C = 12(3) + 10(2) = 56\) thousand - \((2, 3)\): \(2(2)+3=7 \not\geq 8\) ✗ — NOT in the feasibility region.
- \((0, 8)\): \(3(0)+8=8 \not\geq 9\) ✗ — NOT in the feasibility region.
- \((0, 9)\): \(9 \geq 8\) ✓, \(9 \geq 9\) ✓, \(9 \geq 5\) ✓
Cost: \(C = 12(0) + 10(9) = 90\) thousand - \((0, 5)\): \(5 \not\geq 8\) ✗ — NOT in the feasibility region.
Minimum cost is at \((3, 2)\).
Answer: Operate Refinery A for 3 days and Refinery B for 2 days for a minimum cost of $56,000.
Verification: Substitute \((3, 2)\) into all constraints:
- High-grade oil: \(200(3) + 100(2) = 800\) ✓
- Medium-grade oil: \(300(3) + 100(2) = 1100 \geq 900\) ✓
- Low-grade oil: \(200(3) + 200(2) = 1000\) ✓
- Cost: \(C = 12{,}000(3) + 10{,}000(2) = 56{,}000\) ✓
4. A print shop at a community college in Cupertino, California, employs two different contractors to maintain its copying machines. The print shop needs to have 12 IBM, 18 Xerox, and 20 Canon copying machines serviced. Contractor A can repair 2 IBM, 1 Xerox, and 2 Canon machines at a cost of $800 per month, while Contractor B can repair 1 IBM, 3 Xerox, and 2 Canon machines at a cost of $1000 per month. How many months should each of the two contractors be employed to minimize the cost?
Problem 4 Solution
Step 1: Define the variables
Let \(x\) = number of months Contractor A is employed
Let \(y\) = number of months Contractor B is employed
Step 2: Write the objective function
We want to minimize the total cost. Contractor A costs $800 per month and Contractor B costs $1000 per month:
\[C = 800x + 1000y\]Step 3: Write the constraints
- IBM machines: \(2x + y \geq 12\)
- Xerox machines: \(x + 3y \geq 18\)
- Canon machines: \(2x + 2y \geq 20\), simplified to \(x + y \geq 10\)
- Non-negativity: \(x \geq 0, \quad y \geq 0\)
Step 5: Find the corner points of the feasibility region
Intersection of \(2x + y = 12\) and \(x + 3y = 18\):
From first: \(y = 12 - 2x\). Substitute: \(x + 3(12-2x) = 18 \implies -5x = -18 \implies x = 3.6\), \(y = 4.8\).
Corner point: \((3.6, 4.8)\)
Intersection of \(2x + y = 12\) and \(x + y = 10\):
Subtract: \(x = 2\), \(y = 8\). Corner point: \((2, 8)\)
Intersection of \(x + 3y = 18\) and \(x + y = 10\):
Subtract: \(2y = 8 \implies y = 4\), \(x = 6\). Corner point: \((6, 4)\)
Axis intercepts: \((0, 12)\), \((0, 6)\), \((0, 10)\)
Step 6: Evaluate the objective function at each corner point
Check which points satisfy all three constraints:
- \((3.6, 4.8)\): \(3.6 + 4.8 = 8.4 \not\geq 10\) ✗ — NOT in the feasibility region.
- \((2, 8)\): \(2(2)+8=12\) ✓, \(2+3(8)=26 \geq 18\) ✓, \(2+8=10\) ✓
Cost: \(C = 800(2) + 1000(8) = 9{,}600\) - \((6, 4)\): \(2(6)+4=16 \geq 12\) ✓, \(6+3(4)=18\) ✓, \(6+4=10\) ✓
Cost: \(C = 800(6) + 1000(4) = 8{,}800\) - \((0, 12)\): \(12 \geq 12\) ✓, \(36 \geq 18\) ✓, \(12 \geq 10\) ✓
Cost: \(C = 800(0) + 1000(12) = 12{,}000\) - \((0, 6)\): \(6 \not\geq 12\) ✗ — NOT in the feasibility region.
- \((0, 10)\): \(10 \not\geq 12\) ✗ — NOT in the feasibility region.
Minimum cost is at \((6, 4)\).
Answer: Employ Contractor A for 6 months and Contractor B for 4 months for a minimum cost of $8,800.
Verification: Substitute \((6, 4)\) into all constraints:
- IBM machines: \(2(6) + 4 = 16 \geq 12\) ✓
- Xerox machines: \(6 + 3(4) = 18\) ✓
- Canon machines: \(2(6) + 2(4) = 20\) ✓
- Cost: \(C = 800(6) + 1000(4) = 8{,}800\) ✓