✦ScienexySCIENCE KNOWLEDGE LIBRARY
reference · SCI-MAT-013-012

Feasible and Infeasible Regions

A feasible region is the set of all decision-variable combinations satisfying every constraint, while points outside it are infeasible.

  • S = {x ∈ ℝⁿ : Ax ≤ b, x ≥ 0}

  • Feasible point: x ∈ S

  • Infeasible point: x ∉ S

Explanation

In optimization, the feasible region is the geometric or mathematical representation of all allowable decisions. For two-variable problems, linear constraints often divide the coordinate plane into half-planes. The intersection of all required half-planes and equality conditions forms the feasible region. A point inside or on the boundary of this region is feasible, provided it satisfies all variable restrictions. A point outside the region violates at least one constraint. The feasible region may be bounded or unbounded, and it may be empty if the constraints are contradictory. In linear programming, an optimal solution, when a finite optimum exists, can be found at an extreme point of the feasible polyhedron under the standard linear-programming assumptions.

Variables

  • S: feasible region or feasible set

  • x: decision vector

  • A: constraint coefficient matrix

  • b: constraint-bound vector

  • ℝⁿ: n-dimensional real space

Example or application

For x + y ≤ 6, x ≥ 0, and y ≥ 0, the feasible region is a triangular area in the first quadrant, including its boundaries. A point such as (2, 3) is feasible, while (4, 4) is outside the region.

Definition

The feasible region is the set of all points satisfying every constraint of an optimization problem. The infeasible region consists of points that violate at least one required constraint.

Purpose

The purpose is to identify the complete set of allowable decisions and understand the geometric structure of an optimization problem.

Importance

Understanding the feasible region helps identify impossible decisions, detect contradictory constraints, and visualize how the available choices are restricted.

Learning Objectives

  • Define feasible and infeasible regions.

  • Interpret linear inequalities geometrically.

  • Identify the intersection of multiple constraints.

  • Distinguish bounded, unbounded, and empty feasible regions.

  • Test whether a point belongs to a feasible region.

Key Concepts

  • Feasible region

  • Infeasible region

  • Half-plane

  • Boundary

  • Bounded region

  • Unbounded region

  • Empty feasible set

Working Principle

Each constraint identifies a set of allowed points. The feasible region is obtained by intersecting all these sets. Any point that lies outside at least one required set is infeasible.

Process

  • Write the complete set of constraints.

  • Graph each inequality when the problem has two variables.

  • Identify the side of each boundary satisfying the inequality.

  • Find the intersection of all allowed regions.

  • Check whether the intersection is empty, bounded, or unbounded.

  • Test candidate points directly in the original constraints.

Applications

  • Visual analysis of linear programming problems

  • Production planning

  • Budget and resource allocation

  • Engineering design limits

  • Scheduling and capacity planning

Worked Example

Consider x + y ≤ 6, x ≤ 4, x ≥ 0, and y ≥ 0. The first constraint permits points on or below the line x + y = 6. The second restricts x to values no greater than 4. The non-negativity conditions restrict the region to the first quadrant. The point (3, 2) is feasible because 3 + 2 = 5 ≤ 6 and 3 ≤ 4. The point (5, 2) is infeasible because it violates both x + y ≤ 6 and x ≤ 4.

Common Misconceptions

  • The feasible region includes boundary points when the inequalities are non-strict.

  • A feasible region is not always triangular or bounded.

  • An empty feasible region means no decision satisfies all constraints.

  • A point can satisfy one constraint and still be infeasible because it violates another.

Practice Questions

  • What is a feasible region?

  • Explain how two linear inequalities define a common feasible region.

  • Determine whether (2, 3) satisfies x + y ≤ 7, x ≥ 0, y ≥ 0.

  • What is an unbounded feasible region?

  • What does an empty feasible region indicate?

Key Takeaway

The feasible region is the complete set of decisions allowed by all constraints, and optimization must search within this region.

Prerequisites

  • Coordinate geometry

  • Linear inequalities

  • Constraints and Feasible Solutions

Reference

  • Taha, H. A. Operations Research: An Introduction.

  • Bertsimas, D., and Tsitsiklis, J. N. Introduction to Linear Optimization.

Related Topics

  • Constraints and Feasible Solutions

  • Optimal Solutions

  • Local and Global Optima

  • Maximization and Minimization Problems

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.

Suggest a correction or source · More in Optimization & Operations Research