Exercise 4.16

Question

Give an example of a pair (primal and dual) of linear programming problems, both of which have multiple optimal solutions.

Igor · Accepted Answer

\begin{align*}
		\min \; & x_2  &  \max \; & p_2 \
		\mbox{s.t.}\; & -x_2 \geq 0 &  \mbox{s.t.}\; & p_2 \leq 0\
		& x_1 + x_2 \geq 1 & & -p_1 + p_2 \leq 1\
		& x_1 \geq 0 & & p_1 \geq 0\
		& x_2 \geq 0 & & p_2 \geq 0
	\end{align*}

Every $(a, 0)$ for $a \geq 1$ is an optimal feasible solution to the primal (with cost equal to $0$). Every $(b, 0)$ for $b \geq 0$ is an optimal feasible solution to the dual (with cost equal to $0$).

Subham Saha · Answer

Consider the primal problem
\begin{align}
	\min & 0^{T}x \
	\text{subject to} & Ax = 0\
			  & x \geq 0.
\end{align}

The dual problem is
\begin{align}
	\max & p^{T}0 \
	\text{subject to} & p^{T}A \leq 0.
\end{align}

Any feasible $x$ is optimal. If $x$ is feasible and optimal $\lambda x$ is also feasible and optimal for any $\lambda > 0$.
Similarly, any feasible $p$ is optimal, and if $p$ is feasible and optimal so is $\lambda p$ for any $\lambda > 0$.

Exercise 4.16

Answers

Comments

Comments

Exercise 4.16

Answers

Comments

Comments

Add answer