Linear Programming

Dr. Ahmed Al-Arashi

 Linear Programming

 Introduction
 Construction of linear programming
model
 Basic assumption.
 Graphic method.
 Simplex method.
 Introduction
Linear programming is deterministic
mathematic technique used to solve
resource allocation problems specially in
production and planning.
It provides an efficient method for determining
an optimal solution (max. or min.) which
meets various restrictions and constraints.
It used on various levels (projects, sector or
national) in resource allocation problems
(machinery, labor, money, time … etc.)
 Introduction
Linear means that all the mathematical
functions in this model are required to be
linear.
Programming does not refer to computer
programming; rather, it is refers to activities
planning where steps leading to achieve
predefined specified goals.
 Linear programming model
Linear programming model consists of the
following:
1- Objective function:
 It shows the objective to be achieved.
 Mostly it is either to maximize profit or
minimize cost.
 It consists of variables representing the
products, to be produced, with their coefficients
representing unit profit, in maximizing profits
problems, or unit cost, in minimizing production
cost problems.
 Linear programming model
2- Constraints :
It usually specifies the quantities of the available
materials or the technical relation which shows
what does each production unit needs out of the
limited available resources.
3- Non negativity condition:
This means that all variables in the problem under
consideration must not be negative. It must be
either positive or zero.
 Example 1
Transformers factory produces two types of transformers
A and B each one of them passes through two
machines. Machine 1 is for forming the frame and can
be used for up to 70 hours a week. Machine 2 is for
winding and can be used for up to 60 hours a week.
Transformer A takes 4 hours in machine 1 and 10 hours
in machine 2, and transformer B takes 5 hours in
machine 1 and 6 hours in machine 2.
Write a liner programming model which maximize the
profit noting that each transformer of type A gives profit
of $3 and type B $6
 Solution Example 1
Summary of the problem

Per week max. Production needed time Machine

available time

Transformer (B) Trans former (A)

70 Hours 5 Hours 4 Hours M (1)

60 Hours 6 Hours 10 Hours M (2)

6$ 3$ Profit
 Solution Example 1
Object function
We need to produce number of transformers of two types using
two machines in the available time for getting the maximum
possible profit.
Assume that:
X 1 : No. of transformers of type A to be produced.
X2 : No. of transformers of type B to be produced.
Each Trans. A gives profit of $3, if X1 Trans. Produced we get 3
X1 profit. Similarly each Trans. B gives profit of $6, if X2 Trans.
Produced we get 6 X2 profit.
As the total profit is the sum of profits from each type then: Z= 3
X1 + 6 X2
for maximum profit we write Max Z = 3 X1 + 6 X2
 Solution Example 1 (2)
Constrains
First constrain:
Machine 1 can work up to 70 hours and Type A takes 4 hours
and type B takes 5 hours in this machines then:
4 X1 + 5 X2 ≤ 70
Second constrain:
Machine 1 can work up to 60 hours and Type A takes 10 hours
and type B takes 6 hours in this machines then:
10 X1 + 6 X2 ≤ 60

Non Negative:
X1 , X2 ≥ 0
 Solution Example 1 (3)
The linear programming model for this example is:

Max Z = 3 X1 + 6 X2
Subject to
4 X1 + 5 X2 ≤ 70
10 X1 + 6 X2 ≤ 60
X1 , X2 ≥ 0
 Example 2
Write linear programming model for following:

C B A Products

Stages
4 2 3 Stage 1
1 5 1 Stage 2
6 4 5 Stage 3
Available time for stages 1, 2 and 3 are 80, 70 and 90
respectively.
Profits of products A, B and C are $3, 4$ and $2
respectively.
 Solution Example 2
Write linear programming model for following:

Max Z = 3 X1 + 4 X2 + 2 X3
Subject to
3 X1 + 2 X2 + 4 X3 ≤ 80
X1 + 5 X2 + X3 ≤ 70
5 X1 + 4 X2 + 6 X3 ≤ 90
Non negative:
X1 , X2, X3 ≥ 0
 Linear programming problem Solution
Mean methods used to solve linear programming
problems are:
1- Graphic Method
This method uses graphics to find the solution. It is
suitable for problems involving no more than two
decision variables (X1 and X2).
2- Simplex Method
This method is an efficient mathematical mean to obtain
the optimal solution of linear programming problems
disrespect of the number of decision variables. With the
aid of computer, problems with several thousand
variables and constraints can be easily solved.
 Graphic Method
To solve problems using this method do the following:
1- Draw two Axis X1 and X2.
2- Find the intersection of each constraint with the axis by
converting the (≤ ) and ( ≥ ) signs to ( = ) and substitute X1 =0
to find the point of intersection with X2 Axis and substitute X2
=0 to find the point of intersection with X1 Axis.
3- Draw the constraints lines by connecting the intersection with
the Axis X1 and X2 of each constraint which defines the
solution area of each constraint.
4- Define solution area which is the area of intersection of
solution areas.
5- As all variables are non negative the solution is in the first
quarter.
6- Find the value of Z at the head of the ship forming the solution
area.
 Example on Graphic Method
