University of Vaasa Department of Mathematics and Statistics
Faculty of Technology

ORMS1020 Operations Research / Operaatioanalyysi, Fall / Syksy 2016

Huom: Luennot ovat suomeksi, mutta kaikki materiaali on englanniksi. Kokeissa ja harjoituksissa voi vastata joko suomeksi tai englanniksi.

N.B. Lectures are in Finnish, but all the material is in English. In the exams and the exercises you may answer either in Finnish or in English.

N.B. The STATUS parameter shas been changed in glpk for Octave version 4.0.3. Therefore the status parameter in stu_lp_solver is incorrect.

Huom: Kurssin luentomuistiinpanojen linkki Matti Laaksosen suomenkielisiin operaatioanalyysin luentomuistiinpanoihin on virheellinen. Oikea linkki on http://lipas.uwasa.fi/~mla/orms1020/oamoniste2012.pdf.

Lecturer

Tommi Sottinen

Scope

5 cr

Contents

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.

    1. 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"
          round( max( 0, min(10p-4, 5) ) )
        where
          p = a + 0.5(1-a)b
        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.)
    2. Week 38: In the second exercise set we get a first glimpse of optimization problems and study programming with GNU Octave.
      1. Exercise 1.2.
      2. Exercise 2.3.
      3. Exercise 2.4.
      4. Exercise 2.5.
      5. The STATUS parameter shas been changed in glpk for Octave version 4.0.3. Therefore the status parameter in stu_lp_solver is incorrect. Correct this bug for the function stu_lp_solver.
    3. Week 39: Here we consider LPs and their optima, and our our implementation of the Simplex Algorithm.
      1. Exercise 3.1.
      2. Exercise 3.2.
      3. Exercise 3.3.
      4. Exercise 4.1.
      5. Make the following Octave function (m-file). The function takes a matrix as its input parameter. It returns the input matrix where all but the first row and the last column are replaced by zeros.
    4. Week 40: Here we study the Simplex Algorithm, and sensitivity and duality.
      1. Exercise 4.4.
      2. Exercise 4.5.
      3. Exercise 5.2.
      4. Exercise 5.3.
      5. Exercise 5.5.
    5. Week 41: Here we study Data Envelopment Analysis and Transportation Problems.
      1. Exercise 6.1.
      2. Exercise 6.2.
      3. Exercise 7.1.
      4. Exercise 7.3.
      5. Exercise 7.4.
    6. Week 42: Here we study Transportation-type problems, Integer programming (IP) and the traveling salesman problem.
      1. Exercise 7.5.
      2. Exercise 8.1.
      3. Exercise 8.2.
      4. Exercise 9.1.
      5. Find a mistake in the lecture notes.

    Lectures

    • Wed 14-16 F118 (week 36)
    • Wed 14-16 F141 (weeks 37-41)
    • Thu 10-12 F118 (week 36)
    • Thu 10-12 F141 (weeks 37-40)
    • Thu 10-12 F426 (week 41)
    • Fri 10-12 F426 (week 36)
    • Fri 10-12 F141 (weeks 37-41)

    Preliminary schedule for the lectures:

                               Wednesday Thursday Friday
    Week 36: Orientation Chapters 1-2 Chapter 2
    Week 37: Chapters 2-3 Chapter 3 Chapters 3-4
    Week 38: Chapter 4 Chapter 4 Chapters 4-5
    Week 39: Chapter 5 Chapter 6 Chapter 6
    Week 40: Chapter 7 Chapter 7 Chapter 7
    Week 41: Chapter 8 Chapter 9 Canceled

    Exercises

    • 1. Tue 14-16 TF4109 (weeks 37-40, 42)
    • 1. Tue 12-14 TF4109 (week 41)
    • 2. Wed 16-18 TF3102 (weeks 37-42) English group
    • 3. Thu 08-10 TF4109 (weeks 37-42)
    • 4. Thu 14-16 TF4109 (weeks 37-42)

    Exams

    The dates of the final exams are (most likely)

    • Fri Oct 28 at 12-15
    • Sat Dec 10 at 12-15

    Here are some old final exams with solutions:

    Grading

    Your grade will be given by the formula

      round( max( 0, min(10p-4, 5) ) )

    where

      p = a + 0.5(1-a)b

    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 exam you take after the course, i.e. then b=0.