ORMS 1020 Operaatioanalyysi / Operations Research, Syksy / Fall 2011

Huom: Varsinaiset luennot (Sottinen) ovat suomeksi, mutta kurssimateriaali on englanniksi. Tiivistetyt luennot (Wietsma) ovat englanniksi. Harjoitusryhmät ovat suomeksi (Laaksonen, Sottinen) ja englanniksi (Wietsma). Kokeissa ja harjoituksissa voi vastata joko suomeksi tai englanniksi.

N.B. Lectures (Sottinen) are in Finnish, but the course material is in English. Concentrated lectures (Wietsma) are in English. Exercise groups are in Finnish (Laaksonen, Sottinen) and in English (Wietsma). In exams and in exercises you may answer either in Finnish or in English.

Lecturer

Tommi Sottinen

Scope

5 cr

Linear modeling; solving linear programs with Octave; simplex algorithm; sensitivity analysis and duals for linear programs; data envelopment analysis; transportation problems; assignment problems; transshipment problems; mixed integer linear programming; branch-and-bound algorithm; traveling salesman problem; fixed-charge problem; set-covering problem.

Course Material

Lecture notes ORMS 1020: Operations Research with GNU Octave (October 19, 2011) by Tommi Sottinen and the M-files

first_simplex_tableau.m

is_optimal_simplex_tableau.m

maya_travels.m (script file)

new_simplex_tableau.m

npv.m

simplex_lp_solver.m

stu_lp_solver.m

trans_solver.m

Weekly Exercise Sets

The numbers after "Exercise" refer to the Lecture notes.

Week 37: In the first exercise set we get a first glimpse of the GNU Octave programming language. See pages 14-27 of the Lecture Notes or Octave Manual to get help for these exercises.
1. Make Octave print "Hello World!" to the screen. (Type help disp to get help, or if you are a C programmer, type help printf.)
2. Exercise 2.1.
3. Exercise 2.2.
4. Make Octave give a wrong answer due to rounding errors.
5. Visualize the "grading function"
  where
  and a is your percentage of points from the exam and b is the percentage of the exercises you have completed, by using the Octave's plotting functions. (This exercise is very demanding. See Octave Manual: Plotting for help. Also typing help contourf may be useful.)
Solutions: Slides by M.L. and a script file by T.S.
Week 38: In the second exercise set we get a first glimpse of optimization problems and study programming with GNU Octave.
1. Exercise 1.1.
2. Exercise 1.2.
3. Exercise 2.3.
4. Exercise 2.4.
5. Exercise 2.5.
Solutions: Slides by M.L. and a script file by T.S.
Week 39: Here we mainly consider LPs and their optima in general level.
1. Exercise 3.1.
2. Exercise 3.2.
3. Exercise 3.3.
4. Exercise 3.4.
5. (a) Is it possible that LP has no optima, but it is nevertheless bounded? This means that your value z is bounded by some number, but one can still always make any given decision better. (b) Is the previous possible for any optimization problem?
Solutions: Slides by M.L. and a script file by M.L. & T.S. Also, here is a function file corners.m by R.W. that solves LPs by checking corners.
Week 40: Here we study the Simplex Algorithm, especially its implementation.
1. Exercise 4.2.
2. Exercise 4.3.
3. Exercise 4.4.
4. Exercise 4.5.
5. Exercise 4.6.
Solutions: Slides by M.L. and a script file by T.S.
Week 41: Here we study sensitivity and duality, and begin to study Data Envelopment Analysis.
1. Exercise 5.2.
2. Exercise 5.3.
3. Exercise 5.4.
4. Exercise 5.5.
5. Exercise 6.1.
Solutions: Slides by M.L. and a script file (program) by T.S.

Week 42: Here we study Date Envelopment Analysis, Transportation problems and Assignment problems.

Exercise 6.2.
Exercise 6.3.
Exercise 7.1.

An employer must assign 5 jobs to his 5 employees. The time it takes for each employee to complete each job is given in the table below. The employer wants to minimize the total time (since the employees are paid by the hour). How should the employer assign the jobs assuming that each employer can take only one job?

	Job 1	Job 2	Job 3	Job 4	Job 5
Employee 1	11	10	10	10	1
Employee 2	19	18	18	19	20
Employee 3	17	19	17	19	21
Employee 4	18	17	18	17	19
Employee 5	98	97	99	99	31

Exercise 7.3.

Solutions: Slides by M.L. and a script file (program) by T.S.

Week 43: Here in the last exercises we consider transportation-type problems and MILPs.
1. Exercise 7.5.
2. Exercise 8.1.
3. Exercise 9.1.
4. Exercise 9.8.
5. Some typos are corrected from the Lecture Notes. Some typos or even serious mistakes are still probably left. Find at least one.
Solutions: Slides by M.L.

Lectures

Lectures (by Tommi Sottinen, in Finnish):

Wed 12-14 Weeks 37-39 Room F652
Thu 14-16 Weeks 37-42 Room F652
Fri 8-10 Weeks 37-42 Room F652
Wed 12-14 Weeks 40-40 Room F119
Wed 12-14 Weeks 41-42 Room F652

Concentrated Lectures (by Rudi Wietsma, in English)

Mon 14-15 Weeks 37-42 Room D115
Mon 10-11 Weeks 43-43 Room D115

Preliminary schedule (for Lectures by Tommi Sottinen):

	Wednesday	Thursday	Friday
Week 37:	Chapter 1	Sections 2.1 - 2.2	Sections 2.3 - 2.4
Week 38:	Sections 2.5 - 3.1	Sections 3.2 - 3.3	Sections 3.4 - 4.1
Week 39:	Sections 4.2 - 4.4	Section 4.5	Section 5.1
Week 40:	Sections 5.2,	Sections 5.3 - 5.4, 6.1	Sections 6.2 - 6.3
Week 41:	Sections 6.4 - 7.1	Section 7.1	Section 7.2
Week 42:	Sections 7.3 - 8.2	Section 9.1	Sections 9.2 - 9.3

Exercises

There are 4 exercise groups:

Mon 10-12 Weeks 37-43 Room TF4106 (by Matti Laaksonen, in Finnish)
Mon 12-14 Weeks 37-43 Room TF4106 (by Matti Laaksonen, in Finnish)
Thu 12-14 Weeks 37-42 and Thu 10-12 Weeks 43-43 Room TF4106 (by Rudi Wietsma, in English)
Fri 10-12 Weeks 37-43 Room TF4106 (by Tommi Sottinen, in Finnish)

Exams

The dates of the final exams for the course are:

Fri 4.11.2011
Sat 17.12.2011
Sat 4.2.2012

Here are some old final exams with solutions:

Grading

Your grade will be given by the formula

where

and a is your percentage of points from the exam and b is the percentage of the exercises you have completed. The additional points b are not transferable beyond the first final exams you take after the course, i.e. then b=0.