LINEAR PROGRAMMING

Chapter 12

Linear Programming

Big idea: when you have limited time, material or money, many plans are possible but only one is best. Linear programming shows how to find the best plan with a picture and a short list of corner points.

A small workshop makes two products, P and Q. Making P takes $3$ hours of cutting and $2$ hours of finishing. Making Q takes $2$ hours of cutting and $4$ hours of finishing. The workshop has $24$ hours of cutting time and $32$ hours of finishing time each week. Each P gives a profit of $40$ units and each Q gives $50$ units. The owner asks: how many of each product should we make to earn the most profit?

Many plans are possible. The table tries five of them. A plan is allowed only if it fits inside both time limits.

The plan $(5, 5)$ needs $25$ cutting hours, but only $24$ are available, so it is not allowed. Among the other plans, $(4, 6)$ gives the most profit. But is it the best of all possible plans? There are infinitely many plans if parts of a product are allowed, and even with whole numbers there are far too many to try one by one.

We need a method that is sure to find the best plan. Linear programming is that method. It works when:

• you want to make one quantity as large (or as small) as possible, for example profit or cost;
• the limits on time, material or space are all straight-line conditions such as $3x + 2y \le 24$.

Problems like this appear everywhere: planning production, mixing food to meet nutrition needs at lowest cost, and moving goods between places at the least shipping cost. In this chapter we study problems with two unknowns, because then we can draw a picture and read the answer from it.

Every linear programming problem (LPP) has the same parts. Look back at the workshop and give each part its name.

• Decision variables. The numbers you can choose. Here $x$ = number of P made and $y$ = number of Q made.
• Objective function. The quantity you want to make as large or as small as possible, written with the variables. Here the profit $Z = 40x + 50y$. "Optimise" means maximise or minimise.
• Constraints. The limits. Here cutting time $3x + 2y \le 24$ and finishing time $2x + 4y \le 32$.
• Non-negativity conditions. You cannot make a negative number of products: $x \ge 0$ and $y \ge 0$.

The word linear means that the objective function and every constraint are straight-line expressions: each variable appears only to the first power, and variables are never multiplied together. So $3x + 2y \le 24$ is allowed, but $xy \le 24$ or $x^2 + y \le 5$ is not.

• A feasible solution is any pair $(x, y)$ that satisfies all constraints and the non-negativity conditions.
• The feasible region is the set of all feasible solutions.
• An optimal solution is a feasible solution that gives the best value of the objective function. The best value is called the optimal value.

The line $3x + 2y = 24$ splits the plane into two sides. One side satisfies $3x + 2y \le 24$ and the other does not. To find which side, test a point. The origin $(0, 0)$ gives $0 \le 24$, which is true, so the origin side is the allowed side. The point $(10, 10)$ gives $50 \le 24$, which is false. The picture shows the allowed side, kept to the part where $x \ge 0$ and $y \ge 0$. It is a triangle with corners $(0, 0)$, $(0, 12)$, $(8, 0)$.

When there are several constraints, the feasible region is the part of the plane that is on the allowed side of every line at once. It is always a convex polygon (or an unbounded region): a shape with no dents, where the straight line between any two of its points stays inside it.

To formulate a problem means to turn the words into mathematics. You do not solve anything yet. Follow these steps every time:

1. Read the problem and decide what you are choosing. Name these decision variables $x$ and $y$, and say what they mean, with units.
2. Write the objective function and say whether to maximise or minimise it.
3. Write one constraint for each limit. Check the direction: "at most" gives $\le$, "at least" gives $\ge$.
4. Add $x \ge 0$ and $y \ge 0$.

This is the workshop from Section 12.1.

Let $x$ = number of P made and $y$ = number of Q made. The problem is:

$$\text{Maximise } Z = 40x + 50y$$

• $3x + 2y \le 24$
• $2x + 4y \le 32$
• $x \ge 0, \; y \ge 0$

A quick check of one plan: making $6$ of P and $2$ of Q uses $3(6) + 2(2) = 22$ cutting hours and $2(6) + 4(2) = 20$ finishing hours. Both are within the limits, so the plan is allowed (confirmed by computer), and it gives $Z = 340$.

A farm mixes two foods, F1 and F2, for its animals. Each kilogram of F1 gives $3$ units of protein and $1$ unit of iron. Each kilogram of F2 gives $1$ unit of protein and $2$ units of iron. Each day the animals need at least $9$ units of protein and at least $8$ units of iron. F1 costs $4$ units per kilogram and F2 costs $3$ units per kilogram. Find the cheapest mix.

