Linear Programming

Many problems in real life are concerned with obtaining the best result within given constraints. In the business world, people would like to maximise profits and minimise loss; in production, people are interested in maximising productivity and minimising 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 + , 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.

Solving Linear Programming Problems

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.

b) Plot the inequalities on the Cartesian grid and show the region that satisfies all the inequalities. Label the region S.

c) Oranges cost $0.70 each and peaches cost $0.90 each. Find the maximum that Joanne can spend buying the fruits.

Solution:

a) at least 5 oranges: x ≥ 5

oranges less than twice of peaches: x < 2y

not more than 3.6 kg: 150x + 100y ≤ 3600 ⇒ 3x + 2y ≤ 72

b) Write out the equations for the inequalities and draw them on the graph paper. Choose the scales so that the feasible region is shown fully within the grid. (if necessary, draft it out on a graph paper first.) Shade out all the unwanted regions and label the required region S.

c) 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 video gives another example of a linear programming problem and how to test the vertices.

 

 

 

 

Custom Search

 

We welcome your feedback, comments and questions about this site - please submit your feedback via our Feedback page.

 

© Copyright 2005, 2009 - onlinemathlearning.com
Embedded content, if any, are copyrights of their respective owners.

---

Useful Links:
More Geometry Help on MathWorld