Feasible and Infeasible Solutions
1.0What is a Feasible Solution?
A feasible solution in linear programming is any point or solution that meets all of the problem's requirements, including those that say the numbers can't be negative. A feasible solution does not go against any of the rules set by the system of inequalities that define the problem.
- Formal Definition: If a point ((x, y)) satisfies all the constraints of a linear programming problem, it is called a feasible solution.
- Properties:
- Within the feasible region, all possible solutions can be found.
- The optimal solution (the highest or lowest value of the objective function) is always a solution that works.
2.0What is an Infeasible Solution?
An infeasible solution is a solution or point that doesn't meet one or more of the linear programming problem's constraints. These kinds of solutions are not used to make the objective function better.
- Formal Definition: If a point ((x, y)) does not satisfy at least one constraint, it is termed an infeasible solution.
- Properties:
- Infeasible solutions lie outside the feasible region.
- They cannot be candidates for the optimal solution.
3.0Feasible and Infeasible Regions
The feasible region is the set of all points that meet all of the constraints. It is usually shown as a convex polygon or polyhedron on a graph. The infeasible region is the area outside of this feasible region where at least one constraint is broken.
- Feasible Region: The intersection of all half-planes (from inequalities) that satisfy the constraints.
- Infeasible Region: Any region outside the feasible region does not fulfil all constraints.
Visualization (for two variables X and Y):
- Feasible region: A space that is either limited or unlimited, where all the constraints meet.
- Infeasible region: The part of the coordinate plane that is not in the feasible region.
4.0What is the Difference Between a Feasible and Infeasible Extreme Point?
Extreme Points, which are also called vertices or corner points, are the points where the lines that make up the feasible region meet. The main differences are:
- Feasible Extreme Point:
An extreme point that lies inside the feasible region and satisfies all constraints. These are the only candidates for optimal solutions in linear programming. - Infeasible Extreme Point:
An extreme point that lies outside the feasible region, violating at least one constraint. These points have no role in finding the optimal value.
5.0Solved Examples on Feasible and Infeasible Solutions
Example 1: Identifying Feasible and Infeasible Solutions
Problem: For the system of inequalities:
(x+y≤5)(x≥0)(y≥0)
Determine if the points A(2, 2) and B(3, 4) are feasible solutions.
Solution:
- ForA(2,2):(2+2=4≤5)(2≥0),(2≥0) = All conditions are satisfied.
A(2,2) is a feasible solution. - ForB(3,4):(3+4=7≤5)(3≥0),(4≥0) = The first condition is not satisfied.
B(3,4) is an infeasible solution.
Example 2: Feasible and Infeasible Extreme Points
Problem: Consider the constraints:
(x+2y≤8)(x≥0)(y≥0)(x+y≤6)
Is the point (6,0) a feasible or infeasible extreme point?
Solution:
- (6+2∗0=6≤8)
- (6≥0)
- (0≥0)
- (6+0=6≤6) = All constraints are satisfied.
(6,0) is a feasible extreme point.
Example 3: Feasible and Infeasible Regions
Problem:
Given (x+y≤4), (x≥1), (y≥2), plot the feasible region and check if (2,3) and (0,3) are feasible.
Solution:
- For (2,3): (2+3=5≤4) = Not Feasible
- For (0,3):(0+3=3≤4) (0≥1) = (Not feasible)
- The feasible region is where all three inequalities overlap, typically a triangular or quadrilateral region in the first quadrant.
Both (2,3) and (0,3) are infeasible solutions.
Example 4: Feasibility in Optimization
Problem: Maximize ( Z = 3x + 2y ), subject to:
(x+y≤5)(x≥0)(y≥0)
Find all feasible extreme points and determine the optimal value.
Solution:
Find intersection points (vertices):
- (0,0): All constraints satisfied.
- (5,0): (5+0=5≤5),(5≥0),(0≥0)
- (0,5): (0+5=5≤5),(0≥0),(5≥0)
Calculate Z:
- At (0,0): ( Z = 0 )
- At (5,0): ( Z = 15 )
- At (0,5): ( Z = 10 )
The maximum value is ( Z=15 ) at (5,0), which is a feasible extreme point.
6.0Practice Questions on Feasible and Infeasible Solutions
- Check whether the point (2, 3) is a feasible solution for the system of inequalities: x+y≤6,x≥0,y≥0
- Determine if the point (4, 5) is feasible or infeasible for the constraints:2x+y≤10,x≥1,y≥2
- For the linear programming problem: x+2y≤8,2x+y≤10,x≥0,y≥0. Check whether the point (3, 2) is feasible.
- Consider the system of constraints: x+y≥12,x≥0,y≥0. Is the point (5, 6) feasible?
- For the inequalities: 3x+2y≤18,x+y≤10,x≥0,y≥0. Check whether the point (4, 4) is feasible or infeasible.
- A company produces two products, PP and QQ. The constraints are:P+Q≤40,P+2Q≤50,P,Q≥0. Test if (10, 15) is a feasible solution.
- Find whether the point (7, 0) is feasible for the region defined by: x+y≤5,x≥0,y≥0