IM20204: OPERATIONS RESEARCH

Department of Industrial and Systems Engineering

Indian Institute of Technology, Kharagpur

 Instructor: Dr J K Jha
 Office: 212, ISE Department
 E-mail: jkjha@iem.iitkgp.ac.in, Phone: 83748
 Class Schedule:
Timings – Wed (10.00 to 11:00 Hr)
Friday (11.00 to 13:00 Hr)
Thursday (Reserve for compensatory class)
Venue – NR 213
 Individual meetings: after the class or after 5.00pm
 BACKGROUND, OBJECTIVE AND SCOPE

Operations Research is one of the compulsory courses for Industrial Engineering, HS and
ME.

Operations Research (OR) involves “research on operations”. In other words, OR is

applied to the problems that concern how to conduct and coordinate the operations within
an organization.
OR techniques have been widely applied to diverse areas such as manufacturing,
transportation, telecommunication, military, finance, health care, and public services.

This course is intended

to give an appreciation of the problems which can be approached through basic OR
techniques
to familiarize the students with the various techniques available
to develop an understandings of the mechanics of such techniques, and
to develop a general awareness of the applicability and limitations of OR methods and
techniques.
At the end of the course, the students are expected to have a reasonable foundation in OR,
based on which they can further build up and broaden their knowledge-base in order to
deal with the much more complex real-world problems in their-related research and
subsequent jobs.
2
 TEXT BOOK AND REFERENCES

Text Book
• Introduction to Operations Research by F.S. Hillier and G.J. Lieberman

• Operations Research: an Introduction by H.A. Taha

Reference

• Operations Research: Applications and Algorithms by W.L. Winston

• Operations Research: Principles and Practice by Ravindran, Phillips and

Solberg

3
TENTATIVE EVALUATION SCHEME

Component Weightage

Attendance (Deregistration if attendance below 75%) 5

Two Class Tests 5+5=10

Assignment 5

Mid Sem 30

End Sem 50

Total 100

4
 TENTATIVE SESSION PLAN

Topic Readings from Hillier and Lieberman

(Eighth Edition)
Introduction to Operations Research Chapter 1
Operations Research Modeling Approach Chapter 2
Introduction to Linear Programming Chapter 3
Simplex Method Chapter 4
Theory of Linear Programming Chapter 5
Duality Theory and Sensitivity Analysis Chapter 6
Dual Simplex Method Chapter 7
Transportation, Assignment, Transshipment Chapter 5, TAHA 8th ed
Problems
Queuing Theory Chapter 15, TAHA 8th ed
Scope and Applicability of Operations Research (OR)

The Scope and applicability of OR as a field: Enormous

In this course:
Introductory

Applied side

Somewhat basic: Variety of backgrounds

Pre-requisites: Some knowledge of Matrix Algebra

6
 Genesis of OR
World War II (WW II) Military
- UK, USA Operations
Research
- Military applications in transportation and logistics

Later
Post - WW II, other organization (industrial, government)
- Industrial revolution (Boom)
Operations
- Size of firms Research
- Complexity of operations (Management
Science, Decision
- Subdivisions within organization Science)

Basic Question
Same military like problems
How to allocate scarce resources to various in different contexts
activities of an organization ?

MIT was one of the birthplaces of OR

Professor Philip M Morse at MIT was a pioneer in the US
7
Founded MIT OR Center and helped found ORSA
 Definition of OR

OR is the branch of science dealing with techniques for

optimizing (maximizing/minimizing) the performance
(profit, market share, cost etc.) of systems
(manufacturing company, service industry, Government
organization, etc.)

8
 Factors Influencing growth of OR

Initial
- Substantial research in OR (by military scientists mainly)
- Simplex method for solving Linear Programming (LP) Problem (by
George Dantzig, 1947)
- LP, DP, Queuing theory, inventory theory 1950’s

Later
Computer revolution
- Personal Computer (PC) with high capability
- Software packages for LP/IP/NLP: CPLEX, LINGO, SAS
- Current areas: SCM, Logistics, Healthcare, ERP

9
 Steps in OR Modeling Approach

To Solve a real-world problem

Step I: Extract the important features of the problem

Step II: Construct a mathematical model

Step III: Solve the model

Step IV: Test the model

Step V: Apply the model

10
 Steps in OR Modeling Approach

Step I: Extract the important features of the problem

(a) Define the problem
(b) Gather relevant data
(a) Define the problem
- Decision variables: unknown quantities whose value will provide
Components

solution to the problem

