Introduction to Decision

Modelling: Model Formulation

Dr. Shraddha Mishra

IMI, New Delhi
Topics • Introduction to DM & OR
• Terminology used in Model Formulations
• Linear programming
• Characteristics of Linear Programming Problems
• Model Formulation
• A Maximization Model Example
• A Minimization Model Example
• Irregular Types of Linear Programming Models
2
What is
Operations
Research ?

• Operations research (OR) also called as Decision Science or

Management Science, is the art and science of problem-solving and
decision-making for the management of organizations.

3
 Application areas of DM/OR

Logistics Pricing
Location
& Supply and
Strategic and Schedulin
chain revenue
planning Layout g
managem managem
problems
ent ent
Portfolio
Inventory Risk
Managem . .
analysis Analysis
ent
OR Applications:

 Dark Stores
 Strategic
locations
 SOP
 Route
Optimization
 Scheduling
  Platform Sharing
Strategy (6 to 2)
 Optimizing
resources(carryover
parts) (30% to 70%)
 Economies of Scale

How TATA motors' GENIUS STRATEGY is racing it pa

st Hyundai & Suzuki in India? : Business Case study
- YouTube
 In Decision
Identifying a problem that
Modelling Modelling,
problems
are broken needs to be solved.
simplifies down into
basic

complex
component
s and then
solved in
Constructing a model around
the problem that resembles
problems… defined
steps by
mathemati
the real world and variables.
cal
analysis.
Using the model to derive
solutions to the problem.

Testing each solution on the

model and analyzing its
success.

Implementing the solution to

the actual problem.
 Linear Programming:
An Overview
• Linear programming is an analytical technique in
which linear algebraic relationships represent a
firm’s decisions, given a business objective, and
resource constraints.
• Objectives of business decisions frequently
involve maximizing profit or minimizing
costs.
• Steps in application of LPP:
• Identify problem as solvable by linear
programming.
• Formulate a mathematical model of the
unstructured problem.
• Solve the model. 8
 • Decision variables - mathematical symbols
representing levels of activity of a firm.

• Objective function - a linear mathematical relationship

Model describing an objective of the firm, in terms of decision
variables - this function is to be maximized or minimized.

Formulati • Constraints – requirements or restrictions placed on the

on
9
firm by the operating environment, stated in linear
relationships of the decision variables.

• Parameters - numerical coefficients and constants used

in the objective function and constraints.
 Proportionality - The rate of change
(slope) of the objective function and
constraint equations is constant.

Properties Additivity - Terms in the objective

function and constraint equations

of Linear must be additive.

Programmi Divisibility -Decision variables can

take on any fractional value and are

ng Models therefore continuous as opposed to

integer in nature.

Certainty - Values of all the model

parameters are assumed to be known
with certainty (non-probabilistic).

10
Summary of Step Clearly define the decision
Model 1 variables
Formulation
Steps
Step Construct the objective
2 function

Step Formulate the constraints

3
11
 LP Model Formulation : A Maximization Example
Beaver Creek Pottery Company
• How many bowls and mugs should be produced to maximize profits given
labor and materials constraints?
• Product resource requirements and unit profit:

Resource Requirements
Labor Clay Profit
Product
(hr/unit) (lb/unit) ($/unit)
Bowl 1 4 40
Mug 2 3 50

12
 13
Figure: Beaver Creek Pottery Company
 LP Model
Formulation
A Maximization Example
Resource 40 hrs of labor per day
Availability: 120 lbs of clay per
day
Decision
Variables x1 = number of bowls to produce per day
: x2 = number of mugs to produce per day
Objective Maximize Z = 40*x1 + 50*x2
Where Z = profit per day
Function:
1*x1 + 2*x2  40 hours of labor
Resource 4*x1 + 3*x2  120 pounds of clay
Constraints:
x1  0; x2  0
Non-Negativity
14
Constraints:
Complete LP
Model
Formulation
Maximize Z = 40*x1 + 50*x2

subject to: 1*x1 + 2*x2  40 (Labour Constraint)

