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 real-life problems that can be described as linear programs.
Requirements
Online attendance of the lectures is highly recommended. Attendance is registered. In-class performance is assessed and its results form part of the end-term 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)
- 80-100: 5 (excellent)
- 70-79: 4 (good)
- 60-69: 3 (medium)
- 50-59: 2 (satisfactory)
- 0-49: 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, Two-phase 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, non-zero sum games and QP
-
Lecture 10
Selected topics and solving problems with AMPL
-
Lecture 11-12
Student's presentations, end-year test