Quantitative Analysis for Management Decision

Lecture 2
Linear programing (LP)
Course leader : Shewayirga Assalf (Ass.Pro.)
 History of LP

 LP was developed by the Russian mathematician L. V.

Kantorovich in 1939 and extended by the American
mathematician G. B. Dantzig in 1947 at air force.

 The original name for this technique, "programming in a linear

structure," which was later shortened to "linear programming."
 Meaning of LP
 LP is a mathematical technique for choosing the best
alternative from the a set of feasible alternatives.

 Linear programming (LP) problems are optimization problems

where the objective function and the constraints of the problem
are all linear.

 Linear programming is the subject of studying and solving

linear programs.
 Introduction

 Linear Programming(MP) is a field of

management science or operations research
that finds most efficient way of using
limited resources to achieve the objectives
of a business.

Optimization
Characteristics of Optimization Problems
 One or more decisions

 Restrictions or constraints
e.g. Determining the number of products to manufacture

a limited amount of raw materials

a limited amount of labor

 Objective

– The production manager will choose the mix of products that

maximizes profits

– Minimizing the total cost

 Expressing optimization problems
mathematically

 Decision variables
X1 , X2 , X3 , … , Xn
e.g. the quantities of different products
Index n = the number of product types

 Constraints
– a less than or equal to constraint : f(X1 , X2 , X3 , … , Xn) < b
– a greater than or equal to constraint : f(X1 , X2 , X3 , … , Xn) > b
– an equal to constraint : f(X1 , X2 , X3 , … , Xn) = b

 Objective
– MAX(or MIN) : f(X1 , X2 , X3, …, Xn)
 Mathematical formulation of an
optimization problem

MAX(or MIN) : f(X1 , X2 , X3 , … , Xn)

Subject to:
f(X1 , X2 , X3 , … , Xn) < bm

f(X1 , X2 , X3 , … , Xn) > bm

f(X1 , X2 , X3 , … , Xn) = bm

note : n variables , m constraints

 Requirements For Application Of Linear Programming

1.The aim or object should be clearly identifiable in mathematical

terms.

2. The activities involved should be represented in quantitative terms.

3. Limited availability/ constraints should be clearly spelt out.

4.The relationships between the objective function and the resource
limitation consideration must be linear in nature.

5.Feasible alternative courses of action should be available to the

decision makers that are determined by the resources constraints.
ASSUMPTIONS UNDERLYING
LINEAR PROGRAMMING
1. Proportionality

2. Additivity

3. Continuity

4. Certainty

5. Finite choices

6. Non-negativity
1. LP helps a decision maker to ensure effective use of scarce
resources

2. LP techniques improve the quality of decision making.

3. It generates large number of alternate solutions

4. This technique can also cater for changing situations. The
changed conditions can be used to readjust the plan decided for
execution and so on.
 Model formulation
 A linear programming model consists of certain common
components and characteristics.

 Components of LPM:

 decision variables,

 an objective function, and which consists d/t DV and parameters

 model constraints,
Decision variables are mathematical symbols that represent levels of
activity by the firm.
 Contd

 The objective function is a linear relationship that reflects

the objective of an operation.

 The objective function always consists of either

maximizing or minimizing some value (e.g., maximize
the profit or minimize the cost of producing items).

 A constraint is a linear relationship that represents a

restriction on decision making.

 Parameters are numerical values that are included in the

objective functions and constraints.
 STEPS IN
FORMULATION OF LP
PROBLEMS
There are three basic steps in formulation of LPM
Step 1 : define the decision variables

how many x1, x2, x3……xn to produce

Step 2 : define the objective function

maximize profit or minimize a cost

Step 3 : define the constraints

resources available to produce something

 A maximization model example
X Company is a small crafts operation run by an American natives. The
company employs skilled artisans to produce clay bowls and mugs with
authentic Native America designs and colors. The two primary resources used
by the company are special pottery clay and skilled labor. Given these limited
resources, the company desires to know how many bowls and mugs to produce
each day in order to maximize profit.

