MATH 340 (3) Introduction to Linear Programming:
Linear programming problems, dual problems, the simplex algorithm, solution of primal and dual problems, sensitivity analysis.
topics chosen from: Karmarkar's algorithm, non-linear
programming, game theory, applications.
Prerequisite: One of MATH 152, MATH 221, MATH 223.
We follow the textbook, "Linear Programming" by Vanderbei, 4th edition; it is available to anyone with a CWL account.
o LINDO runs on Widows based PCs. There are two basic approaches to running Windows on a Mac:
§ Setting up Apple's Boot Camp
§ Running Windows in a "virtual machine"
Which route you take depends on your needs, particularly how often or permanently you need Windows. The first option sets aside a partition on your Mac's hard drive that you can boot into and run Windows directly on the Apple hardware.
If you have no access to computers then write me to set up an account to the computer lab.
· Joel Friedmans notes about poker and game theory.
· Graph theory and applications a book by Bondy and Murty. We cover the Shortest Path Problem (1.8) the Chinese Postman Problem (4.3) the Traveling Salesman Problem (4.4) and parts of Chapters 5, 10, and 11.
Notes from class
· Introduction (1/6/15)
· A simplex example (1/8/15)
o Max 4x1+6x2
o Subject to
o After completing two more iteration (what we did in class) the optimum is 132, when x1=15 and x2=12.
· An unfeasible LP problem.(1/22/15)
· A LINDO example.(1/29/15)
· Scroll down for the details
In addition to the questions covered in the problem sets there might be a sensitivity analysis question based on a LINDO output. Check the LINDO example we analyzed in class and try to answer the sample question below. We will discuss the answers in class after the break.
In the following example you want to minimize the cost of transportation while satisfying the demands of the four costumers and the supply constraints of the three warehouses. You will find the questions after the LINDO output.
· Last day to withdraw without a W standing: January 19, 2015
· Last day to withdraw with a W standing (course cannot be dropped after this date): February 13, 2015
Term 2 (Jan 05, 2015 to Apr 10, 2015)
Midterm break: February 16-20
Midterm exam: Feb 26 Thursday (in class)
Final: April 20 Monday at 12 noon, location: GEOG 100
Syllabus MATH 340
Week 1-2 (Jan 6- 18)
Chapter 1. Introduction
1. Managing a Production Facility
2. The Linear Programming Problem
Chapter 2. The Simplex Method
1. An Example
2. The Simplex Method
Week 3 (Jan 19-25)
Week 4 (Jan 26-31)
Chapter 3. Degeneracy
1. Definition of Degeneracy
2. Two Examples of Degenerate Problems
3. The Perturbation/Lexicographic Method
4. Blands Rule
5. Fundamental Theorem of Linear Programming
Week 5-6 (Feb 1-16)
Chapter 5. Duality Theory
1. Motivation: Finding Upper Bounds
2. The Dual Problem
3. The Weak Duality Theorem
4. The Strong Duality Theorem
5. Complementary Slackness
6. The Dual Simplex Method
7. A Dual-Based Phase I Algorithm
8. The Dual of a Problem in General Form
Week 8 (Feb 23-28)
Review and Midterm exam
Week 9-10 (March 1-7)
LINDO + sensitivity analysis
Week 10-11 (March 8-21)
Chapter 10. Convex Analysis
1. Convex Sets
2. Carathe΄odorys Theorem
3. The Separation Theorem
4. Farkas Lemma
Chapter 11. Game Theory
1. Matrix Games
2. Optimal Strategies
3. The Minimax Theorem
Week 12(March 25-31)
Part 2 (Network Flows and Applications)
Week 12+ (April)
Note: This is the plan; however we might change the schedule if needed. The indicated chapters and sections are from the courses book. Our treatment some of the listed topics will be slightly different then in the book.