- Parameters: constant (given, fixed) values in objective functions/constraints
- Constraints: restrictions on the values of the decision variables
- Objective function: Target to be achieved
Optimizing: maximizing – profits, sales
minimizing – costs
Should give unique best solution
Satisfying: Good enough
Satisfactory + optimizing
11
Close to optimal, above a threshold
 Different Objectives can lead to different solutions even
for the same set of constraints
• A company manufactures two types of product
Product Selling price per unit Cost price per unit Minimum production requirement
1 p1 c1 d1
2 p2 c2 d2
• Production capacity B units
• Suppose
- d1, d2 much smaller than B
- Selling price of product 1 is less than product 2, i.e. p1<p2
- Profit /unit on product 1 is greater than product 2, i.e. p1-c1>p2-c2
• Parameters: p1, p2, c1, c2, B, d1, d2
• Decision Variables:
x1 : number of units of product 1 to be produced
12
x2: number of units of product 2 to be produced
• Objective: Maximize profit Vs. Maximize Sales price
Max (p1-c1)x1+(p2-c2)x2 Vs. Max p1x1+p2x2
• Constraints:
Subject to
x1 + x2 ≤ B (Production capacity constraint)
x1 ≥ d1 (Minimum production constraint for product 1)
x2 ≥ d2 (Minimum production constraint for product 2)
What picture emerges in x1-x2 plane?
x2 x1 ≥ d1
Solution:
(d1, B-d1) For profit maximization: (B-d2, d2)
For sales maximization: (d1, B-d1)

(B-d2, d2) Solution for Cost minimization?

x2 ≥ d2
(d1, d2)
x1
13
x1 + x2 ≤ B
 Steps in OR Modeling Approach contd…

(b) Gather relevant data

- Available / Secondary data: manager provides the data
- MIS
- Soft / qualitative / subjective data – rough, educated guess

Different types of organization may have different objectives

(Non-Profit Organizations) NPOs: usage or awareness maximization
Airline Industries: Multiple objectives
- customer satisfaction
- employee morale
- cost minimization/revenue maximization

14
Step II: Construct a mathematical model
- idealized representation of reality
- should be good (in terms of representation) and solvable
(tractable). Otherwise model might be as complex as the
reality
- Advantages of Model: Concise, comprehensive,
programmable on computer

15
 Example: Product Mix Problem
Tech Edge Company imports electronic components that are used to assemble two
different models (Deskpro and Portable) of personal computers. The company is
currently interested in developing a weekly production plan for both models. The
other relevant data is given below:

Model Assembly Special Warehouse Space Profit per

time component (Sq m) unit ($)
(hour) (unit)
Deskpro 3 0 8 50
Portable 5 1 5 40
Maximum 150 20 300
Availability

16
Decision Variables:
x1 = Number of units of Deskpro produced
x2 = Number of units of Portable produced

Max Z = 50 x1 + 40 x2
3 x1 + 5 x2 ≤ 150 (Assembly time)
x2 ≤ 20 (Special component)
8 x1 + 5 x2 ≤ 300 (Space)
x1, x2 ≥ 0 (Non-negativity constraint)
17
 Generalized Product Mix Problem

Company can manufacture a set of products using a set of resources.

What should be the production quantity of each product so that the
total profit is maximized.

Parameters:
n : number of products, j = 1, 2, …, n
m: number of resources, i = 1, 2, …, m
cj : profit from per unit of product j
aij: amount of resource i required to manufacture per unit of product j
bi: availability of resource i

18
 Generalized formulation: Product Mix Problem
Decision Variable:
xj: amount of product j to be manufactured, j = 1, 2, …, n
Objective Function:
n
Max Z   c j x j
j 1

Constraints
n
S.t. a
j 1
ij x j  bi , i  1, 2,..., m (1)

x j  0, j  1, 2,..., n ( 2)

Terminology
Eq. (1): resource availability or Functional or technological constraints
Eq. (2): Non-negativity constraint
cj: Profit coefficient (cost coefficient in case of cost)
aij: Technological coefficient
19
bi: resource availability
 Example: Diet Problem

The goal of the diet problem is to select a set of foods

that will satisfy a set of daily nutritional requirements at
minimum cost.

Parameters:
n : number of food items, j = 1, 2, …, n
m: number of nutrients, , i = 1, 2, …, m
cj : cost per unit of food j
aij: amount of nutrient i available in per unit of food j
bi: minimum nutritional requirement for nutrient i

20
 Diet Problem: Formulation
Decision Variable:
xj: amount of food j to be included in the diet, j = 1, 2, …, n

Objective Function:
n
Min Z   c j x j
j 1

Constraints
n
S.t. a x
j 1
ij j  bi , i  1, 2,..., m

