Given a linear programming problem as
Primary Problem
\( min\ C^tx
\\
Subject\ to
\\
Ax \leq b \\\\
x\geq 0
\\
A \in M_{mxn}, \ rank(A)=m \\
b\in \mathbb{R}^m, \ C \in \mathbb{R}^n, x \in \mathbb{R}^n
\)
It is associated with another problem which we call dual form:
Dual Problem
\( max\ b^tw
\\
Subject\ to
\\
A^tw \geq C \\\\
w\geq 0
\\
A \in M_{mxn}, \ rank(A)=m \\
b\in \mathbb{R}^m, \ C \in \mathbb{R}^n, w \in \mathbb{R}^m
\)
That is, what was the cost vector, now is constraints vector and viceversa. Constraints matrix is transposed in the dual problem.
In some cases it is easier to solve one than another, or it is possible to give conditions
for one that determine properties of solutions of the other one.
More generally, if we have a Linear Programming problem as
\(
max\ C^tx
\\
Subject\ to
\\
\sum_{j=1}^{n} a_{ij}x_j \leq b_i,\ i \in M_1\\
\sum_{j=1}^{n} a_{ij}x_j = b_i,\ i \in M-M_1\\
x_j\geq 0 , \ j\in N_1
\)
That is, we have only restricted in sign someone of the variables and only in
some of the restrictions we have inequalities.
Then the dual problem becomes:
\(
max\ b^tw
\\
Subject\ to
\\
\sum_{i=1}^{m} a_{ji}w_i \geq C_i,\ j \in N_1\\
\sum_{i=1}^{m} a_{ji}w_i = C_i,\ j \in N - N_1\\
w_i\geq 0 , \ i\in M_1
\)
ie, we have
1. An inequality constraint in the primal variable means restricted in sign variable
in the dual.
2. Equality constraint in the primal, resulting in a variable unconstrained in
sign in the dual.
Existence Theorem
a) If one of the two problems have finite optimal solution, the other one has it as well.
b) If the primal problem has unbounded solution, the dual one has not feasible
optimal solution (conversely is not true).
Corollary 1
Given a pair of dual problems, only one of these conditions is true:
1) Neither one have feasible optimal solution.
2) One have solution feasible but is unbounded and the other has no solution.
3) They both have finite optimal solution.
Corollary 2 (duality theorem)
Given a pair of dual problems, a necessary and sufficient condition for the primal
optimal solution has finite x, is that there is a dual feasible solution w such
that:
\( Cx = bw \)
