Meetings: MWF 2:10-3:00 PM, 235 Wellman. A couple of sessions will take place in Kerr Hall 451 (computer lab) and this will be announced in class.
Instructor: Jesús A. De Loera.
email: deloera@math.ucdavis.edu
URL: http://www.math.ucdavis.edu/~ deloera/
Phone: (530)-754 70 29
Office hours: Monday, Wednesday 12:10-1pm or by appointment. My office is 580 Kerr Hall.
Text: Textbook Robert J. Vanderbei, Linear programming foundations and extensions, 3rd edition ISBN-13: 978-0387743875 The book is available electronically via the UC Library at http://dx.doi.org/10.1007/978-0-387-74388-2 (If you're connecting from off-campus, you'll need to use the UC Library VPN.) You can also order a print copy (soft cover) for $24.95 from SpringerLink. Topics We will mostly follow the department syllabus. We will cover one additional topic not on the department syllabus: Integer linear optimization. Vanderbei Robert Linear Programming Foundations and Extensions, Kluwer international series second revised edition, 1997.
Description: This course is an introduction to an exciting field of applied mathematics: Optimization and Mathematical Programming. The course intends to teach the basic geometry and algorithms regarding the solution of linear optimization problems as well as to illustrate the very important applications that such models have in areas such as Economics, Engineering, and Management. The course has, in addition to the theoretical part, a component of experimentation with computer software and some elementary programming assignments. Here are the topics to be covered:
Material up to first Midterm (4 weeks): Examples of Linear Programming models and motivation. A first view of the simplex method, pivoting rules and basic geometry, the dual of a linear programming problem, complementary slackness and optimality.
Material for second part (6 weeks): Primal vs. Dual Simplex method, Sensitivity analysis, Numerical-Implementation issues, Convexity and Farkas Lemma, Network flow problems. If time allows we will touch one of the following topics: ellipsoid method, integer programming, game theory.
Grading policy: The course grade will be based on 4 homeworks (approximately 12-15 problems each) that may include some programming assignment (40 points), one midterm exam set for April 30th (30 pts) and the final exam (30 points). The exams will be closed-book and closed-note. The final exam will be comprehensive. I will assign grades based on an statistical curve of points obtained by all students. Please note that NO late homeworks will be accepted. Feel free to call me or send me email if you are stuck!
Prerequisites: MAT 22AB, 108 or equivalent and a willingness to solve many exercises and learn some mathematical software.
FIRST HOMEWORK SET: Due April 16th. A) 2.1,2.2,2.8,2.11,2.12,2.13.
B) 3.1,3.2,3.3,3.5,3.6.
C) Can you formulate the traveling salesman problem as a linear programming problem or some variation of it? Explain your reasoning.
Before you can use MAPLE you need to have a class account. To activate the account follow these steps:
go to main math page
click on computer resources option
.
click on class accounts
fill out the form that appears
get account information
Maple allows you to apply pivots one at a time. YOU are supposed to select the pivots, MAPLE does the arithmetic for you, EXAMPLE:
First call maple type maple, once you get the prompt you type:
with(simplex);
at prompt you can type your dictionary equations:
C:={z=2*x2+x4+5*x1,x4=4-x1-x2-x3,x5=2-x1,x6=6-3*x2-x3};
Apply pivot by typing
pivot(C,x2,[x4=4-x1-x2-x3]);
Where x2 is the entering variable, x4 is the leaving variable
here is the resulting new dictionary which appears in the screen after you hit return.
{x5 = 2 - x1, x2 = -x4 + 4 - x1 - x3, x6 = -6 + 3 x4 + 3 x1 + 2 x3, z = -x4 + 8 + 3 x1 - 2 x3}
IMPORTANT: In the example the choice of entering variable and leaving variable was incorrect! It gave an infeasible dictionary. MAPLE does not check whether your choice is appropiate, but performs the arithmetic without mistakes for you.
4.3, 5.1, 5.2, 5.4, 5.7, 5.11.
A)Answer yes or no and prove your answer: Can a pivot of the simplex method move the basic feasible point a positive distance while leaving the cost unchanged?
B)Prove: If an LP is unbounded there is a vector a such that it satisfies two properties:
1) c1a1+c2a2+c3a3+...+cnan >0, for c1x1+c2x2+...+cnxn the objective
function
2) if x is a feasible solution and k>0 then x+ka is also feasible
The Maple examples file can be downloaded here. Press the shift key and then click on the highlighted text.
A) 7.3, 7.4, 7.5, 10.2, 10.4, 11.1,11.2, 11.4, 11.6
B) Consider a polyhedron P={x | Ax=b x>=0}, an extreme point of P is a point x of P with the property that if y,z in P can be used to write x=1/2(y+z) then y=z=x.
Problem: Prove that x is an extreme point of P if and only if the collection of column vectors {A_j | x_j not=0} is linearly independent.
13.1,13.3,13.4,13.6,13.7,14.1
3.6, 5.1, 6.1, 7.1, 11.1, 13.4, 13.9
FINAL EXAM INFORMATION: The final exam will be Wednesday June 13 from 8-10am at Wellman 235.