1.1 The linear programming model
Definition 1.1.1. A linear programme (LP) consists of
- (i)
- decision variables \(x = (x_1, \ldots , x_n)\), the quantities to be chosen;
- (ii)
- a linear objective function \(c^{\mathsf T}x = c_1x_1 + \cdots + c_nx_n\), to be maximised or minimised;
- (iii)
- finitely many linear constraints, each of the form \(a^{\mathsf T}x \leq \beta \), \(a^{\mathsf T}x \geq \beta \) or \(a^{\mathsf T}x = \beta \); usually including the non-negativity constraints \(x_j \geq 0\).
A point satisfying all the constraints is feasible; the set of feasible points is the feasible region; a feasible point at which the objective attains its best value over the feasible region is optimal. An LP is infeasible if it has no feasible point and unbounded if the objective can be made arbitrarily good on the feasible region.
The model rests on four assumptions, which should be checked in every application:
- proportionality: the contribution of each activity to the objective and to each constraint is proportional to its level (no set-up costs, no economies of scale);
- additivity: the total is the sum of the contributions of the activities (no interactions);
- divisibility: the variables may take fractional values;
- certainty: all the coefficients are known constants.
When divisibility fails we need integer programming (the section on integer programming); when proportionality fails, non-linear programming (the section on non-linear programming); when certainty fails, the sensitivity analysis of the section on sensitivity and the stochastic models later in the course.
Definition 1.1.2. An LP is in standard form if it reads \[ \text {minimise } c^{\mathsf T}x \quad \text {subject to}\quad Ax = b, \quad x \geq 0 , \] with \(A\) an \(m \times n\) matrix and \(b \in \mathbb R^m\), and in canonical form if it reads: maximise \(c^{\mathsf T}x\) subject to \(Ax \leq b\), \(x \geq 0\).
Proposition 1.1.3. Every LP can be written in standard form, with the same optimal value (up to sign) and an explicit correspondence between feasible points.
Proof. Replace maximisation of \(c^{\mathsf T}x\) by minimisation of \(-c^{\mathsf T}x\). Replace an inequality \(a^{\mathsf T}x \leq \beta \) by \(a^{\mathsf T}x + s = \beta \) with a new slack variable \(s \geq 0\), and \(a^{\mathsf T}x \geq \beta \) by \(a^{\mathsf T}x - s = \beta \) with a surplus variable \(s \geq 0\). Replace a variable \(x_j\) that is free in sign by \(x_j^+ - x_j^-\) with \(x_j^\pm \geq 0\). Each step maps feasible points to feasible points with the same objective value, and back. □
The slack in a constraint is the amount of the resource left unused at a solution; it will turn out, in the section on duality, to be paired with the value of that resource.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.