MATH4435 Mathematical Programming Fall 2017

Prof. Dan Chambers

543 Maloney Hall
617-552-3769
chambers@bc.edu (best method)

Office Hours: M3-4, W2-3, F12-1 or by appointment

Mathematical programming is an applied course that focuses on solving optimization problems involving linear functions of variables that satisfy linear inequalities. Such problems are important and numerous, including personnel and equipment assignments, optimal use of limited resources, distribution of goods through a transportation network, investment portfolio funding, project or maintenance scheduling, and many more. In this course, we concentrate on understanding the theory and implementation of the simplex algorithm, a powerful tool for solving linear programming problems. Along the way, we'll consider some aspects of two person, zero sum game theory and see the connection to mathematical programming.

Topics include linear optimization models, development and theory of the simplex algorithm, convexity and linear programming problems, duality, sensitivity analysis, integer programming, some game theory, and applications.

The textbook is An Introduction to Linear Programming and Game Theory, 3rd Edition, by P. R. Thie and G.E. Keough. Here's a copy of the syllabus and here's an errata sheet of typos for the first printing of the textbook.

Academic integrity is taken seriously and University procedures will be followed for any cases of cheating. See here for a description of these procedures.

Office Hours: M3-4, W2-3, F12-1 and by appointment.

We will be using LP Assistant, a Java-based application written by Prof. Jerry Keough, Assoc. Professor Emeritus, Boston College. It may be downloaded here.

Calendar of classes, homework assignments, and exams.

Note: this is a work in progress and changes will be made; check back for updates.

 Date topic/section HW assigned HW due/solutions August 28 [2.2] intro; trail mix: ex.1, ex. 2, graphing feasible region; level curves of objective function, corner points HW1 30 [2.2, 2.3] quick intro to sensitivity analysis, blending with percentages; production problems September 1 [2.3] more production problems HW2 HW1 solutions 6 [2.4], [2.5] transportation and dynamic programming problems 8 [3.1] standard form of a LPP and equivalence of problems; [3.2] definitions 11 [3.2] canonical forms of LPP, examples HW3 HW2 solutions 13 [3.3] canonical form of trail mix; feasible basic solns vs corner points; finding feasible basis- LP Assistant,  geometric approach 15 [3.4] intro to simplex method theory 18 [3.4] Thm. 1, Thm 2 HW3 solutions 20 [3.4] Thm 3 22 [3.5] examples HW4 25 [3.6] artificial variables 27 [3.6] more artificial variables 29 [3.7] redundant equations, [3.8] convergence theorem HW4 solutions October 2 [3.8] ct'd, [3.9] convexity 4 [3.9] ct'd, [4.2] ICP and DOP are dual problems 6 midterm 1  solutions 11 [4.2] max/min form 13 [4.2] dual of problem not in max/min form 16 [4.2] shortcuts to finding dual, dual of trail mix 18 intro to duality theorem, [4.4] duality; Theorem 1 and corollaries HW5 20 [4.4] Theorem 1, corollaries 23 [4.4] duality theorem proof begun 25 [4.4] proof concluded, corollary HW5 solutions 27 [4.4] how to find soln to the dual, examples 30 [4.5] complementary slackness theorem, example 1 HW6 November 1 [4.5] example 2;  [5.2] sensitivity analysis, matrix approach 3 no class 6 [5.2] ct'd HW6 solutions 8 [5.3] changes in the objective function HW7 10 [5.3] ct'd, [5.4] adding a new variable 13 [5.5] changes in b values 15 [5.6] dual simplex algorithm HW7 solutions 17 midterm 2 solutions 20 [6.1] examples 27 [6.2] IPP models: assignments, start of fixed costs HW8 29 [6.2] more examples December 1 [6.2] more examples 4 [6.2] more examples IPP practice problems HW8 6 [6.3] Gomory cutting plane algorithm 8 game theory and LPP: fundamental theorem of game theory IPP solutions 15 Final 9:00 am