Optimal Solutions

Linear programming (LP) is a powerful mathematical technique used to find the best possible outcome — such as maximum profit or minimum cost — given a set of constraints expressed as linear inequalities. The 'best possible outcome' is called the optimal solution, and identifying it is the central goal of any linear programming problem (LPP). In real-world applications, businesses use LP to allocate resources, governments use it to plan logistics, and engineers use it to design efficient systems. The feasible region of an LPP is the set of all points (x, y) that satisfy every constraint simultaneously. This region forms a convex polygon when drawn on a coordinate plane. A fundamental theorem in linear programming states that if an optimal solution exists, it must occur at one of the corner points (vertices) of the feasible region. This theorem — known as the Corner Point Theorem or Extreme Point Theorem — reduces the problem of searching an infinite region to evaluating just a few specific points. Optimal solutions come in two flavors: a maximum value of the objective function (useful when maximizing profit, revenue, or output) and a minimum value (useful when minimizing cost, waste, or time). In some special cases, an LPP may have infinitely many optimal solutions along an edge of the feasible region, or it may be unbounded and have no finite optimal value. Understanding how to identify, verify, and interpret optimal solutions is an essential skill in mathematical modeling.

Key takeaways

Define Variables and the Objective Function
Write and Graph the Constraints
Identify the Feasible Region
Find All Corner Points (Vertices)
Evaluate the Objective Function at Each Vertex
Interpret and Verify the Result

Define Variables and the Objective Function

Assign decision variables (typically x and y) to the quantities you can control. Write the objective function Z = ax + by, where a and b are constants representing the value (profit, cost, etc.) associated with each unit of x and y. Clearly state whether you want to maximize or minimize Z.

Write and Graph the Constraints

Translate each real-world restriction into a linear inequality, for example 2x + 3y ≤ 12. Add non-negativity constraints x ≥ 0 and y ≥ 0, since negative quantities rarely make sense in applied problems. Graph each boundary line and shade the appropriate half-plane for each inequality.

Identify the Feasible Region

The feasible region is the intersection of all shaded half-planes — the area where every constraint is satisfied at once. Check that the region is bounded (finite polygon) or unbounded (extends to infinity in some direction). A bounded feasible region always produces both a maximum and a minimum; an unbounded region may produce only one or neither.

Find All Corner Points (Vertices)

Locate every vertex of the feasible region by solving pairs of boundary equations simultaneously. For example, if two boundary lines are x + y = 6 and 2x + y = 10, solve the system: subtract to get x = 4, then y = 2, giving vertex (4, 2). Always check that each candidate vertex actually satisfies all constraints before accepting it.

Evaluate the Objective Function at Each Vertex

Substitute each corner point into Z = ax + by and compute the value. Create a table of corner points and their corresponding Z values for clarity. The corner point that gives the largest Z value is the maximum optimal solution; the one giving the smallest Z value is the minimum optimal solution.

Interpret and Verify the Result

State the optimal solution in context: 'The maximum profit of $Z is achieved by producing x units of product A and y* units of product B.' If two adjacent vertices yield the same optimal Z value, every point on the edge between them is also optimal (infinitely many solutions). If the feasible region is empty (no point satisfies all constraints), the problem is infeasible.

The Key Equation

Z^* = \max_{(x,y) \in \mathcal{F}} \{cx + dy\} \quad \text{subject to} \quad A\mathbf{x} \leq \mathbf{b},\ x \geq 0,\ y \geq 0

Z^* — Optimal Value (units of objective (e.g., dollars)): The best attainable value of the objective function within the feasible region.
c,\ d — Objective Coefficients (rate (e.g., profit per unit)): Constants that weight each decision variable in the objective function.
\mathcal{F} — Feasible Region (dimensionless (set of points)): The convex polygon formed by all points satisfying every constraint simultaneously.
A\mathbf{x} \leq \mathbf{b} — Constraint System (problem-specific units): The matrix representation of all linear inequality constraints.

Worked Example

Problem. A factory produces two products, chairs (x) and tables (y). Each chair earns $40 profit and each table earns$ 50 profit. The constraints are: wood available: 2x + 4y ≤ 80; labor available: 3x + 2y ≤ 60; non-negativity: x ≥ 0, y ≥ 0. Find the production plan that maximizes profit Z = 40x + 50y.

Z^* = 40(10) + 50(15) = \$1150 \text{ at } (x,y) = (10,15)

Answer. The factory should produce 10 chairs and 15 tables to achieve the maximum profit of $1150.

Figure

Diagram

Origins · 1 minGeorge Dantzig and how this was discovered

George Dantzig

1914–2005 · American

George Dantzig invented the Simplex Method in 1947, which is the most widely used algorithm for solving linear programming problems. His method systematically moves along the edges of the feasible region from vertex to vertex, improving the objective function at each step until the optimal vertex is found. This breakthrough revolutionized operations research, economics, and industrial planning. As a graduate student at UC Berkeley, Dantzig arrived late to a statistics class and copied down two unsolved problems from the board, mistaking them for homework. He solved both problems within days — and they turned out to be famous open problems in statistics that had stumped researchers for years!

Feasible Region in Linear Programming — The feasible region is the domain over which optimal solutions are searched; understanding it is a prerequisite for finding optimal vertices.
Corner Point Theorem — This theorem guarantees that optimal solutions occur at vertices of the feasible region, forming the theoretical foundation for the evaluation method used in this concept.
Objective Function — The objective function is what is being optimized (maximized or minimized), making it inseparable from the concept of optimal solutions.
Systems of Linear Equations — Solving systems of two linear equations is the algebraic technique used to compute the coordinates of each vertex of the feasible region.
Graphical Method for LPP — The graphical method provides the visual framework — drawing constraints and shading half-planes — that makes identifying vertices and optimal solutions possible.