Linear Programming — chapter notes

A linear programming problem asks for the maximum or minimum of a linear function of the decision variables, subject to linear constraints.

• Decision variables $x, y$: the quantities to be chosen.
• Objective function $Z = ax + by$: profit, cost or time, to be optimised.
• Constraints: linear inequalities from the limits of the problem.
• Non-negativity: $x \ge 0$, $y \ge 0$.
• Optimisation: finding the feasible plan with the best value of $Z$.

Advantages: best use of scarce resources; clear, systematic decisions; shows bottlenecks and spare capacity; easy to re-solve when data change.

Limitations: assumes linearity (proportional profit and resource use); all coefficients must be known exactly; one objective at a time; answers may be fractional for whole items.

Application areas: production planning in factories, diet and feed mixing, transport of goods from depots to markets, allocation of advertising budgets, investment choices.

• Manufacturing: maximise profit; constraints usually "at most" ($\le$) on machine hours, labour and material.
• Diet: minimise cost; constraints usually "at least" ($\ge$) on nutrients.
• Transportation-type: minimise transport cost; express every route through two variables using supplies and demands, then require each amount to be non-negative.

Steps: name the variables with units; write $Z$ and its direction; turn each limit into an inequality; add $x, y \ge 0$.

Each inequality $ax + by \le c$ (or $\ge c$) is a half-plane bounded by the line $ax + by = c$. Draw the line from its intercepts, then test a point not on it (usually the origin) to choose the side.

The feasible region is the common part of all the half-planes in the first quadrant. Its corner points are intersections of pairs of boundary lines (including the axes) that satisfy every constraint.

The region may be bounded, unbounded or empty. The ISC course uses at most three constraints besides non-negativity, so a region has at most five corners.

Corner point theorem. If the feasible region is bounded and non-empty, $Z = ax + by$ has both a maximum and a minimum, each at a corner point.

Method: find every corner; evaluate $Z$ at each; the largest and smallest values are the maximum and minimum.

Unbounded regions: let $M$ be the best corner value. For a maximum, if the open half-plane $ax + by > M$ has no point in common with the region, $M$ is the maximum; otherwise there is no maximum. (For a minimum use $ax + by < M$.)

• No optimum: on an unbounded region, a feasible point that beats the best corner value shows that the optimum does not exist in that direction (for example $Z = x + 2y$ on $x + y \ge 8$, $x + 3y \ge 12$ has no maximum).
• Infeasible: an empty region (for example $x + y \le 4$ with $3x + 2y \ge 18$) has no solution.
• Infinitely many optima: if $Z$ has the same best value at two adjacent corners, every point of the edge between them is optimal; the objective line is parallel to that edge.