42101 Introduction to Operations Research
Sorry – no questions right now
… I am busy preparing for the lecture ☺
Questions regarding Julia:
We will deal with them in the exercise session from 15:00 to 17:00
Questions regarding the course:
Please ask them in the break at 14:00, during the lectures or during
the exercise session.
1 Introduction to Operations Research
42101 Introduction to Operations Research
• What is Operations Research?
• Overview of the course
• Introduction to Linear Programming (Chapter 3)
Stefan Røpke
Rasmus Bo Bramstoft Pedersen
Richard Martin Lusby
DTU Management
Department of Technology, Management and Economics
What is Operations Research (OR)?
• Very short definition:
Application of mathematical techniques to decision making
• Examples of applications
– Planning of production: which products should be produced at
what time?
– Work planning: Which employee should be on duty at what
time?
• … it becomes clearer as we go on!
3 Introduction to Operations Research
What is Operations Research?
• Useful skills when studying and applying Operations Research
– Mathematics
– Computer Science
– Machine learning/Artificial intelligence
– Ability to understand new application areas
– Common sense
4 Introduction to Operations Research
Very short history of operations research
• Debatable when and where operations research started.
• However, a milestone is the use of operations research in UK
during World War 2 to improve war efforts.
• After the second world war the techniques were used for
peaceful purposes and accelerated due to the arrival of
computers
• Now OR techniques are used in many places. Everyday we are
in contact with products and services that in one way or the
other have been influenced by OR.
• Video with a British perspective on the history of OR:
https://www.youtube.com/watch?v=ILWbaWrjgU4
5 Introduction to Operations Research
The traveling salesman problem (TSP)
??
6 Introduction to Operations Research
The traveling salesman problem (TSP)
7 Introduction to Operations Research
Distribution planning
Our task: supply supermarkets,
gas stations, corner stores etc.
with dairy (milk) products.
Each truck can at most serve 4
shops.
Arla
8 Introduction to Operations Research
Distribution planning
Our task: supply supermarkets,
gas stations, corner stores etc.
with dairy (milk) products.
Each truck can at most serve 4
shops.
Arla
9 Introduction to Operations Research
Operations research is everywhere
• Products are often brought to the end customer using trucks, ships or
planes. OR is often involved in planning the transport.
• The production of products you buy may have been planned using OR.
• When you ride on the bus, metro or the S-train OR may have been used
in the planning processes.
• OR methods may have been used to design the electronics in your
smartphone, computer, etc. Used to optimize signal path, for example.
10 Introduction to Operations Research
Work cycle in OR
Real-life
system
Interpreting Problem definition
solution Model building
Mathematical
Solution
model
Solution process
11 Introduction to Operations Research
Course overview
12 Introduction to Operations Research
Course overview
Project hand-in on
november 3rd
13 Introduction to Operations Research
Practical info
• Main book
– Hillier, Lieberman: Introduction to Operations Research, 2024 or
evergreen edition.
[earlier version are similar, but page and chapter references in class
may be “off”]
– Material on DTU Learn.
• Prerequisites (Simultaneous Linear Equations, Matrix operations)
– Read appendix 4 and 6
– Appendix 6 you can get from the book web-page or from DTU inside.
• DTU Learn
– Course overview, slides, projects, additional reading material
– “Final” version of slides ready around noon Sunday.
• Language: English
– You can hand in projects in English and Danish
– You can answer exam in Danish or English
14 Introduction to Operations Research
Practical information
• Lectures
– Monday from 13 to 15 building 116 lecture hall 81
• Exercises
– Monday from 15 to 17
– Building 358, building 324 rooms 20, 40, 60, 70 plus the foyer (004, 005, 008)
• Preparation:
– Read the text and look at slides before lecture.
– If you do not finish exercises, then complete them before next lecture.
• Teachers
– Stefan Røpke (
[email protected])
– Rasmus Bo Bramstoft Pedersen (
[email protected])
– Richard Lusby (
[email protected])
– Teaching assistants
Mathias Peter Verena Nicola David Frederik Tim Aidan
Berg Marius Vanessa Accoto Feijóo Fristed Graulich
Rosendal Elkjær Irming- Rodríguez
Pedersen
Demanding course?
• You must make an effort to meet the learning
objectives!
• Be active from the start – we keep building on
material from past lectures.
• Read the book. It’s not enough to be present at the
lectures.
• Solve all exercises
• Exercises from 15 to 17 are more important
compared to the lectures.
16 Introduction to Operations Research
One written assignment
• Show what you can do with OR.
• Go a little further with some topics.
• Preparation for the exam.
• Preliminary plan:
Start 07-10-2024
Hand-in 03-11-2024
Feedback 24-11-2024
• Content is mainly the material covered until (and including) the project
start day. There could also be about the subject taught the following
week.
• Do the project in groups (2-3 three students in each group)
• You need to pass the project in order to attend the exam.
– Perfect project: 100 point
– Passed: 50-100 point
• There are no second attempts for passing the project.
• Your grade is only based on the exam. The mandatory assignment
does not count toward the grade.
17 Introduction to Operations Research
Exam
• 4 hours written exam
• “All aids allowed”. No internet.
• Multiple choice and with a few (perhaps 0) questions that require a text
answer.
• Planned date: 15th of May (check https://kurser.dtu.dk/ to be sure).
18 Introduction to Operations Research
Exercises – Building 324
• See tasks on DTU learn
19 Introduction to Operations Research
Exercises – Building 324
• See tasks on DTU learn
• Building 324, rooms 020,
040, 060 and 070 (red dots)
plus foyer 004, 005, 008 (blue
dots)
• I will be in the room 060
and mainly look at Julia
problems today.
• Solutions to exercises will
be made available at the
end of the exercise
session.
20 Introduction to Operations Research
About myself
• Contact:
– Email: [email protected]
– Office 144, building 358.
• Background
– Been employed at DTU since 2008
– Professor since 2012.
– Education in Computer Science (University of Copenhagen)
– I do research in operations research.
– Is especially interested in applications within tranport and solution
methods.
– World class research in a few specific areas? My expertice
Operations
research
21 Introduction to Operations Research
Introduction to Linear programming (LP)
Programming = make a program = planning
Content of chapter 3
• 3. Introduction to LP
• 3.1 Prototype example: Wyndor
• 3.2 LP-model
• 3.3 Assumptions for LP
• 3.4 More examples
22 Introduction to Operations Research
3.1 Wyndor: problem
• 2 products (glass doors, windows)
• Requires time on 3 plants
1 2 Capacity
(hours/week)
1 1 0 4
2 0 2 12
3 3 2 18
profit 3 5
• Profit is per unit and should be multiplied by 1000$
• We want to plan the production so that our profit is maximized
23 Introduction to Operations Research
3.1 Wyndor model
1 2 Capacity
(Hours/week)
1 1 0 4
2 0 2 12
3 3 2 18
profit 3 5
24 Introduction to Operations Research
3.1 Wyndor model
1 2 Capacity
(Hours/week)
1 1 0 4
2 0 2 12
3 3 2 18
profit 3 5
25 Introduction to Operations Research
3.1 Wyndor model
1 2 Capacity
(Hours/week)
1 1 0 4
2 0 2 12
3 3 2 18
profit 3 5
26 Introduction to Operations Research
3.1 Wyndor model
1 2 Capacity
(Hours/week)
1 1 0 4
2 0 2 12
3 3 2 18
profit 3 5
27 Introduction to Operations Research
Wyndor solution
9
0
0 1 2 3 4 5 6
28 Introduction to Operations Research
Wyndor solution
9
Z=30
4
Z=36
3
2
Z=21
1 Z=15
0
0 2 4 6 8 10 12
29 Introduction to Operations Research
3.2 LP-model in general
30 Introduction to Operations Research
3.2 LP-model in general
31 Introduction to Operations Research
“Our” standard form
32 Introduction to Operations Research
Terminology
Terminology
• Feasible solution
• Infeasible solution
• Feasible region
• Optimal solution
• Objective function
• Objective value
• Unbounded solution
• Corner-point feasible solution – CPF
33 Introduction to Operations Research
Assumptions for linear programming
34 Introduction to Operations Research
3.4 Examples
• p. 52 Design of Radiation Therapy
• p. 56 Controlling Air Pollution
• p. 60 Distributing Goods Through a Distribution Network
• Personnel Scheduling (from an earlier version of the book)
35 Introduction to Operations Research
p. 45 Design of Radiation Therapy
36 Introduction to Operations Research
p. 45 Radiation Therapy: model
37 Introduction to Operations Research
p. 45 Radiation Therapy: solution
38 Introduction to Operations Research
Modelbuilding – how to?
39 Introduction to Operations Research
Personnel Scheduling
Personnel Scheduling: model
41
Personnel Scheduling - solution
42
Solve LP models using software
• See Julia slides
43 Introduction to Operations Research
End of lectures!
Let’s work with the exercises
44 Introduction to Operations Research
