Industrial Engineering (IE)

Linear Programming Model

Name :Kawther Ibrahim Khalil

University of Babylon
College of Engineering
Department :Mechanical Engineering
Class: Third Stage /Division B
Linear Programming
LP is a mathematical modeling technique designed to
optimize the usage of limited resources, such as available
materials, labour and machine time.
The LP model includes three basic elements :
- Decision variables that we seek to determine.
- Objective (goal) that we aim to optimize.
- Constraints that we need to satisfy.

Steps in formulating LP problems:

1- Define the objective.
2- Define the decision variables.
3- Write the mathematical function for the objective
(objective function).
4- Write a one- or two- word description of each
constraint.
5- Write the right – hand side (RHS) of each
constraint, including the unit of measure.
6- Write ≤, = or ≥ for each constraint.
7- Write all the decision variables on the left-hand side
of each constraint.
8- Write the coefficient for each decision variable in
each constraint.

Formulation of linear programming model (LP)

The general form of each model will be:
Z= c1x1+ c2x2+……. ckxk
Subject to:
a11x1+ a12x2+…….a1kxk b1

a21x1+ a22x2+……. a2kxk b2

↓ ↓ ↓
am1x1+ am2x2+……. amkxk b1

where:
Cj is a known (cost or profit) coefficient Xj.
Xj is an unknown variable.
aij is a known constant.
bj is a known constant.

≤ , = or ≥ for each constraint.

Example: A manager wants to know many units of each

product to produce on a daily basis in order to achieve
the highest contribution to profit. Production requirement
for the products are shown in the following table:
Production Departments

ɪ ɪɪ
 Processing time 4 2
required for the first
product (Hours)

Processing time 2 4
required for the second
product (Hours)

Production capacity 60 48
available (Hours)

The profit is £8 for each unit of the first product and £6

for each unit of the second product.

Solution:

1- Define the objective. The problem is a maximum

problem.
2- Define the decision variables. We need to determine
the number of units to be produced.
Let: Xi be the number of units of type i (i= 1,2)

Therefore :
X1= number of units of the first product.
X2= number of units of the second product.

X1, X2 are the decision variables, when we know their

values the problem will be solved.
3- The objective function for the LP is:
Maximize Z = 8X1+6X2
This means the profit Z depend on how many units (X1,
X2) are manufactured. Z= c1x1+ c2x2 where c1, c2 are the
respective profits for each type of product. c1=£8 c2=£6
and Z = 8X1+6X2 and we should select values of the
decision variables X1, X2 that result in the maximum
value of Z.

4- There are two constraints :

Maximum production capacity for Dep.I ≤ 60 hours
Maximum production capacity for [Link] ≤ 48 hours
( Note: because all the constraints in this problem are
maximum capacity , all constraints are the ≤ type)
Now we have to write the coefficient for each decision
variable in each constraint.
The two constraints can be expressed as:
4X1+2X2 ≤ 60 constraint Dep.I
2X1+4X2 ≤ 48 constraint [Link]

Consider the first constraint ( Dep.I) what is the

coefficient of X1 in this constraint? It is the processing
time (Hours) required per unit of X1. In other word, it is
the processing time used in manufacturing each unit, first
product, or 2 hours. Similarly, the coefficient of X2 in
this first constraint is 1 hour.
Therefore the two constraints can be expressed as :
4X1+2X2 ≤ 60
2X1+4X2 ≤ 48
And the no. negatively restriction is all Xj≥ 0 , X1, X2 ≥ 0.

Graphical LP solution:
Steps in the graphical method
1- Formulate the objective and constraint functions.
2- Draw a graph with one variable on the horizontal
axis and one on the vertical axis.
3- Plot each of the constraints as if they were lines or
equities.
4- Outline the feasible solution space.
5- Circle the potential solution points .These are the
intersections of the constraints or axes on the inner
(minimization) or outer (maximization) perimeter of
the feasible solution space.
6- Substitute each of the potential solution point values
of the two decision variables into the objective
function and solve for Z.
7- Select the solution point that optimizes Z.
Solution of maximization model
To demonstrate the steps of the graphical solution of a
maximization problem we use the previous example:
Z = 8X1+6X2
Subject to:
4X1+2X2 ≤ 60
2X1+4X2 ≤ 48
X1 ≥ 0 , X2 ≥ 0

