# 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.

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.