Chapter 2 linear programming problems

Theorem 2.1: Weak Duality Theorem
Consider the symmetric primal-dual linear programmes, Max Z = C^′X, s. t. AX ≤
b, X ≥ 0, and Min W = b^′Y, s. t. A^′X ≥ C, Y ≥ 0. The value of the objective
function of the minimum problem (dual) for any feasible solution is always greater
than or equal to that of the maximum problem (primal).

From the weak duality theorem we can infer the following important results:

Corollary 2.1 The value of the objective function of the maximum (primal)
problem for any (primal) feasible solution is a lower bound to the minimum
value of the dual objective.

Corollary 2.2 Similarly the objective function value of the minimum problem
(dual) for any (dual) feasible solution is an upper bound to the maximum
value of the primal objective.

33

Corollary 2.3 If the primal problem is feasible and its objective is unbounded
(i.e., max Z → +∞), then the dual problem is infeasible.

Corollary 2.4 Similarly, if the dual problem is feasible, and is unbounded (i.e.,min W →
−∞), then the primal problem is infeasible.
Theorem 2.2: Optimality Criterion Theorem
If there exist feasible solutions X⁰ and Y ⁰ for the symmetric dual linear pra-
grammes such that the corresponding values of their objective functions are equal,
then these feasible solution are in fact optimal solutions to their respective prob-
lems.
Theorem 2.3: Main Duality Theorem
If both the primal and dual problems are feasible, then they both have optimal
solutions such their optimal values of the objective functions are equal.

We will use the properties of duality theory in proposed search algorithm, see
section 5.

34