Mathematics BSc
Course description
2013.

Operations research 1
Hours
lect+pc
Credits
lect+pc
Assessment Specialization Course code
lect/pc
Semester Status
2 + 2 2 + 3 exam +
term grade
pure math. mm1c1op3m
mm1c2op3m
3 compulsory
applied math. mm1c1op3a
mm1c2op3a
3 compulsory
Strong Weak Prerequisites
Practice class
Strong:
Strong:
Algebra2L (mm1c1al2)
Lecture
Weak:
practice class
Syllabus
  • Shortest paths, conservative weightings (algorithms of Dijkstra and Bellman-Ford), Critical path method. Assignment and transportation problems, Kuhn's Hungarian method. Algorithms for maximum flows and feasible circulations.
  • The min-cost flow algorithm of Ford and Fulkerson.
  • Linear iqnequality systems and the Fourier-Motzkin elimination. Basic and strong basic solutions. Polyhedra and polytopes, a theorem of Minkowski and Weyl. Farkas lemma, optimality criteria, duality theorem.
  • The simplex method for feasibility. Totally unimodular matrices and their applications in network optimization to derive fundamental theorems of Gallai, Hoffman, and Egervary.