Linear Programming

The One Thing

Linear programming converts a practical optimization problem into decision variables, a linear objective function, constraints, and non-negativity restrictions. For two variables, the graphical method identifies the feasible region and evaluates the objective function at its corner points to obtain the maximum or minimum, when an optimum exists.

Definitions and Results

• Decision Variables: Unknown quantities whose values must be determined, usually represented by $x$ and $y$.
• Objective Function: A linear expression to be maximized or minimized, such as $Z=ax+by$. It may represent profit or output maximization, or cost or resource minimization.
• Constraints: Linear inequalities or equations representing limitations involving resources, demand, time, or other conditions.
• Non-negativity Restrictions: The conditions $x\ge 0$ and $y\ge 0$, because quantities such as products or hours cannot normally be negative.
• Linear Programming Problem: A problem consisting of an objective function, constraints, and non-negativity restrictions. Its standard structure is to optimize $Z=ax+by$, subject to linear constraints and $x\ge 0,y\ge 0$.
• Feasible Region: The common region containing all points that satisfy every constraint and the non-negativity conditions.
• Feasible Solution: Any point that satisfies all the constraints of the problem.
• Corner Point: A vertex or extreme point of the feasible region formed by intersections of boundary lines.
• Optimal Solution: A feasible solution that gives the greatest or least value of the objective function, as required.
• Bounded Feasible Region: A feasible region enclosed within a finite area, generally giving a finite maximum and minimum under suitable conditions.
• Unbounded Feasible Region: A feasible region that extends indefinitely; an optimum may or may not exist.
• Iso-profit or Iso-cost Line: A line obtained by assigning a fixed value to the objective function, such as $ax+by=k$.
• Redundant Constraint: A constraint that does not change the feasible region because it is already satisfied by the other constraints.
• Boundary of a Constraint: For $ax+by\le c$, the boundary line is $ax+by=c$. For $ax+by\ge c$, the boundary is the same line, but the opposite half-plane is selected.
• Corner-point Principle: If an optimum exists for a linear programming problem with a bounded feasible region, at least one optimum occurs at a corner point.
• Multiple Optimal Solutions: If the objective function has the same optimum value at two adjacent corner points, every point on the line segment joining them is also optimal.
• Infeasible Problem: If the feasible region is empty, the problem has no feasible solution.
• Unbounded Problem: If the objective value can increase or decrease indefinitely in the feasible region, the problem is unbounded in the relevant direction.

Worked Methods

Formulating a Linear Programming Problem

• Define the decision variables. For example, let $x$ and $y$ represent the quantities of two products, activities, or resources.
• Write the objective function to be maximized or minimized:

$$Z=ax+by.$$

• Translate each condition in the question into a linear constraint. Conditions involving resources, demand, time, or other limitations may produce linear inequalities or equations.
• Add the non-negativity restrictions:

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

• Check that all units are consistent and that the variable definitions correctly reflect the wording of the problem.
• Interpret the final solution in context. If variables represent whole items, non-integer values may require practical reconsideration unless fractional values are allowed.

Drawing the Constraints and Selecting Half-Planes

• For each inequality, draw its boundary line. For example:

$$ax+by\le c$$ has boundary $$ax+by=c.$$

• For $ax+by\le c$, select the half-plane satisfying the inequality. For $ax+by\ge c$, select the opposite side of the same boundary line.
• Identify the correct half-plane by testing a convenient point, usually $(0,0)$, provided that $(0,0)$ does not lie on the boundary line.
• Include the restrictions $x\ge 0$ and $y\ge 0$, which restrict the solution to the appropriate part of the coordinate plane.
• The intersection of all selected half-planes is the feasible region. It represents every possible choice satisfying all the constraints.

Finding Corner Points

• Identify the boundary lines that form the edges of the feasible region.
• Find each intersection point by solving the corresponding pair of boundary equations simultaneously.
• Include relevant intercepts on the axes, where appropriate.
• Verify every intersection point against every original constraint, not merely the two equations used to calculate it.
• Exclude any point that does not satisfy all constraints and the non-negativity restrictions.
• Determine whether the resulting feasible region is bounded or unbounded, and whether it is empty.

Graphical Optimization

• Draw all boundary lines.
• Shade the half-planes required by the inequalities.
• Identify the feasible region.
• Find all its corner points.
• Evaluate the objective function

$$Z=ax+by$$ at each corner point.

• For maximization, select the feasible point giving the greatest value of $Z$. For minimization, select the point giving the least value.
• Check the reported optimum against the original constraints.
• State the answer using the wording and units of the original problem.

Using Iso-profit or Iso-cost Lines

• Assign a fixed value $k$ to the objective function:

$$ax+by=k.$$

• Draw the resulting iso-profit or iso-cost line.
• Move the line parallel to itself in the direction of increasing or decreasing objective value.
• Identify the last point or edge that still intersects the feasible region.
• The contact point gives an optimum at a corner point; if the line coincides with an edge between two adjacent corner points, every point on that edge is optimal.

Where It Goes Wrong

• Defining the decision variables incorrectly can produce a mathematically valid but practically meaningless answer; the variables must match the quantities described in the problem.
• Reversing an inequality or shading the wrong half-plane gives an incorrect feasible region. The correct side should be checked using a test point, usually $(0,0)$, when that point is not on the boundary.
• Forgetting $x\ge 0$ and $y\ge 0$ permits negative quantities such as negative products or hours.
• Finding an intersection from two boundary equations is not sufficient; the point must also satisfy every original constraint.
• Checking only one or two corner points can miss the optimum. When an optimum exists, the objective function must be evaluated at all relevant corner points.
• Units must remain consistent, and a non-integer answer must be reconsidered when the variables represent whole items unless fractional values are allowed.

What Gets Asked

• Formulate a real-life situation by defining decision variables, writing an objective function, translating conditions into constraints, and adding non-negativity restrictions.
• Draw boundary lines such as $ax+by=c$, identify the correct half-planes, and construct the feasible region.
• Find intersection points by solving pairs of boundary equations simultaneously.
• Determine whether a feasible region is bounded, unbounded, or empty.
• Identify redundant constraints and explain why they do not alter the feasible region.
• Use the corner-point method to maximize or minimize $Z=ax+by$.
• Use iso-profit or iso-cost lines of the form $ax+by=k$ to locate an optimum.
• Recognize infeasibility, unboundedness, and multiple optimal solutions.
• Interpret the optimum in the context and units of resource-allocation, production-planning, diet, transportation, scheduling, profit, or cost problems involving two decision variables.