Your Answer : (Not Answered)

Correct Answer : D

The new optimal basis is \(x_{2}\) and \(x_{4}\).

With \(b = (4, 20)\), the current basis gives \(B^{-1}b\):

\[ \begin{aligned} x_{3} &= 4 - \tfrac{1}{4}(20) = -1 \\ x_{2} &= \tfrac{1}{4}(20) = 5 \end{aligned} \]

\(x_{3}\) is negative, so apply the dual simplex method with \(x_{3}\) leaving. In its row only the \(x_{4}\) entry, \(-1/4\), is negative, so \(x_{4}\) enters. Pivoting gives \(x_{4} = 4\) and \(x_{2} = 5 - \frac{1}{4}(4) = 4\), and the new \(z_{j} - c_{j}\) row is \((24, 0, 24, 0)\), all non-negative.

Check: \(x_{2} = 4\) satisfies the first constraint, and \(4(4) + 4 = 20\) the second, with \(z = 48 - 24 = 24\). Options keeping \(x_{3}\) are wrong because it became negative, and \(x_{1}\) never enters: its reduced cost becomes 24.

Your Answer : (Not Answered)

Correct Answer : B

The optimal dual values are 12 and 0.

The starting basis was \(x_{3}\) (first constraint) and \(x_{4}\) (second constraint), with costs \(c_{3} = 12\) and \(c_{4} = -6\). In the optimal table, the \(z_{j} - c_{j}\) entry of a starting basic column equals the dual value of its constraint minus that column's cost:

\[ \begin{aligned} x_{3}: \ y_{1} - 12 &= 0 \Rightarrow y_{1} = 12 \\ x_{4}: \ y_{2} - (-6) &= 6 \Rightarrow y_{2} = 0 \end{aligned} \]

Equivalently, \(y = c_{B}B^{-1}\) with \(c_{B} = (12, 12)\) and \(B^{-1} = \begin{pmatrix} 1 & -1/4 \\ 0 & 1/4 \end{pmatrix}\), read from the \(x_{3}, x_{4}\) columns, gives \((12, 0)\). Check by duality: \(4y_{1} + 8y_{2} = 48 = z\). The other pairs also give \(4y_{1} + 8y_{2} = 48\), but each violates the dual constraint \(y_{1} \ge 12\) that comes from the \(x_{3}\) column, so none is dual feasible.

Your Answer : (Not Answered)

Correct Answer : B

S2 is TRUE and S1 is FALSE.

S1: \(f(x_{1}, x_{2}) = (x_{1} - x_{2})^{2}\). Then \(f^{-1}(\{0\})\) is the whole line \(x_{1} = x_{2}\), which is unbounded, so the preimage of the compact set {0} is not compact.

S2: g is a positive definite quadratic form, since its matrix \(\begin{bmatrix} 2 & -1/2 \\ -1/2 & 2 \end{bmatrix}\) has eigenvalues 1.5 and 2.5. Hence \(g(x) \ge 1.5\|x\|^{2}\), so the preimage of a bounded set is bounded; it is also closed because g is continuous. Closed and bounded in \(\mathbb{R}^{2}\) means compact, so S2 holds.

Your Answer : (Not Answered)

Correct Answer : B

The maximum is \((a/3)^{3/2}\).

Use Lagrange multipliers with \(g = xy + yz + zx - a\): \(\nabla(xyz) = \lambda\nabla g\) gives

\[ \begin{aligned} yz &= \lambda(y + z) \\ zx &= \lambda(z + x) \\ xy &= \lambda(x + y) \end{aligned} \]

For positive variables these force \(x = y = z\). The constraint then gives \(3x^{2} = a\), so \(x = \sqrt{a/3}\) and

\[ xyz = \left(\sqrt{a/3}\right)^{3} = (a/3)^{3/2}. \]

The same bound follows from AM-GM: \(\frac{a}{3} = \frac{xy + yz + zx}{3} \ge (xyz)^{2/3}\). \(a^{3/2}\) drops the factor 3, \((3/a)^{3/2}\) inverts it, and \((3a/2)^{3/2}\) exceeds the AM-GM bound.

Your Answer : (Not Answered)

Correct Answer : B

The optimal solution lies at a corner point of the feasible region.

The fundamental theorem of linear programming says that if a linear objective has an optimum over a bounded (or suitably unbounded) convex feasible region, it occurs at a corner point (vertex). That is why the corner-point method evaluates the objective only at the vertices.

The centre of the region is never singled out; the origin or a point on the \(x\)-axis is optimal only when it happens to be a vertex; and the objective function being zero has nothing to do with optimality.

Your Answer : (Not Answered)

Correct Answer : B

S2 is TRUE and S1 is FALSE.

S1: with \(\alpha = 2\), \(\beta = 1\), setting \(x_{3} = x_{4} = 0\) gives \(2x_{1} + x_{2} = 4\) and \(x_{1} + x_{2} = 8\), so \(x_{1} = -4\). The basic solution is infeasible, so \((x_{1}, x_{2})\) cannot be an optimal basis.

S2: with \(\alpha = 1\), \(\beta = 4\), setting \(x_{1} = x_{4} = 0\) gives \(4x_{2} = 8\), so \(x_{2} = 2\) and \(x_{3} = 2\): feasible. With \(c_{B} = (4, 4)\) the simplex multipliers are \(y = (4, 0)\), and the reduced costs of the non-basic variables are

\[ \begin{aligned} x_{1}: &\ 2 - (4 \cdot 1 + 0 \cdot 1) = -2 \\ x_{4}: &\ -3 - (4 \cdot 0 + 0 \cdot 1) = -3 \end{aligned} \]

