[tomas789]

It is called duality. For each linear program that is maximizing, you can find a dual linear program wich is minimization. They both have the same optimal objective value. Thus one serves as a lower bound and the other as an upper bound on the optimal objective value. The gap between them is used to measure the closeness to the global optima.

Great thing is that you can find the dual really easily and each feasible solution of the primal problem can be used to get a feasible solution of the dual.

The math behind that is really neat.