Introduction

December 16, 2023

A Starting Example - Bike Replenishment System

▶ Public Bike Sharing is a very efficient and proven way

of decarbonising the transport sector
▶ The company which maintains the Bikes need to check
all Bike stations to make sure they are fully operational
▶ The graph shows the 109 public bike stations in
Dublin. Bike vans need to visit all stations and collect
faulty bikes and transfer them to the maintenance
centre (Black Circle)
▶ The capacity and the number of these vans are limited
▶ The question is “how to optimally dispatch them to do
their mission at minimum traveling costs”.
Origins of Operations Research (OR)

▶ The roots of OR can be traced back many decades when early attempts were
made to use a scientific approach in the management of organizations
Origins of Operations Research (OR)

▶ The roots of OR can be traced back many decades when early attempts were
made to use a scientific approach in the management of organizations
▶ However, the beginning of the activity called “Operations Research” has
generally been attributed to the military services early in World War II
motivated by an urgent need to allocate scarce resources to the various
military operations and to the activities within each operation in an
effective manner
Origins of Operations Research (OR)

▶ The roots of OR can be traced back many decades when early attempts were
made to use a scientific approach in the management of organizations
▶ However, the beginning of the activity called “Operations Research” has
generally been attributed to the military services early in World War II
motivated by an urgent need to allocate scarce resources to the various
military operations and to the activities within each operation in an
effective manner
▶ Therefore, the British and then the U.S. military management called upon a
large number of scientists to apply a scientific approach to dealing with this
and other strategic and tactical problems - “Research” on the Military
“Operations”
Origins of Operations Research (OR)

▶ The roots of OR can be traced back many decades when early attempts were
made to use a scientific approach in the management of organizations
▶ However, the beginning of the activity called “Operations Research” has
generally been attributed to the military services early in World War II
motivated by an urgent need to allocate scarce resources to the various
military operations and to the activities within each operation in an
effective manner
▶ Therefore, the British and then the U.S. military management called upon a
large number of scientists to apply a scientific approach to dealing with this
and other strategic and tactical problems - “Research” on the Military
“Operations”
▶ The success of OR in the war effort spurred interest in applying OR outside
the military as well
Origins of Operations Research (OR)

▶ As the industrial boom following the war was running its course, the problems
caused by the increasing complexity and specialization in organizations were
again coming to the forefront
Origins of Operations Research (OR)

▶ As the industrial boom following the war was running its course, the problems
caused by the increasing complexity and specialization in organizations were
again coming to the forefront
▶ It was becoming apparent to a growing number of people, including business
consultants who had served on or with the OR teams during the war, that
these were basically the same problems that had been faced by the military
but in a different context
Origins of Operations Research (OR)

▶ As the industrial boom following the war was running its course, the problems
caused by the increasing complexity and specialization in organizations were
again coming to the forefront
▶ It was becoming apparent to a growing number of people, including business
consultants who had served on or with the OR teams during the war, that
these were basically the same problems that had been faced by the military
but in a different context
▶ By the early 1950s, these individuals had introduced the use of OR to a
variety of organizations in business, industry, and government. The rapid
spread of OR soon followed
Origins of Operations Research (OR)

▶ As the industrial boom following the war was running its course, the problems
caused by the increasing complexity and specialization in organizations were
again coming to the forefront
▶ It was becoming apparent to a growing number of people, including business
consultants who had served on or with the OR teams during the war, that
these were basically the same problems that had been faced by the military
but in a different context
▶ By the early 1950s, these individuals had introduced the use of OR to a
variety of organizations in business, industry, and government. The rapid
spread of OR soon followed
▶ At least two other factors that played a key role in the rapid growth of OR
during this period can be identified
Origins of Operations Research (OR)

▶ After the war, many of the scientists who had participated on OR teams or
who had heard about this work were motivated to pursue research relevant to
the field - A prime example is the Simplex Method for solving Linear
Programming Problems (LPPs), developed by George Dantzig in 1947
Origins of Operations Research (OR)

▶ After the war, many of the scientists who had participated on OR teams or
who had heard about this work were motivated to pursue research relevant to
the field - A prime example is the Simplex Method for solving Linear
Programming Problems (LPPs), developed by George Dantzig in 1947
▶ Many of the standard methodologies of OR, such as Linear Programming,
Dynamic Programming, Queueing Theory and Inventory Theory, were
relatively well developed before the end of the 1950s
Origins of Operations Research (OR)

▶ After the war, many of the scientists who had participated on OR teams or
who had heard about this work were motivated to pursue research relevant to
the field - A prime example is the Simplex Method for solving Linear
Programming Problems (LPPs), developed by George Dantzig in 1947
▶ Many of the standard methodologies of OR, such as Linear Programming,
Dynamic Programming, Queueing Theory and Inventory Theory, were
relatively well developed before the end of the 1950s
▶ A second factor that gave great impetus to the growth of the field was the
onslaught of the computer revolution. A large amount of computation is
usually required to deal most effectively with the complex problems typically
considered by OR
Origins of Operations Research (OR)

▶ A further boost came in the 1980s with the development of increasingly

powerful personal computers accompanied by good software packages for
doing OR
Origins of Operations Research (OR)

▶ A further boost came in the 1980s with the development of increasingly

powerful personal computers accompanied by good software packages for
doing OR
▶ This brought the use of OR within the easy reach of much larger numbers of
people, and this progress further accelerated in the 1990s and into the 21st
century
Origins of Operations Research (OR)

