CHAPTER TWO

INTRODUCTION TO LINEAR
PRGRAMMING
( Graphical Method)

Yabsiel Gashaw
 Introduction to Linear Programming
• In 1947, George Danztig developed the use of algebra for
determining solutions to problems that involved the
optimal allocation of scarce resources.
• The term “linear” implies that all the mathematical
relations used in the problem are linear, while
“programming” means “choosing a course of action.”
• Linear programming involves choosing a course of
action when the mathematical model of the problem
contains only linear functions( equation having degree of 1).
• LP is a family mathematical techniques for determining
the optimum allocation of resources and obtaining a
particular objective when there are alternative uses of
the limited or constrained resource
Yabsiel
 Components of LP Models
• There are four major components of LP models:
1. Objective and Objective Function
– The objective is the criterion by which all decisions
are evaluated.
– A single, quantifiable objective must be specified by
the decision maker, as it gives focus for problem
solving.
– The mathematical statement of the objective is called
the objective function.
– The objective of an LP will be either maximization or
minimization.
Yabsiel
2. Decision variables
– Are unknown quantities to be solved for.
– For example: how much of each product
should be produced in order to obtain the highest
profit?
3. Constraints
– These are the restrictions on the values of the decision
variables.
– Restrictions can arise due to limited resources such as
space, money, manpower, material, etc.
– The constraints may be in the form of
equations or inequalities (≤, ≥ or ₌).
Yabsiel
 – Constraints can be arranged into three groups:
1. System constraints: involve more than one decision
variable,
2. Individual constraints: involve only one variable, and
3. Non-negativity constraints: specify that no variable is
allowed to take on a negative value.
4. Parameters
– These are constants in the functional relationships.
– They are fixed values that specify the impact that one unit
of each decision variable will have on the objective and on
any constraint it pertains to as well as the numerical value
of each constraint.

Yabsiel
 Mathematical structure of an LP
Let: X1, X2, X3, ………, Xn = decision variables
Z = Objective function or linear function
Objective: Maximization of the linear function Z.
Z = c1X1 + c2X2 + c3X3 + ………+ cnXn …..Eq
(1)
Subject to: the following constraints:

…..Eq (2)

where aij, bi, and cj are given constants.

Yabsiel
Guidelines for Model Formulation

1. Understand the problem thoroughly.

2. Describe the objective.
3. Describe each constraint.
4. Define the decision variables.
5. Write the objective in terms of the
decision (Objective function).
variables
6. Write the constraints in terms of the
decision variables (Functional relationship on
constraints).

Yabsiel
Mathematical structure: Illustration
Zion furniture uses wood and labour to
produce tables and chairs. Unit profit for
tables is $6, and unit profit for chairs is $8.
There are 300 board feet (bf) of wood
available, and 110 hours of labour available. It
takes 30 bf of wood and 5 hours of labour to
make a table, and 20 bf of wood and 10 hours
of labour to make a chair. Formulate the LP
model that can help the company to
maximize its profit.
Yabsiel
Solution:
Let:
o x1 = number of chairs manufactured
o x2 = number of tables manufactured
• The problem can be summarized in the
following table

Yabsiel
• The LP model for the Zion’s example can be
complete as follows.
expressed

Yabsiel
 Example 1: Giapetto’s Woodcarving
Giapetto’s 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
labour and overhead costs by $14. A train sells for $21 and uses $9 worth of
raw materials. Each train built increases Giapetto’s variable labour and
overhead costs by $10. The manufacture of wooden soldiers and trains
requires two types of skilled labour: finishing and carpentry. A soldier
requires 2 hours of finishing labour and 1 hour of carpentry labour. A train
requires 1 hour of finishing and 1 hour of carpentry labour. 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 mathematical model of Giapetto’s situation that can be used
to maximize Giapetto’s weekly profit.

Yabsiel
 Solution
