Exercise 4.11

Question

Consider a linear programming problem in standard form which is infeasible, but which becomes feasible and has finite optimal cost when the last equality constraint is omitted. Show that the dual of the original (infeasible) problem is feasible and the optimal cost is infinite.

Neeraj · Accepted Answer

Consider the LP in standard form:
$$
\text{(P)} \quad \min\ c^T x \quad \text{s.t.} \quad Ax = b,\ x \geq 0,
$$
where (P) is infeasible, but becomes feasible with finite optimal cost when the last constraint $a_m^T x = b_m$ is removed, yielding:
$$
\text{(P')} \quad \min\ c^T x \quad \text{s.t.} \quad \tilde{A}x = \tilde{b},\ x \geq 0.
$$

The dual of (P) is:
$$
\text{(D)} \quad \max\ b^T y \quad \text{s.t.} \quad A^T y \leq c.
$$

Since (P') is feasible and bounded, its dual:
$$
\text{(D')} \quad \max\ \tilde{b}^T y \quad \text{s.t.} \quad \tilde{A}^T y \leq c,
$$
is feasible and bounded. Any feasible $y'$ for (D') can be extended to $y = \begin{bmatrix} y' \ 0 \end{bmatrix}$, which is feasible for (D), proving that (D) is feasible.

By weak duality, since (P) is infeasible and (D) is feasible, (D) must be unbounded. Hence, the \textbf{dual is feasible with infinite optimal cost}.

Exercise 4.11

Answers

Comments

Exercise 4.11

Answers

Comments

Add answer