The GATE Grind

GATE 2025 MA – Question 25

Linear Programming · Models and Solution Methods · 1 mark · Multiple select

S1={x≥0:2x₁+x₂≤4,x₁+2x₂≤5}; S2={x≥0:2x₁−x₂≤5,x₁+2x₂≤5}. Which statements hold?

  1. max(x₁+x₂) on S2 is 3
  2. max(x₁+x₂) on S2∖S1 is 5
  3. max(x₁+x₂) on S1∩S2 is 3
  4. max(x₁+x₂) on S1∪S2 is 4

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) max(x₁+x₂) on S1∩S2 is 3; (D) max(x₁+x₂) on S1∪S2 is 4

Explanation

S1⊂S2 because 2x₁−x₂≤2x₁+x₂≤4<5. S1 vertices (0,0),(2,0),(1,2),(0,2.5) give maximum sum 3 at (1,2). S2 vertices (0,0),(2.5,0),(3,1),(0,2.5) give maximum 4 at (3,1), which is outside S1. Therefore intersection maximum is 3 and union maximum 4. **C,D**.

More Models and Solution Methods questions

All Models and Solution Methods questions →