SYLLABUS - MATH 4593/5593: Linear Programming

Fall 1999

 

Professor: Weldon A. Lodwick

Office: CU-Denver Building, Room 622

Telephone: 556-8462 (office - voice mail), 556-8442 (secretary)

E-Mail: weldon.lodwick@cudenver.edu

Web Site: http://www-math.cudenver.edu/~wlodwick

Text:       Linear and Nonlinear Programming by Stephen G. Nash and Ariela Sofer, McGraw-Hill, 1996.

 

Office Hours:                M/W        2:50 PM -    3:50 PM

                                Tu                11:20 AM - 12:20 PM

If you cannot make these hours, please make an appointment to see me at another time.

 

Students with Disabilities: If you have a disability that requires accommodation in this course, please see me as soon as possible.  I am happy to make appropriate accommodations, provided timely notice is received.

 

Prerequisites: Math 3191 and Math 4320 or consent of the instructor.

 

Below is the proposed outline.  The weeks listed are tentative and indicate my best estimate as to the pace of the class.

 

PROPOSED COURSE OUTLINE

Week                                            Topic                                                                    Readings

1/2                                           Introduction                                                         Sections 1.1-1.3, 2.1-2.3 & Chapters 1 - 3 

3/4                                           Geometry of Linear Programming                                         Chapter 4

5/6                                           The Simplex Method                                                   Chapter 5

7/8                                           Duality and Sensitivity                                                     Chapter 6

9/10                                         Enhancements of the Simplex Method                   Chapter 7

11/12                                       Network Problems                                                                Chapter 8

12/13                                       Computational Complexity of Linear Programming                Chapter 9, readings and handouts

14/15                                       A selection of the following: applications,                         Notes, readings and handouts

                                                modeling uncertainty, more interior point theory

                                                                                                                                               

 

MY APPROACH TO TEACHING

I believe that teaching is a process that involves an active partnership.  My role is that of a guide to your learning.  Therefore, I am responsible to open the way, to encourage, and to nudge you toward your own learning.  I will help guide you toward this learning by providing mathematics for you to experience.  It is my aim to communicate mathematics in a way that is supportive and nurturing of your efforts. Your role is to find a way to experience and articulate the mathematics that is presented and that you encounter.  I believe that it is your responsibility to let me know when you find yourself not understanding mathematical concepts that are presented in class.  Once you make this known, it is our responsibility to work on trying to attain clarity.  I will try to be as proactive as possible.  I believe that results on examinations and assignments give us the opportunity to clearly see where the areas of mathematical understanding are and what areas need more attention.

 

OUTCOMES

By the end of the semester you should be able to read, understand and apply linear programming theory associated with the topics covered in the semester to correctly solve associated problems at the level of our textbook.  Secondly, given a problem for which linear programming can be used, you should be able to translate the description of the problem into a correct linear programming model, choose and obtain the correct solution(s).  Lastly, by the end of the semester, you should be able to judge for yourself, the veracity of statements made in linear programming texts and articles that are at beginning graduate level. 

 

EVALUATION

There are three evaluative criteria: (i) project (40% of your grade), (ii) assigned problems (10% of your grade) and (iii) exams: in-class midterm (20% of your grade) and an in-class comprehensive final (30% of your grade).  Evaluation is based on a point system so that it is very important that you turn in your projects, assignments and complete exams as thoroughly as possible rather than taking a zero score.

 

EXAMINATION: The in-class midterm will be given on October 18th and consists of the material covered between the first day and October 11th.  As best as I can determine now, it will cover chapters 1-6.  The final exam will be comprehensive.  We will have to arrange a 2 hours block of time, place and date.  I would like to arrange to give the final on December 13th from 5:30-7:30pm in one of the seminar rooms of the math department. 

 

PROJECT: A project can be done alone or in a group.  You might think of your project as an exploration for a Masters presentation or Ph.D. thesis.  There are three steps to a project.  Firstly, identify the problem.  Secondly, develop a linear programming model associated with the problem.  Thirdly, solve the problem.  To solve the problem, you may use GAMS, MODLER/ANALYZE (Dr. Greenberg's system), AMPL (AT&T Bell Labs), MINOS (Stanford University), MATLAB Optimization Toolbox, or any system you pull from public domain sources.  I have a MATLAB simplex system you can use.

 

Project requirements:

1. Proposal

a. Description of the project

b. Division of labor

2. Annotated bibliography; that is, an annotated literature review

3. Written report of the results (75% of the grade)

4. In-class presentation of the results (25% of the grade)

 

Between August 25th and September 22nd, please schedule a 15 minute meeting with me to discuss your ideas for a project.  If you are thinking of doing a project with one or more persons, our meeting will be a group meeting.  I will provide more detailed instructions associated with your formal written project proposal, annotated bibliography, project write-up, and project presentation.  The earlier you schedule your meeting the sooner you can get started.

 

Note: If you wish, you may do a purely theoretical project such as doing a detailed research paper on sensitivity analysis or interior point methods.  Moreover, if your interest is more toward computational methods (algorithms), you may wish to develop and test an interior point or a fuzzy linear programming system.  In any case, you must meet with me to discuss what you wish to do for your project and then write up a proposal.

 

POINT DISTRIBUTION:

Project proposal                   September 27th   

Problem sets           50            Text and other written problems due throughout the semester

Midterm                 100                October 18th  

Annotated bibliography                 November 1st  

Final                       150                December 13th   

Project                    150                November 26th   

Presentation outline                December 1st   

Presentation            50            Week of December 6th   (roughly 30 minutes for each presentation)

----

Total                       500 points

 

The following distribution of grades is guaranteed.

                A+ 97-100%, A 93-96.9%, A- 90-92.9%

              B+ 87-89.9%, B 83-86.9%, B- 80-82.9%

              C+ 77-79.9%, C 73-76.9%, C- 70-72.9%

              D+ 67-69.9%, D 63-66.9%, D- 60-62.9%

 

Graduate and undergraduate expectations: What is expected of graduates and undergraduates will be differentiated on examinations (there will be two different exams), assigned problems, and on the project.  These differences will be made explicit in the project instructions, assigned problem instructions and with the two different exams that will be handed out.