Instructor:
Professor Michael P. Johnson

Operations research/management science (OR/MS) is an interdisciplinary field devoted to determining how individuals and organizations ("decisionmakers", or "DMs") can design and implement various policies, using limited resources, that are "best" by various criteria. OR/MS uses techniques from management, economics, finance, operations, mathematics and computer science and other fields to enable firms to deliver service more efficiently and more effectively.

In the public sector, OR/MS is uniquely positioned to help DMs solve problems with multiple stakeholders, multiple objectives, multiple alternative actions and policy restrictions on allowable actions. Whereas economics may provide insight to DMs regarding properties of certain given policies, and management information systems may assist micro-level implementation of given policies, OR/MS can help DMs determine exactly what policy to pursue and the estimated impacts associated with alternative policies.

With this course, you should be able to:

• Develop expertise in modeling novel, complex problems, primarily in the area of deterministic math optimization;
• Use algorithms, often via software, to solve a variety of problems;
• Understand the policy and organizational implications of OR/MS models for the public sector.

Meeting Times:

	Lectures: M-W 2:00 p.m. – 3:20 p.m. 1003 Hamburg Hall
	Discussion: F 3:30 p.m. – 4:50 p.m. 1003 Hamburg Hall

Texts:

Required

• Winston, Wayne L.1994. Operations Research: Applications and Algorithms, Third Ed. Belmont, Calif: Duxbury Press.
• Journal articles and text extracts, distributed in class.

Recommended

• Beasley, J.L. 1997. OR-Notes. World Wide Web, http://mscmga.ms.ic.ac.uk/jeb/or/contents.html.
• Cohon J.L. Multiobjective Programming and Planning. 1978. New York: Academic Press.
• Daskin, M.S. 1995. Network and Discrete Location: Models, Algorithms and Applications. New York: Wiley-Interscience (on reserve at Hunt library).
• Zvi Drezner (ed.). 1995. Facility Location: A Survey of Applications and Methods. New York: Springer-Verlag.
• Fitzsimmons, J.A. and M.J. Fitzsimmons. 1994. Service Management: Operations, Strategy and Information Technology, Second Ed. Boston: Irwin McGraw-Hill.
• Glover, F., D. Klingman and N.V. Phillips. 1992. Network Models in Optimization and Their Applications in Practice. 1992. New York: Wiley.
• Greenberg, H.J. 1996-7. Mathematical Programming Glossary. World Wide Web, http://www-math.cudenver.edu/~hgreenbe/glossary.html. (on reserve at Hunt library)
• Hillier, F.S. and G.J. Lieberman. 1995. Introduction to Operations Research, Sixth Edition. New York: McGraw-Hill.
• Optimization Technology Center of Northwestern University and Argonne National Laboratory. 1998. Linear Programming Frequently Asked Questions. World Wide Web, http://www.mcs.anl.gov/home/otc/Guide/faq/linear-programming-faq.html (on reserve at Hunt library).

Class announcements, questions or discussions relevant to the course will be posted to the Heinz school bulletin board academic.heinz.90-772, as well as this Web page. Students are encouraged to check the b-board frequently for updates, course questions of general interest and other communication.

Students who take this course should have experience in elementary management science with a spreadsheet emphasis, microeconomics, management information systems, statistics and public policy.

There will be approximately eight homework sets, two case studies, a midterm and a final exam. Excel’s Solver is preferred in homeworks and cases, though other platforms such as LINDO/LINGO are acceptable. Exams will be pencil-and-paper only.

Collaboration between students on problem sets and cases is acceptable and encouraged. At most two students may collaborate on problem sets; up to three students may collaborate on cases. Whenever collaboration occurs, please indicate which student is responsible for most of a given problem.

Professor Johnson’s administrative assistant is Ebony Graham, 8-8756. She will have copies of the course syllabus and recent readings. She will also have copies of graded homeworks, cases and exams that have not been picked up.

Course grades will be computed based on the following formula:

The lowest homework grade for each student will be dropped at the end of the semester. Requests for regrades of any course material should be made to the TA. When doing a regrade, the entire homework, exam or case can be examined, and the new grade could be higher or lower than the original grade. All regrades are final.

Students are requested to make appointments for meetings with the professor outside normal office hours.

Topics

	Values, real-world OR modeling and implementation
	Introduction to linear algebra
	Linear programming
	LP duality and sensitivity analysis
	Network LP modeling
	Integer programming
	Location models
	Service operations management
	Multi-objective programming

There will be two case studies this semester. These will be based on real-life OR applications and are intended to develop group analysis and problem-solving skills. Case materials will be distributed one lecture in advance of the actual case discussion; case writeups will be due about two lectures after the case discussion. Class participation will be crucial for the case discussion to result in a learning experience. Students with real-world experience that might be suitable for a case are welcome to share these experiences with the professor.

1. Monday, January 11: Course Introduction

Topics:

• Student introductions
• Review of syllabus

2. Wednesday, January 13: Values and Implementation of OR/MS

Topics:

• Implementing OR/MS
• Public-sector versus private-sector OR/MS
• Use and misuse; understanding and misunderstanding of models
• Value-oriented thinking

Readings:

• Winston, Chapter 1.
• Banks, J. and F. A. Rossini. 1987. "Management Science Failures in the Public Sector", in M. Holzer and A. Halachmi (eds.). Public Productivity Review, no. 42. San Francisco: Jossey-Bass.
• Keeney, R.L. 1993. Creativity in MS/OR: Value-Focused Thinking-Creativity Directed Toward Decision Making. Interfaces 23:3; p. 62-67.
• Liebman, J.C. 1976. Some Simple-Minded Observations on the Role of Optimization in Public Systems Decision-Making. Interfaces 6:4; 102 – 108.

Problem Set #1 (due Wednesday, January 20):

• OR problem identification and description

3. Friday, January 15: Discussion Session

4. Monday, January 18: Martin Luther King, Jr. birthday (class excused)

5. Wednesday, January 20: Linear Algebra

Topics:

• Introduction to matrices
• Formulating and solving systems of linear equations
• Linear independence and dependence
• Matrix inversion

Readings:

• Winston, Sections 2.1 – 2.5.

	Problem Set #1 due
	Problem Set #2 (due Wednesday, January 27):

• Matrix manipulation

6. Friday, January 22: Discussion Session

7. Monday, January 25: Linear Programming Introduction

Topics:

• Economic motivation
• Basic Formulations
• LP Characteristics

Readings:

• Winston Sections 3.1 - 3.4

8. Wednesday, January 27: Linear Programming Formulations

Topics:

• Value-based formulation
• Formulation techniques
• Application Areas

Readings:

• Winston, Sections 3.5 - 3.6, 4.1.
• Keeney, R.L. 1988. Structuring Objectives for Problems of Public Interest. Operations Research 36:3; 396 - 405.
• Keeney, R.L. 1994. Using Values in Operations Research. Operations Research 42:5; p. 793-813.

	Problem set #2 due
	Problem Set #3 (due Friday, February 5):

• LP Formulations
• LP solution

9. Friday, January 29: Discussion Session

10. Monday, February 1: Linear Programming Formulations and Solution Methods

Topics:

• Production planning
• Fractional programming and Data Envelopment Analysis
• Transportation problem
• LP solution algorithms and software to solve linear programs

Readings:

• Winston, Sections 3.9 - 3.12, 4.2, 6.12 through top p. 313, 4.14.
• Lancaster, L. 1992. The Evolution of the Diet Model in Managing Food Systems. Interfaces 22:5 p. 59-68.
• Sherman, H.D. and G. Ladino. 1995. Managing Bank Productivity Using Data Envelopment Analysis (DEA). Interfaces 25:2; p. 60 – 73.

11. Wednesday, February 3: Linear Programming Formulations

Topics:

• HIV/AIDS resource allocation
• Land use planning
• Public library circulation planning

Readings:

• Gleeson, M.E. and J.R. Ottensman. 1993. Using Data From Computerized Circulation and Cataloging Systems for Management Decision Making in Public Libraries. Journal of the American Society for Information Science 44(2): 94 - 100.

12. Friday, February 5: Discussion Section

Problem Set #3 due

13. Monday, February 8: Sensitivity Analysis

Topics:

• Shadow prices and right-hand side ranges
• Reduced costs and objective function coefficient ranges
• Sequences of parameter changes

Readings:

• Winston, Chapter 5, Section 6.4

Problem Set #4 (due Wednesday, February 17):

• Sensitivity analysis
• Formulation of dual LP

14. Wednesday, February 10: Sensitivity Analysis, Continued

Topics

• New activities
• Changing multiple parameters simultaneously
• Tradeoff curves
• Spider plots and Tornado diagrams

Readings

• Eisenbach, T.G. 1992. Spiderplots versus Tornado Diagrams for Sensitivity Analysis. Interfaces 22:6; p. 40-46.

15. Friday, February 12: Discussion Session

16. Monday, February 15: Duality Theory

Topics

• Dual definition
• Economic interpretations of dual
• Formulation of dual
• Link between duality and sensitivity analysis: shadow prices

Readings:

• Winston, Chapter 5, Sections 6.4 – 6.6, 6.8.

Case #1 presentation: for discussion Wednesday, February 17 and writeup Monday, February 22.

17. Wednesday, February 17: Case #1 discussion

Problem set #4 due

18. Friday, Februry 19: Network Washington (discussion session excused)

19. Monday, February 22: Duality Theory, Continued

Topics:

• Important duality theorems
• Complementary slackness
• Sensitivity/economic analysis for the transportation problem

Readings:

• Winston, 6.7 (omit proofs), 6.9, 6.10.
• Greenberg, H.J. 1993. How to Analyze the Results of Linear Programs-Part 2: Price Interpretation. Interfaces 23:5; p. 97-114.
• Rubin, D.S. and H.M. Wagner. 1990. Shadow Prices: Tips and Traps for Managers and Instructors. Interfaces 20:4; p. 150-157.

Case #1 writeup due

20. Wednesday, February 24: Mid-Term Examination

21. Friday, February 26: Discussion Session

Return of mid-term examinations, solution sets

22. Monday, March 1: University mid-semester break (class excused)

23. Wednesday, March 3: Network Flows

Topics:

• Nodes, arcs, flows
• Complete graphs, bipartite graphs, trees, paths
• Klingman’s netforms

Readings:

• Glover, Klingman and Phillips, pp. 21 – 48
• Winston, Section 8.1

24. Friday, March 5: Discussion Session

	Discussion of case #1 writeups
	Networks discussion

25. Monday, March 8: Network Flows, Continued

Topics:

• Assignment problem
• Transportation problem
• Transshipment problem
• Shortest path problem

Readings:

• Winston, Chapter 7 (except Section 7.3), Section 8.1

Problem Set #5: (due Wednesday, March 17):

• Network flows

26. Wednesday, March 10, Network Flows, Continued

Topics:

• Minimum spanning tree problem
• Maximum flow problems
• PERT/CPM
• Min-cost flow problem

Readings:

• Winston, Sections 8.2 – 8.6

27. Friday, March 12: Discussion Session

28. Monday, March 15: Network Flows, Continued

Topics:

• Network flows applications
• Network solution methods

Readings:

• Klingman, D., Phillips, N., Wirth, R. and W. Young. 1986. The Challenges and Success Factors in Implementing an Integrated Products Planning System for Citgo. Interfaces 16:3, p. 1 – 19.
• Shoepfle, O.B. and R.L. Church. 1991. A New Network Representation of a "Classic" School Districting Problem. Socio-Economic Planning Sciences 25:3, p. 189 – 197.

29. Wednesday, March 17: Integer Programming

Topics:

• Introduction to IP
• Formulation methods

Readings:

• Winston, 9.1 – 9.2

	Problem Set #5 due
	Problem Set #6: (due Wednesday, March 31):

• Integer programming
• Network flows

30. Friday, March 19: Discussion Session

31. Monday, March 22 – Friday, March 26: Spring Break (classes excused)

32. Monday, March 29: Integer Programming, Continued

Topics:

• Functions with N possible values
• Fixed-charge problems
• Piecewise-linear functions
• IP applications

Readings:

• Winston, p. 522 – 523, 526 - 529

33. Wednesday, March 31: Integer Programming, Continued

Topics:

• IP applications
• Solving IPs

Readings:

• Winston, 9.3 – 9.4
• Barnhart, C., Johnson, E.L., Nemhauser, G.L., Sigismondi, G. and P. Vance. 1993. Formulating a Mixed-Integer Programming Problem to Improve Solvability. Operations Research 41:6, p. 1013 – 1019.

Problem Set #6 due

34. Friday, April 2: Discussion Session

35. Monday, April 5: Location Models

Topics:

• Introduction
• Location on a plane

Readings:

• Daskin, p. 1 – 18
• Fitzsimmons and Fitzsimmons, Chapter 7.

Problem Set #7 (due Monday, April 19)

• Location on a plane
• Location on networks

36. Wednesay, April 7: Location Models, Continued

Topics

• Set Covering Problem and extensions

Reading:

• Drezner, Chapter 8.

37. Friday, April 9: Discussion Session

38. Monday, April 12: Location Models, Continued

Topics:

• Center and Median Problems

Readings:

• Daskin, p. 154 – 162, p. 198 – 203.

39. Wednesday, April 14: Location Models, Continued

Topics:

• Fixed Charge Facility Location Problems
• Obnoxious/Undesirable Facility Location Problems

Readings:

• Daskin, p. 247-250, 275-277.
• Kuby, Michael. 1987. Programming Models for Facility Dispersion: The p-Dispersion and Maxisum Dispersion Problems. Geographical Analysis 19: 315 - 329.
• Ratick, S. and A. White. 1988. A Risk-Sharing Model for Locating Noxious Facilities. Environment and Planning B 15: 165 - 179.

Case #2 presentation: for discussion Monday, April 19 and writeup Friday, April 23.

40. Friday, April 16: University Carnival (Discussion session excused)

41. Monday, April 19: Case Discussion

Problem Set #7 due

42. Wednesday, April 21: Service Operations Management

Topics:

• Definition and scope of service sector
• Facility layout

Readings:

• Fitzsimmons and Fitzsimmons, Chapters 2, 6

Problem Set #8 (due Wednesday, April 28)

• Service operations management

43. Friday, April 23: Discussion Session

44. Monday, April 26: Service Operations Management, Continued

Topics:

• Matching Supply and Demand

Reading:

• Fitzsimmons and Fitzsimmons, Chapter 13

45. Wednesday, April 28: Multi-Objective Programming

Topics:

• Multiobjective Programming
• Goal Programming

Readings:

• Winston, Sections 14.1, 14.4
• Cohon, Chapter 2.

Problem Set #8 due

46. Friday, April 30: Discussion Session

Final exam review

47. Monday, May 3 – Friday, May 7: Heinz School Final Exams

AMPL: A Mathematical Programming Language (when models are too complex for spreadsheets)

J.L. Beasley,  OR-Notes.

Harvey Greenberg, Mathematical Programming Glossary

Optimization Technology Center of Northwestern University and Argonne National Laboratory, Linear Programming Frequently Asked Questions.

Michael Trick's OR Home Page (everything you need to know about OR, maintained by a GSIA professor)

Institute for Operations Research and the Management Sciences (INFORMS) Home Page

INFORMS Practice Online Web Page.

INFORMS Practice Online Mailing List. (message body: subscribe pol).

Top of Page
Heinz School Home
CMU Home

Last modified 01/11/99