MATH4435 Mathematical Programming Fall 2018

Prof. Dan Chambers

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

Office Hours: M2-3, W12-1, F11-12 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: M2-3, W12-1, F11-12 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 27 [2.2] intro; trail mix: ex.1, ex. 2, graphing feasible region; level curves of objective function, corner points 29 [2.2, 2.3] quick intro to sensitivity analysis, blending with percentages; production problems HW1 31 [2.3] more production problems HW2 September 5 [2.4], [2.5] transportation and dynamic programming problems HW1 solutions 7 [3.1] standard form of a LPP and equivalence of problems; [3.2] definitions 10 [3.2] canonical forms of LPP, examples HW3 HW2 solutions 12 [3.3] canonical form of trail mix; feasible basic solns vs corner points; finding feasible basis- LP Assistant,  geometric approach 14 [3.4] intro to simplex method theory 17 [3.4] Thm. 1, Thm 2 HW3 solutions 19 [3.4] Thm 3 21 [3.5] examples 24 [3.6] artificial variables HW4 26 [3.6] more artificial variables 28 [3.7] redundant equations, [3.8] convergence theorem October 1 class canceled 3 [3.8] ct'd, [3.9] convexity HW4 solutions 5 midterm 1  solutions 10 [3.9] ct'd, [4.2] ICP and DOP are dual problems 12 [4.2] max/min form and duality, dual of an LPP not in max form 15 [4.2] shortcuts to findng dual, dual of trail mix 17 [4.4] Theorem 1, Corollary 1 19 [4.4] Corollary 2, duality theorem HW5 22 [4.4] proof of duality theorem 24 [4.4] technical bits, corollary to duality theorem; finding soln to the dual summary 26 class canceled (early campus closing) 29 [4.5] complementary slackness theorem, example 1 HW5 31 [4.5] example 2 November 2 [5.2] sensitivity analysis, matrix approach 5 [5.2] ct'd 7 [5.3] changes in the objective function HW6 9 [5.3] ct'd, [5.4] adding a new variable 12 [5.5], [5.6] change in b values, DSA 14 [5.6] dual simplex algorithm, Excel and sensitivity analysis HW6 16 midterm 2  solutions 19 [6.1] IPP introduction 26 [6.2] assignments, fixed costs 28 [6.2] change in costs 30 [6.2] assignments, knapsack problems December 3 [6.2] cutting stock, more examples 5 [6.2] alternative constraints 7 [6.3] Gomory cutting plane algorithm 10 game theory and LPP: fundamental theorem of game theory changes in b, ,end of game theory   solutions IPP practice problems   solutions 18 Final 12:30 pm