0
$\begingroup$

max $x_2$ subject to

$x_1 - 2x_2 \le 0$
$2x_1 - 3x_2 \le 2$
$x_1 - x_2 \le 3$
$-x_1 + 2x_2 \le 2$
$-2x_1 + x_2 \le 0$

Optimal solution: (8, 5) --> $x_2 = 5$

Now assume that the objective is replaced with cos(φ)x + sin(φ)y, where φ is chosen at random, according to the uniform distribution on [0, 2π]. What is the probability to get, as an optimal solution, the same point as in the original problem?

Any help is greatly appreciated!

$\endgroup$
  • $\begingroup$ Have you done the first bit yet? If not, try using the simplex algorithm. $\endgroup$ – Esteemator Jan 31 '16 at 16:03
  • $\begingroup$ @Esteemator hi, yes i solved the initial LO and found the optimal solution to be (8,5) just by graphic. Now I'm working on the trig part of the problem. What I'm thinking is that φ has to be between 0 and π/2 because outside of this, the objective function would lead to negative weights which would lead to an infeasible solution (the feasible domain was entirely positive).. Am I on the right track? $\endgroup$ – zulqar Jan 31 '16 at 16:37
0
$\begingroup$

Since it is a two-variable linear programming and as OP said, I can try to answer this using the graphical technique mentioned. Here is the depicted feasible region (bounded by the red line) for the given constraints.

Feasible Region

And we know that the optimal solution must be located at one of the five corners. and now the desired solution is on the top right hand corner $(5, 8)$. Note that now the objective $V$ is

$$ V = \cos(\varphi)x_1 + \sin(\varphi)x_2 $$

Rearranging this family of object lines to the slope-intercept form gives

$$ x_2 = -\cot(\varphi)x_1 + \csc(\varphi)V$$

(ignore the point where $\sin(\varphi) = 0$ as they are measure $0$ anyway). Note that the $x_2$-intercept is $\csc(\varphi)V$. So the objective is strictly increasing with the $x_2$-intercept if and only if $$\sin(\varphi) > 0$$ And in such case, $V$ is maximized when the $x_2$-intercept is maximized, i.e. the objective line must be pushed upward to obtained the maximized $V$. The slope of the line $-\cot(\varphi)$. So now we can work with the 4 cases:

  1. $\sin(\varphi) > 0, \cos(\varphi) > 0$:

In this case we push upward and the slope is negative. And it will always leads to the optimal solution we wanted. Since $$\varphi \in \left(0, \frac {\pi} {2}\right)$$ The probability in this case is $\displaystyle \frac {1} {4}$.

  1. $\sin(\varphi) > 0, \cos(\varphi) < 0$:

In this case we push upward and the slope is positive. Then we will need the slope lies on $$ \left(0, \frac {1} {2}\right)$$ So we have $$ 0 < -\cot(\varphi) < \frac {1} {2} \iff \tan(\varphi) < -2 \iff \varphi \in \left(\frac {\pi} {2}, \tan^{-1}(-2) + \pi\right) = \left(\frac {\pi} {2}, \pi - \tan^{-1}(2) \right)$$ So the probability in this case is $$\frac {1} {4}\left(\frac {\pi} {2} - \tan^{-1}(2) \right)$$

  1. $\sin(\varphi) < 0, \cos(\varphi) > 0$: In this case we push downward and the slope is positive. Then we will need the slope to be larger than $1$. By similar solving, we have $$ \varphi \in \left(\frac {7\pi} {4}, 2\pi\right)$$ and thus the probability in this case is $\displaystyle \frac {1} {8}$.

  2. $\sin(\varphi) < 0, \cos(\varphi) < 0$: In the last case we push downward and the slope is negative. And the optimal solution will never located at our desired corner.

Summing the cases we have the probability

$$ \frac {1} {4} + \frac {1} {4}\left(\frac {\pi} {2} - \tan^{-1}(2) \right) + \frac {1} {8} = \frac {1} {8}(3 + \pi - 2\tan^{-1}(2))$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.