Linear Programming

Dr. Ahmed Al-Arashi

Special cases in Linear Programming

 Degeneracy
 Alternative solution
 Unbounded solution.
 Infeasible solution.
Special cases in Linear Programming
Some cases in solving linear programming
are:
1- Degeneracy
In Graphic method
There will be one of the constraint will have no
effect on the solution.

In Simplex method:
One solution will be repeated in the solution
table.
Special cases in Linear Programming
Example:
Max Z = 3 X1 + 7 X2
Subject to
2 X1 + 8 X2 ≤ 16
2 X1 + 4 X2 ≤ 8
X1 , X2 ≥ 0
 Special cases in Linear Programming
Solution:

X1

X2
Special cases in Linear Programming

Solution S1 S2 X1 X2 Basic Variables

16 1 0 2 8 S1
8 0 1 2 4 S2
0 0 0 -3 -7 Z

Solution S1 S2 X1 X2 Basic Variables

2 1/8 0 1/4 1 X2
0 -1/2 1 1 0 S2
14 7/8 0 -5/4 0 Z

Solution S1 S2 X1 X2 Basic Variables

2 1/4 -1/4 0 1 X2
0 -1/2 1 1 0 X1
14 1/4 5/4 0 0 Z
Special cases in Linear Programming
2- Alternative solution
In some cases we find more than one solution
for the objective function.
Example
Max Z = 2 X1 + 4 X2
Subject to
X1 + 2 X2 ≤ 5
X1 + X2 ≤ 4
X1 , X2 ≥ 0
 Special cases in Linear Programming
Solution:

X1

X2
Special cases in Linear Programming
3- Unbounded solution
When the solution area is open.
Example
Max Z = 3 X1 + 2 X2
Subject to
X1 - X2 ≤ 2
2 X1 + 3 X2 ≤ 6
X1 , X2 ≥ 0
Special cases in Linear Programming
4- Infeasible solution
When the solution area is bounded by oppesit
constraint.
Example
Max Z = 2 X1 + 3 X2
Subject to
5/2 X1 - 2 X2 ≤ 5
5 X1 + 4 X2 ≥ 6
X1 , X2 ≥ 0
 Special cases in Linear Programming
Solution:

X1
5

5/2

X2
2 4
 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 2 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 X1 Trans.
Produced we get 6 X6 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 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:
(I) converting constraint to equality equation and adding (Slack
Variables). Put negative slack variable for constraint equation with
(≤ ) and negative for equation with ( ≥ ).
(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 in the objective function.
4- Determine the Leaving Variable. It could be determined by dividing
the constant values (in the constant column) by the value of the
coefficient of the Entering Variable in the constant row. Then 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
20/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
20/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