| Prev | Next | Top | Quiz0720 |
x \in \R_+^n
to abbreviate
x \in \R^n
and
x_j \geq 0
for all
j
.
We choose
m = 3
,
n = 3
and
define
c \in \R^n
,
A \in \R^{m \times n}
and
b \in \R^m
by
\[
\begin{array}{ccccc}
A = \left( \begin{array}{ccc}
2 & 3 & 1 \\
4 & 1 & 2 \\
3 & 4 & 2
\end{array} \right)
& , &
b = \left( \begin{array} {c} 5 \\ 11 \\ 8 \end{array} \right)
& , &
c = \left( \begin{array} {c} 5 \\ 4 \\ 3 \end{array} \right)
\end{array}
\]
We use (P) to denote the corresponding primal problem
\[
\begin{array}{lll}
{\rm maximize} & c^\T * x & {\rm w.r.t.} \; x \in \R_+^n \\
{\rm subject \; to} & A * x \leq b \\
\end{array}
\hspace{2cm} (P)
\]
and (D) to denote the dual problem
\[
\begin{array}{lll}
{\rm minimize} & b^\T * y & {\rm w.r.t.} \; y \in \R_+^m \\
{\rm subject \; to} & A^\T * y \geq c \\
\end{array}
\hspace{2cm} (D)
\]
x^\star
(you need not show any work for this part)
that solves the primal problem (P)
(Hint: see equation 2.1 of the text).
\[
x^\star =
\left( \begin{array}{c} 2 \\ 0 \\ 1 \end{array} \right)
\]
y^\star
that solves
the dual problem (D).
\[
A * x^\star =
\left( \begin{array}{c} 5 \\ 10 \\ 8 \end{array} \right)
\]
It follows that
y^\star_2 = 0
because
\sum_{j=1}^n A_{2,j} x^\star_j < b_2
.
Furthermore
x^\star_1
and
x^\star_3
are not zero.
Hence
\[
\begin{array}{rcl}
c_1 & = & A_{1,1} * y^\star_1 + A_{2,1} * y^\star_2 + A_{3,1} * y^\star_3
\\
c_3 & = & A_{1,3} * y^\star_1 + A_{2,3} * y^\star_2 + A_{3,3} * y^\star_3
\\
5 & = & 2 * y^\star_1 + 4 * 0 + 3 * y^\star_3
\\
3 & = & 1 * y^\star_1 + 2 * 0 + 2 * y^\star_3
\\
y^\star_1 & = & 3 - 2 * y^\star_3
\\
5 & = & 2 * (3 - 2 * y^\star_3 ) + 3 * y^\star_3
\\
-1 & = & - y^\star_3
\end{array}
\]
Hence the dual solution is given by
\[
y^\star =
\left( \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \right)
\]
\[
\begin{array}{rcll}
c^\T * x^\star & = & 5 * 2 + 4 * 0 + 3 * 1 & = 13 \\
b^\T * y^\star & = & 5 * 1 + 11 * 0 + 8 * 1 & = 13
\end{array}
\]
Thus the answer is yes, the primal and dual objective function
values are equal at
x^\star
,
y^\star
.
t \in \R^n
is defined by
t_1 = 0
,
t_2 = - 1
, and
t_3 = 0
.
We define the perturbed problem
\[
\begin{array}{lll}
{\rm maximize} & c^\T * x & {\rm w.r.t.} \; x \in \R_+^n \\
{\rm subject \; to} & A * x \leq b + t \\
\end{array}
\hspace{2cm}
\]
What is the objective function value
corresponding to the optimal solution for the perturbed problem ?
Show that this agrees with the result predicted by Theorem 5.5.
\[
b + t =
\left( \begin{array}{c} 5 \\ 10 \\ 8 \end{array} \right)
\]
Hence
(using the calculation at the beginning of the solution of problem B)
it follows the point
x^\star
defined in problem A
satisfies the constraints; i.e. is feasible for the perturbed problem.
On could use Theorem 5.2 to show that the pair
x^\star
,
y^\star
are optimal for the perturbed problem.
It is simpler to note that
x^\star
was optimal over a larger set
of feasible solution in the primal problem (P)
(and with the same objective function).
Thus
x^\star
is optimal for the perturbed problem
and the corresponding value of the objective is
13
.
\[
\begin{array}{rcl}
z^\star + \sum_{i=1}^m y^\star_i * t_i
& = &
\sum_{j=1}^n c_j * x^\star_j + \sum_{i=1}^m y^\star_i * t_i
\\
& = &
5 * 2 + 4 * 0 + 3 * 1 + 1 * 0 + 0 * 1 + 1 * 0
\\
& = &
13
\end{array}
\]
Which is the same as the optimal value determined above.