# Primal of Dual of LP problem

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?

## 1 Answer

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*}

Combiningn 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*}