Name: |
Midterm Exam, Tuesday, March 27, 2018.
Solutions
Please do all three problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts, except where stated. You may use one sheet of handwritten notes. The exam lasts 110 minutes.
Q1 | /45 | |
Q2 | /20 | |
Q3 | /35 | |
Total | /100 |
Solution:
Hence, the optimal solution is x = (0, 2), with recourse variables y = (3, 0).
We can use the two equalities to set π_{2} = 1 and then express π_{1} = (2 - 11π_{3}). The two inequalities then become:
Thus, the set of dual optimal solutions is the line segment:
System 1: Ax < 0, Bx = 0 for some x ∈ ℝ^{n}.
System 2: A^{T }u + B^{T }v = 0 for some u ∈ ℝ^{p}, v ∈ ℝ^{q}, with u ≥ 0 and u≠0.
Solution:
Let e denote the vector of ones. Consider the primal-dual pair of LPs:
Let n = 4. Assume the cost c_{t} of a tour is given by the sum of the edge lengths in the tour, and the edge lengths are as follows:
city | 0 | 1 | 2 | 3 | 4 |
0 | – | 4 | 7 | 9 | 4 |
1 | 4 | – | 4 | 6 | 8 |
2 | 7 | 4 | – | 7 | 5 |
3 | 9 | 6 | 7 | – | 7 |
4 | 4 | 8 | 5 | 7 | – |
No tour is allowed to visit more than three cities (plus the base city). A tour can visit just one city and the base city. So, for example, valid tours include 0 - 4 - 0 with cost 8 and 0 - 1 - 2 - 3 - 0 with cost 24.
Solution:
subset t | ∑ _{i∈t}y_{i} | c_{t} | (a^{t})^{T }yc_{t} |
1 | 4 | 8 | < |
2 | 8 | 14 | < |
3 | 12 | 18 | < |
4 | 5 | 8 | < |
1,2 | 12 | 15 | < |
1,3 | 16 | 19 | < |
1,4 | 9 | 16 | < |
2,3 | 20 | 23 | < |
2,4 | 13 | 16 | < |
3,4 | 17 | 20 | < |
1,2,3 | 24 | 24 | = |
1,2,4 | 17 | 17 | = |
1,3,4 | 21 | 21 | = |
2,3,4 | 25 | 25 | = |
The solution to this system is x_{123} = x_{124} = x_{134} = x_{234} = , with all other x_{t} equal to zero. We have primal feasibility, dual feasibility and complementary slackness, so we have optimality.
Check objective function values:
So primal and dual objective function values agree.