MS E 310 Linear Programming Homework 2 2013 HOMEWORK ASSIGNMENT 2 DUE OCTOBER 18 Reading Chapters 3 4 of L Y Introduction to Linear and Nonlinear Programming 1 Farkas lemma can be used to derive many other named theorems of the alternative This problem concerns a few of these pairs of systems Using Farkas s lemma prove each of the following results a Gordan s Theorem Exactly one of the following systems has a solution i Ax 0 ii yT A 0 y 0 y 6 0 b Stiemke s Theorem Exactly one of the following systems has a solution i Ax 0 Ax 6 0 ii yT A 0 y 0 c Gale s Theorem Exactly one of the following systems has a solution i Ax b ii y A 0 yT b 0 T y 0 2 Given that the dual of a linear program minimize cT x subject to Ax b x 0 in standard form is maximize yT b subject to yT A cT y free develop an appropriate dual for each of the following LPs a maximize cT x subject to Ax b x 0 b minimize cT x subject to Ax b x 0 c minimize cT x subject to Ax b A x b x 0 3 Consider the auction problem in Lecture note 4 The LP pricing problem has an objective T x z where the scalar z max Ax is the maximum number of contracts among all states recall that Ax Rm is a vector representing the number of contracts in each state Thus z represents the worstcase payback amount Now assuming that the auction organizer knows the discrete m probability distribution say v R for each state to win Then the expected payback amount would be n X vi Ax i vT Ax i 1 Develop an LP model to decide the contract award vector x and to price each state using the expected payback rather than the worst case payback that is using the objective function T x vT Ax in the LP setting How to solve the problem faster Moreover explain the price properties using duality and or complementarity 4 Strict Complementarity Theorem Read the proof of the strict complementarity theorem for the LP standard form in Lecture note 3 2 Consider the LP problem LP maximize cT x nj 1 cj xj Pn subject to j 1 aj xj Ax b 0 x e P where data A Rm n aj Rm c Rn b Rm and e is the vector of all ones and variables x Rn You may interpret this is a linear program to sell the items of inventory b to n customers such that the revenue is maximized Suppose the problem is feasible and bounded 1 Write down the dual of the problem What are the interpretations of the dual price vector associated with the constraints Ax b and the dual price vector associated with the constraints x e 2 What properties does a strictly complementary solution have for this linear program pair 3 Suppose the linear program pair has a strictly complementary primal solution x such that x j 0 or x j 1 for all j and let y be a strictly complementary dual price vector associated with the constraints Ax b Now consider a on line linear program where customer cj aj comes sequentially and the seller have to make a decision xj 0 or xj 1 as soon as the customer arrives Prove that the following mechanism or decision rule given y being known is optimal If cj aTj y then set xj 1 otherwise set xj 0 5 Consider a system of m linear equations in n nonnegative variables say Ax b x 0 Assume the right hand side vector b is nonnegative Now consider the related linear program minimize eT y subject to Ax Iy b x 0 y 0 where e is the m vector of all ones and I is the m m identity matrix This linear program is called a Phase One Problem a Write the dual of the Phase One Problem b Show that the Phase One Problem always has a basic feasible solution 3 c Using theorems proved in class show that the Phase One Problem always has an optimal solution d Write the complementary slackness conditions for the Phase One Problem e Prove that x Ax b x 0 6 if and only if the optimal value of the objective function in the corresponding Phase One Problem is zero 6 Exercise 4 8 7 of of L Y 7 Exercise 4 8 8 of of L Y 8 Exercise 4 8 10 of of L Y 9 Let A be an m by n matrix and let b be a vector in Rm We consider the problem of minimizing kAx bk over all xinRn Let v be the value of the optimal cost a Let p be any vector in Rm that satisfies kpk1 that bT p v Pm i 1 pi 1 and AT p 0 Show b In order to obtain the best possible lower bound of the form considered in part a we form the linear programming problem bT p maximize subject to AT p 0 kpk1 1 Show that the optimal cost on this problem is equal to v 4