 Solution

Associate a nonnegative Lagrange multiplier ${\lambda }_i$ with each inequality. The Lagrangian dual problem begins withIts infimum over $x\in {\mathbb{R}}^n$ is finite exactly when $A^T\lambda +c=0$, in which case it equals $-b^T\lambda$. The dual linear program is consequentlyFor any primal-feasible $x$ and dual-feasible $\lambda$,which proves weak duality. Strong duality means equality of the two optimal values. The stated strict feasibility is the Slater condition; together with finiteness of the primal optimum it gives strong duality and an attained dual optimum ${\lambda }^{\ast }$.