Past paper questions

Question 1

Without solving the LP of part (a), explain why there will be an optimal solution where no more than two of the variables will take positive value.

[2023, 3m]

Answer 1

There always exists a BASIC OPTIMAL SOLUTION, where the # of BASIC VARIABLES = # of EFFECTIVE CONSTRAINTS.

Since the problem only has 2 resource constraints, there are at most 2 effective constraints, and thus at most 2 variables with positive value.

Question 2

What other algorithm, instead of Dijkstra, would you suggest to find a shortest path efficiently?

[2022, 5m]

Answer 2

1. The network cannot contain a directed cycle (ie. it is ACYCLIC), therefore it has a TOPOLOGICAL ORDER
2. Can apply the critical path method to return a SHORTEST PATH
3. The CPA algorithm is able to determine a LONGEST PATH in an acyclic network with arbitrary arc lengths (positive or negative) &…
4. …finding a shortest path in the above network corresponds to finding a LONGEST PATH with “negative” distances

Question 3

MarkeIt! is interested in knowing how changing the target for Retired Men affects the total
cost. How much does a unit increase or decrease in the target affect the total cost? Compute
the range for which this estimate holds (i.e. compute the upper and lower range for the
target).

Answer 3

1. The dual constraint relative to the Retired Men target is 𝑦3, which takes value 13/9.
2. Therefore any unit increase or decrease in the right hand side will, respectively, increase or decrease the total cost by 13/9, as long as the change in right-hand side
   does not change the optimal dual solution.
3. The optimal dual solution does not change as long as the optimal primal solution is defined by constraints 1 and 3.
4. Thus the right-hand side can decrease until constraint 3 passes through the intersection of
   constraints 1 and 2, and increase until it passes through the intersection of constraint
   1 and of the constraint 𝑥1 ≥ 0.
   - find the points of intersection and substitute into the primal constraint 3

Question 4

The dual solution remains optimal as long as…?

Answer 4

• As long as the solution of the system…
  [the equations that we write to find the “dual” variables] remains FEASIBLE
• which is feasible as long as, eg. x1≥0

Question 5

1. What is an extreme point?
2. What is the importance of extreme points in linear programming?
   [3m]

Answer 5

1. Feasible & satisfies n linearly independent constraints
2. LP importance: if there is an optimal solution, there is always one that is an extreme point.