Let $x$ = kilograms of F1 and $y$ = kilograms of F2 per day. The goal is a minimum cost, and the needs are "at least", so the constraints use $\ge$:

$$\text{Minimise } Z = 4x + 3y$$

• $3x + y \ge 9$
• $x + 2y \ge 8$
• $x \ge 0, \; y \ge 0$

Check: the mix $x = 4$, $y = 2$ gives $3(4) + 2 = 14$ units of protein and $4 + 2(2) = 8$ units of iron, which meets both needs (confirmed), at a cost of $Z = 22$.

A shop needs at least $10$ boxes of goods. Depot A can send at most $7$ boxes and depot B can send at most $6$ boxes. Sending a box from A costs $2$ units and from B costs $3$ units. How should the shop order to pay the least?

Let $x$ = boxes from A and $y$ = boxes from B.

$$\text{Minimise } Z = 2x + 3y$$

• $x \le 7$
• $y \le 6$
• $x + y \ge 10$
• $x \ge 0, \; y \ge 0$

Check: ordering $7$ boxes from A and $4$ from B gives $11$ boxes in total, within both depot limits (confirmed), at a cost of $Z = 26$.

A bakery makes loaves ($x$ per day) and rolls ($y$ per day). A loaf needs $5$ minutes of oven time and $2$ minutes of mixing. A roll needs $2$ minutes of oven time and $3$ minutes of mixing. The oven is available for $100$ minutes and the mixer for $60$ minutes each day. A loaf gives $6$ profit units and a roll gives $4$. Formulate the problem to find the plan with the most profit.

Answers

1. Maximise $Z = 6x + 4y$ subject to $5x + 2y \le 100$ (oven), $2x + 3y \le 60$ (mixer), $x \ge 0$, $y \ge 0$. As a check, $10$ loaves and $10$ rolls use $70$ oven minutes and $50$ mixer minutes, which is allowed (confirmed), and give $Z = 100$.

With two variables we can solve an LPP by drawing it. The method has six steps:

1. Formulate the problem (Section 12.2.1).
2. Draw each constraint as a straight line, then use a test point (usually $(0, 0)$) to decide which side is allowed. The feasible region is where all allowed sides overlap, inside $x \ge 0$, $y \ge 0$.
3. Find the corner points of the region: the points where two boundary lines meet. Solve the two line equations together.
4. Calculate the objective function $Z$ at every corner point.
5. Compare the values (the rule in the next paragraphs tells you how).
6. Write the answer in words, with the units.

Maximise $Z = 40x + 50y$ subject to $3x + 2y \le 24$, $2x + 4y \le 32$, $x \ge 0$, $y \ge 0$.

The corners on the axes are easy: $(0, 0)$, $(8, 0)$ (where $3x + 2y = 24$ meets $y = 0$) and $(0, 8)$ (where $2x + 4y = 32$ meets $x = 0$). The fourth corner is where the two slanted lines meet. Divide the second equation by $2$ to get $x + 2y = 16$. Subtract this from $3x + 2y = 24$: $2x = 8$, so $x = 4$ and $y = 6$. The corner is $(4, 6)$.

The largest value is $460$ at $(4, 6)$. So the workshop should make $4$ of P and $6$ of Q each week, for a profit of $460$ units.

Think of the profit lines $40x + 50y = k$. For each value of $k$ it is a straight line, and all these lines are parallel. As $k$ grows, the line slides away from the origin. The best plan is on the last such line that still touches the feasible region. Because the region is a polygon with straight sides, the last point touched is a corner (or a whole side, which then has corners at both ends). The picture shows this for $k = 200, 320, 460$.

This idea is stated in two theorems. We accept them without a long proof.

Theorem 1. If a linear programming problem has an optimal value, then it is attained at a corner point of the feasible region.

Theorem 2. If the feasible region is bounded (it fits inside some circle), then the objective function has both a maximum value and a minimum value, and each is attained at a corner point.

If two corners both give the optimal value, then every point on the line segment between them is also optimal. We look at this below.

Minimise $Z = 4x + 3y$ subject to $3x + y \ge 9$, $x + 2y \ge 8$, $x \ge 0$, $y \ge 0$ (the diet problem from Section 12.2.1).

This time the region is unbounded: it goes on for ever to the right and upwards. The corners are $(0, 9)$, $(2, 3)$, $(8, 0)$. The solution of $3x + y = 9$ and $x + 2y = 8$ is $(2, 3)$.