4*x1 + 3*x2  120(Raw material Constraint)
x1, x2  0 (Non-negativity constra

15
Terminology
•Feasible solution:
• Any solution of LPP/ NLP which do not violate constraints is called
feasible solution.
• Feasible solution may be optimal (best) solution.
• Any LPP/NLP can have more than one feasible solution.
• Optimal solution to LPP/NLP must be a feasible solution.

•Infeasible Solution:
• Any solution which violates at least one constraint is called infeasible
solution.
• Any LPP/NLP have infinite number of infeasible solution.
• Infeasible solution lies outside the bounded region.
Optimal Solution:
• It is a feasible solution that has the most favorable value of the objective
function.
• The most favorable mean the largest possible objective value if the objective
is to maximize and smallest value if the objective is to minimize.
• A LPP/ NLP can have more than one Optimal solution.
Corner Point Feasible Solution:
• CPF is a solution that lies at the corner of the feasible region
• Every LPP with feasible solution and bounded feasible region must possess
CPF solutions and at least one optimal solution.
• The best CPF solution must be an optimal solution.
• If LPP has exactly one one optimal solution, it must be a CPF solution.
Bounded feasible Region
• A closed region.
• A bounded feasible region will have both a maximum value
and a minimum value.

Unbounded Region

• feasible region extends indefinitely in any direction

• If the coefficients on the objective function are all positive, then an
unbounded feasible region will have a minimum but no maximum.

18
 Feasible Solutions

• A feasible solution does not violate any of the constraints:

Example x1 = 5 bowls
x2 = 10 mugs
Z = 40*x1 + 50*x2 = 700
Labor constraint check:
1(5) + 2(10) = 25 < 40 hours, within constraint Clay
constraint check:
4(5) + 3(10) = 50 < 120 pounds, within constraint

19
 Infeasible Solutions
• An infeasible solution violates at least one of the
constraints:
Example x1 = 10 bowls
x2 = 20 mugs
Z = 1400
Labor constraint
check:
1(10) + 2(20) = 50
> 40 hours,
violates
constraint
20
 Graphical Solution of LP
Models
• Graphical solution is limited to linear programming models containing only two
decision variables (can be used with three variables but only with great
difficulty).

• Graphical methods provide visualization of how a solution for a linear

programming problem is obtained.

21
Coordinate Axes
Graphical Solution of Maximization Model

Maximize Z = $40x1 + $50x2

subject to: 1x1 + 2x2  40
4x1 + 3x2  120
x1, x2  0

Coordinates for Graphical Analysis 22

Irregular Types of Linear Programming
Problems

• For some linear programming models, the general rules

do not apply.

• Special types of problems include those with:

– Multiple optimal solutions
– Infeasible solutions
– Unbounded solutions

23
An Infeasible Problem

Every possible solution

violates at least one
constraint:
Maximize Z = 5x1 + 3x2
subject to: 4x1 + 2x2  8
x1  4
x2  6
x1, x2  0

Figure: Graph of an Infeasible Problem

24
An Unbounded
Problem
Value of objective function
increases indefinitely:
Maximize Z = 4x1 + 2x2
subject to: x1  4
x2  2 x1, x2
0

Figure: Graph of an Unbounded Problem 29

Bounded Feasible Region
Area

Max. Z = 40x1 + 50x2

s.t. 1x1 + 2x2  40
4x1 + 3x2 
120
x1, x2  0

30
Figure: Feasible Solution
Corner Point Solutions
Graphical Solution of
Maximization Model
Maximize Z = 40x1 + 50x2
subject to:1x1 + 2x2  40
4x2 + 3x2  120
x1, x2  0

Figure 11: Solutions at All Corner Points 13

Case of Multiple Optimal
Solutions Beaver Creek
Pottery Example
Objective function is parallel to a
constraint line.
Maximize Z=40x1 + 30x2 subject to:
1x1 + 2x2  40
4x1 + 3x2  120
x1, x2  0
Where:
x1 = number of bowls x2 = number
of mugs

Figure 18: Example with Multiple Optimal Solutions 23

LP Model Formulation A Minimization
Example
• Two brands of fertilizer available - Super-Gro, Crop-Quick.
• Field requires at least 16 pounds of nitrogen and 24 pounds of phosphate.
• Super-Gro costs $6 per bag, Crop-Quick $3 per bag.
• Problem: How much of each brand to purchase to minimize total cost of
fertilizer given following data ?
Chemical Contribution
Nitrogen Phosphate
Brand
(lb/bag) (lb/bag)
Super-gro 2 4

Crop-quick 4 3 15
 Decision Variables:
x1 = bags of

Super-Gro x2 = bags of

Crop-Quick
The Objective
Function:
Minimize Z = 6x1 + 3x2
Where: 6x1 = cost of bags of
Super-Gro 3x2 = cost of bags of
Crop-Quick
Figure 13: Fertilizing Farmer’s field Model Constraints:
2x1 + 4x2  16 lb (nitrogen constraint)
16

4x + 3x  24 lb (phosphate constraint)
Minimize Z = 6x1 + 3x2
subject to:2x1 + 4x2  16
4x1 + 3x2  24
x1, x2  0

Figure 14: Graph of Both Model Constraints 18

Feasible Solution Area
A Minimization
Example
Minimize Z = 6x1 + 3x2
subject to:2x1 + 4x2  16
4x1 + 3x2  24
x1, x2  0

Figure 15: Feasible Solution Area 19

Problem 1
An airline offers coach and first-class tickets. For the airline to be profitable,
it must sell a minimum of 25 first-class tickets and a minimum of 40 coach
tickets. The company makes a profit of $225 for each coach ticket and $200
for each first-class ticket. At most, the plane has a capacity of 150 travellers.
How many of each ticket should be sold to maximize profits?

Answer: x = 125, y = 25, Z = 33125

 Level 2: MODEL FORMULATION
 Product Mix problem

In a product-mix problem, there are two or more products, competing

for limited resources such as limited production capacity/labor hours.

The problem is to find out which products to include in the production

plan and in what quantities these should be produced (product mix)
in order to maximize profit, market share, or some other goal.

17
 Example 1: Product mix problem
For example: product P consists of two subassemblies. To
manufacture the first subassembly, one unit of RM1 passes
through machine A for 15 minutes. The output of machine A
is moved to machine C where it is processed for 10 minutes.
The second subassembly starts with RM2 processed in
machine B for 15 minutes. The output is taken to machine C
for 5 minutes of processing. The two subassemblies are
joined with a purchased part in machine D. The result is a
finished unit of P. Product Q is manufactured by a similar
process as indicated in the figure. The rounded rectangles at
the top of the figure indicate the revenue per unit and the
maximum sales per week.

The rectangle at the upper left indicates that one machine of

each type is available. Each machine operates for 2400
minutes per week. For this case the operating expenses, not
including the raw material cost is $6000. This amount is
RM: Raw Material expended regardless of amounts of P and Q produced.
OE: Operating
Expenses Our problems include the following: Find the product mix
that maximizes profit. 35
 The decisions involve the amounts of the two products.
P= amount of product p is produced Q=
amount of product q is produced
Maximize Z = 45*P + 60*Q - 6000
Subject to:
15*P + 10*Q <= 2400 (Constraint for M/C A)
15*P + 30*Q <= 2400 (Constraint for M/C B)
15*P + 5*Q <= 2400 (Constraint for M/C C)
10*P + 5*Q <= 2400 (Constraint for M/C D)
P <= 100 (max sales)
Q <= 50
P,Q >=0 (Non-negativity constraints)

36
 Financial Planning
A bank makes four kinds of loans to its personal customers and these loans yield the following annual interest rates to
the bank:
• First mortgage 14%
• Second mortgage 20%
• Home improvement 20%
• Personal overdraft 10%
The bank has a maximum foreseeable lending capability of ₹250 million and is further constrained by the policies:
• first mortgages must be at least 55% of all mortgages issued and at least 25% of all loans issued (in ₹ terms)
• second mortgages cannot exceed 25% of all loans issued (in ₹ terms)
• to avoid public displeasure and the introduction of a new windfall tax the interest on all loans must not exceed
15%.
Formulate the bank's loan problem as an LP to maximise interest income whilst satisfying the policy limitations.
Decision Variables
Let, xi = amount loaned in type i in Rs.(million) (where i=1 corresponds to first mortgages, i=2 to second mortgages etc)

Objective: To maximise interest income

Zmax = 0.14x1 + 0.20x2 + 0.20x3 + 0.10x4
Subject to the constraints:
(a) limit on amount lent: x1 + x2 + x3 + x4 <= 250
(b) policy condition 1:
first mortgages >= 0.55(total mortgage lending): x1 >= 0.55(x1 + x2)
first mortgages >= 0.25(total loans): x1 >= 0.25(x1 + x2 + x3 + x4)) (c) policy condition 2
second mortgages <= 0.25(total loans): x2 <= 0.25(x1 + x2 + x3 + x4)
(d) policy condition 3
total annual interest <= 0.15on total loans of (x 1 + x2 + x3 + x4).
0.14x1 + 0.20x2 + 0.20x3 + 0.10x4 <= 0.15(x1 + x2 + x3 + x4)

