Practice: The Four Terminal Outcomes

(a) Infeasible. Check feasibility first, from the constraints alone. With $x_1\le 2$ and $x_2\le 2$ we get $x_1+x_2\le 4$, which contradicts $x_1+x_2\ge 10$. No point satisfies all of them, so the program is infeasible. The objective was never used, and could not have changed the verdict.

(b) Unbounded. Feasibility: $(0,0)$ satisfies every constraint, so the region is nonempty. Unbounded directions: $(0,1)$ keeps you feasible indefinitely, since $x_1-x_2\le 1$ only becomes slacker as $x_2$ grows. Objective along that direction: $c=(0,1)$ gives . The objective improves without limit, so the program is unbounded.

(c) Multiple optima. Feasibility: $(0,0)$ works. Unboundedness: $x_1\le 8$ bounds one variable and $x_1+2x_2\le 10$ with $x_2\ge 0$ bounds the other, so the region is bounded and a finite optimum is guaranteed. No direction test needed. Uniqueness: the objective $3x_1+6x_2$ is exactly $3$ times the constraint left-hand side $x_1+2x_2$, so the objective is constant along that boundary. The contour comes to rest lying flat along it.

The optimal value is $3\times 10=30$, attained at every point of the edge from $(8,1)$ to $(0,5)$.

On the order. In (a) one check finished the problem. In (c) the boundedness observation removed the need for any direction test. Checking in order is not pedantry. It is what keeps each classification cheap.

Both conclusions are unsupported, and for the same underlying reason: the region is settled by the constraints, while three of the four outcomes also depend on the objective.

Model A. An unbounded region is necessary for an unbounded program but not sufficient. The region must continue without limit in a direction along which the objective improves. Minimising $x_1+x_2$ over $x_1-x_2\le 1$, $x_1,x_2\ge 0$ has optimal value $0$ at the origin despite an unbounded region. What decides it: find the directions $d$ in which the region continues, and compute $c^{\mathsf{T}}d$ for each. Model A is unbounded only if one of those is improving.

Model B. A bounded nonempty region guarantees that a finite optimum exists and is attained, that much is right. It does not give uniqueness. If the objective is parallel to one of the binding constraints, an entire edge of the hexagon is optimal. What decides it: check whether the objective's coefficients are proportional to those of the constraint that stops the contour, or equivalently whether any nonbasic variable has reduced cost zero at the optimal basis.

The claim about not needing the objectives. True for exactly one outcome, infeasibility, and neither model was classified as infeasible. For the other three the objective is part of the evidence, so the method as described cannot reach any of them.

What the analyst did have. Two correct region classifications, which is genuine progress and which makes the remaining checks cheap: model B needs no unboundedness test at all, and model A needs only the directions in which its region recedes.

(i) Unbounded. No positive component means no basic variable falls as the entering variable rises, so the step can be taken indefinitely while remaining feasible. Geometrically: the region continues without limit along that edge direction, and the objective improves along it. The contour never loses contact and there is no last position.

(ii) Multiple optima. A nonbasic variable with reduced cost exactly zero can enter the basis without changing the objective value. Moving along that edge reaches a different point of equal value. Geometrically: the contour has come to rest lying flat along an entire edge, because it is parallel to the constraint that stopped it. Note the word exactly. A reduced cost of $-0.0001$ is a different situation and would mean the basis is not optimal.

(iii) Not infeasible; something is wrong with the model or the solve. The origin satisfying every constraint is a feasibility certificate, and a certificate outranks a status line. Infeasibility is a property of the program, not of the algorithm that ran on it.

What to conclude for (iii). The model solved is not the model inspected. The usual causes are a transcription error in a constraint sign or bound, a variable bounded in the solver but not on paper, or a numerical tolerance issue on near-degenerate data. The productive response is to feed the origin to the solver as a starting point and ask why it is rejected, which localises the discrepancy immediately.

What this asks. Each report is one representation of an outcome, and the outcome is the property being named. A learner who can classify only from a sketch has learned the two-variable picture rather than the four cases, which is why the same competence is exercised here with no picture available at all.