Chapter 9 Extra Topics
This is a chapter on random applications of linear optimization that are not generally a standard part of the undergraduate course, but are fun and nifty extensions. There is a good chance that anyone taking or teaching a class on linear optimization will not be able to cover these topics. However, for a class who finds the time, as independent reading for an ambitious or curious student, or fodder for projects or exploration, these can provide some insight into the vast array of problems to which the theory from this course may be applied.
In Section 9.1, we discuss graph matchings and coverings using linear optimization. In Section 9.2 linear optimization is used to solve sudoku and sudoku like puzzles. In Section 9.3 scheduling problems are modled as and solved as linear optimization problems. Finally, Section 9.4 provides al alternative approach to the proof of the Strong Duality Theorem Theorem 4.2.4.
