Name: |

Midterm Exam, Friday, March 18, 2022.

Solutions

Please do all four 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 | /25 | |

Q2 | /25 | |

Q3 | /30 | |

Q4 | /20 | |

Total | /100 |

- (25 points) The linear program min{c
^{T }x : Ax = b,x ≥ 0} hasand the point x

^{*}= (3,2,0,1)^{T }is an optimal solution.- (5 points) Show x
^{*}is not a basic feasible solution. - (10 points) Find a nonzero direction d ∈ ℝ
^{4}satisfying Ad = 0 with d_{ j}= 0 if x_{j}^{*}= 0. - (10 points) What can you say about c
^{T }d? Justify your answer.

Solution:

- Row reduce the 3 columns of A used by x
^{*}:so the set of columns used by x

^{*}gives a submatrix of A of rank only 2. - We have
so we can take d = (2,-1, 0, 1)

^{T }. - We must have c
^{T }d = 0, since both x^{*}+ 2d and x^{*}- d are feasible, so if c^{T }d≠0 then one of these two feasible points would be better than x^{*}, contradicting the optimality of x^{*}.

- (5 points) Show x
- (25 points)
A primal LP is

The corresponding dual problem is

Find optimal solutions to the primal and dual problems.

Solution:

Variable f

_{1}has far smaller cost than f_{2}, so we try to make f_{1}as large as possible. Similarly, if we have a choice between f_{3}and f_{4}, we would pick f_{3}. This gives a primal feasible solution:with value

If we can find a dual feasible solution that satisfies complementary slackness then we have an optimal solution.

All the primal variables are positive, so we need all four dual constraints to hold at equality. The 2nd and 4th primal inequality constraints are strictly satisfied, so we need w

_{2}= w_{4}= 0. This implies we needSince we are primal and dual feasible and we satisfy complementary slackness, we are optimal.

Check: dual objective function value is

- (30 points; each part is worth 5 points) We have a primal-dual pair of linear programs
where the dual slack variables have been included explicitly. Assume both problems are feasible. We let e

_{j}∈ ℝ^{n}denote the jth unit vector. We also work with the related primal-dual pair of problems- Show that problem (Pj) is always feasible.
- Assume (Pj) has an unbounded optimal value. Show x
_{j}is unbounded in the feasible region of (P). - Assume (Pj) has a finite optimal value. What is that optimal value? Can x
_{j}be unbounded in the feasible region of (P)? Why or why not? - Assume (Dj) is feasible. Can s
_{j}be unbounded in the feasible region of (D)? Why or why not? - Assume (Dj) is infeasible. Can s
_{j}be unbounded in the feasible region of (D)? Why or why not? - Show exactly one of the following two statements is true:
- x
_{j}is unbounded in the feasible region of (P). - s
_{j}is unbounded in the feasible region of (D).

- x

Solution:

- Note that d = 0 is always feasible in (Pj).
- Since (Pj) has an unbounded optimal value, there must exist a ray ≥ 0 with
-e
_{j}^{T }< 0, A = 0. Let be feasible in (P). Then + α is feasible in (P) for all α ≥ 0, and we have ( + α )_{j}→∞ as α →∞. - (Pj) is a homogeneous problem, so the only possible finite optimal value is 0.
For x
_{j}to be unbounded in (P), there must exist a direction ≥ 0 with_{j}> 0, A = 0. But no such exists since (Pj) has optimal value 0. - Let , be feasible in (D) and let , be feasible in (Dj). Then y = + α ,
s = + α + αe
_{j}is feasible in (D) for any α ≥ 0. Note that s_{j}→∞ as α →∞. - For s
_{j}to be unbounded, we need to find a direction , with A^{T }+ = 0, ≥ 0,_{j}> 0. We can scale this direction so that_{j}≥ 1. Then , (- e_{j}) is feasible in (Dj). If (Dj) is infeasible then no such direction exists, so s_{j}must be bounded. - There are 2 possible cases for (Pj) since it is always feasible:
- (Pj) has unbounded optimal value, so (Dj) is infeasible, so in this case we
have x
_{j}is unbounded and s_{j}is bounded. - (Pj) has zero optimal value, so (Dj) is feasible, so in this case we have x
_{j}is bounded and s_{j}is unbounded.

- (Pj) has unbounded optimal value, so (Dj) is infeasible, so in this case we
have x

- (20 points) Consider the semi-infinite linear program
where we have a constraint for each w ∈ Q, and we define

Derive an equivalent linear program to (SILP) with the same variables y

_{1}, y_{2}and with a finite number of constraints.Solution:

We can sketch Q:

Any point in Q can be represented as a convex combination of the extreme points plus a nonnegative multiple of the ray:

with λ

_{1}+ λ_{2}+ λ_{3}= 1,λ_{j}≥ 0 for j = 1, 2, 3,μ ≥ 0.So (SILP) is equivalent to the LP with 4 constraints:

The feasible region for this LP is as follows:

Note that we have

So if y is feasible in (LP) then it is feasible in (SILP).

Conversely, if y is not feasible in (LP) then either w

^{T }y > 1 for one of the extreme points of Q, or y_{1}+ y_{2}< 0, which implies w^{T }y > 1 for w = -t(1, 1)^{T }∈ Q for large enough t. So y is not feasible in (SILP).Thus the two problems are equivalent.