Operations Research I

Syllabus

• Shortest path problems; conservative weights; Dijkstra and Ford-type algorithms.
• Critical path method (CPM) for project scheduling.
• Assignment and transportation problems; Hungarian (Kuhn) method.
• Maximum flow algorithms; feasible flows and flow constraints.
• Systems of linear inequalities; Fourier–Motzkin elimination; basic and strong basic solutions; polyhedra construction.
• Farkas lemma; boundedness theorem; LP duality; optimality conditions.
• Simplex method (conceptual and algorithmic overview).
• Totally unimodular matrices and their role in network optimization/integer solutions.