3.1 Maximization Applications
Learning Objectives
- Recognize the typical form of a linear programming problem
- Formulate maximization linear programming problems
- Graph feasibility regions for maximization linear programming problems
- Determine optimal solutions for maximization linear programming problems
Introduction to Linear Programming
In business, economics, and the life sciences, we constantly face decisions based on certain conditions or limits. These limits—called constraints—often take the form of inequalities. In this section, we'll learn how to formulate, analyze, and solve optimization problems step-by-step.
Why does linear programming matter? Imagine you run a small business with limited resources—time, money, materials. You need to decide how to allocate those resources to maximize profit. Or maybe you're a hospital administrator trying to minimize costs while meeting patient care standards. Linear programming gives you a systematic way to find the best possible solution when you're juggling multiple competing constraints.
A linear programming problem consists of finding the extreme value (maximum or minimum) of a linear function subject to certain constraints. We call the function we're trying to optimize the objective function, and the conditions we must satisfy are the constraints.
The linear function we are trying to maximize or minimize in an optimization problem. For example, a profit function \(P = 20x + 30y\) that we want to maximize.
A condition or limitation that must be satisfied, typically expressed as an inequality. For example, \(x + y \leq 12\) represents a constraint that the sum of two variables cannot exceed 12.
Common examples include:
- Production problems: Maximize profit from several products, given limits on materials or resources
- Scheduling problems: Maximize income (or minimize cost) by allocating time to different activities, given time and resource limits
In this chapter, we'll focus on problems with only two variables, which allows us to solve them by graphing. In the next chapter, we'll learn the simplex method—a numerical algorithm that can handle problems with many more variables. We'll also explore real-world applications across business, healthcare, logistics, and other fields.
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. She cannot spend more than 16 hours for preparation.
If Niki 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 3.1.1 Solution
Step 1: Define the variables
Let \(x\) = the number of hours per week Niki will work at Job I.
Let \(y\) = the number of hours per week Niki will work at Job II.
Step 2: Write the objective function
Since Niki earns $40 per hour at Job I and $30 per hour at Job II, her total income \(I\) is:
\[I = 40x + 30y\]Our goal is to maximize this income function.
Step 3: Write the constraints
Now we translate each limitation from the problem into a mathematical inequality:
- Work hour limit: "She never wants to work more than a total of 12 hours a week." \[x + y \leq 12\]
- Preparation time limit: "For every hour at Job I, she needs 2 hours of prep; for every hour at Job II, she needs 1 hour of prep, and she cannot spend more than 16 hours preparing." \[2x + y \leq 16\]
- Non-negativity: Hours worked cannot be negative. \[x \geq 0, \quad y \geq 0\]
Step 4: Formulate the complete linear program
We can now restate the problem in standard form:
Maximize \(I = 40x + 30y\)
Subject to:
\[\begin{align} x + y &\leq 12 \\ 2x + y &\leq 16 \\ x &\geq 0 \\ y &\geq 0 \end{align}\]Step 5: Graph the constraints and find the feasibility region
To graph each constraint, we treat it as an equation and plot the line (usually by finding the x-intercept and y-intercept). Then we use a test point to determine which side of the line satisfies the inequality.
Think of the graph as a map of all possible work schedules Niki could choose. The shaded region—called the feasibility region—contains every combination of hours at Job I and Job II that satisfies all her constraints. Our job is to find which point in that region gives her the highest income.
Test point method:
- If the test point satisfies the inequality, shade the region containing the test point.
- If the test point does NOT satisfy the inequality, shade the opposite side.
For this problem, we can use \((0,0)\) as our test point:
- \((0,0)\) satisfies \(x + y \leq 12\) because \(0 + 0 < 12\) ✓
- \((0,0)\) satisfies \(2x + y \leq 16\) because \(2(0) + 0 < 16\) ✓
Therefore, we shade the region below and to the left of both constraint lines, but above the x-axis and to the right of the y-axis (to satisfy \(x \geq 0\) and \(y \geq 0\)).
The shaded region where all constraints are satisfied is called the feasibility region or feasibility polygon.
The set of all points \((x, y)\) that satisfy all the constraints simultaneously. Graphically, it is the intersection (overlap) of all the shaded regions from each individual constraint.
Step 6: Identify critical points (vertices)
The Fundamental Theorem of Linear Programming states that the maximum (or minimum) value of the objective function always occurs at one of the vertices (corner points) of the feasibility region.
For Niki's problem, the vertices are: \((0, 0)\), \((0, 12)\), \((4, 8)\), \((8, 0)\).
Why do we only check the corner points? Imagine sliding a ruler (representing the income function) across the graph. The ruler's slope stays constant, but as you slide it, the income value changes. The maximum income will always occur when the ruler touches the last corner of the feasibility region before leaving it entirely. This geometric insight saves us from testing every single point inside the region!
Step 7: Evaluate the objective function at each critical point
| Critical Point | Income Calculation | Income |
|---|---|---|
| \((0, 0)\) | \(40(0) + 30(0)\) | $0 |
| \((0, 12)\) | \(40(0) + 30(12)\) | $360 |
| \((4, 8)\) | \(40(4) + 30(8)\) | $400 |
| \((8, 0)\) | \(40(8) + 30(0)\) | $320 |
Step 8: Interpret the result
The maximum income is $400, which occurs at the point \((4, 8)\).
Conclusion: Niki should work 4 hours at Job I and 8 hours at Job II each week to maximize her income at $400.
A factory manufactures two types of gadgets: regular and premium. Each gadget requires the use of two operations, assembly and finishing, and there are at most 12 hours available for each operation. A regular gadget requires 1 hour of assembly and 2 hours of finishing, while a premium gadget needs 2 hours of assembly and 1 hour of finishing. Due to other restrictions, the company can make at most 7 gadgets a day. If a profit of $20 is realized for each regular gadget and $30 for a premium gadget, how many of each should be manufactured to maximize profit?
Example 3.1.2 Solution
Step 1: Define the variables
Let \(x\) = the number of regular gadgets manufactured each day.
Let \(y\) = the number of premium gadgets manufactured each day.
Step 2: Write the objective function
The profit function is:
\[P = 20x + 30y\]Step 3: Write the constraints
- Total gadget limit: "The company can make at most 7 gadgets a day." \[x + y \leq 7\]
- Assembly time limit: Regular gadgets take 1 hour of assembly, premium gadgets take 2 hours, and there are at most 12 hours available. \[x + 2y \leq 12\]
- Finishing time limit: Regular gadgets take 2 hours of finishing, premium gadgets take 1 hour, and there are at most 12 hours available. \[2x + y \leq 12\]
- Non-negativity: \[x \geq 0, \quad y \geq 0\]
Step 4: Complete formulation
Maximize \(P = 20x + 30y\)
Subject to:
\[\begin{align} x + y &\leq 7 \\ x + 2y &\leq 12 \\ 2x + y &\leq 12 \\ x &\geq 0 \\ y &\geq 0 \end{align}\]Step 5: Graph the feasibility region
The feasibility region is shaded, showing all combinations of regular and premium gadgets that satisfy all constraints.
Step 6: Identify and evaluate critical points
The vertices of the feasibility region are: \((0, 0)\), \((0, 6)\), \((2, 5)\), \((5, 2)\), \((6, 0)\).
| Critical Point | Profit Calculation | Profit |
|---|---|---|
| \((0, 0)\) | \(20(0) + 30(0)\) | $0 |
| \((0, 6)\) | \(20(0) + 30(6)\) | $180 |
| \((2, 5)\) | \(20(2) + 30(5)\) | $190 |
| \((5, 2)\) | \(20(5) + 30(2)\) | $160 |
| \((6, 0)\) | \(20(6) + 30(0)\) | $120 |
Conclusion: The maximum profit is $190, achieved by manufacturing 2 regular gadgets and 5 premium gadgets daily.
Standard Maximization Problems
So far we have focused on standard maximization problems, which have the following characteristics:
- The objective function is to be maximized
- All constraints are of the form \(ax + by \leq c\)
- All variables are constrained to be non-negative: \(x \geq 0, y \geq 0\)
Now we'll consider a problem with mixed constraints—some inequalities use \(\leq\) and some use \(\geq\). The non-negativity constraints are still required.
Solve the following maximization problem graphically.
Maximize \(P = 10x + 15y\)
Subject to:
\[\begin{align} x + y &\geq 1 \\ x + 2y &\leq 6 \\ 2x + y &\leq 6 \\ x &\geq 0 \\ y &\geq 0 \end{align}\]Example 3.1.3 Solution
The graph is shown below.
Notice that the first constraint \(x + y \geq 1\) requires the feasibility region to be bounded below by the line \(x + y = 1\). When we use \((0,0)\) as a test point, it does NOT satisfy \(x + y \geq 1\) (since \(0 + 0 < 1\)), so we shade the region on the opposite side of the line from \((0,0)\).
With mixed constraints, you need to be extra careful with test points. A \(\geq\) constraint flips the shading compared to a \(\leq\) constraint. Always check your test point against each inequality before shading.
Critical points: \((1, 0)\), \((3, 0)\), \((2, 2)\), \((0, 3)\), \((0, 1)\)
| Critical Point | Profit Calculation | Profit |
|---|---|---|
| \((1, 0)\) | \(10(1) + 15(0)\) | $10 |
| \((3, 0)\) | \(10(3) + 15(0)\) | $30 |
| \((2, 2)\) | \(10(2) + 15(2)\) | $50 |
| \((0, 3)\) | \(10(0) + 15(3)\) | $45 |
| \((0, 1)\) | \(10(0) + 15(1)\) | $15 |
Conclusion: The point \((2, 2)\) maximizes the objective function with a value of $50.
Important note: If the point \((0,0)\) lies directly on a constraint line, you cannot use it as a test point for that constraint. Choose a different point that clearly lies on one side of the line.
Alternative Method: Graphing the Objective Function
Is it possible to find the optimal point without calculating the value at every critical point?
Yes! We can use a graphical approach by moving the objective function line.
Recall Example 3.1.2 (Gadget Factory), where we evaluated \(P = 20x + 30y\) at five critical points and found values of \(0, 180, 190, 160, 120\).
Alternative graphical method:
- Graph the objective function for any arbitrary value. For example, choose \(P = 60\) and graph the line \(20x + 30y = 60\).
- Move the line parallel to itself (keeping the same slope). As we move the line away from the origin, the value of \(P\) increases.
- The largest value of \(P\) occurs when the line touches the last corner point of the feasibility region before leaving it entirely.
Think of the objective function line as a "level curve" of profit. Each parallel position of the line represents a different profit level. By sliding it outward (for maximization) or inward (for minimization), you visually identify the extreme value at a corner.
The figure below shows this process. The optimum solution is achieved at the point \((2, 5)\)—the farthest critical point from the origin along the direction of increasing \(P\).
Summary: Solving Maximization Linear Programming Problems
An optimization problem in which we seek to maximize a linear objective function subject to linear inequality constraints and non-negativity requirements on all variables.
General procedure:
- Write the objective function (the quantity to be maximized).
- Write the constraints:
- For standard maximization problems, constraints are of the form \(ax + by \leq 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 simultaneously).
- Find the corner points (vertices of the feasibility region).
- Determine the corner point that gives the maximum value:
- Method A: Evaluate the objective function at each corner point.
- Method B: Graph the objective function line and slide it parallel to itself to find the farthest corner.
Problem Set 3.1
For the following maximization 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 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 1 Solution
Step 1: Define variables
Let \(x\) = acres of wheat
Let \(y\) = acres of corn
Step 2: Write the objective function
Maximize profit: \(P = 80x + 100y\)
Step 3: Write the constraints
- Labor: \(4x + 16y \leq 800\) → Simplify: \(x + 4y \leq 200\)
- Capital: \(20x + 40y \leq 2400\) → Simplify: \(x + 2y \leq 120\)
- Land: \(x + y \leq 100\)
- Non-negativity: \(x \geq 0, y \geq 0\)
Step 4: Find critical points by solving constraint intersections
Intersection of \(x + 2y = 120\) and \(x + y = 100\):
\[x + 2y = 120\] \[x + y = 100\]Subtracting: \(y = 20\), so \(x = 80\). Point: \((80, 20)\)
Intersection of \(x + 4y = 200\) and \(x = 0\):
\(4y = 200\), so \(y = 50\). Point: \((0, 50)\) — Check: \(0 + 2(50) = 100 \leq 120\) ✓, \(0 + 50 = 50 \leq 100\) ✓
Intersection of \(x + 4y = 200\) and \(x + 2y = 120\):
\[x + 4y = 200\] \[x + 2y = 120\]Subtracting: \(2y = 80\), so \(y = 40\), \(x = 40\). Check: \(40 + 40 = 80 \leq 100\) ✓. Point: \((40, 40)\)
Intersection of \(x + y = 100\) and \(y = 0\): Point: \((100, 0)\) — Check: \(100 + 2(0) = 100 \leq 120\) ✓
Step 5: Evaluate objective function at all critical points
| Critical Point | Profit Calculation | Profit |
|---|---|---|
| \((0, 0)\) | \(80(0) + 100(0)\) | $0 |
| \((0, 50)\) | \(80(0) + 100(50)\) | $5,000 |
| \((40, 40)\) | \(80(40) + 100(40)\) | $7,200 |
| \((80, 20)\) | \(80(80) + 100(20)\) | $8,400 |
| \((100, 0)\) | \(80(100) + 100(0)\) | $8,000 |
Answer: Plant 80 acres of wheat and 20 acres of corn for maximum profit of $8,400.
Verification: Check \((80, 20)\) against all constraints:
- Labor: \(80 + 4(20) = 160 \leq 200\) ✓
- Capital: \(80 + 2(20) = 120 \leq 120\) ✓
- Land: \(80 + 20 = 100 \leq 100\) ✓
- Profit: \(P = 80(80) + 100(20) = 8400\) ✓
2. Mr. Tran has $24,000 to invest, some in bonds and the rest in stocks. He has decided that the money invested in bonds must be at least twice as much as that in stocks. But the money invested in bonds must not be greater than $18,000. If the bonds earn 6%, and the stocks earn 8%, how much money should he invest in each to maximize profit?
Problem 2 Solution
Step 1: Define variables
Let \(x\) = amount invested in bonds (in dollars)
Let \(y\) = amount invested in stocks (in dollars)
Step 2: Write the objective function
Maximize return: \(R = 0.06x + 0.08y\)
Step 3: Write the constraints
- Total investment: \(x + y \leq 24000\)
- Bonds at least twice stocks: \(x \geq 2y\)
- Bonds not more than $18,000: \(x \leq 18000\)
- Non-negativity: \(x \geq 0, y \geq 0\)
Step 4: Find critical points
Intersection of \(x = 2y\) and \(x + y = 24000\):
\[2y + y = 24000 \implies 3y = 24000 \implies y = 8000, \quad x = 16000\]Check: \(16000 \leq 18000\) ✓. Point: \((16000, 8000)\)
Intersection of \(x = 18000\) and \(x + y = 24000\):
\[18000 + y = 24000 \implies y = 6000\]Check: \(18000 \geq 2(6000) = 12000\) ✓. Point: \((18000, 6000)\)
Intersection of \(x = 2y\) and \(y = 0\): Point: \((0, 0)\)
Intersection of \(x = 18000\) and \(y = 0\): Point: \((18000, 0)\) — Check: \(18000 \geq 2(0)\) ✓
Step 5: Evaluate objective function at critical points
| Critical Point | Return Calculation | Return |
|---|---|---|
| \((0, 0)\) | \(0.06(0) + 0.08(0)\) | $0 |
| \((16000, 8000)\) | \(0.06(16000) + 0.08(8000)\) | $1,600 |
| \((18000, 6000)\) | \(0.06(18000) + 0.08(6000)\) | $1,560 |
| \((18000, 0)\) | \(0.06(18000) + 0.08(0)\) | $1,080 |
Answer: Invest $16,000 in bonds and $8,000 in stocks for maximum annual return of $1,600.
Verification: Check \((16000, 8000)\) against all constraints:
- Total: \(16000 + 8000 = 24000 \leq 24000\) ✓
- Bonds ≥ 2×stocks: \(16000 \geq 2(8000) = 16000\) ✓
- Bonds ≤ $18,000: \(16000 \leq 18000\) ✓
- Return: \(R = 0.06(16000) + 0.08(8000) = 1600\) ✓
3. A factory manufactures chairs and tables, each requiring the use of three operations: Cutting, Assembly, and Finishing. The first operation can be used at most 40 hours; the second at most 42 hours; and the third at most 25 hours. A chair requires 1 hour of cutting, 2 hours of assembly, and 1 hour of finishing; a table needs 2 hours of cutting, 1 hour of assembly, and 1 hour of finishing. If the profit is $20 per unit for a chair and $30 for a table, how many units of each should be manufactured to maximize revenue?
Problem 3 Solution
Step 1: Define variables
Let \(x\) = number of chairs
Let \(y\) = number of tables
Step 2: Write the objective function
Maximize revenue: \(R = 20x + 30y\)
Step 3: Write the constraints
- Cutting: \(x + 2y \leq 40\)
- Assembly: \(2x + y \leq 42\)
- Finishing: \(x + y \leq 25\)
- Non-negativity: \(x \geq 0, y \geq 0\)
Step 4: Find critical points
Intersection of \(x + 2y = 40\) and \(x + y = 25\):
Subtracting: \(y = 15\), so \(x = 10\). Check assembly: \(2(10) + 15 = 35 \leq 42\) ✓. Point: \((10, 15)\)
Intersection of \(2x + y = 42\) and \(x + y = 25\):
Subtracting: \(x = 17\), so \(y = 8\). Check cutting: \(17 + 2(8) = 33 \leq 40\) ✓. Point: \((17, 8)\)
Intersection of \(2x + y = 42\) and \(y = 0\): Point: \((21, 0)\) — Check: \(21 \leq 40\) ✓, \(21 \leq 25\) ✓
Intersection of \(x + 2y = 40\) and \(x = 0\): Point: \((0, 20)\) — Check: \(20 \leq 42\) ✓, \(20 \leq 25\) ✓
Step 5: Evaluate objective function at critical points
| Critical Point | Revenue Calculation | Revenue |
|---|---|---|
| \((0, 0)\) | \(20(0) + 30(0)\) | $0 |
| \((0, 20)\) | \(20(0) + 30(20)\) | $600 |
| \((10, 15)\) | \(20(10) + 30(15)\) | $650 |
| \((17, 8)\) | \(20(17) + 30(8)\) | $580 |
| \((21, 0)\) | \(20(21) + 30(0)\) | $420 |
Answer: Manufacture 10 chairs and 15 tables for maximum revenue of $650.
Verification: Check \((10, 15)\) against all constraints:
- Cutting: \(10 + 2(15) = 40 \leq 40\) ✓
- Assembly: \(2(10) + 15 = 35 \leq 42\) ✓
- Finishing: \(10 + 15 = 25 \leq 25\) ✓
- Revenue: \(R = 20(10) + 30(15) = 650\) ✓
4. The Silly Nut Company makes two mixtures of nuts: Mixture A and Mixture B. A pound of Mixture A contains 12 oz of peanuts, 3 oz of almonds and 1 oz of cashews and sells for $4. A pound of Mixture B contains 12 oz of peanuts, 2 oz of almonds and 2 oz of cashews and sells for $5. The company has 1080 lb. of peanuts, 240 lb. of almonds, 160 lb. of cashews. How many pounds of each of mixtures A and B should the company make to maximize profit?
(Hint: Use consistent units. Work the entire problem in pounds by converting all values given in ounces into fractions of pounds).
Problem 4 Solution
Step 1: Convert ounces to pounds
- Mixture A per pound: \(\frac{12}{16} = 0.75\) lb peanuts, \(\frac{3}{16} = 0.1875\) lb almonds, \(\frac{1}{16} = 0.0625\) lb cashews
- Mixture B per pound: \(\frac{12}{16} = 0.75\) lb peanuts, \(\frac{2}{16} = 0.125\) lb almonds, \(\frac{2}{16} = 0.125\) lb cashews
Step 2: Define variables
Let \(x\) = pounds of Mixture A
Let \(y\) = pounds of Mixture B
Step 3: Write the objective function
Maximize profit: \(P = 4x + 5y\)
Step 4: Write the constraints
- Peanuts: \(0.75x + 0.75y \leq 1080\) → Simplify: \(x + y \leq 1440\)
- Almonds: \(0.1875x + 0.125y \leq 240\) → Multiply by 16: \(3x + 2y \leq 3840\)
- Cashews: \(0.0625x + 0.125y \leq 160\) → Multiply by 16: \(x + 2y \leq 2560\)
- Non-negativity: \(x \geq 0, y \geq 0\)
Step 5: Find critical points
Intersection of \(x + 2y = 2560\) and \(x = 0\): Point: \((0, 1280)\)
Intersection of \(3x + 2y = 3840\) and \(y = 0\): Point: \((1280, 0)\)
Intersection of \(x + y = 1440\) and \(3x + 2y = 3840\):
\[y = 1440 - x \implies 3x + 2(1440 - x) = 3840 \implies x = 960, \quad y = 480\]Check cashews: \(960 + 2(480) = 1920 \leq 2560\) ✓. Point: \((960, 480)\)
Intersection of \(x + y = 1440\) and \(x + 2y = 2560\):
\[x = 1440 - y \implies (1440 - y) + 2y = 2560 \implies y = 1120, \quad x = 320\]Check almonds: \(3(320) + 2(1120) = 3200 \leq 3840\) ✓. Point: \((320, 1120)\)
Step 6: Evaluate objective function at critical points
| Critical Point | Profit Calculation | Profit |
|---|---|---|
| \((0, 0)\) | \(4(0) + 5(0)\) | $0 |
| \((0, 1280)\) | \(4(0) + 5(1280)\) | $6,400 |
| \((1280, 0)\) | \(4(1280) + 5(0)\) | $5,120 |
| \((960, 480)\) | \(4(960) + 5(480)\) | $6,240 |
| \((320, 1120)\) | \(4(320) + 5(1120)\) | $6,880 |
Answer: Make 320 pounds of Mixture A and 1120 pounds of Mixture B for maximum profit of $6,880.
Verification: Check \((320, 1120)\) against all constraints:
- Peanuts: \(320 + 1120 = 1440 \leq 1440\) ✓
- Almonds: \(3(320) + 2(1120) = 960 + 2240 = 3200 \leq 3840\) ✓
- Cashews: \(320 + 2(1120) = 2560 \leq 2560\) ✓
- Profit: \(P = 4(320) + 5(1120) = 1280 + 5600 = 6880\) ✓
5. Maximize: \(Z = 4x + 10y\)
Subject to:
\[\begin{align} x + y &\leq 5 \\ 2x + y &\leq 8 \\ x + 2y &\leq 8 \\ x &\geq 0, \quad y \geq 0 \end{align}\]Problem 5 Solution
Step 1: Identify the constraints and objective function
Maximize: \(Z = 4x + 10y\)
Step 2: Find critical points
Intersection of \(x + y = 5\) and \(2x + y = 8\): Subtracting: \(x = 3\), \(y = 2\). Check: \(3 + 2(2) = 7 \leq 8\) ✓. Point: \((3, 2)\)
Intersection of \(x + y = 5\) and \(x + 2y = 8\): Subtracting: \(y = 3\), \(x = 2\). Check: \(2(2) + 3 = 7 \leq 8\) ✓. Point: \((2, 3)\)
Intersection of \(x + 2y = 8\) and \(x = 0\): Point: \((0, 4)\) — Check: \(0 + 4 = 4 \leq 5\) ✓
Intersection of \(2x + y = 8\) and \(y = 0\): Point: \((4, 0)\) — Check: \(4 + 0 = 4 \leq 5\) ✓
Step 3: Evaluate objective function at critical points
| Critical Point | Objective Calculation | Value |
|---|---|---|
| \((0, 0)\) | \(4(0) + 10(0)\) | $0 |
| \((0, 4)\) | \(4(0) + 10(4)\) | $40 |
| \((2, 3)\) | \(4(2) + 10(3)\) | $38 |
| \((3, 2)\) | \(4(3) + 10(2)\) | $32 |
| \((4, 0)\) | \(4(4) + 10(0)\) | $16 |
Answer: The maximum value is \(Z = 40\) at the point (0, 4).
Verification: Check \((0, 4)\) against all constraints:
- \(0 + 4 = 4 \leq 5\) ✓
- \(2(0) + 4 = 4 \leq 8\) ✓
- \(0 + 2(4) = 8 \leq 8\) ✓
- Objective: \(Z = 4(0) + 10(4) = 40\) ✓
6. This maximization linear programming problem is not in "standard" form. It has mixed constraints, some involving \(\leq\) inequalities and some involving \(\geq\) inequalities. However, with careful graphing, we can solve this using the techniques we have learned in this section.
Maximize \(Z = 5x + 7y\)
Subject to:
\[\begin{align} x + y &\leq 30 \\ 2x + y &\leq 50 \\ 4x + 3y &\geq 60 \\ 2x &\geq y \\ x &\geq 0, \quad y \geq 0 \end{align}\]Problem 6 Solution
Step 1: Identify the constraints and objective function
Maximize: \(Z = 5x + 7y\)
Constraints (mixed):
- \(x + y \leq 30\)
- \(2x + y \leq 50\)
- \(4x + 3y \geq 60\)
- \(2x \geq y\) (or \(y \leq 2x\))
- \(x \geq 0, y \geq 0\)
Step 2: Find critical points
Intersection of \(x + y = 30\) and \(2x + y = 50\): Subtracting: \(x = 20\), \(y = 10\). Check: \(4(20) + 3(10) = 110 \geq 60\) ✓, \(2(20) = 40 \geq 10\) ✓. Point: \((20, 10)\)
Intersection of \(x + y = 30\) and \(y = 2x\):
\[x + 2x = 30 \implies 3x = 30 \implies x = 10, \quad y = 20\]Check: \(2(10) + 20 = 40 \leq 50\) ✓, \(4(10) + 3(20) = 100 \geq 60\) ✓. Point: \((10, 20)\)
Intersection of \(4x + 3y = 60\) and \(y = 2x\):
\[4x + 3(2x) = 60 \implies 10x = 60 \implies x = 6, \quad y = 12\]Check: \(6 + 12 = 18 \leq 30\) ✓, \(2(6) + 12 = 24 \leq 50\) ✓. Point: \((6, 12)\)
Intersection of \(4x + 3y = 60\) and \(y = 0\): Point: \((15, 0)\)
Intersection of \(2x + y = 50\) and \(y = 0\): Point: \((25, 0)\)
Step 3: Evaluate objective function at critical points
| Critical Point | Objective Calculation | Value |
|---|---|---|
| \((6, 12)\) | \(5(6) + 7(12)\) | $114 |
| \((10, 20)\) | \(5(10) + 7(20)\) | $190 |
| \((20, 10)\) | \(5(20) + 7(10)\) | $170 |
| \((25, 0)\) | \(5(25) + 7(0)\) | $125 |
| \((15, 0)\) | \(5(15) + 7(0)\) | $75 |
Answer: The maximum value is \(Z = 190\) at the point (10, 20).
Verification: Check \((10, 20)\) against all constraints:
- \(10 + 20 = 30 \leq 30\) ✓
- \(2(10) + 20 = 40 \leq 50\) ✓
- \(4(10) + 3(20) = 100 \geq 60\) ✓
- \(2(10) = 20 \geq 20\) ✓
- Objective: \(Z = 5(10) + 7(20) = 190\) ✓