What is Linear Programming?

Linear Programming might best be called Linear Optimization: it means finding maxima and minima of linear functions of several variables subject to constraints that are linear equations or linear inequalities. The word “programming” has the old-fashioned meaning of “planning” and was chosen in the forties, before the advent of computers.

Say you are a pig farmer and want to find the cheapest way to make sure your pigs get all the nutrition they need. Let’s say there are three types of food you are considering and that their nutritional contents, prices and the pigs’ daily requirements are as follows:

	Corn	Silage1	Alfalfa	Daily requirement
Carbs	0.9	0.2	0.4	2
Protein	3	8	6	18
Vitamins	1	2	4	15
Cost	7	6	5

Notice that we didn’t specify the units, and it won’t really matter what they are as long as they are consistent. Let’s say the amounts of nutrients shown are in units (of carbs, protein or vitamins) per kilogram of food and that the prices are in cents per kilogram.

To express this problem mathematically choose variables for the amounts of each the foods we should buy: let \(c\) be the number of kilograms of corn per day you’ll buy and similarly let \(s\) be the amount of silage and \(a\) the amount of alfalfa (both in kg/day).

The cost of buying those amounts will be \(7c+6s+5a\) cents per day. This is the amount we wish to minimize. The nutritional requirements give inequalities that the variables must satisfy. For example, getting two units of carbs per day means that \(0.9 c + 0.2 s + 0.4 a \ge 2\).

Putting all of this together we get a linear program (often abbreviated LP):

Minimize \(7c + 6s + 5a\)

subject to \[\begin{aligned} 0.9 c + 0.2 s + 0.4 a & \ge 2 \\ 3 c + 8 s + 6 a & \ge 18 \\ c + 2 s + 4 a & \ge 15 \\ c, s, a & \ge 0 \end{aligned}\]

We added the obvious constraint that all three variable must be non-negative because while it is commonsense for us, if we didn’t include them “the math wouldn’t know about it”.

The bulk of this course will be learning how to solve this type of problem using the Simplex Method.

minimize 7c + 6s + 5a
subject to
  0.9 c + 0.2 s + 0.4 a >  2
  3   c +   8 s +   6 a > 18
      c +   2 s +   4 a > 15
end

Say you need to blend 4000 barrels of aviation gas from three available components: Toluene, Alkylate and Pentane. The prices and certain constraints which must be satisfied by the blend are summarized in the following table³:

Constraint	Toluene	Alkylate	Pentane	Specification
% aromatics	100	0	0	5 (min)
Reid Vapor Pressure	2.0	4.8	19.7	5.5 (min), 7.0 (max)
Performance Number	100	125	125	115 (max)
Cost ($) per Barrel	45	30	30

The first row of the table says that we need at least 5% of “aromatics” in the blend, and also that only toluene is an “aromatic”. The objective is to find the amount of each resource to use in order to minimize the cost of producing the aviation gas. What happens if resource specifications or costs or available amounts change?

We can make several choices of how to define our decision variables; there should definitely be one variable for each of the amounts of toluene (\(t\)), alkylate (\(a\)) and pentane (\(p\)), but we could choose to represent:

• the number of barrels, so we’d have \(t+a+p = 4000\),
• the percentage of the total blend, so that \(t + a + p = 100\), or,
• the fraction of the blend, so that \( t + a + p = 1\).

Each of these would be a valid choice and would give LPs that are only slightly different. If we let \(t\) be the fraction of toluene in the blend (and similarly for alkylate and pentane), we’d get the following LP:

Minimize \( 45t + 30a + 30p\)

subject to \[\begin{aligned} 100t & \ge 5 \\ 2t+4.8a+19.7p &\ge 5.5 \\ 2t+4.8a+19.7p &\le 7 \\ 100t + 125a+125p &\ge 115 \end{aligned} \]