Term |
Day |
Start Time |
End Time |
Building |
Room |
2 |
Tue Thu |
11:00 |
12:30 |
Buchanan |
Apr. 18, 3-4:30 pm. Room: MATH
104 (most likely)
Final:
April 20 Monday at 12 noon, location: GEOG 100
MATH 340
(3) Introduction to Linear Programming:
Linear programming problems, dual problems, the simplex algorithm,
solution of primal and dual problems, sensitivity analysis.
Additional
topics chosen from: Karmarkar's algorithm, non-linear
programming, game theory, applications.
Prerequisite: One of MATH 152, MATH 221, MATH 223.
Course book:
We follow
the textbook, "Linear Programming" by Vanderbei,
4th edition; it is available to anyone with a CWL account.
Here is a
book you might find very useful when you review what weve learned: Practical
Optimization: A Gentle Introduction, by John W. Chinneck.
(up to Chapter 9.)
Grading
Policies
Notes
· We are going to use
the optimization software Classic
LINDO. You have to download it. Here is the User's Manual.
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.
· Applications
of network optimization
· 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.
· Wikipedia has nice
descriptions of the network algorithms weve learned.
o The Ford-Fulkerson
Algorithm
o Dijkstra's Algorithm
o Minimum Spanning Tree
o The Chinese Postman
Problem
o Maximum Matching
o The Traveling
Salesmans Problem
· Here is a book you might find very
useful when you review what weve learned: Practical
Optimization: A Gentle Introduction, by John W. Chinneck.
(up to Chapter 9.)
Notes from class
· Introduction
(1/6/15)
· A simplex example
(1/8/15)
o Max 4x1+6x2
o Subject to
§ -x1+x2<=11
§ x1+x2<=27
§ 2x1+5x2<=90
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)
Syllabus
· Scroll down for the details
Problem Sets
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.
Dates:
Withdrawal Dates
· 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
2015
spring
Part 1. Basic Theory: The Simplex
Method and Duality
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)
3.
Initialization
4.
Unboundedness
5.
Geometry
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
6.
Geometry
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
Reading
break
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 11. Game Theory
1.
Matrix Games
2.
Optimal Strategies
3.
The Minimax Theorem
Week 12+(March 25-31-)
Part 2 Network Flows and Applications
Graph Algorithms
1.
The Ford-Fulkerson Algorith
2.
Dijkstra's Algorithm
3.
Minimum Spanning Tree
4.
The Chinese Postman Problem
5.
Maximum Matching
6.
The Traveling Salesmans
Problem
Week 12+ (April)
Review
Final
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.