constraints—things that limit you in your goal to get to your destination in as little time as possible.
A linear programming problem involves constraints that contain inequalities. Aninequality is denoted with familiar symbols, <,>,
≤ \le ≤
, and≥ \ge ≥
. Due to difficulties with strict inequalities (< and >), we will only focus on≤ \le ≤
and≥ \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).
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. Ifx coach tickets are sold, the total profit for these tickets is 225x.
Profit for first-class tickets is $200. Similarly, ify first class tickets are sold, the total profit for these tickets is 200y.
The total profit, P, is
P = 225x + 200y
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, y
≥ \ge ≥
25 - At least 40 coach tickets means that 40 or more should be sold. That is, x
≥ \ge ≥
40 - The sum of first-class and coach tickets should be 150 or fewer. That is x + y
≤ \le ≤
150
Objective Function: P = 225x + 200y
Constraints: y
≥ \ge ≥
25; x≥ \ge ≥
40; x + y≤ \le ≤
150 We will work to think about these constraints graphically and return to the objective function afterwards. We will thus deal with the following graph:
x= 25
y = 40
x + y = 150
The first two equations are horizontal and vertical lines, respectively. To plot x + y= 150, it is preferable to find the horizontal and vertical intercepts.
To find the vertical intercept, we letx = 0:
y= 150
Giving us the point (0,150) To find the horizontal intercept, we lety = 0:
x = 150
Giving us the point (150,0) Plotting all three equations gives:
We first ask, when is y
≥ \ge ≥
25? Since this is a horizontal line running through a y-value of 25, anything above this line represents a value greater than 25. We denote this by shading above the line:
y
≥ \ge ≥
25. Next, we deal withx
≥ \ge ≥
40. We ask, when is the x-value larger than 40? Values to the left are smaller than 40, so we must shade to the right to get values larger than 40:
all constraints, only the region that is green and blue will suffice.
We have one more constraint to consider:x+ y
≥ \ge ≥
150. We have two options, either shade below or shade above. To help us better see that we will, in fact, need to shade below the line, let us consider an ordered pair in both regions. Selecting an ordered pair above the line, such as (64, 130) gives:64 + 130
≥ \ge ≥
150 Which is a false statement since 64 + 130 = 194, a value larger than 150. According to the graph, the point (64, 65) is one that falls below the graph. Putting this pair in yields the statement:64 + 65
≥ \ge ≥
150 Which is a true statement since 64+65 is 129, a value smaller than 150.
64
≥ \ge ≥
40 TRUE65
≥ \ge ≥
25 TRUE64 + 65
≥ \ge ≥
150 TRUE This gets us to a great point, but still does not answer the question:which point maximizes profit? Fortunately, there is a theorem discovered by mathematicians that allows us to answer this question.
First off, we define a new term: a corner point is a point that falls along the corner of a feasible region. In our situation, we have three corner points, shown on the graph as the solid black dots:
- 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
x + y = 150
x = 40y= 25
y = 25x+ y = 150
We could decide to solve by using matrix equations, but these equations are all simple enough to solve by hand: (40) + y = 150y = 110
Point:(40,110) Point already given Point: (40,25) x + 25 = 150x = 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 |
- 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,
≤ \le ≤
, then shade to the left≥ \ge ≥
, then shade to the right b) A horizontal line≤ \le ≤
, then shade below≥ \ge ≥
, then shade above c) A line with a non-zero, defined slope≤ \le ≤
, shade below≥ \ge ≥
, shade above6. 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?5−1>3−1\displaystyle\frac{{5}}{{-{1}}}\gt\frac{{3}}{{-{1}}}−15>−13
−5>−3\displaystyle-{5}\gt-{3}−5>−3
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.
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?
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 forx servings would thus be 3.33x.
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 beC = 3.33x + 2.00y
We have two major constraints (in addition to the constraints thatx
≥ \ge ≥
0and y
≥ \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 407x mg of potassium in x servings of apricots and 271y mg of potassium in y servings of dates. The sum should be greater than or equal to 4700mg of potassium, or 407x + 271y
≥ \ge ≥
4700 - The same sum should be less than or equal to 9400 mg of potassium, or 407x + 271y
≤ \le ≤
9400.
Objective Function: C = 3.33x + 2.00y Subject To Constraints:
407x + 271y
≥ \ge ≥
4700407x + 271y
≤ \le ≤
9400x
≥ \ge ≥
0y
≥ \ge ≥
0 We graph the constraints as equations:
≥ \ge ≥
, we must shade above and, since the second inequality has≤ \le ≤
, we must shade below (This idea can be confirmed by selecting points above and below each line in order to verify.):
407x + 271y =4700
Solution:
0 + 271y = 4700
y ≈ 17.3
Point: (0,17.3) x = 0407x + 271y = 9400
Solution:
0 + 271y = 9400
y ≈ 34.7
Point: (0,34.7) y = 0407x + 271y = 4700
Solution:
407x + 0 = 4700
x ≈ 11.5
Point: (11.5,0) y = 0407x + 271y = 9400
Solution:
407x + 0 = 9400
x ≈ 23.1
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 |
407mg$3.33≈122.2\displaystyle\frac{{{407}{m}{g}}}{{\${3.33}}}\approx{122.2}$3.33407mg≈122.2
mg per dollar for apricots and271mg$2.00≈135.5\displaystyle\frac{{{271}{m}{g}}}{{\${2.00}}}\approx{135.5}$2.00271mg≈135.5
mg per dollar for dates It makes complete sense to buy dates, since the same dollar amount yields a higher content of potassium. The question still remains: is it desirable to require a larger quantity of dates for a smaller price, or is it more desirable to require a smaller quantity of apricots for a larger price? This indeed depends on the constraints. The company might want to consider the amount of packaging/processing/etc. required in both instances. Perhaps the manufacturing and packaging costs could add constraints that alter the decision-making process. A similar problem will be left as a homework exercise for the reader to think about. As a mathematical note, what we are seeing occurs as a result of having constraint lines that are parallel.There are two terms we should be familiar with when dealing with inequalities: bounded and unbounded. A feasible region is said to be bounded if the constraints enclose the feasible region.
That is, if the shading does not continue to cover the entire plane, we are dealing with a bounded linear programming problem. Both examples thus far have been examples of bounded linear programming problems, since the first feasible region was in the shape of a triangle and the second in the shape of a trapezoid. If the feasible region cannot be enclosed among the lines formed by constraints, it is said to be unbounded. An example of an unbounded linear programming problem would be:
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 = 224x + 280y
There is one constraint given, which is that the total raises must be $5,000 or less. That is,224x + 280y
≤ \le ≤
5 Of course, the college does not want to reduce the salaries, sox
≥ \ge ≥
0 and y≥ \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:
≤ \le ≤
, we shade below the line:
Point | Cost |
(0,0) | 224(0) + 280(0) = $0 |
(0,.018) | 224(0) + 280(.018) = $5.04 |
(.020,0) | 224(.020) + 280(0) = $4.48 |
a) Maximize R = 2x + 3y Subject to –2x – y
≥ \ge ≥
–10x
x≥ \ge ≥
0y
Solution: R=30 at (0,10)B) Minimize T = 3x + y Subject to
x
+ 2y
≥ \ge ≥
4x + 3y
≥ \ge ≥
6 x≥ \ge ≥
0y
Solution: R=2 at (0,2) 2) 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? Solution: x=amount from publix expenditures; y=amount from grade school initiatives Minimize: C=0.55x+0.23y (1/2)x≥y or {(1/2)x-y≥0} y≥2000 x,y≥0 Solution: C=2660, x=4000, y=2000 3) 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)? x=number on medical website; y= number on fitness website. Maximize: R=1200000x+2000000y Subject to: x+y≥15 1100x+1600y≤50000 x≥3 y≥3 x,y≥0Corner Points | R=1200000x+2000000y |
(3,12) | 27,600,000 |
(12,3) | 20,400,000 |
(3,29.2) | 62,000,000 |
(41.1,3) | 55,320,000 |
CC licensed content, Shared previously
- By the Numbers, Meeting Demands with Linear Programming. Authored by: Milos Podmanik. License: CC BY: Attribution
Page 2
patrickJMT, "Linear Programming," licensed under a Standard YouTube license.