As the study of systems of linear equations forms the core of introductory linear algebra, the study of systems of linear inequalities forms the core of linear programming.
The word “programming” in “linear programming” takes on the classical meaning of the word which means “arranging according to a plan”. The word “linear” indicates the sort of constraints under which such plans are made.
These notes cover basic knowledge required to solve systems of linear inequalities which can then be applied to optimize a linear objective function subject to linear constraints. The main tool is Fourier-Motzkin elimination method which is in some ways analogous to Gauss-Jordan elimination for linear equations. Classic duality theory for linear programming is developed in full. The power of linear programming duality is illustrated and used time and again in the subsequent segments.
As the content of these notes is designed towards building a minimal theoretical foundation on linear programming, issues of computational efficiency is not discussed. In particular, no mention is made on the highly popular family of interior-point methods which are computationally efficient both in theory and in practice. Once one possesses an understanding of the fundamentals on linear programming, one should be well equipped to pursue such topics on one's own.
These notes do not depend much on results outside what one can find in a freshman linear algebra course. Below is a checklist of concepts that should be familiarized before tackling the content of these notes:
It is highly recommended that the following problems be completed before beginning.
Let \(m\) and \(n\) be positive integers. Let \(\mathbf{A} \in \mathbb{R}^{m \times n}\). Let \(\mathbf{b} \in \mathbb{R}^m\). Let \(\mathbf{x} = \begin{bmatrix} x_1 \\ \vdots \\ x_n\end{bmatrix}\) be a tuple of variables. Prove that the system of linear equations \(\mathbf{A}\mathbf{x} = \mathbf{b}\) has no solution if and only if there exist \(\mathbf{y} \in \mathbb{R}^m\) such that \(\mathbf{y}^\mathsf{T}\mathbf{A} = \mathbf{0}\) and \(\mathbf{y}^\mathsf{T}\mathbf{b} \neq 0\).
Let \(a_n\) be the sequence of integers defined by \begin{eqnarray*} a_1 & = & 1 \\ a_2 & = & 8 \\ a_n & = & a_{n-1} + 2a_{n-2}~~~n = 3,4,5,\ldots. \end{eqnarray*} Prove that \(a_n = 3\cdot 2^{n-1} + 2 (-1)^n\) for all \(n = 1,2,3,\ldots\).