Back

The origin of linear programming

Linear programming was initially developed independently by George B. Dantzig and Leonid Kantorovich in the first half of the 20th century for solving resource planning problems. Even though linear programming is insufficient for many modern-day applications in operations research, it was useful in many economic and military contexts in the early days.

Graphical example

To motivate the subject of linear programming (LP), we begin with a planning problem that can be solved graphically.

Problem. Say you are a vendor of lemonade and lemon juice. Each unit of lemonade requires 1 lemon and 2 litres of water. Each unit of lemon juice requires 3 lemons and 1 litre of water. Each unit of lemonade gives a profit of $$ 3$ . Each unit of lemon juice gives a profit of $$ 2$ . You have 6 lemons and 4 litres of water available. How many units of lemonade and lemon juice should you make to maximize profit?

If we let $x$ denote the number of units of lemonade to be made and let $y$ denote the number of units of lemon juice to be made, then the profit is given by $3 x + 2 y$ dollars. We call $3 x + 2 y$ the objective function. Note that there are a number of constraints that $x$ and $y$ must satisfied. First of all, $x$ and $y$ should be nonnegative. The number of lemons needed to make $x$ units of lemonade and $y$ units of lemon juice is $x + 3 y$ and cannot exceed 6. The number of litres of water needed to make $x$ units of lemonade and $y$ units of lemon juice is $2 x + y$ and cannot exceed 4. Hence, to determine the maximum profit, we need to maximize $3 x + 2 y$ subject to $x$ and $y$ satisfying the constraints $x + 3 y \leq 6$ , $2 x + y \leq 4$ , $x \geq 0$ , and $y \geq 0.$

A more compact way to write the problem is as follows: $\begin{array}{rrcrll} maximize & 3 x & + & 2 y \\ subject to & x & + & 3 y & \leq & 6 \\ 2 x & + & y & \leq & 4 \\ x & \geq & 0 \\ y & \geq & 0. \end{array}$

We can solve this maximizationproblem graphically as follows. We first sketch the set of $[\begin{matrix} x \\ y \end{matrix}]$ satisfying the constraints, called the feasible region, on the $(x, y)$ -plane. We then take the objective function $3 x + 2 y$ and turn it into an equation of a line $3 x + 2 y = z$ where $z$ is a parameter. Note that as the value of $z$ increases, the line defined by the equation $3 x + 2 y = z$ moves in the direction of the normal vector $[\begin{matrix} 3 \\ 2 \end{matrix}]$ . We call this direction the direction of improvement. Determining the maximum value of the objective function, called the optimal value, subject to the contraints amounts to finding the maximum value of $z$ so that the line defined by the equation $3 x + 2 y = z$ still intersects the feasible region.

Graphical sketch for the lemonade and lemon juice problem

In the figure above, the lines with $z$ at 0, 4 and 6.8 have been drawn. From the picture, we can see that if $z$ is greater than 6.8, the line defined by $3 x + 2 y = z$ will not intersect the feasible region. Hence, the profit cannot exceed $$ 6.8$ .

As the line $3 x + 2 y = 6.8$ does intersect the feasible region, $6.8$ is the maximum value for the objective function. Note that there is only one point in the feasible region that intersects the line $3 x + 2 y = 6.8$ , namely $[\begin{matrix} x \\ y \end{matrix}] = [\begin{matrix} 1.2 \\ 1.6 \end{matrix}] .$ In other words, to maximize profit, we want to make 1.2 units of lemonade and 1.6 units of lemon juice.

The above solution method can hardly be regarded as rigorous because we relied on a picture to conclude that $3 x + 2 y \leq 6.8$ for all $[\begin{matrix} x \\ y \end{matrix}]$ satisfying the constraints. But we can actually show this algebraically.

Note that multiplying both sides of the constraint $x + 3 y \leq 6$ gives $0.2 x + 0.6 y \leq 1.2$ , and multiplying both sides of the constraint $2 x + y \leq 4$ gives $2.8 x + 1.4 y \leq 5.6$ . Hence, any $[\begin{matrix} x \\ y \end{matrix}]$ that satisfies both $x + 3 y \leq 6$ and $2 x + y \leq 4$ must also satisfy $(0.2 x + 0.6 y) + (2.8 x + 1.4 y) \leq 1.2 + 5.6$ , which simplifies to $3 x + 2 y \leq 6.8$ as desired! (Here, we used the fact that if $a \leq b$ and $c \leq d$ , then $a + c \leq b + d$ .)

