We need to find the number of feasible corner points and check if the optimal solution is degenerate for the given Linear Programming Problem (LPP):
Maximize: z=2x1+3x2
Subject to:
c1:x1+2x2≤60
c2:2x1+x2≤30
c3:x1−x2≥−10(or −x1+x2≤10)
c4:x1≥0
c5:x2≥0
**Step 1: Identify all potential corner points by finding intersections of boundary lines.**
The boundary lines are:
- x1+2x2=60
- 2x1+x2=30
- x1−x2=−10
- x1=0
- x2=0
Let's find the intersection points and check their feasibility:
* **P1: Intersection of x1=0 and x2=0**
Point: (0,0)
Feasibility Check: 0+2(0)≤60 (True), 2(0)+0≤30 (True), 0−0≥−10 (True).
Result: Feasible.
* **P2: Intersection of x2=0 and 2x1+x2=30**
Substituting x2=0 into 2x1+x2=30⟹2x1=30⟹x1=15.
Point: (15,0)
Feasibility Check: 15+2(0)≤60 (True), 2(15)+0≤30 (True), 15−0≥−10 (True).
Result: Feasible.
* **P3: Intersection of x1=0 and x1−x2=−10**
Substituting x1=0 into x1−x2=−10⟹−x2=−10⟹x2=10.
Point: (0,10)
Feasibility Check: 0+2(10)≤60 (True), 2(0)+10≤30 (True), 0−10≥−10 (True).
Result: Feasible.
* **P4: Intersection of 2x1+x2=30 and x1−x2=−10**
Adding the two equations: (2x1+x2)+(x1−x2)=30−10⟹3x1=20⟹x1=20/3.
Substitute x1=20/3 into 2x1+x2=30⟹2(20/3)+x2=30⟹40/3+x2=90/3⟹x2=50/3.
Point: (20/3,50/3)
Feasibility Check: x1≥0,x2≥0 (True). 20/3+2(50/3)=120/3=40≤60 (True). 2(20/3)+50/3=90/3=30≤30 (True). 20/3−50/3=−30/3=−10≥−10 (True).
Result: Feasible.
* **Intersection of x1+2x2=60 and 2x1+x2=30**
Multiply the second equation by 2: 4x1+2x2=60.
Subtract the first equation (x1+2x2=60) from this: (4x1+2x2)−(x1+2x2)=60−60⟹3x1=0⟹x1=0.
Substitute x1=0 into 2x1+x2=30⟹x2=30.
Point: (0,30)
Feasibility Check: 0−30=−30≥−10.
Result: Not Feasible.
* **Intersection of x1+2x2=60 and x1−x2=−10**
From x1−x2=−10⟹x1=x2−10.
Substitute into x1+2x2=60⟹(x2−10)+2x2=60⟹3x2=70⟹x2=70/3.
Then x1=70/3−10=40/3.
Point: (40/3,70/3)
Feasibility Check: 2(40/3)+70/3=80/3+70/3=150/3=50≤30.
Result: Not Feasible.
We have found 4 feasible corner points: (0,0), (15,0), (0,10), and (20/3,50/3).
**Step 2: Determine if the optimal solution is degenerate.**
An optimal solution is degenerate if, at that corner point, more constraints than the number of variables are binding (active as equalities). Here, we have n=2 variables (x1,x2). A corner point is degenerate if more than 2 constraints are binding.
Let's check the binding constraints for each feasible corner point:
* **P1 (0,0):** Constraints x1=0 and x2=0 are binding. (2 constraints = n).
* **P2 (15,0):** Constraints x2=0 and 2x1+x2=30 are binding. (2 constraints = n).
* **P3 (0,10):** Constraints x1=0 and x1−x2=−10 are binding. (2 constraints = n).
* **P4 (20/3,50/3):** Constraints 2x1+x2=30 and x1−x2=−10 are binding. (2 constraints = n).
Since exactly two constraints (equal to the number of variables) are binding at each feasible corner point, none of the feasible corner points are degenerate. This implies the optimal solution, which must occur at one of these non-degenerate corner points, is also not degenerate. (The objective function value at P4 is z=2(20/3)+3(50/3)=40/3+150/3=190/3, which is the optimal value.)
Thus, there are 4 feasible corner point solutions, and the optimal solution is not degenerate.