Introduction to Operation Research

❖ Terminology
• The British/Europeans refer to “Operational Research", the Americans to
“Operations Research" - but both are often shortened to just "OR".

• Another term used for this field is “Management Science" ("MS"). In U.S. OR
and MS are combined together to form "OR/MS" or "ORMS".

• Yet other terms sometimes used are “Industrial Engineering" ("IE") and
“Decision Science" ("DS").

• It had its early roots in World War II and is flourishing in business and industry
with the aid of computer

• Primary applications areas of Operations Research include forecasting, production

scheduling, inventory control, capital budgeting, and transportation

❖ What is Operations and Research?

• Operations: the activities carried out in an organization

• Research: the process of observation and testing scientific method includes

Situation, problems, model construction and experimentation

• Operations Research is a quantitative approach to decision making based on the

scientific method of problem solving.

• OR is simply a scientific approach to decision making that seeks to best design

and operate a system, usually under conditions requiring the allocation of scare
resources.

• Operations Research is the scientific approach to execute decision making,

which consists of:

• The art of mathematical modeling of complex situations

• The science of the development of solution techniques used to solve these models

• The ability to effectively communicate the results to the decision maker

❖ Problem Solving and Decision Making

• 7 Steps of Problem Solving

(First 5 steps are the process of decision making)

– Identify and define the problem.

– Determine the set of alternative solutions.

– Determine the criteria for evaluating the alternatives.

– Evaluate the alternatives.

– Choose an alternative.

– Implement the chosen alternative.

– Evaluate the results.

 Linear programming problem
❖ Constructing a Model
• Problem must be translated from verbal, qualitative terms to logical, quantitative
terms

• A logical model is a series of rules, usually embodied in a computer program

• A mathematical model is a collection of functional relationships by which

allowable actions are delimited and evaluated.

❖ Steps for constructing mathematical model:

1. Define the variables of the problem.
2. Construct the model, which consist of three parts:
a) Objective function
b) Function constraints
c) Non-negativity constraints

❖ Advantages of models:
Generally, experimenting with models (compared to experimenting with the real
situation):
• Requires less time
• Is less expensive
• Involves less risk

• Cost/benefit considerations must be made in selecting an appropriate

mathematical model.

• Frequently a less complicated (and perhaps less precise) model is more

appropriate than a more complex and accurate one due to cost and ease of solution
considerations.

❖ Steps of mathematical model:

• Relate decision variables (controllable inputs)
• Frequently seek to maximize or minimize some objective function subject
to constraints.
• The values of the decision variables that provide the mathematically-best
output are referred to as the optimal solution for the model.
❖ Model Formulation:
• Introduction
• Many management decisions involve trying to make the most effective use
of an organization’s resources.
• Resources typically include machinery, labor, money, time, warehouse
space, or raw materials.

• Resources may be used to produce products (such as machinery, furniture,

food, or clothing) or services (such as schedules for shipping and
production, advertising policies, or investment decisions).

• Linear programming (LP) is a widely used mathematical technique

designed to help managers in planning and decision making relative to
resource allocation.

• Despite the name, linear programming, and the more general category of
techniques called “mathematical programming”, have very little to do with
computer programming.

• In the world of Operations Research, programming refers to modeling and

solving a problem mathematically.

• Computer programming has, however, played an important role in the

advancement and use of LP to solve real-life LP problems
Example: Giapetto woodcarving Inc.,

Giapetto Woodcarving, Inc., manufactures two types of wooden toys: soldiers and trains.
A soldier sells for $27 and uses $10 worth of raw materials.

Each soldier that is manufactured increases Giapetto’s variable labor and overhead cost
by $14. A train sells for $21 and uses $9 worth of raw materials. Each train built
increases Giapetto’s variable labor and overhead cost by $10.

The manufacture of wooden soldiers and trains requires two types of skilled labor:
carpentry and finishing. A soldier requires 2 hours of finishing labor and 1 hour of
carpentry labor. A train requires 1 hour of finishing and 1 hour of carpentry labor. Each
week, Giapetto can obtain all the needed raw material but only 100 finishing hours and
80 carpentry hours.

Demand for trains is unlimited, but at most 40 soldiers are bought each week. Giapetto
wants to maximize weekly profit.

Formulate a linear programming model of Giapetto’s situation that can be used to

maximize Giapetto’s weekly profit.
 • Solution: Giapetto woodcarving Inc.,

Step 1: Model formulation

1. Decision variables: we begin by finding the decision variables. In any LP, the
decision variables should completely describe the decisions to be made. Clearly,
Giapetto must decide how many soldiers and trains should be manufactured each
week. With this in mind, we define:
X1 = number of soldiers produced each week
X2 = number of trains produced each week

