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