Lecture 24: Linear Programming and Two-Person Games

Om kurset

Description This lecture focuses on several topics that are specific parts of optimization. These include linear programming (LP), the max-flow min-cut theorem, two-person zero-sum games, and duality. Summary Linear program: Minimize cost subject to \(Ax = b\) and \(x\geq 0\) Inequalities make the problem piecewise linear. Simplex method reduces cost from corner point to corner point. Dual linear program is a maximization: Max = Min! Game: \(X\) chooses rows of payoff matrix, \(Y\) chooses columns. Related sections in textbook: VI.2–VI.3 Instructor: Prof. Gilbert Strang