x j  0, j  1, 2,..., n
21
Step III: Solve the model
- Standard algorithm can usually give optimal solution. Example: Simplex
- Heuristic Solution: decision based on intuition, can sometimes give good sub-
optimal solution. Example:
Knapsack Problem –Given a set of items (j=1, 2, …, n) with a weight (wj) and value
(vj), select the items so that the total weight is less than a given limit (W) and the
total value is as large as possible.
- Decision variable: xj =1 if item is included in knapsack; 0 Otherwise
Formulatio n Efficient Heuristic :
n
- Sort v j w j in descending order
max  v j x j ,
j 1 - Starting with theitem with
n highest v j w j ratio, pick items to
subject to  w j x j  W include in knapsack till the
j 1
total weight  W
x j  0,1, j  1,2,...,n

-Sensitivity analysis: How sensitive solution is to changes in

22
parameter values
Step IV: Test the model
- Does model solution translate to problem solution
- Since model is representation of reality: what is the role of
assumptions?
- Retrospective test: use past, reconstruct history, test model
recommendations
- Face validity: Does it make sense?

Step V: Apply the model in actual decision making

- Model should be part of a large system used to help managers in
making better decisions: DSS approach
- Top management support
- Careful documentation: solution procedures, operating
procedures
23
Steps in Linear Programming (LP) Model Formulation

Step 1: Identify the decision variables

Unknown quantities whose value will provide solution of
the problem
Step 2: Identify the objective function
Target to be achieved
Optimizing: maximizing – profits, sales
minimizing – costs
Should give unique best solution
Step 3: Identify the constraints
restrictions on the values of the decision variables
Step 4: Construct mathematical expressions for objective function
and constraints
 Example: Advertising Media Selection
An advertising company wishes to plan an advertising campaign in three different
media - television, radio and magazines. The purpose of the advertising program is
to reach as many potential customers as possible. Results of a market study are
given below:
Television
Daytime Prime time Radio Magazines
Cost of an advertising unit $40,000 $75,000 $30,000 $15,000
Number of potential customers 400,000 900,000 500,000 200,000
reached per unit
number of women customers 300,000 400,000 200,000 100,000
reached per unit
The company does not want to spend more than $800,000 on advertising. Further
(1) at least 2 million exposures take place among women;
(2) advertising on television be limited to $500,000;
(3) at least 3 advertising units be bought on daytime television, and 2 units during
prime time; and
(4) the number of advertising units on radio and magazine should each be between 5
25
and 10.
 Advertising Media Selection: LP Formulation
Decision Variables :
x1 = Number of advertising units bought in daytime television
x2 = Number of advertising units bought in prime time television
x3 = Number of advertising units bought in radio
x4 = Number of advertising units bought in magazines

Objective: Maximize Z = 400,000x1 + 900,000x2 + 500,000x3 + 200,000x4

Subject to:
40,000x1 + 75,000x2 + 30,000x3 + 15,000x4 ≤ 800,000 (advertising budget)
300,000x1 + 400,000x2 + 200,000x3 + 100,000x4 ≥2,000,000 (women customers)
40,000x1 + 75,000x2 ≤ 500,000 (television advertisement)
x1 ≥ 3 (advertising units on daytime)
x2 ≥ 2 (advertising units on prime time)
x3 ≥ 5 (advertising units on radio)
x3 ≤ 10 (advertising units on radio)
x4 ≥ 5 (advertising units on magazines)
26
x4 ≤ 10 (advertising units on magazines)
 Example: Load Balancing Problem
A machine shop has one drill and five milling machines, which are to be used
to produce an assembly of two parts, 1 and 2. The productivity of each
machine for the two parts is given below:

Production time in minutes per piece

Part Drill Milling
1 3 20
2 5 15

It is desired to maintain a balanced loading on all machines such that no

machine runs more than 30 minutes per day longer than any other machine
(assume that the milling load is distributed equally among all five milling
machines).
Divide the work time of each machine to obtain the maximum number
of completed assemblies assuming an 8-hour working day.
27
 Load Balancing Problem: LP Formulation
Decision Variables:
x1 = number of part 1 produced per day
x2 = number of part 2 produced per day
y = number of completed assemblies, then y = minimum of (x1, x2)
Objective: Maximize y = Maximize (minimum of (x1, x2))
Equivalent to this: Maximize y,
Subject to y ≤ x1, y ≤ x2
Load on each milling m/c (in minutes)= (20x1 + 15x2 )/5 = 4x1 + 3x2
Load on the drill m/c (in minutes)= 3x1 + 5x2
Total time available per day = 8x60 = 480 minute
Thus, the time restriction on each machine
For each milling m/c, 4x1 + 3x2 ≤ 480
For the drill press, 3x1 + 5x2 ≤ 480
The load balance constraint can be represented by
|(4x1 + 3x2 ) – (3x1 + 5x2 )| ≤ 30
or, | x1 – 2x2 | ≤ 30 (non-linear constraint) 28
equivalent to this: x1 – 2x2 ≤ 30 and – x1 + 2x2 ≤ 30
Load Balancing Problem: Complete Formulation