▶ A further boost came in the 1980s with the development of increasingly

powerful personal computers accompanied by good software packages for
doing OR
▶ This brought the use of OR within the easy reach of much larger numbers of
people, and this progress further accelerated in the 1990s and into the 21st
century
▶ For example, the widely used spreadsheet package, Microsoft Excel, provides
a Solver that will solve a variety of OR problems. Today, literally millions of
individuals have ready access to OR software
Origins of Operations Research (OR)

▶ A further boost came in the 1980s with the development of increasingly

powerful personal computers accompanied by good software packages for
doing OR
▶ This brought the use of OR within the easy reach of much larger numbers of
people, and this progress further accelerated in the 1990s and into the 21st
century
▶ For example, the widely used spreadsheet package, Microsoft Excel, provides
a Solver that will solve a variety of OR problems. Today, literally millions of
individuals have ready access to OR software
▶ Consequently, a whole range of computers from mainframes to laptops now
are being routinely used to solve OR problems, including some of enormous
size
OR for Decision Making

▶ Decision Making - an integral part of process of management - A Search

process
OR for Decision Making

▶ Decision Making - an integral part of process of management - A Search

process
▶ Specifically decision making requires selection of the Best course of action
OR for Decision Making

▶ Decision Making - an integral part of process of management - A Search

process
▶ Specifically decision making requires selection of the Best course of action
▶ Managers must select the best one from a set of available alternatives
OR for Decision Making

▶ Decision Making - an integral part of process of management - A Search

process
▶ Specifically decision making requires selection of the Best course of action
▶ Managers must select the best one from a set of available alternatives
▶ Mostly, managers use “Thumb Rule” or Common Sense in selecting best
alternative - A form of art
OR for Decision Making

▶ Decision Making - an integral part of process of management - A Search

process
▶ Specifically decision making requires selection of the Best course of action
▶ Managers must select the best one from a set of available alternatives
▶ Mostly, managers use “Thumb Rule” or Common Sense in selecting best
alternative - A form of art
▶ “Trial & Error” for manageable decision making problem
OR for Decision Making

▶ Decision Making - an integral part of process of management - A Search

process
▶ Specifically decision making requires selection of the Best course of action
▶ Managers must select the best one from a set of available alternatives
▶ Mostly, managers use “Thumb Rule” or Common Sense in selecting best
alternative - A form of art
▶ “Trial & Error” for manageable decision making problem
▶ Growing complexity of situations require efficient tools and techniques for
decision making
OR for Decision Making

▶ Decision Making - an integral part of process of management - A Search

