Operations Research
1
,Contents
Operations Research 1
Lecture 1. Introduction to Linear Programming & Formulating
Problems 1
1.1. Outline of Lecture 1
1.2. Disclaimer 1
1.3. What is Operations Research? 2
1.4. What is Linear Programming? 3
1.5. Formulating a Problem as a Linear Program 4
1.6. Linear Programming Assumptions 9
1.7. Some Examples 10
Lecture 2. Solving the LP: The Graphical Method 17
2.1. Outline of Lecture 17
2.2. Solving LPs 17
2.3. Graphical Method (2 Variable LPs) 17
2.4. Terminology 21
2.5. Some Examples 22
Lecture 3. Analysing the Solution: Graphical Sensitivity Analysis 33
3.1. Outline of Lecture 33
3.2. What is Sensitivity Analysis? 33
3.3. Changing the Objective Function Coefficient of a Variable
(Range of Optimality) 35
3.4. Changing the RHS of a Constraint (Range of Feasibility) 40
3.5. Determining How a Change in the RHS of a Constraint
Affects the Optimal Decision Variable Values 41
3.6. Dual Prices (Shadow Prices) 44
, LECTURE 1. INTRO TO LP & FORMULATING PROBLEMS 1
LECTURE 1
Introduction to Linear Programming &
Formulating Problems
1.1. Outline of Lecture
• What is Operations Research?
• What is Linear Programming?
• Formulating a Problem as a Linear Program
• Linear Programming Assumptions
• Some Examples
1.2. Disclaimer
This set of notes is not a replacement for the textbook itself. They merely
summarise the main ideas from each lecture.
These notes are a work in progress. In the event of any discrepancies
or contradictions between these notes and the textbook, trust the text-
book.
It is not enough to do all of your learning in class. You are advised to
do your own reading and attempt problems in the textbook outside
of class.
, 2 AR & NSNK, OPERATIONS RESEARCH
1.3. What is Operations Research?
Operations Research (OR) is a scientific approach that seeks to best
design and operate a system, usually under conditions requiring the
allocation of scarce resources.
OR began in World War II, when British military leaders asked scientists
and engineers to analyse several military problems
• Deployment of radar.
• Management of convoy, bombing, antisubmarine, and min-
ing operations.
After the war, applications of OR extended beyond the military into
many different industries. Today, OR plays an important role in indus-
tries such as:
• Airline - scheduling planes and crews, determining fleet sizes.
• Finance - marketing, credit scoring.
• Logistics - route planning, vehicle scheduling.
Our main interest is in a branch of OR known as optimisation, which
uses mathematical techniques to determine the best (or optimal) choice
to make when faced with many suitable (or feasible) options. To be
even more specific, we are interested in the branch of optimisation
known as Linear Programming.
In the beginning of this course, we will be using Linear Programming
methods to:
• MODEL
- Formulate the problem, express it mathematically.
• SOLVE
- Graphical Method.
- Simplex Method.
- M -Method.
- Two-Phase Method.
• ANALYZE
- Sensitivity Analysis.
We will then move on to using specialised solution methods tailored to
specific problem types, namely:
• Shortest Path Problem.
• Minimum Spanning Tree Problem.
• Project Management.
• Game Theory.
1
,Contents
Operations Research 1
Lecture 1. Introduction to Linear Programming & Formulating
Problems 1
1.1. Outline of Lecture 1
1.2. Disclaimer 1
1.3. What is Operations Research? 2
1.4. What is Linear Programming? 3
1.5. Formulating a Problem as a Linear Program 4
1.6. Linear Programming Assumptions 9
1.7. Some Examples 10
Lecture 2. Solving the LP: The Graphical Method 17
2.1. Outline of Lecture 17
2.2. Solving LPs 17
2.3. Graphical Method (2 Variable LPs) 17
2.4. Terminology 21
2.5. Some Examples 22
Lecture 3. Analysing the Solution: Graphical Sensitivity Analysis 33
3.1. Outline of Lecture 33
3.2. What is Sensitivity Analysis? 33
3.3. Changing the Objective Function Coefficient of a Variable
(Range of Optimality) 35
3.4. Changing the RHS of a Constraint (Range of Feasibility) 40
3.5. Determining How a Change in the RHS of a Constraint
Affects the Optimal Decision Variable Values 41
3.6. Dual Prices (Shadow Prices) 44
, LECTURE 1. INTRO TO LP & FORMULATING PROBLEMS 1
LECTURE 1
Introduction to Linear Programming &
Formulating Problems
1.1. Outline of Lecture
• What is Operations Research?
• What is Linear Programming?
• Formulating a Problem as a Linear Program
• Linear Programming Assumptions
• Some Examples
1.2. Disclaimer
This set of notes is not a replacement for the textbook itself. They merely
summarise the main ideas from each lecture.
These notes are a work in progress. In the event of any discrepancies
or contradictions between these notes and the textbook, trust the text-
book.
It is not enough to do all of your learning in class. You are advised to
do your own reading and attempt problems in the textbook outside
of class.
, 2 AR & NSNK, OPERATIONS RESEARCH
1.3. What is Operations Research?
Operations Research (OR) is a scientific approach that seeks to best
design and operate a system, usually under conditions requiring the
allocation of scarce resources.
OR began in World War II, when British military leaders asked scientists
and engineers to analyse several military problems
• Deployment of radar.
• Management of convoy, bombing, antisubmarine, and min-
ing operations.
After the war, applications of OR extended beyond the military into
many different industries. Today, OR plays an important role in indus-
tries such as:
• Airline - scheduling planes and crews, determining fleet sizes.
• Finance - marketing, credit scoring.
• Logistics - route planning, vehicle scheduling.
Our main interest is in a branch of OR known as optimisation, which
uses mathematical techniques to determine the best (or optimal) choice
to make when faced with many suitable (or feasible) options. To be
even more specific, we are interested in the branch of optimisation
known as Linear Programming.
In the beginning of this course, we will be using Linear Programming
methods to:
• MODEL
- Formulate the problem, express it mathematically.
• SOLVE
- Graphical Method.
- Simplex Method.
- M -Method.
- Two-Phase Method.
• ANALYZE
- Sensitivity Analysis.
We will then move on to using specialised solution methods tailored to
specific problem types, namely:
• Shortest Path Problem.
• Minimum Spanning Tree Problem.
• Project Management.
• Game Theory.