Objective:
Maximize y

Subject to:
y ≤ x1
y ≤ x2
4x1 + 3x2 ≤ 480 (Milling Machine)
3x1 + 5x2 ≤ 480 (Drill Press)
x1 – 2x2 ≤ 30 (Balance Constraint)
– x1 + 2x2 ≤ 30 (Balance Constraint)
x1≥ 0,
x2≥ 0
y≥0

29
 Example: Marketing Research
A market survey company (MSC) specializes in evaluating consumer reaction to new
products, services, and advertising campaigns. A client firm requested MSC’s assistance in
ascertaining consumer reaction to a recently marketed household product. During meetings
with the client, MSC agreed to conduct door-to-door personal interviews to obtain responses
from households with children and households without children. In addition, MSC agreed to
conduct both day and evening interviews. Specifically, the client’s contract called for MSC to
conduct 1000 interviews under the following quota guidelines.
i.Interview at least 400 households with children.
ii.Interview at least 400 households without children.
iii.The total number of households interviewed during the evening must be at least as great as
the number of households interviewed during the day.
iv.At least 40% of the interviews for households with children must be conducted during the
evening.
v.At least 60% of the interviews for households without children must be conducted during
the evening. Cost per interview (in $)
Face validity check
Household Day Evening Per unit cost of interviewing a household
with children in evening higher, because
Children 20 25 evening -> overtime to interview
No children 18 20 HH/C/E -> take longer to interview

What is the household, time-of-day interview plan that will satisfy the contract requirements
30
at a minimum total interviewing cost?
 Marketing Research: LP Formulation
Decision variable:
DC = number of daytime interviews of households with children
EC = number of evening interviews of households with children
DNC = number of daytime interviews of households without children
ENC = number of evening interviews of households without children

Minimize Z = 20DC + 25EC + 18DNC + 20ENC

Subject to
DC + EC + DNC + ENC = 1000 (Total Interviews) (1)
DC + EC ≥ 400 (Households with children) (2)
DNC + ENC ≥ 400 (Households without children) (3)
EC + ENC ≥ DC + DNC (Evening interviews) (4)
EC ≥ 0.4(DC + EC) (Evening interviews in households with children) (5)
ENC ≥ 0.6(DNC + ENC) (Evening interviews in households without children) (6)
DC, EC, DNC, ENC ≥ 0
31
Contd..

• Optimal solution generated by computer software is as follow :

D E
C 240 160 400
NC 240 360 600
480 520 1000

Q. Check constraints feasibility.

Q. Check face validity – Does it make sense?

In general, it appears that the optimal solution drives the allocation of HH with C to
only as much as required by the contract thus yielding several constraints as “tight”
constraints.
Q. Which are tight (binding) constraints?
(1), (2), (5), (6) (These constraints are satisfied as equality for the optimal solution, i.e.
LHS =RHS)
32
 Bus Scheduling Problem
City bus service is planning to introduce a mass-transit bus system.
The number of buses required during each 4-hour shift is given
below. To carry out the required daily maintenance, each bus can
operate 8 successive hours a day only. Schedule the buses to meet
the each 4-hr shift requirement while minimizing the total number
of buses in operation.

Shift 12am-4am 4am-8am 8am-12pm 12pm-4pm 4pm-8pm 8pm-12am

Buses needed 6 8 10 7 12 4

33
 Bus Scheduling Problem: Formulation
• Decision variables:
x1= number of buses starting at 12:00 am
x2= number of buses starting at 4:00 am
x3= number of buses starting at 8:00 am
x4= number of buses starting at 12:00 pm
x5= number of buses starting at 4:00 pm
x6= number of buses starting at 8:00 pm

Minimize Z = x 1 + x2 +x3 +x4 +x5 + x6

Subject to
x1 + x6 ≥ 6 (12:00 am - 4:00 am)
x1 + x2 ≥ 8 (4:00 am - 8:00 am)
x2 + x 3 ≥ 10 (8:00 am - 12:00 noon)
x3 + x 4 ≥ 7 (12:00 pm - 4:00 pm)
x 4 + x5 ≥ 12 (4 :00 pm - 8:00 pm)
x5 + x 6 ≥ 4 (8:00 pm - 12:00 am)
x j ≥ 0, j = 1,2,..,6
34