DEPARTMENT OF MATHEMATICS, UNIVERSITY OF HONG KONG
MATH3903 Network Models in Operations Research
Second Semester: Jan 20, 2003 - May 10, 2003 (13 Weeks)
(Tue 9.30am, Tue 10.40, Thu 9.30am)
Course Instructor: Dr. S.C.K.Chu (Room 427, Run Run Shaw Bldg)
Office Hours: Wed 9.00-12.00noon
Course Demonstrator: Miss M.C. So (Room 704, Knowles Bldg)
Office Hours: Tue 12.30- 1.30pm; Thu 12.30- 1.30pm
_________________________________________________________________
Dates of RECITATION CLASSES and ASSIGNMENT due dates
Recitation classes Assignment due dates
Asg# (Thursday 9.30am) (Monday before)
1. Feb 20, 2003 Feb 17, 2003
2. Mar 06, 2003 Mar 03, 2003
READING WEEK: Mar 17 - Mar 22, 2003
3. Mar 27, 2003 Mar 24, 2003
CLASS TEST: Tuesday, Apr 01, 2003
** Re-scheduled to Tue, Apr 29. 2003
4. Apr 17, 2003 Apr 14, 2003
5. May 06, 2003(Tue) May 02, 2003(Fri)
Dates of TUTORIAL CLASSES with in-class exercises (Thu 9.30am)
(i) Jan 30; (ii) Feb 27; (iii) Mar 13; (iv) Apr 10; (v) Apr 24
_________________________________________________________________
TOPICS
o Notions of algorithms on graphs and networks
o Spanning trees
o Model and algorithm of transportation problem
o Bipartite matchings
o Model and algorithm of assignment problem
o Shortest paths
o Maximum flows and minimum cuts: theory and algorithm
o Minimum cost flows: theory and algorithm
o Project scheduling (applications - only if time permits)
REFERENCES
R.K.Ahuja, T.L.Magnanti and J.L.Orlin, "Network Flows: Theory
Algorithms, and Applications" 1993
M.S.Bazaraa, J.J.Jarvis and H.D.Sherali, "Linear Programming
and Network Flows" (2/e) 1990
H.A.Taha, "Operations Research: an Introduction" (5/e) 1992
Supplemented by Lecture Notes distributed in class
ASSESSMENT
Final 60% ; Test 20% ; Course Work (Assignments+Tutorials) 20%