Reading: Meeting Demands with Linear Programming
Wouldn't it be nice if we could simply produce and sell infinitely many units of a product and thus make a never-ending amount of money? In business (and in day-to-day living) we know that we cannot simply choose to do something because it would make sense that it would (unreasonably) accomplish our goal. Instead, our hope is to maximize or minimize some quantity, given a set of constraints. Think about this: you are traveling from Chandler, AZ, to San Diego, CA. Your hope is to get there in as little time as possible, hence aiming to minimize travel time. At the same time, you will be facing more or less traffic on certain stretches of the trip, you will need to stop for gas at least once (unless you are driving a hybrid vehicle), and, if you have kids, you'll definitely need to stop for a restroom break. While we have only mentioned a few, these are all constraints—things that limit you in your goal to get to your destination in as little time as possible.Solving Linear Programming Problems Graphically
A linear programming problem involves constraints that contain inequalities. An inequality is denoted with familiar symbols, <, >, $latex \le $, and $latex \ge $. Due to difficulties with strict inequalities (< and >), we will only focus on$latex \le $ and$latex \ge $. In order to have a linear programming problem, we must have:- Inequality constraints
- An objective function, that is, a function whose value we either want to be as large as possible (want to maximize it) or as small as possible (want to minimize it).
Example 1
An airline offers coach and first-class tickets. For the airline to be profitable, it must sell a minimum of 25 first-class tickets and a minimum of 40 coach tickets. The company makes a profit of $225 for each coach ticket and $200 for each first-class ticket. At most, the plane has a capacity of 150 travelers. How many of each ticket should be sold in order to maximize profits?Solution
The first step is to identify the unknown quantities. We are asked to find the number of each ticket that should be sold. Since there are coach and first-class tickets, we identify those as the unknowns. Let, x = # of coach tickets y = # of first-class tickets Next, we need to identify the objective function. The question often helps us identify the objective function. Since the goal is the maximize profits, our objective is identified. Profit for coach tickets is $225. If c coach tickets are sold, the total profit for these tickets is 225 × c. Profit for first-class tickets is $200. Similarly, if f first-class tickets are sold, the total profit for these tickets is 200 × f. The total profit, P, is P = 225c + 200f We want to make the value of as large as possible, provided the constraints are met. In this case, we have the following constraints:- Sell at least 25 first-class tickets
- Sell at least 40 coach tickets
- No more than 150 tickets can be sold (no more than 150 people can fit on the plane)
- At least 25 first-class tickets means that 25 or more should be sold. That is, f $latex \ge $ 25
- At least 40 coach tickets means that 40 or more should be sold. That is, c $latex \ge $ 40
- The sum of first-class and coach tickets should be 150 or fewer. That is c + f $latex \le $ 150
Fundamental Theorem of Linear Programming
- If a solution exists to a bounded linear programming problem, then it occurs at one of the corner points.
- If a feasible region is unbounded, then a maximum value for the objective function does not exist.
- If a feasible region is unbounded, and the objective function has only positive coefficients, then a minimum value exist
System 1
c = 40 c + f = 150System 2
c = 40 f = 25System 3
f = 25 c + f = 150 We could decide to solve by using matrix equations, but these equations are all simple enough to solve by hand:System 1
(40) + f = 150 f = 110 Point:(40,110)System 2
Point already given Point: (40,25)System 3
c + 25 = 150 c = 125 Point: (125,25) We test each of these three points in the objective function:Point | Profit |
(40,110) | 225(40) + 200(110) = $ 31,000 |
(40,25) | 225(40) + 200(25) = $14,000 |
(125,25) | 225(125) + 200(25) = $33,125 |
Solving a Linear Programming Problem Graphically
- Define the variables to be optimized. The question asked is a good indicator as to what these will be.
- Write the objective function in words, then convert to mathematical equation
- Write the constraints in words, then convert to mathematical inequalities
- Graph the constraints as equations
- Shade feasible regions by taking into account the inequality sign and its direction. If,
$latex \le $, then shade to the left
$latex \ge $, then shade to the right
b) A horizontal line$latex \le $, then shade below
$latex \ge $, then shade above
c) A line with a non-zero, defined slope$latex \le $, shade below
$latex \ge $, shade above
6. Identify the corner points by solving systems of linear equations whose intersection represents a corner point.
7. Test all corner points in the objective function. The "winning" point is the point that optimizes the objective function (biggest if maximizing, smallest if minimizing)
There is one instance in which we must take great caution. First, consider the (true) inequality, 5 > 3 Suppose we were to divide both sides by –1. Would it still be true to say the following? [latex-display]\displaystyle\frac{{5}}{{-{1}}}\gt\frac{{3}}{{-{1}}}[/latex-display] [latex-display]\displaystyle-{5}\gt-{3}[/latex-display] Clearly, –5 is not larger than –3! To keep the statement true, we should change the direction of the inequality sign so that, –5 < –3 We can see by the number line below, that the two sets of numbers are symmetric about 0, except that the way in which we describe size is opposite. This justifies that we should also use the opposite sign when we reflect values to the other side of 0.Changing the Inequality Sign
When multiplying/dividing any inequality by –1, the direction of the inequality should changeExample 2
A health-food business would like to create a high-potassium blend of dried fruit in the form of a box of 10 fruit bars. It decides to use dried apricots, which have 407 mg of potassium per serving, and dried dates, which have 271 mg of potassium per serving (SOURCE: www.thepotassiumrichfoods.com). The company can purchase its fruit through www.driedfruitbaskets.com in bulk for a reasonable price. Dried apricots cost $9.99/lb. (about 3 servings) and dried dates cost $7.99/lb. (about 4 servings). The company would like the box of bars to have at least the recommended daily potassium intake of about 4700 mg, but would like to keep it under twice the recommended daily intake. In order to minimize cost, how many servings of each dried fruit should go into the box of bars?Solution
We begin by defining the variables. Let, x = # of servings of dried apricots y = # of servings of dried dates We next work on the objective function. For apricots, there are 3 servings in one pound. This means that the cost per serving is $9.99/3 = $3.33. The cost for x servings would thus be 3.33 × x. For dates, there are 4 servings per pound. This means that the cost per serving is $7.99/4 $2.00. The cost for y servings would thus be 2.00y. The total cost for apricots and dates would be C = 3.33x + 2.00y We have two major constraints (in addition to the constraints that x $latex \ge $ 0 and y $latex \ge $ 0, given that negative servings cannot be used):- Product must contain at least 4700mg of potassium
- Product should contain no more than 4700 × 2 = 9400mg of potassium
- There are 407 × x mg of potassium in x servings of apricots and 271 × y mg of potassium in y servings of dates. The sum should be greater than or equal to 4700mg of potassium, or 407x + 271y $latex \ge $ 4700
- The same sum should be less than or equal to 9400 mg of potassium, or 407x + 271y $latex \le $ 9400.
System 1
x = 0 407x + 271y =4700System 2
x = 0 407x + 271y = 9400System 3
y = 0 407x + 271y = 4700System 4
y = 0 407x + 271y = 9400 Again, we could solve by using matrix equations, but the systems are straightforward to solve by substitution:System 1
0 + 271 y = 4700 y ≈ 17.3 Point: (0,17.3)System 2
0 + 271 y = 9400 y ≈ 34.7 Point: (0,34.7)System 3
407 x + 0 = 4700 x ≈ 11.5 Point: (11.5,0)System 4
407 x + 0 = 9400 x ≈ 23.1 Point: (23.1,0) Since the problem is bounded, we now check to see which one minimizes cost:Point | Cost |
(0,17.3) | 33.3(0) = 2.00(17.3) = $34.60 |
(0,34.7) | 33.3(0) = 2.00(34.7) = $69.40 |
(11.5,0) | 33.3(11.5) = 2.00(0) = $38.30 |
(23.1,0) | 33.3(23.1) = 2.00(0) = $76.92 |
Example 3
A human resources office is working to implement an increase in starting salaries for new administrative secretaries and faculty at a community college. An administrative secretary starts at $28,000 and new faculty receive $40,000. The college would like to determine the percentage increase to allocate to each group, given that the college will be hiring 8 secretaries and 7 faculty in the upcoming academic year. The college has at most $5,000 to put towards raises. What should the percentage increase be for each group?Solution
Our goal is to determine the percentage increase for administrative secretaries and faculty, so let x = percentage increase for secretaries y = percentage increase for faculty The college would like to minimize its total expenditures, so the objective function must include the total amount of money outflows. Since the new secretaries will require a total budget of $28,000 × 8 = $224,000 and the faculty a total budget of $40,000 × 7 = $280,000, the total cost will be the raise percentage for each group, multiplied by the total salaries: C = x × 224 + y × 280 C = 224x + 280y There is one constraint given, which is that the total raises must be $5,000 or less. That is, 224x + 280y $latex \le $ 5 Of course, the college does not want to reduce the salaries, so x $latex \ge $ 0 and y $latex \ge $ 0. To visualize the situation, we graph the constraint as an equation. To help us find points, we first find the intercepts: Horizontal Intercept: 224(0) + 280 y = 5 y ≈ .018 Vertical Intercept 224x + 280(0) = 5 x ≈ .022 We then plot the points and connect them with a straight line: Since the inequality sign is $latex \le $, we shade below the line: This gives us three corner points, as shown above. We test each to verify which of the pairs of percentages gives the minimum cost:Point | Cost |
(0,0) | 224(0) + 280(0) = $ |
(0,.018) | 224(0) + 280(.018) = $ |
(.020,0) | 224(.020) + 280(0) = $ |
Practice Problems
- Solve each of the following linear programming problems.
- Maximize R = 2x + 3y Subject to constraints,x $latex \ge $ 0 y $latex \ge $ 0 –2x – y $latex \ge $ –10 x + 3$latex \ge $ 6
- Minimize T = 3x + ySubject to constraints,x $latex \ge $0 y $latex \ge $ 0 x + 2y$latex \ge $ 4 x + 3y $latex \ge $ 6
- A local school governing board approves a new math education program that is to be implemented at a series of elementary schools within the district. Money for the program will come from two different budgets: public expenditures budget and grade-school initiatives budget. The board is willing to pay at least half of what comes out of the initiatives budget from its public expenditures budget. Since this program is considered an initiative, the government mandates that at least $2,000 comes from the local initiatives budget. Both budgets are partially funded by federal emergency funding. For the public expenditures budget, the percentage is 55% and 23% for the grade-school initiatives budget. In order to properly use emergency funding, the district would like to minimize the use of federal dollars. How much should come from each budget?
- A public relations director for a homeopathic is seeking to advertise her company's products on two different websites—one is a medical parts supplier and the other is a fitness e-zine (a web-based magazine). The medical parts supplier website receives, on average, about 1,200,000 hits per day per page, while the fitness e-zine receives about 2,000,000 hits per day per page. The daily cost to advertise is $1,100 per advertisement and $1,600 per advertisement, respectively. The director would like at least 15 ads and is able to allocate up to $50,000 for advertising. At least 3 ads should be placed on each website. How many adds should be placed on each website to maximize the potential number of readers (even if some viewers see the add on different pages of the website)?
- Reconsider the conclusions of Example 2: A health-food business would like to create a high-potassium blend of dried fruit in the form of a box of 10 fruit bars. It decides to use dried apricots, which have 407 mg of potassium per serving, and dried dates, which have 271 mg of potassium per serving (Source: www.thepotassiumrichfoods.com). The company can purchase its fruit through www.driedfruitbaskets.com in bulk for a reasonable price. Dried apricots cost $9.99/lb. (about 3 servings) and dried dates cost $7.99/lb. (about 4 servings). The company would like the box of bars to have at least the recommended daily potassium intake of about 4700 mg, but would like to keep it under twice the recommended daily intake.On top of the original constraints above, suppose that the company determines that it can process at most 10 servings of dates and at most 30 servings of apricots per box. In order to minimize cost, how many servings of each dried fruit should go into the box of bars?Using the information given in the problem and the new constraints,A health-food business would like to create a high-potassium blend of dried fruit in the form of a box of 10 fruit bars. It decides to use dried apricots, which have 407 mg of potassium per serving, and dried dates, which have 271 mg of potassium per serving (Source:
www.thepotassiumrichfoods.com). The company can purchase its fruit through www.driedfruitbaskets.com in bulk for a reasonable price. Dried apricots cost $9.99/lb. (about 3 servings) and dried dates cost $7.99/lb. (about 4 servings). The company would like the box of bars to have at least the recommended daily potassium intake of about 4700 mg, but would like to keep it under twice the recommended daily intake.On top of the original constraints above, suppose that the company determines that it can process at most 10 servings of dates and at most 30 servings of apricots per box. In order to minimize cost, how many servings of each dried fruit should go into the box of bars?Using the information given in the problem and the new constraints,
- Does the optimal number of servings of each change? What is the new cost?
- Why does this change take place? Give numerical support.
- In addition to the new manufacturing constraints in Problem 4, suppose also that each serving of dates takes up 2 in3 of packaging and that each serving of apricots takes up 3 in3 of packaging. If the company can process at most 73 in3 per box.
- Does the optimal number of servings of each change? What is the new cost?
- Why does this change take place? Give numerical support.
Licenses & Attributions
CC licensed content, Shared previously
- By the Numbers, Meeting Demands with Linear Programming. Authored by: Milos Podmanik. License: CC BY: Attribution.