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.

\max 5x_1 + 3x_2
\text{s.t.} 2x_1 + 1x_2 \leq 20
  1x_1 + 1x_2 \leq 16
  1x_1 + 0x_2 \leq 7
  x_1, x_2 \geq 0

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.