Faculty: P.N. Ram Kumar E-mail: ram@iimk.ac.

in Phone Extension: 426

Operations research (OR) is an interdisciplinary mathematical science that focuses on the effective use of resources/technology by organizations

As the name implies, OR involves research on operations

OR is applied to problems that concern how to conduct,

manage and coordinate the operations (activities) within an organization in the best possible manner

Nature of the organization is essentially immaterial

OR has been applied extensively in diverse areas such as manufacturing, transportation, construction,

telecommunications, financial planning, health care, military

and public services, to name just a few.

Scarce resources Labor, materials, machinery, money Quest for best combination of inputs Minimizing costs or Maximizing profits Linear Programming (LP) problems - Linear objective function - Linear constraints Why only LP? - Majority of real-life problems can be approximated - Efficient solution procedures - Easy Sensitivity Analysis

Linear Programming problems Formulation, Graphical method - Sensitivity Analysis and Duality Transportation, Transshipment and Assignment problems Network optimization models Integer programming problems

Project management
Simulation A brief overview Waiting line models

Multi-objective decision problems

Dynamic Programming Markovian Models

A. Exams: Mid term: 25%; End term: 35% B. Assignments + Case Presentation: 15% C. Surprise Quizzes: 15%

D. Class participation: 10%

Its only for Quants guys, not for us!

Its too mathematical!!

OR models can replace decision makers

A model should never be taken too literally Beware of overselling a model Verification and Validation

Linear Programming problems Formulation, Graphical method - Sensitivity Analysis and Duality Transportation, Transshipment and Assignment problems Network optimization models Integer programming problems

Project management
Simulation A brief overview Waiting line models

Multi-objective decision problems

Dynamic Programming Markovian Models

Linear Programming problems Formulation, Graphical method - Sensitivity Analysis and Duality Transportation, Transshipment and Assignment problems Network optimization models Integer programming problems

Project management
Simulation A brief overview Waiting line models

Multi-objective decision problems

Dynamic Programming Markovian Models

A small factory makes three products, soap,

shampoo and detergent. The processing is done in

two stages at two plants, I and II, each of which works for 40 hours every week.

The time required for processing each product at

each plant and the profit of each product are shown in the table Formulate a linear program to maximize the profits

Plant I

Plant II

Profit / Kg

Soap Shampoo

3 4

5 4

Rs.10 Rs. 13

Detergent
Hours / week

Rs. 12

40 hrs

40 hrs

1. Decision Variables??? 2. Let

X1, X2, and X3 be the quantities of soap,

shampoo and liquid soap manufactured per week.

3. Constraints???
4. Time available per week (40 hours) 5. Last, the objective function (Max Profit or Minimize Cost)

Maximize

Z = 10X1 +13X2 + 12X3

Objective Function

Subject to 3X1 + 4X2 + 4X3 < 40 5X1 + 4X2 + 2X3 < 40 X1 > 0, X2 > 0, X3 > 0 X1, X2 , X3

Constraints Non-Negativity Constraints

Decision Variables

A middle-aged woman, convalescing after a surgery,

has been advised by her doctor to plan her diet in

such a way as to ensure that she gets the prescribed quantities of vitamins. The choice of foods available to her, the amounts of vitamins they contain, the cost of each unit and the daily requirement of vitamins are shown in the table

Cost

Vitamin A

Vitamin B

Vitamin D

Eggs

Rs 1.50/unit 15 mg/unit 40 mg/unit 10 mg/unit

Milk
Cereals Daily requirement

Rs. 14.00/lit
Rs. 18/unit (kg)

30 mg/lit
10 mg/kg 100 mg

25 mg/lit
55 mg/kg 250mg

20 mg/lit
30 mg/kg 120mg

Formulate a linear programme to determine the

quantity of each food that the woman needs to buy in order to minimize her total expenditure, ensuring at

the same time that she meets her daily requirements

of vitamins.

Decision Variables?

X1, X2, X3 be the quantities of eggs, milk and cereals

bought Constraints? Dietary requirements are to be satisfied Objective Function Minimization of expenditure

Let X1, X2, X3 be the quantities of eggs, milk and cereals bought. The problem is of the form

(i) There is an objective function which describes what we desire (ii) A set of constraints, usually in the form of inequalities (iii) Non-negativity constraints for the decision variables (iv) The objective function and the constraints are linear.