• In developing the Giapetto model, we explore
characteristics shared by all linear programming
problems.
 Decision Variables:
o x1 = number of soldiers produced each week
o x2 = number of trains produced each week
 Objective Function
o We note that, for the Giapetto problem, fixed
costs do not depend upon the values of x1 or x2.

Yabsiel
• So, Giapetto can concentrate on maximizing its weekly profit.

Weekly Profit = (weekly revenues) - (raw material

purchase costs) - (other variable costs)
• Giapetto’s weekly profit can be expressed in terms of
the decision variables x1 and x2:
Weekly revenue = 27x1 + 21x2
Weekly raw material costs = 10x1 + 9x2
Weekly labor costs = 14x1 + 10x2

• Weekly profit = (27x1 + 21x2) – (10x1 + 9x2) – (14x1 + 10x2 )

= 3x1 + 2x2
Yabsiel
• Therefore, Giapetto’s objective function is expressed
as:
Maximize z = 3x1 + 2x2
• The coefficient of an objective function variable
is called an objective function coefficient.
 Constraints
• The values of x1 and x2, for Giapetto, are limited by the
following three restrictions /constraints:

Yabsiel
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.
These three constraints can be expressed mathematically
by the following equations:
Constraint 1: 2 x1 + x2 ≤ 100
Constraint 2: x1 + x2 ≤ 80

Constraint 3: x1 ≤ 40

Yabsiel
• To complete the formulation of a linear programming
problem we need to decide whether NNC (sign
restriction) has to be assumed or not.
– If the decision variable can assume only
nonnegative values, the sign restriction xi ≥ 0 is
added.
– If the variable can assume both positive and
negative values, the decision variable xi is
unrestricted in sign (often abbreviated urs).

Yabsiel
• The optimization model For the Giapetto
problem is summarized and stated as
follows.

Max z = 3x1 + 2x2 (objective

function) Subject to (s.t.):

2 x1 + x2 ≤ 100 (finishing constraint)

x1 x1 + ≤
x2 40
≤ (constraint on dd
80 (carpentry for soldiers)
constraint)
x1 ≥0 (sign restriction)

x2 ≥0 (sign restriction)

Yabsiel
 Assumptions Of LP Models
1. Linearity (proportionality)
– The linearity requirement is that each variable has a
linear impact on the objective function and in each
constraint in which it appears.
– On the other hand, the amount of each resource
used (supplied) and its contribution to the profit (or
cost) must be proportional to the value of each
decision variable.
– For example, the contribution to the objective
function for 4 soldiers is exactly fours times the
contribution of 1 soldier.
Yabsiel
2. Divisibility (Continuity)
• It is assumed that non-integer values are acceptable.
• However, if the problem requires strictly integer
solutions, integer-programming methods should be
used.
• For example, this assumption implies it is acceptable
to produce a fractional number of trains.
• The Giapetto LP does not satisfy the divisibility
assumption since a fractional soldier or train cannot
be produced.

Yabsiel
3. Certainty
• Its holds that each parameter (objective function
coefficients, RHS, and technological coefficients)
are known with certainty.
4. Non-negativity
• It assumes that negative values of variables are
unrealistic and, therefore, will not be considered in
any potential solutions.
• Only positive values and zero will be allowed and
the non-negativity assumption is inherent in LP
models.
Yabsiel
 Solving LP Model
• The most common approaches to solve are to solve
Linear Programming Models are:
1. The Graphic Approach: a relatively straightforward
approach for determining the optimal solution to
LPPs involving only two decision variables.
2. The Algebraic Approach: The simplex method, or
iterative or step by step method, which is an
efficient method for solving LPPs involving two or
more decision variables.

Yabsiel
Feasible Region and Optimal Solution
• The feasible region of an LP is the set of all points
satisfying all the LP’s constraints and sign restrictions.
• An optimal solution is a feasible solution that results in
the largest possible objective function value when
maximizing (or smallest when minimizing).
• Most LPs have only one optimal solution.
• However, some LPs have no optimal solution, and
some LPs have an infinite number of solutions.

