# Converting generic linear problems into their dual

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements.

I have to convert the following generic linear program to their duals

$$(P1)=\begin{cases}\max & c^Tx\\ &Ax=b\\ &x\ge 0 \end{cases},(P2)=\begin{cases}\max & c^Tx\\ &Ax=b \end{cases}$$

$$(P3)=\begin{cases}\min & b^Tx\\ &Ax\le b\\ &x\ge 0 \end{cases},(P4)=\begin{cases}\min & c^Tx\\ &Ax\le b \end{cases}$$

I did:

$$(D1)=\begin{cases}\min & b^Ty\\ &A^{T}y\le c\\ &y\ge 0 \end{cases},(D2)=\begin{cases}\min & b^Ty\\ &A^{T}y=c \end{cases}$$

$$(D3)=\begin{cases}\max & c^Ty\\ &A^{T}y\le c\\ &y\ge 0 \end{cases},(D4)=\begin{cases}\max & b^Ty\\ &A^{T}y= c\\&y\le 0 \end{cases}$$

Yet, following the following array:

Should I do:

$$(D1)=\begin{cases}\min & b^Ty\\ &A^{-1}y\le c\\ \end{cases},(D2)=\begin{cases}\min & b^Ty\\ &A^{-1}y=c \end{cases}$$

$$(D3)=\begin{cases}\max & b^Ty\\ &A^{-1}y\le c\\ &y\le 0 \end{cases},(D4)=\begin{cases}\max & b^Ty\\ &A^{-1}y\le c \end{cases}$$

Which are yet to be transformed into their canonical form?

• For one thing, all the $A^{-1}$ should be $A^T$. – Théophile Apr 26 '16 at 13:24
• @Théophile isn't it the same? – IggyPass Apr 28 '16 at 8:27
• No, they are very different! $A^{-1}$ is the inverse while $A^T$ is the transpose. The inverse is a matrix such that $AA^{-1} = I$; note that in almost all linear programming problems, the inverse doesn't exist because it is only defined when $A$ is square. On the other hand, the transpose is the result of exchanging the rows and columns of the matrix. – Théophile Apr 28 '16 at 17:34
• @Théophile Yes, okay! Understood! I mixed things up because to know if a program is feasible we have to see if its matrix is invertible... – IggyPass Apr 28 '16 at 20:52
• Good work! (Are you sure about the objective function, though?) – Théophile Apr 29 '16 at 8:43

In all four cases, your $A^{-1}$ should be $A^T$. (Make sure you understand the difference!) Apart from that, $(D1)$ and $(D2)$ are fine.
For $(D3)$, since the primal is a minimization problem with the restriction $A \mathbf x \leq \mathbf b$ (as opposed to $A \mathbf x \geq \mathbf b$), then the dual should have its variables constrained by $\mathbf x \leq \mathbf 0$ (not $\mathbf x \geq \mathbf 0$). Also, the objective function should be $\mathbf b^T \mathbf y$, not $\mathbf c^T \mathbf y$.
Can you fix $(D4)$ yourself?