Math 340 Assignment #3 Due Wednesday March 9, 2016 1. Consider an LP which has as its rst constraint x1 + x2 x3 x4 1. Assume that you know (based on other constraints) that x2 = 0. Show that the dual variable y1 associated with the rst constraint is zero. 2. Consider the following LP: max c1 x 1 (10 + d1 )x1 (10 + d2 )x1 (10 + d3 )x1 (10 + d4 )x1 (10 + d5 )x1 +7x2 +4.5x2 +4x2 +3x2 +2x2 +x2 +7x3 +1.2x3 +1x3 +3x3 +4x3 +5x3 +11.1x4 +9x4 +8.2x4 +3x4 +x4 +x4 100 100 100 100 100 x1 , x2 , x3 , x4 0 where d1 d2 d3 d4 d5 are the rst 5 digits of your student number. a) Graph (sketch) the optimal value of the objective function as a function of c1 for all c1 (, ). Use the LINDO package or any other software but provide a printout of at least one input and one output. Begin with c1 = 0 and use ranging to determine an interval for c1 for which you know the answer. Ranging gives you the interval in which the optimal basis B is unchanged and the value for x1 in the optimal solution gives the slope (Why?). Now choose a c1 outside this interval and repeat. Continue until you know the optimal values for all possible c1 . You might need as many as nine intervals or as few as two intervals depending on your student number. b) Consider the optimal value of the objective function as a function of the value c1 , say f (c1 ). Show that f (c1 ) is a concave upwards function. 3. (from an old exam) If you are given an optimal primal solution x to an LP and you wish to deduce an optimal dual solution y , then you might try to determine y using (1) Complementary Slackness of y with x . (2) y satises constraints (including positivity constraints if any) in dual, i.e. y is a feasible solution of the dual.. Many of our examples in class and quizzes yielded unique optimal y but in general there may be many optimal dual solutions. Are all y satisfying (1),(2) optimal to the dual? Is every optimal dual solution determined as a solution to (1),(2)? Explain. 4. Let A be an m n matrix with A 0 and each column of A has a non-zero positive entry. Let b 0. Then show that the LP max c x Ax b x0 always has an optimal solution. 5. a) Show there is an x 0 with Ax < 0 if and only if there is an x 0 with Ax 1. Note: we use the denition (x1 , x2 , . . . , xn ) < (y1 , y2 , . . . , yn ) if and only if x1 < y1 , x2 < y2 , . . . and xn < yn . This is the standard notation in matrix theory for matrix or vector inequalities. This may be contrary to your expectations. Mathematically speaking, the symbol > would generally mean and = but this is not true for matrices or vectors. A vector x might satisfy x 0 and also x = 0 and yet still have some 0 entries. Such a vector x with 0 entries has x >0. b) Let A be an m n matrix. Prove that either: i) there exists an x 0 with Ax < 0 or ii) there exists y 0 with AT y 0 and y = 0 but not both. Hint: Extend the idea in a) and use it in setting up a primal dual pair