Introduction

Here, we provide a breif introduction to linear programming and the simplex algorithm.

Linear Programming

In a linear program, we have a set of decisons we need to make. We represent each decison as a decison variable. For example, say we run a small company that sells 2 types of widgets. We must decide how much of each each widget to produce. Let \(x_1\) and \(x_2\) denote the number of type 1 and type 2 widgets produced respectively.

Next, we have a set of constraints. Each constraint can be an inequality (\(\leq,\geq\)) or an equality (\(=\)) but not a strict inequality (\(<,>\)). Furthermore, it must consist of a linear combination of the decison variables. For example, let’s say we have a buget of $20. Type 1 and type 2 widgets cost $2 and $1 to produce respectively. This gives us our first constraint: \(2x_1 + 1x_2 \leq 20\). Furthermore, we can only store 16 widgets at a time so we can not produce more than 16 total. This yeilds \(1x_1 + 1x_2 \leq 16\). Lastly, due to enviromental regulations, we can produce at most 7 type 2 widgets. Hence, our final constraint is \(1x_1 + 0x_2 \leq 7\).

This leaves the final component of a linear program: the objective function. The objective function specifies what we wish to optimize (either minimize or maximize). Like constraints, the objective function must be a linear combination of the decison variables. In our example, we wish to maximize our revenue. Type 1 and type 2 widgets sell for $5 and $3 respectively. Hence, we wish to maximize \(5x_1 + 3x_2\).

Combined, the decison variables, constraints, and objective function fully define a linear program. Often, linear programs are written in standard inequality form. Below is our example in standard inequality form.

\[\begin{split}\begin{align*} \text{maximize} \quad & 5x_1 + 3x_2\\ \text{subject to} \quad & 2x_1 + 1x_2 \leq 20 \\ & 1x_1 + 1x_2 \leq 16 \\ & 1x_1 + 0x_2 \leq 7 \\ & x_1, x_2 \geq 0 \end{align*}\end{split}\]

Let us now summarize the three componets of a linear program in a general sense.

  • Decision variables
    The decision variables encode each “decision” that must be made and are often denoted \(x_1, \dots , x_n\).
  • Constraints
    The set of constraints limit the values of the decision variables. They can be inequalities or equalities (\(\leq, \geq, =\)) and must consist of a linear combination of the decision variables. In standard inequality form, each constraint has the form: \(c_1x_1 + \dots + c_nx_n = b\).
  • Objective Function
    The objective function defines what we wish to optimize. It also must be a linear combination of the decision variables. In standard inequality form, the objective function has the form: \(\max c_1x_1 + \dots + c_nx_n\).

The decison variables and constraints define the feasible region of a linear program. The feasible region is defined as the set of all possible decisions that can feasibly be made i.e. each constraint inequality or equality holds true. In our example, we only have 2 decision variables. Hence, we can graph the feasible region with \(x_1\) on the x-axis and \(x_2\) on the y-axis. The area shaded blue denotes the feasible region. Any point \((x_1, x_2)\) in this region denotes a feasible set of decisions. Each point in this region has some objective value. Consider the point where \(x_1 = 2\) and \(x_2 = 10\). This point has an objective value of \(5x_1 + 3x_2 = 5(2) + 3(10) = 40\). You can move the objective slider to see all the points with some objective value. This is called an isoprofit line. If you slide the slider to 40, you will see that \((2,10)\) lies on the red isoprofit line.