Convex set of feasible solutions of $AX=b, X\ge0$ is a convex polyhedron, then which of the following statements is true?

Question

Accepted Answer

The problem at hand involves a convex set of feasible solutions defined by the linear system $AX = b$ with the constraint $X \ge 0$. This set forms a convex polyhedron. The task is to determine which statement about the extreme points of this polyhedron is true.

### Explanation for Option 2:

**Option 2: At least one of the extreme points gives an optimal solution.**

This statement is true due to the fundamental properties of linear programming. In linear programming, if there exists an optimal solution, it will occur at an extreme point (or vertex) of the feasible region, which is a convex polyhedron. This is because the objective function, being linear, will achieve its maximum or minimum value at one or more of these vertices. Therefore, at least one of the extreme points will provide an optimal solution, making Option 2 the correct choice.

### Explanation for why other options are incorrect:

**Option 1: All extreme points give optimal solution.**

This statement is incorrect because it is not necessary for all extreme points to be optimal. In fact, typically only a subset of the extreme points will be optimal, depending on the orientation of the objective function relative to the feasible region. The objective function will generally have a unique direction, and only those extreme points that lie in the direction of optimization will be optimal.

**Option 3: Exactly one extreme point gives an optimal solution.**

This statement is incorrect because it is possible for multiple extreme points to yield the same optimal value, especially in cases where the objective function is parallel to a face of the polyhedron. In such scenarios, any point along the edge of that face, including multiple extreme points, can be optimal.

**Option 4: No extreme point gives an optimal solution.**

This statement is incorrect because, as previously mentioned, if an optimal solution exists, it must occur at an extreme point of the feasible region. The nature of linear programming ensures that the optimal solution will be found at one or more of these vertices.

In conclusion, Option 2 is the correct answer because it accurately reflects the property of linear programming that guarantees at least one extreme point will provide an optimal solution.