The smallest corner value is $17$ at $(2, 3)$. But Theorem 2 does not apply, because the region is unbounded. A smallest corner value is only a candidate. We must check it with the half-plane test:

Here the half-plane $4x + 3y < 17$ misses the region completely (the picture shows the whole region on or above the dashed line, and the computer confirms that no feasible point gives a smaller value). So the minimum cost is $17$, using $2$ kg of F1 and $3$ kg of F2. For a maximum there is none: the point $(100, 0)$ is allowed and gives $Z = 400$, and $(0, 200)$ is allowed and gives $Z = 600$. The cost can be made as large as you like.

Minimise $Z = -x + y$ subject to $2x + y \ge 6$, $x + 2y \ge 6$, $x \ge 0$, $y \ge 0$.

The smallest corner value is $-6$ at $(6, 0)$. Is it the minimum? Test a point of the region to the right of the corner: $(7, 0)$ is allowed and gives $Z = -7$, which is smaller. In fact, moving right along the axis makes $Z$ smaller and smaller. So there is no minimum, even though the table has a smallest corner value. (The computer agrees: this problem is unbounded.) The same region with $Z = x + y$ does have a minimum, namely $4$ at $(2, 2)$, because moving away from the origin there only makes $Z$ larger.

Take the workshop region again, but change the profits to $15$ and $10$ units: maximise $Z = 15x + 10y$. The profit lines now have the same slope as the cutting-time line $3x + 2y = 24$, because $15 : 10 = 3 : 2$. So the last profit line to touch the region lies along a whole side. The corners $(4, 6)$ and $(8, 0)$ both give $Z = 120$. So does every point on the side between them, for example $(6, 3)$: it is allowed and gives $15(6) + 10(3) = 120$. The problem has many optimal solutions, and every one has the same optimal value.

Maximise $Z = x + y$ subject to $x + y \le 2$, $x + y \ge 5$, $x \ge 0$, $y \ge 0$. The first says $x + y$ is at most $2$. The second says it is at least $5$. No point can do both, so the two allowed sides do not overlap. The feasible region is empty: there are no corners, and the problem is infeasible (it has no solution). Checking whole-number or fractional points will not help.

Maximise $Z = 5x + 4y$ subject to $2x + 3y \le 13$, $3x + y \le 10$, $x, y \ge 0$, where $x$ and $y$ must be whole numbers of items. The graphical method gives the corner $\left(\frac{17}{7}, \frac{19}{7}\right)$ with $Z = 23$. But you cannot make $\frac{17}{7}$ of an item. We test whole-number plans directly (the computer tried every whole pair with $x, y \le 10$). The best whole-number plan is $(2, 3)$ with $Z = 22$, which is below $23$.

1. Maximise $Z = 3x + 4y$ subject to $x + y \le 6$, $x + 3y \le 12$, and $x, y \ge 0$.
2. Minimise $Z = 2x + 5y$ subject to $x + y \ge 5$, $x + 3y \ge 9$, and $x, y \ge 0$.
3. Maximise $Z = 5x + 3y$ subject to $2x + y \le 10$, $x + 2y \le 8$, $x \le 4$, and $x, y \ge 0$.
4. A small factory makes desk lamps ($x$ per week) and floor lamps ($y$ per week). A desk lamp needs $2$ hours of wiring and $1$ hour of painting. A floor lamp needs $3$ hours of wiring and $2$ hours of painting. There are $60$ hours of wiring and $32$ hours of painting each week. A desk lamp gives $11$ profit units and a floor lamp $17$. Formulate the problem and find the weekly plan with the most profit.
5. Two feeds, A and B, are mixed for a farm. Each kilogram of A has $4$ units of protein and $1$ unit of vitamins. Each kilogram of B has $1$ unit of protein and $2$ units of vitamins. The daily mix must have at least $8$ units of protein and at least $6$ units of vitamins. A costs $5$ units per kilogram and B costs $4$. Find the cheapest mix.
6. Maximise $Z = x + y$ subject to $x - 2y \le 2$, and $x, y \ge 0$.
7. Maximise $Z = x + 2y$ subject to $x + y \le 3$, $2x + 2y \ge 10$, and $x, y \ge 0$.
8. Maximise $Z = x + 2y$ subject to $x + 2y \le 8$, $x \le 6$, $y \le 3$, and $x, y \ge 0$.

Answers

