Catalog Description

M 456 LINEAR PROGRAMMING (3-0-3)(S). Simplex algorithm, two-phase method, simplex algorithm for problems with bounded variables, duality theory, post-optimality analysis, network simplex method, and the transportation and assignment problems. PREREQ: M 301. Offered spring of even-numbered years, subject to sufficient demand.

Prerequisites

To understand M 456, a student needs a grasp of some of the basic ideas of linear algebra. In particular the student should be able to work with systems of linear equations, matrix manipulations, Gaussian elimination in terms of matrices, linear independence of vectors in Rⁿ, subspaces of Rⁿ, dimension of a subspace of Rⁿ, and the rank of a matrix.

Jurisdiction

This course is not controlled by a departmental committee. The selection of the text and specific content is made by the instructor with guidance from the catalog description. Potential textbooks for this course vary greatly and thus the content of the course is sensitive to the selection of the instructor.

Learning Objectives

M 456 concentrates on three of the Department's four teaching goals: that students be able to give examples of nontrivial applications of mathematics to various (non-mathematical) fields, that students be able to use suitable mathematical tools, and that students use mathematics as a language. However, a key notion of the course is duality theory, and study here enhances one's appreciation of the aesthetic aspect of mathematics.

Upon completion of this course, students should:

1. Be able to identify several types of business problems where linear programming has played an important role.
2. Be able to model real-world problems as linear programming problems in cases where the translation is fairily straightforward.
3. Be able to use several algorithms-simplex method with various pricing stratagies, simplex method for problems with bounded variables, two-phase method, dual simplex method, network simplex method, and some algorithms for network optimization-and be able to explain, in very general terms, the key ideas of their computer implementation.
4. With some refreshing, be able to explain the general duality theorem and its relation to the simplex method and dual simplex method.
5. Be able to explain some concepts concerned with the geometrical setting of linear programming-convexity and polyhedral sets and vertices of such sets.

Assessment of Learning Objectives

The extent to which a student masters the learning objectives is judged by his or her performance on homework, quizzes, projects, and exams.

Topics and Approximate Timeline

The following table is based on a typical semester schedule-43 class meetings of 50 minutes each. The actual amount of time spent on each topic will vary slightly from semester to semester and instructor to instructor.

Text

Introduction to Mathematical Programming, Winston and Venkataramanan,Brooks/Cole, 2003.

Format, Student Activities, and Grades

Class meetings involve a combination of lecture, questions, and discussion. Most instructors would require the students to use a linear programming software package (e.g. Lingo, Lindo) to encourage experimentation and reinforce ideas but would keep this activity at a minor level. Also students would be encouraged to use software such as Maple or Mathematica for the pivot steps on homework problems requiring step by step computations with various algorithms. Some instructors would give take-home exams and others would employ in-class exams. The grading scheme is typically based on exams, homework, and projects.