MATH 6080: Linear programming
Schedule
for Week 15. Training final exam on Monday, April 16 (no
grading for this exam).
Assignment
#7 is due to Monday,
April 16. Please, find a Maple worksheet with an example of
solving a
linear system of algebraic equations here.
Course
Info
|
Weekly Schedules
|
|
|
|
|
Course
description: This course will cover a modern theory
of Linear
Programming including Interior-Points methods and Integer
Programming.
We plan to cover Parts 1,2, some Chapters from Part 3
and first
Chapter of Part 4 (integer Programming) of the textbook.
We'll use a computer algebra
system Maple
15 in this course for some computer projects.
Textbook: Linear programming:
Foundations and Extensions
by R.J.Vanderbei 3rd edition, Springer.
Office
Hours: Tuesday
10:00-11:40 a.m., Wednesday and Thursday: 10:00-10:50
at Everett
Tower 5527, see detailed schedule
here.
Week 15: April
16 - April 20
Topics for
study
and reading
- Chapter 23: Integer Programming. Examples:
traveling salesman problem etc. Branch-and-bound method.
Week 14:
April 9 - April 13
Topics for
study
and reading
- Chapter
18: Path-following method.
Assignment
#7 is due to Monday, April 16. Please, find a
Maple worksheet with an example of
solving a linear system of algebraic equations here.
Week 13:
April 2 -
April 6
Topics for
study
and reading
- Chapter
17: Cental-path method. Barrier
functions.
Lagrange Multiplier Rule.
Uniqueness of central-path (analytic center), existence of
central path.
- Chapter
18: Path-following method.
Assignment
#7 is due to Monday, April 16. Please, find a Maple worksheet with an
example of
solving a linear system of algebraic equations here.
Week 12: March 26 - March 30
Topics for
study
and reading
- Interior-points
methods
- Chapter
17: Cental-path method. Barrier functions.
Lagrange Multiplier Rule.
Second
mid-term exam on Friday, March 30 will cover topics from Chapters
6,7,
10, 12, 14.
Week 11:
March
19 - March 23
Topics for
study
and reading
- Chapter 14 Network flow problems: primal-dual simplex method.
- Chapter 15: Applications of network flow problems.
Transportation
and assignment problems.
Assignment
#6 is due to Monday, March 26: download the PDF file with
problems
Week 10:
March
12- March 16
Topics for
study
and reading
- Chapter 14 Network flow problems: primal-dual simplex method.
Week 8:
February
27- March 2
Topics for
study
and reading
- Chapter 12 L^1-regression
- Chapter 13: Financial applications of LP
- Chapter 14 Network flow problems: networks,, trees and bases,
primal simplex method
Week 7 : February 20 - February 24
Topics for
study
and reading
- Chapter
10. Covex Analysis: Convex sets and functions , separation
theorems,
Farkas's lemma... .Applications.
Week 6 : February 13 - February 17
Topics for
study
and reading
- Chapter 7: Sensitivity and parametric analysis
First mid-term exam on Friday February 17,
problems
from Chapter 1-6. Sample exam here.
Week 5: February 6 - February 10
Topics for
study
and reading:
- Chapter 5: Resource Allocation problem
- Chapter 6: Simplex method in matrix notation
- Chapter 7: Sensitivity and parametric analysis
New
Assignment #3 is due to February
13,
Monday.
Week 4: January 30 - February 3
Topics for
study
and reading:
- Chapter 5: Dual Simplex Method
- Chapter 5:Dual-based Phase I Algorithm
- Chapter 5: Dual of a problem in general form
- Chapter 5: Resource Allocation problem
- Chapter 6: Simplex method in matrix notation
New
Assignment #3 is due to February 13,
Monday.
Week 3: January 23 - January 27
Topics for study and reading:
- Chapter
5: Duality Theory, dual problems
- Chapter
5: Weak and strong duality theorems, complementary slackness
- Chapter
5: Dual Simplex Method
Assignment #2 is due to
Wednesday, February 1
Week 2: January 16 - January 20
Topics for
study
and reading:
- Chapter
2: Initialization, checking
infeasibility, checking unboundedness. Two-phase
method.
- Chapter
3: Degeneracy, cycling, anti-cycling rules:Bland's rule
- Chapter
3:
Fundamental theorem of Linear programming
- Chapter
4:
Efficiency of Simplex Method
Week 1: January 9 - January 13
Topics for
study
and reading:
- Chapter
1:
General
optimiation
problems
with
constraints
:
objective
function,
equality and inequality constraints. Examples.
Linear programming problems : objective functions,
decision variables,
equality and inequality
constraints.
Examples of linear programming model formulation. Standard
form of
linear programming model.
- Lecture
Notes:
Graphical method of solution of two-dimensional LP
problems.
- Chapter
2:
The Simplex Method, basic and nonbasic variables, pivot
rules.
- Chapter
3:
Degeneracy, cycling, anti-cycling rules
Look
for a list of homework problems for Assignment
#1 for this week.
Homework Assignments
Note that
problems
marked with * are extra.
Assignment #1(due to Friday, January 20)
problems (p.8) 1.1, 1.2, (p.24) 2.1, 2.3, 2.9,
2.16,
2.19*
(p.42) 3.2
Assignment
#2
(due to Wednesday, February 1): use online Java
applet
with
a
simple
pivot
rule
to solve problems (p.52) 4.1, 4.2.,
solve (p.79) 5.1, you can use online Java
applet
with an advanced pivot rule to solve problems
(p.79)
5.2, 5.3
Assignment #3
(due to Monday, February 13): problems (p.81) 5.6, 5.7, 5.14,
6.2
Assignment
#4
(due to Friday, March 2): problems (p.122) 7.1, 7.2, (p.170)
10.2, 10.4
Assignment
#5
(due to Wednesday, March 21): problems (p.203) (use Maple or
Java
applet to find optimal solution of corresponding LP problem)
12.2, 12.7,
Assignment
#6 (due to Monday,March 26):
download the PDF file with problems
Assignment #7 (due to Wednesday, April 11): problems (p.299)
17.1,
17.2, 18.1 (b).
Maple 15.0
worksheets
(click on the title to download worksheet):
Exams
- First mid-term
exam : Friday, February 17. Sample exam here.
- Second mid-term exam: Friday, March
30.
Sample exam here.
- Final exam (comprehensive) :
Monday, April 23 at 10:15 am - 12:15 pm.
Grades and
Makeup
Policy
Grades will be assigned using a
sliding
scale. The usual passing level "C" is between 65% and 68%. Someone
with
88% may get "A". After each test we'll get an approximate passing
level. Do not panic if your grade seems low, come and talk with
me about your performance.Various numbers below
determine the relative weights of exams' and quizzes'
grades: Total number of points 500. The final exam - 200 points.
Each
midterm exam - 100 points, quizzes grade - 100.
In general, there will be NO
makeups
for exams. If you miss an exam for a valid well-documented
reason then
arrangements may be made on an individual basis.
Academic Integrity
You are
responsible for making yourself aware of and understanding the
policies
and procedures in the Graduate Catalog (pp. 26-28) that pertain to
Academic Integrity. These policies include cheating, fabrication,
falsification and forgery, multiple submission, plagiarism,
complicity
and computer misuse. If there is reason to believe you have been
involved in academic dishonesty, you will be referred to the
Office of
Student Conduct. You will be given the opportunity to review the
charge(s). If you believe you are not responsible, you will have
the
opportunity for a hearing. You should consult with me if you are
uncertain about an issue of academic honesty prior to the
submission of
an assignment or test.
Comments,
questions, problems to ledyaev@wmich.edu
.
Last modified April 14, 2012.
