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