Consider the feasible region $C = \{(x, y) : 0 \leq x \leq 1, 0 \leq y \leq 1, y \leq x\}$. (a) Suppose $a \neq 0, b \neq 0$. Show that an optimal solution to $\max_{(x,y) \in C} a... Consider the feasible region $C = \{(x, y) : 0 \leq x \leq 1, 0 \leq y \leq 1, y \leq x\}$. (a) Suppose $a \neq 0, b \neq 0$. Show that an optimal solution to $\max_{(x,y) \in C} ax + by$ is either (0,0), (1,0), or (1,1). Describe all possible values of $a$ and $b$ for which each of $\{(0,0), (1,0), (1, 1)\}$ is an optimal solution. (b) Suppose $a$ and $b$ are independently drawn from [-1,1] using a probability distribution with cumulative distribution function (cdf) F. What is the probability that the unique optimal solution to the above optimization problem is (1,0)? Read more

Steps to Solve

1. Understanding the feasible region

The feasible region $C$ is a triangle defined by the vertices (0,0), (1,0), and (1,1). This region is a subset of the unit square where $y \leq x$.

2. Evaluating the objective function at the vertices

The objective function is $ax + by$. Evaluate this function at each vertex of the feasible region:

• At (0,0): $a(0) + b(0) = 0$
• At (1,0): $a(1) + b(0) = a$
• At (1,1): $a(1) + b(1) = a + b$

3. Showing optimality at the vertices

Since $C$ is a convex set and the objective function is linear, the maximum value must occur at one of the vertices. Thus, the optimal solution must be one of (0,0), (1,0), or (1,1).

4. Characterizing when (0,0) is optimal

(0,0) is optimal if $0 > a$ and $0 > a+b$. This is equivalent to $a < 0$ and $a + b < 0$.

5. Characterizing when (1,0) is optimal

(1,0) is optimal if $a > 0$ and $a > a+b$. This is equivalent to $a > 0$ and $b < 0$.

6. Characterizing when (1,1) is optimal

(1,1) is optimal if $a+b > 0$ and $a+b > a$. This is equivalent to $a+b > 0$ and $b > 0$.

7. Solving part (b): Probability of (1,0) being the unique optimal solution

For (1,0) to be the unique optimal solution, we need $a > 0$, $b < 0$, $a > a+b$ (which simplifies to $b < 0$), $a > 0$ and to ensure it's unique, we want $a+b < a$ and $0 < a$. The conditions are therefore $a > 0$ and $b < 0$. Since $a$ and $b$ are independently drawn from [-1,1], the probability density function for each is $f(x) = 1/2$ for $-1 \le x \le 1$. The probability that $a > 0$ is $\int_0^1 \frac{1}{2} da = \frac{1}{2}$. The probability that $b < 0$ is $\int_{-1}^0 \frac{1}{2} db = \frac{1}{2}$. Since $a$ and $b$ are independent, the probability that $a > 0$ and $b < 0$ is $\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$.