The two products have the following resource requirements for production and
profit per item produced (i.e., the model parameters):
Resource Requirements
Required:
formulate
product Labor (hr/unit) Clay (lb/unit) Profit/unit linear model
Bowl 1 4 40
Mug 2 3 50
There are 40 hours of labor and 120 pounds of clay available each day for
production.
 Summary of LP Model Formulation Steps
Step 1. Define the decision variables

How many bowls and mugs to produce

Step 2. Define the objective function

Maximize profit

Step 3. Define the constraints

The resources (clay and labor) available

 Solution
o Decision Variables
how many bowls and mugs to produce

X1: numbers of bowls to produce

X2: numbers of mugs to produce

o The Objective Function

maximize total profit

maximize Z = $40x1 + 50x2
Where,
Z= total profit per day
$40X1= profit from bowls
$50X2= profit from mugs
 Contd
 Class work
 DeReal wood co., produces wooden soldiers and trains. Each soldier sells
for $27, uses $10 of raw materials and takes $14 of labor& overhead costs.
Each train sells for $21, uses $9 of raw materials, and takes $10 of
overhead costs. Each soldier needs 2 hours finishing and 1 hour carpentry;
each train needs 1 hour finishing and 1 hour carpentry. Raw materials are
unlimited, but only 100 hours of finishing and 80 hours of carpentry are
available each week. Demand for trains is unlimited; but at most 40 soldiers
can be sold each week. How many of each toy should be made each week
to maximize profits.
 Answer
 Decision variables completely describe the decisions to be
made (in this case, by DeReal). DeReal must decide how
many soldiers and trains should be manufactured each week.
With this in mind, we define:

 x1= the number of soldiers produced per week,

 x2= the number of trains produced per week,

 Contd
 Objective function: maximizing the total weekly profit (z).
Here, profit equals to (weekly revenues) – (raw material purchase
cost) – (other variable costs).

 Weekly profit from soldiers toys: 27-(10+14)= 3

 Weekly profit from Train: 21-(9+10)= 2

Hence DeReal’s objective function is:

Max z = 3x1+ 2x2

 Cont
 Constraints: Here there are three constraints:

 Finishing time per week

 Carpentry time per week

 Weekly demand for soldiers

non-negative values: (DeReal can not manufacture negative

number of soldiers or trains!)
 Contd
 The complete Linear Programming (LP) problem

Max z = 3x1+ 2x2 (The Objective function)

st: 2x1+ x2 ≤100 (Finishing constraint)

x1+ x2 ≤80 (Carpentry constraint)

x1 ≤40 (Constraint on demand for soldiers)

x1, x2 >0 (Sign restrictions)

 A minimization model example
 A farmer is preparing to plant a crop in the spring and needs to
fertilize a field. There are two brands of fertilizer to choose from,
Super-gro and Crop-quick. Each brand yields a specific amount of
nitrogen and phosphate per bag, as follows:
Chemical contribution
Brand Nitrogen (lb/bag) Phosphate (lb/bag)
super-gro 2 4
Crop-quick 4 3

The farmer's field requires at least 16 pounds of nitrogen and 24 pounds of

phosphate. Super-gro costs $6 per bag, and Crop-quick costs $3. The farmer
wants to know how many bags of each brand to purchase in order to minimize
the total cost of fertilizing.
Summary of LP Model Formulation Steps

Step 1. Define the decision variables

How many bags of Super-gro and Crop-quick to buy

Step 2. Define the objective function

Minimize cost

Step 3. Define the constraints

The field requirements for nitrogen and phosphate

 Contd
 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

 Contd

 Class work
 DeReal makes luxury cars and jeeps for high-income men and
