| Prev | Next | Top | Quiz0810 |
s_j
|
probability (each month) that the marshalls search city
j
|
h_j
|
probability (each month) that the criminal hides in city
j
|
z
| the objective function for the marshall problem |
x
|
the vector
(z , s_1, s_2, s_3)^\T
|
D \in \R^{3 \times 3}
such that the US marshalls optimal strategy
solve the problem
\[
\begin{array}{ll}
{\rm maximize}
& \left[
{\rm min} \; h^\T * D * s \; {\rm w.r.t} \; h \in R_+^3
\right] \; {\rm w.r.t} \; s \in R_+^3
\\
{\rm subject \; to}
& h_1 + h_2 + h_3 = 1
\\
& s_1 + s_2 + s_3 = 1
\end{array}
\]
\[
h_1 * .05 * s_1 + h_2 * .10 * s_2 + h_3 * .15 * s_3
\]
(Note that this assumes that, given the strategies,
the realizations of the strategies are independent.)
If
\[
D = \left( \begin{array}{ccc}
.05 & .00 & .00 \\
.00 & .10 & .00 \\
.00 & .00 & .15
\end{array} \right)
\]
then
h^\T D s^\T
is the probability of finding the
criminal per month.
\[
\begin{array}{ll}
{\rm maximize} & c^\T * x \; {\rm w.r.t} \; x \in \R_+^4
\\
{\rm subject \; to}
& A * x \leq b
\end{array}
\]
where
A \in \R^{5 \times 4}
,
b \in \R^5
,
and
c \in \R^4
.
Note that
z = x_1 \geq 0
does not add an extra constraint
because
s^\T * D * h \geq 0
for all
s \in \R_+^3
and all
h \in \R_+^3
.
What is the matrix
A
and the vectors
b
and
c
.
(Hint: translate the equality constraint to two inequality constraints.)
\[
A = \left( \begin{array}{ccccc}
0 & 1 & 1 & 1 & 1 \\
0 & -1 & -1 & -1 & -1 \\
1 & - .05 & .00 & .00 \\
1 & .00 & - .10 & .00 \\
1 & .00 & .00 & -.15
\end{array} \right)
\; , \;
b = \left( \begin{array}{c}
1 \\ -1 \\ 0 \\ 0 \\ 0
\end{array} \right)
\; , \;
c = \left( \begin{array}{c}
1 \\ 0 \\ 0 \\ 0
\end{array} \right)
\]
s_1 = 6 / 11
,
s_2 = 3 / 11
, and
s_3 = 2 / 11
.
In addition, they think that the optimal strategy for the criminal is
h_1 = 6 / 11
,
h_2 = 3 / 11
, and
h_3 = 2 / 11
.
s
proposed above
there is a corresponding primal vector
x
that is feasible
for the problem in B.
Compute the corresponding objective value
c^\T x
.
The dual to the problem in B is
\[
\begin{array}{ll}
{\rm maximize} & b^\T * y
\\
{\rm subject \; to}
& A^\T * y \geq c
\end{array}
\]
Show that there is a feasible
y \in \R^5
that has the dual objective
b^\T y
equal to the primal value
c^\T x
computed above.
x = ( z , 6/11 , 6/22 , 6/33 )^\T
.
For this vector to be primal feasible, we need
\[
A * x
=
\left( \begin{array}{c}
6 / 11 + 3 / 11 + 2 / 11
\\
- 6 / 11 - 3 / 11 - 2 / 11
\\
z - .05 * 6 / 11
\\
z - .10 * 3 / 11
\\
z - .15 * 2 / 11
\end{array} \right)
=
\left( \begin{array}{c}
1 \\ -1 \\ z - 3 / 110 \\ z - 3 / 110 \\ z - 3 / 110
\end{array} \right)
\leq
\left( \begin{array}{c}
1 \\ -1 \\ 0 \\ 0 \\ 0
\end{array} \right)
=
b
\]
Thus, with
z = 3 / 110
,
the vector
x \in \R_+^4
satisfies all the primal constraints.
Furthermore, the primal objective is equal to
\[
c^\T * x = z = 3 / 110
\]
( y_1 , y_2 , 6 / 11 , 3 / 11 , 2 / 11)
.
For this vector to be dual feasible, we need
\[
A^\T * y
=
\left( \begin{array}{c}
6 / 11 + 3 / 11 + 2 / 11 \\
y_1 - y_2 - .05 * 6 / 11 \\
y_1 - y_2 - .10 * 3 / 11 \\
y_1 - y_2 - .15 * 2 / 11
\end{array} \right)
=
\left( \begin{array}{c}
1 \\ y_1 - y_2 - 3 / 110 \\ y_1 - y_2 - 3 / 110 \\ y_1 - y_2 - 3 / 110
\end{array} \right)
\geq
\left( \begin{array}{c}
1 \\ 0 \\ 0 \\ 0
\end{array} \right)
=
c
\]
Thus, with
y_1 = 3 / 100
and
y_2 = 0
the vector
y \in \R_+^5
satisfies all the dual constraints.
Furthermore, the dual objective is equal to
\[
b^\T * y = y_1 - y_2 = 3 / 100
\]