# Linear Programming: Introduction

## Definition

Formally, a linear program is an optimzation problem of the form:

\begin{equation}
\min \vec{c}^\mathsf{T}\vec x\\
\textrm{subject to} \begin{cases}
\mathbf{A}\vec x=\vec b\\
\vec x\ge\vec 0
\end{cases}
\end{equation}

where $\vec c\in\mathbb R^n$, $\vec b\in\mathbb R^m$ and $\mathbf A \in \mathbb R^{m\times n}$. The vector inequality $\vec x\ge\vec 0$ means that each component of $\vec x$ is nonnegative. Several variations of this problem are possible; eg. instead of minimizing, we can maximize, or the constraints may be in the form of inequalities, such as $\mathbf A\vec x\ge \vec b$ or $\mathbf A\vec x\le\vec b$. We shall see later, these variations can all be rewritten into the standard form.  

## Example

A manufacturer produces  four different  products  $X_1$, $X_2$, $X_3$ and $X_4$. There are three inputs to this production process:

- labor in man weeks,  
- kilograms of raw material A, and 
- boxes  of raw  material  B.

Each product has different input requirements. In determining each  week's production schedule, the manufacturer cannot use more than the available amounts of  manpower and the two raw  materials:

|Inputs|$X_1$|$X_2$|$X_3$|$X_4$|Availabilities|
|------|-----|-----|-----|-----|--------------|
|Person-weeks|1|2|1|2|20|
|Kilograms of material A|6|5|3|2|100|
|Boxes of material B|3|4|9|12|75|
|Production level|$x_1$|$x_2$|$x_3$|$x_4$| |

These constraints can be written in mathematical form

\begin{align}
x_1+2x_2+x_3+2x_4\le&20\\
6x_1+5x_2+3x_3+2x_4\le&100\\
3x_1+4x_2+9x_3+12x_4\le&75
\end{align}

Because negative production levels are not meaningful, we must impose the following nonnegativity constraints on the production levels:

\begin{equation}
x_i\ge0,\qquad i=1,2,3,4
\end{equation}

Now suppose that one unit of product $X_1$ sells for €6 and $X_2$, $X_3$ and $X_4$ sell for €4, €7 and €5, respectively. Then, the total revenue for any production decision $\left(x_1,x_2,x_3,x_4\right)$ is

\begin{equation}
f\left(x_1,x_2,x_3,x_4\right)=6x_1+4x_2+7x_3+5x_4
\end{equation}

The problem is then to maximize $f$ subject to the given constraints.

## Vector Notation

Using vector notation with

\begin{equation}
\vec x = \begin{pmatrix}
x_1\\x_2\\x_3\\x_4
\end{pmatrix}
\end{equation}

the problem can be written in the compact form
\begin{equation}
\max 
\begin{pmatrix}6&4&7&5\end{pmatrix}
\begin{pmatrix}
x_1\\x_2\\x_3\\x_4
\end{pmatrix}\\
\textrm{subject to}
\begin{cases}
\begin{pmatrix}
1&2&1&2\\
6&5&3&2\\
3&4&9&12
\end{pmatrix}
\begin{pmatrix}
x_1\\x_2\\x_3\\x_4
\end{pmatrix}\le
\begin{pmatrix}
20\\100\\75
\end{pmatrix}\\
\begin{pmatrix}
x_1\\x_2\\x_3\\x_4
\end{pmatrix}\ge
\begin{pmatrix}
0\\0\\0\\0
\end{pmatrix}
\end{cases}
\end{equation}

## Two-dimensional Linear Program

Many fundamental concepts of linear programming are easily illustrated in two-dimensional space.

Consider the following linear program:

\begin{equation}
\max
\begin{pmatrix}
1&5
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2
\end{pmatrix}\\
\textrm{subject to}
\begin{cases}
\begin{pmatrix}
5&6\\
3&2
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2
\end{pmatrix}\le
\begin{pmatrix}
30\\
12
\end{pmatrix}\\
\begin{pmatrix}
x_1\\
x_2
\end{pmatrix}\ge
\begin{pmatrix}
0\\
0
\end{pmatrix}
\end{cases}
\end{equation}


```julia
#using Pkg
#pkg"add LaTeXStrings"

using Plots
using LaTeXStrings

x = -2:6
plot(x, (30 .- 5 .* x) ./ 6, linestyle=:dash, label=L"5x_1+6x_2=30")
plot!(x, (12 .- 3 .* x) ./ 2, linestyle=:dash, label=L"3x_1+2x_2=12")
plot!([0,4,1.5,0,0],[0,0,3.75,5,0], linewidth=2, label="constraints")
plot!(x, -x ./ 5, label=L"f\left(x_1,x_2\right)=x_1+5x_2=0")
plot!(x, (25 .- x) ./ 5, label=L"f\left(x_1,x_2\right)=x_1+5x_2=25")
```

