Linear Programming

The One Thing

Linear programming optimizes a linear objective function subject to simultaneous linear constraints and non-negativity restrictions. In a two-variable problem with a bounded feasible region, the optimum generally occurs at a corner point.

Definitions and Results

• Linear Programming Problem: A problem involving the optimization of a linear objective function subject to linear inequalities or equations and non-negativity restrictions.
• Decision Variables: Unknown quantities whose values must be determined, usually represented by $x$ and $y$.
• Objective Function: The linear expression to be maximized or minimized, such as $Z=ax+by$.
• Constraints: Linear inequalities or equations representing limitations on the decision variables, such as resource, time, or production limits.
• Non-Negativity Constraints: Conditions requiring the decision variables to be non-negative, usually written as $x\ge 0$ and $y\ge 0$.
• Feasible Region: The common region containing all points that satisfy every constraint and the non-negativity conditions.
• Feasible Solution: Any ordered pair in the feasible region that satisfies every constraint.
• Optimal Solution: A feasible solution that gives the maximum or minimum value of the objective function.
• Corner Point: A vertex or extreme point of the feasible region formed by the intersection of boundary lines.
• Bounded Feasible Region: A feasible region enclosed within a finite area, so that both variables have limited ranges.
• Unbounded Feasible Region: A feasible region extending indefinitely in at least one direction.
• Iso-profit or Iso-cost Line: A line representing a fixed objective-function value, obtained by writing $ax+by=k$.
• General two-variable form: Optimise $Z=ax+by$, subject to linear constraints and $x\ge 0,y\ge 0$.
• Corner point principle: If an optimum exists for a linear programming problem with a bounded feasible region, it occurs at one or more corner points.
• Multiple optima: If the same optimum value occurs at two adjacent corner points, every point on the line segment joining them is also optimal.
• Empty feasible region: If the constraints have no common point, there is no feasible solution.
• Unbounded case: An unbounded feasible region may or may not have an optimum; the objective function must be examined in the direction of increase or decrease.
• Contextual interpretation: Units must be interpreted according to the problem, such as products, hours, kilograms, or rupees. Quantities generally cannot be negative, and whole-number restrictions may be required when fractional production is impractical.

Worked Methods

1. Graphing a constraint

• Begin with a constraint such as

$$ax+by\le c\text{or}ax+by\ge c.$$

• Draw the boundary line

$$ax+by=c.$$

• Because the inequality includes the boundary, use a solid line.
• Select a test point, commonly $(0,0)$, provided that it is not on the boundary line.
• Substitute the test point into the inequality to determine the correct half-plane.
• Shade the half-plane satisfying the constraint.

2. Constructing the feasible region

• Graph the boundary line for every linear constraint.
• Identify the appropriate half-plane for each inequality using a test point.
• Include the first-quadrant restrictions

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

• Take the intersection of all the shaded half-planes.
• The resulting common region is the feasible region.
• Any ordered pair within this region is a feasible solution because it satisfies every constraint simultaneously.

3. Maximising or minimising the objective function

• Define the decision variables $x$ and $y$.
• State all linear constraints and the non-negativity restrictions

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

• Write the objective function, for example

$$Z=ax+by.$$

• Graph the constraints and identify the feasible region.
• Determine the coordinates of every corner point, usually by finding intersections of boundary lines.
• Substitute each corner point into the objective function.
• For a maximisation problem, select the greatest objective-function value.
• For a minimisation problem, select the least objective-function value.
• State the result in context, including the relevant units such as products, hours, kilograms, or rupees.
• If two adjacent corner points give the same optimum, conclude that every point on the line segment joining them is also optimal.

4. Using an iso-profit or iso-cost line

• Start with the objective function

$$Z=ax+by.$$

• Set it equal to a constant:

$$ax+by=k.$$

• This produces an iso-profit or iso-cost line representing a fixed value of $Z$.
• Consider the direction in which $k$ increases for maximisation or decreases for minimisation.
• Compare this movement with the feasible region.
• In an unbounded feasible region, examine whether the objective function can continue improving indefinitely or whether a limiting boundary prevents this.

5. Applying the graphical method

The graphical method is mainly suitable for problems with two decision variables. A complete solution should include the constraints, the graph or identified feasible region, the corner points, the objective-function evaluations, and the final interpretation.

Where It Goes Wrong

• Treating a point that satisfies only some constraints as feasible; every constraint must be satisfied simultaneously.
• Forgetting the non-negativity conditions $x\ge 0$ and $y\ge 0$, which impose the first-quadrant restrictions.
• Drawing a dashed boundary for $ax+by\le c$ or $ax+by\ge c$; these inequalities include the boundary, so a solid line is required.
• Shading the wrong half-plane because the test point, commonly $(0,0)$, was not substituted into the inequality.
• Checking only one or some corner points instead of evaluating the objective function at every relevant corner point.
• Assuming that an unbounded feasible region has an optimum, or ignoring the possibility that an empty feasible region gives no feasible solution.

What Gets Asked

• Define a linear programming problem, decision variables, objective function, constraints, feasible region, feasible solution, and optimal solution.
• Formulate a two-variable problem by writing $Z=ax+by$, its constraints, and $x\ge 0,y\ge 0$.
• Graph inequalities such as $ax+by\le c$ or $ax+by\ge c$, including the correct solid boundary and half-plane.
• Identify the feasible region as the intersection of all constraints and the first-quadrant restrictions.
• Determine the corner points of a bounded feasible region.
• Evaluate the objective function at each corner point to find a maximum or minimum.
• Explain why the corner point principle applies to a linear objective function over a polygonal feasible region.
• Determine whether a problem has no feasible solution when the feasible region is empty.
• Analyse whether an optimum exists when the feasible region is unbounded.
• Use an iso-profit or iso-cost line $ax+by=k$ to interpret fixed objective-function values.
• Recognise multiple optimal solutions when adjacent corner points give the same optimum value.
• Interpret the final answer in context, including units and any required whole-number restrictions.