2. Objective function: in any LP, the decision maker wants to maximize (usually
revenue or profit) or minimize (usually costs) some function of the decision
variables. The function to be maximized or minimized is called the objective
function. For the Giapetto problem, we will maximize the net profit (weekly
revenues – raw materials cost – labor and overhead costs).

Weekly revenues and costs can be expressed in terms of the decision variables,
X1 and X2 as following:

• Weekly revenues = weekly revenues from soldiers + weekly revenues from trains

= 27 X1 + 21 X2

Also,

Weekly raw materials costs = 10 X1 + 9 X2

Other weekly variable costs = 14 X1 + 10 X2

Therefore, the Giapetto wants to maximize:

(27 X1 + 21 X2) – (10 X1 + 9 X2) – (14 X1 + 10 X2) = 3 X1 + 2 X2

Hence, the objective function is:

Maximize Z = 3 X1 + 2 X2

3. Constraints: as X1 and X2 increase, Giapetto’s objective function grows larger. This

means that if Giapetto were free to choose any values of X1 and X2, the company could
make an arbitrarily large profit by choosing X1 and X2 to be very large. Unfortunately,
the values of X1 and X2 are limited by the following three restrictions (often called
constraints):

Constraint 1: each week, no more than 100 hours of finishing time may be used.

Constraint 2: each week, no more than 80 hours of carpentry time may be used.
Constraint 3: because of limited demand, at most 40 soldiers should be produced.

• The three constraints can be expressed in terms of the decision variables X 1 and
X2 as follows:

Constraint 1: 2 X1 + X2  100

Constraint 2: X1 + X2  80

Constraint 3: X1  40

Note:

The coefficients of the decision variables in the constraints are called technological
coefficients. This is because its often reflect the technology used to produce different
products. The number on the right-hand side of each constraint is called Right-Hand Side
(RHS). The RHS often represents the quantity of a resource that is available.

• Sign restrictions: to complete the formulation of the LP problem, the following

question must be answered for each decision variable: can the decision variable
only assume nonnegative values, or it is allowed to assume both negative and
positive values?

If a decision variable Xi can only assume a nonnegative values, we add the sign
restriction (called nonnegativity constraints)

Xi  0.

If a variable Xi can assume both positive and negative values (and zero), we say that Xi is
unrestricted in sign (urs).

In our example the two variables are restricted in sign, i.e., X1  0 and X2  0
 • Combining the non-negativity constraints with the objective function and the
structural constraints yield the following optimization model (usually called LP
model):

Max Z = 3 X1 + 2 X2 (objective function)

(st)

2 X1 + X2  100 (finishing constraint)

X1 + X2  80 (carpentry constraint)

X1  40 (soldier demand constraint)

X1  0 and X2  0 (nonnegativity constraint)

The optimal solution to this problem is :

X1 = 20, and X2 = 60, Z = 180

Applications Of LP

1. Product Mix problem

2. Diet problem
3. Media selection problem
4. Assignment problem
5. Transportation problem
6. Portfolio selection problem
7. Production selection problem
8. Inventory problem
9. Multi period financial problem
10. Capital budgeting problem
 1) Product Mix Problem:
Formulate a linear programming model for this problem, to determine how many containers
of each product to produce tomorrow in order to maximize the profits. The company makes
four types of juice using orange, grapefruit, and pineapple. The following table shows the price
and cost per quart of juice (one container of juice) as well as the number of kilograms of fruits
required to produce one quart of juice.

Product Price/quart Cost/quart Fruit needed

Orange juice 3 1 1 Kg.

Grapefruit juice 2 0.5 2 Kg.

Pineapple juice 2.5 1.5 1.25 Kg.

All –in – one 4 2 0.25 Kg each

On hand there are 400 Kg of orange, 300 Kg. of grapefruit, and 200 Kg. of pineapples.
The manager wants grapefruit juice to be used for no more than 30 percent of the number
of containers produced. He wants the ratio of the number of containers of orange juice to
the number of containers of pineapples juice to be at least 7 to 5. Pineapples juice should
not exceed one-third of the total product.
 1) Media selection problem
A company has budgeted up to $8000 per week for local advertisement. The money is to
be allocated among four promotional media: TV spots, newspaper ads, and two types of
radio advertisements. The company goal is to reach the largest possible high-potential
audience through the various media. The following table presents the number of potential
customers reached by making use of advertisement in each of the four media. It also
provides the cost per advertisement placed and the maximum number of ads than can be
purchased per week.

Medium Audience Cost per ad Maximum ads

per week
Reached per ad

TV spot (1 minute) 5000 800 12

Daily newspaper 8500 925 5

(full-page ad)

Radio spot 2400 290 25

(30 second, prime time)

Radio spot 2800 380 20

(1 minute, afternoon)

The company arrangements require that at least five radio spots be placed each week. To
ensure a board-scoped promotional campaign, management also insists that no more than
$1800 be spent on radio advertising every week.
 1) Transportation problem
