MA3252 Linear and Network Optimization Homework 2, Semester 2, 2015/16. Due 3 March 2016, 12 noon (Drop in mailbox in level 3 of S17.) (Total marks is 10.) 1. Consider the region satisfying the constraints in Tutorial 3, Q4: 2x1 3x1 3x1 2x1 x1 + + 3x2 2x2 2x2 3x2 x2 6 6 12 3 0 0 (a) List the constraint(s) needed to be added so that i. the feasible region becomes bounded and ii. a point is a BFS of the new feasible region if and only if it is a BFS of the original feasible region. (b) For all the BFS of the new feasible region, indicate which are degenerate and which are nondegenerate. (c) Sketch the (new) feasible region, and mark on the sketch: i. A point A that is feasible and has rank 2. ii. A point B that is feasible and has rank 1. iii. A point C that is feasible and has rank 0. 2. Consider the problems (P1) min s.t. ( min(x1 , 2x2 )) x1 , x2 0 (P2) min t t x1 t 2x2 x1 , x2 0 (a) Is the mapping f : R2 R dened by f (x1 , x2 ) = min(x1 , 2x2 ) convex? (b) What are the objectives of (P1) and (P2)? 3. Consider an LP in standard form, where A Rmn , c Rn , b Rm . Suppose that the set of optimal solutions is bounded. Is it true that all optimal solutions have at most m nonzeros? If so, give a proof. If not give a counterexample. 4. Prove that the reduced costs corresponding to basic variables are all zero. In other words, prove that cB = (0, . . . , 0). 1