MATP6640/ISYE6770 Linear Programming, Homework 2.

Due: 11.59pm on Friday, February 4, 2022 on LMS.

10% penalty for each day late.

- 1.
- Prove that if (D) has a nondegenerate optimal solution then (P) has a unique optimal solution for the
primal-dual pair
where c ∈ ℝ

^{n}, b ∈ ℝ^{m}, and A ∈ ℝ^{m×n}. - 2.
- Let A be an m × n matrix and let b be a vector in ℝ
^{m}. We consider the problem of minimizing ||Ax - b||_{∞}:= max_{i=1,…,m}{|(Ax - b)_{i}|} over all x ∈ ℝ^{n}. Let v be the value of the optimal cost.- (a)
- Let y ∈ ℝ
^{m}satisfy ∑_{i=1}^{m}|y_{i}|≤ 1 and A^{T}y = 0. Show that b^{T}y ≤ v without using Question 3. - (b)
- Reformulate the problem as a linear program and show that an optimal solution exists.

- 3.
- In the setting of Question 2, use LP duality to show that the optimal value of the following problem is
v:
- 4.
- Define the Lagrangian
Show that

if and only if x

^{*}and y^{*}are optimal solutions to the primal-dual pair from Question 1. - 5.
- Consider the linear programming problem
Show that this problem has unbounded objective function value by using the revised simplex algorithm starting from the basic feasible solution x = [0,2,1,1,0]

^{T}. Use the eta factorization of the inverse, so you should first factorize the initial basis B as LB = U, where L is lower triangular and U is upper triangular. On subsequent iterations, update the basis matrix by using eta matrices. What is the ray that you find? (Hint: you should find the ray on the second iteration.) - 6.
- The dual to the linear program in Question 5 is infeasible. Taking nonnegative linear combinations of the dual constraints gives further valid dual constraints. Show how the ray you found for the linear programming problem in Question 5 can be used to construct a linear combination of the dual constraints that is clearly infeasible.
- 7.
- Use AMPL or another linear programming package to solve the standard form linear programming
problem
(See the course webpage for more information on AMPL. The software is available on LMS.)

John Mitchell |

Amos Eaton 325 |

x6915. |

mitchj at rpi dot edu |

Office hours: Thursday 11am–1pm., on webex https://rensselaer.webex.com/meet/mitchj |