Linear Programming

Finding the most profit, or the least cost, when time, money and material are limited is an everyday problem for a shop, a farm or a factory. Linear programming is a method for it. “Programming” here is an old word for planning, not computer programs: in the 1940s the United States Air Force called its plans for training, supplies and moving people “programs”. “Linear” means that every quantity involved is built from the variables like 2x + y: no squares, no products of variables.

A linear programming problem has three parts:

• the variables (the unknowns), the numbers we may choose (how many batches of cakes, x, and of bread, y);
• the limits, written as linear inequalities (2x + y ≤ 16 for the flour);
• the quantity to make as large or as small as possible, also linear (the profit, 600x + 400y).

The method was found twice, on two sides of the world. It is now used wherever many limits must be kept at once: in transport, factories, energy and farming.

An equation says two things are equal; an inequality says one is smaller or bigger. Four signs are used:

An inequality whose variables appear only to the first power, like x ≤ 2 or 15x + 25y ≤ 750, is a linear inequality.

A linear inequality in one variable, like x ≤ 2, allows every point on one side of the upright line x = 2. A linear inequality in two variables, like 15x + 25y ≤ 750, is true for a whole half of the plane, all on one side of the line 15x + 25y = 750: that line is its boundary line, and the half it allows is its solution region.

Why a whole half? Along any upright line, x stays the same and y grows. For 15x + 25y, going up always makes the value bigger. So once you cross the boundary, where 15x + 25y is exactly 750, you are above 750 and stay above it. Every point on one side is below 750, every point on the other side above it.

That is why one point is enough to decide. Pick any point not on the line, a test point, and put its coordinates into the inequality. If the statement comes out true, the point is on the allowed side, and so is the whole of that side. If it comes out false, the allowed side is the other one. O(0, 0) is the easiest test point, because every term with x or y becomes 0.

Steps for showing a linear inequality on a graph

1. The boundary line. Change the sign to “=” to get the boundary line’s equation.
2. Draw it. Find two points on it (putting x = 0, then y = 0, is usually quickest) and draw the line through them: a solid line for ≤ or ≥, because the points on the line are allowed; a dashed line for < or >, because they are not.
3. A test point. Choose a point not on the line, usually O(0, 0), and put it into the inequality. For example, (0, 0) in 2x + y ≤ 5 gives 0 ≤ 5: true.
4. Decide the side. True: the solution region is the side with the test point. False: it is the other side.
5. Shade the solution region.

Worked examples

A real plan has to keep several limits at once: the bakery must not use more than 16 kg of flour and not more than 10 oven hours, and it can’t make a negative number of batches. Two or more linear inequalities taken together are a system of linear inequalities.

Each inequality allows one side of its line. The points that satisfy every inequality of the system are where all those sides overlap: the common solution region, called the feasible region (feasible means possible). Every point inside it is a plan that keeps every limit.

When the feasible region is closed in on all sides, it is a convex polygon: a shape with straight sides and no dents, in which the straight path between any two of its points stays inside. Its corners are its vertices (corner points). Each vertex is where two boundary lines cross, so its coordinates are found by solving those two equations together, and a vertex satisfies every inequality of the system. In 3.4 the corners turn out to be where the best plans are.

Worked examples

Going the other way, from a shaded graph back to its inequalities, needs the equation of each boundary line. When a line meets the axes at (a, 0) and (0, b), its equation in double-intercept form is

$$\frac{x}{a} + \frac{y}{b} = 1$$

Then a test point inside the region gives the sign.

Linear programming is used in business and industry to make the best use of resources, time and money: the least cost of production, the most production or profit. In every such problem:

• the linear quantity to be made as large (maximized) or as small (minimized) as possible, such as Z = 600x + 400y, is the objective function;
• the conditions written as linear inequalities, such as 2x + y ≤ 16, are the constraints. Most problems also have x ≥ 0 and y ≥ 0, because you can’t make a negative number of anything.

A plan in the feasible region is a feasible solution; the feasible solution that gives the best value of the objective function is the optimal solution. Problems with two variables are solved by the graphical method of this unit; problems with hundreds or millions of variables are solved by computers with Dantzig’s simplex method and newer methods, which you will not need here.

Why the best plan is at a corner

Take the bakery. A profit of, say, Rs 2,400 comes from every plan on the line 600x + 400y = 2400. A profit of Rs 4,000 comes from the line 600x + 400y = 4000: the same slope, a little further from O. So as the profit you ask for grows, its line slides across the feasible region parallel to itself. The largest profit you can still reach is where the line is about to leave the region, and a straight line leaves a convex polygon at a corner (or, if it is parallel to a side, along that whole side, corners included).

Corner-point rule: if the objective function Z = ax + by has a maximum or a minimum on a feasible region, that value occurs at a vertex of the region. So you never need to test the points inside: work out Z at each vertex and compare.

Steps for solving a linear programming problem by graph

1. Draw every inequality (constraint) on the same graph.
2. Find the common solution region, the feasible region.
3. Find the coordinates of its vertices (from the graph, or by solving the two boundary equations that meet there), and put each into the objective function.
4. The largest value of the objective function is its maximum, the smallest its minimum; say at which vertex each occurs.

For a problem given in words, start with a step 0: say what x and y stand for, and write the constraints and the objective function.

Worked examples

Back to the bakery

A computer can check this by brute force, trying every whole-number plan. Run it, then change a profit and run it again.

best = 0for x in range<span class="lm-pt">(0, 11)</span>:          # batches of cakes    for y in range<span class="lm-pt">(0, 17)</span>:      # batches of bread        if 2*x + y <= 16 and x + y <= 10:   # enough flour and oven time            profit = 600*x + 400*y            if profit > best:                best, plan = profit, (x, y)print("Best plan (cakes, bread):", plan, "profit Rs", best)

Question 1

Question 2

Draw the graph of each inequality.

Question 3

Draw each system of inequalities and find its common solution region (feasible region).

Question 4

Find the inequalities represented by each shaded region.

Question 5

Find the maximum and minimum values of each function under the given constraints.

Question 6

In the SEE’s Optional Mathematics paper (75 marks, 3 hours), Linear Programming is one of the units of Algebra (Units 1 to 6 of this book). CDC’s specification grid gives Algebra 17 marks, in three kinds of question:

In CDC’s model paper, linear programming is the last part of a group B question that starts with matrices: a system of two constraints with x ≥ 0 and y ≥ 0, and “show the feasible region on a graph”, 2 marks at the application level. Its marking scheme gives 1 mark for the lines drawn correctly and 1 for finding and shading the right feasible region.

What each kind asks, and where its marks are:

• Writing an inequality: a sentence (“at least”, “more than”) or a shaded graph into an inequality. One mark each in group A.
• Showing a system on a graph: each boundary from two points, solid or dashed, a test point for each side, the common region shaded. A mark for the lines, a mark for the region.
• The inequalities of a shaded region: each line’s equation (double-intercept form, or the slope), and a test point for its sign.
• Maximum and minimum: the region, its vertices (one found by solving two equations), the objective function at each, and the answer with where it occurs.

Here is a question of the longer kind, written for this book, with how it is marked.