Max / Min Z = C1 x1 + C2 x2 +..+ Cn xn

Subject to

a11 x1 + a12 x2 + + a1n xn < or b1 a21 x1 + a22 x2 + + a2n xn < or b2

. .

an1 x1 + an2 x2 + + amn xn < or bm x1 , x2 ,.., xn - Unrestricted in Sign b1 , b2 ,.., bm - Unrestricted in Sign OR

Maximize / Minimize Z C j x j
j

Subject to

a x
j 1 ij

or bi i 1.....m

bi Unrestricted in sign i 1.....m x j Unrestricted in sign j 1.....n

Proportionality Additivity Divisibility Certainty

A financial advisor who recently graduated from IIMK

received a call from a client who wanted to invest a

portion of a $ 150,000 inheritance

The client wanted to realize an annual income, but

also wanted to spend some of the money

After discussing the matter, the client and the adviser agreed that a mutual fund, corporate bonds, and a money market account would make suitable investments.

The client was willing to leave allocation of the funds among these investment vehicles to the financial adviser, but with the following conditions:
At least 25 percent of the amount invested should be in the money market account A maximum of only 35% should be invested in corporate bonds The investment must produce at least $ 12,000 annually (ROI) The un-invested portion should be as large as possible

The annual returns would be 11 percent for the mutual fund, 8 percent for the bonds, and 7 percent for the money market

Formulate an LP model that will achieve the clients requests. Ignore transaction costs, the advisers fee and so on.

Let X1, X2, X3 be the amounts to be invested in mutual fund, corporate bonds and money market

Non-negativity condition: X1, X2, X3 0

At least 25 percent of the amount invested should be in the money market account X3 / (X1+X2+X3) 0.25 A maximum of only 35% should be invested in corporate bonds X2 / (X1+X2+X3) 0.35 The investment must produce at least $12,000 annually (ROI) 0.11X1 + 0.08X2 + 0.07X3 12000

Objective Function: Maximize Z = 150,000 (X1 + X2 + X3)

A trucking company with Rs.20 crores to spend on new equipment is contemplating three types of vehicles

Vehicle A has a 10-ton payload and is expected to cover 55 km per hour. It costs Rs.40 lakhs.

Vehicle B has a 20-ton payload and is expected to cover 50 km per hour. It costs Rs.65 lakhs.

Vehicle C is a modified form of B: it carries sleeping quarters

for one driver, and this reduces its capacity to 18-tons and
raises the cost to Rs.75 lakhs.

Vehicle A requires a crew of one man, and, if driven on three shifts per day, could be run for an average of 18 hours per day. Vehicles B and C require a crew of two men each. Where, B would be driven 18 hours per day with three shifts, C could be run for an average 21 hours per day. The company has 150 drivers available each day and would find it very difficult to obtain further crews. Maintenance facilities are such that the total number of vehicles must not exceed 30. How many vehicles of each type should be purchased if the company wishes to maximize its capacity in ton-km per day?

A senior executive of a public sector company

recently quit his job under the VRS with a hefty

packet of Rs 1 Crore. Messrs. Dhana-chor Chit Fund people: Company has offered the following investment scheme for the benefit of such retired

"Invest a certain sum (in lakhs of rupees) in any

month, invest half of that amount in the next month. In the subsequent month, one would get

twice the amount invested originally in the first

month

This scheme is available only for the next six months (Encashment is possible on 181st day) Returns received at the end of any month can be used immediately for reinvesting either as a fresh investment or as a follow-up investment

Let Xt = Fresh investment on the 0th, 30th, 60th,

90th, 120th day respectively (t = 1,2,3,4,5) (in

lakhs of Rs.)

Noting that, in any month, the cash outflow must not exceed the cash on hand, the following linear programme is formulated

Day 0:

X1

100

Day 30:

Day 60:

X1 X 2 100 X1 2 X2 X1 X 3 100 X2 2 2

Day 90:
Day 120: Day 150:

X3 X1 X 2 X 4 100 X3 2 2 2
X4 X 5 100 2 X5 100 2 X1 2 X1 2 X2 X3 X4 2 2 X2 X3 X4 X5 2 2 2

On 181st day, the cash on hand must be maximum Hence the objective function is

