15.093 - Recitation 2 Michael Frankovich and Shubham Gupta September 21, 2009 1 Linear Algebra Review Read Section 1.5 of BT. Important concepts: • linear independence of vectors • subspace, basis, dimension • the span of a collection of vectors • the rank of a matrix • nullspace, column space, row space 2 BT Exercise 2.10 Problem Consider the standard form polyhedron P = {x ∈ Rn|Ax = b, x ≥ 0}. Suppose that the matrix A has dimensions m × 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. 1. If n = m + 1, then P has at most two basic feasible solutions. 2. The set of all optimal solutions is bounded. 3. At every optimal solution, no more than m variables can be positive. 4. If there is more than one optimal solution, then there are uncountably many opti-mal solutions. 5. If there are several optimal solutions, then there exist at least two basic feasible solutions that are optimal. 6. 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 . 1Solution 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)|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 (x1, x2, x3) ≥ (0, 0, 0). Its unique optimal solution is (x1, x2, x3) = (0.5, 0.5, 1) which is not a BFS. 3 BFS Definition. Consider a polyhedron P defined by linear equality and inequality con-straints, and let x ∗ ∈ Rn . Then 1. The vector x ∗ is a basic solution if: • All equality constraints are active; • Out of the constraints that are active at x ∗ , there are n of them that are linearly independent. 2. If x ∗ is a basic solution that satisfies all of the constraints, we say that i t is a basic feasible solution. 4 Degeneracy Definition. A basic solution x ∈ Rn of a linear optimization problem is said to be degenerate if there are more than n constraints which are active at x. Definition. Consider the standard form polyhedron P = {x ∈ Rn|Ax = b, x ≥ 0} and let x be a basic solution. Let m be the number of rows of A. The vector x is a degenerate basic solution if more than n − m of the components of x are zero. 2MIT OpenCourseWarehttp://ocw.mit.edu 15.093J / 6.255J Optimization Methods Fall 2009 For information about citing these materials or our Terms of Use, visit: