| Prev | Next | Top | DualExample |
\R_+^n
to denote the set of
x \in \R^n
such that
x \geq 0
; i.e.,
x_j \geq 0
for
j = 1 , \ldots , n
.
\[
\begin{array}{rrrrrrrrrr}
{\rm maximize} & 4 x_1 & + & x_2 & + & 5 x_3 & + & 3 x_4 & & \\
{\rm subject \; to} & x_1 & - & x_2 & - & x_3 & + & 3 x_4 & \leq & 1 \\
& 5 x_1 & + & x_2 & + & 3 x_3 & + & 8 x_4 & \leq & 55 \\
& - x_1 & + & 2 x_2 & + & 3 x_3 & - & 5 x_4 & \leq & 3 \\
& x_1 & , & x_2 & , & x_3 & , & x_4 & \geq & 0
\end{array}
\]
The feasible set for this problem is defined by
\[
X = \left\{ x \in \R_+^4 \; : \; \begin{array}{rrrrrrrrr}
x_1 & - & x_2 & - & x_3 & + & 3 x_4 & \leq & 1 \\
5 x_1 & + & x_2 & + & 3 x_3 & + & 8 x_4 & \leq & 55 \\
- x_1 & + & 2 x_2 & + & 3 x_3 & - & 5 x_4 & \leq & 3
\end{array} \right\}
\]
The extended primal objective function for this problem
f : \R_+^4 \rightarrow \R \cup \{ - \infty \}
is defined by
\[
f(x) = \left\{ \begin{array}{ll}
4 x_1 + x_2 + 5 x_3 + 3 x_4 & {\rm if} \; x \in X \\
- \infty & {\rm otherwise}
\end{array} \right.
\]
Solving the primal problem is equivalent to finding
an argument
x
that maximizes the value of
f(x)
with respect to
x \in \R_+^4
.
L : \R_+^4 \times \R_+^3 \rightarrow \R
is defined by
\[
\begin{array}{rcl}
L(x,y) & = &
4 x_1 + x_2 + 5 x_3 + 3 x_4
\\
& + &
y_1 ( 1 - x_1 + x_2 + x_3 - 3 x_4 )
\\
& + &
y_2 ( 55 - 5 x_1 - x_2 - 3 x_3 - 8 x_4 )
\\
& + &
y_3 ( 3 + x_1 - 2 x_2 - 3 x_3 + 5 x_4 )
\end{array}
\]
It follows from this definition that for all
x \in \R_+^4
\[
f(x) = \inf \; L(x, y) \; {\rm with \; respect \; to} \; y \in \R_+^3
\]
Regrouping terms in the definition of
L
,
we have
\[
\begin{array}{rcl}
L(x,y)
& = & y_1 + 55 y_2 + 3 y_3
\\
& + & x_1 ( 4 - y_1 - 5 y_2 + y_3 )
\\
& + & x_2 ( 1 + y_1 - y_2 - 2 y_3 )
\\
& + & x_3 ( 5 + y_1 - 3 y_2 - 3 y_3 )
\\
& + & x_4 ( 3 - 3 y_1 - 8 y_2 + 5 y_3 )
\end{array}
\]
g : \R_+^3 \rightarrow \R \cup \{ + \infty \}
is defined by
\[
g(y) = \sup \; L(x, y) \; {\rm with \; respect \; to} \; x \in \R_+^4
\]
The corresponding feasible set for the dual problem is
\[
Y = \left\{ y \in \R_+^3 \; : \; \begin{array}{rrrrrrr}
y_1 & + & 5 y_2 & + & y_3 \geq & 4 \\
- y_1 & + & y_2 & + & 2 y_3 \geq & 1 \\
- y_1 & + & 3 y_2 & + & 3 y_3 \geq & 5 \\
3 y_1 & + & 8 y_2 & - & 5 y_3 \geq & 3
\end{array} \right\}
\]
And the dual objective can be represented by
\[
g(y) = \left\{ \begin{array}{ll}
y_1 + 55 y_2 + 3 y_3 & {\rm if} \; y \in Y \\
+ \infty & {\rm otherwise}
\end{array} \right.
\]
The dual problem is to find an argument value
y
that minimizes
g(y)
with respect to
y \in \R_+^3
.
This is equivalent to the following problem:
\[
\begin{array}{rrrrrrrrrr}
{\rm minimize} & y_1 & + & 55 y_2 & + & 3 y_3 & & \\
{\rm subject \; to} & y_1 & + & 5 y_2 & + & y_3 & \geq & 4 \\
- y_1 & + & y_2 & + & 2 y_3 & \geq & 1 \\
- y_1 & + & 3 y_2 & + & 3 y_3 & \geq & 5 \\
3 y_1 & + & 8 y_2 & - & 5 y_3 & \geq & 3 \\
y_1 & , & y_2 & , & y_3 & \geq & 0
\end{array}
\]