Your Answer : (Not Answered)

Correct Answer : A

The maximal flow is 70 units.

The two arcs leaving the source, S-1 (40) and S-2 (30), form a cut of capacity 70, so no flow can exceed 70. A flow of 70 can be achieved:

• S to 1: 40, sent on as 30 to node 3, 5 to node 4 and 5 to node 2.
• S to 2: 30, plus 5 from node 1, so 35 goes on to node 4.
• Node 4 receives 5 + 35 = 40: 30 goes to N and 10 to node 3 on the undirected arc 3-4 (capacity 25).
• Node 3 receives 30 + 10 = 40 and sends it to N (capacity 50).

The flow into N is 40 + 30 = 70, equal to the cut, so by the max-flow min-cut theorem it is maximal. 75 exceeds the cut; 60 and 65 stop short of a flow that is achievable.

Your Answer : (Not Answered)

Correct Answer : C

The probability that the counter is free is \(1 - \dfrac{1.5}{2.5}\).

Treat the counter as an M/M/1 (or M/G/1) queue. The arrival rate is \(\lambda = 2/5 = 0.4\) per minute and the mean service time is 1.5 minutes, so the traffic intensity is

\[ \rho = \lambda \times 1.5 = 0.6 = \frac{1.5}{2.5} \]

In the long run the server is busy a fraction \(\rho\) of the time, so it is free with probability \(1 - \rho = 0.4\). 2.5 minutes is the mean time between arrivals. \(1 - 1.5/5\) wrongly uses 5 minutes as the inter-arrival time, \(1 - 1.5/2\) uses the arrival count, and 0 would mean the counter is always busy.

Your Answer : (Not Answered)

Correct Answer : D

The true statement is that the simplex method approaches the solution by moving from corner to corner along the edges.

The simplex method starts at a vertex (basic feasible solution) of the feasible region and at each step moves along an edge to an adjacent vertex with a better objective value, stopping when no neighbouring vertex is better.

It is not guaranteed to solve every problem: it can only report infeasibility or unboundedness, and without anti-cycling rules it can cycle. Searching through the interior of the region is what Karmarkar's interior-point algorithm (1984) does, so the second and third statements have the two methods the wrong way round.

Your Answer : (Not Answered)

Correct Answer : C

The statement that is not true is constraints are assumed to be non-homogeneous.

Karmarkar's projective algorithm works with a problem in a special canonical form: minimise \(c'x\) subject to homogeneous constraints \(Ax = 0\), \(\sum x_{j} = 1\), \(x \ge 0\). The centre of the simplex, \(x = (1/n, \ldots, 1/n)\), is assumed to satisfy \(Ax = 0\), and the algorithm starts from this interior point, moving through the interior rather than along the edges.

So (A) and (B) describe it, and, being a polynomial-time interior point method, it typically needs far fewer iterations on large problems (D). Non-homogeneous constraints are not part of its assumptions.

Your Answer : (Not Answered)

Correct Answer : C

The statement that is not true is that linear programming problems cannot be solved using dynamic programming.

Linear programmes can be solved by dynamic programming: each variable is treated as a stage and the remaining resources as the state, and the recursion works through the variables one at a time. It is usually less efficient than the simplex method, but it is possible, and textbooks include such examples.

The other statements are the defining features of dynamic programming: the problem is split into stages (A), each stage has a number of states (B), and the optimal solution is built from optimal solutions of sub-problems, Bellman's principle of optimality (D).

Your Answer : (Not Answered)

Correct Answer : C

The value is f₃(15) = 75, option C.

The printed recurrence leaves out the transition between stages. I read it as \(b_{k-1} = b_k - x\), which is what makes the printed line \(f_1(b_1) = (b_2 - x)^{2}\) consistent: it is \(f_1\) evaluated at \(b_1 = b_2 - x\), that is \(f_1(b) = b^{2}\). This is the problem of minimising \(x_1^{2} + x_2^{2} + x_3^{2}\) subject to \(x_1 + x_2 + x_3 = 15\).