process
▶ Specifically decision making requires selection of the Best course of action
▶ Managers must select the best one from a set of available alternatives
▶ Mostly, managers use “Thumb Rule” or Common Sense in selecting best
alternative - A form of art
▶ “Trial & Error” for manageable decision making problem
▶ Growing complexity of situations require efficient tools and techniques for
decision making
▶ Operations Research - A bouquet of quantitative techniques facilitating
selection of the best alternative for decision making
Operations Research Society, USA defined OR as
“Operations research is the systematic applications of quantitative methods,
techniques, tools to the analysis of problems involved in the operation of
systems”
OR & Analytics
▶ There has been great buzz throughout the business world in recent years
about something called analytics (or business analytics) and the
importance of incorporating analytics into managerial decision making
OR & Analytics
▶ There has been great buzz throughout the business world in recent years
about something called analytics (or business analytics) and the
importance of incorporating analytics into managerial decision making
▶ The primary impetus for this buzz was a series of articles and books by
Thomas H. Davenport, a renowned thought-leader who has helped
hundreds of companies worldwide to revitalize their business practices
OR & Analytics
▶ There has been great buzz throughout the business world in recent years
about something called analytics (or business analytics) and the
importance of incorporating analytics into managerial decision making
▶ The primary impetus for this buzz was a series of articles and books by
Thomas H. Davenport, a renowned thought-leader who has helped
hundreds of companies worldwide to revitalize their business practices
▶ In January 2006 issue of the Harvard Business Review with an article,
“Competing on Analytics”, that now has been named as one of the ten
must-read articles in that magazine’s 90-year history
OR & Analytics
▶ There has been great buzz throughout the business world in recent years
about something called analytics (or business analytics) and the
importance of incorporating analytics into managerial decision making
▶ The primary impetus for this buzz was a series of articles and books by
Thomas H. Davenport, a renowned thought-leader who has helped
hundreds of companies worldwide to revitalize their business practices
▶ In January 2006 issue of the Harvard Business Review with an article,
“Competing on Analytics”, that now has been named as one of the ten
must-read articles in that magazine’s 90-year history
▶ So what is analytics? The short (but oversimplified) answer is that it is
basically operations research by another name with some differences in their
relative emphases
OR & Analytics
▶ There has been great buzz throughout the business world in recent years
about something called analytics (or business analytics) and the
importance of incorporating analytics into managerial decision making
▶ The primary impetus for this buzz was a series of articles and books by
Thomas H. Davenport, a renowned thought-leader who has helped
hundreds of companies worldwide to revitalize their business practices
▶ In January 2006 issue of the Harvard Business Review with an article,
“Competing on Analytics”, that now has been named as one of the ten
must-read articles in that magazine’s 90-year history
▶ So what is analytics? The short (but oversimplified) answer is that it is
basically operations research by another name with some differences in their
relative emphases
▶ A very short definition of Analytics can be given as:
”Analytics is the scientific process of transforming data into insight for
making better decisions”
OR & Analytics
▶ There has been great buzz throughout the business world in recent years
about something called analytics (or business analytics) and the
importance of incorporating analytics into managerial decision making
▶ The primary impetus for this buzz was a series of articles and books by
Thomas H. Davenport, a renowned thought-leader who has helped
hundreds of companies worldwide to revitalize their business practices
▶ In January 2006 issue of the Harvard Business Review with an article,
“Competing on Analytics”, that now has been named as one of the ten
must-read articles in that magazine’s 90-year history
▶ So what is analytics? The short (but oversimplified) answer is that it is
basically operations research by another name with some differences in their
relative emphases
▶ A very short definition of Analytics can be given as:
”Analytics is the scientific process of transforming data into insight for
making better decisions”
▶ The application of analytics can be divided into three overlapping categories
OR & Analytics
▶ First one of these is descriptive analytics, which involves “using innovative
techniques to locate the relevant data and identify the interesting patterns in
order to better describe and understand what is going on now”
OR & Analytics
▶ First one of these is descriptive analytics, which involves “using innovative
techniques to locate the relevant data and identify the interesting patterns in
order to better describe and understand what is going on now”
▶ A second (and more advanced) category is predictive analytics, which
involves “using the data to predict what will happen in the future”
OR & Analytics
▶ First one of these is descriptive analytics, which involves “using innovative
techniques to locate the relevant data and identify the interesting patterns in
order to better describe and understand what is going on now”
▶ A second (and more advanced) category is predictive analytics, which
involves “using the data to predict what will happen in the future”
▶ The final (and most advanced) category is prescriptive analytics, which
involves “using the data to prescribe what should be done in the future”. The
powerful optimization techniques of operations research generally are used
here
OR & Analytics
▶ First one of these is descriptive analytics, which involves “using innovative
techniques to locate the relevant data and identify the interesting patterns in
order to better describe and understand what is going on now”
▶ A second (and more advanced) category is predictive analytics, which
involves “using the data to predict what will happen in the future”
▶ The final (and most advanced) category is prescriptive analytics, which
involves “using the data to prescribe what should be done in the future”. The
powerful optimization techniques of operations research generally are used
here
▶ OR analysts also often deal with all three of these categories, but somewhat
more with the second one, and heavily with the last one
OR & Analytics
▶ First one of these is descriptive analytics, which involves “using innovative
techniques to locate the relevant data and identify the interesting patterns in
order to better describe and understand what is going on now”
▶ A second (and more advanced) category is predictive analytics, which
involves “using the data to predict what will happen in the future”
▶ The final (and most advanced) category is prescriptive analytics, which
involves “using the data to prescribe what should be done in the future”. The
powerful optimization techniques of operations research generally are used
here
▶ OR analysts also often deal with all three of these categories, but somewhat
more with the second one, and heavily with the last one
▶ Thus, OR can be thought of as focusing mainly on advanced
analytics-predictive and prescriptive activities-whereas analytics professionals
might get more involved than OR analysts with the entire business process,
including what precedes the first category (identifying a need) and what
follows the last category (implementation)
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined -
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms -
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms - Constraints
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms - Constraints
3. Determine the criterion or criteria to evaluate the Decision Variable
alternatives either to be maximized or minimized -
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms - Constraints
3. Determine the criterion or criteria to evaluate the Decision Variable
alternatives either to be maximized or minimized - Objective Function(s)
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms - Constraints
3. Determine the criterion or criteria to evaluate the Decision Variable
alternatives either to be maximized or minimized - Objective Function(s)
4. Determine the set of possible alternatives obeying the identified
constraints -
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms - Constraints
3. Determine the criterion or criteria to evaluate the Decision Variable
alternatives either to be maximized or minimized - Objective Function(s)
4. Determine the set of possible alternatives obeying the identified
constraints - Candidate Solutions
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms - Constraints
3. Determine the criterion or criteria to evaluate the Decision Variable
alternatives either to be maximized or minimized - Objective Function(s)
4. Determine the set of possible alternatives obeying the identified
constraints - Candidate Solutions
5. Evalutate the alternatives -
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms - Constraints
3. Determine the criterion or criteria to evaluate the Decision Variable
alternatives either to be maximized or minimized - Objective Function(s)
4. Determine the set of possible alternatives obeying the identified
constraints - Candidate Solutions
5. Evalutate the alternatives - Evaluate candidate solutions based on
Objective Function
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms - Constraints
3. Determine the criterion or criteria to evaluate the Decision Variable
alternatives either to be maximized or minimized - Objective Function(s)
4. Determine the set of possible alternatives obeying the identified
constraints - Candidate Solutions
5. Evalutate the alternatives - Evaluate candidate solutions based on
Objective Function
6. Choose the “best” alternative -
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms - Constraints
3. Determine the criterion or criteria to evaluate the Decision Variable
alternatives either to be maximized or minimized - Objective Function(s)
4. Determine the set of possible alternatives obeying the identified
constraints - Candidate Solutions
5. Evalutate the alternatives - Evaluate candidate solutions based on
Objective Function
6. Choose the “best” alternative - Optimal Solution
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms - Constraints
3. Determine the criterion or criteria to evaluate the Decision Variable
alternatives either to be maximized or minimized - Objective Function(s)
4. Determine the set of possible alternatives obeying the identified
constraints - Candidate Solutions
5. Evalutate the alternatives - Evaluate candidate solutions based on
Objective Function
6. Choose the “best” alternative - Optimal Solution
7. Evaluate the problem formulation and solution(s) for some unseen
scenario(s)
Decision Making and its Framework
Any decision making problem follows the following steps
1. Identify the unknown quantity(ies) to be determined - Decision Variable(s)
2. Identify and define the restrictions or boundaries on resources in terms of
Decision Variables in algebraic forms - Constraints
3. Determine the criterion or criteria to evaluate the Decision Variable
alternatives either to be maximized or minimized - Objective Function(s)
4. Determine the set of possible alternatives obeying the identified
constraints - Candidate Solutions
5. Evalutate the alternatives - Evaluate candidate solutions based on
Objective Function
6. Choose the “best” alternative - Optimal Solution
7. Evaluate the problem formulation and solution(s) for some unseen
scenario(s) - Model Validation
8. Implement the solution(s)
Formulation I - Product Mix Problem