Now, one might ask if it is always possible to find an algebraic proof like the one above for similar problems. If the answer is “yes”, how does one find such a proof? We will see answers to this question later on.

Before we end, let us consider the following problem: $\begin{array}{rrcrll} minimize & - 2 x & + & y \\ subject to & - x & + & y & \leq & 3 \\ x & - & 2 y & \leq & 2 \\ x & \geq & 0 \\ y & \geq & 0. \end{array}$ Note that for any $t \geq 0$ , $[\begin{matrix} x \\ y \end{matrix}] = [\begin{matrix} t \\ t \end{matrix}]$ satisfies all the constraints. The value of the objective function at $[\begin{matrix} x \\ y \end{matrix}] = [\begin{matrix} t \\ t \end{matrix}]$ is $- t$ . As $t \to \infty$ , the value of the objective function tends to $- \infty$ . Therefore, there is no minimum value for the objective function. The problem is said to be unbounded. Later on, we will see how to detect unboundedness algorithmically. Until then, we rely on inspection to identifying such a family of solutions whenever possible.

Exercise. Check that unboundedness can also be established by using $[\begin{matrix} x \\ y \end{matrix}] = [\begin{matrix} 2 t + 2 \\ t \end{matrix}]$ for $t \geq 0$ .

Worked examples

Show that the problem $\begin{aligned} Minimize & - x + y \\ Subject to & 2 x - y \geq 0 \\ x + 3 y \geq 3 \end{aligned}$ is unbounded.

We could glean some insight by first making a sketch on the $(x, y)$ -plane.

The line defined by $- x + y = z$ has $x$ -intercept $- z$ . Note that for $z \leq - 3$ , $[\begin{matrix} x \\ y \end{matrix}] = [\begin{matrix} - z \\ 0 \end{matrix}]$ satisfies both inequalities and the value of the objective function at $[\begin{matrix} x \\ y \end{matrix}] = [\begin{matrix} - z \\ 0 \end{matrix}]$ is $z$ . Hence, there is no lower bound on the value of objective function.
Suppose that you are shopping for dietary supplements to satisfy your required daily intake of 0.40mg of nutrient $M$ and 0.30mg of nutrient $N$ . There are three popular products on the market. The costs and the amounts of the two nutrients are given in the following table:

Product 1 Product 2 Product 3

Cost $27 $31 $24

Amount of $M$ per daily serving 0.16 mg 0.21 mg 0.11 mg

Amount of $N$ per daily serving 0.19 mg 0.13 mg 0.15 mg

You want to determine how much of each product you should buy so that the daily intake requirements of the two nutrients are satisfied at minimum cost. Formulate your problem as a linear programming problem, assuming that you can buy a fractional number of each product.

Let $x_{i}$ denote the amount of Product $i$ to buy for $i = 1, 2, 3$ .

Then, the problem can be formulated as $\begin{array}{rrcrcrll} minimize & 27 x_{1} & + & 31 x_{2} & + & 24 x_{3} \\ subject to & 0.16 x_{1} & + & 0.21 x_{2} & + & 0.11 x_{3} & \geq & 0.40 \\ 0.19 x_{1} & + & 0.13 x_{2} & + & 0.15 x_{3} & \geq & 0.30 \\ x_{1} & , & x_{2} & , & x_{3} & \geq & 0. \end{array}$

Remark. If one cannot buy fractional amounts of the products, the problem can be formulated as $\begin{array}{rrcrcrll} minimize & 27 x_{1} & + & 31 x_{2} & + & 24 x_{3} \\ subject to & 0.16 x_{1} & + & 0.21 x_{2} & + & 0.11 x_{3} & \geq & 0.40 \\ 0.19 x_{1} & + & 0.13 x_{2} & + & 0.15 x_{3} & \geq & 0.30 \\ x_{1} & , & x_{2} & , & x_{3} & \geq & 0. \\ x_{1} & , & x_{2} & , & x_{3} & \in & Z . \end{array}$

	Product 1	Product 2	Product 3
Cost	$27	$31	$24
Amount of $M$ per daily serving	0.16 mg	0.21 mg	0.11 mg
Amount of $N$ per daily serving	0.19 mg	0.13 mg	0.15 mg