\[ \begin{aligned} f_1(b) &= b^{2} \\ f_2(b) &= \min_x \{x^{2} + (b-x)^{2}\} = \frac{b^{2}}{2} \quad (x = b/2) \\ f_3(b) &= \min_x \{x^{2} + \tfrac{(b-x)^{2}}{2}\} = \frac{b^{2}}{3} \quad (x = b/3) \end{aligned} \]

Hence \(f_3(15) = 225/3 = 75\): each of the three variables equals 5, and \(3 \times 25 = 75\). Option A (25) is one term only, and 112.5 is \(15^{2}/2\), the two-stage value \(f_2(15)\).

Your Answer : (Not Answered)

Correct Answer : B

The minimum value is \(2c\).

For non-negative \(y_{1}, y_{2}\),

\[ \begin{aligned} &y_{1}^{2} + y_{2}^{2} - 2y_{1}y_{2} \\ &= (y_{1} - y_{2})^{2} \ge 0 \end{aligned} \]

so \(y_{1}^{2} + y_{2}^{2} \ge 2y_{1}y_{2} = 2c\), with equality when \(y_{1} = y_{2} = \sqrt{c}\). (Dynamic programming gives the same: with \(y_{2} = c/y_{1}\), minimise \(y_{1}^{2} + c^{2}/y_{1}^{2}\), which is least at \(y_{1}^{2} = c\).) The options in \(c^{2}\) have the wrong dimension: if \(y\) is doubled, \(c\) quadruples and the minimum must quadruple too.

Your Answer : (Not Answered)

Correct Answer : D

The current stock level is 600.

In this model Q is the stock at the start, \(u\) the rate of usage per unit time and \(t\) the time elapsed, so the stock remaining is

\[ S = Q - ut = 1000 - 40 \times 10 = 600 \]

400 is the quantity used, not the stock left; 1000 ignores the usage, and 1200 adds the usage instead of subtracting it.

Your Answer : (Not Answered)

Correct Answer : C

A stock-out occurs when \(t = Q/u\).

In \(S = Q - ut\), the stock starts at Q and is used at the constant rate \(u\). It runs out when \(S = 0\):

\[ Q - ut = 0 \Rightarrow t = \frac{Q}{u} \]

At \(t = 0\) the stock is full, \(u/Q\) inverts the ratio (it is the fraction of the order used per unit time), and \(Q = S\) holds only at \(t = 0\).

Your Answer : (Not Answered)

Correct Answer : C

The statement that is not a dual constraint is \(3w_{1} + w_{2} \ge 6\).

For a minimisation primal with \(\ge\) constraints and non-negative variables, the dual is to maximise \(3w_{1} + 5w_{2}\) subject to one \(\le\) constraint per primal variable:

• \(x_{1}\): \(w_{1} \le 4\)
• \(x_{2}\): \(3w_{1} + w_{2} \le 6\)
• \(x_{3}\): \(2w_{2} \le 18\), i.e. \(w_{2} \le 9\)
• \(w_{1}, w_{2} \ge 0\)

The constraint for \(x_{2}\) is \(3w_{1} + w_{2} \le 6\); option C has the inequality reversed, so it is not a constraint of the dual. The others are.

Your Answer : (Not Answered)

Correct Answer : B

The optimal assignment is U \(\to\) II, V \(\to\) IV, W \(\to\) III, X \(\to\) I, at a total cost of 16.

Hungarian method. Subtract each row minimum (5, 3, 2, 5):

U: 5, 0, 8, 10; V: 0, 6, 15, 0; W: 8, 5, 1, 0; X: 0, 6, 4, 2.

Column minima are 0, 0, 1, 0; subtracting 1 from column III gives U: 5, 0, 7, 10; V: 0, 6, 14, 0; W: 8, 5, 0, 0; X: 0, 6, 3, 2. A full set of independent zeros is U-II, V-IV, W-III, X-I, so this assignment is optimal, with cost \(5 + 3 + 3 + 5 = 16\) (the total reduction \(15 + 1\)).

