Fundamental Theorem of Linear Programming

We now see a proof of the Fundamental Theorem of Linear Programming, which states that if a linear programming (LP) problem is not infeasible and is not unbounded, then it has an optimal solution.

Remark. It is possible to construct multipliers to infer the inequality ${\mathbf{c}}^{\mathsf{T}}\mathbf{x}\ge \gamma$ from the system $\mathbf{A}\mathbf{x}\ge \mathbf{b}$. Because we obtained the inequality $z\ge \gamma$ using Fourier-Motzkin elimination, there must exist real numbers $\alpha ,\beta ,y_1^{\ast },\dots ,y_m^{\ast }\ge 0$ such that $$\left[\begin{array}{ccccc}\alpha & \beta & y_1^{\ast }& \cdots & y_m^{\ast }\end{array}\right]\left[\begin{array}{cc}1& -{\mathbf{c}}^{\mathsf{T}}\\ -1& {\mathbf{c}}^{\mathsf{T}}\\ 0& \mathbf{A}\end{array}\right]\left[\begin{array}{c}z\\ \mathbf{x}\end{array}\right]\ge \left[\begin{array}{ccccc}\alpha & \beta & y_1^{\ast }& \cdots & y_m^{\ast }\end{array}\right]\left[\begin{array}{c}0\\ 0\\ \mathbf{b}\end{array}\right]$$ is identically $z\ge \gamma$. Note that we must have $\alpha -\beta =1$ and $${\mathbf{y}}^{\ast }\ge \mathbf{0},{{\mathbf{y}}^{\ast }}^{\mathsf{T}}\mathbf{A}={\mathbf{c}}^{\mathsf{T}},\text{and }{{\mathbf{y}}^{\ast }}^{\mathsf{T}}\mathbf{b}=\gamma$$ where ${\mathbf{y}}^{\ast }=[y_1^{\ast },\dots ,y_m^{\ast }{]}^{\mathsf{T}}$. Hence, $y_1^{\ast },\dots ,y_m^{\ast }$ are the desired multipliers.,

The significance of the fact that we can infer ${\mathbf{c}}^{\mathsf{T}}\mathbf{x}\ge \gamma$ where $\gamma$ is the optimal value will be discussed in more details when we look at duality theory for linear programming.

Worked examples

1. Show that ${\mathbf{x}}^{\ast }$ is an optimal solution to $$\begin{array}{rl}min& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ \text{s.t.}& \mathbf{A}\mathbf{x}\ge \mathbf{b}\end{array}$$ if and only if $(z,\mathbf{x})=({\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\ast },{\mathbf{x}}^{\ast })$ is an optimal solution to $$\begin{array}{rl}min& z\\ \text{s.t.}& z-{\mathbf{c}}^{\mathsf{T}}\mathbf{x}\ge 0\\ & \mathbf{A}\mathbf{x}\ge \mathbf{b}\end{array}$$

   The discussion in the notes above shows that ${\mathbf{x}}^{\ast }$ is an optimal solution to $$\begin{array}{rl}min& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ \text{s.t.}& \mathbf{A}\mathbf{x}\ge \mathbf{b}\end{array}$$ if and only if $(z,\mathbf{x})=({\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\ast },{\mathbf{x}}^{\ast })$ is an optimal solution to $$\begin{array}{rl}min& z\\ \text{s.t.}& z-{\mathbf{c}}^{\mathsf{T}}\mathbf{x}=0\\ & \mathbf{A}\mathbf{x}\ge \mathbf{b}\end{array}$$ Therefore, this question is saying that “$=$” can be replaced with “$\ge$”.

   Suppose that ${\mathbf{x}}^{\ast }$ is an optimal solution to $$\begin{array}{rl}min& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ \text{s.t.}& \mathbf{A}\mathbf{x}\ge \mathbf{b}.\end{array}$$ Clearly, $(z,\mathbf{x})=({\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\ast },{\mathbf{x}}^{\ast })$ is a feasible solution to $$\begin{array}{rl}min& z\\ \text{s.t.}& z-{\mathbf{c}}^{\mathsf{T}}\mathbf{x}\ge 0\\ & \mathbf{A}\mathbf{x}\ge \mathbf{b}.\end{array}$$ If it is not optimal, then there exist a feasible solution $z^{\prime },{\mathbf{x}}^{\prime }$ with $z^{\prime }<{\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\ast }$. Thus, ${\mathbf{x}}^{\prime }$ is a feasible solution to $$\begin{array}{rl}min& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ \text{s.t.}& \mathbf{A}\mathbf{x}\ge \mathbf{b}\end{array}$$ with objective function value at most $z^{\prime }<{\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\ast }$, contradicting the optimality of ${\mathbf{x}}^{\ast }$.

   Conversely, suppose that ${\mathbf{x}}^{\ast }$ is not an optimal solution to $$\begin{array}{rl}min& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ \text{s.t.}& \mathbf{A}\mathbf{x}\ge \mathbf{b}.\end{array}$$ Then there exists a feasible solution ${\mathbf{x}}^{\prime }$ such that ${\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\prime }<{\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\ast }$. Since $(z,\mathbf{x})=({\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\prime },{\mathbf{x}}^{\prime })$ and $(z,\mathbf{x})=({\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\ast },{\mathbf{x}}^{\ast })$ are both feasible solutions to $$\begin{array}{rl}min& z\\ \text{s.t.}& z-{\mathbf{c}}^{\mathsf{T}}\mathbf{x}\ge 0\\ & \mathbf{A}\mathbf{x}\ge \mathbf{b}\end{array}$$ and ${\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\prime }<{\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\ast }$, we see that $(z,\mathbf{x})=({\mathbf{c}}^{\mathsf{T}}{\mathbf{x}}^{\ast },{\mathbf{x}}^{\ast })$ is not an optimal solution.