Classes - Operations Research Models and Methods

Instruction

Network Flows

Resources

Syllabus

	Network Flow Programming
	Syllabus - Network Flow Programming Class

*Required Texts*	Operations Research Models and Methods, Paul A. Jensen and Jonathan F. Bard, John Wiley Inc., 2003
	Network Flow Programming by Paul A. Jensen, Printed by the University Coop Custom Publishing, Summer 2002
*Computer Programs*	Access to Microsoft Excel version 97 or later for Windows or Mac OS.
*Syllabus*	Situations arising from the fields of transportation, water resources, manufacturing and many others give rise to network flow models. A flow network is a collection of nodes and arcs. Each arc passes from one node to another and carries a commodity called flow. A requirement is that flow be conserved at each node. The optimization problem is to find the flow in each arc that minimizes the total cost of the flow in the network. This course has three aspects: modeling real problems as networks, the theory associated with network optimization, and algorithms implementing the theory. The course covers the broad range of network flow problems, but stresses the pure and generalized, single commodity, minimum cost network flow problem.
Exams	There are three exams including the final exam. All exams have equal weight in the exam average.
Class Contribution	Each student should prepare a web site or give a verbal presentation of some topic of interest to this class.

Schedule

The references to MMOR are from Models and Methods of Operations Research. The references to the Lecture Notes are to notes supplied by Paul Jensen. The leaf images are linked to pages in this site or to pdf files for supplements.

Lect	Date	Topic	Read MMOR	Lecture Notes	HW	Link
Network Flow Programming Models
1		Introduction and Network Models	5.1	1-5
		Terminology
2		Modeling Examples	5.2	6-12
		Distribution Example
		Special Cases
		Other Examples
3		Optimization Add-ins for Excel
		General Discussion of Add-ins
		Math Programming Add-in
		Network Models
		Transportation Model
		Network Solver Add-in
		Excel Files (Network Models)
		Excel Demo (Math Programming)
4		Nonlinear Costs/Economic Model		13-18	HW 1
5		Side Constraints		19-22
6		Integer Variables		23-29	HW 2
7		Distance Problems		31-33
8		Nonlinear Problems			HW 3
9		Modeling Exercises
10		Modeling Exercises
11		Exam
Solution Methods for Specialized Problems
12		The Transportation Problem	6.1	34-36
		Teach Transportation Add-in
		Transportation Demo
13		MST and SPT Algorithms	6.2	37-48
		MST and SPT Demonstrations
14		Maximum Flow Problem	6.3	49-57	HW 4
15		Primal and Dual Problems		58-62
Primal Simplex Methods for Network Problems
16		LP and Network Flows		63-68	HW 5
17		Basic Solutions for the Pure Problem	6.4	69-72
18		The Primal Simplex for the Pure Problem		73-78	HW 6
19		Simplex for Upper Bounded Problems		79-86
		Teach Networks Add-in
		Network Simplex Demo
20		The Shortest Path and Maximum Flow Problems		87-88	HW 7
21		Computational Implementation		89-94
22		Review
23		Exam
The Generalized Ñetwork Problem
24		The Basis for the Generalized Problem	C.1	95-96	HW 8
25		Finding the Primal and Dual Solutions	C.2	97-100
26		Finding the arcs to enter and Leave the Basis	C.3	101-109	HW 9
27		Networks with Upper Bounds	138-140	110-122
		Teach Network Add-in for Generalized Problems
28		Review			HW 10
29		Review
		Final Exam