(e) non-negativity: xi >= 0 (i=1,2,3,4).

Note: while solving the model, all the variables should be transferred to the left-hand side of the inequality. So, 2 nd
constraint will become: 0.45x1 - 0.55x2 >= 0, and so on
Diet/Blending problem
Another classic problem that can be modeled as a LP concerns blending
ingredients to obtain a product with certain characteristics. The
product must satisfy several nutrient restrictions.
final
ingredients, their nutritive contents The possible kilograms
(in
• kilograms of ingredient) and the of
unit cost are shown in the nutrient perNutritive content and price of ingredients
following table.
Ingredients Calcium Protein Fiber Unit
• The mixture must meet the cost
following restrictions:
• Calcium — at least 0.8% but not
Limestone 0.38 0.0 0.0 10.0
more than 1.2%. Corn 0.001 0.09 0.02 30.5
• Protein — at least 22%. Soyabean 0.002 0.5 0.08 90.0
• Fiber — at most 5%.
The problem is to find the composition of the food mix that satisfies these constraints
while minimizing cost.
39
Formulation:

L, C, S : proportions of limestone, corn, and soybean meal, respectively,

in the mixture
Objective function:
Because each decision variable is defined as a fraction of a kilogram, the
objective is to minimize the cost of providing one kilogram of feed mix.
Minimize Z = 10L + 30.5C + 90S
Subject to constraint:
0.38L + 0.001C + 0.002S >
0.008
0.38L + 0.001C + 0.002S <
0.012
0.09C + 0.50S > 0.22
0.02C + 0.08S < 0.05 40