Linear Programming Formulation Questions and Answers

Answer: C

The true statement is if an optimal solution exists, at least one optimal solution lies at a corner of the feasible set.

This is the fundamental theorem of linear programming: if the feasible region has extreme points and the objective attains its optimum, it attains it at some extreme point (basic feasible solution). That is why the simplex method searches only the corners.

The others fail. An LP may be infeasible or unbounded, so not every LP has an optimum. The optimum need not occur 'only' at extreme points: with alternative optima, every point of an edge between two optimal corners is optimal (as in Q9). And a feasible solution is optimal only by coincidence.

Answer: B

The LP has no feasible solution.

The equality \(5x_{1} = 10\) fixes \(x_{1} = 2\). Then:

\[ \begin{aligned} 3(2) + 2x_{2} \le 12 &\Rightarrow x_{2} \le 3 \\ 2 + x_{2} \ge 8 &\Rightarrow x_{2} \ge 6 \end{aligned} \]

No \(x_{2}\) can be both at most 3 and at least 6, so the constraints are inconsistent. (The last constraint, \(x_{2} \ge 6\), agrees with the third but cannot help.) The objective, printed with the slip \(x_{2/2}\), plays no part: with an empty feasible region there is no feasible solution, degenerate or not.

Answer: B

The correct pair is option B: the primal with \(\le\) constraints and the dual minimise \(500y_1 + 150y_2 + 250y_3\) subject to \(2y_1 + y_2 \ge 8\) and \(y_1 + y_3 \ge 5\).

Let \(x_1, x_2\) be the type A and type B hats. Labour: an A hat takes twice a B hat and 500 B hats fill a day, so \(2x_1 + x_2 \le 500\). Market limits give \(x_1 \le 150\) and \(x_2 \le 250\). Profit is \(Z = 8x_1 + 5x_2\).

For a maximisation primal with \(\le\) constraints, the dual is a minimisation with one variable per constraint (\(y_1, y_2, y_3\)), objective coefficients from the right-hand sides (500, 150, 250), and \(\ge\) constraints, one per primal variable, with the profits 8 and 5 on the right: column of \(x_1\) gives \(2y_1 + y_2 \ge 8\), column of \(x_2\) gives \(y_1 + y_3 \ge 5\).

Option A has the dual inequalities the wrong way round. Option C swaps the roles of costs and right-hand sides and drops a dual variable, and the primal and dual of this problem are not the same.

Answer: C

The correct pair is the primal Maximize Z with the constraints written as less than or equal and the dual Minimize Z' with the constraints written as greater than or equal.

With \(x_1, x_2, x_3\) units of P1, P2, P3, profit is \(Z = 5x_1 + 6x_2 + 4x_3\), to be maximised subject to machine hours \(3x_1 + x_2 + 4x_3 \le 60\) and labour hours \(2x_1 + 3x_2 + 3x_3 \le 75\), with all \(x \ge 0\).

The dual of a maximisation problem with \(\le\) constraints is a minimisation problem with \(\ge\) constraints: the right-hand sides 60 and 75 become the objective coefficients, and each column of the primal becomes a dual constraint: \(3y_1 + 2y_2 \ge 5\), \(y_1 + 3y_2 \ge 6\), \(4y_1 + 3y_2 \ge 4\).

The first option wrongly maximises the dual, the second gives the dual constraints as \(\le\), and the last minimises the primal with \(\ge\) constraints, which turns the problem upside down.

Answer: C

The convex sets are (i) and (iii) only.

(i) The line \(y = x\) is convex: any segment between two of its points lies on it. (iii) The region above the parabola, \(y \ge x^{2}\), is the epigraph of the convex function \(x^{2}\), so it is convex.

(ii) is not convex. The points \((-1, 1)\) and \((1, 1)\) satisfy \(y \le |x|\), but their midpoint \((0, 1)\) does not, since \(1 \gt 0\). The region below the V-shaped graph of \(|x|\) has a notch at the origin. So every option containing (ii) is wrong, and '(i) only' leaves out (iii).

Answer: A

Both are true.

(I) The feasible region of an LP is the intersection of finitely many half-spaces \(a_{i}^{t}x \le b_{i}\) (and \(x \ge 0\)). Each half-space is convex and an intersection of convex sets is convex, so the feasible set is convex, a fact the simplex method relies on.

(II) A hyperplane \(\{x : a^{t}x = b\}\) is convex: if \(a^{t}x = a^{t}y = b\), then \(a^{t}(\lambda x + (1 - \lambda)y) = b\) for every \(\lambda \in [0, 1]\).

Since both statements hold, the options saying only one is true, or neither, are wrong.

Answer: A

The LP has an infeasible solution, that is, no feasible solution.

Divide the constraints by 2 and by 4:

\[ \begin{aligned} x_{1} + 2x_{2} &\le 2 \\ x_{1} + 2x_{2} &\ge 4 \end{aligned} \]

No point can make the same expression at most 2 and at least 4, so the feasible region is empty. Without a feasible point there is no basic feasible solution and no unbounded solution either, which rules out B, C and D.

Answer: C

Both \(S_{1}\) and \(S_{2}\) are true.

The feasible region has corners (0, 0), (2.5, 0), (0, 2) and the intersection of \(x + 5y = 10\) with \(x + y = 2.5\):

\[ \begin{aligned} 4y &= 7.5,\ y = 1.875,\ x = 0.625 \\ Z &= 3(0.625) + 5(1.875) = 11.25 \end{aligned} \]

The other corners give 0, 7.5 and 10, so the optimum 11.25 is attained only at (0.625, 1.875). The objective (3, 5) is not parallel to either constraint, (1, 5) or (2, 2), so no edge is optimal and \(S_{1}\) holds.

The optimal primal solution is non-degenerate (both variables positive, both constraints tight), so complementary slackness fixes the dual solution uniquely: \(u_{1} + 2u_{2} = 3\), \(5u_{1} + 2u_{2} = 5\), giving \(u_{1} = 0.5\), \(u_{2} = 1.25\) with value \(10(0.5) + 5(1.25) = 11.25\). So \(S_{2}\) holds too.

Answer: A

The objective is a dummy objective function with all zero coefficients, with the allocation in option A.

The 21 bottles are 7 full, 7 half-full and 7 empty, so the total drink is \(7 + 3.5 = 10.5\) bottles' worth and each person must get 7 bottles holding 3.5. Nothing is to be maximised or minimised; the problem only asks for a feasible integer solution, so the objective has zero coefficients and the constraints do the work.

Option A satisfies every constraint: person 1 gets 1 full, 5 half and 1 empty (7 bottles, 1 + 2.5 = 3.5); persons 2 and 3 each get 3 full, 1 half and 3 empty (7 bottles, 3 + 0.5 = 3.5); and the columns use exactly 7 of each kind.

The other allocations break the constraints: in B the full bottles total 6, in C person 1 gets no drink at all, and in D person 2 gets 5 full bottles.

Answer: A

The infeasible corner points are (x1 = 0, x2 = 6) and (x1 = 12, x2 = 0).

The basic solutions are the intersections of the constraint lines with the axes and with each other. The line \(x_1 + 3x_2 = 12\) meets the axes at (12, 0) and (0, 4); the line \(3x_1 + 2x_2 = 12\) meets them at (4, 0) and (0, 6).

\[ \begin{aligned} (0, 6)&: 0 + 3(6) = 18 \gt 12 \\ (12, 0)&: 3(12) + 0 = 36 \gt 12 \end{aligned} \]

Each violates the other constraint, so these two basic solutions are infeasible. The points in B and C are not intersections of these lines at all, and D is wrong because two corner points are infeasible.