women. It wishes to advertise with 1 minute spots in comedy
shows and football games. Each comedy spot costs 50birr and is
seen by 7M high-income women and 2M high-income men.
Each football spot costs 100birr and is seen by 2M high-income
women and 12M high-income men. How can DeReal reach
28M high-income women and 24M high-income men at the
least cost.
 Answer:
 The decision variables are
x1 = the number of comedy spots

x2 = the number of football spots.

 Giving the problem

 min z = 50x1 + 100x2

St: 7x1 + 2x2 ≥ 28

2x1 + 12x2 ≥ 24

x1, x2 ≥ 0
 Home work
 A company is making two products A and B. The cost of
producing one unit of product A and B is $ 60 and $ 80
respectively. As per the agreement, the company has to supply at
least 200 units of product B to its regular customers. One unit of
product A requires one machine hours whereas product B has
machine hours available abundantly within the company. Total
machine hours available for product A are 400 hours. One unit of
each product A and B requires one labour hour each and total of
500 labour hours are available. The company wants to minimise
the cost of production by satisfying the given requirement.
Formulate the problem as a linear programming problem.
 LP:
Graphical method
Solution of Linear Programming Problems

 The linear programming problems can be

solved to determine optimum strategy by
two methods- Graphical and Simplex
method.
 GRAPHICAL METHOD

 Graphical method is suitable when there are only two

decision variables. Models with three decision variables
can be graphed in three dimensions, but the process is
quite cumbersome, and models of four or more decision
variables cannot be graphed at all.
 STEPS IN GRAPHICAL METHOD

Step I. Formulate the LP Problem as explained in previous class.

Step II. Convert the inequalities in to equalities to obtain

graphical form of the constraints. (Draw the line of each

constraint, first putting x1=0 to find the value of x2 and then
putting x2=0 to find the value of x1.

 Then draw the line for the values of x1 and x2 which represents

the particular constraint. Once the lines are drawn for all the

constraints, identify the

feasible polygon (area) by shading the area below the line for the

constraint < and shading above the line for the constraint > type).
 Contd

Step III. Identify the extreme points of the feasible polygon and
name the Corners.
Step IV. Evaluate the objective function Z or C for all points of
feasible region.

Step V. In case of maximizing objective function Z, the corner

point of feasible region giving the maximum value of Z becomes
the value of decision variables. Similarly in minimizing case, the
point of minimum value of C gives the answer.
 Example 1 (problem of Maximizing Z)

 Two commodities P1 and P2 are to be produced. The profit Margin on P1

is $ 8 and on P2 is $ 6. Both the commodities are required to be

processed through two different machines. Sixty hours of time are

available on I machine and forty eight hours of time are available on II

machine. One unit of P1 requires 4 hours of time in machine I and 2

hours of time on machine II. Similarly, one unit of P2 requires 2 hours of

time on machine I and 4 hours of time on machine II. Determine the

number of units of P1 and P2 to be produced in order to maximize the

profits using graphical method?

 solu
Step I. Formulate LP Problem. tion
The information available can be put into structural matrix form as follow.
Commodities
Requirement Total
P1 P2
Machine I 4 2 60
Machine II 2 4 48
Profit $ per unit 8 6 -

Let x1 be number of units to be produced for P1

DV
Let x2 be number of units to be produced for P2
X1 and X2 are unknown decision variables.
Max Z= 8x1 + 6x2 Objective Function
st: 4x1 + 2x2 < 60
Resource constraints
2x1 + 4x2 < 48
x1, x2 > 0 non-negativity condition.
 nt
Step II. Convert constraint inequalities in to equalities, draw respective lines and
d
determine feasible polygon (area).

 Taking constraint (i)

4x1 + 2x2 = 60 ∴ 4x1= 60 or x1 =15

X1 X2
0 30
∴ 2x2 = 60 or x2 = 30
15 0
By these coordinates (15,30) we get line BD in graph. Similarly, taking constraint (ii).

2x1 + 4x2 = 48
X1 X2
∴ 2x1= 48 or x1 =24
0 12
24 0 ∴ 4x2 = 48 or x2 = 12

 By these coordinates (24,12) we get line AE in graph.

 contd

 Now, any point on line BD satisfies (i) constraint and

