Introduction to Linear Programming
When both the goal and every restriction are linear, optimization becomes remarkably tractable — and remarkably useful. Linear programming is the single most applied technique in all of operations research, scheduling refineries, planning power dispatch, and routing logistics every day. This chapter lays the groundwork: the LP model and the assumptions behind it, the standard forms solvers expect, the idea of a basic feasible solution, and the beautiful geometric fact that the best answer always sits at a corner of the feasible region.
- The general linear-programming model — a linear objective over linear constraints.
- The four assumptions LP rests on: proportionality, additivity, divisibility, certainty.
- The difference between standard and canonical form and why each is used.
- What feasible, basic, and basic feasible solutions are, and how they relate to vertices.
- Why the feasible region is a convex polyhedron and the optimum sits at a corner.
- The four special cases: unique, alternative, unbounded, and infeasible solutions.
What Is a Linear Program?
A linear program (LP) optimizes a linear objective function subject to a set of linear equality and inequality constraints, with the variables usually required to be non-negative. Every term is first-degree — no squares, no products of variables, no exponentials. In full generality:
The \(c_j\) are cost or profit coefficients, the \(a_{ij}\) are technological coefficients (how much of resource \(i\) each unit of \(x_j\) consumes), and the \(b_i\) are the right-hand-side limits. In matrix shorthand this is simply \(\max\, \mathbf{c}^{\mathsf T}\mathbf{x}\) subject to \(A\mathbf{x} \le \mathbf{b},\ \mathbf{x} \ge \mathbf{0}\). Despite the simplicity, LPs model an astonishing range of decisions — because so many real relationships are, to a good approximation, linear.
The Assumptions of Linear Programming
The linearity that makes LP so powerful also embeds four assumptions. Knowing them tells you when an LP model is faithful — and when reality has outgrown it and you need the nonlinear or integer methods of later chapters.
| Assumption | Meaning | Broken when… |
|---|---|---|
| Proportionality | Each variable's contribution scales linearly with its value | Economies of scale, setup costs |
| Additivity | Total effect is the sum of individual effects — no interactions | Cross-terms like \(x_1 x_2\) |
| Divisibility | Variables may take fractional values | Whole units only → integer programming |
| Certainty | All coefficients are known exactly | Random demand/prices → stochastic LP |
Standard and Canonical Forms
Chapter 2 introduced the conversions; here is the LP-specific summary. The standard form (used by the simplex method) has equalities and non-negative variables; the canonical form (used for duality) has \(\le\) inequalities for a maximization. Slack and surplus variables bridge the two.
Recall the moves: add a slack to each "\(\le\)" (\(\mathbf{a}^{\mathsf T}x + s = b\)), subtract a surplus from each "\(\ge\)" (\(\mathbf{a}^{\mathsf T}x - s = b\)), split any free variable as \(x = x^+ - x^-\), and multiply through any negative right-hand side by \(-1\). After these steps every LP looks the same to the algorithm, which is exactly the point.
Feasible and Basic Solutions
With the LP in standard form we have \(m\) equations in \(n\) variables (\(n > m\) after adding slacks). The vocabulary below is the language the simplex method speaks.
| Term | Definition |
|---|---|
| Feasible solution | Any \(x\) satisfying all constraints, including \(x \ge 0\) |
| Feasible region | The set of all feasible solutions — a convex polyhedron |
| Basic solution | Set \(n - m\) variables to zero (non-basic); solve for the rest (basic) |
| Basic feasible solution (BFS) | A basic solution in which every variable is \(\ge 0\) |
| Degenerate BFS | A BFS with a basic variable equal to zero |
Each choice of which \(m\) variables are basic gives one basic solution (when the system is solvable). Only those with all components \(\ge 0\) are feasible. The great insight of the next two sections is that these finitely many basic feasible solutions are exactly the corners of the feasible region — so the optimum must be among them.
The Geometry of Linear Programming
Each linear constraint \(\mathbf{a}^{\mathsf T}x \le b\) is a halfspace, and the feasible region is the intersection of these halfspaces — a convex polyhedron (Chapter 3). The objective \(z = \mathbf{c}^{\mathsf T}x\) has straight, parallel contour lines; optimizing means sliding a contour as far as possible in the improving direction until it is about to leave the region. That contact happens at a vertex.
The Corner-Point (Extreme-Point) Theorem
The geometric observation is elevated to a theorem — the Fundamental Theorem of Linear Programming — which is what makes LP finitely solvable. The corners of the polyhedron are its extreme points (vertices), and these correspond exactly to the basic feasible solutions.
Because extreme points are basic feasible solutions and there are at most \(\binom{n}{m}\) of them, an LP can be solved by examining a finite list of corners rather than the infinite interior. The simplex method (Chapter 8) is precisely a clever walk from corner to improving corner — never wandering through the interior at all.
Special Cases
Not every LP has a single tidy answer. Four outcomes are possible, and recognising them geometrically saves a great deal of confusion at the tableau.
| Case | Geometry | At the tableau |
|---|---|---|
| Unique optimum | Best contour touches one vertex | One optimal BFS |
| Alternative optima | Objective parallel to a binding edge | A non-basic variable has zero reduced cost |
| Unbounded | Region open in the improving direction | No leaving variable in the ratio test |
| Infeasible | Constraints contradict; region empty | Artificial variable stays positive |
Worked Examples
Problem. Describe the feasible region of \(x_1 + x_2 \le 4,\ x_1 + 3x_2 \le 6,\ x_1, x_2 \ge 0\), and list its vertices.
Solution. Four half-planes bound a convex polygon. Its corners are the axis intercepts and the intersection of the two constraint lines: solving \(x_1 + x_2 = 4\) and \(x_1 + 3x_2 = 6\) gives \(2x_2 = 2 \Rightarrow x_2 = 1,\ x_1 = 3\). The vertices are \((0,0),\ (4,0),\ (3,1),\ (0,2)\) — the finite candidate set the optimum must live in.
Problem. Maximize \(z = 3x_1 + 4x_2\) over the region of Example 1.
Solution. By the corner-point theorem, evaluate \(z\) at each vertex:
The maximum is \(z^\star = 13\) at the interior vertex \((3,1)\). Checking only the four corners settled it — no need to search the region's interior.
Problem. Put the constraints \(x_1 + x_2 \le 4,\ x_1 + 3x_2 \le 6\) in standard form and count the basic solutions.
Solution. Adding slacks \(s_1, s_2\) gives \(x_1 + x_2 + s_1 = 4,\ x_1 + 3x_2 + s_2 = 6\): \(m = 2\) equations, \(n = 4\) variables. The number of basic solutions is at most
Four of these turn out to be feasible (all variables \(\ge 0\)) — exactly the four polygon vertices from Example 1. The other two are basic but infeasible (some variable negative).
Problem. Maximize \(z = 2x_1 + 2x_2\) subject to \(x_1 + x_2 \le 4,\ x_1, x_2 \ge 0\).
Solution. The objective \(2x_1 + 2x_2\) is a constant multiple of the binding constraint \(x_1 + x_2\), so its contours are parallel to the edge \(x_1 + x_2 = 4\). Every point on that edge gives \(z = 8\) — the vertices \((4,0)\) and \((0,4)\) and the whole segment between them are all optimal. There are infinitely many optimal solutions.
Problem. Maximize \(z = x_1 + x_2\) subject to \(x_1 - x_2 \le 1,\ x_1, x_2 \ge 0\).
Solution. The feasible region extends without limit up and to the right (increase \(x_2\) freely, and \(x_1\) with it). The objective grows along that direction with no bound, so \(z \to \infty\): the LP is unbounded and has no finite optimum. A well-posed model almost always has a missing constraint when this happens.
Problem. Is there any point satisfying \(x_1 + x_2 \le 1\) and \(x_1 + x_2 \ge 3\) with \(x_1, x_2 \ge 0\)?
Solution. No. The first demands \(x_1 + x_2 \le 1\); the second demands \(x_1 + x_2 \ge 3\); the two half-planes never overlap, so the feasible region is empty and the LP is infeasible. No objective can be optimized over an empty set — the model itself must be repaired.
Chapter Summary
Linear objective \(\mathbf{c}^{\mathsf T}x\) over linear constraints \(A x \le b,\ x \ge 0\).
Proportionality, additivity, divisibility, certainty — each, when broken, points to another method.
\(A x = b,\ x \ge 0\) via slack and surplus variables — what the simplex method reads.
Set \(n-m\) variables to zero and solve; if all \(\ge 0\), it is a BFS — a vertex.
If an optimum exists, one occurs at an extreme point — search corners, not the interior.
Unique, alternative (parallel objective), unbounded (open region), infeasible (empty region).
Problems
For each item, sketch the region or reason about the corners; identify the special case where relevant. Difficulty rises down the list.
- Write the general LP in matrix form and label \(\mathbf{c}\), \(A\), \(\mathbf{b}\), and the sign restrictions.
- State which LP assumption is violated by: (a) a volume discount, (b) a "buy whole machines only" rule, (c) demand that is a random variable.
- Convert to standard form: \(\max\ 5x_1 + 4x_2\) s.t. \(6x_1 + 4x_2 \le 24,\ x_1 + 2x_2 \le 6,\ x \ge 0\).
- List the vertices of the region \(x_1 + 2x_2 \le 8,\ 3x_1 + 2x_2 \le 12,\ x \ge 0\).
- For the region in Problem 4, maximize \(z = 2x_1 + 3x_2\) by checking corners.
- How many basic solutions can a standard-form LP with 3 equality constraints and 5 variables have?
- Give a small LP whose objective is parallel to a constraint edge, and identify all its optimal solutions.
- Construct a two-variable LP that is unbounded, and explain which constraint is "missing."
- Construct a two-variable LP that is infeasible, and identify the contradictory constraints.
- Explain, in your own words, why the optimum of an LP can always be found at a vertex rather than in the interior.
- Define a degenerate basic feasible solution and sketch a region where one occurs (three constraint lines through one point).
- A workshop makes products P and Q. P yields ₹5 and uses 2 h machining, 1 h finishing; Q yields ₹4 and uses 1 h machining, 1 h finishing; 40 h machining and 30 h finishing are available. Formulate the LP, list all vertices of the feasible region, find the optimum by the corner-point theorem, and state the values of the slack variables at the optimum.