QE2013_AC-3_ECE580-3
(i)
Solution:
To remove absolute values, each variable is separated into a positive component and a negative component. For $ x_1 $ for example:
$ x_1 = x_1^+ - x_1^-, \ \ \ \ x_1^+ ,x_1^- \ge 0, \ at\ least\ one\ of\ x_1^+,\ x_1^-\ is\ 0 $
Then $ |x_1| = x_1^+ + x_1^- $
Therefore the given problem can be converted into a linear programming problem:
$ maximize -x_1^+ -x_1^- -x_2^+ -x_2^- -x_3^+ -x_3^- \\ subject\ to \\ \begin{bmatrix} 1 & -1 & 1 & -1 & -1 & 1 \\ 0 & 0 & -1& 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_1^+ \\ x_1^- \\ x_2^+ \\ x_2^- \\ x_3^+ \\ x_3^- \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \\ x_1^+ ,x_1^- ,x_2^+ ,x_2^- ,x_3^+ ,x_3^- \ge 0 $
This problem shares the same solution of the original problem if for i = 1,2,3, at least one of $ x_i^+\ and\ x_i^-\ is\ 0. $
$ -x_2^+ +x_2^- = 1 \Rightarrow x_2^+ = 0,\ x_2^- = 1 $
Therefore the equality constraint can be simplified as
$ x_1^+ -x_1^- -x_3^+ +x_3^- = 3 $
There are 4 cases to consider:
Case 1: $ x_1^+ = x_3^+ = 0 $
This is equivalent to finding $ x_1^-, x_3^- \ge 0\ to\ maximize\ -x_1^- -x_3^-\ subject\ to\ -x_1^- +x_3^- = 3 $
Optimal solution is $ x_1^- = 0, x_3^- = 3 $, in this case $ -x_1^+ -x_1^- -x_2^+ -x_2^- -x_3^+ -x_3^- = -4 $
The other 3 cases can be solved similarly:
Case 2: $ x_1^+ = x_3^- = 0 $
No solution as $ -x_1^- -x_3^+ = 3 $ cannot be satisfied (left side is non-positive).
Case 3: $ x_1^- = x_3^+ = 0 $
Every feasible solution is optimal in this case (any $ x_1^+, x_3^- $ satisfying $ x_1^+ +x_3^- = 3, x_1^+, x_3^-\ge 0 $, $ -x_1^+ -x_1^- -x_2^+ -x_2^- -x_3^+ -x_3^- = -4 $
Case 4: $ x_1^- = x_3^- = 0 $
Optimal solution is $ x_1^+ = 3, x_3^+ = 0 $, in this case $ -x_1^+ -x_1^- -x_2^+ -x_2^- -x_3^+ -x_3^- = -4 $
(ii)
Solution:
The schema will be destroyed if and only if the 2nd or 4th symbol change. Equivalently, the schema will not be destroyed if and only if both 2nd and the 4th symbols stay the same. As those events are independent:
$ P(Not\ destroyed) = P(2nd\ symbol\ does\ not\ change) \times P(4th\ symbol\ does\ not\ change) $
$ = (1-0.1)\times(1-0.1) = 0.81 $
Therefore
$ P(destroyed) = 1 - 0.81 = 0.19 $
