Question

Consider the standard form polyhedron P = x . Suppose that the matrix A has dimensions m x n and that its rows are linearly independent. For each one of the following statements, state whether it is true or false. If true, provide a proof, else, provide a counterexample.(a) If n = m + 1, then P has at most two basic feasible solutions.(b) The set of all optimal solutions is bounded.(c) At every optimal solution, no more than m variables can be positive. (d) If there is more than one optimal solution, then there are uncountably many optimal solutions. (e) If there are several optimal solutions, then there exist at least two basic feasible solutions that are optimal (f) Consider the problem of minimizing max{c'x, d'x} over the set P. If this problem has an optimal solution, it must have an optimal solution which is an extreme point of P.

Answer 1

Answer: 1. True

2. False

3. False

4. True

5. False

6. False

Explanation:

Solution

1. True. The set P lies in an affine subspace defined by m = n − 1 linearly

independent constraints, that is, of dimension one. Hence, every solution

of Ax = b is of the form x0 + λx1, where x0 is an element of P and x1 is a

nonzero vector. This, P is contained in a line and cannot have more than

two extreme points. (If it had three, the one “in the middle” would be a

convex combination of the other two, hence not an extreme point).

2. False. Consider minimizing 0, subject to x ≥ 0. The optimal solution set

[0, ∞) is unbounded.

3. False. Consider a standard form problem with c = 0. Then, any feasible

x is optimal, no matter how many positive components it has.

4. True. If x and y are optimal, so is any convex combination of them.

5. False. Consider the problem of minimizing x2 subject to (x1, x2) ≥ (0, 0)

and x2 = 0. Then the set of all optimal solutions is the set x1 ≥ 0.

There are several optimal solutions, but only one optimal BFS.

6. False. Consider the problem of minimizing x1−0.5 = max{x1−0.5x3, −x1+

0.5x3} subject to x1+x2 = 1, x3 = 1 and (x

|

1, x2, x3

|

) ≥ (0, 0, 0). Its unique

optimal solution is (x1, x2, x3) = (0.5, 0.5, 1) which is not a BFS.