Feasible solutions
Feasible Solutions
A feasible solution is a decision vector that satisfies every constraint of the problem.
It does not need to be optimal.
It only needs to be allowed.
Basic Definition
For a problem with feasible set $S$, a point $x$ is feasible if:
\[x\in S\]A point is infeasible if:
\[x\notin S\]LP Feasibility
For an LP written as:
\[Ax\le b,\qquad x\ge 0\]a vector $x$ is feasible if:
\[Ax\le b\]and:
\[x\ge 0\]Both conditions must hold.
Standard Form Feasibility
For a standard-form LP:
\[Ax=b\] \[x\ge 0\]a vector $x$ is feasible if:
- it satisfies the equation $Ax=b$
- every component is nonnegative
Example
Consider:
\[x_1+2x_2\le 10\] \[2x_1+x_2\le 16\] \[-x_1+x_2\le 3\] \[x_1,x_2\ge 0\]Check:
\[x=(2,3)\]First constraint:
\[2+2(3)=8\le 10\]Second constraint:
\[2(2)+3=7\le 16\]Third constraint:
\[-2+3=1\le 3\]Nonnegativity:
\[2\ge 0,\qquad 3\ge 0\]So $(2,3)$ is feasible.
Infeasible Example
For the same constraints, check:
\[x=(5,4)\]First constraint:
\[5+2(4)=13>10\]So $(5,4)$ is infeasible.
We do not need to check further once one constraint is violated.
Feasible Set
The feasible set is the set of all feasible solutions.
For:
\[Ax\le b,\qquad x\ge 0\]the feasible set is:
\[S=\{x\in\mathbb{R}^n\mid Ax\le b,\ x\ge 0\}\]Feasible Region
In two-variable LP problems, the feasible set is often called the feasible region.
It is found by:
- drawing each boundary line
- selecting the correct half-plane for each inequality
- intersecting all allowed regions
- applying nonnegativity constraints
Boundary Points
A feasible point may lie on the boundary of a constraint.
Example:
\[x_1+2x_2=10\]means the constraint:
\[x_1+2x_2\le 10\]is exactly active.
Boundary points are important because optimal LP solutions often occur at vertices, where several constraints are active.
Interior Points
A feasible point is an interior point if all inequality constraints are satisfied strictly.
Example:
\[x_1+2x_2<10\]means the point is not on that constraint boundary.
Interior feasible points are allowed, but they are usually not optimal in linear programming unless the objective is constant over a region.
Feasible Does Not Mean Optimal
A feasible solution only satisfies the constraints.
An optimal solution is a feasible solution with the best objective value.
Example:
If the objective is:
\[\max x_1+x_2\]then both:
\[(2,3)\]and:
\[(6,2)\]may be feasible, but:
\[6+2=8\]is better than:
\[2+3=5\]So feasibility is only the first check.
Candidate Solutions
When solving graphically, candidate optimal solutions are usually vertices of the feasible region.
When solving algebraically, candidate solutions include basic feasible solutions.
Empty Feasible Set
If no point satisfies all constraints, then:
\[S=\emptyset\]The LP is infeasible.
In that case, there is no feasible solution and therefore no optimal solution.
How to Check a Candidate Vector
Given a proposed vector $\bar{x}$:
- substitute it into every equality constraint
- substitute it into every inequality constraint
- check all sign restrictions
- if all constraints are satisfied, it is feasible
- if at least one constraint fails, it is infeasible
Key Takeaway
Feasibility is the permission test.
Before asking whether a solution is best, first ask whether it is allowed.
Exam checkpoint
For formulation questions, show variables, objective, constraints, sign restrictions, and units. Do not solve unless the question asks for a solution.