Operations Research I
Linear Programming
1 Instructor
Robert Molzon
Office: POT 933
E-Mail: molzon@ms.uky.edu
Phone: 859 257-1480
Office Hours: MWF 10:00-11:00
2 Text
Linear Programming: Foundations and Extensions by Robert Vanderbei
The text is available online for online reading at Robert Vanderbei http://www.princeton.edu/~rvdb/LPbook/
I suggest you purchase a copy at an online bookstore such as Amazon.
You can pick up a new copy for about $63. You will also find a set
of online lecture notes to go with the text at the above URL. I suggest
you download these notes since I will follow them fairly closely.
There are many other sources online for notes on linear programming.
Here are a few you might find useful.
I've also put some notes and ampl code online. You can find links
here. notes.xhtml
3 Grading
Your grade for the course will be based on a midterm exam, a project,
a final exam, and homework. Each of the four components will count
toward 25% of your grade. I will post sample problems for the midterm
and final exams.
sample_midterm sample_midterm.pdf
4 Software
We will make extensive use on AMPL for solving linear programming
problems. This software is available free (student version) from the
AMPL website, AMPL http://www.ampl.com/index.html. You can
download a version for either Windoz or Linux. You should also download
and install at least the two solvers Minos and CPLEX.
Here are a couple of links to files that contain sample AMPL model
files and data files. You should start with the basic.mod file and
then go to the general.mod file.
basic.mod ampl/basic.mod
basic.dat ampl/basic.dat
general.mod ampl/general.mod
general.dat ampl/general.dat
general.run ampl/general.run
ampl ampl/ampl_guide.pdf
Excel has a builtin solver and if you are familiar with Excel you
might want to try using that solver as well. The solver that comes
with Excel is rather limited in the size of the problem that it can
deal with, so you should certainly get used to using AMPL. You will
need it for working your project.
4.3 Pivot Tools
You will also need a matrix pivot tool for working some of the simplex
exercises. You can find one on Vanderbei's website. It is written
in Java and if you have the right version of Java linked to your html
browser, you can use it. There is also an online pivot tool available
at Online Pivot http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/tutorialsf1/scriptpivot2.html.
This tool allows you to perform pivot operations on a matrix. In addition,
some of the more sophisticated calculators have builtin pivot tools.
You can download the pivot tool and use it with Excel.
You can also use the Java Script pivot tool found on Vanderbei's web
site. You must have Jave Runtime Environment installed on your computer.
5 Homework
We will use the online web homework system for weekly homework. Here
is a link to the site.
mathclass http://www.mathclass.org
Information about using Webclass can be found here. webclass_information.html
.
You should have an account for the class. If you are in MA416 (CS416)
your homework will be on the Webclass MA416 (CS416). The due dates
for the assignments are indicated on each assignment.
6 Topics and Goals
We will cover Part I of Vanderbei's text as well as basic use of AMPL.
In the course of learning to use the AMPL software we will cover several
"real world" examples. The your goals for the course are
- Gain an understanding of the basic ideas of linear programming,
- Learn to formulate and solve moderately complicated practical optimization
problems that can be approached using linear programming,
- Gain a basic working knowledge of the use of LP software such as AMPL.
Here is a list of the topics in the order that they will be covered.
Each topic will take approximately one week.
- Introduction to LP: What is a typical problem that can be solved using
linear programming?
- Simplex Method: Geometric and algebraic approach. Formalism of the
simplex tableau and linear equations.
- AMPL: Setting up and solving some simple problems. Submitting problems
to NEOS.
- Degeneracy: What can go wrong in the simplex method and how can it
be fixed?
- Efficiency: Basic ideas of computational complexity.
- Duality: Economic and geometric interpretation. Setting up the dual.
- Matrix Notation: Write a linear programming problem and dual in matrix
notation.
- Sensitivity: Modification of a problem. Getting more information from
AMPL. Bounding constraints.
- General Form of an LP: Equality constraints, unbounded variables.
Very easy in AMPL.
- Convex Analysis: Convex sets, hyperplane seperation.
- Game Theory: Zero sum games. Mixed strategies. (Go rent the DVD "A
Beautiful Mind")
- Regression: Economists make a living doing it. So do statisticians.
7 Projects
As part of your course grade you are to do a project that goes beyond
the standard homework in complexity. Your project must be typed as
a report and include information about any software you used. At a
minimum you must include
- Statement of Problem
- Sources of data or information about the problem.
- Statement of methods
- Description of solution including software used.
- Set of references used (including online references).
I have included a list of project topics below. You can select one
of these or come up with your own project. If you select your own
project, you must discuss it with me first and give me a basic outline
for approval.
7.1 Regression
Construct and solve an
regression model for your favorite
statistic. For example, find a relationship between earnings of two
or more different occupations. The Bureau of Labor Statistics is a
good source of data on prices, wages, and employment.
7.2 Portfolio Optimization
Read the lecture notes of Vanderbie on portfolio optimization. Impliment
the AMPL program he describes to find an optimal portfolio.
7.3 Scheduling
Set up and solve a linear model for scheduling of instructors to courses
and time slots. Allow each instructor to weight each course and time
slot. Maximize the total reward of the instructors and cover all courses.
7.4 An interactive Simplex Solver
Write an interactive simplex solver in Perl. The user should be able
to input a linear programming problem in augmented form (including
slack, surplus varaibles). Input should be possible from STDIN or
from a file. The user selects pivots and the program performs the
pivot operations and tests for optimality. Display should include
varaible and constraint labels. Ideally, the program would be placed
in a CGI script so that it could be used online.
7.5 Data estimation and supression.
The Census Bureau and the Bureau of Labor Statistics both release
huge amounts of data to the public. However, private data must be
protected. The BLS uses linear programming to determine which data
should be suppressed. As a project, set up and carry out an AMPL to
determine data that must be suppressed in a three dimensional table.
8 Additional Links
File translated from
TEX
by
TTM,
version 3.72.
On 17 Oct 2007, 11:26.