Linear Programming | Sahithyan's Notes

Linear programming focuses on solving optimization problems with a linear objective function subject to linear constraints.

Programming here means planning or scheduling, not computer programming. The term predates modern computing: the US military used “program” for a training or logistics schedule, and George Dantzig, who developed the simplex algorithm in 1947, called his method “programming in a linear structure” to describe planning resource allocation under constraints.

Decision Variable

A quantity $x_j$ ( $j = 1, \dots, n$ ) whose value is chosen by the solver to optimize the objective. The vector $x = (x_1, \dots, x_n)^T \in \mathbb{R}^n$ is determined by solving the LP.

Linear Objective Function

A function $z = \sum_{j=1}^n c_j x_j = c^T x$ with $c \in \mathbb{R}^n$ , to be maximized or minimized. Linear in the $x_j$ .

Linear Constraint

A linear inequality or equality restricting $x$ , of the form

\sum_{j=1}^n a_{ij} x_j \ \{\le,\ =,\ \ge\}\ b_i

Structural constraint
Limits imposed by resources, demand, or policy.
Non-negativity constraint
$x_j \ge 0$ for every decision variable. Negative quantities are not physically meaningful.
Bound constraint
Fixes an upper or lower limit on a single variable.

Types by direction:

Less than or equal to ( $\le$ )
Caps usage, common for limited resources.
Greater than or equal to ( $\ge$ )
Enforces a minimum, common for demand or quality requirements.
Equal to ( $=$ )
Forces exact equality, common for balance conditions.

Linear Program

A linear program is an optimization problem with a linear objective function subject to linear constraints. With $n$ variables and $m$ constraints:

\begin{aligned} \text{maximize (or minimize)} \quad & z = \sum_{j=1}^n c_j x_j \\ \text{subject to} \quad & \sum_{j=1}^n a_{ij} x_j \le b_i \quad (i = 1, \dots, m) \\ & x_j \ge 0 \quad (j = 1, \dots, n) \end{aligned}

In matrix form, with $c \in \mathbb{R}^n$ , $A \in \mathbb{R}^{m \times n}$ , $b \in \mathbb{R}^m$ :

\begin{aligned} \max_{x \in \mathbb{R}^n} \quad & z = c^T x \\ \text{s.t.} \quad & Ax \le b \\ & x \ge 0 \end{aligned}

$x$ : decision variables
$c$ : objective coefficients
$A = [a_{ij}]$ : constraint coefficients
$b$ : constraint bounds

To solve a linear program:

Identify decision variables
Express the objective and constraints as linear functions
Use a linear programming solver to find the optimal solution

Standard Model Types

A standard model type is a recurring pattern of variables, objective, and constraints for building a linear program.

Product mix
Maximize profit from $n$ products under limited resources.
Blending
Minimize cost of mixing $n$ $n$ ingredients into a product meeting quality specs.
- Diet
  Special case of blending. Minimize food cost subject to minimum nutrient requirements.
Transportation
Minimize shipping cost of one commodity from $m$ $m$ supply points to $n$ $n$ fixed demand points.
- Assignment
  Special case of transportation with unit supply and demand. Minimize cost of assigning $n$ agents to $n$ tasks, one-to-one.
Transshipment
Minimize shipping cost when goods pass through intermediate nodes instead of direct supply-to-demand routes.

Choosing Between Models

LP requires linear relationships, a single objective, no time-staging, and no integrality restriction. Use instead:

Nonlinear programming
Relationships aren’t linear.
Pure integer programming
Every variable must be an integer.
Mixed integer linear programming
Only some variables must be integers.
Goal programming
Multiple competing objectives balanced against targets.
Dynamic programming
Sequential, stage-based decisions where one stage affects later ones.