A hospital administrator has the following minimal daily requirements for nursing personnel:
Period 1 2 Clock Time 6 AM to 10 AM 10 AM to 2 PM Minimal No. of nurses 60 70

3
4 5 6

2 PM to 6 PM
6 PM to 10 PM 10 PM to 2 AM 2 AM to 6 AM

60
50 20 30

Nurses report to the hospital wards at the beginning of each period and work for 8 consecutive hours. The hospital wants to determine the minimal number of nurses to employ so that there will be a sufficient number of personnel available for each period.

A brewery blends three raw materials, A, B and C in varying proportions to obtain three final products, D, E and F. The salient data is given below.
Final Product Selling price/ Litre Ingredient Cost/ Litre Quantity Available D $15 A $10 10,000 E $9 B $8 12,000 F $12 C $7 15,000

Final Product D E

Specifications At least 25% of ingredient A Not more than 15% of C At least 50% of ingredient B Not more than 30% of C

At least 65% of ingredient C Not more than 5% of A

Formulate a linear programme to maximize the net profit of the brewery.

Solution to Example Problem No.7

Let Xij be the no. of litres of the ith raw material in jth the product

B
C

A shipping company has to lift three types of

cargo whose details are given below.

Type of Cargo Quantity (tons) Volume per ton Profit per ton

A
B C

300
500 400

1.2 m3
0.8 m3 1 m3

Rs. 10,000
Rs. 7,000 Rs. 8,000

Weight in aft, center, forward must be in the same proportion as the holding capacities by weight, i.e., 100 : 200 : 75

Formulate a linear programme to maximize the profits of the shipping company.

Solution to Example Problem No.8

Constraints on holding space

A final product is assembled with 4 units of component A and 3 units of component B. The manufacturing shop runs three different processes, each of which requires varying amounts of raw materials and produce different amounts of A and B. Two types of raw materials are used. 100 units of raw material I (RM I) and 200 units of raw material II (RM II) are available to the shop each day

Shop

Input per run (units) RM I RM II 5

Output per run (units) A 6 B 4

II
III

4
2

8
7

5
7

8
3

100

200

Formulate a linear programme to maximize the number

of completed assemblies produced each day.

Let X1, X2, X3 be the number of runs of each

process operated per day

Total quantity of A produced = Total quantity of B produced =

No. of units of finished product??

A machine tool company conducts a job-training program for machinists Trained machinists are used as teachers in the program at a ratio of one for every ten trainees. The training program lasts for one month (Assumption: No. of trainees multiple of 10) From past experience it has been found that out of ten trainees hired, only seven complete the program successfully (the unsuccessful trainees are released) Trained machinists are also needed for machining and the companys requirements for the next three months are as follows: January 100 February 150 March 200

In addition, the company requires 250 trained machinists by

April. There are 130 trained machinists available at the beginning of the year. Payroll costs per month are:

Each Trainee
Each trained machinist (machining or teaching)

$ 400
$ 700

Each trained machinist idle

$500

(Union contract forbids firing trained machinists) Set up the linear programming problem that will produce the

minimum cost hiring and training schedule and meet the

companys requirements.

Every month, a trained machinist can do one of the following: (1) Work a machine, (2) Teach or (3) Stay idle Since the number of trained machinists for machining is fixed, the only decision variables are the number teaching and the number idle for each month. Thus, the decision variables are: X1 trained machinists teaching in January X2 trained machinists idle in January X3 - trained machinists teaching in February X4 trained machinists idle in February X5 trained machinists teaching in March X6 trained machinists idle in March

Number machining + Number teaching + Number idle = Total trained machinists available at the beginning of the month For January : 100 + X1 + X2 = 130 For February : 150 + X3 + X4 = 130 + 7X1 For March : 200 + X5 + X6 = 130 + 7X1 + 7X3 Since the company requires 250 trained machinists by April, 130 + 7X1 + 7X3 + 7X5 = 250 Objective Function: Minimize Z = 400 (10X1 + 10X3 + 10X5) +700 (X1 + X3 + X5) +500 (X2 + X4 + X6)

50 units produced

F1

$ 900/unit

30 units needed
W1

$ 300/unit

$ 200/unit

10 units max

DC

40 units produced

F2

$ 200/unit

W2

60 units needed