Solution:
1- Plot the constraints (shown in the following figure)
change constraints to equalities:

4X1+2X2 ≤ 60 → 4X1+2X2 = 60

2X1+4X2 ≤ 48 → 2X1+4X2 = 48
For each constraint ( set X1=0 and solve for X2 , then
set X2=0 and solve for X1)
the graph the constraint as if it were an equality

4X1+2X2 = 60 →X1=15 X2=0

X1=0 X2=30

2X1+4X2 = 48→ X1=24 X2=0

X1=0 X2=12

2- Outline the feasible solution space the values of X1

and X2 at points M,A,B and C are four potential
solutions to problem.
Note: point B can be determined as follow:
4X1+2X2 = 60
(2X) 2X1+4X2 = 48
____________________
4X2+2X2 = 60
4X2+8X2 = 96
___________________
6X2=36
X2= 36/6 = 6
Then: 4X1+2X2 = 60
4X1+2(6) = 60
4X1 = 48
X1= 48/4 = 12

point X1 X2 Z
M 0 0 Z=8(0)+6(0)=0
A 15 0 Z=8(15)+6(0)=120
B 12 6 Z=8(12)+6(6)=132
C 0 12 Z=8(0)+6(12)=72

To maximize Z, the optimal solution is point B, where

X1=12 and X2=6 and Z=£132 profit.
Minimization case:
Consider the following LP problem:
Min Z = 3X1+8X2
Subject to:
X1≤ 80
X2≥ 60
X1+ X2=200
X1, X2 ≥ 0
Solved problem: X1=80 X2=60
X1=0 X2=200
X1=200 X1=0
B/ X1+ X2=200
X1=80
Then X2=200-80
=120
Point X1 X2 Z
A 0 200 3(0)+8(200)=1600
B 80 120 3(80)+8(120)=1200

Min Z=1200
X1=80 X2=120
Special cases in LP
Five special cases and difficulties arise at times when
using the graphical approach to solve LP problems:
1) Infeasibility: infeasibility is a condition that arises
when there is no solution to LP problem that
satisfies all of constraints given.
Graphically, it means that no feasible solution region
exists- a situation that might occur if the problem was
formulated with conflicting constraints.
Let us consider the following three constraints:
X1+2X2 ≥6
2X1+X2 ≥8
X1 ≥7
As seen in the figure there is no feasible solution region
for this problem because of the presence of conflicting
constraints.

2) Unboundedness:
Sometimes a linear program will not have a finite
solution. This means that in a maximization problem, for
example, one or more solution variables, and the profit,
can be made infinitely large without violating any
constraints. If we try to solve such a problem graphically,
we will note that the feasible region is open-ended.
Let us consider a simple example to illustrate the
situation.
Z = 3X1+5X2
Subject to: X1≥ 5
X2≤ 10
X1+2 X2≥10
X1, X2 ≥ 0

As you see, because this is a maximization problem and

the feasible region extends infinitely the right, there is
unboundedness or unbounded solution.
3)Redundancy: The presence of redundant constraints
occurs in large LP formulations, a redundant
constraint is simply on that does not affect the
feasible solution region.
Let us kook at the following example:
Max Z= X1+2X2
Subject to: X1+X2≤ 20
2X1+X2≤ 30
X1≤ 25
X1, X2 ≥ 0
The third constraint, X1≤25 is redundant and
unnecessary in the formulation and solution of the
problem because it has no effect on the feasible region
set.
4) Alternate Optimal Solutions: An LP problem may
on occasion, have two or more alternate optimal
solutions. Graphically, this is the case when the objective
function’s is profit or is cost line runs perfectly parallel
to one of the problem’s constraints.
Ex: Max Z= 3X1+2X2
Subject to: 6X1+4X2≤ 24
X1≤ 3
X1, X2 ≥ 0
 As you see any point along the line between A and B
