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\}$$ We want to represent $S$ graphically, find a feasible nondegenerate basic solution, two distinct extreme directions, and all non-extreme directions. 2. **Step 1: Understand constraints and feasible region** - Rewrite inequalities: - $-x_1 - x_2 \leq 1 \Rightarrow x_1 + x_2 \geq -1$ - $-x_1 + 2x_2 \geq 2 \Rightarrow -x_1 + 2x_2 \geq 2$ - $x_1 - x_2 \leq -1$ - $x_1 \leq 0$ - $x_2 \geq 0$ 3. **Step 2: Find vertices (basic feasible solutions)** Vertices occur at intersections of constraints. Solve pairs: - Intersection of $x_1 = 0$ and $x_2 \geq 0$ with others: - From $x_1 + x_2 = -1$ at $x_1=0$: $x_2 = -1$ (not feasible since $x_2 \geq 0$) - Intersection of $-x_1 + 2x_2 = 2$ and $x_1 - x_2 = -1$: Solve system: $$\begin{cases} -x_1 + 2x_2 = 2 \\ x_1 - x_2 = -1 \end{cases}$$ Add equations: $$(-x_1 + 2x_2) + (x_1 - x_2) = 2 + (-1) \Rightarrow x_2 = 1$$ Substitute $x_2=1$ into $x_1 - x_2 = -1$: $$x_1 - 1 = -1 \Rightarrow x_1 = 0$$ So vertex at $(0,1)$. - Check if $(0,1)$ satisfies all constraints: - $x_1 + x_2 = 1 \geq -1$ ✓ - $-x_1 + 2x_2 = 2 \geq 2$ ✓ - $x_1 - x_2 = -1 \leq -1$ ✓ - $x_1 = 0 \leq 0$ ✓ - $x_2 = 1 \geq 0$ ✓ - Intersection of $x_1 = 0$ and $x_1 + x_2 = -1$ is infeasible. - Intersection of $x_1 - x_2 = -1$ and $x_1 + x_2 = -1$: Add: $$2x_1 = -2 \Rightarrow x_1 = -1$$ Substitute into $x_1 - x_2 = -1$: $$-1 - x_2 = -1 \Rightarrow x_2 = 0$$ Vertex at $(-1,0)$. - Check feasibility: - $x_1 + x_2 = -1 \geq -1$ ✓ - $-x_1 + 2x_2 = 1 \geq 2$ ✗ (fails) So $(-1,0)$ is not feasible. - Intersection of $-x_1 + 2x_2 = 2$ and $x_2 = 0$: Substitute $x_2=0$: $$-x_1 = 2 \Rightarrow x_1 = -2$$ Check $x_1 - x_2 = -1$: $$-2 - 0 = -2 \leq -1$$ ✓ Check $x_1 \leq 0$: $$-2 \leq 0$$ ✓ Check $x_1 + x_2 \geq -1$: $$-2 + 0 = -2 \geq -1$$ ✗ (fails) So $(-2,0)$ not feasible. - Intersection of $x_1 + x_2 = -1$ and $x_1 \leq 0$, $x_2 \geq 0$: Since $x_2 \geq 0$, $x_1 = -1 - x_2 \leq 0$ implies $x_2 \geq -1 - 0 = -1$ which is true. But $x_2 \geq 0$ restricts $x_2$ to $[0, \infty)$. So points on line segment from $(-1,0)$ upwards. - Check if $(-1,0)$ feasible: - $-x_1 + 2x_2 = 1 \geq 2$ ✗ no - Check if $(-0.5, -0.5)$ feasible: Not in $x_2 \geq 0$. - So feasible vertices are: - $(0,1)$ - Intersection of $x_1 + x_2 = -1$ and $x_2 = 0$: $$x_1 + 0 = -1 \Rightarrow x_1 = -1$$ Check $x_1 - x_2 = -1$: $$-1 - 0 = -1 \leq -1$$ ✓ Check $-x_1 + 2x_2 = 1 \geq 2$ ✗ no - So only vertex in $S$ is $(0,1)$. 4. **Step 3: Feasible nondegenerate basic solution** - $(0,1)$ is feasible and satisfies 2 constraints with equality: - $-x_1 + 2x_2 = 2$ - $x_1 \leq 0$ (active at $x_1=0$) - $x_2 \geq 0$ (active at $x_2=1$ but not equality) - So $(0,1)$ is a feasible nondegenerate basic solution. 5. **Step 4: Extreme directions** - Extreme directions satisfy all constraints with inequalities replaced by $\leq 0$ or $\geq 0$ and lie in the recession cone. - The recession cone $D$ is: $$D = \{d \in \mathbb{R}^2 : -d_1 - d_2 \leq 0, -d_1 + 2d_2 \geq 0, d_1 - d_2 \leq 0, d_1 \leq 0, d_2 \geq 0\}$$ - Find extreme rays of $D$: - Try $d_1=0$, $d_2=1$: Check: $$-0 - 1 = -1 \leq 0$$ ✓ $$-0 + 2(1) = 2 \geq 0$$ ✓ $$0 - 1 = -1 \leq 0$$ ✓ $$0 \leq 0$$ ✓ $$1 \geq 0$$ ✓ So $d^{(1)} = (0,1)$ is an extreme direction. - Try $d_1 = -1$, $d_2 = 0$: Check: $$-(-1) - 0 = 1 \leq 0$$ ✗ no - Try $d_1 = -1$, $d_2 = -1$: $d_2$ must be $\geq 0$, so no. - Try $d_1 = -1$, $d_2 = 1$: Check: $$-(-1) - 1 = 0 \leq 0$$ ✓ $$-(-1) + 2(1) = 1 + 2 = 3 \geq 0$$ ✓ $$-1 - 1 = -2 \leq 0$$ ✓ $$-1 \leq 0$$ ✓ $$1 \geq 0$$ ✓ So $d^{(2)} = (-1,1)$ is an extreme direction. 6. **Step 5: Non-extreme directions** - Any positive linear combination of $d^{(1)}$ and $d^{(2)}$ is a non-extreme direction. 7. **Step 6: Solve problem (P) with $c_1 = -2$, $c_2 = -4$** - Objective: minimize $$Z = -2x_1 - 4x_2$$ - Since $x_1 \leq 0$ and $x_2 \geq 0$, and coefficients are negative, minimizing $Z$ means maximizing $x_1$ and $x_2$ in feasible region. - Check vertex $(0,1)$: $$Z = -2(0) - 4(1) = -4$$ - Check direction $d^{(1)} = (0,1)$: Moving along $d^{(1)}$ increases $x_2$ without bound, $Z$ decreases without bound. - So problem is unbounded below. 8. **Step 7: Values for $c_1$, $c_2$ for (a), (b), (c)** (a) Optimal solution at $x^* = (-3,2)$: - $x^*$ must be feasible: Check constraints: - $-(-3) - 2 = 3 - 2 = 1 \leq 1$ ✓ - $-(-3) + 2(2) = 3 + 4 = 7 \geq 2$ ✓ - $-3 - 2 = -5 \leq -1$ ✓ - $-3 \leq 0$ ✓ - $2 \geq 0$ ✓ - For $x^*$ to be optimal, gradient $c = (c_1, c_2)$ must satisfy: $$c^T (x - x^*) \geq 0 \quad \forall x \in S$$ - Equivalently, $c$ must be a normal vector to a supporting hyperplane at $x^*$. - Since $x^*$ is in interior or boundary, $c$ must satisfy: $$c_1 (x_1 - (-3)) + c_2 (x_2 - 2) \geq 0$$ - Choose $c_1, c_2$ such that $x^*$ minimizes $Z$. (b) Problem (P) impossible: - No feasible region $S$ or empty. - Since $S$ is nonempty, impossible if $c$ points opposite to feasible directions and no minimum. (c) Bounded edge of optimal solutions with $c_1 = -2$: - Find $c_2$ such that objective is constant along an edge. - Edge between $(0,1)$ and direction $d^{(2)} = (-1,1)$: Objective along edge: $$Z = -2 x_1 - c_2 x_2$$ - For edge to be optimal, gradient must be orthogonal to edge direction: $$c^T d^{(2)} = 0 \Rightarrow -2(-1) - c_2 (1) = 0 \Rightarrow 2 - c_2 = 0 \Rightarrow c_2 = 2$$ - Edge solutions: $$x = (0,1) + \lambda (-1,1), \lambda \geq 0$$ - Optimal value: $$Z = -2 x_1 - 2 x_2 = -2(0 - \lambda) - 2(1 + \lambda) = 2 \lambda - 2 - 2 \lambda = -2$$ - So all points on edge have $Z = -2$. --- **Final answers:** - Feasible nondegenerate basic solution: $(0,1)$. - Extreme directions: $(0,1)$ and $(-1,1)$. - Non-extreme directions: positive combinations of these two. - Problem (P) with $c_1 = -2$, $c_2 = -4$ is unbounded below. - For (a) $x^* = (-3,2)$ optimal, $c$ must satisfy supporting hyperplane conditions. - For (b) problem impossible if $S$ empty (not the case here). - For (c) with $c_1 = -2$, $c_2 = 2$, bounded edge of optimal solutions along $x = (0,1) + \lambda (-1,1)$ with optimal value $Z = -2$.