CO 250 Assignment 7 - Winter 2015 Due: Friday, March 13th 2015, by 4pm (sharp) Note: Submit your completed assignment to the following dropboxes outside MC 4066: Section 1 [L. Sanit`] a TTh 11:30am-12:50pm Section 2 [J. Knemann] o MWF 2:30-3:20pm Box 6, Slots 6 (A-J), 7 (K-S), 8 (T-Z) Box 7, Slots 9 (A-J), 10 (K-S), 11 (T-Z) Assignment policy: While it is acceptable to discuss the course material and the assignments, you are expected to do the assignments on your own. For example, copying or paraphrasing a solution from some fellow student or old solutions from previous oerings of related courses qualies as cheating and we will instruct the TAs to actively look for suspicious similarities and evidence of academic oenses when grading. All students found to be cheating will automatically be given a mark of 0 on the assignment (where that grade will not be ignored as the lowest assignment). In addition, there will be a 5/100 penalty to their nal mark, as well as all academic oenses will be reported to the Associate Dean for Undergraduate Studies and recorded in the student's le (this may lead to further, more severe consequences). If you have any complaints about the marking of assignments, then you should rst check your solutions against the posted solutions. After that if you see any marking error, then you should return your assignment paper to the instructor of your section within one week and with written notes on all the marking errors; please write the notes on a new sheet and attach it to your assignment paper. Please USE THE COVER SHEET that is available at the end of the assignment. It is imperative that you indicate your full name and student ID (as we have many students with the same last name). Problem 1: Simplex Geometry Consider the following LP: (P) max s.t. (1, 1)x 2 2 1 x 16 1 4 x1 0 x2 0 (a) Covert (P) in SEF (note that x2 0), and solve it via the Simplex Algorithm (start with the basis formed by the slack variables). (b) Give a diagram showing the set of feasible solutions of the LP (P), and show the order that the Simplex algorithm visits its extreme points. Problem 2: Convexity I (a) For each of the following sets corresponding to the shaded gures, indicate (i) whether it is convex or not, and (ii) if it is convex indicate which of its points are extreme points. 1 (1) (2) (3) (4) (b) Let P = {x Rn : Ax b} be a polyhedron, and let x1 , x2 be two distinct extreme points of P . Prove or disprove: the set P \\ {x Rn : x = x1 + (1 )x2 , 0.2 0.8} is convex. (c) Let r > 0. Prove that the following set is convex: {x R2 : x2 + x2 r2 } 1 2 Hint: use the Cauchy-Schwartz inequality stating that every pair of vectors x, y satises xT y xT x y T y Problem 3: Convexity II Let A Rn be a convex set. Let M be an n n matrix and dene, B := {M x : x A} i.e. B is the set of all points in Rn that can be obtained by selecting a point x A and applying the transformation x M x. (a) Show that B is convex. (b) Suppose that M is invertible and consider z A, hence M z B. Show that z is an extreme point of A if and only if M z is an extreme point of B. 2 Problem 4: Polyhedra (a) Enumerate all the extreme points of (P ) := {x : Ax b} where 2 1 0 2 1 4 1 6 ,b = A= 1 0 5 1 1 0 0 0 Justify your answer. (b) Prove or disprove: Every non-empty polyhedron has at least one extreme point. Problem 5: Shortest Paths (a) Consider the following graph, where all edges have unit lengths. Find (by inspection) an s, t-path of length 5. Prove that the path you found is a shortest s, t-path. (b) Consider the following graph, where numbers indicate the edge lengths. Prove that P = {sa, ab, bd, dg, gt} is a shortest s, t-path. 3 CO 250 ASSIGNMENT 7 - COVER SHEET Surname: First Name: Signature: Id.#: Section#: Problem 1 Mark Awarded 2 3 4 5 Total 4