1. Introduction to Linear Programming

Linear Programming

With linear programming, we have some:

• Linear Objective Function which is the quantity to be maximised / minimised.
• Linear Constraints which is a set of linear inequalities restricting the ‘feasible’ solutions.

A linear programming problem may look like:

$$\begin{array}{rlrl}\text{Maximise }& 2x+3y& & \\ \text{Subject to }& 3x+2y& & \le 15\\ & 2y-x& & \le 5\\ & x+2y& & \le 7\end{array}$$

There may be a unique solution, infinitely many solutions or no solution.

Matrix Notation

It is common for these problems to be represented in a matrix-vector equation:

$$\begin{array}{rl}\left[\begin{array}{cc}3& 2\\ -1& 2\\ 1& 2\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]& \le \left[\begin{array}{c}15\\ 5\\ 7\end{array}\right]\\ A\vec{x}& \le \vec{b}\end{array}$$

Formal Linear Programming Definition

Formally, a linear programming problem can be defined as follows: Input:

• A set of linear constraints, $A\vec{x}\le \vec{b}$.
• A linear objective function, $f:{\mathbb{R}}^n\to \mathbb{R}$. Output: A solution $\vec{x}\in ({\mathbb{R}}^{\ge 0}{)}^n$ such that:

1. $\vec{x}$ satisfies the constraints $A\vec{x}\le \vec{b}$
2. $f(\vec{x})$ is maximal

The Feasible Region is the set of all possible solutions satisfying the linear constraints.

$$R=\{\vec{x}\in {\mathbb{R}}^n:A\vec{x}\le \vec{b}\}$$

The set of optimal solutions for a given objective function $f:{\mathbb{R}}^n\to \mathbb{R}$ is:

$$\{\vec{x}\in R:\forall \vec{y}\in R(f(\vec{x})\ge f(\vec{y}))\}\subseteq R$$