1
$\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$
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*} $$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.