## Slack Variables

Theorems and solution techniques are usually stated for problems in standard form. other forms of linear programs can be converted as the standard form. If a linear program is in the form

\begin{equation}
\min \vec{c}^\mathsf{T}\vec x\\
\textrm{subject to} \begin{cases}
\mathbf{A}\vec x\ge \vec b\\
\vec x\ge\vec 0
\end{cases}
\end{equation}

then by introducing _surplus variables_, we can convert the orginal problem into the standard form

\begin{equation}
\min \vec{c}^\mathsf{T}\vec x\\
\textrm{subject to} \begin{cases}
\mathbf{A}\vec x-\mathbf I\vec y = \vec b\\
\vec x\ge\vec 0\\
\vec y\ge\vec 0
\end{cases}
\end{equation}

where $\mathbf I$ is the $m\times m$ identity matrix.

If, on the other hand, the constraints have the form
\begin{equation}
\begin{cases}
\mathbf{A}\vec x\le b\\
\vec x\ge\vec 0
\end{cases}
\end{equation}

then we introduce the _slack variables_ to convert the constraints into the form

\begin{equation}
\begin{cases}
\mathbf{A}\vec x+\mathbf I\vec y = \vec b\\
\vec x\ge\vec 0\\
\vec y\ge\vec 0
\end{cases}
\end{equation}

Consider the following optimization problem

\begin{equation}
\max x_2-x_1\\
\textrm{subject to}
\begin{cases}
3x_1=x_2-5\\
\left|x_2\right|\le2\\
x_1\le0
\end{cases}
\end{equation}

To convert the problem into a standard form, we perform the following steps:

1. Change the objective function to:

\begin{equation}
\min x_1 - x_2
\end{equation}

2. Substitute $x_1=-x_1^\prime$.

3. Write $\left|x_2\right|\le2$ as $x_2\le 2$ and $-x_2\le 2$.

4. Introduce slack variables $y_1$ and $y_2$, and convert the inequalities above to

\begin{cases}
\hphantom{-}x_2 + y_1 =2\\
-x_2+y_2 =2
\end{cases}

5. Write $x_2=u-v$ with $u,v\ge0$.

Hence, we obtain

\begin{equation}
\min -x_1^\prime-u+v\\
\textrm{subject to}
\begin{cases}
3x_1^\prime+u-v=5\\
u-v+y_1=2\\
v-u+y_2=2\\
x_1^\prime,u,v,y_1,y_2\ge0
\end{cases}
\end{equation}

## Fundamental Theorem of Linear Programming

We consider the system of equalities

\begin{equation}
\mathbf{A}\vec x=\vec b
\end{equation}

where $\mathrm{rank}\,\mathbf A=m$.

Let $\mathbf B$ a square matrix whose columns are $m$ linearly independent columns of $\mathbf A$. If necessary, we reorder the columns of $\mathbf A$ so that the columns in $\mathbf B$ appear first: $\mathbf A$ has the form $\left(\mathbf B |\mathbf N\right)$.

The matrix is nonsingular, and thus we can solve the equation

\begin{equation}
\mathbf B\vec x_\mathbf B = \vec b
\end{equation}

The solution is $\vec x_\mathbf B = \mathbf B^{-1}\vec b$.

Let $\vec x$ be the vector whose first $m$ components are equal to $\vec x_\mathbf B$ and the remaining components are equal to zero. Then $\vec x$ is a solution to $\mathbf A\vec x=\vec b$. We call $\vec x$  a _basic solution_. Its components refering to the the components of $\vec x_\mathbf B$ are called _basic variables_.

- If some of the basic variables are zero, then the basic solution is _degenerate_.
- A vector $\vec x$ satisfying $\mathbf A\vec x=\vec b$, $\vec x \ge \vec 0$, is said to be a _feasible solution_.
- A feasible solution that is also basic is called a _basic feasible solution_.

The fundamental theorem of linear programming states that when solving a linear programming problem, we need only consider basic feasible solutions. This is because the optimal value (if it exists) is always achieved at a basic solution.

162d7466e9ef9f19b55cae7e80719ed031028d97
ipynb
Jupyter Notebook
Lectures_old/Lecture 5.ipynb
BenLauwens/ES313.jl
5a7553e53c288834f768d26e0d5aa22f9062b6af
MIT
2018-12-17T16:00:26.000Z
2020-01-18T04:09:25.000Z
Lectures_old/Lecture 5.ipynb
BenLauwens/ES313
5a7553e53c288834f768d26e0d5aa22f9062b6af
MIT
Lectures_old/Lecture 5.ipynb
BenLauwens/ES313
5a7553e53c288834f768d26e0d5aa22f9062b6af
MIT
2018-08-27T13:41:05.000Z
2020-02-08T11:00:53.000Z
Qwen/Qwen-72B
1. YES
2. YES