Feasible Region

In linear programming, the feasible region is the set of all points that simultaneously satisfy every constraint in the problem. Think of it as the 'allowed zone' — any solution you propose must live inside this region to be valid. When we have two decision variables (say x and y), we can draw the feasible region directly on the coordinate plane as a polygon or an unbounded area bounded by straight lines. Each constraint in a linear program is a linear inequality such as 2x + 3y ≤ 12 or x ≥ 0. When graphed, each inequality shades one side of a boundary line. The feasible region is the intersection of all these shaded half-planes. If the constraints are compatible (consistent), the intersection is non-empty and the problem has at least one feasible solution; if no point satisfies all constraints simultaneously, the region is empty and the problem is called infeasible. Understanding the feasible region is essential because the optimal solution to any linear program — the point that maximizes or minimizes the objective function — always occurs at a corner point (vertex) of the feasible region, provided the region is bounded. This powerful geometric fact, guaranteed by the Corner Point Theorem, means we only need to evaluate the objective function at a finite number of vertices rather than checking every point in the plane.

Key takeaways
  • Write constraints as inequalities
  • Graph each boundary line
  • Shade the correct half-plane for each constraint
  • Identify the intersection (feasible region)
  • Find the corner points (vertices)
  • Apply the Corner Point Theorem

Write constraints as inequalities

Identify every constraint, including any non-negativity restrictions (x ≥ 0, y ≥ 0). For example: 3x + 2y ≤ 18, x + 2y ≤ 10, x ≥ 0, y ≥ 0. These four inequalities will define our region.

Graph each boundary line

Replace the inequality sign with '=' to get the boundary line. For 3x + 2y ≤ 18, graph 3x + 2y = 18 by finding intercepts: x-intercept at (6, 0) and y-intercept at (0, 9). Draw this line. Use a solid line for ≤ or ≥ (the boundary is included) and a dashed line for strict inequalities < or >.

Shade the correct half-plane for each constraint

To decide which side to shade, test a convenient point — usually the origin (0, 0) if it is not on the line. For 3(0) + 2(0) = 0 ≤ 18: TRUE, so shade the side containing the origin (below-left of the line). Repeat for each constraint. The non-negativity constraints x ≥ 0 and y ≥ 0 restrict us to the first quadrant.

Identify the intersection (feasible region)

The feasible region is the area where ALL shaded half-planes overlap. Highlight or label this region clearly. If the overlapping area is a closed polygon, the region is bounded. If it extends infinitely in some direction, it is unbounded (this can still have an optimal solution depending on the objective).

Find the corner points (vertices)

Locate every vertex of the feasible region. Vertices occur where two boundary lines intersect. Solve each pair of boundary equations simultaneously using substitution or elimination. Always check that each vertex actually satisfies ALL constraints — boundary intersections outside the feasible region are not valid vertices.

Apply the Corner Point Theorem

Evaluate the objective function at each vertex. The largest value gives the maximum; the smallest gives the minimum. For a bounded feasible region, both a maximum and minimum always exist. The Corner Point Theorem states: if an optimal value exists, it occurs at one or more corner points of the feasible region.

The Key Equation

S={(x, y)∈R2∣aix+biy≤ci for all i=1,2,…,m}S = \{ (x,\, y) \in \mathbb{R}^2 \mid a_i x + b_i y \leq c_i \text{ for all } i = 1, 2, \ldots, m \}
  • S — Feasible Region (none): The complete set of all (x, y) pairs that satisfy every constraint; the 'allowed zone' for solutions.
  • a_i,\, b_i — Constraint coefficients (none): The numerical coefficients of the decision variables x and y in the i-th constraint.
  • c_i — Constraint bound (none): The right-hand side value (limit) of the i-th constraint inequality.
  • m — Number of constraints (none): The total count of linear inequality constraints defining the feasible region.

Worked Example

Problem. A school canteen sells sandwiches (x) and salads (y). The kitchen can prepare at most 30 items total: x + y ≤ 30. Ingredients allow at most 2x + y ≤ 40. Both quantities must be non-negative: x ≥ 0, y ≥ 0. Profit is P = 3x + 2y dollars. Find the feasible region's vertices and the maximum profit.

Pmax⁡=3(10)+2(20)=70 dollars at (x,y)=(10,20)P_{\max} = 3(10) + 2(20) = 70 \text{ dollars at } (x, y) = (10, 20)

Answer. Maximum profit is $70, achieved at the vertex (10, 20).

Figure
Diagram
x + y = 302x+y=40A(0,0)B(20,0)C(10,20)D(0,30)FeasibleRegionxy02030
Origins · 1 minGeorge Bernard Dantzig and how this was discovered
GB
George Bernard Dantzig
1914–2005 · American

George Dantzig invented the Simplex Method in 1947 while working for the U.S. Air Force. The Simplex Method is an algorithm for solving linear programming problems by systematically moving along the edges of the feasible region from one vertex to the next, improving the objective function at each step, until the optimal corner point is found. His work transformed operations research, economics, and logistics. As a graduate student at Berkeley in 1939, Dantzig arrived late to a statistics lecture and copied two problems from the blackboard, assuming they were homework. He solved both and handed them in — not realizing they were famous unsolved problems in statistics. His professor was astonished and helped him publish the solutions.

  • Objective Function — The objective function is what we optimize over the feasible region; understanding the feasible region is meaningless without knowing what function to maximize or minimize within it.
  • Corner Point Theorem — This theorem guarantees that the optimal value of the objective function occurs at a vertex of the feasible region, making vertex identification the key step in solving linear programs graphically.
  • Systems of Linear Inequalities — A feasible region is precisely the graphical solution set of a system of linear inequalities; mastery of graphing such systems is the prerequisite skill.
  • Linear Equations in Two Variables — Finding the vertices of the feasible region requires solving pairs of linear equations simultaneously, a foundational algebra skill.