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 1 Solution 1 True The set P lies in an a ne subspace de ned 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 De nition Consider a polyhedron P de ned 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 satis es all of the constraints we say that it is a basic feasible solution 4 Degeneracy De nition 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 De nition 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 2 MIT OpenCourseWare http ocw mit edu 15 093J 6 255J Optimization Methods Fall 2009 For information about citing these materials or our Terms of Use visit http ocw mit edu terms