The linear programming problem: Maximise \(Z=x_{1}+\displaystyle\frac{5}{2}x_{2}\) subject to \(5x_{1}+3x_{2}\le 15\), \(-x_{1}+x_{2}\le 1\), \(2x_{1}+5x_{2}\le 10\), \(x_{1}, x_{2}\ge 0\), has
Answer & explanation
Correct answer: option 2
The correct answer is Option (2) → infinitely many optimal solutions
The feasible region is bounded (it lies inside \(2x_1+5x_2\le 10\) in the first quadrant), so Z has a maximum at a corner point. Its corners are found from the boundary lines.
On the \(x_1\)-axis, \(5x_1+3x_2 = 15\) gives \(x_1 = 3\) (smaller than the 5 from \(2x_1+5x_2 = 10\)), so (3, 0) is a corner. On the \(x_2\)-axis, \(-x_1+x_2 = 1\) gives \(x_2 = 1\), so (0, 1) is a corner.
Point P, where \(5x_1+3x_2 = 15\) meets \(2x_1+5x_2 = 10\):
\(25x_1+15x_2 = 75\)
\(6x_1+15x_2 = 30\)
\(19x_1 = 45\)
\( \displaystyle P = \left(\frac{45}{19}, \frac{20}{19}\right) \)
Point Q, where \(2x_1+5x_2 = 10\) meets \(-x_1+x_2 = 1\): putting \(x_2 = 1+x_1\),
\(2x_1+5+5x_1 = 10\)
\(7x_1 = 5\)
\( \displaystyle Q = \left(\frac{5}{7}, \frac{12}{7}\right) \)
P satisfies \(-x_1+x_2 \le 1\) and Q satisfies \(5x_1+3x_2 \le 15\), so the corners are (0, 0), (3, 0), P, Q and (0, 1). Values of Z:
\(Z(0, 0) = 0\)
\(Z(3, 0) = 3\)
\( \displaystyle Z(P) = \frac{45}{19}+\frac{5}{2}\times\frac{20}{19} = \frac{95}{19} = 5 \)
\( \displaystyle Z(Q) = \frac{5}{7}+\frac{5}{2}\times\frac{12}{7} = \frac{35}{7} = 5 \)
\( \displaystyle Z(0, 1) = \frac{5}{2} \)
The maximum 5 is reached at the two adjacent corners P and Q, so every point of the edge PQ is optimal: there are infinitely many optimal solutions.
This happens because \(Z = \frac{1}{2}(2x_1+5x_2)\): the objective line is parallel to the constraint \(2x_1+5x_2 \le 10\), and Z = 5 all along that edge.