The other options cost far more: U-II, V-III, W-I, X-IV costs \(5 + 18 + 10 + 7 = 40\); U-III, V-IV, W-II, X-I costs \(13 + 3 + 7 + 5 = 28\); U-IV, V-II, W-III, X-I costs \(15 + 9 + 3 + 5 = 32\).

Your Answer : (Not Answered)

Correct 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.

Your Answer : (Not Answered)

Correct 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.

Your Answer : (Not Answered)

Correct Answer : C

Such a payoff is called both a saddle point and an equilibrium point.

In a two-person zero-sum game with a pure-strategy solution, the payoff at the intersection of the optimal row and column is the minimum of its row and the maximum of its column. Maximin equals minimax there, neither player gains by deviating, and so each player always selects the same pure strategy.

Game theory texts call this payoff the saddle point (after the shape of the payoff surface) and also the equilibrium point (because neither player has an incentive to move). Since both names are standard, choosing only one of them is incomplete, and 'none of the above' is wrong.

Your Answer : (Not Answered)

Correct 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.

Your Answer : (Not Answered)

Correct 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.

Your Answer : (Not Answered)

Correct 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.

Your Answer : (Not Answered)

Correct Answer : A

The correct dual is the one with constraints \(0.1k_{1} + 0.1k_{3} + 0.2k_{4} \le 0.07\) and \(0.1k_{2} + 0.2k_{3} + 0.1k_{4} \le 0.05\).

For a minimisation primal with \(\ge\) constraints and non-negative variables, the dual maximises \(b^{T}k\) subject to \(A^{T}k \le c\), \(k \ge 0\). The objective uses the right-hand sides 0.4, 0.6, 2.0, 1.8, which all options share.

Each dual constraint comes from one primal variable's column. Column \(x_{1}\) has coefficients 0.1, 0, 0.1, 0.2 and cost 0.07; column \(x_{2}\) has 0, 0.1, 0.2, 0.1 and cost 0.05. That gives exactly the keyed pair.

The second option puts \(k_{2}\) in the \(x_{1}\) constraint in place of \(k_{3}\). The third and fourth swap the right-hand sides 0.07 and 0.05 between the columns.

Your Answer : (Not Answered)

Correct Answer : C

The shadow price is zero.

A shadow price is the increase in the optimal objective value from one more unit of a resource. If some of the resource is already left over at the optimum, an extra unit would only add to the slack and could not improve the objective. This is complementary slackness: a constraint with positive slack has a zero dual value.

A positive (or, for minimisation, negative) shadow price is possible only for a binding resource, one that is fully used. An infinite shadow price has no meaning for a resource that is not even fully used.

Your Answer : (Not Answered)

Correct Answer : A

The entering variable is \(x_{11}\) and the leaving variable is \(x_{24}\): \(x_{11}\) and \(x_{24}\).

Find \(u_{i}, v_{j}\) from \(u_{i} + v_{j} = c_{ij}\) on the basic cells, with \(u_{1} = 0\): \(v_{2} = 4\), \(u_{2} = -1\), \(v_{3} = 8\), \(v_{4} = 7\), \(u_{3} = -3\), \(v_{1} = 6\).

Reduced costs \(c_{ij} - u_{i} - v_{j}\) on the non-basic cells:

\[ \begin{aligned} x_{11} &: 3 - 0 - 6 = -3 \\ x_{33} &: 3 + 3 - 8 = -2 \\ x_{13}, x_{14} &: 0 \\ x_{21} &: 2,\quad x_{32}: 8 \end{aligned} \]

The most negative is \(x_{11}\), so it enters. Its loop is \(x_{11}(+), x_{12}(-), x_{22}(+), x_{24}(-), x_{34}(+), x_{31}(-)\). The minus cells hold 60, 20 and 40, so \(\theta = 20\) and \(x_{24}\) leaves.

The options entering \(x_{13}\) or \(x_{14}\) are wrong because those cells have zero reduced cost and would not lower the cost, and \(x_{33}\), at -2, is less negative than \(x_{11}\), at -3.