Example (1): Find the optimal solution for the following using
graphic method:
Max Z = 3 X1 + 2 X2
Subject to
X1 + X2 ≤ 5
X2 ≤ 4
X1 + 2 X2 ≤ 8
Non negative:
X1 , X2 ≥ 0
 Example on Graphic Method
Example (1) solution:

Take first constraint (X1 + X2 ≤ 5) and make it ( X1 + X2 = 5 )

Putting X2 = 0 , X1 = 5 and Putting X1 = 0 , X2 = 5

6
5
4
3
2
1
 Example on Graphic Method
Example (1) solution:

Take second constraint (X2 ≤ 4) and make it (X2 = 4 )

X2

6
5
4
3
2
1
X1
 Example on Graphic Method
Example (1) solution:

Take first constraint (X1+2 X2≤ 8) and make it (X1 + 2 X2 = 8)

Putting X2 = 0 , X1 = 8 and Putting X1 = 0 , X2 = 4
X2

6
5
4 D
3 C
2
1
A B X1
 Example on Graphic Method
Example (1) solution:

Now Solution area is bounded by the Points (ABCD).

A= (0,0) , B= (0,5), C (3,2) and D= (4,0)
X2

6
5
4 D
3 C
2
1
A B X1
 Example on Graphic Method
Example (1) solution:
Now solving for Z in the objective function (Z = 3 X1 + 2 X2)

Z X2 X1 Boundary
0 0 0 A
15 0 5 B
12 3 2 C
8 4 0 D

Then the optimal solution that gives the max. profit is when
Z=15 which means that X1= 5 and X2 =0.
 Simplex Method (1)
To solve problems using this method do the following:
1- Convert the linear programming model to the Standard form by:
Constant S1 S2 X1 X2 Basic Variables
(I) converting
20
constraint
1
to equality
0 1
equation
2
and adding
S1
(Slack
Variables). Put negative slack variable for constraint equation with
12 0 1 1 1 S2
(≤ ) and positive for equation with ( ≥ ).
0 0 0 -2 -3 Z
(II) take all variables in the objective function variables to the left
hand side making the equation = (0).
2- Construct the first simplex table (Basic Feasible Solution) by
setting Xi to 0 (X1=0, X2=0, Xn=0) and slack variables will have
values. Z=0 and Sj will have values and will be the Basic
variables. The table will contain rows and columns as follows:
Rows
 1st row, names of variables and solution.
 2nd row , values of variables as in the objective function.
 3rd , 4th ,….. Etc. coefficients of variables in the constraint equation.
 Simplex Method (2)
Columns
 1st columns, names of basic variables which have been set for the
initial solution Z and Sj).
 2nd columns , names of non basic variables in the first row and its
coefficients in the following rows.
 3rd columns, names of slack variables in the first row and its
coefficients in the following rows.
 4th columns, constants of objective function and constraint
equations.
3- Determine the Entering Variable which is the variable with the
largest negative coefficient
Constant S1 inS2
theX1objective function.
X2 Basic Variables
4- Determine20 the Leaving
1 Variable.
0 It1could be determined
2 by dividing
S1
the constant
12 values
0 (in the constant
1 1 column) by 1 the value
S2 of the
coefficient
0
of the Entering
0
Variable
0 -2
in the constant
-3
row. Then
Z
the
Leaving Variable is the one against the smallest positive value
resulted from the division ( ignore infinity and negative).
 Simplex Method (3)
5- Determine the Pivot Element. It is the coefficient where the column
of the Entering Variables intersects with the row of the leaving
Variable.
4- Construct the Pivot Equation by dividing the values in the Leaving
Variable row by the Pivot Element.
5- Find effect on the objective function as follows:
New Z = Old Z – (Entering Element coefficient) (Pivot Equation).
6- Find effect on the constraints as follows:
New Sj = Old Sj – (Entering Element coefficient) (Pivot Equation).
7- Construct the second iteration table by replacing the Leaving
Variable by the Entering Variable and replacing Old Z and Old Sj
by New Z and New Sj.
8- Check the values at the objective function row. If there is no
negative value the optimal solution is reached. If not repeat
processes from 3 until optimal solution is found.
 Example on Simplex Method (1)
Example (2): Find the optimal solution for the following using
simplex method:
Max Z = 2 X1 + 3 X2
Subject to
X1 + 2 X2 ≤ 20
X1 + X2 ≤ 12
X1 , X2 ≥ 0
Solution Ex. (2):
Convert to the standard form:
Z - 2 X1 - 3 X2 = 0
Subject to
X1 + 2 X2 + S1 = 20
X1 + X2 + S2 =12
X1 , X2, S1, S2 ≥ 0
 Example on Simplex Method (2)