Reddy Mikks produces both interior and exterior paints from two raw materials, M1
and M2 . The following table provides the basic data of the problem:

Exterior Paint Interior Paint Availability

Raw Material M1 6 4 24
Raw Material M2 1 2 6
Profit (’000 Rs) per Ton 5 4

The daily demand for interior paint cannot exceed that for exterior paint by more
than 1 ton. Also, the maximum daily demand for interior paint is 2 tons. Reddy
Mikks wants to determine the optimum (best) product mix of interior and exterior
paints that maximizes the total daily profit.
Formulation I - Product Mix Problem
Identify Decision variables:
x1 = Tons produced daily of exterior paint
Formulation I - Product Mix Problem
Identify Decision variables:
x1 = Tons produced daily of exterior paint
x2 = Tons produced daily of interior paint
Formulation I - Product Mix Problem
Identify Decision variables:
x1 = Tons produced daily of exterior paint
x2 = Tons produced daily of interior paint
Formulation I - Product Mix Problem
Identify Decision variables:
x1 = Tons produced daily of exterior paint
x2 = Tons produced daily of interior paint
Identify Constraints:
6x1 + 4x2 ≤ 24 (Daily usage of raw material M1 )
Formulation I - Product Mix Problem
Identify Decision variables:
x1 = Tons produced daily of exterior paint
x2 = Tons produced daily of interior paint
Identify Constraints:
6x1 + 4x2 ≤ 24 (Daily usage of raw material M1 )
x1 + 2x2 ≤ 6 (Daily usage of raw material M2 )
Formulation I - Product Mix Problem
Identify Decision variables:
x1 = Tons produced daily of exterior paint
x2 = Tons produced daily of interior paint
Identify Constraints:
6x1 + 4x2 ≤ 24 (Daily usage of raw material M1 )
x1 + 2x2 ≤ 6 (Daily usage of raw material M2 )
x2 − x1 ≤ 1 (Daily demand of Exterior and Interior Paint)
Formulation I - Product Mix Problem
Identify Decision variables:
x1 = Tons produced daily of exterior paint
x2 = Tons produced daily of interior paint
Identify Constraints:
6x1 + 4x2 ≤ 24 (Daily usage of raw material M1 )
x1 + 2x2 ≤ 6 (Daily usage of raw material M2 )
x2 − x1 ≤ 1 (Daily demand of Exterior and Interior Paint)
x2 ≤ 2 (Daily demand of Interior Paint)
Formulation I - Product Mix Problem
Identify Decision variables:
x1 = Tons produced daily of exterior paint
x2 = Tons produced daily of interior paint
Identify Constraints:
6x1 + 4x2 ≤ 24 (Daily usage of raw material M1 )
x1 + 2x2 ≤ 6 (Daily usage of raw material M2 )
x2 − x1 ≤ 1 (Daily demand of Exterior and Interior Paint)
x2 ≤ 2 (Daily demand of Interior Paint)
x1 , x2 ≥ 0 (Non-negativity of Decision Variables)
Identify Objective Function:
Profit associated with Exterior Paint is Rs. 5/Ton and with interior paint Rs. 4/Ton
So, total daily profit is: 5x1 + 4x2 , which needs to be maximized
So, Objective function is
max 5x1 + 4x2 (Profit Function)
General Structure of OR Problems
Objective Function:

max or min z = f (x)

General Structure of OR Problems
Objective Function:

max or min z = f (x)

= cx
Xp
= cj xj
j=1

Here
c = [c1 , c2 , . . . , cp ] is objective function coefficient vector and
x = [x1 , x2 , . . . , xp ]T is decision variable vector
General Structure of OR Problems
Objective Function:

max or min z = f (x)

= cx
Xp
= cj xj
j=1

Here
c = [c1 , c2 , . . . , cp ] is objective function coefficient vector and
x = [x1 , x2 , . . . , xp ]T is decision variable vector
Constraints:

gi (x) ≤ or ≥ or = 0 ≡ Ax ≤ or ≥ or = (Functional Constraints)

xj ≤ or ≥ or = 0 or Unrestricted in sign (Geometric Constraints)

Here, i = 1, 2, . . . , m, j = 1, 2, . . . , p,A ∈ Rm×p , b ∈ Rm×1

Formulation II - Manpower Requirement

The daily requirement of nurses in a private nursing home is given in the following
table. The nurses start working at the beginning of the shift i.e. at 8 am, 12 noon
etc and work for 8 continuous hours. What is the minimum number of nurses
required to meet the daily demand?

Time of Day Requirement

