# Applications of Linear Programming

## Information

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

• 80-100: 5 (excellent)
• 70-79: 4 (good)
• 60-69: 3 (medium)
• 50-59: 2 (satisfactory)
• 0-49: 1 (fail)

## 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