346:001, Fall 2017

An Introduction to Optimization Theory


General Course Information
Meeting time:  Monday and Wednesday 10:00 am - 11:15 am in W201

Instructor
: Hao Huang

Textbook: P. Thie and G. Keough, An Introduction to Linear Programming and Game Theory, 3/e

Syllabus:
Please click here for the syllabus of this course, which includes more details on the course goal, grading scheme, exam and homework policy.



My Contact Information
E-mail: hao.huang AT emory.edu
Office: MSC E432
Office hour: Monday/Wednesday 11:15a-12:15p or by appointment.

Communicating with me:  If you have a general question about this class, you are welcome to send me an email. For mathematical questions, the best way is to come to my office hour. If you cannot make to it, you can send me an email to make an appointment with me. Please include the course number in the subject line of your emails.




Homework Assigments
The homework assignements will be posted below, together with their due dates.

HW1:
2.2.8, 2.2.12, 2.3.7, 2.3.16, 2.3.23        (due date: Sep 6, 2017).       Solution to HW1

HW2: 2.4.4, 2.4.6, 2.5.3, 2.6.9, 3.1.3 (e) and (f)        (due date: Sep 13, 2017).        Solution to HW2

HW3: 3.2.2, 3.2.6, 3.9.6, and solve the LP in Exercise 3.3.2 on Page 76 using the general representation theorem (a.k.a. fundamental theorem of LP)      (due date: Sep 20, 2017) . Solution to HW3  

HW4: 3.3.3, 3.4.5, 3.5.2(b), 3.5.6(b)        (due date: Sep 27, 2017)         Solution to HW4

HW5: 3.6.1(b), 3.6.1(a) (use big-M method), 3.6.2(c) (use two-phase method), 3.7.2        (due date: Oct 11, 2017)
For 3.6.1(a), you can pick an objective function at your choice. 

HW6: 4.2.1(e), 4.2.3, 4.4.1, 4.4.2, 4.5.2   (due date: Oct 25, 2017


Tentative Outline
Chapter 1: Mathematical Models (1-2 classes)
Chapter 2: The Linear Programming Model (1-2 classes)
Chapter 3: The Simplex Method (7 classes)
Chapter 4: Duality (4-5 classes)
Chapter 5: Sensitivity Analysis (2-3 classes)
Chapter 6: Integer Programming (2 classes)
Chapter 7: The Transportation Problem (2-3 classes)
Chapter 9:  Two-Person, Zero-Sum Games (2-3 classes)


Course Schedule 

The materials covered in the classes will be updated and posted below after each class.

Aug 23 (W)        
Course introduction, how to formulate a problem in mathematical languages, diet problem, introduction and assumptions of general linear programming, history of LP (Ch 1.1, 1.2, 2.1)

Aug 28 (M)       
Blending model, production model, graphical method to solve LP (Ch 2.2 + 2.3).

Aug 30 (W)        
Transportation model, dynamic planning model (investment portofolio), how to convert LP into the standard form. (Ch 2.4, 2.5, 3.1)

Sep 4 (M)   
--- No class due to Labor day.

Sep 6 (W)          
Canonical Form, Basic feasible solution (BFS), pivot operation on linear equations, definitions and examples of a convex set. (Ch 3.2, 3.9)

Sep 11 (M)   --- No class due to Hurricane Irma.


Sep 13 (W)      
   Definition of extreme points (vertices) of a convex set, proof of "BFS=extreme points of feasible region", definition of directions (Ch 3.9 + beyond the textbook)   

Sep 18 (M)         
Definition of extreme direction of a convex set, solving a LP using the General Representation Theorem.

Sep 20 (W)         
An introduction to the simplex method; solve the LP assuming an initial BFS exists.  (Ch 3.3 + 3.4)

Sep 25 (M)         
Simplex tableau, more examples of solving LP using the simplex method, artificial variables (Ch 3.5 + 3.6)

Sep 27 (W)         
Discussion of redundant systems, Big-M Method (Ch 3.7 + beyond the book)

Oct 2 (M)           
Single Artificial Variable method, the motivation to study duality. (Ch 4.1, 4.2)

Oct 4 (W)   ----  Midterm 1 (tentative)

Oct 9 (M)
 ----  No class due to the Fall recess

Oct 11 (W)         
How to obtain the dual of a linear program. Weak duality of linear programming and its implications, example that both the primal and dual are infeasible. Solution to Midterm 1 (Ch 4.2, 4.3, 4.4)

Oct 16 (M)         
 Proof of the strong duality using the Farkas Lemma. Statement of Complementary Slackness.

Oct 18 (W)         


Oct 23 (M)
       

Oct 25 (W)         


Oct 30 (M)         


Nov 1 (W)          


Nov 6 (M)          


Nov 8 (W)  ----  Midterm 2 (tentative)

Nov 13 (M)        


Nov 15 (W)        


Nov 20 (M)       


Nov 22 (W)
--- No class due to the Thanksgiving recess

Nov 27 (M)          


Nov 29 (W)          


Dec 4 (M)            


Final exam will be on Tuesday, Dec 12, from 3:00 pm to 5:30 pm in the usual classroom (MSC W201).