3 min read

Linear Programming Basics

I’ve been using linear programming a fair bit at work and wanted to write a gentle introduction to the topic.

Goal

Linear programming is about how to optimize a linear function subject to some linear constraints The goal is to minimize or maximize something, but due to some business rule, we are subject to certain limitations. For example often times we want to minimize the cost or maximize the profit of some operation and we are limited by the materials needed.

Bake Sale example

Here is a motivating example. Your high school is having a bake sale. You can sell cake for 3$ and bread for 2$ Each cake requires 2 cups of flour and 4 cups of sugar. Each loaf of bread requires 3 cups of flour and 2 cups of sugar. You have 9 cups of flour and 14 cups of sugar in the pantry. How many cakes and how many loafs of bread should you bake for the school bake sale?

Decision Variables

The decision variables are what you have control over. We want to choose the best values of the decision variables to maximize/miniize the objective function. In this case

\[x_1 = \text{number of cakes}\] \[x_2 = \text{number of loafs of bread}\]

Objective Function

We need to create a mathematical function, called an objective function to represent the thing we want to optimize. Linear programming requires the objective function to be a linear function, for example

\[f(x_1, x_2) = 3 x_1 + 2 x_2\]

Constraints

Sometimes there are rules that need to be followed that limit the objective function. For example, we may only have a limited number of resources available. In the bake sale example we have one constraint for flour and one constraint for sugar.

\[ 2x_1 + 3x_2 \leq 9 \ \ \text{(flour constraint)} \] \[ 4x_1 + 2x_2 \leq 14 \ \ \text{(sugar constraint)} \]

There are also some domain constraints on the decision variables. We need the decision variables to be non-negative, since we can’t produce negative items.

\[x_1, x_2 \geq 0\]

Linear Program

The decision variables, objective function, and constraints form a linear program.

\[\begin{align*} \text{Max}_{x_1, x_2} f(x_1, x_2) &= 3 x_1 + 2 x_2 \\ \text{subject to } &2x_1 + 3x_2 \leq 9 \\ &4x_1 + 2x_2 \leq 14 \\ &x_1 \geq 0 \\ &x_2 \geq 0 \end{align*}\]

Most of the work in industrial linear programming is converting a business problem into a linear program

x = 1:100
y = rnorm(length(x), mean=3*x + 10, sd=10)
mydata = data.frame(x=x, y=y)
library(ggplot2)
gg = ggplot(mydata, aes(x=x, y=y)) +
  geom_point() +
  geom_smooth(alpha=0.5)
gg
## `geom_smooth()` using method = 'loess' and formula 'y ~ x'