# How can I derive the following dual problem?

Standard form of the linear program is $$\text{Min} \, C^{T} x$$ $$s.t. Ax=b$$ $$x\ge 0$$

Dual is $$\text{Max}\, b^Ty$$ $$s.t. C-A^{T}y \ge 0$$

By using the above definition, I want to find the dual of the following linear problem and convert it into the standard form.

$$\text{Min} \, - {\left[\begin{array}{r} b \\ -b \\ 0 \end{array}\right]}^{T} {\left[\begin{array}{r} y_1 \\ y_2 \\ S \end{array}\right]}$$ $$s.t. (A^T, -A^T , I) {\left[\begin{array}{r} y_1 \\ y_2 \\ S \end{array}\right]}=C$$ $$y_1, y_2,S \ge 0$$

How can I do this?

Using your definition of the dual, the primal problem can be transformed to

\begin{align} & \max Z = C^T u \\ & \text{s.t. } -{\left[\begin{array}{r} b \\ -b \\ 0\end{array}\right]} - {\left[\begin{array}{r} A \\ -A \\ I \end{array}\right]} u \ge 0. \end{align}

Simplify this to

\begin{align} \max Z = C^T u & \\ \text{s.t. } Au &\le -b \\ Au &\ge -b \\ u &\le 0. \end{align}

\begin{align} \max Z = C^T u & \\ \text{s.t. } Au &= -b \\ u &\le 0. \end{align}

\begin{align} \max Z = C^T (-u) & \\ \text{s.t. } A(-u) &= -b \\ u &\ge 0. \end{align}

Finally, we get

\begin{align} \min Z = C^T u & \\ \text{s.t. } Au &= b \\ u &\ge 0. \end{align}

• Thank you very much! I hope this is correct!!!! – Oily Jan 9 '16 at 6:34