Many problems in real life are concerned with obtaining the best result within given constraints. In the business world, people would like to maximize profits and minimize loss; in production, people are interested in maximizing productivity and minimizing cost. However, there are constraints like the budget, number of workers, production capacity, space, etc. Linear programming deals with this type of problems using inequalities and graphical solution method.
Example:
On the graph below, R is the region of feasible solutions defined by inequalities y > 2, y = x + 1 and 5y + 8x < 92. Find the greatest value of 2y + x which satisfies the set of inequalities, where x and y are integers.
Solution:
We are looking for integer values of x and y in the region R where 2y + x has the greatest value. We could substitute all the possible (x , y) values in R into 2y + x to get the largest value but that would be too long and tedious.
A better method would be to find the line 2y + x = c where x and y are in R and c has the largest possible value. In this case, the equation 2y + x = c is known as the linear objective function.
Rewriting 2y + x = c as y = – x + c, we find that the gradient of the line is –
. We need to find a line with gradient –
, within the region R that has the greatest value for c.
Draw a line on the graph with gradient – . (Any line with a gradient of –
would be acceptable).
To look for the line, within R , with gradient – and the greatest value for c, we need to find the line parallel to the line drawn above that has the greatest value for c (the y-intercept). We can use the technique in the previous section to construct parallel lines. We will draw parallel lines with increasing values of c. (Increasing values of c means we move upwards). We will stop at the parallel line with the largest c that has the last integer value of (x , y) in the region R.
Now, we have all the steps that we need for solving linear programming problems, which are:
Step 1: Interpret the given situations or constraints into inequalities.
Step 2: Plot the inequalities graphically and identify the feasible region.
Step 3: Determine the gradient for the line representing the solution (the linear objective function).
Step 4: Construct parallel lines within the feasible region to find the solution.
Example:
Joanne wants to buy x oranges and y peaches from the store. She must buy at least 5 oranges and the number of oranges must be less than twice the number of peaches. An orange weighs 150 grams and a peach weighs 100 grams. Joanne can carry not more than 3.6 kg of fruits home.
a) Write 3 inequalities to represent the information given above.Solution:
a) at least 5 oranges: x ≥ 5c) We need to find the maximum that Joanne can spend buying the fruits. This would mean looking for the maximum value of c for 70x + 90y = c .
70x + 90y = c
y =
We need to find the line with gradient with maximum value of c such that (x, y) is in the region S
Plot a line and with gradient move it to find the maximum within the region S. Draw parallel lines with increasing values of c. (Increasing values of c means we move upwards). Stop at the parallel line with the largest c that has the last integer value of (x , y) in the region S.
The maximum value is found at (5,28) i.e. 5 oranges and 28 peaches. Therefore, the maximum that Joanne can spend on the fruits is: 70 × 5 + 90 × 28 = 2870 cents = $28.70.
It also possible to test the vertices of the feasible region to find the minimum or maximum values, instead of using the linear objective function. The following videos gives examples of linear programming problems and how to test the vertices.
Linear Programming
Example:
Maximize C = x + y given the constraints,
y ≥ 0
x ≥ 0
4x + 2y ≤ 8
2x − y ≤ 0
Try the free Mathway calculator and
problem solver below to practice various math topics. Try the given examples, or type in your own
problem and check your answer with the step-by-step explanations.
We welcome your feedback, comments and questions about this site or page. Please submit your feedback or enquiries via our Feedback page.