The Top Speed Bicycle Co. manufactures and markets a line of 10-speed bicycles
nationwide. The firm has final assembly plants in two cities in which labor costs are low,
New Orleans and Omaha. Its three major warehouses are located near the larger market
areas of New York, Chicago, and Los Angeles.

The sales requirements for next year at the New York warehouse are 10000 bicycles, at
the Chicago warehouse 8000 bicycles, and at the Los Angeles warehouse 15000 bicycles.
The factory capacity at each location is limited. New Orleans can assemble and ship
20000 bicycles; the Omaha plant can produce 15000 bicycles per year. The cost of
shipping one bicycle from each factory to each warehouse differs, and these unit shipping
costs are:

New York Chicago Los Angeles

New Orleans $2 3 5

Omaha 3 1 4

The company wishes to develop a shipping schedule that will minimize its total annual
transportation cost
 1) Portfolio selection
The International City Trust (ICT) invests in short-term trade credits, corporate bonds,
gold stocks, and construction loans. To encourage a diversified portfolio, the board of
directors has placed limits on the amount that can be committed to any one type of
investment. The ICT has $5 million available for immediate investment and wishes to do
two things: (1) maximize the interest earned on the investments made over the next six
months, and (2) satisfy the diversification requirements as set by the board of directors.
The specifics of the investment possibilities are:

Investment Interest earned % Maximum investment

($ Million)

Trade credit 7 1

Corporate bonds 11 2.5

Gold stocks 19 1.5

Construction loans 15 1.8

In addition, the board specifies that at least 55% of the funds invested must be in gold
stocks and construction loans, and that no less than 15% be invested in trade credit.
A firm produces 4 products A, B, C and D. Each unit of product A requires 4 hours of
milling, 1 unit of assembly and worth $ 12 of in-process inventory.

Each unit of product B requires 1 hour of milling, 4 hours of assembly, and worth $ 10 of
in-process inventory.

Each unit of product C requires 2 hours of milling, 2 hours of assembly and worth $ 5 of
in-process inventory.

Finally each unit of product D requires 5 hours of milling, no assembly, and worth $ 14
of in-process inventory.

The firm has 150 hours of milling time, 140 hours of assembly time available. In
addition, not more than $ 1,500 may be tied up in in-process inventory.

Each unit of product A returns $ 25 profit, each unit of B return $ 40 profits, each unit of
C has profit of $ 32, and each unit of product D returns $ 24 profits.

Not more than 22 units of product A can be sold, not more than 16 units of product C can
be sold, and any number of products B & D can be produced and sold to satisfy a contract
requirement.

The firm objective is to maximize the profit resulting from the sale of the four products.

Formulate the above linear programming model.

Assignment: to be submitted Tuesday
28.02.2017
An operation manager is trying to determine a production plan for the next week. There
are three products (P,Q and R) to produce using four machines (A,B,C and D) each of the
four machines performs a unique process. There is one machine of each type, and each
machine is available for 2400 minutes per week. The unit processing times for each
machine is given in table 1:

Table 1: Machine Data;

Unit processing time (min)

Machine Product P Product Q Product R Availability
A 20 10 10 2400
B 12 28 16 2400
C 15 6 16 2400
D 10 15 0 2400
Total 57 59 42 9600
processing time

The unit revenues and maximum sales for the week are indicated in table 2. Storage from
one week to the next is not permitted. The operating expenses associated with the plant
are $6000 per week, regardless of how many components and products are made. The
$6000 includes all expenses except for material costs.

Table 2: product Data:

Item Product P Product Q Product r

Revenue/ unit $90 $100 $70
Material cost/ unit 45 40 20
Profit/unit 45 60 50
Maximum sales 100 40 60

The manager seeks the optimal product mix that is, the amount of each product that
should be manufactured during the present week in order to maximize profits. Formulate
this as LP.

Graphical Methehod in linear programming

Linear programming is an application of matrix algebra used to solve a broad class of
problems that can be represented by a system of linear equations.

A linear equation is an equation whose variable quantity or quantities are in the first
power only and whose graph is a straight line.

LP problems are characterized by an objective function that is to be maximized or

minimized subject to a number of constraints; both the objective function and the
constraints must be formulated in terms of a linear equality or inequality.

The following assumptions must be satisfied to justify the use of linear programming.

• Linearity: all functions such as costs, price and technological requirements, must
be linear in nature.
• Certainty: all parameters are assumed to be known with certainty.
• Non-negativity: negative values of decision variables are unacceptable.

❖ Two approaches were commonly used to solve LP problems:

• Graphical method
• Simplex method
The graphical method is limited to LP problems involving two decision variables and a limited
number of constraints due to the difficulty of graphing and evaluating more than two decision
variables. This restriction usually limits the use of the graphical method in real life.