Homework 5

Due Nov 15 in class.

  1. Let Ax \le b be the m inequalities of a linear program in n variables and all entries of A,b be from -1, 0,1. What values of r, R can be supplied to the Ellipsoid algorithm so that when it terminates it either finds a feasible point or realizes that the feasible set must be lower dimensional or empty?
  2. Let B be a box with side lengths a_1,a_2,...,a_n. What is the volume of the largest ellipsoid that fits in the box and the volume of the smallest ellipsoid that contains the box?
  3. Show how to solve the problem of finding a minimum-cost arborescence in a directed graph in polynomial time (see HW4 for definition of min-cost arborescence).
  4. Given a polytope Ax \le b guaranteed to be full-dimensional, give a convex function defined over the polytope, whose minimum is unique and occurs at a strict interior point of the polytope. How can you efficiently minimize the function?
  5. A furniture plant produces 480 chairs, 400 tables and 230 cabinets every day; each of these products can be sold either natural or polished. The total number of furniture items that can be polished during a normal working day is 420; in addition, up to 250 products can be polished during overtime at a higher cost. The net profits are as follows:\begin{array}{c c c c} & Fresh & Polished (regular) & Polished (overtime)\\ Chairs & \$8 & \$14 & \$11\\ Tables & \$4 & \$12 & \$7\\ Cabinets & \$4 & \$13 & \$9\\ \end{array}Find the production schedule that maximizes the total net profit, and give a proof that it is the optimal one.
  6. Give a pivot rule for the Simplex algorithm which can lead to cycling and an example showing this.