Both are negative, so no entering variable can increase Z; the basis is optimal with Z = 16.

Your Answer : (Not Answered)

Correct Answer : D

The optimal value is 2.

The feasible region is bounded by \(2x_{1} + x_{2} \le 2\), \(x_{1} + x_{2} \ge 1\) and the axes. Its corners are \((0, 1)\), \((0, 2)\), \((1, 0)\).

\[ \begin{aligned} (0, 1) &: 5(0) + 2(1) = 2 \\ (0, 2) &: 4 \\ (1, 0) &: 5 \end{aligned} \]

The minimum is 2 at \((0, 1)\). 4 and 5 are the values at the other corners, and 0 would need \((0, 0)\), which violates \(x_{1} + x_{2} \ge 1\).

Your Answer : (Not Answered)

Correct Answer : D

The answer is \(\alpha \geq 7\).

The primal is a maximisation with one 'at most' constraint and one equality, so its dual is: minimise \(10y_{1} + 8y_{2}\) with \(y_{1} \geq 0\), \(y_{2}\) free, and one 'at least' constraint per primal variable, from the columns of the coefficients:

\[ \begin{aligned} y_{1} + 2y_{2} &\geq 5 \\ 2y_{1} - y_{2} &\geq 12 \\ y_{1} + 3y_{2} &\geq 0 \end{aligned} \]

\[ \begin{aligned} y_{2} = -1: \ \alpha - 2 &\geq 5 \Rightarrow \alpha \geq 7 \\ 2\alpha + 1 &\geq 12 \Rightarrow \alpha \geq 5.5 \\ \alpha - 3 &\geq 0 \Rightarrow \alpha \geq 3 \end{aligned} \]

All three must hold, and the strictest is \(\alpha \geq 7\). The ranges starting at 3 or 5.5 satisfy only the weaker constraints, and \(\alpha \lt 3\) fails all three.

Your Answer : (Not Answered)

Correct Answer : D

\((3, 0)\) is the only optimal solution exactly when \(\alpha \gt 2\).

The feasible region has corners \((0, 0)\), \((3, 0)\), \((2, 2)\) (where \(2x_{1} + x_{2} = 6\) meets \(x_{1} + x_{2} = 4\)), \((1.5, 2.5)\) (where \(x_{1} + x_{2} = 4\) meets \(-x_{1} + x_{2} = 1\)) and \((0, 1)\). The objective at each:

\[ \begin{aligned} (3, 0) &: 3\alpha \\ (2, 2) &: 2\alpha + 2 \\ (1.5, 2.5) &: 1.5\alpha + 2.5 \\ (0, 1) &: 1, \quad (0, 0) : 0 \end{aligned} \]

\((3, 0)\) must beat its neighbour \((2, 2)\) strictly: \(3\alpha \gt 2\alpha + 2\), so \(\alpha \gt 2\). Then it also beats the rest. At \(\alpha = 2\) the whole edge from \((3, 0)\) to \((2, 2)\) is optimal, so the optimum is not unique.

For \(1 \lt \alpha \lt 2\) the optimum moves to \((2, 2)\); for \(-2 \lt \alpha \lt 1\) it is at \((1.5, 2.5)\) or \((0, 1)\); and for \(\alpha \lt -2\) the point \((3, 0)\) gives a negative value, far from optimal.

Your Answer : (Not Answered)

Correct Answer : D

The FALSE statement is Even if both primal and dual are feasible, the optimal values of the primal and the dual can differ.

By the strong duality theorem, if both the primal and the dual are feasible, both have optimal solutions and their optimal objective values are equal. So the values cannot differ.

The other three are true. An equality constraint in the primal gives a dual variable unrestricted in sign. Both problems can be infeasible at once; standard small examples exist. And by weak duality, an unbounded primal leaves no feasible point for the dual, since any dual feasible value would bound the primal.

Your Answer : (Not Answered)

Correct Answer : D

The true statement is A linear programming problem can have a non-basic optimal solution.

When an LP has two optimal basic feasible solutions, every point on the segment joining them is also optimal, because the objective is linear. The interior points of that segment are optimal but not basic.

The others are false. A convex set can have infinitely many extreme points: every point of a circle is an extreme point of a closed disc. The feasible region of an LP is a polyhedron, which has only finitely many extreme points, since each is fixed by a choice of basis. And if an LP has two different optimal solutions, it has infinitely many (the whole segment between them), so it can never have exactly two.

Your Answer : (Not Answered)

Correct Answer : D

The point is a non-basic feasible solution.

It is feasible: all values are non-negative, and \(8 + 9 - 0 - 2 = 15\), \(24 + 3 + 0 - 6 = 21\), \(32 + 6 + 0 - 8 = 30\).

A feasible solution is basic only if the columns of its positive variables are linearly independent. Here \(x_{1}, x_{2}, x_{4}\) are positive, and their columns give

\[ \det\begin{bmatrix} 2 & 3 & -1 \\ 6 & 1 & -3 \\ 8 & 2 & -4 \end{bmatrix} = 4 - 0 - 4 = 0, \]

so the three columns are dependent and the solution is not basic. That rules out both basic options (degenerate and non-degenerate). It is not optimal either: it gives \(z = 4 + 6 + 0 - 8 = 2\), while the basic feasible solution \(x_{1} = 3, x_{2} = 3, x_{3} = x_{4} = 0\) satisfies all three constraints and gives \(z = 9\).