1. Corner points and values of $Z$: $(0, 0)$: $0$; $(0, 4)$: $16$; $(3, 3)$: $21$; $(6, 0)$: $18$. The maximum value is $21$, at $(3, 3)$.
2. Corner points and values of $Z$: $(0, 5)$: $25$; $(3, 2)$: $16$; $(9, 0)$: $18$. The minimum value is $16$, at $(3, 2)$.
3. Corner points and values of $Z$: $(0, 0)$: $0$; $(0, 4)$: $12$; $(4, 0)$: $20$; $(4, 2)$: $26$. The maximum value is $26$, at $(4, 2)$.
4. Maximise $Z = 11x + 17y$ subject to $2x + 3y \le 60$, $x + 2y \le 32$, $x, y \ge 0$. Corner points and values of $Z$: $(0, 0)$: $0$; $(0, 16)$: $272$; $(24, 4)$: $332$; $(30, 0)$: $330$. The maximum value is $332$, at $(24, 4)$. The corner is a whole-number plan, and the computer's check of every whole-number plan up to $40$ agrees: $332$ at $(24, 4)$.
5. Let $x$ = kg of A and $y$ = kg of B. Minimise $Z = 5x + 4y$ subject to $4x + y \ge 8$, $x + 2y \ge 6$, $x, y \ge 0$. Corner points and values of $Z$: $(0, 8)$: $32$; $(\frac{10}{7}, \frac{16}{7})$: $\frac{114}{7}$; $(6, 0)$: $30$. The minimum value is $\frac{114}{7}$, at $(\frac{10}{7}, \frac{16}{7})$. The region is unbounded, so the half-plane test is needed; the computer confirms that the minimum exists.
6. Corner points and values of $Z$: $(0, 0)$: $0$; $(2, 0)$: $2$. The region is unbounded and $Z$ keeps improving along it, so there is no maximum.
7. No point satisfies all the constraints together, so the feasible region is empty and the problem has no solution.
8. Corner points and values of $Z$: $(0, 0)$: $0$; $(0, 3)$: $6$; $(2, 3)$: $8$; $(6, 0)$: $6$; $(6, 1)$: $8$. The maximum value is $8$, at every point of the line segment joining $(2, 3)$ and $(6, 1)$ (many optimal solutions). The value is the same at $(2, 3)$ and $(6, 1)$, because the profit line is parallel to the side $x + 2y = 8$.

• LPP: optimise (maximise or minimise) a linear objective function $Z = ax + by$ subject to linear constraints and $x \ge 0$, $y \ge 0$.
• Feasible solution: a point satisfying all constraints. Feasible region: the set of all of them (a convex polygon, bounded or unbounded). Optimal solution: a feasible point giving the best value of $Z$.
• Formulating: name the variables, write the objective function, write one constraint per limit ("at most" is $\le$, "at least" is $\ge$), add $x, y \ge 0$.
• Corner point method: draw the region, find the corners, evaluate $Z$ at each corner, compare.
• Theorem 1: if an optimal value exists, it is attained at a corner point.
• Theorem 2: if the region is bounded, both a maximum and a minimum exist, at corner points.
• Unbounded region: the best corner value $m$ (or $M$) is only a candidate. It is the minimum (maximum) only if the open half-plane $Z < m$ ($Z > M$) has no point in common with the region. Otherwise there is no minimum (maximum).
• Many optimal solutions: if two corners give the same best value, every point on the segment between them does too.
• Infeasible: if the allowed sides do not overlap, the region is empty and there is no solution.
• Whole numbers: a corner may have fractions. If items must be whole, test whole-number plans directly.

Linear programming grew out of the need to plan large operations with limited resources. It became important during the Second World War, when planners had to decide how to use scarce supplies, vehicles and workers as well as possible.

• About 1941: the mathematician Leonid Kantorovich and the economist Frank Hitchcock, working separately, each described the transportation problem: how to send goods from several sources to several destinations at the least total cost.
• 1945: the economist George Stigler described the diet problem: how to choose foods so that nutrition needs are met at the lowest cost.
• 1947: George Dantzig invented the simplex method, a step-by-step procedure that solves any linear programming problem in a finite number of steps, whatever the number of variables.
• 1975: Kantorovich and Tjalling Koopmans received the Nobel Prize in Economics for their pioneering work on the best use of resources.

With computers, the simplex method and later methods now solve problems with thousands of variables, in industry, transport, energy and many other areas. The two-variable pictures in this chapter show the main idea behind all of them: the best plan sits at a corner of the region of allowed plans.