Operations Research Questions and Answers

Answer: B

The problem has one solution.

The feasible region is the polygon with vertices (0, 0), (10, 0), (5, 5) and (0, 5), bounded by the axes, \(x_{1} + x_{2} \le 10\) and \(x_{2} \le 5\). A linear objective reaches its maximum at a vertex:

\[ \begin{aligned} z(0,0) &= 0, \quad z(10,0) = 10 \\ z(5,5) &= 0, \quad z(0,5) = -5 \end{aligned} \]

The maximum, z = 10, occurs only at (10, 0). Multiple optima would need the objective's contour lines to lie parallel to an edge through the best vertex; here the edges meeting at (10, 0) are \(x_{2} = 0\) and \(x_{1} + x_{2} = 10\), neither parallel to \(x_{1} - x_{2} = \text{constant}\). The region is bounded and non-empty, so a solution exists, ruling out 'no solution'.

Answer: B

The maximum profit is ₹4000 per day.

Let \(x\) and \(y\) be the daily output of P1 and P2. The linear programme is:

\[ \begin{aligned} \max\ Z &= 150x + 100y \\ 2x + 3y &\le 70 \quad (M1) \\ 2x + y &\le 50 \quad (M2) \\ 2y &\le 40 \quad (M3) \end{aligned} \]

The optimum lies at a corner of the feasible region. The M1 and M2 lines meet where \(2y = 20\), so \(y = 10\), \(x = 20\), which also satisfies M3. Evaluating the corners:

• (25, 0), limited by M2: \(Z = 3750\)
• (20, 10), M1 and M2: \(Z = 3000 + 1000 = 4000\)
• (5, 20), M1 and M3: \(Z = 750 + 2000 = 2750\)
• (0, 20): \(Z = 2000\)

The maximum is 4000 at 20 pieces of P1 and 10 of P2. 5000 and 6000 would need more material than is available (for example, 6000 needs 40 pieces of P1, using 80 units of M2 against 50), and 3000 is below an achievable corner.

Answer: B

The feasible region is Region Q.

Simplify the constraints: \(10X_{1} + 10X_{2} \ge 600\) is \(X_{1} + X_{2} \ge 60\), and \(25X_{1} + 5X_{2} \le 750\) is \(5X_{1} + X_{2} \le 150\). A feasible point must lie

• below the horizontal line \(X_{2} = 50\);
• on or above the gently sloping line \(X_{1} + X_{2} = 60\) (intercept 60 on each axis);
• on or left of the steep line \(5X_{1} + X_{2} = 150\) (intercept 30 on the \(X_{1}\) axis), which already keeps \(X_{1} \le 30 \lt 45\).

These meet in a small triangle with corners (10, 50), (20, 50) and (22.5, 37.5), the shaded Region Q.

Region P lies below \(X_{1} + X_{2} = 60\), so it breaks the \(\ge 600\) constraint. Region S lies to the right of the steep line, breaking \(25X_{1} + 5X_{2} \le 750\). Region R breaks both.

Answer: D

The problem has an unbounded solution.

The feasible region is not empty: (2, 1) satisfies \(2 - 1 \le 1\) and \(2 + 1 \ge 3\). But it is not bounded. Take \(x_{1} = 0\) and let \(x_{2}\) grow: \(0 - x_{2} \le 1\) and \(0 + x_{2} \ge 3\) hold for every \(x_{2} \ge 3\), while \(Z = 2x_{2}\) increases without limit. So Z has no finite maximum.

An LP is classified by what happens to its optimum. Feasible points exist, but 'feasible solution' does not describe the outcome; 'optimum solution' and 'feasible but not optimum' do not fit either, since there is no maximum to attain. The standard classification of this problem is unbounded.

Answer: C

S is a convex set.

S is the solid ellipse \(\dfrac{x_{1}^{2}}{2} + \dfrac{x_{2}^{2}}{3} \le 1\). The function \(g(x_{1}, x_{2}) = 3x_{1}^{2} + 2x_{2}^{2}\) is convex (a sum of convex quadratics), and a sublevel set \(\{g \le 6\}\) of a convex function is convex: if \(g(p) \le 6\) and \(g(q) \le 6\), then \(g(\lambda p + (1 - \lambda)q) \le \lambda g(p) + (1 - \lambda)g(q) \le 6\).

'Concave' and 'not concave' describe functions, not sets; the standard term for sets is convex. 'Not convex' is false, since every segment joining two points of an ellipse region stays inside it.

Answer: C

At least one extreme point gives an optimal solution.

This is the fundamental theorem of linear programming. When the feasible set of \(AX = B, X \ge 0\) is a convex polyhedron (bounded and non-empty), the linear objective is continuous on a compact set and so attains its optimum. Every point of a polytope is a convex combination of its extreme points, and a linear function on such a combination cannot exceed its largest value at those vertices, so an optimum is reached at an extreme point.

That is why the simplex method searches only basic feasible solutions. An unbounded solution cannot occur on a bounded polyhedron, an infeasible solution contradicts the set being non-empty, and 'bounded but not optimal' is not a property the theorem gives.

Answer: D

The optimal solution is (2/7, 9/7).

The feasible region has corners (0, 0), (1/2, 0) on \(6x_{1} + x_{2} = 3\), (0, 3/2) on \(3x_{1} + 4x_{2} = 6\), and the intersection of the two lines. From the second, \(x_{2} = 3 - 6x_{1}\); substituting, \(3x_{1} + 12 - 24x_{1} = 6\), so \(x_{1} = 2/7\) and \(x_{2} = 9/7\).

\[ \begin{aligned} Z(1/2, 0) &= 1, \quad Z(0, 3/2) = 1.5 \\ Z(2/7, 9/7) &= 4/7 + 9/7 = 13/7 \end{aligned} \]

The maximum, \(13/7 \approx 1.86\), is at (2/7, 9/7). The other points fail: (5/7, 5/7) violates \(6x_{1} + x_{2} \le 3\) (it gives 35/7), (3/11, 14/11) is feasible but gives only \(Z = 20/11 \approx 1.82\), and (1/3, 2/3) gives 4/3.

Answer: D

The conditions are \(4x_{1} = 2 - \lambda_{1} - \lambda_{2} + \mu_{1}\) and \(3 + \mu_{2} = 4\lambda_{1} + \lambda_{2}\).

Attach multipliers \(\lambda_{1}, \lambda_{2} \ge 0\) to the constraints \(x_{1} + 4x_{2} \le 4\) and \(x_{1} + x_{2} \le 2\), and \(\mu_{1}, \mu_{2} \ge 0\) to \(x_{1}, x_{2} \ge 0\). Stationarity of the Lagrangian for a maximum requires \(\nabla Z = \sum\lambda_{i}\nabla g_{i} - \mu\):

\[ \begin{aligned} 2 - 4x_{1} &= \lambda_{1} + \lambda_{2} - \mu_{1} \\ 3 &= 4\lambda_{1} + \lambda_{2} - \mu_{2} \end{aligned} \]

Rearranged, these are exactly option D. The other options attach the wrong coefficients: the objective has no \(x_{2}^{2}\) term, so no equation can contain \(x_{2}\) or \(4x_{2}\) (options A, B and C), and option C also has the wrong sign on the constant 2.