Information
Classroom, timetable
IMEN102E/G,
Description
Linear programming is a widely used field of optimization. Many practical problems in operations research can be expressed as linear programming problems. It has a wide range of practical business, commerce, and industrial applications and simultaneously has received so thorough a theoretical development. Today, this theory is being successfully applied to problems of capital budgeting, design of diets, conservation of resources, games of strategy, economic growth prediction, and transportation systems. The aim of the course is to introduce basic and advanced theory of linear programming, and to show and solve reallife problems that can be described as linear programs.
Requirements
Online attendance of the lectures is highly recommended. Attendance is registered. Inclass performance is assessed and its results form part of the endterm grade. The final score (%) of the course is constructed as follows: 20% lecture and seminar attendance, 30% homeworks, and 50% home project + presentation (last lecture of the semester).
Grades (based on points)
 80100: 5 (excellent)
 7079: 4 (good)
 6069: 3 (medium)
 5059: 2 (satisfactory)
 049: 1 (fail)
Online available material
Applications of linear programming (lecture notes handout) and official version
Syllabus

Lecture 01
Motivation and introduction to linear programming, examples, basic definitions. Lecture 1 slides

Lecture 02
Simplex algorithm, Twophase simplex method, degeneracy, cycling, pivot rules, fundamental theorem of LP. Further examples. Lecture 2 slides

Lecture 03
Duality, weak and strong duality theorems, complementary slackness, economic interpretation. General LP. Examples. Lecture 3 slides

Lecture 04
Integer programming. Branch and bound method, knapsack problems, examples. Lecture 4 slides

Lecture 05
Multiperiod work scheduling. Linear algebra overview and Simplex algorithm in matrix form. Totally unimodular matrices and integer programming. Lecture 5 slides

Lecture 06
Graphs: basic definitions. Network problems: shortest path, minimum spanning tree, maximum flow. Lecture 6 slides

Lecture 07
Transportation, assignment and transshipment problems Lecture 7 slides

Lecture 08
Introduction to stochastic programming: portfolio problem, newspaper vendor problem, reliability problems Lecture 8 slides

Lecture 09
Elements of game theory, zero sum games and LP, nonzero sum games and QP

Lecture 10
Selected topics and solving problems with AMPL

Lecture 1112
Student's presentations, endyear test