Despite being able to simply provide a link to wikipedia’s already excellent article on Linear Programming, I wanted to provide a short introduction in order to present what I am doing exactly on my thesis in a future article.
Linear Programming is best described as a technique, in which we want to maximize or minimize an objective function subject to a set of constraints. It is called linear because both the objective function and the constraints are linear inequalities on the variables.
And just to make sure that no one is left behind: a linear function on a set of variables \(x_1, x_2, \dots, x_n\) is a function \(a_0 + a_1 x_1 + a_2 x_2 + \dots + a_n x_n\), where \(a_0, a_1, a_2, \dots, a_n\) are numbers. For example, \(4 + 3x_1 - 2x_2\) is a linear function, whereas \(x_1 * x_2 / x_3\) isn’t.
Example: diet problem
A classical example for linear programming is the diet problem. We want to determine a diet that satisfies all of our nutritional requirements while keeping it as cheap as possible. We have a set of different foods that fulfill certain requirements by containing a certain amount of proteins, vitamins, etc; and each food has a certain price per kilogram. Needless to say, the values in the following table are completely fictional.
| Food | Proteins per kg | Vitamins per kg | Carbohydrates per kg | Cost per kg |
|---|---|---|---|---|
| Apples | 2 | 4 | 2 | 5 |
| Beef | 10 | 5 | 4 | 20 |
| Cucumbers | 4 | 3 | 3 | 6 |
| Potatos | 1 | 2 | 8 | 2 |
Suppose also that we need at least 60 units of each nutrient in our diet. Our objective will be to find a solution that specifies how much food of each type we should buy to cover all of our needs while keeping budget to a minimum.
In order to create a linear programming model, we must first define which variables we will be working with. We will define \(x_i\) as how many kg of food \(i\) we will be purchasing; therefore, our variables will be \(x_A, x_B, x_C, x_P\).
Now we must specify our restrictions. We want to consume at least 60 units of each nutrient, and each food provides a certain amount per kg of it. For instance, we may express that we need 60 units of carbs as:
$$ 2 x_A + 4 x_B + 3 x_C + 8 x_P \geq 60$$
Note that each unit of apples provides 2 units of carbs, therefore the total amount of carbs provided by apples will be the product \(2 \times x_A\); same holds for all foods.
Similar expressions can be derived for vitamins:
$$ 4 x_A + 5 x_B + 3 x_C + 2 x_P \geq 60$$
And for proteins:
$$ 2 x_A + 10 x_B + 4 x_C + 1 x_P \geq 60$$
Needless to say, all amounts must be positive, as we are buying food, not selling it. Therefore, we add constraints:
$$ x_A, x_B, x_C, x_P \geq 0 $$
The set of constraints we have built specify a set of valid or feasible solutions for us. For example, we will not accept a solution in which we purchase only 20kg of apples, since although that satisfies our vitamin intake, it does not satisfy carbs and proteins.
What we have to do now is, from every feasible solution, choose one that minimizes how much money we spend. So far, nothing prevents buying a whole supermarket of food from being a valid solution, albeit a very expensive one. In order to prevent that situation, we add an objective function to minimize, which is the cost of all the food we want to buy:
$$ c(x) = 5 x_A + 20 x_B + 6 x_C + 2 x_P $$
The purpose of the objective function is to measure how good or bad a particular solution is, whereas the constraints restrict what we consider a valid solution for us. Putting all of them together, we have constructed a linear programming model for our diet problem.
Generalizing
A linear programming problem consists in the minimization of a linear objective function \(c(x)\) subject to a set of linear constraints, which can be expressed as \(Ax \geq b\), where \(A\) is a matrix in which element \(a_{ij}\) represents how much each unit of variable \(j\) contributes to satisfying demand \(b_i\) for product \(i\).
Note that by using simple algebraic operations we can include all kind of non-strict linear constraints: \(a(x) \leq \beta\), \(a(x) \geq \beta\) and \(a(x) = \beta\). Therefore, there are different canonical ways to represent a linear programming problem, one of which is the one we have already seen:
$$ \min{c(x)} \quad \text{subject to } Ax \geq b$$
We may also express it as a maximization of the objective function:
$$ \max{c(x)} \quad \text{subject to } Ax \leq b$$
Or either of them subject to a set of equalities:
$$ \max{c(x)} / \min{c(x)} \quad \text{subject to } Ax = b$$
In all canonical forms variables are usually restricted to be positive or zero, which makes sense in most scenarios. In a future post I would like to revisit this subject, using one of the canonical forms to go a little deeper into the economical interpretation of each of the variables and constraints. But for now, we will go straight to the resolution.
Resolution
We have seen how to model an optimization problem using linear programming, but we still need to know how to solve it. Luckily, there are several algorithms that deal with these specific problems, one of the most widely known is simplex.
How simplex works deserves another blog post of its own, but for now lets just say that it solves most models incredibly fast. The problem of solving an LPP (linear programming problem) is known to be polynomial, which means that it can be solved within an acceptable timespan.
Needless to say, linear programming is an invaluable tool for modeling several real life scenarios, and has multiple applications within operations research. In future posts I would like to dwelve deeper into linear programming, which I will do if I have some spare time, but for now I will go on blogging within the scope of my thesis: integer linear programming.