Yabsiel
I. Graphical Solution to LP Problems

• Any LP with only two can be solved

variables graphically.
• We always label the variables and x2 and
x1 coordinate axes the x1 and x2 the
• axes.
Since the Giapetto LP has two variables, it may
be solved graphically.
• The feasible region is the set of all points satisfying
the constraints:

Yabsiel
 Example [Maximization]: Giapetto
• Giapetto’s Problem Constraints

2 x1 + x2 ≤ 100 (finishing constraint)

x1 + x2 ≤ 80 (carpentry constraint)
x1 ≤ 40 (demand constraint)
x1, x2 ≥ 0 (non-negativity constraint)

A graph of the constraints and feasible region is shown on

the next slide.

Yabsiel
• Feasible Solution for Giapetto’s Problem

Yabsiel
• From figure, we see that the set of points satisfying
the Giapetto LP is bounded by the five sided polygon
IBCEF.
• Any point on or in the interior of this polygon (the
shade area) is in the feasible region.
• Set of Points which make up the feasible
solution are: I (0,0), B (0, 80), C (20, 60), E (40, 20), F
(40, 0).

Yabsiel
 Finding the Optimal Solution
• We use an Extreme Point Approach to find the optimal
solution of the problem.
• Corner points which make up the feasible region will be
taken in to consideration, and the one that can maximize
the Z-value will be the optimal Solution.
Corner Points Coordinates O.F (Zmax=3x1+2x2)
I (0,0) 0
B (0,80) 160
C (20,60) 180
E (40,20) 160
F (40,0) 120

Yabsiel
• We can see in the previous table that the combination of
values for each variable which yield the maximum profit
is the one indicated by point C.
• Therefore, the optimal solution to the Giapetto problem
is:
X1=20
X2=60, and
Maximum profit= $180
 Interpretation
• For Giapetto to maximize its weekly profit
($180), it should produce 20 soldiers and 60 trains.

Yabsiel
A Maximization Problem

Example:
Consider two models of color TV sets; Model A and B, are
produced by a company to maximize profit. The profit realized
is $300 from A and $250 from set B. The limitations are
a. availability of only 40hrs of labor each day in
the production department.
b. a daily availability of only 45 hrs on machine time
c. ability to sale 12 set of model A.
How many sets of each model will be produced each day so
that the total profit will be as large as possible?

29
Yabsiel
A Maximization Problem

Constraints Model A Model B Maximum Available hrs.

(X1) (X2)
Labor hr. 2 1 40
Machine hr. 1 3 45
Marketing hr. 1 0 12
Profit $300 $250

30
Yabsiel
 A Maximization Problem

Solution
1. Formulation of mathematical modeling of LPP
Max Z = 300X1 +250X2
St:
2X1 +X2 < 40
LPP Model
X1 +3X2 <
X1 < 12
45
X1, X2 > 0
2. Convert constraints inequalities into equalities
2X1 +X2 = 40
X1 +3X2 = 45
X1 = 12
31
Yabsiel
A Maximization Problem

Solution

3. Draw the graph by intercepts

2X1 +X2 = 40 ==> (0, 40) and (20, 0)

X1 +3X2 = 45 ==> (0, 15) and (45, 0)
X1 = 12 ==> (12, 0) X1,
X2= 0

32
Yabsiel
A Maximization Problem

Solution
2X1
X2 +X 2
X1 =0 = 40

40 X1=12

X1
+X 2
B = 45
15

Feasible C (12, 11)

Region
X2 =0
X1
D
A 12 20 45

33
Yabsiel
 A Maximization Problem
