| Prev | Next | Top | DualTheorem |
A \in \R^{m \times n}
,
b \in \R^m
,
and
c \in \R^n
define the
primal problem
with extended objective
f(x)
and the
dual problem
with extended objective
g(y)
.
Q \in \R^{m \times m}
to be the identity matrix and the slack vector
s \in \R_m
are defined by
\[
b = A x + Q s
\]
The scalar
e \in \R
and the
coefficient vector
y \in \R^m
are defined by
e = 0
,
y = 0
.
The primal problem has the following tableau form:
\[
\begin{array}{llclcl}
{\rm maximize} & z
\\
{\rm subject \; to} & b = A x & + & Q s
\\
& e = c^T x & - & y^T s & - & z
\\
& x \geq 0 & , & s \geq 0
\end{array}
\]
\[
\begin{array}{llclcl}
{\rm maximize} & z
\\
{\rm subject \; to} & \hat{b} = \hat{A} x & + & \hat{Q} s
\\
& \hat{e} = \hat{c}^T x & - & \hat{y}^T s & - & z
\\
& x \geq 0 & , & s \geq 0
\end{array}
\]
In other words,
x \in \R^n
,
s \in \R^m
,
and
z \in \R
satisfies the constraints in the tableau above
if and only if they satisfy the constraints in the original tableau.
\hat{c} \leq 0
,
\hat{y} \geq 0
, and there is a feasible pair
( \hat{x} , \hat{s} )
such that
\[
0 = \hat{c}^T \hat{x} - \hat{y}^T \hat{s}
\]
It follows that
\hat{x}
solves the primal problem
and
\hat{y}
solves the dual problem.
Q
is the identity matrix and
e = 0
.
Thus for all
x \in \R_+^n
, by setting
s = b - A x
we have
\[
\begin{array}{rcl}
\sum_{j=1}^n c_j x_j
& = &
- \hat{e} + \sum_{j=1}^n \hat{c}_j x_j - \sum_{i=1}^m \hat{y}_i s_i
\\
& = &
- \hat{e}
+ \sum_{j=1}^n \hat{c}_j x_j
- \sum_{i=1}^m \hat{y}_i \left( b_i - \sum_{j=1}^n A_{i,j} x_j \right)
\\
\sum_{i=1}^m b_i \hat{y}_i + \hat{e}
& = &
\sum_{j=1}^n \left(
- c_j + \hat{c}_j + \sum_{i=1}^m \hat{y}_i A_{i,j}
\right) x_j
\hspace{1cm} (\star)
\end{array}
\]
From equation
(\star)
, choosing
x = 0
, we obtain
\[
\begin{array}{rcl}
\sum_{i=1}^m b_i \hat{y}_i + \hat{e} & = & 0
\\
\sum_{i=1}^m b_i \hat{y}_i & = & - \hat{e}
\end{array}
\]
Form equation
(\star)
, choosing
x = 0
except for the j-th component which is one,
we obtain the following equation for
j = 1 , \ldots , n
:
\[
\begin{array}{rcl}
0 & = & - c_j + \hat{c}_j + \sum_{i=1}^m \hat{y}_i A_{i,j}
\\
c_j & \leq & \sum_{i=1}^m \hat{y}_i A_{i,j}
\end{array}
\]
Note that we used
\hat{c}_j \leq 0
to obtain the
inequality above.
It follows that
\hat{y}
is dual feasible,
\hat{x}
is primal feasible, and
\[
f( \hat{x} ) =
- \hat{e} + \hat{c}^T \hat{x} - \hat{y}^T \hat{s}
=
- \hat{e}
=
b^T \hat{y}
=
g( \hat{y} )
\]
The conclusion of the theorem now follows from the
Duality Gap Lemma
.