# Where does the duality comes from in linear programing and can we get the optimal basis from it?

$$\begin{cases} \max & c^Tx\\ & Ax\le b\\ & x\ge 0 \end{cases}\Leftrightarrow \begin{cases} \min & y^Tb\\ & y^TA\ge c^T\\ & y^T\ge 0 \end{cases}$$

Then we come to the following formula

$$c^Tx\le y^TAx\le y^Tb$$

I don't know where this comes from. It allows to have:

$$c^Tx\le y^TAx\le \tilde y^TAx \le \alpha$$

It seems to be linked to dual linear program resolution which leads to:

$$y^T\ge x^TAy\ge \tilde x^TAy\alpha$$

From this we can obtain the value $\alpha$ of the optimum, still, can we have the optimal basis?

$$Ax \le b$$
Now pre-multiply $y^T$ on both sides.
$$c^T \le y^T A$$
Now post-multiply $x$ on both sides.