Linear Programming

The One Thing

Linear programming optimises a linear objective function subject to linear constraints. For a bounded feasible region, the maximum or minimum occurs at at least one corner point, so the standard graphical method is to identify the feasible region, determine its corner points, and evaluate the objective function at each one.

Definitions and Results

• Decision variables: The unknown quantities to be determined, such as the number of products to manufacture.
• Objective function: A linear expression to be maximised or minimised, usually representing profit, cost, time, or output. Its standard form is

$$\text{Maximise or minimise }Z=ax+by.$$

• Constraints: Linear equations or inequalities representing limitations on resources, capacity, demand, or other conditions. Examples include

$$a_{1}x+b_{1}y\le c_1,a_{2}x+b_{2}y\ge c_2.$$

• Non-negativity restrictions: Conditions such as

$$x\ge 0,y\ge 0,$$ stating that quantities represented by the variables cannot be negative.

• Feasible region: The common region containing all points satisfying every constraint, including the non-negativity restrictions.
• Feasible solution: Any ordered pair, or set of variable values, satisfying all the constraints.
• Corner point: A vertex of the feasible region formed by the intersection of boundary lines.
• Optimal solution: A feasible solution giving the greatest or least value of the objective function, according to whether the problem is a maximisation or minimisation problem.
• Bounded feasible region: A feasible region enclosed within finite boundaries. In this case, a linear objective function generally has both a maximum and a minimum.
• Unbounded feasible region: A feasible region extending indefinitely in at least one direction. An optimum may exist, but there may be no maximum or no minimum, depending on the direction in which the objective function increases or decreases.
• Redundant constraint: A constraint that does not alter the feasible region because it is already implied by the other constraints.
• Iso-profit or iso-cost line: A line obtained by assigning a fixed value to the objective function. Shifting this line parallel to itself indicates the direction in which the objective function improves.
• Linear programming model: A representation of a practical optimisation problem using decision variables, a linear objective function, and a system of linear inequalities or equations. The objective function and every constraint must be linear.
• Corner-point principle: If a linear programming problem has an optimum in a bounded feasible region, at least one corner point gives that optimum.
• Empty feasible region: If the constraints are inconsistent, no point satisfies them all; consequently, the problem has no feasible solution.
• Optimality along an edge: If the objective function has the same optimum value at two adjacent corner points, every point on the line segment joining those points is also optimal.
• Practical interpretation: A mathematical optimum must be checked against the meaning of the variables, including units and restrictions such as whole-number production quantities.

Worked Methods

Formulating the linear programming model

• Define the decision variables. For example, let $x$ and $y$ represent quantities such as the numbers of two products manufactured.
• Formulate the objective function, such as

$$\text{Maximise or minimise }Z=ax+by.$$

• Translate limitations on resources, capacity, demand, or other conditions into linear constraints, for example

$$a_{1}x+b_{1}y\le c_1,a_{2}x+b_{2}y\ge c_2.$$

• Include the non-negativity restrictions

$$x\ge 0,y\ge 0.$$

• Confirm that the objective function and all constraints are linear.

Graphing the constraints and identifying the feasible region

• For each constraint, replace the inequality sign with an equals sign to obtain its boundary line.
• Draw each boundary line.
• Use a test point, commonly $(0,0)$ when it is not on the boundary line, to determine which side of each line satisfies the original inequality.
• Shade the appropriate half-plane for each constraint.
• Intersect all shaded half-planes with the first quadrant determined by

$$x\ge 0,y\ge 0.$$

• The common shaded region is the feasible region. Every point in it is a feasible solution.
• Check whether the region is bounded, unbounded, or empty. An empty region indicates inconsistent constraints and therefore no feasible solution.

Finding corner points

• Identify every vertex of the feasible region.
• Determine the coordinates of each corner point by solving the equations of the intersecting boundary lines.
• Check that each resulting point satisfies every original constraint, not merely the two equations used to calculate it.
• Exclude intersections that do not lie in the feasible region.
• Note any redundant constraint: it may be present in the model but does not alter the feasible region.

Evaluating the objective function

• Substitute the coordinates of every relevant corner point into the objective function $Z=ax+by$.
• For a maximisation problem, compare the values and choose the greatest.
• For a minimisation problem, compare the values and choose the least.
• If two adjacent corner points give the same optimum value, every point on the line segment joining them is also optimal.
• State the optimal variable values, the optimal value of $Z$, and the relevant units.
• Interpret the result in context. If the variables represent physical quantities, apply practical restrictions such as whole-number production quantities.

Using iso-profit or iso-cost lines

• Assign a fixed value to the objective function $Z=ax+by$.
• Draw the resulting iso-profit or iso-cost line.
• Shift the line parallel to itself across the feasible region.
• For maximisation, move it in the direction of increasing $Z$; for minimisation, move it in the direction of decreasing $Z$.
• The last point or edge of contact with the feasible region identifies the optimum, subject to the same corner-point and practical checks.

Applying the complete graphical procedure

The common graphical solution procedure is:

• Define the variables.
• Formulate the objective function.
• Write the constraints and non-negativity restrictions.
• Graph the constraints.
• Identify the feasible region.
• Locate its corner points.
• Evaluate the objective function at every corner point.
• State the maximum or minimum and interpret the conclusion in context.

The method applies to practical problems involving the efficient allocation of limited resources, including production, transportation, diet planning, and profit maximisation.

Where It Goes Wrong

• Omitting $x\ge 0$ and $y\ge 0$, and therefore failing to restrict the feasible region to the first quadrant when the variables represent non-negative quantities.
• Shading the wrong side of a boundary line because no test point, commonly $(0,0)$ when available, is used to verify the inequality.
• Treating a boundary inequality as an equality throughout, rather than using the equality only to draw the boundary line and then selecting the correct half-plane.
• Checking only some corner points instead of evaluating the objective function at every corner point relevant to the feasible region.
• Assuming that an unbounded feasible region has no optimum; it may have a finite optimum, although it may also have no maximum or no minimum depending on the objective-function direction.
• Reporting a mathematical optimum without checking practical restrictions, including units and whole-number requirements for physical quantities.

What Gets Asked

• Define decision variables, the objective function, constraints, non-negativity restrictions, feasible solutions, feasible regions, corner points, and optimal solutions.
• Formulate a linear programming model from a practical situation involving production, transportation, diet planning, or profit maximisation.
• Graph linear inequalities and identify the feasible region.
• Determine whether a feasible region is bounded, unbounded, empty, or altered by a redundant constraint.
• Find corner points by solving pairs of boundary-line equations.
• Apply the corner-point principle to find a maximum or minimum.
• Evaluate $Z=ax+by$ at all corner points and state the optimal value.
• Use iso-profit or iso-cost lines to explain the direction of optimisation.
• Explain why every point on a line segment may be optimal when adjacent corner points have the same objective-function value.
• Interpret the final answer in context, including units and practical restrictions such as whole-number production quantities.