**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.

A

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 copies of the transparencies I used for the class about Duality theorem are available at here

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

In preparation for the final exam, I have selected a few problems (some even from the previous homeworks) which are very important and most relevant for preparation: Make sure you know how to do them!

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.

Jesus De Loera 2001-03-13