Week 12 and 13

We finished the material on the MCF, minimum cost network flow problem. Explaining how the simplex algorithm simplifies, and we get bases that correspond to spanning trees. We saw how we computed efficiently corresponding primal (x) and dual (y,z) variables, using a leaf elimination order in the tree. On 24 March I presented special cases of MCF, and the integrality theorem; assignment problem, transportation problem, maximum flow problem. This was not very detailed. Some details on efficiency in the simplex algorithm were skipped (but they are in the notes; not very important). Have a nice Easter holiday later!