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%