Linear Programming Methods Questions and Answers

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.

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.

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\).

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.

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.

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.

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.

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\).

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.

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.