1-fundamental.Rmd

# Solving linear programming problems {#fund-lp}


[Fourier-Motzkin elimination](#fm) can actually be used to
solve a linear programming problem though the method
is not efficient and is almost never used in practice.
We illustrate the process
with an example.


Consider the following linear programming problem:
\begin{equation}
\begin{array}{rl}
\min & x + y \\
\text{s.t.}
& x + 2y  \geq 2 \\
& 3x + 2y  \geq 6.
\end{array}(\#eq:LP)
\end{equation}
Observe that \@ref(eq:LP) is equivalent to
\begin{equation}
\begin{array}{rl}
\min & z \\
\text{s.t.}
& z - x - y = 0 \\
& x + 2y  \geq 2 \\
& 3x + 2y  \geq 6.
\end{array}(\#eq:LPprime)
\end{equation}
Note that the objective function is replaced with \(z\) and \(z\) is
set to the original objective function in the first constraint of 
\@ref(eq:LPprime) since \(z = x+ y\) if and only if \(z-x-y=0\).
Then, solving \@ref(eq:LPprime) is equivalent to finding
among all the solutions to the following system a solution that minimizes 
\(z\), if it exists.
\[
\begin{array}{rl}
 z - x - y \geq 0 & ~~~(1) \\
-z + x + y \geq 0 & ~~~(2) \\
 x + 2y  \geq 2 &~~~(3)\\
 3x + 2y  \geq 6 & ~~~(4)
\end{array}
\]
Since we are interested in the minimum possible value for \(z\)
we use Fourier-Motzking elimination to eliminate the variables \(x\) and \(y\).


To eliminate \(x\), we first multiply \((4)\) by \(\frac{1}{3}\) to obtain:
\[
\begin{array}{rl}
 z - x - y \geq 0 & ~~~(1) \\
-z + x + y \geq 0 & ~~~(2) \\
 x + 2y  \geq 2 &~~~(3)\\
 x + \frac{2}{3}y  \geq 2 & ~~~(5)
\end{array}
\]
Then eliminate \(x\) to obtain
\[
\begin{array}{rrl}
(1) + (2):  & 0 \geq 0 \\
(1) + (3):  & z + y \geq 2 & ~~~(6) \\
(1) + (5):  & z - \frac{1}{3} y \geq 2 & ~~~(7) \\
\end{array}
\]
Note that there is no need to keep the first inequality.
To eliminate \(y\), we first multiply \((7)\) by \(3\) to obtain:
\[
\begin{array}{rl}
  z + y \geq 2 & ~~~(6) \\
  3z - y \geq 6 & ~~~(8) \\
\end{array}
\]
Then eliminate \(y\) to obtain
\[
\begin{array}{rl}
  4z \geq 8 & ~~~(9) \\
\end{array}
\]
Multiplying \((9)\) by \(\frac{1}{4}\) gives \(z \geq 2\).
Hence, the minimum possible value for \(z\) among all the solutions
to the system is \(2\).  So the optimal value of \@ref(eq:LPprime) is \(2\).
To obtain an optimal solution, set \(z = 2\).
Then we have no choice but to set \(y = 0\) and \(x = 2\).
One can check that \((x,y) = (2,0)\) is a feasible solution with objective
function value \(2\).


We can obtain an independent proof that the optimal value is indeed \(2\)
if we trace back the computations.
Note that the inequality \(z \geq 2\)
is given by 
\begin{eqnarray*}
\frac{1}{4} (9) 
& \Leftarrow & \frac{1}{4} (6) + \frac{1}{4} (8) \\
& \Leftarrow & \frac{1}{4} (1)+\frac{1}{4}(3) + \frac{3}{4}(7) \\
& \Leftarrow & \frac{1}{4} (1)+\frac{1}{4}(3) + \frac{3}{4}(1)+\frac{3}{4}(5) \\
& \Leftarrow & (1)+ \frac{1}{4}(3) + \frac{1}{4} (4)  \\
\end{eqnarray*}
This shows that \(\frac{1}{4}(3) + \frac{1}{4} (4)\) gives the
inequality \(x+y \geq 2\).  Hence, no feasible solution to 
\@ref(eq:LP) can have objective function value less than \(2\).
But we have found one feasible solution with objective function value
\(2\).  Hence, \(2\) is the optimal value.


## Fundamental Theorem of Linear Programming

Having used Fourier-Motzkin elimination to solve a linear programming
problem, we now will go one step further and use the same technique
to prove the following important result.  


```{theorem, label="fund-lp", name="Fundamental Theorem of Linear Programming"}
For any given linear programming problem, exactly one of the following
holds:

1. the problem is infeasible;

2. the problem is unbounded;

3. the problem has an optimal solution.

```

*Proof.*
Without loss of generality, we may assume that the linear programming
problem is of the form
\begin{equation}
\begin{array}{rl}
\min & \vec{c}^\T \vec{x}  \\
\text{s.t.} & \mm{A} \vec{x} \geq \vec{b}
(\#eq:fund-lp-P)
\end{array}
\end{equation}
where \(m\) and \(n\) are positive integers,
\(\mm{A} \in \RR^{m\times n}\), 
\(\vec{b} \in \RR^m\), \(\vec{c} \in \RR^n\),
and \(\vec{x}= \begin{bmatrix} x_1\\\vdots \\ x_n\end{bmatrix}\) 
is a tuple of variables.
Indeed, any linear programming problem can be converted to a
linear programming problem in
the form of \@ref(eq:fund-lp-P) having the same feasible region
and optimal solution set.  To see this, note that a constraint of the form
\(\mathbf{a}^\T \vec{x} \leq \beta\) can be written as
\(-\mathbf{a}^\T \vec{x} \geq -\beta\);
a constraint of the form \(\mathbf{a}^\T \vec{x} = \beta\) written as
a pair of constraints \(\mathbf{a}^\T \vec{x} \geq \beta\) and
\(-\mathbf{a}^\T \vec{x} \geq -\beta\); and a maximization problem
is equivalent to the problem that minimizes the 
negative of the objective function subject to the same constraints.


Suppose that \@ref(eq:fund-lp-P) is not infeasible.
Form the system
\begin{align}
\begin{split}
z- \vec{c}^\T \vec{x} & \geq 0\\
-z+ \vec{c}^\T \vec{x} & \geq 0 \\
\mm{A}\vec{x} & \geq \vec{b}.
\end{split}
(\#eq:fund-lp-S)
\end{align} 
Solving \@ref(eq:fund-lp-P) is equivalent to finding
among all the solutions to \@ref(eq:fund-lp-S)
one that minimizes \(z\), if it exists.
Eliminating the variables \(x_1,\ldots,x_n\) (in any order) using
Fourier-Motzkin elimination gives a system of linear inequalities
(S) containing at most the variable \(z\).
By scaling, we may assume that the each coefficient of \(z\)
in (S) is \(1\), \(-1\), or \(0\).
Note that any \(z\) satisfying (S)
can be extended to a solution to \@ref(eq:fund-lp-S)
and the \(z\) value from
any solution to \@ref(eq:fund-lp-S) must satisfy (S).

That \@ref(eq:fund-lp-P) is not unbounded implies that
(S) must contain an inequality
of the form \(z \geq \beta\) for some \(\beta \in \RR.\)  (Why?)
Let all the inequalites in which the coefficient of \(z\) is positive be
\[z \geq \beta_i\]
where \(\beta_i \in \RR\) for \(i = 1,\ldots,p\) for
some positive integer \(p\).
Let \(\gamma = \max\{\beta_1,\ldots,\beta_p\}\).
Then for any solution \(x,z\) to \@ref(eq:fund-lp-S),
\(z\) is at least \(\gamma\).
But we can set \(z = \gamma\) and extend it to a solution to
\@ref(eq:fund-lp-S).
Hence, we obtain an optimal solution for \@ref(eq:fund-lp-P) and
\(\gamma\) is the optimal value.  This completes the proof of
the theorem.

\(\qed\)

**Remark.** We can construct multipliers
to infer the inequality \(\vec{c}^\T \vec{x} \geq \gamma\) from
the system \(\mm{A}\vec{x} \geq \vec{b}\).
Because we obtained the inequality \(z \geq \gamma\)
using Fourier-Motzkin elimination,
there must exist real numbers \(\alpha, \beta, y^*_1,\ldots, y^*_m\geq 0\)
such that
\[
\begin{bmatrix}\alpha & \beta & y^*_1 & \cdots &y^*_m\end{bmatrix}
\begin{bmatrix}
1 & -\vec{c}^\T  \\
-1 & \vec{c}^\T  \\
0 & \mm{A}
\end{bmatrix}
\begin{bmatrix} z \\ \vec{x} \end{bmatrix}
\geq
\begin{bmatrix}\alpha & \beta & y^*_1 & \cdots &y^*_m\end{bmatrix}
\begin{bmatrix} 0 \\ 0\\ \vec{b} \end{bmatrix}
\]
is identically  \(z \geq \gamma\).
Note that we must have \(\alpha-\beta = 1\) and
\[\mathbf{y}^* \geq \mathbf{0},~{\mathbf{y}^*}^\T \mm{A}
= \vec{c}^\T ,~\mbox{and }
{\mathbf{y}^*}^\T \vec{b} = \gamma\]
where \(\mathbf{y}^* = [y^*_1,\ldots,y^*_m]^\T \).
Hence, \(y^*_1,\ldots,y^*_m\) are the desired multipliers.,


The significance of the fact
that we can infer \(\vec{c}^\T \vec{x} \geq \gamma\)
where \(\gamma\) will be discussed in more details when we
look at duality theory for linear programming.