Introduction to Operations Research

(3 Credit Hours) · Undergraduate

Operations research is the science of decision making. The success of a decision is frequently quantified through achieving certain objectives (mathematically, maximizing an objective function) under constraints imposed on various resources. In this course we will focus on a fundamental yet widely applicable family of optimization problems known as linear programs. These have a linear objective function, and the constraints are linear equalities and inequalities. We will see how to formulate linear programs and interpret their solutions. We will study in detail the simplex method, which combines linear algebra and polyhedral geometry to efficiently solve linear programs, as well as the rich and surprising theory of duality, which swaps the roles of objectives and resources. We will apply these tools to find optimal strategies for two-player zero-sum games in game theory. Additional topics and applications include network flows and the max-flow min-cut theorem, integer programming and totally unimodular matrices, the transportation and assignment problems, stable matching algorithms, and additional topics at the discretion of the instructor.