<s>[INST] Dual of a Linear Program \begin{align}
\min_{x} c^Tx \\
s.t.~Ax=b
\end{align}
Note that here $x$ is unrestricted. I need to prove that the dual of this program is given by
\begin{align}
\max_{\lambda} \lambda^Tb \\
s.t.~\lambda^TA\leq c^T
\end{align}
But in the constraint, I always get an equality (using what I learnt)
\begin{align}
\max_{\lambda} \lambda^Tb \\
s.t.~\lambda^TA = c^T
\end{align}
Please give some explanation also. 
 [/INST] \begin{align}
\min_{x} c^Tx \\
s.t.~Ax=b \\
Unrestricted 
\end{align}
Take $x=x_1-x_2$
\begin{align}
\min c^T(x_1-x_2) \\
s.t.~A(x_1-x_2)=b \\
~ x_1, x_2 \ge 0
\end{align}
This is can be written as
\begin{align}
\min {\begin {pmatrix}c \\ -c \\ \end  {pmatrix} }^T  \begin {pmatrix} x_1 \\ x_2 \\ \end  {pmatrix} \\
s.t.~\begin {pmatrix} A, & -A  \end  {pmatrix} \begin {pmatrix} x_1 \\ x_2 \\ \end  {pmatrix}=b \\
~ x_1, x_2 \ge 0
\end{align}
Now,  this is in the standard form of the linear program. Therefore, the dual can be written as
\begin{align}
\max b^T y \\
s.t.~ \begin {pmatrix}c \\ -c \\ \end  {pmatrix}  - 
\begin {pmatrix} A^T\\ -A^T \\ \end  {pmatrix}  y \ge 0\\ 
~ y \ge 0
\end{align}
This can be simplify as
\begin{align}
\max b^T y \\
s.t.~ c-A^T y \ge 0\\ 
~ -c+A^T y \ge 0\\ 
~ y \ge 0
\end{align}
\begin{align}
\max b^T y \\
s.t.~ A^T y \le c\\ 
~ A^T y \ge c\\ 
~ y \ge 0
\end{align}
This is equivalent to 
\begin{align}
\max b^T y \\
s.t.~ A^T y = c\\ 
~ y \ge 0
\end{align}
</s>