15 093 Recitation 4 Michael Frankovich and Shubham Gupta October 2 2009 1 BT Exercise 4 5 Consider a linear programming problem in standard form and assume the rows of A are linearly independent For each of the following statements provide either a proof or a counterexample a Let x be a basic feasible solution Suppose that for every basis corresponding to x the corresponding basic solution to the dual is infeasible Then the optimal cost must be strictly less than c x b The dual of the auxiliary problem in Phase I of the simplex method is always feasible c Let pi be the dual variable associated with the ith equality constraint in the primal Eliminating the ith primal constraint is equivalent to introducing the additional constraint pi 0 in the dual problem d If the unboundedness criterion in the primal simplex algorithm is satis ed then the dual problem is infeasible Solution a True If the optimal cost is c x then there is an optimal basis associated with the given basic feasible solution The corresponding dual basic solution is feasible and optimal b True The primal auxiliary problem is always feasible Furthermore its optimal objective value is bounded below by 0 So it has a nite optimum Hence so does the dual problem and so it must be feasible c True Let a i x bi be the ith primal equality constraint and recall that the dual constraints are of the form i pi ai ci Eliminating the ith primal equality constraint e ectively removes the term pi ai from the dual constraint and the term pi bi from the dual cost This is equivalent to setting pi to zero 1 d True The unboundedness criterion in the primal simplex algorithm is that the vector B 1 Aj is nonpositive for a negative reduced cost c j In this case the primal cost is Thus the dual problem must be infeasible 2 BT Exercise 4 21 Clark s Theorem Theorem Consider the following pair of linear programming problems P min c x s t Ax b x 0 p b p A c p 0 Suppose that at least one of these problems has a feasible solution Prove that the set of feasible solutions to at least one of the two problems is unbounded D max s t Proof Given that the primal and dual have essentially the same form we assume with out loss of generality that the primal feasible set is nonempty If the primal feasible set is unbounded then we are done So assume the primal feasible set is bounded We will show that the dual feasible set is unbounded Note that the primal must have a nite optimum since its feasible set is bounded therefore so must the dual In particular the dual feasible set is nonempty Consider the following primal dual pair P min s t D max s t e x Ax b x 0 p b p A e p 0 We have argued that there exists a dual feasible solution i e a p s t p A e and p 0 Note that p 0 We now note that if q is a feasible solution to the original dual problem then so is q p 0 This shows that the dual feasible set is unbounded 3 BT Exercise 4 25 This exercise shows that if we bring the dual problem into standard form and then apply the primal simplex method the resulting algorithm is not identical to the dual simplex method Consider the following standard form problem and its dual 2 P min x1 x2 s t x1 x2 x D max s t p1 p2 p1 p2 1 1 0 1 1 Here there is only one possible basis and the dual simplex method must terminate im mediately Show that if the dual problem is converted to standard form and the primal simplex method applied to it one or more changes of basis may be required Solution The dual problem in standard form is max p 1 p1 p2 p2 s t p 1 p1 s1 p2 p2 s2 p s 1 1 0 There are several basic feasible solutions to this problem with di erent objective values Thus if we start with a nonoptimal BFS then the primal simplex method will require at least one change of basis 3 MIT OpenCourseWare http ocw mit edu 15 093J 6 255J Optimization Methods Fall 2009 For information about citing these materials or our Terms of Use visit http ocw mit edu terms 1