any point on line AE satisfies (ii) constraint. The
constraints cannot be violated, they must be satisfied.
Any solution which satisfies all the know constraints is
called optimal solution. Since both the constraints are of
the type < hence any point on the right hand side (RHS)
of BD or AE becomes infeasible area/solution for which
we are not concerned.
 Co
ntd

Feasible
region
 contd
 Step III. Both the constraints are to be satisfied
simultaneously, therefore, OACD becomes the region of
feasible solution. This is also known as feasible polygon.

 On line OA, point A give maximum profit, on line OD, point

D gives maximum profit.
 co
nt
d Z= 8
Step IV. Evaluate the objective function x1 + 6x2 for all points of
feasible region i.e. O,A,C,D.

At point O profit is zero ∴ Z=O

At point A x2=12, x1=0 ∴ Z=12x6=72
At point D x1=15, x2=0 ∴ Z=15x8=120
At point C x1=12, x2=6 ∴Z=12x8+6x6=132

(from graph)
Step V. Z is maximizing objective function, hence the point with maximum
value of Z is the optimal solution point.

Therefore at point C (Z=132) with x1=12 and x2=6 is the optimal point.
 A maximization model (class work)
X Company is a small crafts operation run by an American natives. The
company employs skilled artisans to produce clay bowls and mugs with
authentic Native America designs and colors. The two primary resources used
by the company are special pottery clay and skilled labor. Given these limited
resources, the company desires to know how many bowls and mugs to produce
each day in order to maximize profit.

The two products have the following resource requirements for production and
profit per item produced (i.e., the model parameters):
Required:
Resource Requirements
formulate linear
model, solve
product Labor (hr/unit) Clay (lb/unit) Profit/unit graphically, find
Bowl 1 4 40 the optimum
point
Mug 2 3 50
There are 40 hours of labor and 120 pounds of clay available each day for
production.
 answer

 Contd X2
The labor constraint area

60

50
 Letting X1 and solving for X2
40
Let’s first consider labor constraint line first
30
1(0)+2X1=40
20
X2= 20 10
1X1+2(0)=40 X1
0 40 50 60
10 20 30
X1=40 (40,20) X2
The constraint area for clay
Then, let’s consider clay constraint 60

4(0)+3X2=120 50

40
X2=40
30
4X1+3(0)= 120
20
X1=30 10

(30, 40) 0
X1
10 20 30 40 50 60
 Contd
The feasible solution area is an area on the graph that is
bounded by the constraint equations.
X2

60

50

40
Common area to both constraints
30

20

10
X1
0 10 20 30 40 50 60
 The Optimal Solution Point

 After plotting the graph, the next step in graphical solution

method is locate the point in the feasible solution are that will
result in the greatest total profit.
 Contd
Let’s assign letters
to each corner
X2 0ABC are the feasible region
60

50

40

30
4X1+3X2=120
A
20

10
B 1X1+2X2=40

C X1
0 10 20 30 40 50 60
Calculate the value of each
corner (O, A, B and C) to get
the optimal solution
 Max Z= $40X1+$50X2

 At point 0, Profit is 0 (substitute both X1 and X2 by 0 in the OF)

 At point A, profit is 1000 (substitute X1 by 0 and X2 by 20)

 At point B, profit is 1360 (substitute X1 by 24 and X2 by 8)

 At point C, profit is 1200 (substitute X1 by 30 and X2 by 0)

 Thus the optimal solution is point be (the firm should produce 24
bowls and 8 mugs so as to meet its objective).
 Contd
Let’s assign letters
to each corner
X2 0ABC are the feasible region
60

50

40

30
4X1+3X2=120 Optimum solution
A
20 The optimal solution is
the best feasible solution.
10
B 1X1+2X2=40

C X1
0 10 20 30 40 50 60