1. Show that to every extremal point u of L there is a set of n linearly independent constraints that are tight for it.

2. Show that if there is no extremal solution of our set of constraints then we can add some new constraint xj = 0 and there will still be solutions. [Hint: consider a solution for which the maximal number of constraints is tight, and a segment containing it, and extend the segment to a line.]

Problem 2 The expression x+ (1-)y is called a conver (linear) combination of vectors x, y in R'' if 0 s 1 . This combination is nontrivial if 0