Solution
4. Identify the feasible area of the solution which satisfies
all constrains.
5.Identify the corner points in the feasible region
A (0, 0), B (0, 15), C (12, 11) and D (12, 0)
6. Identify the optimal point
7. Interpret the result
Corners Coordinates MaxZ=300 X1 +250X2
A (0, 0) $0
B (0, 15) $3750
C (12, 11) $6350
D (12, 0) $3600
Interpretation:
12 units of product A and 11 units of product B should
be produced so that the total profit will be $6350. 47
Yabsiel
 Minimization Problem
Minimize Z with inequalities of constraints in > form
Example:
Suppose that a machine shop has two different types of machines;
machine 1 and machine 2, which can be used to make a single
product .These machine vary in the amount of product produced per hr., in
the amount of labor used and in the cost of operation.
Assume that at least a certain amount of product must be produced and
that we would like to utilize at least the regular labor force. How much
should we utilize each machine in order to utilize total costs and still
meets the requirement? The data are given below.

Resource used
Machine 1 (X1) Machine (X2) Mini. requirement hrs

Product produced/hr 20 15 100

Labor/hr 2 3 15
Operation Cost $25 $30_
35
Yabsiel
Minimization Problem
1. Formulate the LP

Min.Z  25X 130X 2

St :
LPP Model
20X 115X 2 100
2 X 13X 2 15
X 1, X 2  0

2. Constraint equation:
20X1 +15X2=100 ==> (0, 20/3) and (5,
0)
2X1+3X2=15 ==> (0, 5) and (7.5, 0)
X1 X2> 0
36
Yabsiel
3. Graphical solutions
XX 2
X1 =0

AA ((00,, 22 00// 33))

FFeeaassiibbllee

RReeggiioonn

B (2.5, 3.33)
X2 =0

X1

5
CC

((77..55,,
00))

37
Yabsiel
Final solutions

Corners Coordinates MinZ=25 X1 + 30X2

A (0, 20/3) 200

B (2.5, 3.33) 162.5

C (7.5, 0) 187.5

X1 =2.5
X2 =3.33 and
MinZ = 162.5

38
Yabsiel
Self Practice Maximization: Solve the given linear programming
problems graphically:

Maximize: Z = 8x1 + x2
and the constraints are Points
: Z = 8x1 + x2

(0, 0) 0
x1 + X2 ≤ 40,
(0, 40) 40

2x1 + X2 ≤ 60, (20, 20) 180

(30, 0) 240
x1 ≥ 0, X2 ≥ 0

39
Yabsiel
Self practice Minimization: Solve the following LPP by
graphical method
Minimize z = 5x1+4x2 
Subject to constraints
4x1+ x2 ≥ 40 ;
2x1+3x2 ≥ 90
 x1, x2 > 0

The minimum value of Z occurs at

B(3,28).

Hence the optimal solution is x1 =

3, x2 = 28 and Zmin=127

40
Yabsiel
 the Special Cases of LP
1. Unboundedness: occurs when the decision variable
increases indefinitely without violating any of the
constraints.
– Reason: wrong formulation of the problem such as
incorrectly maximizing instead of minimizing and/or
errors in the given problem.
• Example:

Yabsiel
2. Redundant Constraints: A constraint is redundant if
its removal would not alter the feasible solution
space.
If a constraint when plotted on a graph doesn’t form part
of the boundary making the feasible region of the
problem that constraint is said to be redundant.

Yabsiel
 3. Alternative or multiple optimal solutions
Example:
Corner Points Coordinates O.F (Zmax=3x1+2x2)
A (40,0) 120
E (20,30) 120
D (0,50) 100
F (0,0) 0
• Points A through E along with point A and E can be alternate
optimal solutions.
4. Infeasibility: a condition that arises when no value of
the variables satisfy all the constraints simultaneously.
Max Z=20X1+30X2
St:
2X1+X2< 40
4X1+X2< 60
X1 > 30
X1, X2 > 0
Yabsiel
Yabsiel
Linear programming through
Simplex method ………

40
Yabsiel