2
$\begingroup$

Given that the following relation holds: $$\begin{align*} &\textbf{Primal problem} \\ &\max Z = c^Tx \\ &s.t. \\ &Ax \leq b \\ & x \geq 0\end{align*}$$ $\Longrightarrow$ $$\begin{align*} &\textbf{Dual problem} \\ &\min W = b^Ty \\ &s.t. \\ &A^Ty \geq c \\ & y \geq 0\end{align*}$$ Derive the primal problem corresponding to the dual problem below, using only the relation given above. $$\begin{align*} &\min W = b^Ty \\ &s.t. \\ &A^Ty \geq c \\ &y \text{ unrestricted}\end{align*}$$

I tried the following: Define $y^+ \geq 0$ and $y^-\geq 0$ such that $y = y^+ - y^-$ Then we have $$\begin{align*} &\min W = b^T(y^+ - y^-) = b^Ty^+ - b^T y^- \\ &s.t. \\ &A^T (y^+ - y^- ) = A^Ty^+ - A^Ty^-\geq c \\ &y^+ \geq 0, y^-\geq 0\end{align*}$$ Then we make it into a maximisation problem: $$\begin{align*} &\max W' = b^T(y^- - y^+) \\ &s.t. \\ &A^T(y^- - y^+)\leq c \\ &y^+ \geq 0, y^-\geq 0\end{align*}$$ Then define $u:= y^- - y^+$, so that we have $$\begin{align*} &\max W' = b^Tu \\ &s.t. \\ &A^Tu\leq c \\ &u \text{ unrestricted}\end{align*}$$ And then I am stuck, any hints on how to continue?

$\endgroup$

1 Answer 1

0
$\begingroup$

The question is asking how to convert the dual back into the primal. After the substitution of $y^+ - y^-$ for $y$, you have $$\begin{align*} \min W &= b^Ty^+ - b^T y^- & \\ {\rm s.t.} \hspace{1in} \\ A^Ty^+ - A^Ty^- & \geq c \\ y^+ & \geq 0 \\ y^- &\geq 0 \end{align*} $$

Moving back to the primal, you have one variable for each of the structural constraints, and separate constraints for each of the variables $$ \begin{align*} \max Z & = c x \\ {\rm s.t.} \hspace{1in} \\ A x & \le b \\ -A x & \le -b \\ x & \ge 0 \end{align*} $$

Combining the two sets of structural constraints and the problem becomes $$ \begin{align*} \max Z & = c x \\ {\rm s.t.} \hspace{1in} \\ A x & = b \\ x & \ge 0 \end{align*} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .