1. **Problem statement:** We have the feasible region $S = \{(x_1,x_2) \in \mathbb{R}^2 : -x_1 - x_2 \leq 1, -x_1 + 2x_2 \geq 2, x_1 - x_2 \leq -1, x_1 \leq 0, x_2 \geq 0\}$ and want to analyze it graphically and solve the optimization problem $\min Z = c_1 x_1 + c_2 x_2$. 2. **Representing $S$ graphically:** Rewrite inequalities: - $-x_1 - x_2 \leq 1 \implies x_2 \geq -x_1 -1$ - $-x_1 + 2x_2 \geq 2 \implies 2x_2 \geq x_1 + 2 \implies x_2 \geq \frac{x_1 + 2}{2}$ - $x_1 - x_2 \leq -1 \implies x_2 \geq x_1 + 1$ - $x_1 \leq 0$ - $x_2 \geq 0$ The feasible region is the intersection of these half-planes. 3. **Find vertices (basic feasible solutions):** Solve intersections of pairs of boundary lines that satisfy all constraints. - Intersection of $x_1 = 0$ and $x_2 = 0$ is $(0,0)$ but check constraints: - $-0 - 0 = 0 \leq 1$ OK - $-0 + 2\cdot0 = 0 \geq 2$ NO (fails) - Intersection of $x_1 = 0$ and $-x_1 + 2x_2 = 2$: - $-0 + 2x_2 = 2 \implies x_2 = 1$ - Check other constraints: - $-0 - 1 = -1 \leq 1$ OK - $x_1 - x_2 = 0 - 1 = -1 \leq -1$ OK - $x_2 \geq 0$ OK So $(0,1)$ is feasible. - Intersection of $-x_1 - x_2 = 1$ and $x_1 - x_2 = -1$: From $x_1 - x_2 = -1 \implies x_1 = x_2 -1$ Substitute into $-x_1 - x_2 = 1$: $$- (x_2 -1) - x_2 = 1 \implies -x_2 +1 - x_2 = 1 \implies -2x_2 +1 = 1 \implies -2x_2 = 0 \implies x_2 = 0$$ Then $x_1 = 0 -1 = -1$ Check other constraints: - $-x_1 + 2x_2 = -(-1) + 0 = 1 \geq 2$ NO (fails) - Intersection of $-x_1 - x_2 = 1$ and $-x_1 + 2x_2 = 2$: From $-x_1 - x_2 = 1 \implies x_1 = -x_2 -1$ Substitute into $-x_1 + 2x_2 = 2$: $$-(-x_2 -1) + 2x_2 = 2 \implies x_2 +1 + 2x_2 = 2 \implies 3x_2 +1 = 2 \implies 3x_2 = 1 \implies x_2 = \frac{1}{3}$$ Then $x_1 = -\frac{1}{3} -1 = -\frac{4}{3}$ Check $x_1 \leq 0$ OK, $x_2 \geq 0$ OK, $x_1 - x_2 = -\frac{4}{3} - \frac{1}{3} = -\frac{5}{3} \leq -1$ OK So $\left(-\frac{4}{3}, \frac{1}{3}\right)$ is feasible. - Intersection of $-x_1 + 2x_2 = 2$ and $x_1 - x_2 = -1$: From $x_1 - x_2 = -1 \implies x_1 = x_2 -1$ Substitute into $-x_1 + 2x_2 = 2$: $$-(x_2 -1) + 2x_2 = 2 \implies -x_2 +1 + 2x_2 = 2 \implies x_2 +1 = 2 \implies x_2 = 1$$ Then $x_1 = 1 -1 = 0$ Check $x_1 \leq 0$ OK, $x_2 \geq 0$ OK, $-x_1 - x_2 = -0 -1 = -1 \leq 1$ OK So $(0,1)$ again (already found). - Intersection of $x_1 = 0$ and $x_1 - x_2 = -1$: $0 - x_2 = -1 \implies x_2 = 1$ Same point $(0,1)$. - Intersection of $x_1 = 0$ and $-x_1 - x_2 = 1$: $-0 - x_2 = 1 \implies x_2 = -1$ (not feasible since $x_2 \geq 0$) - Intersection of $x_2 = 0$ and $-x_1 + 2x_2 = 2$: $-x_1 + 0 = 2 \implies x_1 = -2$ (feasible since $x_1 \leq 0$) Check other constraints: - $-x_1 - x_2 = -(-2) - 0 = 2 \leq 1$ NO (fails) - Intersection of $x_2 = 0$ and $x_1 - x_2 = -1$: $x_1 - 0 = -1 \implies x_1 = -1$ Check $-x_1 - x_2 = -(-1) - 0 = 1 \leq 1$ OK Check $-x_1 + 2x_2 = -(-1) + 0 = 1 \geq 2$ NO (fails) **Feasible vertices found:** $(0,1)$ and $\left(-\frac{4}{3}, \frac{1}{3}\right)$. 4. **Feasible non-degenerate basic solution:** Choose $(0,1)$ because it is a vertex where exactly two constraints are active and linearly independent. 5. **Extreme directions:** Since $S$ is unbounded, find directions $d$ such that for any $x \in S$, $x + \lambda d \in S$ for $\lambda \geq 0$. Check constraints for $d = (d_1, d_2)$: - $-d_1 - d_2 \leq 0$ - $-d_1 + 2 d_2 \geq 0$ - $d_1 - d_2 \leq 0$ - $d_1 \leq 0$ - $d_2 \geq 0$ Try $d^1 = (0,1)$: - $-0 -1 = -1 \leq 0$ OK - $-0 + 2\cdot1 = 2 \geq 0$ OK - $0 -1 = -1 \leq 0$ OK - $0 \leq 0$ OK - $1 \geq 0$ OK So $d^1 = (0,1)$ is an extreme direction. Try $d^2 = (-1,0)$: - $-(-1) - 0 = 1 \leq 0$ NO (fails) Try $d^2 = (-1, -1)$: - $-(-1) - (-1) = 1 + 1 = 2 \leq 0$ NO Try $d^2 = (-1, 1)$: - $-(-1) - 1 = 1 - 1 = 0 \leq 0$ OK - $-(-1) + 2\cdot1 = 1 + 2 = 3 \geq 0$ OK - $-1 - 1 = -2 \leq 0$ OK - $-1 \leq 0$ OK - $1 \geq 0$ OK So $d^2 = (-1,1)$ is an extreme direction. 6. **Non-extreme directions:** Any positive linear combination of $d^1$ and $d^2$ that is not a scalar multiple of either is a non-extreme direction. 7. **Solve problem (P) with $c_1 = -2$, $c_2 = -4$:** Minimize $Z = -2 x_1 -4 x_2$ over $S$. Evaluate $Z$ at vertices: - At $(0,1)$: $Z = -2\cdot0 -4\cdot1 = -4$ - At $\left(-\frac{4}{3}, \frac{1}{3}\right)$: $Z = -2 \cdot \left(-\frac{4}{3}\right) -4 \cdot \frac{1}{3} = \frac{8}{3} - \frac{4}{3} = \frac{4}{3} \approx 1.333$ Since $Z$ is smaller at $(0,1)$, the minimum is at $(0,1)$ with $Z = -4$. Check if moving along extreme directions decreases $Z$: - Direction $d^1 = (0,1)$: $c \cdot d^1 = -2\cdot0 -4\cdot1 = -4 < 0$ so $Z$ decreases moving along $d^1$. - Direction $d^2 = (-1,1)$: $c \cdot d^2 = -2\cdot(-1) -4\cdot1 = 2 -4 = -2 < 0$ also decreases. Since $Z$ decreases along extreme directions, problem is unbounded below. But $S$ restricts $x_2 \geq 0$, so check if feasible. 8. **Values for $c_1, c_2$ for (a) optimal at $x^* = (-3,2)$:** Check if $x^* \in S$: - $-(-3) - 2 = 3 - 2 = 1 \leq 1$ OK - $-(-3) + 2\cdot2 = 3 + 4 = 7 \geq 2$ OK - $-3 - 2 = -5 \leq -1$ OK - $-3 \leq 0$ OK - $2 \geq 0$ OK For $x^*$ to be optimal, $c$ must satisfy: $$c \cdot (x - x^*) \geq 0 \quad \forall x \in S$$ This means $c$ is a normal vector to supporting hyperplane at $x^*$. Use active constraints at $x^*$ to find $c$: Active constraints at $x^*$ are those satisfied with equality: - $-x_1 - x_2 = 1$ at $(-3,2)$: $3 - 2 = 1$ active - $x_1 - x_2 \leq -1$: $-3 - 2 = -5 \leq -1$ not active - $-x_1 + 2x_2 \geq 2$: $3 + 4 = 7 \geq 2$ not active - $x_1 \leq 0$: $-3 \leq 0$ active - $x_2 \geq 0$: $2 \geq 0$ not active Gradients of active constraints: - For $-x_1 - x_2 = 1$: gradient $g_1 = (-1, -1)$ - For $x_1 \leq 0$: gradient $g_2 = (1, 0)$ $c$ must be a nonnegative combination: $c = \lambda_1 g_1 + \lambda_2 g_2$ with $\lambda_i \geq 0$. Set $c = (c_1, c_2) = \lambda_1 (-1, -1) + \lambda_2 (1, 0) = (-\lambda_1 + \lambda_2, -\lambda_1)$. Choose $\lambda_1 > 0$ to have $c_2 = -\lambda_1 < 0$. Example: $\lambda_1 = 1$, $\lambda_2 = 2$ gives $c = (-1 + 2, -1) = (1, -1)$. So $c_1 = 1$, $c_2 = -1$ is one such vector. 9. **(b) Problem impossible:** If $S$ is empty or $c$ points away from $S$ so no minimum exists. Since $S$ is nonempty, problem impossible if $c$ points strictly inside the recession cone with $c \cdot d < 0$ for all extreme directions $d$. For example, if $c = (1,1)$, then $c \cdot d^1 = 1\cdot0 + 1\cdot1 = 1 > 0$, so no unbounded decrease. If $c$ is such that no feasible $x$ minimizes $Z$, problem is impossible. 10. **(c) Bounded edge of optimal solutions with $c_1 = -2$:** Set $c_1 = -2$ and find $c_2$ such that the objective is constant along an edge. Check edge between $(0,1)$ and $\left(-\frac{4}{3}, \frac{1}{3}\right)$: Vector along edge: $$v = \left(-\frac{4}{3} - 0, \frac{1}{3} - 1\right) = \left(-\frac{4}{3}, -\frac{2}{3}\right)$$ For $Z$ constant along edge: $$c \cdot v = 0 \implies -2 \cdot \left(-\frac{4}{3}\right) + c_2 \cdot \left(-\frac{2}{3}\right) = 0$$ $$\frac{8}{3} - \frac{2}{3} c_2 = 0 \implies \frac{2}{3} c_2 = \frac{8}{3} \implies c_2 = 4$$ So $c = (-2,4)$ gives a bounded edge of optimal solutions along that segment. Optimal value at $(0,1)$: $$Z = -2 \cdot 0 + 4 \cdot 1 = 4$$ At $\left(-\frac{4}{3}, \frac{1}{3}\right)$: $$Z = -2 \cdot \left(-\frac{4}{3}\right) + 4 \cdot \frac{1}{3} = \frac{8}{3} + \frac{4}{3} = 4$$ **Final answers:** - Feasible non-degenerate basic solution: $(0,1)$ - Extreme directions: $d^1 = (0,1)$, $d^2 = (-1,1)$ - Non-extreme directions: positive combinations of $d^1$ and $d^2$ not scalar multiples - For $c_1 = -2$, $c_2 = -4$, minimum at $(0,1)$ with $Z = -4$ - For $x^* = (-3,2)$ optimal, $c$ must be a positive combination of gradients of active constraints, e.g. $c = (1,-1)$ - Problem impossible if $c$ points away from $S$ - For bounded edge of optimal solutions with $c_1 = -2$, set $c_2 = 4$, optimal value $Z=4$ along edge between $(0,1)$ and $\left(-\frac{4}{3}, \frac{1}{3}\right)$