8 am - 12 noon 12
12 noon - 4 pm 15
4 pm - 8 pm 10
8 pm to midnight 8
Midnight - 4 am 6
4 am - 8 am 10
Formulation II - Manpower Requirement, Contd
Identifying Decision Variables
Let, xi be the number of nurses required at the beginning of the ith shift. There are
total 6 such beginnings of shifts.
Formulation II - Manpower Requirement, Contd
Identifying Decision Variables
Let, xi be the number of nurses required at the beginning of the ith shift. There are
total 6 such beginnings of shifts.
Objective function:
6
X
min xi = min(x1 + x2 + . . . + x6 )
i=1
Formulation II - Manpower Requirement, Contd
Identifying Decision Variables
Let, xi be the number of nurses required at the beginning of the ith shift. There are
total 6 such beginnings of shifts.
Objective function:
6
X
min xi = min(x1 + x2 + . . . + x6 )
i=1
subject to:
x1 + x2 ≥ 15
x2 + x3 ≥ 10
x3 + x4 ≥ 8
x4 + x5 ≥ 6
x5 + x6 ≥ 10
x6 + x1 ≥ 12
xi ≥ 0 ∀i = 1, 2, . . . 6
Formulation III - Production Planning

The demands for 2 weeks for a product are 800 and 1000 units respectively. The
company can produce up to 700 units in regular production hours @ Rs 100/
product. It can employ overtime and produce up to an extra 300 units in a week @
Rs 120/ product. The cost of carrying a product from one week to the next week is
Rs 15/product/week. How should they design their production plan to meet the
demand at minimum cost?
Formulation III - Production Planning

The demands for 2 weeks for a product are 800 and 1000 units respectively. The
company can produce up to 700 units in regular production hours @ Rs 100/
product. It can employ overtime and produce up to an extra 300 units in a week @
Rs 120/ product. The cost of carrying a product from one week to the next week is
Rs 15/product/week. How should they design their production plan to meet the
demand at minimum cost?
Identifying Decision Variables
Let,
x1 be the number of products to be produced using regular time in week 1
x2 be the number of products to be produced using regular time in week 2
y1 be the number of products to be produced using over time in week 1
y2 be the number of products to be produced using over time in week 2
w be the number of products to be carried from week 1 to week 2
Formulation III - Production Planning, Contd.
Objective function:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 + 15w
|{z}
Carrying Cost
Formulation III - Production Planning, Contd.
Objective function:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 + 15w
|{z}
Carrying Cost

subject to:
Formulation III - Production Planning, Contd.
Objective function:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 + 15w
|{z}
Carrying Cost

subject to:

x1 + y1 = 800 + w
Formulation III - Production Planning, Contd.
Objective function:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 + 15w
|{z}
Carrying Cost

subject to:

x1 + y1 = 800 + w
w + x2 + y2 = 1000
Formulation III - Production Planning, Contd.
Objective function:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 + 15w
|{z}
Carrying Cost

subject to:

x1 + y1 = 800 + w
w + x2 + y2 = 1000
x1 ≤ 700 , x2 ≤ 700
Formulation III - Production Planning, Contd.
Objective function:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 + 15w
|{z}
Carrying Cost

subject to:

x1 + y1 = 800 + w
w + x2 + y2 = 1000
x1 ≤ 700 , x2 ≤ 700
y1 ≤ 300 , y2 ≤ 300
Formulation III - Production Planning, Contd.
Objective function:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 + 15w
|{z}
Carrying Cost

subject to:

x1 + y1 = 800 + w
w + x2 + y2 = 1000
x1 ≤ 700 , x2 ≤ 700
y1 ≤ 300 , y2 ≤ 300
x1 , x2 , y1 , y2 , w ≥ 0
Formulation III - Production Planning, Contd.
Modified Formulation
Putting w = x1 + y1 − 800 the objective function becomes:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 +15 (x1 + y1 − 800)
| {z }
Carrying Cost
Formulation III - Production Planning, Contd.
Modified Formulation
Putting w = x1 + y1 − 800 the objective function becomes:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 +15 (x1 + y1 − 800)
| {z }
Carrying Cost
= 115x1 + 100x2 + 135y1 + 120y2 − 12000
Formulation III - Production Planning, Contd.
Modified Formulation
Putting w = x1 + y1 − 800 the objective function becomes:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 +15 (x1 + y1 − 800)
| {z }
Carrying Cost
= 115x1 + 100x2 + 135y1 + 120y2 − 12000

subject to:

x1 + y1 ≥ 800
Formulation III - Production Planning, Contd.
Modified Formulation
Putting w = x1 + y1 − 800 the objective function becomes:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 +15 (x1 + y1 − 800)
| {z }
Carrying Cost
= 115x1 + 100x2 + 135y1 + 120y2 − 12000

subject to:

x1 + y1 ≥ 800
x1 + x2 + y1 + y2 = 1800
Formulation III - Production Planning, Contd.
Modified Formulation
Putting w = x1 + y1 − 800 the objective function becomes:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 +15 (x1 + y1 − 800)
| {z }
Carrying Cost
= 115x1 + 100x2 + 135y1 + 120y2 − 12000

subject to:

x1 + y1 ≥ 800
x1 + x2 + y1 + y2 = 1800
x1 ≤ 700 , x2 ≤ 700
Formulation III - Production Planning, Contd.
Modified Formulation
Putting w = x1 + y1 − 800 the objective function becomes:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 +15 (x1 + y1 − 800)
| {z }
Carrying Cost
= 115x1 + 100x2 + 135y1 + 120y2 − 12000

subject to:

x1 + y1 ≥ 800
x1 + x2 + y1 + y2 = 1800
x1 ≤ 700 , x2 ≤ 700
y1 ≤ 300 , y2 ≤ 300
Formulation III - Production Planning, Contd.
Modified Formulation
Putting w = x1 + y1 − 800 the objective function becomes:

Regular Cost Overtime Cost

z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2 +15 (x1 + y1 − 800)
| {z }
Carrying Cost
= 115x1 + 100x2 + 135y1 + 120y2 − 12000

subject to:

x1 + y1 ≥ 800
x1 + x2 + y1 + y2 = 1800
x1 ≤ 700 , x2 ≤ 700
y1 ≤ 300 , y2 ≤ 300
x1 , x2 , y1 , y2 ≥ 0
Formulation III - Production Planning, Contd.
Modified Formulation
Second functional constraint with ≥ rather than = will indicate the excess
production incurring holding cost in objective function
Constraints:
x1 + y1 ≥ 800
Formulation III - Production Planning, Contd.
Modified Formulation
Second functional constraint with ≥ rather than = will indicate the excess
production incurring holding cost in objective function
Constraints:
x1 + y1 ≥ 800
x1 + x2 + y1 + y2 ≥ 1800
Formulation III - Production Planning, Contd.
Modified Formulation
Second functional constraint with ≥ rather than = will indicate the excess
production incurring holding cost in objective function
Constraints:
x1 + y1 ≥ 800
x1 + x2 + y1 + y2 ≥ 1800
x1 ≤ 700, x2 ≤ 700 , y1 ≤ 300, y2 ≤ 300
Formulation III - Production Planning, Contd.
Modified Formulation
Second functional constraint with ≥ rather than = will indicate the excess
production incurring holding cost in objective function
Constraints:
x1 + y1 ≥ 800
x1 + x2 + y1 + y2 ≥ 1800
x1 ≤ 700, x2 ≤ 700 , y1 ≤ 300, y2 ≤ 300
x1 , x2 , y1 , y2 ≥ 0
Now the objective function becomes:
Regular Cost Overtime Cost
z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2
+15 {(x1 + y1 − 800) + (x1 + x2 + y1 + y2 − 1800)}
| {z }
Carrying Cost
Formulation III - Production Planning, Contd.
Modified Formulation
Second functional constraint with ≥ rather than = will indicate the excess
production incurring holding cost in objective function
Constraints:
x1 + y1 ≥ 800
x1 + x2 + y1 + y2 ≥ 1800
x1 ≤ 700, x2 ≤ 700 , y1 ≤ 300, y2 ≤ 300
x1 , x2 , y1 , y2 ≥ 0
Now the objective function becomes:
Regular Cost Overtime Cost
z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2
+15 {(x1 + y1 − 800) + (x1 + x2 + y1 + y2 − 1800)}
| {z }
Carrying Cost
= 130x1 + 115x2 + 150y1 + 135y2 − 39, 000
Formulation III - Production Planning, Contd.
Modified Formulation
Second functional constraint with ≥ rather than = will indicate the excess
production incurring holding cost in objective function
Constraints:
x1 + y1 ≥ 800
x1 + x2 + y1 + y2 ≥ 1800
x1 ≤ 700, x2 ≤ 700 , y1 ≤ 300, y2 ≤ 300
x1 , x2 , y1 , y2 ≥ 0
Now the objective function becomes:
Regular Cost Overtime Cost
z }| { z }| {
min z = 100x1 + 100x2 + 120y1 + 120y2
+15 {(x1 + y1 − 800) + (x1 + x2 + y1 + y2 − 1800)}
| {z }
Carrying Cost
= 130x1 + 115x2 + 150y1 + 135y2 − 39, 000
Formulation IV - Caterer Problem

The requirements of napkins on five consecutive days of dinner are 100, 60, 80,
90 and 70. New napkins cost Rs 60. Napkins sent to laundry at the end of any day
take one full day for washing etc. The laundry cost is Rs 20/ napkin. Find a plan to
minimize the total cost of usage of napkins in terms of buying new ones or sending
the used napkins to laundry.
Formulation IV - Caterer Problem

The requirements of napkins on five consecutive days of dinner are 100, 60, 80,
90 and 70. New napkins cost Rs 60. Napkins sent to laundry at the end of any day
take one full day for washing etc. The laundry cost is Rs 20/ napkin. Find a plan to
minimize the total cost of usage of napkins in terms of buying new ones or sending
the used napkins to laundry.
Identifying Decision Variables
Let,
x1 to x5 be the numbers of napkins to be bought on each day
and
y1 to y3 be the numbers of napkins to be sent to laundry at the end of the day
Formulation IV - Caterer Problem, Contd.
Formulating the constraints
Day 1 demand:
For day 1, no other option than buying. So,
x1 ≥ 100
Formulation IV - Caterer Problem, Contd.
Formulating the constraints
Day 1 demand:
For day 1, no other option than buying. So,
x1 ≥ 100
Day 2 demand:
x1 − 100 unused napkins are carried over from day 1 to day 2
x1 − 100 + x2 ≥ 60
≡ x1 + x2 ≥ 160
Formulation IV - Caterer Problem, Contd.
Formulating the constraints
Day 1 demand:
For day 1, no other option than buying. So,
x1 ≥ 100
Day 2 demand:
x1 − 100 unused napkins are carried over from day 1 to day 2
x1 − 100 + x2 ≥ 60
≡ x1 + x2 ≥ 160
Day 3 demand:
Is given by Extra napkins from day 2 + new napkins on day 3 + napkins from
laundry from day 1

x1 + x2 − 160 + x3 + y1 ≥ 80
≡ x1 + x2 + x3 + y1 ≥ 240
Formulation IV - Caterer Problem, Contd.

Day 4 demand:

x1 + x2 + x3 + y1 − 240 + x4 + y2 ≥ 90
≡ x1 + x2 + x3 + x4 + y1 + y2 ≥ 330

Day 5 demand:

x1 + x2 + x3 + x4 + y1 + y2 − 330 + x5 + y3 = 70
≡ x1 + x2 + x3 + x4 + x5 + y1 + y2 + y3 = 400
Formulation IV - Caterer Problem, Contd.

Limits on napkins to be sent to the Laundry:

y1 ≤ 100
y2 ≤ 60
y3 ≤ 80
Formulation IV - Caterer Problem, Contd.

Limits on napkins to be sent to the Laundry:

y1 ≤ 100
y2 ≤ 60
y3 ≤ 80

Objective function:

X5 3
X
min z = 60( xi ) + 20( yj )
i=1 j=1
Formulation IV - Caterer Problem, Contd.
Let the number of new napkins bought in day i be Xi and number of napkins sent
to the laundry at the end of day i be Yi
Objective function:
n
X n−p
X
min z = c xi + a yi
i=1 i=1
subject to:
i
X X i i
X
xj + yj ≥ di ∀i
j=1 j=p+1 j=1
yi ≤ di
xi , yi ≥ 0
Here,
c = Cost of new napkin a = Laundry cost
d = Demand p = Laundry days
Formulation V - Cutting Stock Problem

Consider a big steel roll from which steel sheets of same lengths but different
widths to be cut. Lets us assume that the roll is of 20 inches width and the
following sizes have to be cut:
▶ 9 inches - 511 pieces
▶ 8 inches - 301 pieces
▶ 7 inches - 263 pieces
▶ 6 inches - 383 pieces
It is assumed that all the cut sheets have the same length of 25 inches (One
dimensional cutting). The problem is to cut the sheets in such a way to minimize
the wastage of material.
Formulation V - Cutting Stock Problem
Let us define the waste first
If we cut only 9 inches pieces from 20 inches then waste is = 20 − 2 × 9 = 2
If we cut only 8 inches pieces from 20 inches then waste is = 20 − 2 × 8 = 4
In this way, identify the wastes for different cutting patterns:

9in 8in 7in 6in Waste

2 0 0 0 2
0 2 0 0 4
0 0 2 1 0
0 0 0 3 2
1 1 0 0 3
1 0 1 0 4
1 0 0 1 5
0 1 1 0 5
0 1 0 2 0
0 0 1 2 1
Formulation V - Cutting Stock Problem
In this wastage calculation, a pattern which will create wastage of 6 inches will not
be considered i.e. 0, 0, 2, 0 is not a valid pattern
So, wastage of materials till 5 inches will be considered here
Identifying Decision Variables: xj : number of sheets cut using pattern j
Identifying Constraints: From the table of patterns, develop the constraints:

2x1 + x5 + x6 + x7 = 511
2x2 + x5 + x8 + x9 = 301
2x3 + x6 + x8 + x10 = 263
x3 + 3x4 + x7 + 2x9 + 2x10 = 383
xj ≥ 0 and Integer

Objective Function
min 2x1 + 4x2 + 2x4 + 3x5 + 4x6 + 5x7 + 5x9 + x10
Here, = type of constraints are used to bring out the fact that anything left is of no
use
Formulation V - Cutting Stock Problem

Instead of forced constraints of = type if we plan for to reuse the waste material
Identifying Decision Variables: xj : number of sheets cut using pattern j
Identifying Constraints: From the table of patterns, develop the constraints:

2x1 + x5 + x6 + x7 ≥ 511
2x2 + x5 + x8 + x9 ≥ 301
2x3 + x6 + x8 + x10 ≥ 263
x3 + 3x4 + x7 + 2x9 + 2x10 ≥ 383
xj ≥ 0 and Integer

Objective Function min 2x1 + 4x2 + 2x4 + 3x5 + 4x6 + 5x7 + 5x9 + x10
Formulation VI - Water Supply Network Design
A Water Treatment Plant wants to pump water from Source (S) to Destination (D)
or Sink using the network in diagram. Nodes 1 to 5 are the internal nodes between
S and D. This type of network is called as Directed Acyclic Network as there is no
cycle between the nodes. The connecting arcs between the nodes are having a
particular carrying capacity in million gallons written on the arc. Objective is to find
out the flow in each arc so that there is maximum flow of water i.e. the amount of
water supplied by S must fully reach to the D. No node has any storage in it.

2
10
20
f 30 f
25

30
S 1 4 5 D
35
40
20
3
Formulation VI - Water Network Design, Contd.
Identifying Decision Variables Let, xij be the flow in arc connecting node i and j
Formulation VI - Water Network Design, Contd.
Identifying Decision Variables Let, xij be the flow in arc connecting node i and j
So, Decision variables are x12 , x13 , . . ., x45
Formulation VI - Water Network Design, Contd.
Identifying Decision Variables Let, xij be the flow in arc connecting node i and j
So, Decision variables are x12 , x13 , . . ., x45
Constraints: Capacity Constraints on Arcs:
x12 ≤ 20, x13 ≤ 40, x23 ≤ 30, x24 ≤ 30, x34 ≤ 35, x25 ≤ 10, x45 ≤ 25, x35 ≤ 20
Formulation VI - Water Network Design, Contd.
Identifying Decision Variables Let, xij be the flow in arc connecting node i and j
So, Decision variables are x12 , x13 , . . ., x45
Constraints: Capacity Constraints on Arcs:
x12 ≤ 20, x13 ≤ 40, x23 ≤ 30, x24 ≤ 30, x34 ≤ 35, x25 ≤ 10, x45 ≤ 25, x35 ≤ 20
Flow Constraints: Lets suppose that, entering amount at Node 1 is f . So the exit
amount from Node 5 also will be f .

x12 + x13 = f (Node 1)

−x12 + x23 + x24 + x25 = 0 (Node 2)
−x13 − x23 + x34 + x35 = 0 (Node 3)
−x24 − x34 + x45 = 0 (Node 4)
x25 + x35 + x45 = f (Node 5)

Objective Function: max f

Formulation VII - Bin Allocation Problem
You are given the numbers 8, 6, 9, 28, 17, 24, 7, 21. Make minimum number of
groups so that sum of numbers in each group must not exceed 45.
Formulation VII - Bin Allocation Problem
You are given the numbers 8, 6, 9, 28, 17, 24, 7, 21. Make minimum number of
groups so that sum of numbers in each group must not exceed 45.
Identifying Decision Variables
Maximum 8 such groups are possible
Formulation VII - Bin Allocation Problem
You are given the numbers 8, 6, 9, 28, 17, 24, 7, 21. Make minimum number of
groups so that sum of numbers in each group must not exceed 45.
Identifying Decision Variables
Maximum 8 such groups are possible
Let, (
1 if group j is formed
yj =
0 if group j is not formed
and
Formulation VII - Bin Allocation Problem
You are given the numbers 8, 6, 9, 28, 17, 24, 7, 21. Make minimum number of
groups so that sum of numbers in each group must not exceed 45.
Identifying Decision Variables
Maximum 8 such groups are possible
Let, (
1 if group j is formed
yj =
0 if group j is not formed
and (
1 if number i belongs to group j
xij =
0 if number i does not belong to group j
Formulation VII - Bin Allocation Problem
You are given the numbers 8, 6, 9, 28, 17, 24, 7, 21. Make minimum number of
groups so that sum of numbers in each group must not exceed 45.
Identifying Decision Variables
Maximum 8 such groups are possible
Let, (
1 if group j is formed
yj =
0 if group j is not formed
and (
1 if number i belongs to group j
xij =
0 if number i does not belong to group j

Objective function:
8
X
min yj = y1 + y2 + . . . + y8
j=1
Formulation VII - Bin Allocation Problem, Contd.
Constraints
Each number must belong to one and only one group.

x11 + x12 + . . . + x18 = 1

... + ... + ... + ... = ...
x81 + x82 + . . . + x88 = 1
8
X
Written in compact form xij = 1 ∀i Similarly,
j=1

8x11 + 6x21 + 9x31 + 28x41 + 17x51 + 24x61 + 7x71 + 21x81 ≤ 45y1

8
X
In compact form, aij xij ≤ 45yj , aij are the numbers
i=1
So, total 64 + 8 = 72 Decision Variables and 16 constraints
Classification of OR Models

OR models can be classified according to

▶ Existence of Functional Constraints - Constrained or Unconstrained
Classification of OR Models

OR models can be classified according to

▶ Existence of Functional Constraints - Constrained or Unconstrained
▶ Nature of Decision Variables - Continuous or Discrete or Mixed type.
Discrete can be of Binary type or Multivalued type
Classification of OR Models

OR models can be classified according to

▶ Existence of Functional Constraints - Constrained or Unconstrained
▶ Nature of Decision Variables - Continuous or Discrete or Mixed type.
Discrete can be of Binary type or Multivalued type
▶ Nature of Constraints and/or Objective Functions - Linear or Nonlinear,
Deterministic or Random, Static or Stochastic
Classification of OR Models

OR models can be classified according to

▶ Existence of Functional Constraints - Constrained or Unconstrained
▶ Nature of Decision Variables - Continuous or Discrete or Mixed type.
Discrete can be of Binary type or Multivalued type
▶ Nature of Constraints and/or Objective Functions - Linear or Nonlinear,
Deterministic or Random, Static or Stochastic
▶ Number of Objective Functions - Single or Bi-objective or Multiobjective
Classification of OR Models

OR models can be classified according to

▶ Existence of Functional Constraints - Constrained or Unconstrained
▶ Nature of Decision Variables - Continuous or Discrete or Mixed type.
Discrete can be of Binary type or Multivalued type
▶ Nature of Constraints and/or Objective Functions - Linear or Nonlinear,
Deterministic or Random, Static or Stochastic
▶ Number of Objective Functions - Single or Bi-objective or Multiobjective
▶ Usage of Direction or Gradient - Traditional or Direct Search
Classification of OR Models

OR models can be classified according to

▶ Existence of Functional Constraints - Constrained or Unconstrained
▶ Nature of Decision Variables - Continuous or Discrete or Mixed type.
Discrete can be of Binary type or Multivalued type
▶ Nature of Constraints and/or Objective Functions - Linear or Nonlinear,
Deterministic or Random, Static or Stochastic
▶ Number of Objective Functions - Single or Bi-objective or Multiobjective
▶ Usage of Direction or Gradient - Traditional or Direct Search
▶ Nature of Search Space - Convex or Non-convex