Due Nov 15 in class.
- Let be the inequalities of a linear program in variables and all entries of be from . What values of 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?
- Let be a box with side lengths . What is the volume of the largest ellipsoid that fits in the box and the volume of the smallest ellipsoid that contains the box?
- 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).
- Given a polytope 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?
- 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:Find the production schedule that maximizes the total net profit, and give a proof that it is the optimal one.
- Give a pivot rule for the Simplex algorithm which can lead to cycling and an example showing this.