Solution Ex. (2):
Convert to the standard form:
Z - 2 X1 - 3 X2 = 0
Subject to
X1 + 2 X2 + S1 = 20
X1 + X2 + S2 =12
X1 , X2, S1, S2 ≥ 0

Constant the first simplex table (Basic Feasible Solution)

First Iteration
Constant S1 S2 X1 X2 Basic Variables
20 1 0 1 2 S1
12 0 1 1 1 S2
0 0 0 -2 -3 Z

Entering Variable is (X2) as it has the largest negative coefficient.

 Example on Simplex Method (3)
To find the Leaving Variable divide Constants by coefficient of the
Entering Variable at its row we get:
Ratio Constant S1 S2 X1 X2 Basic Variables
20/2= 10 20 1 0 1 2 S1
12/1= 12 12 0 1 1 1 S2
0 0 0 -2 -3 Z

The smallest ratio is 10. Then the Leaving Variable is S1.

Pivot Element is (2). From the table below it could be seen that
intersection of X2 and S1 is at (2)
Ratio Constant S1 S2 X1 X2 Basic Variables
20/2= 10 20 1 0 1 2 S1
12/1= 12 12 0 1 1 1 S2
0 0 0 -2 -3 Z
 Example on Simplex Method (4)
Construct the Pivot equation by dividing the values at the Leaving
Variable by Pivot element (2) we get
Constant S1 S2 X1 X2 Basic Variables
10 1/2 0 1/2 1 S1

Find New Z
New Z = Old Z – (Entering Element coefficient) (Pivot Equation).
Entering Element coefficient in Z row is (-3)

(-3) ( 1/2 1 1/2 0 10)

= (-3/2 -3 -3/2 0 -30)
Old Z= ( -2 -3 0 0 0)

New Z =( -1/2 0 3/2 0 30)

 Example on Simplex Method (5)
Find New Sj: We have only S2 to be found from:
New S2 = Old S2 – (Entering Element coefficient) (Pivot Equation).
Entering Element coefficient in S2 row (1)
(1) ( 1/2 1 1/2 0 10)
= ( 1/2 1 1/2 0 10)
Old S2= ( 1 1 0 1 12)
New S2 = ( 1/2 0 -1/2 1 2)
Put all the values in Second Iteration table we get
Constant S1 S2 X1 X2 Basic Variables
10 1/2 0 1/2 1 X2
2 - 1/2 1 1/2 0 S2
30 3/2 0 -1/2 0 Z

As there negative value in Z row optimal solution has not been reached.
Repeat the process. Entering Variable is (X1) as it has the largest
negative coefficient in Z row.
 Example on Simplex Method (6)
To find the Leaving Variable divide Constants by coefficient of the
Entering Variable at its row we get:
Ratio Constant S1 S2 X1 X2 Basic Variables
10/1/2=20 10 1/2 0 1/2 1 X2
2/1/2= 4 2 - 1/2 1 1/2 0 S2
30 3/2 0 -1/2 0 Z

The smallest ratio is 2. Then the Leaving Variable is S2.

Pivot Element is (1/2). From the table below it could be seen that
intersection of X1 and S2 is at (1/2)

Ratio Constant S1 S2 X1 X2 Basic Variables

20 10 1/2 0 1/2 1 X2
4 2 - 1/2 1 1/2 0 S2
30 3/2 0 -1/2 0 Z
 Example on Simplex Method (7)
Construct the Pivot equation by dividing the values at the Leaving
Variable by Pivot element (1/2) we get
Constant S1 S2 X1 X2 Basic Variables
4 -1 2 1 0 S2

Find New Z
New Z = Old Z – (Entering Element coefficient) (Pivot Equation).
Entering Element coefficient in Z row is (-1/2)

(-1/2) ( 1 0 -1 2 4)
= (-1/2 0 1/2 -1 -2)
Old Z= ( -1/2 0 3/2 0 30)

New Z =( 0 0 1 1 32)
 Example on Simplex Method (8)
Find New Xj
We have only X2 to be found from:
New X2 = Old X2 – (Entering Element coefficient) (Pivot Equation).
Entering Element coefficient in X2 row (1/2)
(1/2) ( 1 0 -1 2 4)
= ( 1/2 0 -1/2 1 2)
Old X2= ( 1/2 1 1/2 0 10)
New X2 = ( 0 1 1 -1 8)
Put all the values in third Iteration table we get
Constant S1 S2 X1 X2 Basic Variables
8 1 -1 0 1 X2
4 -1 2 1 0 X1
32 1 1 0 0 Z

Now no negative values in Z row.

Then X1=4, X2= 8 and Z = 32