Reader for the course Operations Research with examples and detailed explanation of the substance, based on the book: Introduction to Operations Research (10th edition - International Edition) - Hillier & Lieberman.
operations research technical business administration industrial engineering
Connected book
Book Title:
Author(s):
Edition:
ISBN:
Edition:
Written for
Rijksuniversiteit Groningen (RuG)
Industrial Engineering and Management
Operations Research (WBIE18003)
All documents for this subject (1)
Seller
Follow
LeYaoo
Reviews received
Content preview
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 𝑍
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller LeYaoo. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.89. You're not tied to anything after your purchase.
