15.093J Recitation 4 Notes

15.093 - Recitation 4 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 satisfied, 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 finite 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 effectively 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 finite 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 different objective values. Thus if we start with a nonoptimal BFS, then the primal simplex method will require at least one change of basis. 3