Operations Research Reader – 2019/2020 IEM
Introduction to Operations Research, 10th edition (2015)
Operations Research Reader 2019/2020 – IEM
Book: Introduction to Operations Research, 10th edition, 2015 (some, less important, figures and
graphs are only referred to but not showed in this reader)
Overview
Overview of the Course.......................................................................................................................3
Lecture 1: Linear Programming ...........................................................................................................3
Chapter 3 Introduction to Linear Programming ...............................................................................3
3.1 Prototype Example (Wyndor Glass CO. problem) ..................................................................3
3.2 The Linear Programming Model.............................................................................................4
3.3 Assumptions of Linear Programming .....................................................................................5
3.4 Other Examples .....................................................................................................................6
Chapter 4 Solving Linear Programming Problems: The Simplex Method ..........................................6
4.1 The Essence of the Simplex Method ......................................................................................6
4.2 Setting up the Simplex Method .............................................................................................7
Lecture 2: Linear Programming ...........................................................................................................8
4.3 The Algebra of the Simplex Method .......................................................................................8
4.4 The Simplex Method in Tabular Form ....................................................................................9
4.6 Adapting to Other Model Forms .......................................................................................... 11
Lecture 3: Linear Programming ......................................................................................................... 12
Chapter 5 The Theory of the Simplex Method ............................................................................... 12
5.2 The Simplex Method in Matrix Form .................................................................................... 12
5.3 A Fundamental Insight......................................................................................................... 15
Chapter 4 Solving Linear Programming Problems: the Simplex Method ......................................... 16
4.7 Postoptimality Analysis........................................................................................................ 16
Chapter 6 Duality Theory .............................................................................................................. 16
6.1 The Essence of Duality Theory ............................................................................................. 16
6.2 Economic Interpretation of Duality ...................................................................................... 18
Lecture 4: Linear Programming ......................................................................................................... 18
Chapter 7 Linear Programming under Uncertainty ........................................................................ 18
7.1 The Essence of Sensitivity Analysis....................................................................................... 18
7.2 Applying Sensitivity Analysis ................................................................................................ 21
Lecture 5: Transportation Problem ................................................................................................... 26
Chapter 9: The Transportation and Assignment Problems ............................................................. 26
9.1 The Transportation Problem ................................................................................................ 26
9.2 A Streamlined Simplex Method for the Transportation Problem .......................................... 27
Lecture 6: Network Optimization Problems ....................................................................................... 31
Chapter 10: Network Optimization Problems ................................................................................ 31
,Operations Research Reader – 2019/2020 IEM
Introduction to Operations Research, 10th edition (2015)
10.1 Prototype Example ............................................................................................................ 31
10.2 The Terminology of the Networks ...................................................................................... 31
10.3 The Shortest-Path Problem ................................................................................................ 31
10.4 The Minimum Spanning Tree Problem ............................................................................... 32
10.5 The Maximum Flow Problem ............................................................................................. 33
Lecture 7: Integer Linear Programming ............................................................................................. 35
Chapter 12: Integer Programming ................................................................................................. 35
12.1 Prototype Example ............................................................................................................ 35
12.2 Some BIP Applications (yes-or-no decision) ....................................................................... 35
12.3 Innovative Uses of Binary Variables ................................................................................... 36
12.4 Some Formulation Examples ............................................................................................. 39
Lecture 8: Integer Linear Programming ............................................................................................. 42
12.5 Some Perspectives on Solving Integer Programming Problems .......................................... 42
12.6 The Branch-And-Bound Technique and its Applications to Binary Integer Programming .... 42
,Operations Research Reader – 2019/2020 IEM
Introduction to Operations Research, 10th edition (2015)
Operations Research Reader 2019/2020 – IEM
Book: Introduction to Operations Research, 10th edition, 2015 (some, less important, figures and
graphs are only referred to but not showed in this reader)
Overview of the Course
1. Linear Programming – Ch. 3.1-4, 4.1-2
2. Linear Programming – Ch. 4.3-4, 4.6
3. Linear Programming – Ch. 5.2-3, p. 135-136, Ch. 6.1-2
4. Linear Programming – Ch. 7.1-2
5. Transportation Problem – Ch. 9.1-2 (course material differs slightly from book)
6. Network Optimization Models – Ch. 10.1-5
7. Integer Linear Programming – Ch. 12.1-4
8. Integer Linear Programming – Ch. 12.5-6, (12.8)
Lecture 1: Linear Programming
Ch. 3.1-4, 4.1-2
Chapter 3 Introduction to Linear Programming
Linear programming (LP) uses a mathematical model to describe the problem of concern. Linear
means that all mathematical functions are required to be linear functions. Programming refers to the
planning of activities to obtain an optimal result. An efficient solution procedure, called the simplex
method, is available for solving LP problems.
3.1 Prototype Example (Wyndor Glass CO. problem)
Wyndor Glass Co. has three plants and two products to be made.
- Product 1 requires production capacity of plants 1 and 3.
- Product 2 requires production capacity of plants 2 and 3.
Problem statement: determine what production rates for the two products maximize total profit?
Take into account limited production capacity restrictions. Any combination that satisfies the
restrictions is permitted, including producing none of one product and as much as possible of the
other (=product mix problem).
Information needed:
1. Number of hours of production time available per week per plant.
2. Number of hours of production time used per plant for each batch produced per product.
3. Profit per batch produced.
Data for Wyndor Glass
Co. Problem (table 3.1)
, Operations Research Reader – 2019/2020 IEM
Introduction to Operations Research, 10th edition (2015)
Formulation as a Linear Programming Problem
Problem statement indicates that the decision variables (x1,x2,…,xn) are:
- 𝑥1 = number of produced product 1
- 𝑥2 = number of produced product 2
These decision values must be chosen to maximize the objective function:
𝑍 = 3𝑥1 + 5𝑥2
Subject to the restrictions imposed on these variables:
𝑥1 ≤ 4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
and
𝑥1 ≥ 0 𝑎𝑛𝑑 𝑥2 ≥ 0
Graphical Solution
Small problems (2 decision variables) can be solved by the
graphical solution.
1. Find values of 𝑥1 , 𝑥2 that are permitted by the
restrictions.
2. The resulting region of permissible values of 𝑥1 , 𝑥2
is called the feasible region.
3. Pick the point in this feasible region that
maximizes the value of the objective function:
𝑍 = 3𝑥1 + 5𝑥2
This is done by trial and error. The equation in the
3 1
form 𝑥2 = − 5𝑥 + 5 𝑍 is the slope-intercept form
1
of the object function, it demonstrates that the
3 1
slope is − and the intercept is 𝑍. The slope is fixed so all lines constructed this way are
5 5
parallel. The line that passes through the point (2,6) gives the largest value of 𝑍 and is the
optimal solution: 𝑥1 = 2, 𝑥2 = 6 filling this in for 𝑍 = 3𝑥1 + 5𝑥2 gives 𝑍 = 36.
It is sufficient to form a single line with a rules to establish the slope, then move this through the
feasible region in the direction of improving 𝑍 (or to minimize if that is the objective). This procedure
is referred to as the graphical method for linear programming.
To answer the problem statement: since for the optimal solution 𝑥1 = 2, 𝑥2 = 6 with 𝑍 = 36 →
product 1 should be produced at a rate of 2 batches per week, product 2 at 5 batches per week,
which gives a profit of $36.000 per week.
3.2 The Linear Programming Model
Common terminology for LP (table 3.2)
Prototype Example General Problem
Production capacities of plants Resources
3 plants 𝑚 resources
Production of products Activities
2 products 𝑛 activities
Production rate of product 𝑗, 𝑥𝑗 Level of activity 𝑗, 𝑥𝑗
Profit 𝑍 Overall measure of performance 𝑍
Introduction to Operations Research, 10th edition (2015)
Operations Research Reader 2019/2020 – IEM
Book: Introduction to Operations Research, 10th edition, 2015 (some, less important, figures and
graphs are only referred to but not showed in this reader)
Overview
Overview of the Course.......................................................................................................................3
Lecture 1: Linear Programming ...........................................................................................................3
Chapter 3 Introduction to Linear Programming ...............................................................................3
3.1 Prototype Example (Wyndor Glass CO. problem) ..................................................................3
3.2 The Linear Programming Model.............................................................................................4
3.3 Assumptions of Linear Programming .....................................................................................5
3.4 Other Examples .....................................................................................................................6
Chapter 4 Solving Linear Programming Problems: The Simplex Method ..........................................6
4.1 The Essence of the Simplex Method ......................................................................................6
4.2 Setting up the Simplex Method .............................................................................................7
Lecture 2: Linear Programming ...........................................................................................................8
4.3 The Algebra of the Simplex Method .......................................................................................8
4.4 The Simplex Method in Tabular Form ....................................................................................9
4.6 Adapting to Other Model Forms .......................................................................................... 11
Lecture 3: Linear Programming ......................................................................................................... 12
Chapter 5 The Theory of the Simplex Method ............................................................................... 12
5.2 The Simplex Method in Matrix Form .................................................................................... 12
5.3 A Fundamental Insight......................................................................................................... 15
Chapter 4 Solving Linear Programming Problems: the Simplex Method ......................................... 16
4.7 Postoptimality Analysis........................................................................................................ 16
Chapter 6 Duality Theory .............................................................................................................. 16
6.1 The Essence of Duality Theory ............................................................................................. 16
6.2 Economic Interpretation of Duality ...................................................................................... 18
Lecture 4: Linear Programming ......................................................................................................... 18
Chapter 7 Linear Programming under Uncertainty ........................................................................ 18
7.1 The Essence of Sensitivity Analysis....................................................................................... 18
7.2 Applying Sensitivity Analysis ................................................................................................ 21
Lecture 5: Transportation Problem ................................................................................................... 26
Chapter 9: The Transportation and Assignment Problems ............................................................. 26
9.1 The Transportation Problem ................................................................................................ 26
9.2 A Streamlined Simplex Method for the Transportation Problem .......................................... 27
Lecture 6: Network Optimization Problems ....................................................................................... 31
Chapter 10: Network Optimization Problems ................................................................................ 31
,Operations Research Reader – 2019/2020 IEM
Introduction to Operations Research, 10th edition (2015)
10.1 Prototype Example ............................................................................................................ 31
10.2 The Terminology of the Networks ...................................................................................... 31
10.3 The Shortest-Path Problem ................................................................................................ 31
10.4 The Minimum Spanning Tree Problem ............................................................................... 32
10.5 The Maximum Flow Problem ............................................................................................. 33
Lecture 7: Integer Linear Programming ............................................................................................. 35
Chapter 12: Integer Programming ................................................................................................. 35
12.1 Prototype Example ............................................................................................................ 35
12.2 Some BIP Applications (yes-or-no decision) ....................................................................... 35
12.3 Innovative Uses of Binary Variables ................................................................................... 36
12.4 Some Formulation Examples ............................................................................................. 39
Lecture 8: Integer Linear Programming ............................................................................................. 42
12.5 Some Perspectives on Solving Integer Programming Problems .......................................... 42
12.6 The Branch-And-Bound Technique and its Applications to Binary Integer Programming .... 42
,Operations Research Reader – 2019/2020 IEM
Introduction to Operations Research, 10th edition (2015)
Operations Research Reader 2019/2020 – IEM
Book: Introduction to Operations Research, 10th edition, 2015 (some, less important, figures and
graphs are only referred to but not showed in this reader)
Overview of the Course
1. Linear Programming – Ch. 3.1-4, 4.1-2
2. Linear Programming – Ch. 4.3-4, 4.6
3. Linear Programming – Ch. 5.2-3, p. 135-136, Ch. 6.1-2
4. Linear Programming – Ch. 7.1-2
5. Transportation Problem – Ch. 9.1-2 (course material differs slightly from book)
6. Network Optimization Models – Ch. 10.1-5
7. Integer Linear Programming – Ch. 12.1-4
8. Integer Linear Programming – Ch. 12.5-6, (12.8)
Lecture 1: Linear Programming
Ch. 3.1-4, 4.1-2
Chapter 3 Introduction to Linear Programming
Linear programming (LP) uses a mathematical model to describe the problem of concern. Linear
means that all mathematical functions are required to be linear functions. Programming refers to the
planning of activities to obtain an optimal result. An efficient solution procedure, called the simplex
method, is available for solving LP problems.
3.1 Prototype Example (Wyndor Glass CO. problem)
Wyndor Glass Co. has three plants and two products to be made.
- Product 1 requires production capacity of plants 1 and 3.
- Product 2 requires production capacity of plants 2 and 3.
Problem statement: determine what production rates for the two products maximize total profit?
Take into account limited production capacity restrictions. Any combination that satisfies the
restrictions is permitted, including producing none of one product and as much as possible of the
other (=product mix problem).
Information needed:
1. Number of hours of production time available per week per plant.
2. Number of hours of production time used per plant for each batch produced per product.
3. Profit per batch produced.
Data for Wyndor Glass
Co. Problem (table 3.1)
, Operations Research Reader – 2019/2020 IEM
Introduction to Operations Research, 10th edition (2015)
Formulation as a Linear Programming Problem
Problem statement indicates that the decision variables (x1,x2,…,xn) are:
- 𝑥1 = number of produced product 1
- 𝑥2 = number of produced product 2
These decision values must be chosen to maximize the objective function:
𝑍 = 3𝑥1 + 5𝑥2
Subject to the restrictions imposed on these variables:
𝑥1 ≤ 4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
and
𝑥1 ≥ 0 𝑎𝑛𝑑 𝑥2 ≥ 0
Graphical Solution
Small problems (2 decision variables) can be solved by the
graphical solution.
1. Find values of 𝑥1 , 𝑥2 that are permitted by the
restrictions.
2. The resulting region of permissible values of 𝑥1 , 𝑥2
is called the feasible region.
3. Pick the point in this feasible region that
maximizes the value of the objective function:
𝑍 = 3𝑥1 + 5𝑥2
This is done by trial and error. The equation in the
3 1
form 𝑥2 = − 5𝑥 + 5 𝑍 is the slope-intercept form
1
of the object function, it demonstrates that the
3 1
slope is − and the intercept is 𝑍. The slope is fixed so all lines constructed this way are
5 5
parallel. The line that passes through the point (2,6) gives the largest value of 𝑍 and is the
optimal solution: 𝑥1 = 2, 𝑥2 = 6 filling this in for 𝑍 = 3𝑥1 + 5𝑥2 gives 𝑍 = 36.
It is sufficient to form a single line with a rules to establish the slope, then move this through the
feasible region in the direction of improving 𝑍 (or to minimize if that is the objective). This procedure
is referred to as the graphical method for linear programming.
To answer the problem statement: since for the optimal solution 𝑥1 = 2, 𝑥2 = 6 with 𝑍 = 36 →
product 1 should be produced at a rate of 2 batches per week, product 2 at 5 batches per week,
which gives a profit of $36.000 per week.
3.2 The Linear Programming Model
Common terminology for LP (table 3.2)
Prototype Example General Problem
Production capacities of plants Resources
3 plants 𝑚 resources
Production of products Activities
2 products 𝑛 activities
Production rate of product 𝑗, 𝑥𝑗 Level of activity 𝑗, 𝑥𝑗
Profit 𝑍 Overall measure of performance 𝑍