provides an optimal X1 and X2 combination Z=12
5) Degeneracy: Degeneracy is a condition that arises
when one of the decision variable equal zero. Look
to the following example:
Max Z = 3X1+9X2
Subject to: X1+4X2≤ 8
X1+2X2≤ 4
X1, X2 ≥ 0
Solution: X1=8 X2=2
X1=4 X2=2
Then: at point A
X1=0 X2=2 Max Z=18
Problems:
Q1/ Montana wood products manufacturers two high-quality
products, chairs and bookshelf units. Its profit is $15 per
chair and $21 per bookshelf unit. Next week’s production
will be constrained by two limited resources, labor and
wood. The labor available next week is expected to be 920
labor hours, and the amount of wood available is expected
to be 2400 board feet. Each chair requires 4 labor hours
and 8 board feet of wood. Each bookshelf unit requires 3
labor hours and 12 board feet of wood. Management
would like to produce at least 100 units of each product.

a- To maximize total profit, how many chairs and

bookshelf units should be produced next week?
b- How much profit will result?
Solution: Let X1: number of chairs to produce next
week.
X2: number of bookshelves to produce next week.
Max Z = 15X1+21X2
Subject to: 4X1+3X2≤920 …….. (1)
8X1+12X2≤ 2400 …….. (2)
X1≥100 X2≥100
X1, X2 ≥ 0
X1=0 X2=306.6
X2=0 X1=230 …………….. (1)
X1=0 X2=200
X2=0 X1=300 …………… (2)
Z= 4350 with X1=150 X2=100

Point X1 X2 Z
A 100 100 3600
B 100 133.3 4299.3
C 150 100 4350
Q2: solve graphically the following linear programming
problem:
Max Z = 60X1+40X2
Subject to: 2X1+X2≤ 60
X1≤ 25, X2≤ 35
X1, X2 ≥ 0

Solution:
Max Z = 60X1+40X2
Subject to: 2X1+X2≤60
X1≤25 X2≤35
X1, X2 ≥ 0
X1=0 X2=306.6
X2=0 X1=30

point X1 X2 Z
M 0 0 0
A 0 35 1400
B 12.5 35 2150
C 25 10 1900
D 25 0 1500

B: 2X1+X2= 60 X2=35 X1= (60-35)/2 = 12.5

It is clear that Z equal to 2150 is Maximum at B when
X1=12.5 X2=35.
Q3: solve graphically:
Max Z = 10X1+15X2
Subject to: 2X1+X2≤ 26
2X1+4X2≤ 56
X1-X2≥-5
X1, X2 ≥ 0
Solution: Max Z = 10X1+15X2
Subject to: 2X1+X2≤26
2X1+4X2≤ 56

X1-X2 ≥-5→ -X1+X2 ≤5

X1, X2 ≥ 0
X1=-5 X2=5
 Point X1 X2 Z
M 0 0 0
A 0 5 75
B 6 11 225
C 8 10 230
D 13 0 130

Hence, Z is Maximum (230) at C.

`

Q4: Consider the following problem and solve

graphically:
Minimize Z = 2X1+4X2
Subject to: X1+X2≤ 14
3X1+2X2≥ 30
2X1+X2≤18
X1, X2 ≥ 0
Solution: Min Z = 2X1+4X2
Subject to: X1+X2≤14
3X1+2X2≥30
2X1+X2≤18
X1, X2 ≥ 0
Point X1 X2 Z
A 2 12 52
B 4 10 48
C 6 6 36

Thus, Z is Minimum at point C when X1 , X2=6 Z=36 .

Q5: solve the following problem using graphical linear
programming.
Minimize Z = 2X1+3X2
Subject to: 4X1+2X2≥ 20
2X1+6X2≥ 18
X1+2X2≤12
X1, X2 ≥ 0
Solution:

The optimum solution X1=4.2 and X2=1.6

Minimum Z=2(4.2)+3(1.6) = 13.2