Introduction to Linear Programming

In a general linear-programming problem, we wish to optimize a linear function, subject to a set of linear inequalities. We are given an $m \times n$ matrix A, an m-vector $\vec{b}$, and an n-vector $\vec{c}$. We wish to find a vector $\vec{x}$ of nelements that maximizes the objective function: $\sum_{i=1}^{n}c_{i}x_{i}$ subject to the m constraints given by A $\vec{x} \geq \vec{b}$, and $\forall i,\ x_i \geq 0$.
This problem can be written formally as a linear-program of the following structure (also called the primal linear program):
Minimize: $\vec{c}^{T}\vec{x}$
Subject To: $A\vec{x} \geq \vec{b}$ and $\vec{x} \geq \vec{0}$
Many problems can be expressed as linear programs, and for this reason much work has gone into algorithms for linear programming. Today we know some polynomial algorithms that can be used to solve this problem, and there are many software packages can solve it.
Each minimization problem can easily be transformed to a dual maximization problem of the form:
Maximize: $\vec{b}^{T}\vec{y}$
Subject To: $A^{T}\vec{y} \leq \vec{c}$ and $\vec{y} \geq \vec{0}$

Theorem 6.7 (no proof)   $\vec{c}^{T}\widehat{\vec{x}}=\vec{b}^{T}\widehat{\vec{y}}$, where $\widehat{\vec{x}}$ and $\widehat{\vec{y}}$ are the solutions of a minimization problem and its dual maximization problem.

The above theorem suggests that we can either solve the primal or the dual linear program.