Definition / feasibility domain

A solution to a linear problem is said to be achievable if all the constraints are satisfied. The feasibility domain contains all the feasible solutions to the problem. The optimal solution is the « best » of the feasible solutions.

Feasible solution

To see if a solution is feasible, just test if all constraints are satisfied, it can be done manually or in matrix form.

Manually :

Let us check if the solution (3, 1) is feasible.

The first equation gives 3 * 1/3 + 1 = 2, the constraint is satisfied.
The second inequality gives -2 * 3 + 5 * 1 = -1 ≤ 7, the constraint is satisfied.
The third inequality gives 3 + 1 = 4 ≤ 4, the constraint is satisfied, we say that it is saturated.
Both type constraints are satisfied.

The solution is in the feasibility domain. The value of the objective function is z=3-1=2.

With the matrix: multiply the matrix of the linear program by the solution vector and compare the result to the members to the right of the linear program

Feasibility domain

For example the equationPar exemple l’équation ai*x1 + bi*x2 = ci divides the plane into two half-planes P1 and P2 of equation:

The lower or equal constraint will determine a half plane, the greater or equal constraint will determine the other half plane. To know in which half-plane lies the feasible solutions for the constraints, it suffices to test a simple example and to determine if it is feasible or not.

For example for the constraint: x1 + x2 ≤ 4, the solution (0,0) is reachable, so the origin is in the faisible half-plane.

The intersection of all the achievable half-planes constitutes the feasibility domain. The latter can be bounded or unbounded.