Advance Operations Research
Uploaded by
goldy243usAdvance Operations Research
Uploaded by
goldy243usLECTURE NOTES
Dr.P.Nagarajan, Assistant Professor of Mathematics
OPERATIONS RESEARCH (MMAF183T20)
UNIT-I
Preview
Gomory’s All Integer Cutting Plane Method
Gomory’s mixed Integer Cutting Plane method
Branch and Bound Method.
Dynamic Programming Terminology –Optimal Decision Policy
Introduction:-
In linear programming problem, the variables are allowed to take any
real or fractional value, however in the real life problem the fractional
values of variables has no significance, for example it does not make sense
that 3.5 workers are required for the project, 2.4 machines required for the
work shop ect.,
The integer solution is obtained by rounding off the optimal value of
the variables to the nearest integer. This approach is very easy, however it
may not satisfies all the given constrains and also the value of the objective
function so obtained may not be optimal.
This type of difficulties can be avoided if the given problem is solved
by integer programming method. The integer linear programming
problems are those in which some or all the variables are restricted to
integer value (discrete value).
Application:-
Capital Budgeting, construction scheduling, plant location and size,
routing and shifting schedule, batch size , capacity extension fixed charges,
ect., are few problems that demonstrate the area of application of integer
programming problem.
Types of Integer Programming Problems
Integer programming problems can be classified in to three
categories
(i) Pure (all) integer programming problems in which all decision
variables are restricted to integer values.
(ii) Mixed integer programming problems in which some, but not all, of
the decision variables restricted to integer values.
(iii) Zero-one integer programming problems in which all decision
variables are restricted to either zero (0) or one (1).
Standard form of Pure Integer Programming Problem
The pure integer programming problem in its standard form can be
written as follows
Max Z=c1x1+c2x2+....cnxn,
Subject to the constraints
a11x1+a12x2+...............a1nxn=b1
a21x1+a22x2+...............a2nxn=b2
a31x1+a32x2+...............a3nxn=b3
;
am1x1+am2x2+...............amnxn=bm
and x1, x2, x3, ....xn 0 and are integers.
Cut
A cut is a linear constraint added to the given LP Problem, it is also
called additional linear constraint.( or fractional cut)
Enumeration and Cutting Plane Solution Concept
The cutting plane method is used to solve integer linear
programming problem
The cutting plane method was developed by R.E. Gomory in the year
1956.
The cutting plane method is based on the generation of sequence of
linear inequality called cut.
The hyper plane boundary of a cut is called cutting plane.
Example:-
Consider the following linear integer programming problem
Max Z=14x1+16x2
Subject to the constraints
4x1+3x2 12 and 6x1+8x2 24
and x1, x2 0 and are integers.
Solution:-
Relax the integer requirements and apply graphical method,
Graphical Method
The feasible region is OABC.
We get the following solution x1=1.71 and x2=1.71 , Max Z=51.42.
This solution does not satisfies the integer requirements of the
variables x1 and x2.
Rounding off the solution, we get x1=2 and x2=2, Max Z=60, But it is
not feasible solution, since it does not satisfies the given inequalities
4x1+3x2= 4(2)+3(2)=14 is not less than 12
6x1+8x2=6(2)+8(2)=28 is not less than 24,
Therefore the solution is infeasible.
The dots in the graph represents the possible integer solution lies in
the feasible region of the LP problem. The dots are also called lattice points.
Cutting plane Method
The optimal lattice point C is obtained by cutting away the small
portion above the dotted line. This suggest a solution procedure that
successively cuts down (reduce) the feasible solution space until the
integer valued corner is found.
The optimal integer solution to the given LP problem is x1=0, x2=3
and Max Z=48.
Remarks:-
Reducing the feasible region by adding the extra constraints (cut) can
never give an improved objective function value.
If ZIP is the minimum value of the objective function in an ILP
problem ZLP is the minimum value of the objective function in an LP
problem, then ZIP ZLP.
Gomory's all integer cutting plane method
A systematic procedure that generates cuts (additional linear
constraints) so as to ensure the integer solution to the LP problem in a
finite number of steps is called Gomory all integer cutting plane algorithm.
Properties of Gomory's Algorithm
Additional linear constraints never cut off that portion of the original
feasible solution space that contains a feasible integer solution to the
original problem.
Each new additional constraints (hyper planes) cut off the current
non integer optimal solution to the linear programming problem.
Construction of additional constraints (CUT)
In the optimal simplex table, we select one of the row, called source
row for which basic variables is non integer. The desired cut is developed
by considering only fractional part of the coefficient in the source row, for
this reason such a cut is also called fractional cut.
Procedure of Gomory's Algorithm
Step:-01
Solve the given LP problem using simplex method by ignoring integer
requirements.
Step:-02
If all the variables in the XB column of the final simplex table is non
negative integer, then the current solution is optimal. otherwise go to next
step.
Step:-03
If some of the basic variables do not have non negative integer
value, then an additional linear constraints called Gomory's linear
constraints (cut) is generated, after having generated linear constraints
(cutting plane) , it is added to the bottom of the optimum simple table so
that the solution no longer remains feasible.
Step:-04
The new problem is then solved by dual simplex method, If the
optimum solution , so obtained is integer. Which is the required one,
otherwise repeat Step: 03 until all basic variables assume non negative
integer values.
Problem:-01
Solve the following integer programming problem using Gomory's
Cutting plane method, Max Z=x1+x2, subject to the conditions 3x1+2x2 5,
x2 2 and x1, x2 0 and integer.
Solution:-
Step:-01
Let us find the optimal solution by simplex method (ignoring integer
conditions )
Simple method
First we have to convert the inequality constraints to equality
constraints by adding slack or surplus variables.
3x1+2x2 5, Add slack variable s1 0, we have 3x1+2x2 +s1=5,
x2 2 , Add slack variable s2 0, we have x2 +s2 =2 ,
We have to add the slack variables in the objective function with zero
coefficients.
Max Z=x1+x2+0s1 +0s2
Initial Basic feasible solution
Let x1=0 and x2=0 (non Basic variables) substitute in the given
problem, we have s1=5 , s2=2 (basic variables) and Max z=0.
Initial Simple table
Cj 1 1 0 0
CBj Basic x1 x2 s1 s2 Minimum
variables of ratios
0 s1=5 [3] 2 1 0 5/3
0 s2=2 0 1 0 1 ---
z=0 Zj 0 0 0 0
Zj-Cj -1 -1 0 0
Arrows represents selected row and column. Square bracket [ ]
represent the diagonal element.( x1 enters the basis and s1 leaves the basis)
Simplex iteration Rule:
(i) Divide the entire selected row by its diagonal element
(ii) All selection column entries zero except diagonal entry
(ii) Remaining all the position values using the formula
present position value - (corresponding selected row value) x
(corresponding selected column value)/(diagonal element)
First row values for the new table
5 3 2 1 0
1 0
3 3 3 3 3
Second row values for the new table
(5)(0) (3)(0) ( 2)(0) (1)(0) (0)(0)
2 2, 0 0, 1 1, 0 0, 1 1
3 3 3 3 3
First simplex table
Cj 1 1 0 0
CBj Basic x1 x2 s1 s2 Minimum
variables of ratios
1 x1=5/3 1 2/3 1/3 0 5/2
0 s2=2 0 [1] 0 1 2
z=5/3 Zj 1 2/3 1/3 0
Zj-Cj 0 -1/3 1/3 0
Max Z=5/3+0+0s1 +0s2=5/3
x2 enters the basis and s2 leaves the basis, the diagonal element is 1
First row values for the new table
5 ( 2)(2 / 3) 1 (0)(2 / 3) 2 ( 2 / 3)(1) 1 ( 2 / 3)(0) 1 ( 2 / 3)(1) 2
1 1 0 0
3 1 3 1 3 1 3 3 3 1 3
Second row values for the new table
2 0 1 0 1
2 0 1 0 1
1 1 1 1 1
Second simplex table
Cj 1 1 0 0
CBj Basic x1 x2 s1 s2 Minimum
variables of ratios
1 x1=1/3 1 0 1/3 -2/3
1 x2=2 0 1 0 1
z=7/2 Zj 1 1 1/3 1/3
Zj-Cj 0 0 1/3 1/3
Max Z=1/3+2+0s1 +0s2=7/2
Since Zj-Cj 0 for all j=1,2,3,4, therefore by the simplex procedure
the above table is optimum, and the optimum solution is given by x1=1/3,
x2=2 and Max z=7/2.
Step-02
In the current optimal solution all the basic variables in the basis are
not integer.
Therefore the above solution is not desirable.
Step:-03
Since x1 is the only basis variable whose value is non-negative
fraction, so we consider the first row as source row for generating Gomory
fractional cut.
[Rule:- Fractional cut
Each non integer coefficient is factorized into integer and fractional
part in such a way that fractional part is positive.]
0+1/3 = x1+0x2+(1/3)s1-(2/3)s2
0+1/3 = (1+0) x1+(0+0) x2+(0+1/3)s1+(-1+1/3)s2
Therefore the Gomory's fractional cut -I is written as follows
(1/3) (1/3) s1+(1/3)s2
(1/3)= (1/3) s1+(1/3)s2 -sg1 (ADD surplus variable Sg1)
(-1/3)= (-1/3) s1-(1/3)s2 +sg1
(Multiply by -1, so that coefficient of sg1 is positive)
Let us add the above equation at the end of the optimum table and
apply dual simplex method.
First Dual simplex Table
Cj 1 1 0 0 0
CBj Basic x1 x2 s1 s2 sg1
variables
1 x1=1/3 1 0 1/3 -2/3 0
1 x2=2 0 1 0 1 0
0 sg1=-1/3 0 0 [-1/3] -1/3 1
z=7/2 Zj 1 1 1/3 1/3 0
Cj -Zj 0 0 -1/3 -1/3 0
Ratio - - 1 1 -
Ratio=(Cj-Zj)/y3j, calculate for all y3j<0
Since the values of the ratio row are positive , therefore the above
table is not optimum.
(Rule:-Suppose if all are negative , it is optimal)
Always we have to select the row that contain Gomory's slack
variable and column with least positive ratio value.
sg1 leaves the basis, s1 enters the basis, diagonal element is -1/3.
First row of new table
(1 / 3)(1 / 3) (0)(1 / 3) (1 / 3)(1 / 3) (1 / 3)(1 / 3)
1/ 3 0 1 1 1/ 3 0 2/3 1
(1 / 3) (1 / 3) (1 / 3) (1 / 3)
(1 / 3)(1)
0 1
(1 / 3)
Second row of new table
(0)(1 / 3) (0)(0) (0)(0) (0)(1 / 3) (0)(1)
2 2 0 0 1 1 1 1 0 0
(1 / 3) (1 / 3) (1 / 3) (1 / 3) (1 / 3)
Last row of the new table (divide the entire row by -1/3)
(1 / 3) 0 0 (1 / 3) (1 / 3) 1
1 0 0 1 1 3
(1 / 3) (1 / 3) (1 / 3) (1 / 3) (1 / 3) (1 / 3)
Second Gomory's cut table
Cj 1 1 0 0 0
CBj Basic x1 x2 s1 s2 Sg1
variables
1 x1=0 1 0 0 -1 1
1 x2=2 0 1 0 1 0
0 s1=1 0 0 1 1 -3
z=2 Zj 1 1 0 0 1
Cj -Zj 0 0 0 0 -1
Since Cj -Zj 0 for all j=1,2,3,4,5,6. Therefore the above table is
optimum.
Hence the optimum integer solution is x1=0, x2=2 and Max Z=2.
Problem:-02
Solve the following integer programming problem using Gomory's
Cutting plane method, Max Z=5x1+7x2, subject to conditions -2x1+3x2 6,
6x1+ x2 30 and x1, x2 0 and integer.
Solution:-
Step:-01
Let us find the optimal solution by simplex method (ignoring integer
conditions )
Simple method
First we have to convert the inequality constraints to equality
constraints by adding slack or surplus variables.
-2x1+3x2 6, Add slack variable s1 0, we have -2x1+3x2+s1=6,
6x1+ x2 30, Add slack variable s2 0, we have 6x1+ x2+s2=30,
We have to add the slack variables in the objective function with zero
coefficients.
Max Z=5x1+7x2+0s1 +0s2
Initial Basic feasible solution
Let x1=0 and x2=0 (non Basic variables) substitute in the given
problem, we have s1=6 , s2=30 (basic variables)and Max z=0.
Initial Simplex table
Cj 5 7 0 0
CBj Basic x1 x2 s1 s2 Minimum
variables of ratios
0 s1=6 -2 [3] 1 0 2
0 s2=30 6 1 0 1 30
z=0 Zj 0 0 0 0
Zj-Cj -5 -7 0 0
The diagonal element is 3.( x2 enters the basis and s1 leaves the basis)
Simplex iteration Rule:
(i) Divide the entire selected row by its diagonal element
(ii) All element of the selected column are zero except diagonal entry
(ii) Remaining all the position values using the formula
present position value - (corresponding selected row value) x
(corresponding selected column value)/(diagonal element)
First row values for the new table
6 2 3 1 0
2 1 0
3 3 3 3 3
Second row values for the new table
(6)(1) ( 2)(1) (1)(1) (0)(0)
30 28 6 20 / 3 0 1 / 3 1 1
3 3 3 3
First simplex table
Cj 5 7 0 0
CBj Basic x1 x2 s1 s2 Minimum
variables of ratios
7 x2=2 -2/3 1 1/3 0 -
0 s2=28 [20/3] 0 -1/3 1 21/5
z=14 Zj -14/3 7 7/3 0
Zj-Cj -29/3 0 7/3 0
Max Z=5.0+7.2+0s1 +0s2=14
x1 enters the basis and s2 leaves the basis, the diagonal element is
20/3
First row values for the new table
(28)(2 / 3) 24 (0)(2 / 3) 1 (2 / 3)(1 / 3) (2 / 3)(1) 1
2 1 1 3 / 10 0
(20 / 3) 5 20 / 3 3 (20 / 3) (20 / 3) 10
Second row values for the new table
28 (20 / 3) 0 (1 / 3) 1
21 / 5 1 0 1 / 20 3 / 20
(20 / 3) (20 / 3) (21 / 3) (20 / 3) (20 / 3)
Second simplex table
Cj 5 7 0 0
CBj Basic x1 x2 s1 s2 Minimum
variables of ratios
7 x2=24/5 0 1 3/10 1/10
5 x1=21/5 1 0 -1/20 3/20
z=273/5 Zj 5 7 37/20 29/20
Zj-Cj 0 0 37/20 29/20
Max Z=5x(21/5)+7x(24/5)+0s1 +0s2=273/5
Since Zj-Cj 0 for all j=1,2,3,4, therefore by the simplex procedure
the above table is optimum, and the optimum solution is given by x1=21/5,
x2=24/5 and Max z=273/5.
Step-02
In the current optimal solution all the basic variables in the basis are
not integer.
Therefore the above solution is not desirable.
Step:-03
Since x1 is the only basis variable whose value is non-negative
fraction, so we consider the first row for generating Gomory fractional cut.
[Rule:- Each non integer coefficient is factorized into integer and fractional
part in such a way that fractional part is positive.]
0+24/5 =0. x1+x2+(3/10)s1+(1/10)s2
4+4/5 =(0+0). x1+(1+0)x2+(0+3/10)s1+(0+1/10)s2
Therefore the Gomory's fractional cut -I is written as follows
(4/5) (3/10) s1+(1/10)s2
(4/5)= (3/10) s1+(1/10)s2 -sg1 (ADD Gomory surplus variable Sg1)
(-4/5)= (-3/10) s1+(-1/10)s2 +sg1
(Multiply by -1, so that coefficient of sg1 is positive)
Let us add the above equation in the last row of the optimum table
and apply dual simplex method
First Dual simplex Table
Cj 5 7 0 0 0
CBj Basic x1 x2 s1 s2 Sg1
variables
7 x2=24/5 0 1 3/10 1/10 0
5 x1=21/5 1 0 -1/20 3/20 0
0 Sg1=-4/5 0 0 [-3/10] -1/10 1
z=273/5 Zj 5 7 37/20 29/20 0
Cj -Zj 0 0 -37/20 -29/20 0
Ratio - - 37/6 29/2 -
Ratio=(Cj-Zj)/y3j, calculate for all y3j<0
Since the values of the ratio row are positive , therefore the above
table is not optimum.
Always we have to select the row that contain Gomory's slack
variable and column with least positive ratio value.
Sg1 leaves the basis, s1 enters the basis, diagonal element is -3/10.
First row of new table
(4 / 5)(3 / 10) (0)(3 / 10) (0)(3 / 10) (3 / 10)(1 / 10)
24 / 5 4 0 0 1 1 1 / 10 0
(3 / 10) (3 / 10) (3 / 10) (3 / 10)
(3 / 10)(1)
0 1
(3 / 10)
Second row of new table
(4 / 5)(1 / 20) (0)(1 / 20) (0)(1 / 20)
21 / 5 13 / 3 1 1 0 0
(3 / 10) (3 / 10) (3 / 10)
(1 / 20)(1 / 10) (1)(1 / 20)
3 / 20 1/ 6 0 1 / 6
(3 / 10) (3 / 10)
Last row of the new table(divide the entire row by -3/10)
(4 / 5) 0 0 (3 / 10) (1 / 10) 1
8/3 0 0 1 1/ 3 10 / 3
(3 / 10) (3 / 10) (3 / 10) (3 / 10) (3 / 10) (3 / 10)
Second Dual simplex Table
Cj 5 7 0 0 0
CBj Basic x1 x2 s1 s2 Sg1
variables
7 x2=4 0 1 0 0 1
5 x1=13/3 1 0 0 1/6 -1/6
0 s1=8/3 0 0 1 1/3 -10/3
z=149/3 Zj 5 7 0 5/6 37/6
Cj -Zj 0 0 0 -5/6 -37/6
Since Cj -Zj<0 for some j=1,2,3,4,5,6. Therefore the above table is not
optimum.
Step:-03 (repetition)
Since x1 is the basis variable whose value is non-negative fraction, so
we consider the second row for generating Gomory fractional cut-II
[Rule:- Each non integer coefficient is factorized into integer and fractional
part in such a way that fractional part is positive.]
4+1/3 =1. x1+0.x2+0.s1+(1/6)s2-1/6sg1
4+1/3 =(1+0). x1+(0+0)x2+(0+0)s1+(0+1/6)s2+(-1+5/6)sg1
Therefore the Gomory's fractional cut -I is written as follows
(1/3) (1/6) s2+(5/6)sg1
(1/3)= (1/6) s2+(5/6)sg1 -sg2 (ADD Gomory surplus variable Sg2)
(-1/3)= (-1/6) s2+(-5/6)sg1 +sg2
(Multiply by -1, so that coefficient of sg2 is positive)
Let us add the above equation in the last row of the optimum table
and apply dual simplex method.
Third Dual simplex Table
Cj 5 7 0 0 0 0
CBj Basic x1 x2 s1 s2 Sg1 Sg2
variables
7 x2=4 0 1 0 0 1 0
5 x1=13/3 1 0 0 1/6 -1/6 0
0 s1=8/3 0 0 1 1/3 -10/3 0
0 Sg2=-1/3 0 0 0 [-1/6] -5/6 1
z=149/3 Zj 5 7 0 5/6 37/6 0
Cj -Zj 0 0 0 -5/6 -37/6 0
Ratio - - - 5 37/5 -
Since few values in the ratio row are positive, therefore it is not
optimal,
sg2 leaves the basis, and s2 enters the basis, diagonal element is -1/6.
First row values of new table
(0)(1 / 3) (0)(0) (0)(0) (0)(0)
4 4 0 0 1 1 0 0
(1 / 6) (1 / 6) ( 1 / 6) ( 1 / 6 )
(0)(5 / 6) (1)(0)
1 1 0 0
( 1 / 6 ) ( 1 / 6 )
Second row values of new table
(1 / 6)(1 / 3) (1 / 6)(0) (1 / 6)(0) (1 / 6)(0)
13 / 3 4 1 1 0 0 0 0
(1 / 6) (1 / 6) (1 / 6) (1 / 6)
(1 / 6)(5 / 6) (1)(1 / 6)
1/ 6 1 0 1
(1 / 6) (1 / 6)
Third row values of new table
(1 / 3)(1 / 3) (1 / 3)(0) (1 / 3)(0) (1 / 3)(0)
8/3 2 0 0 0 0 1 1
(1 / 6) (1 / 6) (1 / 6) (1 / 6)
(1 / 3)(5 / 6) (1)(1 / 3)
10 / 3 5 0 2
(1 / 6) (1 / 6)
Last row values of new table
(1 / 3) 0 0 0 (1 / 6) (5 / 6) 1
2 0 0 0 1 5 6
(1 / 6) (1 / 6) (1 / 6) (1 / 6) (1 / 6) (1 / 6) (1 / 6)
Fourth Dual Simplex Table
Cj 5 7 0 0 0 0
CBj Basic x1 x2 s1 s2 Sg1 Sg2
variables
7 x2=4 0 1 0 0 1 0
5 x1=4 1 0 0 0 -1 1
0 s1=2 0 0 1 0 -5 2
0 s2=2 0 0 0 1 5 -6
z=48 Zj 5 7 0 0 2 5
Cj -Zj 0 0 0 0 -2 -5
Since all Cj -Zj 0 for all j, therefore the above solution is optimal.
Hence the optimum integer solution is x1=4, x2=4 and Max Z=48.
Problem:-03
Solve the following integer programming problem using Gomory's
Cutting plane method, Max Z=1.5x1+3x2+4x3 , subject to conditions
2.5x1+2x2+4x3 12, 2x1+4 x2-x3 7 and x1, x2 ,x3 0 and integer.
Solution:-
Let us find the optimal solution by simplex method (ignoring integer
conditions )
Simple method
First we have to convert the inequality constraints to equality
constraints by adding slack or surplus variables.
2.5x1+2x2+4x3 12,
Add slack variable s1 0, we have 2.5x1+2x2+4x3+s1=12,
2x1+4 x2-x3 7, Add slack variable s2 0, we have 2x1+4 x2-x3+s2=7,
We have to add the slack variables in the objective function with zero
coefficients.
Max Z=1.5x1+3x2+4x2 +0s1 +0s2
Initial Basic feasible solution
Let x1=0, x2=0 and x3=0 (non Basic variables) substitute in the given
problem, we have s1=12 , s2=7 (basic variables)and Max z=0.
Initial Simplex table
Cj 1.5 3 4 0 0
CBj Basic x1 x2 X3 s1 s2 Minimum
variables of ratios
0 s1=12 5/2 2 [4] 1 0 12/4=3
0 s2=7 2 4 -1 0 1 -
z=0 Zj 0 0 0 0 0
Zj-Cj -1.5 -3 -4 0 0
The diagonal element is 4. ( x3 enters the basis and s1 leaves the
basis)
First row values of new table
12 / 4 3, (5 / 2) / 4 5 / 8, 4 / 4 1, 1 / 4, 0 / 4 0
Second row values of new table
(12)(1) (5 / 2)(1) (2)(1) (1)(1)
7 10 2 21 / 8 4 9/2 0 1/ 4
(4) (4) (4) (4)
(0)(1)
1 1
(4)
First Simplex table
Cj 1.5 3 4 0 0
CBj Basic x1 x2 x3 s1 s2 Minimum
variables of ratios
4 x3=3 5/8 1/2 1 1/4 0 6
0 s2=10 21/8 [9/2] 0 1/4 1 20/9
z=12 Zj 5/2 2 4 1 0
Zj-Cj 1 -1 0 1 0
second simplex table
Cj 1.5 3 4 0 0
CBj Basic x1 x2 x3 s1 s2 Minimum
variables of ratios
4 x3=17/9 1/3 0 1 2/9 -1/9
3 x2=20/9 7/12 1 0 1/18 2/9
z=128/9 Zj 37/12 3 4 19/18 2/9
Zj-Cj 19/12 0 0 19/18 2/9
Since Zj-Cj 0 for all j, therefore the above table is optimum
Hence he optimum solution is x = 20/9, x3=17/9, Max z=128/9.
2
1+8/9 =(0+1/3) x1+(0+0)x2+(1+0)x3 +(0+2/9)s1+(-1+8/9)s2
Therefore the Gomory's fractional cut -I is written as follows
(8/9) (1/3)x1 +(2/9) s1+(8/9)s2
(8/9)= (1/3)x1 +(2/9) s1+(8/9)s2 -Sg1
(ADD Gomory surplus variable Sg1)
-(8/9)= -(1/3)x1 -(2/9) s1-(8/9)s2 +Sg1
(Multiply by -1, so that coefficient of sg1 is positive)
First dual simple table
Cj 1.5 3 4 0 0 0
CBj Basic x1 x2 x3 s1 s2 Sg1
variables
4 x3=17/9 1/3 0 1 2/9 -1/9 0
3 x2=20/9 7/12 1 0 1/18 2/9 0
0 Sg1=-8/9 -1/3 0 0 -2/9 [-8/9] 1
z=128/9 Zj 37/12 3 4 19/18 2/9 0
Cj-Zj -19/12 0 0 -19/18 -2/9 0
Ratio 19/4 - - 19/4 1/4 0
sg1 leaves the basis, s2 enters the basis
Second dual simplex table
Cj 1.5 3 4 0 0 0
CBj Basic x1 x2 x3 s1 s2 Sg1
variables
4 x3=2 3/8 0 1 1/4 0 1/8
3 x2=2 1/2 1 0 0 0 1/4
0 S2=1 3/8 0 0 1/4 1 -9/8
z=14 Zj 3 3 4 1 0 5/4
Cj-Zj -3/2 0 0 -1 0 -5/4
Since Zj-Cj 0 for all j, therefore the above table is optimum
Hence he optimum solution is x = 2, x3=2, Max z=14.
2
Mixed Integer Programming Algorithm
Step:-01
Solve the given LP problem using simplex method, by ignoring integer
requirements of the variables.
Step:-02
If all integer restricted basic variables have integer values, then the
current solution is optimal. otherwise go to step 03.
Step:-03
Choose a row r corresponding to a basic variable xr that has the
highest fractional value fr and generate a cutting plane as below
f
s g f r a rj x j r a rj x j where 0<fr<1.
fr 1
Add this cutting plane at the bottom of the optimum simplex table
Step:-04
Find the new optimal solution using dual simplex method, and return
to step 02. The process is repeated until all the restricted variables are
integer.
Problem:-01
Solve the following mixed integer programming problem
Max Z= x1+x2
Subject to the constraints
3x1+2x2 5,
x2 2
and x1, x2 0 ; x1 is non negative integer.
Solution:-
Step:-01
Let us find the optimal solution by simplex method (ignoring integer
conditions )
Simple method
First we have to convert the inequality constraints to equality
constraints by adding slack or surplus variables.
3x1+2x2 5, Add slack variable s1 0, we have 3x1+2x2+s1=5,
x2 2 , Add slack variable s2 0, we have x2+s2=2,
Max Z=x1+x2+0s1 +0s2
Initial Basic feasible solution
Let x1=0 and x2=0 (non Basic variables) substitute in the given
problem, we have s1=5 , s2=2 (basic variables)and max z=0.
Initial Simple table
Cj 1 1 0 0
CBj Basic x1 x2 s1 s2 Minimum
variables of ratios
0 s1=5 [3] 2 1 0 5/3
0 s2=2 0 1 0 1 -
z=0 Zj 0 0 0 0
Zj-Cj -1 -1 0
Since some Zj-Cj are <0, therefore the above solution is not optimal.
Diagonal element is 3. x1 enters the basis and s1 leaves the basis
First row values
5/3, 3/3=1 2/3 1/3 0/3=0
Second row values
2-(5)(0)/3=2 1-(0)(2)/3=1 0-(0)(1)/3=0 1-(0)(0)/3=1
First simplex table
Cj 1 1 0 0
CBj Basic x1 x2 s1 s2 Minimum
variables of ratios
1 x1=5/3 1 2/3 1/3 0 5/2
0 s2=2 0 [1] 0 1 2
z=5/3 Zj 1 2/3 1/3 0
Zj-Cj 0 -1/3 1/3 0
Since some Zj-Cj are <0, therefore the above solution is not optimal.
Diagonal element is 1, x2 enters the basis and s2 leaves the basis
First row values
5/3-(2)(2/3)/1=1/3, 1-(0)(2/3)/1=1 1/3-(2/3)(0)=1/3
0-(1)(2/3)=-2/3
Second row values
2/1=2 0/1=0 1/1=1 0/1=1 1/1=1
Second simplex table
Cj 1 1 0 0
CBj Basic x1 x2 s1 s2 Minimum
variables of ratios
1 x1=1/3 1 0 1/3 -2/3
1 x2=2 0 1 0 1
z=7/3 Zj 1 1 1/3 1/3
Zj-Cj 0 0 1/3 1/3
Since all Zj-Cj values are non-negative, therefore the above solution is
optimal.
The optimal solution is x1=1/3 , x2=2 and Max Z=7/2
Step-02
In the current optimal solution the basic variable x1 not integer.
Therefore the above solution is not desirable.
Step:-03
Since x1 is the only basis variable whose value is non-negative
fraction, so we consider the first row for generating Gomory fractional cut.
[Rule:- Each non integer coefficient is factorized into integer and fractional
part in such a way that fractional part is positive.]
1/3=x1+0x2+1/3s1-2/3s2
(0+1/3)=(1+0)x1+(0+1/3)s1+(-1+1/3)s2
1/3 0+(1/3)s1+(1/3)s2 (Gomory fractional cut-I)
1/3=(1/3)s1+(1/3)s2-sg1 (Add Gomory surplus variable sg1)
-1/3=-(1/3)s1-(1/3)s2+sg1
(Multiply by -1, so that coefficient of sg1 is positive)
Add this in the above table as a last row, we have
First Dual Simplex Table
Cj 1 1 0 0 0
CBj Basic x1 x2 s1 s2 sg1
variables
1 x1=1/3 1 0 1/3 -2/3 0
1 x2=2 0 1 0 1 0
0 sg1=-1/3 0 0 [-1/3] -1/3 1
z=7/3 Zj 1 1 1/3 1/3 0
Cj- Zj 0 0 -1/3 -1/3 0
Ratio - - 1 1 -
Ratio=(Cj- Zj)/y3j, where y3j<0.
sg1 leave the basis and s1 enters the basis, diagonal element is -1/3
Second Dual Simplex Table
Cj 1 1 0 0 0
CBj Basic x1 x2 s1 s2 sg1
variables
1 x1=0 1 0 0 -1 1
1 x2=2 0 1 0 1 0
0 s1=1 0 0 1 1 -3
z=2 Zj 1 1 0 0 1
Cj- Zj 0 0 0 0 -1
Since all Cj- Zj 0, therefore the above solution is optimal.
Hence the mixed integer optimum solution is x1=0 , x2=2 and Max Z=2.
Problem:02
Solve the following mixed integer problem
Max Z=4x1+6x2+2x3
Subject to constraints
4x1-4x2 5,
-x1+6x2 5 ,
-x1+x2+x3 5
and x1, x2, x3 0; x1 , x3 are integers.
Solution:-
Simplex method
4x1-4x2 5, Add slack variable s1, we have 4x1-4x2+s1=5,
-x1+6x2 5 , Add slack variable s2, we have -x1+6x2+s2=5,
-x1+x2+x3 5, Add slack variable s3, we have -x1+x2+x3+s3=5.
Max Z=4x1+6x2+2x3+0s1+0s2+0s3
IBFS x1=0, x2=0, x3=0, s1=5, s2=5,s3=5, Max z=0.
Initial Simplex table
Cj 4 6 2 0 0 0
CBj Basic x1 x2 x3 s1 s2 s3 Ratio
variables
0 s1=5 4 -4 0 1 0 0 -
0 s2=5 -1 [6] 0 0 1 0 5/6
0 s3=5 -1 1 1 0 0 1 5
z=0 Zj 0 0 0 0 0 0
Zj -Cj -4 -6 -2 0 0 0
Since some Zj -Cj values are negative, therefore the above is not a
optimal table.
i.e x2 enters the basis and s2 leaves the basis, diagonal element is 6
First row values
5-(5)(-4)/6=25/3, 4-(-1)(-4)/6=10/3 0-(-4)(0)/6=0
1-(0)(-4)/6=1 0-(1)(-4)/6=2/3 0-(0)(-4)/6=0
Second row values
5/6 -1/6 6/6=1 0/6=0 0/6=0 1/6 0/6
Third row values
5-(5)(1)/6=25/6 -1-(-1)(1)/6=-5/6 1-(0)(1)/6=1
0-(0)(1)/6=0 0-(1)(1)/6=-1/6 1-(0)(1)/6=1
First simplex table
Cj 4 6 2 0 0 0
CBj Basic x1 x2 x3 s1 s2 s3 Ratio
variables
0 s1=25/3 [10/3] 0 0 1 2/3 0 25/10
6 x2=5/6 -1/6 1 0 0 1/6 0
0 s3=25/6 -5/6 0 1 0 -1/6 1
z=5 Zj -1 6 0 0 1 0
Zj -Cj -5 0 -2 0 1 0
Since some Zj -Cj values are negative, therefore the above table is not
optimal.
x1 enters the basis, s1 leaves the basis, diagonal element is 10/3.
First row values
(25/3)/(10/3)=5/2, (10/3)/(10/3)=1 0/(10/3)=0
0/(10/3)=0 1/(10/3)=3/10 (2/3)/(10/3)=1/5
0-(25/3)(0)/(10/3)=0
Second row values
(5/6)-(25/3)(-1/6)/(10/3)=5/4 1-(-1/6)(0)/=1
0-(0)(-1/6)/(10/3)=0 0-(1)(-1/6)/(10/3)=1/20
(1/6)-(2/3)(-1/6)/(10/3)=1/5 0-(0)(-1/6)/(10/3)=0
Third row values
(25/6)-(25/3)(-5/6)/(10/3)=25/4 0-(-5/6)(0)/(10/3)=0
1-(0)(-5/6)/(10/3)=1 0-(-5/6)(1)/(10/3)=1/4
-1/6-(-5/6)(2/3)/(10/3)=0 1-(0)(-5/6)/(10/3)=1
Second simplex table
Cj 4 6 2 0 0 0
CBj Basic x1 x2 x3 s1 s2 s3 Ratio
variables
4 x1=5/2 1 0 0 3/10 1/5 0 -
6 x2=5/4 0 1 0 1/20 1/5 0 -
0 s3=25/4 0 0 [1] 1/4 0 1 25/12
z=35/2 Zj 4 6 0 3/2 2 0
Zj -Cj 0 0 -2 3/2 2 0
Since some Zj -Cj values are negative, therefore the above table is not
optimal.
x3 enters the basis, s3 leaves the basis, diagonal element is 1.
First row values
(5/2)-(0)(25/12)/1=5/2 1-(0)(0)/1=1 0-(0)(0)/1=0
3/10-(0)(1/4)/1=3/10 1/5-(0)(0)/1=1/5 0-(1)(0)/1=0
Second row values
(5/4) -(0)(25/12)/1=5/4 0-(0)(0)/1=0 1-(0)(0)/1=1
(1/20)-(0)(0)/1=1/20 1/5-(0)(0)/1=1/5 0-(0)(1)/1=0
Third row values
(25/4)/1=25/4 0/1=0 0/1=0 1/1=1
(1/4)/1=1/4 0/1=0 1/1=1
Third simplex table
Cj 4 6 2 0 0 0
CBj Basic x1 x2 x3 s1 s2 s3 Ratio
variables
4 x1=5/2 1 0 0 3/10 1/5 0 -
6 x2=5/4 0 1 0 1/20 1/5 0 -
2 x3=25/4 0 0 1 1/4 0 1 -
z=30 Zj 4 6 2 2 2 2
Zj -Cj 0 0 0 2 2 0
Since some Zj -Cj values are either zero or positive, therefore the
above table is optimal.
In the above optimal solution x1 and x3 are not integer, therefore the
current optimal solution is not desirable .
Let us consider the fractional cut (5/2=2+1/2) (25/4=6+1/4)
5/2=x1+(3/10)s1+(1/5)s2
(2+1/2)=(1+0)x1+(0+3/10)s1+(0+1/5)s2
(1/2) (3/10)s1+(1/5)s2 (Fractional cut I)
(1/2)=(3/10)s1+(1/5)s2-sg1 (Add Gomory slack variable sg1)
-1/2=-3/10s1-1/5s2+sg1 (Multiply by -1)
Add the above equation in the optimum simplex table and solve
using dual simplex methods, we have
First Dual Simplex table
Cj 4 6 2 0 0 0
CBj Basic x1 x2 x3 s1 s2 s3 sg1
variables
4 x1=5/2 1 0 0 3/10 1/5 0 0
6 x2=5/4 0 1 0 1/20 1/5 0 0
2 x3=25/4 0 0 1 1/4 0 1 0
0 sg1=-1/2 0 0 0 [-3/10] -1/5 0 1
z=30 Zj 4 6 2 2 2 2 0
Cj -Zj 0 0 0 -2 -2 -2 0
Ratio - - - 20/3 10 - -
Since some values of ratio are positive, therefore the above it not
optimal.
s1 enters the basis, sg1 leaves the basis, diagonal element -3/10.
First row values
(5/2)-(3/10)(-1/2)/(-3/10)=2 1-(3/10)(0)/(-3/10)=1
0-(3/10)(0)/(-3/10)=0 0-(3/10)(0)/(-3/10)=0
(1/5)-(3/10)(-1/5)/(-3/10)=0 0-(0)(3/10)/(-3/10)=0
0-(1)(3/10)/(-3/10)=1
Second row values
(5/4)-(-1/2)(1/20)/(-3/10)=7/6 0-(0)(1/20)/(-3/10)=0
1-(1/20)(0)/(-3/10)=1 0-(1/20)(0)/(-3/10)=0
(1/5)-(1/20)(-1/5)/(-3/10)=1/6 0-(0)(1/20)/(-3/10)=0
0-(1/20)(1)/(-3/10)=1/6
Third row values
(25/12)-(-1/2)(1/4)/(-3/10)=5/3 0-(0)(1/4)/(-3/10)=0
0-(0)(1/4)/(-3/10)=0 1-(0)(1/4)/(-3/10)=1
0-(-1/5)(1/4)/(-3/10)=-1/6 1-(0)(1/4)/(-3/10)=1
0-(1)(1/4)/(-3/10)=5/6
Fourth row values
(-1/2)/(-3/10)=5/3 0/(-3/10)=0 0/(-3/10)=0 0/(-3/10)=0
(-3/10)/(-3/10)=1 (-1/5)/(-3/10)=2/3 0/(-3/10)=0
1/(-3/10)=-10/3
Second dual simplex Table
Cj 4 6 2 0 0 0 0
CBj Basic x1 x2 x3 s1 s2 s3 sg1
variables
4 x1=2 1 0 0 0 0 0 1
6 x2=7/6 0 1 0 0 1/6 0 1/6
2 x3=35/6 0 0 1 0 -1/6 1 5/6
0 s1=5/3 0 0 0 1 2/3 0 -10/3
z=80/3 Zj 4 6 2 0 2/3 2 20/3
Cj -Zj 0 0 0 0 -2/3 -2 -20/3
Since all Cj -Zj 0 , therefore the above table is optimal, but the basic
variable x3 is not integer.
Let us add fractional cut in the above table
35/6=x3-(1/6)s2+s3+(5/6)sg1
(5+5/6)=(1+0)x3+(-1+5/6)s2+(1+0)s3+(0+5/6)sg1
(5/6) (5/6)s2+(5/6)sg1 (Fractional cut-II)
(5/6) =(5/6)s2+(5/6)sg1-sg2 (Add Gomory slack variable sg2)
(-5/6) =-(5/6)s2-(5/6)sg1+sg2 (Multiply by -1)
Add the this equation at the end of the above optimum table.
Third Dual Simplex Table
Cj 4 6 2 0 0 0
CBj Basic x1 x2 x3 s1 s2 s3 sg1 sg2
variables
4 x1=2 1 0 0 0 0 0 1 0
6 x2=7/6 0 1 0 0 1/6 0 1/6 0
2 x3=35/6 0 0 1 0 -1/6 1 5/6 0
0 s1=5/3 0 0 0 1 2/3 0 -10/3 0
0 sg2=-5/6 0 0 0 0 [-5/6] 0 -5/6 1
z=80/3 Zj 4 6 2 0 2/3 2 20/3 0
Cj -Zj 0 0 0 0 -2/3 -2 -20/3 0
Ratio - - - - 4/5 - 8 -
Some values in the ratio row are positive, therefore the above table is
not optimal.
sg2 leaves the basis, s2 enters the basis, diagonal element -5/6.
First row values
2-(0)(-5/6)/(-5/6)=2 1-(0)(0)/(-5/6)=1 0-(0)(0)/(-5/6)=0
0-(0)(0)/(-5/6)=0 0-(0)(0)/(-5/6)=0 0-(0)(0)/(-5/6)=0
1-(0)(-5/6)/(-5/6)=1 0-(0)(1)/(-5/6)=0
Second row values
(7/6)-(1/6)(-5/6)/(-5/6)=1 0-(0)(1/6)/(-5/6)=0
1-(1/6)(0)/(-5/6)=1 0-(1/6)(0)/(-5/6)=0
0-(0)(1/6)/(-5/6)=0 0-(1/6)(0)/(-5/6)=0
1/6-(1/6)(-5/6)/(-5/6)=0 0-(1/6)(1)/(-5/6)=1/5
Third row values
(5/3)-(-1/6)(-5/6)/(-5/6)=11/6 0-(-1/6)(0)/(-5/6)=0
0-(-1/6)(0)/(-5/6)=0 1-(-1/6)(0)/(-5/6)=1
0-(-1/6)(0)/(-5/6)=0 1-(-1/6)(0)/(-5/6)=1
(5/6)-(-1/6)(-5/6)/(-5/6)=1 0-(-1/6)(1)/(-5/6)=-1/5
Fourth row values
(5/3)-(2/3)(-5/6)/(-5/6)=1 0-(2/3)(0)/(-5/6)=0
0-(2/3)(0)/(-5/6)=0 0-(2/3)(0)/(-5/6)=0
1-(2/3)(0)/(-5/6)=1 0-(2/3)(0)/(-5/6)=0
(-10/3)-(2/3)(-5/6)/(-5/6)=-4 0-(2/3)(1)/(-5/6)=4/5
Fifth row values
(-5/6)/(-5/6)=1 0/(-5/6)=0, 0/(-5/6)=0, 0/(-5/6)=0
0/(-5/6)=0, (-5/6)/(-5/6)=1 0/(-5/6)=0
(-5/6)/(-5/6)=1 1/(-5/6)=-6/5
Fourth Dual Simplex Table
Cj 4 6 2 0 0 0
CBj Basic x1 x2 x3 s1 s2 s3 sg1 sg2
variables
4 x1=2 1 0 0 0 0 0 1 0
6 x2=1 0 1 0 0 0 0 0 1/5
2 x3=6 0 0 1 0 0 1 1 -1/5
0 s1=1 0 0 0 1 0 0 -4 4/5
0 s2=1 0 0 0 0 1 0 1 -6/5
z=26 Zj 4 6 2 0 0 2 6 4/5
Cj -Zj 0 0 0 0 0 -2 -6 -4/5
Since all Cj -Zj 0 , therefore the above table is optimal.
Hence the mixed integer optimal solution is given by x1=2, x2=1, x3=6
and Max Z=4(2)+6(1)+2(6)=26.
Branch and Bound Method
It was first developed by A H Land and AG Doig.
It can be used to solve all integer, mixed integer and zero-one
integer programming problems
It partition the feasible solution region in to smaller regions
until the optimal solution obtained.
It starts by imposing bounds on the value of the objective
function that helps the sub problem to be eliminated from the
consideration when the optimum solution has been found.
Procedure of Branch and Bound Algorithm
Step:-01(Initialization)
Consider the following all integer programming problem
Max Z=c1x1+c2x2+.....cnxn
Subject to the constraints
a11x1+a12x2+......+a1nxn=b1
a21x1+a22x2+......+a2nxn=b2..
.
am1x1+am2x2+......+amnxn=b1m
and xj 0 and non negative integer.
Obtain the optimal solution of the given problem ignoring integer
restriction on the variables
(i) If the solution to this LP problem (say LP-A) is infeasible or unbounded,
the solution to the all integer programming problem is also infeasible or
unbounded , as the case may be.
(ii) If the solution satisfies the integer restriction, the optimal integer
solution has been obtained. If one or more basic variables do not satisfies
integer requirement, then go to step 2. Let the optimal value of the
objective function of LP-A be Z1. This value provides an initial upper bound
on objective function value and it is denoted by ZU.
(iii) Find the feasible value by rounding off each variable value. The value
of the objective function so obtained is the least upper bound and it is
denoted by ZL.
Step:-02(Branching step)
(i) Let xk be one basic variable which does not have an integer value and
also has the largest fractional value
(ii) Branch ( or partition) the LP-A into two new LP sub problems (also
called nodes) based on integer values of xk that are immediately above and
below its non integer value. That is, it is portioned by adding two mutually
exclusive constraints.:
xk [xk] and xk [xk]+1
to the original LP problem, Here [xk] is the integer portion of the current
non-integer value of the variable xk. This is obviously is done to exclude the
non integer value of the variable xk. The two new Lp sub problems are as
follows:
LP Sub problem B LP Sub Problem C
n n
Max Z= c j x j Max Z= c j x j
j 1 j 1
n n
subject to aij x j bi subject to a ij x j bi
j 1 j 1
xk [xk] xk [xk]+1
and xj 0 and xj 0
Step:-03(Bound step)
Obtain the optimal solution of sub problems B and C. Let the optimal
value of the objective function of LP-B be Z2 and that of LP-C be Z3. The best
integer solution value becomes the lower bound on the integer LP problem
objective function value (initially this is the rounded off value). Le the
lower bound be denoted by ZL.
Step:-03(Fathoming step) Examining the solution of both LP-B and LP-C
(i) If the sub problem yields an infeasible solution , then terminate the
branch.
(ii) If the sub problems yields the feasible solution, but not integer solution
then go to step 2.
(iii)If the sub problem yields the integer feasible solution, then examine the
value of the objective function. If the value is equal to upper bound, then
the optimal solution has been obtained. But if it is not equal to upper bound
but exceed the lower bound, then this value is considered as new upper
bound and return to step 2. Finally, If it is less than the lower bound
terminate the branch.
Step 05 (Termination)
procedure of branching and bounded continues, until no sub
problem remains to be examined. At this stage, the integer solution
corresponding to the current lower bound is optimal all integer
programming problem.
Problem:-01
Solve the following all integer programming problem using branch
and bound method,
Max Z=2x1+3x2,
Subject to the conditions
6x1+5x2 25,
x1+3x2 10
and x1, x2 0 and integers
Solution:-
Step:-01
Relaxing the integer condition, Let us find the optimal solution to the
given LP problem by graphical method
Graphical Method
Let us draw the line 6x1+4x2=25-----(1)
Let x1=0, 6(0)+5x2=25 =>x2=25/4 i.e (0,5)
Let x2=0, 6x1+5(0)=25 =>x1=25/6 i.e(4.16,0)
Let us draw the line x1+3x2=10------(2)
Let x1=0, (0)+3x2=10 =>x2=10/3 i.e (0,3.33)
Let x2=0, x1+3(0)=10 =>x1=10 i.e(10,0)
To find the intersection point
(1)x1=> 6x1+5x2=25
(2)x6=> 6x1+18x2=60
(Subtract) ------------------
-13x2=-35 =>x2=35/13
Sub x2 values in equation (2), we have x1=25/13
i.e the intersection point is (1.92,2.69)
At (4.16,0) Max Z=2(4.16)+3(0)=8.32
At (0,3.33) Max Z=2(0)+3(3.33)=9.99
At (1.92,2.69) Max Z=2(1.92)+3(2.69)=11.91
The optimum solution is x1=1.92, x2=2.69 and Max Z1=11.91.
Let ZU=11.91 be the initial upper bound.
The feasible solution by rounding off the solution gives the initial
lower bound ZL=11 (rounding off x1=1, x2=3). The optimal solution lies
between these two bounds.
Step:-02(Branching step)
Here both x1 and x2 are not integers, therefore we can select variable
for branching with highest fractional value, here x2 has more fractional
value compared to x1.
Solving the variable x2 for branching, divide the given problem into
two sub problem A and B to eliminate the fractional part of x2=2.69,
The new constraints to be added are x2 2 and x2 3 .
LP sub problem B LP sub problem C
Max Z=2x1+3x2, Max Z=2x1+3x2,
Subject to the conditions Subject to the conditions
6x1+5x2 25, 6x1+5x2 25,
x1+3x2 10 x1+3x2 10
x2 2 x2 3
and x1, x2 0 and integers and x1, x2 0 and integers
Draw the line x2=2-------(3) Draw the line x2=3--------(4)
It is the line parallel to x1 axis and It is a line parallel to x1 axis and
passes through (0,2) passes through (0,3)
The corresponding graph is given by
The solution to the sub The solution to the sub
problem B is given by equation (1) problem C is given by equation (2)
and (3) and (4)
Sub x2=2 in equation (1), we Sub x2=3 in equation (2), we
have 6x1+5(2)=25 =>x1=5/2 have x1+3(3)=10 =>x1=1
i.e (2.5, 2) and i.e (1, 3) and
Max Z2=2(2.5)+3(2)=11 Max Z3=2(1)+3(3)=11
Step:-03 (Bound step)
Rule :-The best integer solution gives the lower bound.
Here the best integer solution is x1=1, x2=3 and Max Z3=11
The value ZL=11 is the lower bound for the given LP problem.
(i.e the value of the objective function in the sub sequence steps
cannot be less than this)
Step:-04(Fathoming step)
Both the sub problems B and C gives same Z value.
In the sub problem C both the variables x1 and x2 are integer, so there
is no need to branch the sub problem C further.
Since ZL Z3<ZU (11 11<11.91), therefore the new upper bound is
ZU=11.
In the sub problem B x1 is not an integer and since ZL Z2( 11 11).
Therefore the sub problem B can be branch further.
Step:-05 (Branch step)
Let us divide the sub problem B into two sub problem namely D and
E by taking variable x1=2.5.
The new constraints to be added are x1 2 and x1 3 .
LP sub problem D LP sub problem E
Max Z=2x1+3x2, Max Z=2x1+3x2,
Subject to the conditions Subject to the conditions
6x1+5x2 25, 6x1+5x2 25,
x1+3x2 10 x1+3x2 10
x2 2 x2 2
x1 2 x1 3
and x1, x2 0 and integers and x1, x2 0 and integers
Draw the line x1=2-------(5) Draw the line x1=3------(6)
It is the line parallel to x2 axis and It is the line parallel to x2 axis and
passes through (2,0) passes through (3,0)
The solution to the sub The solution to the sub
problem D is given by equation (3) problem E is given by equation (1)
and (5) and (6)
i.e x1=2 and x2=2 Sub x1=3 in equation (1), we
have 6(3)+5x2=25 =>x2=1.4
Max Z4=2(2)+3(2)=10 i.e (3, 1.4) and
Max Z5=2(3)+3(1.4)=10.2
Step:-05(Bound step)
Rule :-The best integer solution gives the lower bound.
Here the best integer solution is x1=2, x2=2 and Max Z4=10
Step:-06(Bound step)
The solution to the LP sub problem D is integer feasible, but Z4< ZL
(10<11), and since value of lower bound remain unchanged (ZL=11).
therefore the sub problem D is not considered for further branching.
Since solution of sub problem E is non integer (x2 is not integer), So it
can be further branched with variable x2, but Z5<ZL (10.2<11), therefore
sub problem E is not considered for further branching.
Thus the integer solution corresponding to the current lower bound
is the optimal solution.
Hence the integer optimal solution is corresponding to sub problem C
and is given by x1=1, x2=3 and Max Z=11
The entire branch and bound procedure can be represented by
following enumeration tree. Each node is a sub problem.
Note:-
(i) Suppose if both the sub problem gives non integer solution, then
always the sub problem which has maximum objective value has to
branched further.
(ii) Suppose if one of the sub problem has no feasible solution and other
has feasible solution but not integer and any other sub problem of same
kind exist, always select the sub problem which has maximum objective
function value for further branching.
Dynamic programming problem
Introduction:-
Dynamic programming is a mathematical technique dealing with the
optimization of multistage decision processes. It provides a systematic
procedure for determining the optimal combination decision.
In contrast to linear programming, there does not exist a standard
mathematical formulation of dynamic programming problem. The word
programming has been used in the mathematical sense of selecting
(planning) an optimal allocation of resources, and it is 'dynamic' as it
particularly useful for problems where decisions are taken at several stages,
such as everyday or every week.
Dynamic Programming Technique
Dynamic programming is a technique that allow us to break up
difficult problems into sequence of sub problems
It start with a small sub problem and finds the optimal solution
for this smaller problem.
It then gradually enlarges the problem, finding the current
optimal solution from the preceding one, until the original
problem is solved in its entirely.
Richard Bellman developed this technique in early 1950 and invented
its name. It is also known as recursive optimization.
Backward Recursive Equation(function)
Let fi(xj) be the shortest distance to node j at stage i.
Let d(xj-1, xj) be the distance between xj-1 and xj.
The recursive equation is given by
fi ( x j ) min
all feasible
{d ( x j 1 , x j ) fi 1 ( x j 1 )} where i=1,2,3...n (stages) and
(x j 1 , x j ) routes
j=1,2,3...m (states)
Note:-
In backward recursive equation we calculate fi(xj) is obtained by
substituting the value of fi-1(xj-1) (previous stage value)
Forward Recursive Equation(function)
Let fi(xj) be the shortest distance to node j at stage i.
Let d(xj-1, xj) be the distance between xj-1 and xj.
The forward recursive equation is given by
fi ( x j ) min {d ( x j , x j 1 ) f i 1 ( x j 1 )} where i=1,2,3...n (stages) and
all feasible
(x j 1 , x j ) routes
j=1,2,3...m (states)
Note:-
In forward recursive equation we calculate fi(xj) by substituting the
value of fi+1(xj+1) (next stage value)
Bellman's Principle of Optimality
An optimal policy has the property that, whatever the initial state and
initial decision are, the remaining decisions must constitute an optimal
policy with regard to the state resulting from the first decision process.
In greedy method only one decision sequence is generated.
In dynamic programming many decision sequences may be generated
Forward Recursion
Forward recursion in which computation proceeds starts from the
stage 1 and ending at stage n.
Backward Recursion
Backward recursion in which computation proceeds starts from the
stage n and ending at stage 1.
In dynamic programming problem, the solution process is initiated
by determining the optimal policy for the last stage, which we label as stage
1, since we analyze it first, with the state transformation function and
recursive criterion function developed for the particular problem. We then
work backward stage by stage to find the optimal policy for each state of
every stage i, given the optimal policy for each state of stage i-1. The
optimal policy for the entire problem is determined when this process
terminates at the initial stage. This procedure is called backward recursion.
Note :-
Both forward and backward procedure yields the same solution.
Forward procedure seems to be more logic
DP invariably uses backward procedure, the reason is backward
procedure more efficient computationally.
SHORTEST ROUTE PROBLEM
Suppose that you want to select the shortest highway route between
two cities. The network in the following figure provides the possible route
between the starting city at node 1, and the ending city at node 7.
We can solve this problem by exhaustively enumerating all such
routes between node 1 to node 7 (Here there are five such routes namely
1-2-5-7, 1-3-6-7, 1-3-5-7, 1-4-5-7, 1-4-6-7). However in large network
exhaustive enumeration is intractable computationally.
We first decompose this problem into stages as delineated by the
vertical dashed lines in following figure
(i) Solve using forward recursion procedure
Optimum solution at Stage `1'
In stage one ending nodes are 2,3,4, this nodes can be reached from
starting node 1 only.
Shortest distance from node 1 to node 2 is 7
shortest distance from node 1 to node 3 is 8
shortest distance from node 1 to node 4 is 5
Optimum solution at Stage `2'
In stage one ending nodes are 5,6.
Here the node 5 can be reached from three nodes 2,3,4.
the node 6 can be reached from two nodes 3,4.
Shortest distance from node 1 to node 5 are 7+12=19, 8+8=16,
5+7=12 corresponding to the following routes 1-2-5, 1-3-5, 1-4-5. Here the
minimum value is 12 corresponding to the routes 1-4-5
Shortest distance from node 1 to node 6 is 8+9=17, 5+13=18
corresponding to the following routes 1-3-6, 1-4-6. Here the minimum
value is 17 corresponding to the routes 1-3-6.
Optimum solution at Stage `3'
In stage one ending nodes is 7.
Here the node 7 can be reached from three nodes 5,6.
Shortest distance from node 1 to node 7 are 12+9=21, 17+6=23
corresponding to the following routes 1-4-5-7, 1-3-6-7. Here the minimum
value is 21 corresponding to the routes 1-4-5-7.
Hence stage 3 shows that the shortest distance between node 1 to 7
is 21 miles,
(ii) Solve using Back word recursion.
Since there are three stages, therefore i=1,2,3.
and there are 7 states, therefore j=1,2,3,4,5,6,7.
Stage
Each point in the problem where a decision must be made.
Example:-
(i) In Shortest Root Problem
The stage may be group of cities with a common property (minimum
number of areas from the destination)
(ii) In Sales Man Allocation Problem
Each territory represents a stage.
State
Information describing the problem at each stage, generally in the
form of specific value of state variables.
Example:-
(i) In Shortest Root Problem
The state at any stage was a specific city.
(ii) In Sales Man Allocation Problem
The state was the specific value of the number of salesmen still
available, Here the number of salesman is a state variable.
Policy A
A decision making rule which, at any stage, permits a feasible
sequence of decisions. In effect, a policy transforms
Example:-
(i) In Shortest Root Problem
The policy at any stage of the problem was the selection of the routes
to the next group of cities.
(ii) In Sales Man Allocation Problem
The policy at any stage of the problem would be the allocation of
some specific number of available salesman to the territory represented by
that stage.
Optimal Policy A
A policy which optimizes the value of a criterion, objective, or return
function. Stating in any given state of any stage., the optimal policy depends
only upon that state and not upon how it was reached.
In other words, the optimal decision at any state is in no way
dependent on the previous history of the system.
i.e The future decisions for the remaining stages will constitute an
optimal policy regardless of the policy adopted in previous stage.
State Transformation Function
The state transformation function Ti transforms state Si to state Si-1,
given decision Di.
i.e Ti(Si,Di)=Si-1, Moving backward to the system.
Note
There are two differences between Linear programming and
Dynamic programming problem.
(i) There is no common method available for solving all dynamic
programming problem, like simplex method available for linear
programming problem.
(ii) Linear programming is a method that gives single (one
time period) solutions. But dynamic programming has the
power to determine the optimal solution over a one year time
horizon by breaking the problem into twelve smaller one-
month time horizon problem and solve each of the optimally.
ie. in DP many decision making sequence may be generated.
Problem:-01
Use dynamic programming method to solve the following problem
Min Z=y12+y22+y32
Subject to the constraints
y1+y2+y3 15 and y1, y2, y3 0
Solution:-
Since there are three decision variables y1, y2, y3.
Therefore the given problem is to be solved in 3 stages.
Let s3= y1+y2+y3 ----------(1)
` s2= y1+y2 (=s3-y3) --------(2)
s1=y1 (=s2-y2) ---------(3)
The functional relation is given by
min
f1(s1)= y12 --------(4)
0 y1 s1
min min
f2(s2)= y12 y22 { f1 ( s1 ) y22 } --------(5)
0 y2 s2 0 y1 , y2 s2
min min
f3(s3)= y12 y22 y32 { f 2 ( s 2 ) y32 } --------(6)
0 y3 s3 0 y 3 s3
To find the minimum value of f2(s2)
f2(s2)=y12+y22
f2(s2)=(s2-y2)2+y22 ( equation (3))
Differentiate with respect to 'y2' and assume equal to zero, we have
2(s2-y2)(0-1)+2y2=0
=>y2=s2/2 -------(7)
Sub the value of y2 in f2(s2), we have
f2(s2)= y12+y22= y12+( s2/2)2 (by equation (5))
f2(s2)= (s2-y2)2+( s2/2)2 (by equation (3))
f2(s2)= (s2- s2/2)2+( s2/2)2
f2(s2)= (s2/2)2+( s2/2)2=2s22/4
f2(s2)=s22/2. --------(8)
To find the minimum value of f3(s3)
f3(s3)=f2(s2)+y32 (by equation (3))
f3(s3)= s22/2+y32 (by equation (8))
f3(s3)= (s3-y3) 2/2+y32 (by equation (2))
Differentiate with respect to 'y3' and equate it to zero, we have
2(s3-y3) (0-1)/2+2y3=0
2(15-y3) (0-1)/2+2y3=0 (Sub s3=15, data in given problem)
(15-y3) (-1)+2y3=0
-15+y3+2y3=0
=>y3=5 --------(9)
Substitute y3 values in f3(s3)
f3(s3)= (15-5) 2/2+52=100/2+25=75
Optimal solution
Since s3=15
(2)=>s2=s3-y3=15-5=10 f2(s2)=s22/2=(10)2/2
(3)=>s1=s2-y2=10-5=5 (y2=s2/2)
(3)=>y1*=s1=5
(7)=>y2*=s2/2=10/2=5
(9)=>y3*=5
Hence the optimal policy is (5,5,5) with f 3*(15)=75.
Problem:-02
Use dynamic programming method to solve the following problem
Min Z=y12+y22+y32
Subject to the constraints
y1+y2+y3=10
and y1, y2, y3 0
Solution:-
Since there are three decision variables y1, y2, y3.
Therefore the given problem is 3 stage problem
Let s3= y1+y2+y3 ----------(1)
` s2= y1+y2 (=s3-y3) --------(2)
s1=y1 (=s2-y2) ---------(3)
The functional relation is given by
min
f1(s1)= y12 --------(4)
0 y1 s1
min min
f2(s2)= y12 y 22 { f 1 ( s1 ) y 22 } --------(5)
0 y2 s2 0 y2 s2
min min
f3(s3)= y12 y22 y32 { f 2 ( s 2 ) y32 } --------(6)
0 y3 s3 0 y 3 s3
To find the minimum value of f2(s2)
f2(s2)=y12+y22
f2(s2)=(s2-y2)2+y22 ( equation (3))
Differentiate with respect to 'y2' and assume equal to zero, we have
2(s2-y2)(1-0)+2y2=0
=>y2=s2/2 -------(7)
Sub the value of y2 in f2(s2), we have
f2(s2)= y12+y22= y12+( s2/2)2 (by equation (5))
f2(s2)= (s2-y2)2+( s2/2)2 (by equation (3))
f2(s2)= (s2- s2/2)2+( s2/2)2
f2(s2)= (s2/2)2+( s2/2)2=2s22/4
f2(s2)=s22/2. --------(8)
To find the minimum value of f3(s3)
f3(s3)=f2(s2)+y32 (by equation (3))
f3(s3)= s22/2+y32 (by equation (8))
f3(s3)= (s3-y3) 2/2+y32 (by equation (2))
Differentiate with respect to 'y3' and equate it to zero, we have
2(s3-y3) (0-1)/2+2y3=0
2(10-y3) (0-1)/2+2y3=0 (Sub s3=10, data in given problem)
(10-y3) (-1)+2y3=0
-10+y3+2y3=0
=>y3=10/3 --------(9)
Substitute y3 values in f3(s3)
f3(s3)= (10-10/3) 2/2+(10/3)2=(400/9)/2+100/9
f3(s3)=300/9=100/3
Optimal solution
Since s3=10
(2)=>s2=s3-y3=10-10/3=20/3
(3)=>s1=s2-y2=20/3-10/3=10/3 [y2=s2/2]
(3)=>y1*=s1=10/3
(7)=>y2*=s2/2=(20/3)/2=10/3
(9)=>y3*=10/3
Hence the optimal policy is (10/3, 10/3, 10/3) with f3*(10/3)=100/3.
EXCERCISE
1. Solve the following all integer programming problem using branch
and bound method,
Max Z=3x1+2.5x2,
Subject to the conditions
x1+2x2 20,
3x1+2x2 50
and x1, x2 0 and integers. [Ans. Sub problem D x1=14, x2=4 Z=52]
2. Solve the following all integer programming problem using branch
and bound method,
Max Z=3x1+5x2,
Subject to the conditions
2x1+4x2 25,
x1 8,
2x2 10
and x1, x2 0 and integers. [ Ans. Sub problem B x1=8, x2=2 Z=34]
3. Consider the linear programming problem
Max z=5x1+4x2
Subject to constraints
3x1+4x2 10
and x1,x2 0 integers.
(a) Solve this model using branch and bound method
(b) Demonstrate the solution partition graphically.
4. Solve the following linear programming problem using branch and
bound method.
Min Z=3x1+6x2
Subject to constraints
7x1+3x2 40
and x1,x2 0 and integers.
5. Solve the following linear programming problem using branch and
bound method
Max Z=100x1+150x2
Subject to constraints
8000x1+4000x2 40000
15x1+30x2 200
and x1,x2 0 and integers. [Ans. x1=1, x2=6 and Max Z=1000]
6. Solve the following LP problem using Gomory's cutting plane algorithm
Max Z=1.5x1+3x2+4x3
Subject to constraints
2.5x1+2x2+4x3 12
2x1+4x2-x3 7
and x1,x2, x3 0 and integers.
7.Solve the following LP problem using cutting plane algorithm
Max Z=2x1+3x2
Subject to constraints
x1+3x2 9
3x1+x2 7
x1-x2 1
and x1,x2 0 and integers.
8.Solve the following LP problem using cutting plane algorithm
Max Z=7x1+6x2
Subject to constraints
2x1+3x2 12
6x1+5x2 30
and x1,x2 0 and integers.
9.Solve the following LP problem using cutting plane algorithm
Max Z=5x1+4x2
Subject to constraints
x1+x2 2
5x1+3x2 15
3x1+5x2 15
and x1,x2 0 and integers.
10.Solve the following LP problem using cutting plane algorithm
Max Z=-3x1+x2+3x3
Subject to constraints
-x1+2x2+x3 4
2x1-1.5x3 1
x1-3x2 +2x3 3
and x1,x2 0 and x3 is non negative integer.
11.Solve the following LP problem using cutting plane algorithm
Max Z=x1+x2
Subject to constraints
2x1+5x2 16
6x1+5x2 30
and x2 0 and x1 is non negative integer.
12.Solve the following LP problem using cutting plane algorithm
Min Z=4x1+3x2+5x3
Subject to constraints
2x1-2x2+4x3 7
2x1+6x2-2x3 5
x1-3x2 +2x3 3
and x2 0 and x1 ,x3 are non negative integers.
13.Solve the following LP problem using cutting plane algorithm
Max Z=110x1+100x2
Subject to constraints
6x1+5x2 29
4x1+14x2 48
and x1,x2 0 and integers.
LECTURE NOTES
OPERATIONS RESEARCH
UNIT-II
LPP STANDARD FORM I
Max Z=CX
Subject to constraints
AX=b, and
X0
If the objective function is considered as one of the constraints
equation then the LP problem in its standard form is written by Z-CX=0 and
AX=b, X 0
Problem:-01
Use the revised simplex method to solve the following LP problem
Max z=3x1+5x2
Subject to
x1 4
x2 6
3x1+2x2 18
and x1,x2 0
Solution:-
The standard form I corresponding to the given problem is written
by
z-3x1-5x2=0 (Add objective function as constraint )
x1+s1=4 (Add slack variable s1 0)
x2+s2=6 (Add slack variable s2 0)
3x1+2x2+s3= 18 (Add slack variable s3 0)
and x1,x2, s1, s2, s3 0
Initial basic feasible solution is s1=4, s2=6, s3=18 and Max Z=0 (x1=0, x2=0)
0(1) 1(1) 2(1) 3(1) a1(1) a2(1)
Z s1 s2 s3 Ck-zk x1 x2
z=0 1 0 0 0 -3 -5
s1=4 0 1 0 0 1 0
s2=6 0 0 1 0 0 1
s3=18 0 0 0 1 3 2
3 5
1 0
Ck-zk=Max 1 0 0 0 =Max{-(-3,-5)}=Max{3,5}=5,
0 1
3 2
Corresponding to x2 ( k=2)
1 0 0 0 5 5
0 1 0 0 0 0
yk(1)=B(1)ak(1)=
0 0 1 0 1 1
0 0 0 1 2 2
x2 enters the basis
z s1 s2 s3 y2(1) Min
XB/yrj
z=0 1 0 0 0 -5 -
s1=4 0 1 0 0 0 -
s2=6 0 0 1 0 [1] 6
s3=18 0 0 0 1 2 9
s2 leaves the basis
First row values for new table
0-(-5)(6)/1=30, 1-(-5)(0)/1=1, 0-(-5)(0)/1=0,
0-(-5)(1)/1=5, 0-(0)(-5)/1=0
Second row values for new table
4-(0)(6)/1=4, 0-(0)(0)/1=0, 1-(0)(0)/1=1,
0-(0)(1)/1=0, 0-(0)(0)/1=0,
Third row values for new table
6/1, 0/1, 0/1, 1/1, 0/1
Fourth row values for new table
18-(6)(2)/1=6, 0-(0)(2)/1=0, 0-(0)(2)/1=0,
0-(1)(2)/1=-2, 1-(0)(2)/2=1
0(1) 1(1) 2(1) 3(1) a1(1) a3(1)
Z s1 x2 s3 Ck-zk x1 s2
z=30 1 0 5 0 -3 0
s1=4 0 1 0 0 1 0
x2=6 0 0 1 0 0 1
s3=6 0 0 -2 1 3 0
3 0
1 0
Ck-zk=Max 1 0 5 0 =Max{-(-3,5)}=Max{3,-5}=3,
0 1
3 0
Corresponding to x1 (k=1)
1 0 5 0 3 3
0 1 0 0 1 1
yk(1)=B(1)ak(1)=
0 0 1 0 0 0
0 0 2 1 3 3
x1 enters the basis
z s1 x2 s3 y1(1) Min XB/yrj
z=30 1 0 5 0 -3 -
s1=4 0 1 0 0 1 4
x2=6 0 0 1 0 0 -
s3=6 0 0 -2 1 [3] 2
s3 leaves the basis
First row for new table
30-(-3)(6)/3=36, 1-(0)(-3)/3=1, 0-(0)(-3)/3=0,
5-(-2)(-3)/3=3, 0-(1)(-3)/3=1
Second row for new table
4-(1)(6)/3=2, 0-(0)(1)=0, 1-(0)(1)/3=1,
0-(-2)(1)/3=2/3, 0-(1)(1)/3=-1/3
Third row for new table
6-(6)(0)/3=6, 0-(0)(0)/3=0, 0-(0)(0)/3=0,
1-(-2)(0)/3=1, 0-(1)(0)/3=0
Fourth row for new table
6/3=2, 0/3=0, 0/3=0, -2/3, 1/3, 3/3=1,
0(1) 1(1) 2(1) 3(1) a1(1) a3(1)
Z s1 x2 x1 Ck-zk s3 s2
z=36 1 0 3 1 0 0
s1=2 0 1 2/3 -1/3 0 0
x2=6 0 0 1 0 0 1
x1=2 0 0 -2/3 1/3 1 0
0 0
0 0
Ck-zk=Max 1 0 3 1 =Max{-(1,3)}=Max{-1,-3},
0 1
1 0
Since Ck-zk 0 for all k, therefore the above table is optimal table,
Hence the optimum solution is x1=2, x2=6 and Max Z=36
Problem:-02
Use the revised simplex method to solve the following LP problem
Max z=2x1+x2
Subject to
3x1+ 4x2 6
6x1+x2 3
and x1,x2 0
Solution:-
The standard form I corresponding to the given problem is written
by
z-2x1-x2=0 (Add objective function as constraint)
3x1+4x2+ s1=6 (Add slack variable s1 0)
6x1 +x2+s2=3 (Add slack variable s2 0)
and x1,x2, s1, s2 0
Initial basic feasible solution is s1=6, s2=3 and Max Z=0 (x1=0, x2=0)
0(1) 1(1) 2(1) a1(1) a2(1)
Z s1 s2 Ck-zk x1 x2
z=0 1 0 0 -2 -1
s1=6 0 1 0 3 4
s2=3 0 0 1 6 1
2 1
Ck-zk=Max 1 0 0 3 4 =Max{-(-2,-1)}=Max {2,1}=2,
6 1
Corresponding to x1 ( k=1)
1 0 0 2 2
yk(1)=B(1)ak(1)= 0 1 0 3 3
0 0 1 6 6
x1 enters the basis
z s1 s2 y1(1) Min
XB/yrj
z=0 1 0 0 -2 -
s1=6 0 1 0 3 2
s2=3 0 0 1 [6] 0.5
First row values for new table
0-(-2)(3)/6=1, 1-(-2)(0)/1=1, 0-(-2)(0)/1=0,
0-(-2)(1)/6=1/3,
Second row values for new table
6-(3)(3)/6=9/2, 0-(0)(3)/6=0, 1-(0)(3)/6=1,
0-(3)(1)/6=-1/2,
Third row values for new table
3/6, 0/6, 0/6, 6/6,
s2 leaves the basis
0(1) 1(1) 2(1) a1(1) a3(1)
Z s1 x1 Ck-zk s2 x2
z=1 1 0 1/3 0 -1
s1=9/2 0 1 -1/2 0 4
x1=3/6 0 0 1/6 1 1
0 1
Ck-zk=Max 1 0 1 / 3 0 4 =Max{-(1/3,-2/3)}=Max {-1/3,2/3}=2/3,
1 1
Corresponding to x2 ( k=2)
1 0 1 / 3 1 2 / 3
yk(1)=B(1)ak(1)= 0 1 1 / 2 4 7 / 2
0 0 1 / 6 1 1 / 6
x2 enters the basis
z s1 x1 y2(1) Min
XB/yrj
z=1 1 0 1/3 -2/3 -
s1=9/2 0 1 -1/2 [7/2] 9/7
x1=1/2 0 0 1/6 1/6 3
s1 leaves the basis
First row for new table
1-(-2/3)(9/2)/(7/2)=13/7, 1-(0)(-2/3)/(7/2)=1,
0-(1)(-2/3)/(7/2)=4/21, 1/3-(-2/3)(-1/2)/(7/2)=5/21
Second row for new table
(9/2)/(7/2)=9/7, 0/(7/2)=0, 1/(7/2)=2/7,
(-1/2)/(7/2)=-1/7, (7/2)/(7/2)=1
Third row for new table
1/2-(9/2)(1/6)/(7/2)=2/7, 0-(0)(1/6)/(7/2)=0,
0-(1)(1/6)/(7/2)=-1/21, 1/6-(-1/2)(1/6)/(7/2)=4/21
0(1) 1(1) 2(1) a1(1) a3(1)
Z x2 x1 Ck-zk s2 s1
z=13/7 1 4/21 5/21 0 0
x2=9/7 0 2/7 -1/7 0 1
x1=2/7 0 -1/21 4/21 1 0
0 0
Ck-zk=Max 1 4 / 21 5 / 21 0 1 Max{-(5/21,4/21)}=Max{-5/21,-4/21},
1 0
Since Ck-zk 0 for all k, therefore the above table is optimal table,
Hence the optimum solution is x1=2/7, x2=9/7 and Max Z=13/7.
Problem:-03
Use the revised simplex method to solve the following LP problem
Max z=x1+x2+3x3
Subject to
3x1+ 2x2+x3 3
2x1+x2+2x3 2
and x1,x2,x3 0
Solution:-
The standard form I corresponding to the given problem is written
by
z-x1-x2-3x3=0 (Add objective function as constraint)
3x1+ 2x2+x3+s1=3 (Add slack variable s1 0)
2x1+x2+2x3+s2=2 (Add slack variable s2 0)
and x1,x2,x3, s1, s2 0
Initial basic feasible solution is s1=3, s2=2 and Max Z=0 (x1=0, x2=0, x3=0)
0(1) 1(1) 2(1) a1(1) a2(1) a3(1)
Z s1 s2 Ck-zk x1 x2 x3
z=0 1 0 0 -1 -1 -3
s1=3 0 1 0 3 2 1
s2=2 0 0 1 2 1 2
1 1 3
Ck-zk=Max 1 0 0 3 2 1 =Max{-(-1,-1,-3)}=Max {1,1,3}=3,
2 1 2
Corresponding to x3 ( k=3)
1 0 0 3 3
yk(1)=B(1)ak(1)= 0 1 0 1 1
0 0 1 2 2
x3 enters the basis
Z s1 s2 y3(1) Min
XB/yrj
z=0 1 0 0 -3 -
s1=3 0 1 0 1 3
s2=2 0 0 1 [2] 1
First row values for new table
0-(2)(-3)/2=3, 1-(-3)(0)/2=1, 0-(-3)(0)/2=0,
0-(-3)(1)/2=3/2,
Second row values for new table
3-(1)(2)/2=2, 0-(0)(1)/2=0, 1-(0)(1)/2=1,
0-(1)(1)/2=-1/2,
Third row values for new table
2/2=1, 0/2=0, 0/2=0, 1/2,
s2 leaves the basis
0(1) 1(1) 2(1) a1(1) a3(1)
Z s1 x1 Ck-zk x1 x2 s2
z=3 1 0 3/2 -1 -1 0
s1=2 0 1 -1/2 3 2 0
x3=1 0 0 1/2 2 1 1
1 1 0
Ck-zk=Max 1 0 3 / 2 3 2 0 =Max{-(2, 1/2, 3/2)}
2 1 1
=Max {-2, -1/2, -3/2}
Since Ck-zk 0 for all k, therefore the above table is optimal table,
Hence the optimum solution is x1=0, x2=0, x3=1 and Max Z=3.
Problem:-04
Use the revised simplex method to solve the following LP problem
Max z=x1+2x2
Subject to
x1+x2 3
x1+2 x2 5
3x1+x2 6
and x1,x2 0
Solution:-
The standard form I corresponding to the given problem is written
by
z-x1-2x2=0 (Add objective function as constraint)
x1+x2+s1=3 (Add slack variable s1 0)
x1+2 x2+s2=5 (Add slack variable s2 0)
3x1+x2+s3= 6 (Add slack variable s3 0)
and x1,x2, s1, s2, s3 0
Initial basic feasible solution is s1=3, s2=5, s3=6 and Max Z=0 (x1=0, x2=0)
0(1) 1(1) 2(1) 3(1) a1(1) a2(1)
Z s1 s2 s3 Ck-zk x1 x2
z=0 1 0 0 0 -1 -2
s1=3 0 1 0 0 1 1
s2=5 0 0 1 0 1 2
s3=6 0 0 0 1 3 1
1 2
1 1
Ck-zk=Max 1 0 0 0 =Max{-(-1,-2)}=Max{1,2}=2,
1 2
3 1
Corresponding to x2 ( k=2)
1 0 0 0 2 2
0 1 0 0 1 1
yk(1)=B(1)ak(1)=
0 0 1 0 2 2
0 0 0 1 1 1
x2 enters the basis
z s1 s2 s3 y2(1) Min
XB/yrj
z=0 1 0 0 0 -2
s1=3 0 1 0 0 1 3
s2=5 0 0 1 0 [2] 5/2
s3=6 0 0 0 1 1 6
s2 leaves the basis
First row values for new table
0-(5)(-2)/2=5, 1-(-2)(0)/2=1, 0-(-2)(0)/2=0,
0-(-2)(1)/2=1, 0-(0)(-2)/2=0
Second row values for new table
3-(1)(5)/2=1/2, 0-(1)(0)/2=0, 1-(0)(1)/2=1,
0-(1)(1)/2=-1/2, 0-(0)(1)/2=0,
Third row values for new table
5/2, 0/2=0, 0/2=0, 1/2, 0/2=0
Fourth row values for new table
6-(5)(1)/2=7/2, 0-(0)(1)/2=0, 0-(0)(1)/2=0,
0-(1)(1)/2=-1/2, 1-(0)(1)/2=1
0(1) 1(1) 2(1) 3(1) a1(1) a3(1)
Z s1 x2 s3 Ck-zk x1 s2
z=5 1 0 1 0 -1 0
s1=1/2 0 1 -1/2 0 1 0
x2=5/2 0 0 1/2 0 1 1
s3=7/2 0 0 -1/2 1 3 0
1 0
1 0
Ck-zk=Max 1 0 1 0 =Max{-(0,1)}=Max{-1}
1 1
3 0
Since Ck-zk 0 for all k, therefore the above table is optimal table,
Hence the optimum solution is x1=0, x2=5/2 and Max Z=5.
Procedure
Step:-01
Verify whether all variables has 0 lower bound, if not suppose xk
has a positive lower bound, then make its lower bound zero using
substitution xk'=xk-LB, where LB is lower bound of xk. Update xk' where
ever we have xk by using the substitution.
Step:-02
The objective function is should be maximisation type , otherwise
change the given minimisation problem into maximisation type problem.
Step:-03
Solve using usual simplex method, add upper bound (ur) of
variables (0 xr u r ) on the top of the simplex table, for slack or surplus
variables upper bound is not defined, therefore it is assumed to be infinity
. If the current solution is not optimal proceed to step 4. F
Step:-04
Find the initial basic feasible solution, then select a non-basic
variable to enter (using simple procedure) and the basic variable to leave
(using the following procedure)
X
1 min Bi , if y ir 0
yir
Here yir are the values in the rth column which is going to enter into
the basis.
u X Bi
2 min r , if y ir 0
y ir
Here ur is the upper bound value of the rth column which is going to
enter into the basis.
min 1 , 2 , u 3 , Go to Step 05
Step:-05
(i) If 1 then corresponding basic variable is removed from the basis.
Select the basic variable to leave the basis and apply usual simplex
algorithm to get new updated table. Go to Step 06.
(ii) If 2 then corresponding basic variable is removed from basis,
Select the basic variable to leave the basis and apply usual simplex
algorithm to get new updated table. Go to Step 06.
The following changes to be done in the updated table
(a) Change of leaving basic variables column values
We have to put of leaving basic variable xr at its upper bound use
the equation xr=ur-xr', 0 xr' ur. where xr' is new variable to be written in
place of xr, and multiply the xr' column values by -1, because the coefficient
of xr' is negative in the substitution.
(b) Y=XB column
(xBK)r=(xBk)'-ykrur,
Here (xBk)' is the old table value and (xBk) is the new table value.
Write the updated table. Go to Step 06.
(iii)If u r then variable xr is not leaving the basis, but given its upper
bound value is calculated as xr=ur-xr', 0 xr' ur
The new updated table is same as old one, but with the following
two column changes
(a) xr Column
Replace xr by xr', and multiply the xr' column values by -1, because
the coefficient of xr' is negative in the substitution.
(b) Y=XB column
(xBK)r=(xBk)'-ykrur,
Here (xBk)' is the old table value and (xBk) is the new table value.
Write the updated table. Go to Step 06.
Step:-06
After getting updated table, if it is optimal then stop calculation,
otherwise use step:-04 for new table.
Bounded Variable Method
Problem:-01
Use bounded variable method to solve the following LP problem
Max z=x2+3x3
Subject to
x1+x2+x3 10
x1-2 x3 0
2x1-x3 10
and0 x1 8 , 0 x2 4 , x3 0
Solution:-
The standard form of given LP problem is
Max z= x2+3x3+0s1+0s2+0s3
x1+x2+x3+s1= 10 (Add slack variable s1 0)
-x1+2 x2+s2=0 (Add slack variable s2 0)(x by -1 )
2x1-x3+s3=10 (Add slack variable s3 0)
and 0 x1 8 , 0 x2 4, 0 x3 , 0 s1 , 0 s2 , 0 s3
Initial basic feasible solution is s1=10, s2=0, s3=10, x1=0, x2=0, x3=0 and
Max z=0
uj 8 4
cj 0 1 3 0 0 0
CB XB x1 x2 x3 s1 s2 s3
0 s1=10 1 1 1 1 0 0
0 s2=0 -1 0 [2] 0 1 0
0 s3=10 2 0 -1 0 0 1
zj 0 0 0 0 0 0
zj-cj 0 -1 -3 0 0 0
Since some zj-cj are negative, therefore the above table is not optimal.
x3 enters the basis
To find the variable leaves the basis
X
1 min Bi , if y ir 0 [ yir are the selected column values]
yir
10 0
1 min ,
1 2
1 0 [ corresponding to the variable s2]
u X Bi
2 min r , if yir 0
yir
u X B3 10
2 min 3 min [ corresponding to the variable x3]
y33 (1)
min 1 , 2 , u 3 min 0, , 0 [ corresponding to the variable s2]
0 1 [ corresponding to the variable s2]
[Rule :-
If 1 then corresponding basic variable is removed from the
basis. Select the basic variable to leave the basis and apply usual
simplex algorithm to get new updated table. Go to Step 06.]
s2 leave the basis
First row values
10-(0)(1)/2=10 1-(-1)(1)/2=3/2 1-(0)(1)/2=1
1-(0)(1)/2=1 0-(1)(1)/2=-1/2 0-(0)(1)/2=0
Second row values
0/2=0 -1/2 0/2=0 2/2=1 0/2=0 1/2 0/2=0
Third row values
10-(0)(-1)/2=10 2-(-1)(-1)/2=3/2 0-(0)(-1)/2=0
0-(0)(-1)/2=0 0-(1)(-1)/2=1/2 1-(0)(-1)/2=1
uj 8 4
cj 0 1 3 0 0 0
CB Y=XB x1 x2 x3 s1 s2 s3
0 s1=10 [3/2] 1 0 1 -1/2 0
-3 x3=0 -1/2 0 1 0 1/2 0
0 s3=10 3/2 0 0 0 1/2 1
zj -3/2 0 3 0 3/2 0
zj-cj -3/2 -1 0 0 3/2 0
Since some zj-cj are negative, therefore the above table is not optimal.
x1 enters the basis
To find the variable leaves the basis
X
1 min Bi , if y ir 0 [ yir are the values of selected column]
yir
20 20
1 min ,
3 3
1 20 / 3 [ corresponding to the variable s1, s3]
u X Bi
2 min r , if y ir 0
y ir
u X B1 80
2 min 1 min 16 [ corresponding to the variable x3]
y 21 (1 / 2)
min1 , 2 , u1 min20 / 3, 16, 8 20 / 3 [ corresponding to variables s1, s3]
20 / 3 1
[Rule :-
If 1 then corresponding basic variable is removed from the
basis. Select the basic variable to leave the basis and apply usual
simplex algorithm to get new updated table. Go to Step 06.]
s1 leaves the basis
First row values
10/(3/2)=20/3 (3/2)/(3/2)=1 1/(3/2)=2/3 0/(3/2)=0
1/(3/2)=2/3 (-1/2)/(3/2)=-1/3 0/(2/3)=0
Second row values
0-(10)(-1/2)/(3/2)=10/3 0-(1)(-1/2)/(3/2)=1/3 1-(0)(-1/2)/(3/2)=1
0-(1)(-1/2)(3/2)=1/3 1/2-(-1/2)(-1/2)(3/2)=1/3 0-(0)(-1/2)/(3/2)=0
Third row values
10-(10)(3/2)/(3/2)=0 0-(1)(3/2)/(3/2)=-1 0-(0)(3/2)/(3/2)=0
0-(1)(3/2)/(3/2)=-1 1/2-(-1/2)(3/2)/(3/2)=1 1-(0)(3/2)/(3/2)=1
uj 8 4
cj 0 1 3 0 0 0
CB XB x1 x2 x3 s1 s2 s3
0 x1=20/3 1 2/3 0 2/3 -1/3 0
-3 x3=10/3 0 1/3 1 1/3 1/3 0
0 s3=0 0 -1 0 -1 1 1
zj 0 1 3 1 1 0
zj-cj 0 0 0 1 1 0
Since all zj-cj 0 , therefore the above table is optimal.
Hence the optimal solution is x1=0, x2=0 , x3=10/3 and Max z=10
Problem:-02
Use bounded variable method to solve the following LP problem
Max z=x1+3 x2-2x3
Subject to
x2-2x3 1
2x1+ x2+2x3 8
and 0 x1 1 , 0 x2 3 , 0 x3 2
Solution:-
The standard form of given LP problem is
Max z= x1+3 x2-2x3+0s1+0s2+0s3
x2-2x3+s1= 1 (Add slack variable s1 0)
2x1+ x2+2x3 +s2=8 (Add slack variable s2 0)
and 0 x1 1 , 0 x2 3, 0 x3 2, 0 s1 , 0 s2 .
Initial basic feasible solution is s1=1, s2=8, x1=0, x2=0, x3=0 and
Max z=0
uj 1 3 2
cj 1 3 -2 0 0
CB XB x1 x2 x3 s1 s2
0 s1=1 0 [1] -2 1 0
0 s2=8 2 1 2 0 1
zj 0 0 0 0 0
zj-cj -1 -3 2 0 0
Since some zj-cj are negative, therefore the above table is not optimal.
x2 enters the basis
To find the variable leaves the basis
X
1 min Bi , if yir 0
yir
1 min1,8 1 [ corresponding to the variable s1]
u X Bi
2 min r , if y ir 0
y ir
2
min 1 , 2 , u2 min 1, ,3 1 [ corresponding to the variable s1]
1 1
[Rule :-
If 1 then corresponding basic variable is removed from the
basis. Select the basic variable to leave the basis and apply usual
simplex algorithm to get new updated table. Go to Step 06.]
s1 leave the basis
First row values
1/1=1 0/1=0 1/1=1 -2/1=-2 1/1=1 0/1=0
Second row values
8-(1)(1)/1=7 2-(0)(1)/1=2 2-(-2)(1)/1=4 0-(1)(1)/1=-1
1-(1)(0)/1=1
uj 1 3 2
cj 1 3 -2 0 0
CB XB x1 x2 x3 s1 s2
3 x2=1 0 1 [-2] 1 0
0 s2=7 2 0 4 -1 1
zj 0 3 -6 3 0
zj-cj -1 0 -4 3 0
Since some zj-cj are negative, therefore the above table is not optimal.
x3 enters the basis
To find the variable leaves the basis
X
1 min Bi , if yir 0
yir
7
1 min 7 / 4 [ corresponding to the variable s2]
4
u X Bi
2 min i , if a ir 0
a ir
u X B1 2 1
2 min 3 min min{1 / 2} 1 / 2
y13 (2)
[ corresponding to the variable x2]
min1 , 2 , u3 min7 / 4, 1 / 2, 2 1 / 2
1/ 2 2 [ corresponding to the variable x2]
x2 leaves the basis
[ If 2 then corresponding basic variable is removed from basis,
Select the basic variable to leave the basis and apply usual simplex
algorithm to get new updated table.
The following changes to be done in the updated table
(a) Change of leaving basic variables column values
We have to put of leaving basic variable xr at its upper bound
use the equation xr=ur-xr', 0 xr' ur. where xr' is new variable to be
written in place of xr, and multiply the xr' column values by -1, because
the coefficient of xr' is negative in the substitution.
(b) Y=XB column
(xBK)r=(xBk)'-ykrur,
Here (xBk)' is the old table value and (xBk) is the new table
value. ]
First row values
1/(-2)=-1/2 0/(-2)=0 1/(-2)=-1/2 (-2)/(-2)=1
1/(-2)=-1/2 0/(-2)=0
Second row values
7-(1)(4)/(-2)=9 2-(0)(4)/(-2)=2 0-(1)(4)/(-2)=2 0 -1-(4)(1)/(-2)=1
1-(0)(4)/(-2)=1
uj 1 3 2
cj 1 3 -2 0 0
CB XB x1 x2 x3 s1 s2
-2 x3=-1/2 0 -1/2 1 -1/2 0
0 s2=9 2 2 0 1 1
(z0=1) 0 1 -2 1 0
zj
zj-cj -1 -2 0 1 0
The following must updated in the above table
Let x2=u2-x2'=3-x2', then
0 x2 3
0 3 x2 ' 3
0 3 3 x2 '3 3 3 (subtract 3)
3 x2 ' 0
3 x2 ' 0 (x by -1)
i.e 0 x2 ' 3
We know that
xBk=xBk'-akrur
xB1=xB1'-y12u2=-1/2-(-1/2)(3)=1
xB2=xB2'-y22u2=9-(2)(3)=3
z0=z0'-(z2-c2)u2=1-(-2)(3)=7
uj 1 3 2
cj 1 -3 -2 0 0
CB XB x1 x2' x3 s1 s2
-2 x3=1 0 1/2 1 -1/2 0
0 s2=3 2 -2 0 1 1
(z0=7) 0 -1 -2 1 0
zj
zj-cj -1 +2 0 1 0
x1 enters the basis
To find the basic variable leaves the basis
X
1 min Bi , if yir 0
yir
1 min 3 / 2 1.5 [ corresponding to the variable s2]
u X Bi
2 min i , if yir 0
yir
2
min1 , 2 , u1 min1.5, , 1 1
1 u1
Rule:-
If ur then variable xr is not leaving the basis, but its upper
bound value is calculated as xr=ur-xr', 0 xr' ur
The new updated table is same as old one, but with the following
two column changes
(a) xr Column
Replace xr by xr', and multiply the xr' column values by -1, because
the coefficient of xr' is negative in the substitution.
(b) Y=XB column
(xBK)r=(xBk)'-ykrur,
Here (xBk)' is the old table value and (xBk) is the new table value.]
Let x1=u1-x1'=1-x1', then
0 x1 1
0 1 x1 ' 1
0 1 1 x1 '1 1 1 (subtract 1)
1 x1 ' 0
1 x1 ' 0 (x by -1)
i.e 0 x1 ' 1
We know that
xBk=xBk-akrur
xB1=xB1-y11u1=1-(0)(1)=1
xB2=xB2-y21u1=3-(2)(1)=1
z0=z0'-(z1-c1)u1=7-(-1)(1)=8
uj 1 3 2
cj -1 -3 -2 0 0
CB XB x1' x2' x3 s1 s2
-2 x3=1 0 1/2 1 -1/2 0
0 s2=1 -2 2 0 1 1
(z0=8) 0 -1 -2 1 0
zj
zj-cj 1 2 0 1 0
Since all zj-cj 0, therefore the above table is optimal
x1'=0
1-x1=0 [since x1=1-x1']
i.e x1=1
x2'=0 [since x2=3-x2']
3-x2=0
i.e x2=3
x3=1
Hence the optimal solution is x1=1, x2=3, x3=1 and
Max z=1(1)+3(3)-2(1)=8
Problem:-03
Use upper bound algorithm to solve
Max z=3x1+5x2+2x3
Subject to
x1+x2+2x3 14
2x1+4x2+3x3 34
and 0 x1 4 , 0 x2 10 , 0 x3 3
Solution:-
The standard form of given LP problem is
Max z= 3x1+5 x2+2x3+0s1+0s2+0s3
x1+x2+2x3+s1= 1 (Add slack variable s1 0)
2x1+4x2+3x3+s2=8 (Add slack variable s2 0)
and 0 x1 4 , 0 x2 10, 0 x3 3, 0 s1 , 0 s2 .
Initial basic feasible solution is s1=14, s2=34, x1=0, x2=0, x3=0 and
Max z=0
uj 4 10 3
cj 3 5 2 0 0
CB XB x1 x2 x3 s1 s2
0 s1=14 1 1 2 1 0
0 s2=34 2 [4] 3 0 1
zj 0 0 0 0 0
zj-cj -3 -5 -2 0 0
Since some zj-cj are negative, therefore the above table is not optimal.
x2 enters the basis
To find the variable leaves the basis
X
1 min Bi , if yir 0
yir
1 min14 / 1, 34 / 4 34 / 4 8.5 [ corresponding to the variable s2]
u X Bi
2 min r , if y ir 0
y ir
2
min1 , 2 , u2 min8.5, ,10 8.5
8.5 1 [ corresponding to the variable s2]
[Rule :-
If 1 then corresponding basic variable is removed from the
basis. Select the basic variable to leave the basis and apply usual
simplex algorithm to get new updated table. Go to Step 06.]
s2 leave the basis
First row values
14-(34)(1)/4=11/2 1-(2)(1)/4=1/2 2-(3)(1)/4=5/4
1-(0)(1)/4=1 0-(1)(1)/4=-1/4
Second row values
34/4=17/2 2/4=1/2 4/4=1 3/4 0/4=0 1/4
uj 4 10 3
cj 3 5 2 0 0
CB XB x1 x2 x3 s1 s2
3 s1=11/2 1/2 0 5/4 1 -1/4
0 x2=17/2 1/2 1 3/4 0 1/4
zj 5/2 5 15/4 0 5/4
zj-cj -1/2 0 7/4 0 5/4
Since some zj-cj are negative, therefore the above table is not optimal.
x1 enters the basis
To find the variable leaves the basis
X
1 min Bi , if yir 0
yir
1 min(11/ 2) /(1 / 2), (17 / 2) /(1/ 2) min{11, 17} 11
[corresponding to the variable s1]
u X Bi
2 min i , if y ir 0
y ir
2
min1 , 2 , u1 min11, , 4 4
4 u1 [corresponding to the variable x1]
Rule:-
If ur then variable xr is not leaving the basis, but its upper
bound value is calculated as xr=ur-xr', 0 xr' ur
The new updated table is same as old one, but with the following
two column changes
(a) xr Column
Replace xr by xr', and multiply the xr' column values by -1, because
the coefficient of xr' is negative in the substitution.
(b) Y=XB column
(xBK)r=(xBk)'-ykrur,
Here (xBk)' is the old table value and (xBk) is the new table value.]
Let x1=u1-x1'=4-x1', then
0 4 x1 ' 4
0 4 x1 ' 4
0 4 4 x1 '4 4 4 (subtract 4)
4 x1 ' 0
4 x1 ' 0 (x by -1)
i.e 0 x1 ' 4
We know that
xBk=x'Bk-akrur
xB1=xB1'-y11u1=11/2-(1/2)(4)=7/2
xB2=xB2'-y21u1=17/2-(1/2)(4)=13/2
z0=z0'-(z1-c1)u1=85/2-(-1/2)(4)=89/2
uj 4 10 3
cj -3 5 2 0 0
CB XB x1' x2 x3 s1 s2
0 s1=7/2 -1/2 0 5/4 1 -1/4
5 x2=13/2 -1/2 1 3/4 0 1/4
zj 5/2 5 15/4 0 5/4
zj-cj 1/2 0 7/4 0 5/4
Since all zj-cj 0, therefore the above table is optimal
x1'=0,
4-x1=0 [since x1=4-x1']
x1=4,
Hence the optimal solution is given by
x1=4, x2=13/2, x3=0 and Max z=3(4)+5(13/2)+2(0)=89/2.
Problem:-04
Use upper bound algorithm to solve
Max z=4x1+2x2+6x3
Subject to
4x1-x2 9
-x1+x2+2x3 8
-3x1+x2+4x3 12
and 1 x1 3 , 0 x2 5 , 0 x3 2
Solution:-
Since x1 has positive lower bound
1 x1 3
0 x1-1 3-1 (Subtract 1)
0 x1' 2, where x1'=x1-1
Sub x1=x1'+1 in the given problem
The new updated problem is given by
Max z=4x1+2x2+6x3
=4(x1'+1)+2x2+6x3
=4x1'+2x2+6x3+4
Subject to
4(x1'+1)-x2 9 4x1'+4-x2 9 4x1'-x2 5
-(x1'+1)+x2+2x3 8 -x1'-1+x2+2x3 8 -x1'+x2+2x3 9
-3(x1'+1)+x2+4x3 12 -3x1'-3+x2+4x3 12 -3x1'+x2+4x3 15
and 1 x1'+1 3 1-1 x1'+1-1 3-1 0 x1' 2
0 x2 5 , 0 x3 2
Apply simplex algorithm
Max z=4x1'+2x2+6x3+4+0s1+0s2+0s3
Subject to
4x1'-x2+s1=5 (add slack variable s1 0)
-x1'+x2+2x3+s2 =9 (add slack variable s2 0)
-3x1'+x2+4x3+s3=15 (add slack variable s3 0)
and 0 x1' 2 0 x2 5 , 0 x3 2, 0 s1 , 0 s2 0 s3 .
The initial basic feasible solution is given by
s1=5, s2=9,s3=15, x1'=0, x2=0, x3=0 and Max z=4(0)+2(0)+6(0)+4=4
uj 2 5 2
cj 4 2 6 0 0 0
CB XB x1' x2 x3 s1 s2 s3
0 s1=5 4 -1 0 1 0 0
0 s2=9 -1 1 2 0 1 0
0 s3=15 -3 1 4 0 0 1
zj 0 0 0 0 0 0
zj-cj -4 -2 -6 0 0 0
Since some zj-cj are negative, therefore the above table is not optimal.
x3 enters the basis
To find variable leaves the basis
X
1 min Bi , if yir 0
yir
1 min9 / 2,15 / 4 15 / 4 [ corresponding to the variable s3]
u X Bi
2 min i , if a ir 0
a ir
2
min1 , 2 , u3 min15 / 4, , 2 2
2 u3 [ corresponding to the variable x3]
Rule:-
If ur then variable xr is not leaving the basis, but its upper
bound value is calculated as xr=ur-xr', 0 xr' ur
The new updated table is same as old one, but with the following
two column changes
(a) xr Column
Replace xr by xr', and multiply the xr' column values by -1, because
the coefficient of xr' is negative in the substitution.
(b) Y=XB column
(xBK)r=(xBk)'-ykrur,
Here (xBk)' is the old table value and (xBk) is the new table value.]
Let x3=u3-x3'=2-x3', then
0 2-x3' 2,
0 2 2 x3 '2 2 2 (subtract 2)
2 x3 ' 0
2 x3 ' 0 (x by -1)
i.e 0 x3 ' 2
We know that
xBk=x'Bk-akrur
xB1=x'B1-y31u3=5-(0)(2)=5
xB2=xB2-y32u3=9-(2)(2)=5
xB3=xB3-y33u3=15-(4)(2)=7
z0=z0'-(z3-c3)u3=4-(-6)(2)=16.
uj 2 5 2
cj 4 2 -6 0 0 0
CB XB x1' x2 x3' s1 s2 s3
0 s1=5 [4] -1 0 1 0 0
0 s2=5 -1 1 -2 0 1 0
0 s3=7 -3 1 -4 0 0 1
zj 0 0 0 0 0 0
zj-cj -4 -2 6 0 0 0
x1' enters the basis
To find variable leaves the basis
X
1 min Bi , if yir 0
yir
1 min5 / 4 5 / 4 [ corresponding to the variable s1]
u X Bi
2 min i , if y ir 0
y ir
u X B1 u1 X B1 25 27
2 min 1 , min{ , } min{3,5 / 3}
y 21 y 31 ( 1) ( 3)
min1 , 2 , u1 min5 / 4, , 2 5 / 4
5 / 4 1 [ corresponding to the variable s1]
s1 leaves the basis
[Rule :-
If 1 then corresponding basic variable is removed from the
basis. Select the basic variable to leave the basis and apply usual
simplex algorithm to get new updated table. Go to Step 06.]
First row values
5/4 4/4=1 -1/4 0/4=0 1/4 0/4=0 0/4=0
Second row values
5-(5)(-1)/4=25/4 1-(-1)(-1)/4=3/4 -2-(0)(-1)/4=-2
0-(1)(-1)/4=1/4 1-(0)(-1)/4=1 0-(0)(-1)/4=0
Third row values
7-(5)(-3)/4=43/4 1-(-1)(-3)/4=1/4 -4-(0)(-3)/4=-4
0-(1)(-3)/4=3/4 0-(0)(-3)/4=0 1-(0)(-3)/4=1
uj 2 5 2
cj 4 2 -6 0 0 0
CB XB x1' x2 x3' s1 s2 s3
4 x1'=5/4 1 [-1/4] 0 1/4 0 0
0 s2=25/4 0 3/4 -2 1/4 1 0
0 s3=43/4 0 1/4 -4 3/4 0 1
zj 4 -1 0 1 0 0
zj-cj 0 -3 6 1 0 0
x2 enters the basis
To find variable leaves the basis
X
1 min Bi , if yir 0
yir
1 min(25 / 4)/ (3/4), (43/4)/(1/4) min{25 / 3, 43} 25 / 3
[ corresponding to the variable s2]
u X Bi
2 min r , if yir 0
y ir
u X Bi
2 min 2 , if y i 2 0
yi 2
5 5/ 4 15 / 4
2 min min 15 [ corresponding to the variable x1']
(1 / 4) 1/ 4
min1 , 2 , u2 min25 / 3, 15, 5 5
5 u2 [ corresponding to the variable x2]
Rule:-
If ur then variable xr is not leaving the basis, but its upper
bound value is calculated as xr=ur-xr', 0 xr' ur
The new updated table is same as old one, but with the following
two column changes
(a) xr Column
Replace xr by xr', and multiply the xr' column values by -1, because
the coefficient of xr' is negative in the substitution.
(b) Y=XB column
(xBK)r=(xBk)'-ykrur,
Here (xBk)' is the old table value and (xBk) is the new table value.]
Let x2=u2-x2'=5-x2', then
0 5-x2' 5,
0 5 5 x2 '5 5 5 (subtract 5)
5 x2 ' 0
5 x2 ' 0 (x by -1)
i.e 0 x2 ' 5
We know that
xBk=x'Bk-akrur
xB1=x'B1-y12u2=5/4-(-1/4)(5)=5/2
xB2=xB2-y22u2=25/4-(3/4)(5)=10
xB3=xB3-y32u2=43/4-(1/4)(5)=19/2
uj 2 5 2
cj 4 -2 -6 0 0 0
CB XB x1' x2' x3' s1 s2 s3
4 x1'=5/2 1 1/4 0 1/4 0 0
0 s2=10 0 -3/4 -2 1/4 1 0
0 s3=19/2 0 -1/4 -4 3/4 0 1
zj 4 1 0 1 0 0
zj-cj 0 3 6 1 0 0
Since zj-cj 0 , therefore the above table is optimal.
Hence the optimal solution is x1'=5/2, x2'=0, x3'=0
x1'=5/2
x1-1=5/2 [ since x1'=x1-1]
x1=7/2
x2'=0
5-x2=0 [since x2=5-x2']
x2=5
x3'=0
2-x3=0 [since x3=2-x3']
x3=2
i.e x1=7/2,x2=5, x3=2 and Max z=4(7/2)+2(5)+6(2)=36
Exercise
Solve the following LP problems
1. Max z=3x1+2x2
Subject to constraints
x1-3x2 3, x1-2x2 4, 2x1+x2 20, x1+3x2 30 , -x1+x2 6
and 0 x1 8; 0 x2 6. Ans. x1=7, x2=6, max z=33.
2. Max z=3x1+5x2+2x3
Subject to constraints
x1+2x2+2x3 14, 2x1+4x2+3x3 23
and 0 x1 4; 2 x2 5, 0 x3 3. Ans. x1=0, x2=15/4, max z=123/4.
3. Max z=2x1+x2
Subject to constraints
x1+2x2 10, x1+x2 6, x1-x2 2, x1-2x2 1
and 0 x1 3; 0 x2 2. Ans. x1=3, x2=2, max z=8.
4. Max z=4x1+4x2+3x3
Subject to constraints
-x1+2x2+3x3 15, -x2+x3 4, 2x1+x2-x3 6, x1-x2+2x3 10
and 0 x1 8; 0 x2 4, 0 x3 4. Ans. x1=17/5, x2=16/5, x3=4
max z=192/5.
5. Min z=x1+2x2+3x3-x4
Subject to constraints
x1-x2+x3-2x4 6, -x1+ x2-x3+x4 8, 2x1+x2-x3 2
and 0 x1 3; 1 x2 4, 0 x3 10, 2 x4 5
Ans. x1=17/5, x2=16/5, x3=4 max z=192/5.
UNIT-III
Inventory control
The word inventory refers to any kind of resources having economic
value and is maintained to full fill the present and further needs of the
organisation.
Fred hansman inventory as an ideal resources of any kind provided such
a resource has economic.
Resources
Resources may be classified into three categories.
(i) physical resources such as raw material, semi-finish goods, finished goods,
Spare part, lubricant etc...
(ii) Human resources such as un-used labour
(iii) Financial resource such as working capital etc..
Example
Types of organisation Type of inventory held
Manufacture Raw material, spare parts,semi-
finished goods,finished good etc...
Hospital No. Of beds, stock of drugs,specialised
doctor etc...
Bank Cash reserve etc..
Air line company Seating capacity spare parts etc..
Use of inventory
It is essential to balance the advantage of having inventory of resources
and the cost of maintain it so as to determine an optimal level of inventory of
each resources so that the total inventory cost is minimum.
Inventory models
The model of inventory are classified into two catogeries.
(i) deterministic model
(ii) probability model
Deterministic model
Deterministic model deals with constant rate of demand and lead time
situation to decided ordering quantity (EOQ) so that total cost of ordering (cp),
Inventory holding cost (ch) and shortage cost(cs) is at its minimum.
Probability model
Probabilistic model deals with though situation to determine EOQ in
which demand/lead time is probabilistic .
Relevant cost
The cost that are affected (i.e, increase or decrease) by the company
decision to maintain particular level of inventory are called relevant cost.
Purchase cost
This cost consists of the actual price paid for the procurement cost
(i) when the unit price (c)of an item is independent of the size of the quantity
order or purchased.
Purchased cost = (price/unit)*(demand/unit time)
C =C.D
(ii) when price break or quantity discounts are available for bulk purchase above
a specified quantity, the unit price become smaller as size of order quantity
exceeds the specified level.
In this case the purchase cost become variable and depends on the size of
the order.
Purchase cost=(price/unit when order size is q)* (demand per unit time)
=c(Q).D
Carrying or holding cost
The carrying cost is associated with carrying or holding inventory
(i) carrying cost=(cost of carrying 1 units of an item in the inventory for a given
length of time ) * (average number of units of an item carrying in the inventory
for a given length of time).
(ii) carrying cost = (cost to carry one rupee worth of inventory per time period)*
(rupees value of unit carried)
Note
carrying cost includes
(i) storage cost for providing ware house.
(ii) inventory holding cost for payment of salaries to employees.
(iii) Insurance cost against possible loss from fire or other form of damage etc.
Ordering cost(setup cost)
Ordering cost incurred each time an order is placed for procuring items
from outside suppliers.
When an item is produced internally ordering cost is reffered as setup
cost which includes both paper cost and physical preparation cost.
Ordering cost =(cost per order)*(number of orders in the inventory planning
period).
Setup cost= (cost per setup)*( no of setup in the planning periods)
Note
Ordering cost includes
(i) requisition cost of handling invoice, stationary, papers, etc..
(ii) cost of services like mailing, telephone calls etc..
Shortage or stock out cost
Shortage of items occur when item cannot be supplied o demand.
(i) the supply of items is awaited by the customers
i.e, the items are back ordered and therefore there is no loss in sale.
In this case it is very difficult to determine the nature and magnitude of the back
ordering cost.
The situation may lead to loss of good will.
(ii) customers are not ready to will therefore there the loss of sale.
In this case shortage cost shall be measured in terms of good eill loss
Shortage cost=(cost of being short one unit in the inventory)*(average no of
units short in the inventory)
mininventory
maxinventory *
Average number if unit short= (time for
3
which shortage occurs)
Total inventory cost= purchase cost + ordering cost + carrying cost+ shortage
cost
When the purchase cost remains constant and is independent of the quantity of
purchase.
Total variable inventory cost(TVC) = ordering cost + carrying cost + shortage
cost
1) optimal length if inventory replenishment cycle time (t*), optimal interval
between the successive orders.
Q* = annual demand * reorder cycle time
=D.t
Or
Q* 1 2 DC 0 2C 0
t* =
D D Ch DC h
2) optimal number of orders (N*) to the placed in the given time period
(assumed as one year)
D 1 DC h
N* D =
Q* 2 DC 0 2C 0
C1
3) optimum (minimum) total variable inventory cost( TVC*)
D Q* 1 Ch 2 DC 0
C0 C h D .C 0 * *
Q* 2 2 DC 0 2 Ch
TVC*=
Ch
= 2 DC 0 C h
4) optimal total inventory cost is the seem of variable cost and fixed cost.
TC=DC+TVC*
Alternative formulas:
TVC= 2* reorder cost component
=2*holding cost component
2 DC 0
TVC= *
Q* * Ch
Q
Carrying cost = inventory carrying rate * unit cost of item
=r*C
Demand in units= rupee value of demand / unit cost of the item
If unit cost of item is not known then EOQ in rupee terms is expressed as
2 * annualdema ndinrupee
Q *=
inventoryc arrying cos t
2 * C .D * C 0
=
r *C
Lead time
Elapsed time between the placement of order and its receipt in the
inventory is known as lead time.
Reorder time
This is the time when we should place an order by taking into
consideration the interval between placing the order and receiving the supply.
Example
We like to place a new order precisely at the time when the inventory
level reaches zero.
Economic order quantity(EOQ)
Economic order quantity is the size of order which minimize the total
inventory cost of carrying inventory and the ordering cost.
Under the assumed conditions of certainty and the annual demand are
known.
Problem
The production department for a company requires 3600 kg of raw
material for manufacturing a particular item for a year it has been estimated
that the cost of placing an order is rs36 and cost of carrying inventory is 25% of
the investment in the inventory. The price is rs 10/kg. The purchase manager
wishes to determine an ordering policy for raw material.
Solution
D=3600 kg/year
C0 = Rs36 /order
Ch=25% of investment
C=10
Ch=r*C
25
* 10
100
=Rs.2.5 /kg/year
2 * D * C0
Q *=
Ch
2 * 3600 * 36
=
2 .5
=321.99 kg/order
2C0
t*
DCh
2 * 36
3600 * 2 .5
=0.089 / year
DC h
N*
2C 0
3600 * 2 .5
=
2 * 36
=11.18 order/year
2 DC 0 C h
* = 2 * 3600 * 36 * 2 . 5
TVC =
=804.98 / year
TC=DC+TVC*
=(3600*10)+804.98
=36804.98 / year
Formula
Profit=revenue-total cost
Revenue= demand*selling price
2) A company operating 50 weeks in a year concened about its stock of copper
cable. This cost rupees 240/meter and there is a demand for a 8000m a week.
Each replenishment cost Rs1050 for administer and Rs1650 for delivery holding
cost are estimated at 25% of the value held a year. Assuming no shortage are
allowed. What is the optimal inventory policy for the company. How would this
analysis f=differ if the company wanted to maximize the profit rather than
minimize cost? What is the gross profit if the company sell cable for Rs.360 a
meter.
Solution
C=purchase cost = 240/meter
D= 8000*50=no of working weeks* demand/week
=400000 m/year
C0= Administer cost +delivering cost
=1050+1650 =Rs 2700m/year
Ch=r*C
25
* 240
= 100
=Rs. 60m/year
2 * D * C0
Q *=
Ch
2 * 400000 * 2700
=
60
=6000 m/year
2C0
t*
DCh
2 * 2700
400000 * 60
=0.015/ year
2 DC 0 C h
* = 2 * 400000 * 2700 * 60
TVC =
=360000 / year
TC=DC+TVC*
=(400000*240)+360000
=96360000m / year
If the company sell the cable for a Rs.360m its revenue is Rs360*400000
(selling cost* demand)
=Rs14400000m/year
Profit= revenue-total cost
= 144000000-96360000
=47640000
3) An aircraft company uses rivets at an approximately constant rate of
5000kg/y. The rivets cost rupees 2/kg and the company personal estimate that it
cost Rs 200 to place an order and the sharing cost of inventory is 10%/y
(i) How frequently should order for rivets be placed and what quantity should
be ordered for
(ii) If the actual cost for Rs 500 to place an order and 15% for carrying cost, the
optimal policy would change how much the company losing per year because of
imperfect cost of information.
Solution
D=5000kg/y
C=20/kg
r=inventory carrying rate =10%=0.1
C0=rs200/order
Ch=r*c=0.1*20=rs2/year
(i)
2 * D * C0
Q *=
Ch
2 * 5000 * 500
=
2
=1000/order
D 5000
N*
Q* 1000
=5
2 DC 0 C h
* = 2 * 5000 * 200 * 2
TVC =
=2000/ year
TC=DC+TVC*
=(500*20)+2000
=10200 / year
(ii)
If r =15%=0.15
C0=rs500/order
Ch=r*c=0.15*20=3
2 * D * C0
Q *=
Ch
2 * 5000 * 500
=
3
=1291/order
2 DC 0 C h
= 2 * 5000 * 500 * 3
TVC*=
=3873/ year
Thus the loss per year due to imperfect cost information
= 3873-2000
=1873/yr
Note
(i) TC =10200
(ii) TC=D.C+TVC
=(5000*20)+3873
=103873
=103873-10200
=1873/yr
4) Retail store sells 5200 units of production in a year. Each unit cost Rs.2 to
this store. The whole saler charges Rs.10 for each delivery irrespective of the
quantity order. The interest charges on working capital 15% and the insurance
charges on inventory amount to 5% per annum. All other expenses either fixed
in nature pr do not vary with the level of inventory or the quantity order. The
owner is presently following the policy of ordering 100 units every week.
He wish to evaluate this inventory policy. What recommendation would you
make?
solution
D=5200units/year
C=2
C0 = Rs10 /order
Holding cost =15%+5%
r=20%
Ch=r*C=0.4
2 * D * C0
Q *=
Ch
2 * 5200 * 10
=
0 .4
=510 units
2C0
t*
DCh
2 * 10
5200 * 0 .4
=0.098/ year
N* D/Q*
5200
10
=
510
Note
2 DC 0 C h
* = 2 * 5200 * 10 * 0 . 4
TVC =
=203.9
=204/yr
TC=DC+TVC*
=(5200*2)+204
=10604 / year
5) A company works 50 weeks in a year. For a certain part included in the
assumble of several part. There is a annual demand of 10000 units. this may be
obtained from either an outside supplier or subsidiary company. The following
data relating to the parts are given
From the outside From subside company
suppliers Rs.
Purchase price/unit 12 13
Cost of placing an order 10 10
Cost of receiving order 20 15
Storage an all carrying 2 2
cost included capital cost
/unit/annum
(i) What purchase quantity and from which source would you recommend
(ii) What would be the minimum total cost.
Solution
D=10000 units
From outside supplies
C=12/unit
C0 = 10+20=30/order
Ch=2
2 * D * C0
Q *=
Ch
2 * 10000 * 30
=
2
=548unit
2 DC 0 C h
= 2 * 10000 * 30 * 2
TVC*=
=1095/unit
TC=DC+TVC*
=(10000*12)+1095
=121095/unit
From subside company
D=10000 units
C=13/unit
C0 = 10+15=25/order
Ch=2
2 * D * C0
Q *=
Ch
2 * 10000 * 25
=
2
=500unit
2 DC 0 C h
* = 2 * 10000 * 25 * 2
TVC =
=1000/unit
TC=DC+TVC*
=(10000*13)+1000
=131000/unit
Since the total cost of bying from subsiding company is more than the outside
supplier.
Therefore an order of Q*= 548 units should be place in outside supplies.
6) The whole seller supply 30 stuffed dolls each week days to varies shops.
dolls are purchased from the manufacture in lots of 120 each per Rs.1200per lot.
Every order incures a handling charge of Rs.60 plus the flight charge of Rs 25-
per lot multiple and fractional lots also can be order and incremental cost is
Rs0.60/yr to store the doll in the inventory. The whole seller finances inventory
investment by paying its holding its company 2% monthly for borroded funds
how many doll should be ordered for at a time in order to minimum the total
annual inventory cost? Assume that there are 250 working days in a year how
frequently should be ordered.
Solution
D=30/day
D=30*250=7500 dolls/year
Since manufacture pay rupees 1200 lot
C= cost/doll=Rs10 / doll
C0=60+250=Rs310 / order
R=2% /month=2*12=24% /yr
Ch=rC=0.60+rC
=Rs 3/year
2 * D * C0
Q *=
Ch
2 * 7500 * 310
=
3
=1245dolls/order
2C0
t*
DCh
2 * 310
7500 * 3
=0.166/ year
Note
D Q*
*
C 0 Ch
TVC= Q 2
TC=D*C+TVC
TVC= annual ordering cost+annual carrying cost
7) A chemical company hold its inventory of raw material in special containers,
it each container occupying 10sq feet of floor space. There are only 5000sq.feet
of storage space available. Each year this company uses 9000 special containers
of raw material paying Rs 8/ container of raw material. If ordering cost is
Rs40/order and annual holding cost are 20% of the average inventory value,
how much is it work for this company to increase its container of raw material
storage of inventory can be stored with 5000sq.f storage limitation, assume that
this company works a 300days /yr.
Solution
D=9000 containers/year
C=Rs 8/ containers
C0 = 40 /order
R=20%=0.2
Ch=r*C=0.2*8=1.6
2 * D * C0
Q *=
Ch
2 * 9000 * 40
=
1 .6
=671 containers/order
Since each containers occupies 10sq.ft of floor space.
Therefore the company requires 671*10=6710 sqft of floor space
The total storage space available with the company is 5000sqft.
To calculate how much is work this company calculate TVC for Q* =500 and
Q* =671.
D Q*
*
C 0 Ch
TVC= Q 2
9000 500
= 500 40 2 (1 . 6 )
=720+400
=1120
9000 671
TVC= 671 40 2 (1 . 6 )
536.5+536.8
=1074
The company will save Rs 46 if it following economic order policy (Q*=671).
Rs46 worth for the company to increase the storage space.
With 5000sqft limitation only 500 units can be order.
Each day usage is 30
Nearly 500/30=17 days supply of inventory 17 days of inventory will be there.
Model –III
EOQ model with different rate of demand
1
Annual carrying cost = 2 qC h T
D
Annual ordering cost = q C 0
TVC= A.C.C+ A.D.C
1 D
C0
= 2 qC h T + q
2 DC 0
*
EOQ q = TC h
D
TVC*= 2C h C 0 ( T )
Where T is the total time period.
D is the total demand over the time T.
Model-IV
Economic production quantity model
When supply is gradual.
Formula
Q d
1 C h
Annual carrying cost = 2 p
D
C
Production setup cost = Q 0
Economic batch quantity (EBQ)
2 DC0 p
Q*
Ch pd
TVC*=carrying cost + production setup cost
Q d D
1 C h
= 2 p + Q C0
d
2 DC0 C h 1
= p
Optimum length of each lot size production run
* Q*
tp
p
Optimal production cycle time
Q*
t= D
optimal number of production cycles.
D
N*
Q*
Note
p-production rate per day
d-demand rate per day
D-demand per day
Problem
1) A contractor has to supply 10000 bearings per day to an automobile
manufacture. If finds that when his state production run, he can produce 25000
bearings per day. The cost of bearing in stock for a year Rs2 and setup cost of a
production run is a rs1800. How frequently should production run we made.
Solution
d= 10000/day
p=25000/day
Ch=2
C0=1800/production run
D= demand per day* no of working days
=10000*300=3000000
(assuming no of working day 300)
Economic batch quantity for each production
2 DC0 p
Q*
Ch pd (p>d)
2(3000000)1800 25000
2 25000 10000
=94868 bearings
Q*
*
t = D frequency of production cycle.
94868
= 25000
=9.48 days
2) The manufacturing company use an EOQ approach in planning its production
of gears. The following information is available. Each gear cost Rs 250 per
year, annual demand is 60000 gears, setup cost are Rs 4000 per setup, and the
inventory carrying cost per month is established at 2% of the average inventory
value. When in production this gears can be produced at the rate of 400 units
per day and these company works only for 300days in year. Determine
economic lot size, the no of production run per year and the total inventory cost.
Solution
Since each gear cost Rs250
C=Rs250
D=annual demand=60000
d= D/no.of working days=600000/300
=200 gears/day
C0=4000/setup
Carrying cost per month is establish at 2% of carrying inventory value.
Carrying cost per year = 2*12=24%
24
Ch=r x C= 100 * 250 =60 per year
p= Rs400/day
Economic production per each lot size
2 DC0 p
Q*
Ch pd
2(60000)4000 400
60 400 200
=4000years
D
N*
No.of production run Q*
60000
N*
4000 =15
Q* d D
1 C h C0
TVC= 2 p + Q
4000 200 60000
1 60
= 2 400 + 4000 (4000)
=Rs120000/yr
TC=TVC
= Rs120000/yr
3) The product is sold at the rate of 50 piece per day and is manufactured at the
rate of 250 pieces per day. The setup cost for the machine is rs1000 and the
storage cost is found to be rs.0.0015 per piece per day. With lower charges of
Rs3.20 per piece and material cost Rs. 2.10 per piece overhead cost of Rs4.10
per piece, find minimum cost batch size with interest charges are 8%(assume
300 working days in a year). Compute the optimum numbers of cycle required.
In a year for the manufacture of this product.
Solution
d= 50 piece per day
D=d*300=50*300=15000piece per year
p=250 piece per day
C0=1000
storage cost is found to be rs.0.0015 per piece per day
storage cost 0.0015x300 per year
With lower charges of Rs3.20 per piece and material cost Rs. 2.10 per
piece and overhead cost of Rs4.10 per piece .
i.e C=3.20+2.10+4.10=9.40
r=8%
Ch=r.C+0.0015(300)
Ch=(8/100).(9.4)+0.0015(300)
=1.202per year
2 DC0 p
Q*
Ch pd
2(15000)1000 250
1.202 250 50
=5586
D 15000
N*
Q* 5586
=3cycles
4)a) At present a company is purchase at item X from outside suppliers. The
consumption is 10000unit per year. The cost of the item is Rs5 per unit and the
ordering cost is estimated to be Rs 100 per order. The cost carry inventory is
25%. If the consumption rate is uniform determine the economic purchase
quantity.
b) In the above problem assume that company is going to manufacture the item
with the equipment that is estimated to produce 100 units per day. The cost of
the unit thus produced is Rs.3.5 per unit. A setup cost is Rs150 per setup and the
inventory carrying charge is 25%. How has your answer changed.
Solution
(a)
D= 10000/year
C=Rs. 5 /unit
C0=100/order
r=25%=0.25
Ch=rC=0.25*5=1.05
2 DC 0
Q*
Ch
2 * 100000 * 100
1.05
=1265 unit per order
b)
D=10000/year
p=100 units per day
C=3.5 per unit
C0=150 per setup
r=25%=0.25
Ch=rC=0.25*3.5=0.875%
d=10000/250=40unit per day
2 DC0 p
Q*
Ch pd
2 * 10000 * 150 100
Q*
0.875 100 40
=2391 units per order
The increase in EOQ may be due to increase procurement cost(setup cost)
Model-V
EOQ model with constant rate of demand and variable order cycle time.
2 DC0 Ch Cs
Q*
Ch Cs (EOQ)
2DC0 Cs
M*
Ch Ch Cs (optimal level)
Ch
R*=Q*-M*=Q* C h C s (optimum shortage level)
Q* 2 DC 0 Ch Cs
t
D DC h Cs
TVC=order cost + carry cost+ shortage cost
D M2 (Q M ) 2
C0 Ch Cs
Q 2Q 2Q
TC=D.C+TVC
Cs
2 DC 0 C h
TVC*= Cs Ch
Problem
1)consider the following data
Unit cost Rs 100
Order cost Rs 160
Inventory carry cost Rs 20
Back order cost(due to stock out ) Rs 10
Annual demand 1000units
i) minimum cost order quantity
ii)time b/w order
iii)maximum no. Of back order
iv) maximum level of inventory
v)overall annual cost
Solution
C=100
C0=160
Ch=20
Cs=10
D=1000
(i)
2 DC0 Ch Cs
Q*
Ch Cs
2 * 1000 * 160 20 10
20 10
=219
(ii)
Q*
t
D
219
1000
=0.219 yr (0.219*12=2.6months)
(iii) maximum back order = maximum no.of shortage
Ch
R*=Q* C h C s
=146units
(iv) maximum no.of inventory level=optimal stock level
2DC0 Cs
M*
Ch Ch Cs
2 *1000*160 10
20 20 10
=73
(v) TC=D.C+TVC
Cs
2 DC 0 C h
TVC*= Cs Ch
10
2 * 1000 * 160 * 20
10 20
TVC*=
=1460
TC= (1000*100)+1460
=101460
2)A commodity is to be supply at a constant rate of 200 units per day. Supply of
any amount can be obtained at any required time, but each ordering cost Rs50
Cost of holding the commodity in inventory is Rs 2 per day while the delay in
supply of item induce the penalty of Rs 10 per unit per day. Find the optimum
policy if the penalty cost become infinity.
Solution
d=200/day
C0=Rs50/order
Ch=Rs2unit/day
Cs=Rs10 unit/day
2 DC0 Ch Cs
Q*
Ch Cs
2 * 200 * 50 12
2 10
=109.5 units
Q*
t
D
109.5
0.547
200
Cs
If then
2 DC0 Ch Cs
Q*
Ch Cs
2 * 200 * 50 C h C s
2 Cs
2 * 200 * 50 C h
1
2 Cs
2
10000 1
100001
=100 units
3) The dealer supply you the following information with regard a product deal
in by you. Annual demand 10,000units ordering cost Rs 10/order, price
Rs 20/unit, inventory carrying cost 20% of the value of inventory per year.
The dealer is considering the possibilities of allowing some back order (stock
out) to occur. He has estimated that annual cost of back ordering will be 25% of
value of inventory.
(i) what should be the optimum no.of units of the product the should by in one
lot?
(ii) What quantity of the product should be allowed to be back order, if any?
(iii) What could be the max quantity of inventory at the any time of the year?
(iv) would be requirement to allow back ordering?
If so, what would be the annual cost saving by adopting the policy of back
ordering
Solution
D=10,000/year
C0=Rs10/order
C=Rs20/unit
r=20%
Ch=r.C=0.20*20=4 per unit per year
Cs=25% of Rs. 20=Rs5 per unit per year [C=20]
(i) economic back order quantity
When stock out not permitted
2 DC 0 2 * 10000 * 10
Q*
Ch 4
=223.6 units
When back order is permitted
2 DC0 Ch Cs
Q*
Ch Cs
2 * 100000 * 10 9
Q*
4 5
=300 units
(ii) optimum quantity of product to be back order (R*)
Ch
R*=Q* C h C s
4
=300* 9
=133.3 unit/day
(iii) max quantity of inventory at the any time of the year(M*)
2DC0 Cs
M*
Ch Ch Cs
2 *1000*10 5
4 9
=167 units/day
(iv)
TVC=
2 DC0 C h
2 * 10000 * 10 * 4
=
=894.4 units/day (Q*=223.6)
Cs
TVC(Q* 300) 2DC0Ch
C
h C s
=666.6 units/day
TVC(Q*=223.6)>TVC(Q*=300)
Therefore the dealer should accept the proposal for back ordering and this will
save him.
Rs 227.76/yr (894.4-666.6)
4) A dealer suppliers you the following information will regard a product deal
in by you annual demand 5000 units buying cost Rs 250 per order, Ch is 30%
per year, C =Rs100/ unit. The dealer is consider the possibilities of
allowing some back order(stock out) to occur for the product. The
estimated that annual cost of back ordering (allowing shortage) of the
product will be Rs10/ unit.
(i) what should be the optimum no.of units of the product he should
by in one lot?
(ii) what quantity of the product should be allowed to be back order?
(iii) how much additional cost will be have inquire on inventory if he
does not permit back ordering?
Solution
D=5000 units
C0=Rs250/order
Ch=r.C=100*0.30=30 /unit/year
Cs=Rs10 unit
(i)
2 DC0 Ch Cs
Q*
Ch Cs
2 * 250 * 5000 30 10
30 10
=576 units
(ii)optimum level of inventory
Cs
C
M*=Q* s
Ch
=576{10/40}
=144 units
The quality of product to back order R*=Q*-M*
=576-144
=432 units
(iii) Additional cost incurred=TVC=
Cs
2DC0 Ch
Ch Cs
10
2 * 5000* 250* 30
40
=Rs 4330
EOQ model with gradual supply and shortage allow
Optimal production lot size
2 DC 0 p C h C s
Q*
Ch p d C s
Optimal level of shortage
d C h
1
p C s C h
R*=Q2*=Q *
Production cycle time
Q*
t
D
2C 0 p C h C s
t*
DC h p d C s
Optimal inventory level
* pd *
Q1 Q Q2 *
p
* 2 DC 0 p C s
Q1 1
Ch d C s C h
Total minimum variable inventory cost
d C s
2 DC 0 C h 1
p C s C h
TVC*=
Problems
1) The cost parameter and other factors for a production inventory system of
automobile pitons of given below demand per year D=6000 units, unit per cost
C=Rs40, setup cost C0=Rs500, Ch=Rs8, production rate per year 36000units
shortage cost per unit per year Cs=Rs20
Find (i) optimum lot size
(ii) no.of shortages
(iii) manufacturing time
(iv) time between setups cycle time.
Solution
D=6000 units /yr
P=36000/yr
C=Rs40
C0=Rs500
Ch=Rs8
Cs=Rs20
(i)
2 DC 0 p C h C s
Q*
Ch p d C s
2 * 6000 * 500 36000 8 20
Q*
8 36000 6000 20
=1123 units
(ii)
d C h
1
p C s C h
R*=Q *
6000 8
1
36000 8 20
=1123
=267 units
(iii)
Q*
t*
D
1123
6000
=0.19yrs
* Q*
t
P
1123
36000
=0.03yrs
problem:-02
The demand for an item in a company is 18000 units per year, and the
company can produce the at the rate of 3000 per month. The cost of one setup is
Rs 500 and the holding cost of one unit per month is 15 piece the shortage cost
of one unit is Rs240 per year. Determine the optimum manufacturing quantity
and the no.of shortage. Also determine the manufacturing time and the time b/w
setup.
Solution
D=18000 units /yr
d=1500 unit per month
p=3000/month
C0=Rs500/setup
Ch=0.15 paisa per unit per month
Cs=20 per month
(i)
2 DC 0 p C h C s
Q*
Ch p d C s
2 * 1500 * 500 3000 0.15 20
Q*
0.15 3000 1500 20
=4489 per month
(ii)
d C h
1
p C s C h
R*=Q *
1500 0.15
1
3000 0.15 20
= 4489*
=17 per month
(iii)
* Q*
t
d
4489
t*
1500
=3 month(time b/w setup)
(iv)
Q*
t*
P
4489
t*
3000
=1.5 month( manufacturing time)
3) A purchase as desired to place order for a quantity of 500 units of a particular
item in order to get discount of 10%. From the past record it was found
out that in the last year 8 orders each of size 200 units where placed.
Given the ordering cost Rs 500/order inventory cost 40% of the inventory
value and the price of the item of Rs400/unit. Is the purchase manager
justified in the decision? What is the exact of his decision of the
company.
Solution
D=8*200=1600 units /yr
C0=Rs500/order
r=40%
C=400/unit
Ch=r.C=.40x400=160
2 DC 0
Q*
Ch
2 * 1600 * 500
160
=100units
Price break problem
1)A shop keeper has a uniform demand of an item at the rate of 100 item per
month. He buys from supplier at a cost of Rs12 per item and the cost of
ordering is Rs 10 each time. If the stock holding cost are 20% per year of
stock value. How frequently should he replenish his stock? Further
suppose the suppliers offers 5% discount on orders between b/w 200 and
999 item,10% discount on orders exceeding or equal to 1000, can the
shopkeeper reduces his cost by taking advantage of either of those
discount.
Solution
d=100/month
D=1200/yr
C=12/item
C0=Rs. 10/yr
r=20%=0.20
Ch=rC=0.20*12=2.4
When no discount is offer
2 DC 0
Q*
Ch
2 * 1200 * 10
2.4
=100
D
N*
Q*
1200
100
=12
TVC 2 DC 0 C h
2 * 1200 * 10 * 2.4
=240
TC=D.C+TVC
=(1200*12)+240
=14640
(ii)
When quantity discount are offer
Quantity prince/unit
0≤Q1<200 12 (no discount)
5% of 12=0.05x12=0.6
200≤Q2<1000 11.40 (5% discount 0.6rs)
10% of 12 =.1x12=1.2
1000≤Q3 10.8 (10% discount 1.2rs)
b1=200
b2=1000
let us calculate Q3* based on the price C3=10.8
2 DC 0
Q*
Ch
* 2 * 1200 * 10
Q3
0.20 * 10.8
=105
* *
Since Q3 < b2 and Q3 < b1
TC(b1=200)=D.C+TVC
=13968
TC(b2=1000)=D.C+TVC
=14052
Since TC (b1)<TC(b2)<TC(Q1*)
Hence the shopkeeper accept the offer 5% discount
His net saving per year would be 14640-13968= Rs672
Two price break
1)The annual demand of product is 10000units. Each unit cost RS 100 if the
orders placed in quantities below 200 units but for orders of 200 or above the
price is Rs95. The annual inventory holding cost is 10% of the value of the item
and the ordering cost is rs5 per order. Find the economic lot size.
Solution
D= 10000 units per yr
C0=5 per order
r=10%
C=100
Quantity prince/unit
0≤Q1<200 100
200≤Q2 95
b1=200
* 2 DC 0
Q2
Ch
2 * 10000 * 5
0.10 * 95
=103
Since Q2*<b1
We calculate Q1* using C1=100
2 * 10000 * 5
0.10 * 100
=100
TC(Q1*)=D.C2+TVC
=1001000
TC(b1*)=D.C2+TVC
=950000
TC(b1=200)=950000+1200
=951200
TC(Q1)>TC(b1)
Therefore optimal order quantity is Q*=b1=200 units
UNIT-IV
NETWORK
PROJECT
A project defined as a combination of inter related activities, all of
which must be executed in a certain order to achieve the goal.
EXAMPLE:-
Construction of building is the project consist of several levels
(activities) of works
ACTIVITY
It is a task or an item of work to be done in a project.
An activity can be represented by an arrow with a node (event) at the
beginning and at the end, arrow indicating the termination of activity.
Node A Node
I J
NOTE:-
In the above arrow diagram,
A denotes the activity.
Node I is called starting node (Node I is also called tail event )
Node II is called ending node (Node II is also called head event)
Symbolically the above activity can be written as I < J .
ARROW DIAGRAM
The diagram in which arrow represents an activity is called arrow
diagram.
IMMEDIATE PREDECESSOR /SUCCESSOR
Node A Node B Node C Node
I J K L
In the above arrow diagram,
Activity 'A' is called immediate predecessor of the activity B.
Activity 'B' is called the immediate successor of the activity A.
Activity 'B' is called immediate predecessor of the activity C.
Activity 'C' is called the immediate successor of the activity B.
NOTE:-
(i) C is a successor of A, but not immediate successor
(ii) A is a predecessor of C, but not immediate predecessor.
(iii) It can be written short form as follows A,B<C ( or C>A,B) and A<B
(or B>A)
EXAMPLE:-
Node A
I
C
Node Node
K L
Node B
J
Relation Immediate Immediate
Activity Predecessor Successor
A A<C (C>A) - C
B B<C (C>B) - C
C A,B<C (C>A,B) A,B -
STARTING ACTIVITY
An activity which does not have predecessor is called starting activity
in the project.
NOTE:-
(i) There may be one or more than one starting activities in the
network diagram.
(ii)The starting nodes of all the starting activity can be combined into
a single nodes.
EXAMPLE
From the following construct the arrow diagram.
Activities : P Q R S
Predecessor: - - P Q
SOLUTION:-
Since P, Q has no predecessor's, therefore P and Q are starting nodes.
I P J R L
Q S
N K M
Here P,Q are starting activities, therefore the starting notes of these
activities namely I and N can be combined into single node.
P R
I J L
Q S
K M
ENDING ACTIVITY
An activity which does not have successor is called ending activity in
the project.
NOTE:-
(i) There may be one or more than one ending activities in the
network diagram.
(ii) The ending nodes of all the ending activity can be combined into
a single nodes.
EXAMPLE
From the following construct the arrow diagram.
Activities : P Q R S
Predecessor: - - P Q
SOLUTION:-
Since P, Q has no predecessor's, therefore P and Q are starting nodes.
I P J R L
Q S
N K M
Here P,Q are starting activities, therefore the starting notes of these
activities namely I and N can be combined into single node.
P R
I J L
Q S
K M
Since R,S has no successor's, therefore R and S are ending nodes,
Therefore the ending nodes of the ending activities can be combined into
single node
P R
I L
Q S
DUMMY ACTIVITY
If the project contains two or more activities which have some of
their immediate predecessor in common then there is a need for introducing
dummy activity.
EXAMPLE
From the following construct the arrow diagram.
Activities : P Q R S
Predecessor: - - P,Q Q
SOLUTION:-
Since P, Q has no predecessor's, therefore P and Q are starting nodes.
Similarly R, S has no successor's, therefore R and S are ending nodes.
Here activities R and S have predecessor Q in common, therefore we
must add dummy activity in the network diagram. Otherwise we could not
draw the arrow diagram. At the same time P is not the predecessor of S.
J R L
I
Q
S
K M
EXAMPLE:-
Construct the arrow diagram for the following
Activity Predecessor
P -
Q -
R P,Q
S Q
SOLUTION:-
Since P,Q has no predecessor, therefore P,Q are starting activities
Similarly R,S has no successor, there for R,S are ending activities.
Here the activity Q is the common predecessor for both the activities
R and S, So there is a need of dummy activity. (without adding dummy
activity the arrow diagram could not be completed)
I P J R L
Q S
N K M
The starting and ending nodes of starting and ending activities can be
combined into single node.
P R
Q S
N K M
NOTE:-
(i) Dummy activity is an imaginary activity which does not consume
any resources and it serves the purpose of indicating the
predecessor or successor.
(ii) Dummy activity is represented by a dotted line in the arrow
diagram.
(iii) When there are two activities with common predecessor's, then
there may be a need of adding dummy activity , otherwise no need
to add. It should be added only when the arrow diagram could not
be completed without this.
RULES FOR CONSTRUCTING PROJECT NETWORK
(i) There must be no loop
(ii) Only one activity should connect any two nodes.
(iii) No dangling should appear in a project.
i.e. No ending node of any activity, expect terminal activities of the
project should be left without any activity emanating from it.
RULES FOR NUMBERING OF NODE
(Foral and Fulkerson’s algorithm or rule)
Step (i) Number the start node which has no predecessor activity as 1.
Step (ii) Delete all the activities emanating from this node 1, number all
the resulting start node without any predecessor as 2,3.....
Step (iii) Delete all the activity originating or emanating from 2,3,.....
Step (iv) Number all the resulting new starting nodes left in step 3.
Step (v) Repeat the process until the terminal node without any
successor activity is reached and number the terminal node
suitably.
ERRORS IN NETWORK
(i) Looping
A case of endless loop in a network diagram which also known and looping.
Looping is considered as faults in a network, therefore it must be avoided.
C 3 4
1 B ( Looping not allowed )
A 2
(ii) Dangling
A case of disconnect activity before the completion of all activities which is also
known as dangling. Dangling is considered as faults in network, therefore it must be
avoided.
A B D
1 2 4
C Dangling activity
Here C is a dangling activity, since the activity is disconnected before completion
of the activity D.
ADDITION OF DUMMY ACTIVITY IN NETWORK
There are two situations in which use of dummy activity may help in drawing the
network correctly as follows
(I) When two or more parallel activities in a project have the same head and tail events.
i.e two events are connected with more than one arrow. These parallel activities are not
allowed in network.
C
A D
1 2
B
Here the activities B and C have common predecessor A and successor D.
This can be corrected using dummy activity as follow
C
A D
1 3
B Dummy
Otherwise
C Dummy
A D
1 3
B
(II) When two chains of activities have a common predecessor, then we may have to
add dummy.
A C E
Dummy
B D
Here C and D has common predecessor A, but B is not a predecessor of C.
PROBLEM:-01
Draw the network for the project whose activities which predecessor activities are
given below.
A,B,C- can start simultaneously . E>B,C; F,G>D; H,I>E,F; J>I,G; K>H; D>A.
SOLUTION:-
Since there is no predecessor's for the activity A,B,C, therefore A,B,C are the
starting activity
A
C
Similarly there is no successor's for the activities J,K, therefore J,K are ending
activities.
J
A
C
B
K
Since E>B,C, i.e E is the successor of B and C.
J
A
C
B D1
E K
Since D>A, i.e D is the successor of A.
D
J
A
C
B D1
E K
Since F,G>D, i.e F,G is the successor of D
D F
J J
A G
C
B D1
E K
Since H,I>E,F
D
A G J
C
F K
B D1
E H
Since J>I,G, i.e J successor of I,G
D
A G J
C
F K
B D1
E I
Since K>H
D
A G J
C
F K
B D1
E I
H
NOTE:-
Numbering of nodes
First we have to number the starting node as 1, then remove all activities
emanating from the node 1, namely A, B and C
D
G G J
1
F
D1 I K
E H
H
Now there are two starting nodes, name the nodes as 2 and 3, then remove all
activities emanating from node 2 and node 3. Namely D , D1 and E
G G J
1
3 F
I K
H
Now there are two starting node, name it as 4 and 5, remove all activities
emanating from node 4 and node 5. Namely F and G.
2
5G J
1
3
I K
H
4
Now there is only one starting node, name it as 6, remove all activities emanating
from node 6. Namely I and H.
2
5G J
1
3
4 6
Now there is two starting nodes, name it as 7 and 8, remove all activities
emanating from node 7 and 8. Namely J and K.
2
5G
1 7 9
3
4 6 8
Name the final node as 9.
PROBLEM:-02
Construct the network for the project whose activities and their relation are
given below:
A,D,E can start simultaneously. B,C>A; G,F>D,C; H>E,F
SOLUTION:-
Since there is no predecessor's for the activities A, D and E , therefore starting
activities are A,D,E
A
D
Since there is no successors for the activities B, G and H, therefore the B,G,H are
ending activities
A B
D G
E h
Since B,C>A, i.e B and C are successor's of A
A B
D C G
E H
Since G,F>D,C, i.e G and F are Successors for the activities D and C.
A B
C G
D F
E H
Since H>E,F, i.e H is the successor for the activities E and F.
2
A B
C G
1 3 5
D F
E H
4
NOTE:-
Numbering of nodes
First we have number initial node as 1, then remove all activities emanating
from node 1. namely A , D and E.
B
C G
1 F
H
Now there is only one starting node, name it as 2, remove edges emanating from
node 2. namely B and C.
G
1 F
H
Now there is only one starting node, name it as 3, remove edges emanating from
node 3 . namely G and F.
2
1 3
Now there is only one starting node, name it as 4, remove edges emanating from
node 4 . namely H.
1 3 5
Name the final node as 5.
PROBLEM:-03
Draw the network for the project whose activities and their relationship are given
below.
ACTIVITY A B C D E F G H I
IMMEDIATE - A A - D B,C,E F E G,H
PREDECESSOR
SOLUTION:-
Since there is no predecessor's for the activities A and D, therefore A,D are the
starting activities.
D
Since there is no successor's for the activity I, therefore I is the ending activity.
A
I
D
Since A is predecessor for activities B and C
B
A
C I
D
Since D is predecessor for activity E
B
A
C I
D
Since B,C and E are predecessor for activity F
B
A
C D1 I
D
E F
Since F is predecessor for activity G
B
A
C D1 I
D
E F G
Since E is predecessor for activity H, we have to add dummy activity(D1), since
two activities F and H are having predecessor E in common. Also the activities B, C are
predecessor's for the activity F but not for the activity H.
B
A
C D1 I
D
E F G
D2
H
Since G, H are the predecessor for activity I.
B
4
A 2
1 C D1
D
3 6 7
9
E F G I
D2
H
5 8
PROBLEM:-04
Draw the network for the project whose activities and their relationship are given
below.
P Q R S T U
- - - P,Q P,R Q,R
SOLUTION:-
Since there is no predecessor's for the activities P,Q and R, therefore P,Q,R are
starting activities.
P
Q
R
Since there is no successor's for the activities S,T and U, therefore S,T and U are
ending activities.
S
P
Q T
R
U
Since P,Q are the predecessor for S, we have to add dummy activity D1
S
P D1
Q T
R
U
Since P,R are the predecessor for T. We have to add dummy activity [D2 ], since
two activities S and T have predecessor P in common.
S
P D1
Q D2
R T
U
Since Q,R are the predecessor for U. We have to add dummy activities[D3 and D4],
since two activities U and T have predecessor R in common.
3
S
P D1
1 Q D2 T
2 6
5
R D3 D4 U
EXERCISE
1. Draw network diagram from following activities and find critical path and total slack
of
activities.
Job A B C D E F G H I J K
Immediate
Predecessor - A B C B E D,F E H G,I
J
2. A small project is composed of 7 activities whose time estimates are listed in the table
below.
Activity A B C D E F G H
Predecessor - - - A B C D,E F,G
Draw the network diagram.
3. A small project consists of seven activities for which the relevant data are given
below;
Activity A B C D E F G
Preceding Activity - - - A,B A,B C,D,E C,D,E
Draw the network diagram.
4. Draw the network for the following
Activity Predecessors
A -
B -
C A
D B
E B
F C,D
G E
5. A Professional institute is organizing a seminar on new accounting techniques at
Delhi.
The seminar will include 2 keynote speeches and 8 paper reading sessions. It is
considered
that the following activities are to be accomplished with the respective duration as
specified in the table below;
Activity A B C D E F G H I J K L M N O
Preceding - - - B B A,E C,D G H I C,D C,D C,D J M
6. A small project consists of seven activities, the details of which are given below:
Activity Immediate predecessor
A -
B A
C A
D B,C
E B
F D,E
G D
Draw the network diagram.
PERT and CPM
PERT (Programme Evaluation Review Technique) and CPM (Critical Path
Method) are network techniques used for planning, scheduling and executing large
projects which require coordination and execution of large number of activities. These
activities should be completed within a specified time, cost and meeting the
performance standards.
The objective of PERT and CPM is to estimate the total project duration and to
assign starting and finishing times to all activities involved in the project. This help in
checking actual progress against the scheduled duration of the project.
The duration of individual activities may be uniquely determined in case of CPM ,
But it may involve the three time estimate in case of PERT out of which the expected
duration of an activity is computed.
NOTATIONS
The following are the notations used in the PERT analysis.
Ei = Earliest occurrence time of an event i, It is earliest time at which an event occur
without affecting the total project time.
Li = Latest occurrence time of an event i, It is the latest time at which an event can occur
without affecting the total project time.
ESij = Earliest start time for an activity (i,j). It is the earliest time at which the activity
can start without affecting the total project time.
LSij = Latest start time for an activity (i,j). It is the latest possible time by which the
activity must start without affecting the total project time.
EFij = Earliest finish time for an activity (i,j). It is the earliest possible time at which an
activity can finish without affecting the total project time.
LFij = Latest finish time for an activity (i,j). It is the latest time by which an
activity must get completed without delaying completion. without affecting the
total project time.
tij = Duration of an activity (i,j)
NOTE:
(I) In a network diagram there should be only one initial event and one end
event.
(II) For the calculation of earliest start, finish, and latest start, finish time. we use
the forward pass method and backward pass method respectively.
FORWARD PASS METHOD
(To calculate earliest start and finish)
The calculations of forward pass method begin from the initial event (Node 1),
proceed through the events in an increasing order of event numbers and end at the final
(Node N)
Step:-01
Let the earliest occurrence time of initial event 1 be zero. i.e E1=0
Step:-02
Calculate the earliest start time (ESij) for each activity (i,j) , where i=1
ESij = Ei, for all activity (i,j) starting at event i.
Step:-03
Calculate the earliest finish time (EFij) of each activity (i,j) that begin at event i.
EFij = ESij + tij=Ei+tij for all activity (i,j) beginning at event i
Step:-04
Proceed to the next event J where j>i
Step:-05
Calculate the earliest occurrence time for the even j, This is the maximum of the
earliest finish times of all activities ending into that event.
Ej=Max{EFij}=Max{Ei+tij} for all immediate predecessor activities.
Step:06
If j=N (final event), then earliest finish time for the project, that is earliest
occurrence time EN for the final event is given by
EN=Max{EFij}=Max{EN-1+tij}, for all terminal activities.
BACKWARD PASS METHOD
(To calculate latest finish and start)
The calculations of backward pass method begin from the end event (Node N),
proceed through the events in an decreasing order of event numbers and end at the
initial (Node 1)
Step:-01
Let the latest occurrence time of last event N equal to its earliest occurrence
time LN=EN (known from forward pass method)
Step:-02
Calculate the latest finish time (LFij) for each activity (i,j), which ends at the
event j.
LFij = Lj, for all activity (i,j) ending at event j.
Step:-03
Calculate the latest start time (LSij) of each activity (i,j) that end at event i.
LSij = LFij - tij=Lj-tij for all activity (i,j) ending at event j
Step:-04
Proceed to backward go to the previous event, i < j
Step:-05
Calculate the latest occurrence time for the even i, This is the minimum of the
latest start times of all activities from the event.
Li=Min {LSij}=Min {Lj-tij} for all immediate successor activities.
Step:06
If j=1 (initial event), then latest finish time for the project, that is latest
occurrence time L1 for the inital event is given by
L1=Min{LSij}=Min{Lj-1 - tij}, for all starting activities
CRITICAL ACTIVITY
Certain activities in the network diagram of a project are called critical activities
because delay in their executions will cause further delay in the project completions
time.
FLOAT OF AN EVENT (SLACK)
The float (slack) or free time of the event is difference between its latest
occurrence time (Li) and its earliest occurrence time (Ei).
Event float=Li-Ei
It is a measure of how much later than a particular event could be started
without delaying the completion of the entire project.
FLOAT OF AN ACTIVITY (SLACK)
The float (slack) or free time of the activity is the length of time to which a non-
critical activity or event can be delayed or extended without delaying the total project
completion time.
There are three types of float, (i) Total float (ii) free float , and (iii)
Independent float. (iv) Interfering float
TOTAL FLOAT
It is an amount of time by which an activity can be delayed without affecting
project completion time.
Total float for the activity (i,j) is denoted by TFij
TFij=Lj-Ei-tij
NOTE
The activity which has total float equal to zero are called as critical activities.
FREE FLOAT
It is calculated to know how much an activity's completion time may be delayed
without causing any delay in its immediate successor activities. i.e a delay in performing
an activity without affecting floats of subsequent activities.
It is denoted by FFij
FFij=Ej-Ei-tij
INDEPENDENT FLOAT
It is the amount of time an activity can be delayed for start without affecting the
completion of preceding activities.
It is denoted by IFij
IFij=Ej-Li-tij
NOTE:-
(i) Li Ei for all i
(ii) Independent float Free float Total float.
(iii) Calculations of various float can help the decision -maker in identifying the
under utilized resources, flexibility in the total schedule and possibilities of
redeployment of recourses
CRITICAL PATH
It is a continuous chain of critical activities in a network diagram. It is the longest
path starting from first to the last event .
It is usually represented by double line or think line in the network diagram.
NOTE:-
The critical path on the network diagram can be identified as follows
(i) For all activity (i,j) lying on the critical path, Ei=Li and Ej=Lj
(ii) On the critical path Ej-Ei=Lj-Li=tij
LENGTH OF CRITICAL PATH
It is the sum of the individual durations of all the critical activities lying on the
critical path and defines the minimum time required to complete the project .
THREE TIME ESTIMATE IN PERT
If the duration of activities in project is uncertain, then activity scheduling
calculation are done by using the expected value of the durations. Thus rather than
estimating directly the expected completion time of an activity, three values are
considered. From these timings a single value is estimated for future consideration. This
is called three -time estimates in PERT. The three time estimates namely optimistic,
pessimistic and most likely times.
OPTIMISTIC TIME
This is the shortest possible time to perform an activity, assuming that every thing
goes well.
It is denoted by to or a
PESSIMISTIC TIME
This is the maximum time that is required to perform an activity, under extremely
bad conditions. However, such conditions do not include acts of god like earthquakes,
flood, etc.,
It is denoted by tp or b
MOST LIKELY TIME
This is the most realistic time to complete the activity. Statistically, it is the modal
value of duration of the activity.
It is denoted by tm or m
NOTE:-
Formulae for PERT Calculations
t 0 4t m t p
(1) Expected Activity Time=te=
6
1
(2) S.D= (t p t o )
6
2
1
(3) Variance= 2 (t p t o )
6
(4) Estimation of Project Completion Time:
Probability of completing the project by scheduled time (TS) can be determined
using the standard normal variable value,
TS Te
i.e P{TS r } can be calculated using Z= , where Te is the expected
e
completion time of the project (Total duration of critical path) and e is the number of
standard deviations the scheduled time lies from the expected (mean) time.
Basic Difference Between PERT and CPM
PERT CPM
It assumes probability distribution for the This technique was developed in
duration of each activity. Thus the connection with a construction and
completed time estimate for all the maintenance project in which duration of
activities are needed each activity was known with certainty
It emphasis on the completion of a task It is suitable for establishing a trade - off
rather than the activities required to be for optimum balancing between schedule
performed to reach to a particular even or time and cost of the project.
task, So it is also called event oriented
technique.
It is used for one time projects involving It is used for completion of projects
activities of non-repetitive nature (i.e involving activities of repetitive nature.
activities which may never have been
performed before) in which time estimates
are uncertain, such as redesigning an
assembly line or installing a new
information system.
PROBLEM:-01
Calculate earliest start and finish time of each activity of the project given below.
Activity 1-2 1-3 2-4 2-5 3-4 4-5
Duration 8 4 10 2 5 3
in days
SOLUTION:-
E2=8
2
2
8 0 E5=21
5
E1=0 1 4 3
E4=18
4 5
3
E3=4
First we have to calculate Earliest start time then Earliest finish time.
ACTIVITY Duration Earliest Start Earliest Finish
i-j tij ESij=Ei= Max{Ei-1+tij} EFij=ESij+tij
1-2 8 E1=0 0+8=8
1-3 4 E1= 0 0+4=4
2-4 10 E2= 0+8=8 8+10=18
[Node 2 can be reached from only one node 1]
2-5 2 E2 0+8=8 8+2=10
[Node 2 can be reached from only one node 1]
3-4 5 E3=0+4=4 4+5=9
[Node 3 can be reached from only one node 1]
4-5 3 E4= Max{8+10, 4+5}=18 18+3=21
[ Node 4 can be reached from node 2 and 3]
NOTE
(i) E5=Max{8+2,18+3}=21, since node 5 can be reached from node 2 and
node 4.
(ii) The method used here is called forward pass method, since it start from
the initial node and ending with terminal node of the network diagram.
PROBLEM:-02
Calculate earliest start and finishing time of each activity of the project given below.
Activity 1-2 1-3 1-5 2-3 2-4 3-4 3-5 5-6 4-6 3-6
Duration 8 7 12 4 10 3 5 4 7 10
in week
SOLUTION:-
E1=8 10 E2=18
2 4
E1=0 8 4 3 7
7
1 3 6
10
E3=12 E6=25
12 5 4
E5=17
First we have to calculate Earliest start time then Earliest finish time.
ACTIVITY Duration Earliest Start Earliest
i-j tij ESij=Ei= Max{Ei-1+tij} Finish
EFij=ESij+tij
1-2 8 E1= 0 0+8=8
1-3 7 E1= 0 0+7=7
1-5 12 E1= 0 0+12=12
2-3 4 E2=0+8=8 8+4=12
[ Node 2 can be reached from only one node 1]
2-4 10 E2=0+8=8 8+10=18
3-4 3 E3=max{8+4,0+7}=12 12+3=15
[Node 3 can be reached from Node 1 ,Node 2]
3-5 5 E3=12 12+5=17
3-6 10 E3=12 12+10=22
4-6 7 E4= Max{8+10,12+3}=18 18+7=25
[Node 4 can be reached from Node 2 ,Node 3]
5-6 4 E5= Max{5+12,0+12}=17 17+4=21
[Node 5 can be reached from Node 1, Node 3]
NOTE:-
E6=max{18+7, 12+10, 17+4}=25, since Node 6 can be reached from Node 3, Node
4 and Node 5.
PROBLEM:-03
Calculate the latest start and finish time of the activity of the project given below.
Activity 1-2 1-3 2-4 2-5 3-4 4-5
Duration in days 8 4 10 2 5 3
SOLUTION:-
First we have to calculate earliest start and then earliest finish time.
E2=8, L2=8 E5=21, L5=21
2 2 5
8
E1=0 , L1=0 10 3
1
4
4 E3=4 ,L3=13 5 E4=18, L4=18
3
Latest finish time has to be calculated first then latest start time.
Activity Duration Latest Start Latest Finish
(tij) LSij=LFij-tij LFij=Lj=Min{Lj+1-tij}
1-2 8 8-8=0 L2=Min{18-10,21-2}= 8
[Node 2 can be reached in backward direction from
Node 4 and Node 5]
1-3 4 13-4=9 L3 =13
[Node 3 can be reached in backward direction from
Node 4]
2-4 10 18-10=8 L4= 18
2-5 2 21-2=19 L5= 21
3-4 5 18-5=13 L4= 18
[ Node 4 can be reached in backward direction from
only Node 5]
4-5 3 21-3=18 L5= 21
NOTE
(i) L1=Min{13-4,8-8}=0, since node 1 can be reached in backward direction
from node 2 and node 3.
(ii) The method used here is called backward pass method, since it start from
the terminal node and ending with initial node of the network diagram.
PROBLEM:-04
Calculate the latest start and finish time of the activity of the project given below.
Activity 1-2 1-3 1-5 2-3 2-4 3-4 3-5 3-6 4-6 5-6
Duration in week 8 7 12 4 10 3 5 10 7 4
SOLUTION:-
First we have to calculate earliest start and finish time.
E2=8, L2=8
2
8 10 E4=18, L4=18
E1=0 , L1=0 4 4
1 7 3 3
E3=12 ,L3=15 7
12 5 10
5 6
4
E5=17, L4=21 E6=25, L4=25
Activity Duration Latest Start Latest Finish
i-j (tij) LSij=LFij-tij LFij=Lj=Min{Lj+1-tij}
1-2 8 0 8
1-3 7 8 15
1-5 12 9 21
2-3 4 11 15
2-4 10 8 18
3-4 3 15 18
3-5 5 16 21
3-6 10 15 25
4-6 7 18 25
5-6 4 21 25
PROBLEM:-05
Calculate the latest start and finish time and earliest start and finish time of each activity
of the project given below.
Activity 1-2 1-3 2-4 2-5 3-4 4-5
Duration 8 4 10 2 5 3
Also find (i) Floats (ii) find the critical path.
SOLUTION:-
E2=8, L2=8
2
E1=0, L1= 0 8 10 2 E5=21, L5=21
5
1 55
3
3 4
4 5
E3=4, L3=13 E4=18, L4=18
Activity Duration ESij EFij LSij LFij TFij FFij IFij InFij
i-j tij Ei Ei+tij Lj-tij Lj Lj-tij-Ei Ej-Ei-tij Ej-Li-tij TF-FF
1-2 8 0 8 0 8 0 0 0 0
1-3 4 0 4 9 13 9 0 0 0
2-4 10 8 18 8 18 0 0 0 0
2-5 2 8 10 19 21 11 11 11 0
3-4 5 4 9 13 18 9 9 0 0
4-5 3 18 21 18 21 0 0 0 0
The critical path is the above network is 1-2-4-5 and the longest duration is 21.
NOTE:-
If total float is zero, then the corresponding activity is called critical activity.
PROBLEM:-06
Find (i) critical path (ii) Earliest start , finish, (iii) Latest start, finish (iv) value of float
for the following.
Activity 1-2 1-3 1-5 2-3 2-4 3-4 3-5 3-6 4-6 5-6
Duration 8 7 12 4 10 3 5 10 7 4
SOLUTION :-
E2=8, L2=8
2
8 10 E4=18, L4=18
E1=0 , L1=0 4 4
1 7 3 3 7
E3=12 ,L3=15 E6=25, L4=25
12 5 10 6
5
E5=17, L4=21 4
Activity Duration ESij EFij LSij LFij TFij FFij IFij InFij
i-j tij Ei Ei+tij Lj-tij Lj Lj-tij-Ei Ej-Ei-tij Ej-Li-tij TF-FF
1-2 8 0 8 0 8 0 0 0 0
1-3 7 0 7 8 15 8 5 5 3
1-5 12 0 12 9 21 9 5 5 4
2-3 4 8 12 11 15 3 0 0 3
2-4 10 8 18 8 18 0 0 0 0
3-4 3 12 15 15 18 3 3 0 0
3-5 5 12 17 16 21 4 0 -3 4
3-6 10 12 22 15 25 3 3 0 0
4-6 7 18 25 18 25 0 0 0 0
5-6 4 17 21 21 25 4 4 0 0
The critical path is 1-2-4-6 and project completion time 25.
PROBLEM:-07
Construct the network for the project whose activity are given below and find the
critical path and its project duration and also float values.
Activity 0-1 1-2 1-3 2-4 2-5 3-4 3-6 4-7 5-7 6-7
Duration 3 8 12 6 3 3 8 5 3 8
SOLUTION:-
E2=11, L2=14
2
10 E5=21, L5=24
E0=0 , L0=0 3 8 5
0 6 7
1
4 5 E7=31, L7=31
E1=3, L1= 3 E4=18 ,L4=26 7
12 3 8
3 6
8
E3=15, L3=15 E6=23, L6=23
Activity Duration ESij EFij LSij LFij TFij FFij IFij InFij
i-j tij Ei Ei+tij Lj-tij Lj Lj-tij-Ei Ej-Ei-tij Ej-Li-tij TFij-FFij
0-1 3 0 3 0 3 0 0 0 0
1-2 8 3 11 3 11 0 0 0 0
1-3 12 3 15 3 15 0 0 0 0
2-4 6 11 17 20 26 9 1 -2 8
2-5 3 11 14 25 26 12 0 -3 12
3-4 3 15 18 23 28 10 0 0 10
3-6 8 15 23 15 26 3 0 0 3
4-7 5 18 23 26 23 0 8 0 -8
5-7 3 14 17 28 31 14 3 0 11
6-7 8 23 31 23 31 0 0 0 0
The critical path is 0-1-3-6-7 and the project duration is 31.
PROBLEM-08
The following table indicates the details of the project. The duration
are in days ‘a’ refers to optimistic time, ‘m’ refer to most taking time, ‘b’
refer to estimate time duration.
Activity to(a) tm(m) tp(b)
1-2 2 4 5
1-3 3 4 6
1-4 4 5 6
2-4 8 9 11
2-5 6 8 12
3-5 2 3 4
4-5 2 5 7
(i) Draw the network
(ii) Find the critical path
(iii)Determine the expected S.D of the completion time.
SOLUTION:-
E2=3.8, L2=3.8
2 8.33
3.8 E4=17.79, L4=17.79
E1=0 , L1=0 9.16 5
1 5 4 4.83
E3=12.96 ,L3=12.96
4.16 3 3
E5=4.16, L4=14.79
Activity to(a) tm(m) tp(b) te= 1
2
2 (t p t0 )
1 6
(t0 4tm t p )
6
1-2 2 4 5 3.8 0.5
1-3 3 4 6 4.16 0.5
1-4 4 5 6 5 0.3
2-4 8 9 11 9.16 0.5
2-5 6 8 12 8.33 1
3-5 2 3 4 3 0.3
4-5 2 5 7 4.83 0.33
Therefore the Critical path is 1-2-4-5 and its total duration is
17.79(=3.8+9.16+4.83)
The expected standard deviation of critical path is 1.33 (=10.5+0.5+0.33)
PROBLEM:-09
A project consist of the following activities and tome estimates to-
least time in day , tp-greatest time in days
Activity to tp tm
1-2 3 15 6
2-3 2 14 5
1-4 6 30 12
2-5 2 8 5
2-6 5 17 11
3-6 3 15 6
4-7 3 27 9
5-7 1 7 4
6-7 2 8 5
(i) Prove the network
(ii) What is the probability that project will be completed in 27 days
SOLUTION:-
Activity to tp tm te SD σ2
1-2 3 15 6 7 2 4
2-3 2 14 5 6 2 4
1-4 6 30 12 14 4 16
2-5 2 8 5 5 1 1
2-6 5 17 11 11 2 4
3-6 3 15 6 7 2 4
4-7 3 27 9 11 4 16
5-7 1 7 4 4 1 1
6-7 2 8 5 5 1 1
E2=7, L2=7 E3=13, L3=13
6
2 3
7 11
E1=0 , L1=0 5 7
1 54.8 6
E5=12 ,L5=21 E6=20, L6=20
4 5
14 4 11
7
E4=14, L4=14 E7=25, L7=25
Critical paths are
(i) 1-2-3-6-7 and its duration 25 (=7+6+7+5)
(ii) 1-4-7 and its duration 25 (=14+11)
Variance are
(i) Critical path 1-2-3-6-7 variance is 13 (=4+4+4+1)
(ii) 1-4-7 is 16+16=32
Let tS- denotes the project completion time
P(project will be completed in 27 days)= pt s 27
= pt s t e 27 25
t s t e 27 25
p
=
5.65
= p Z 0.35
= p[ Z 0] P[0 Z 0.35]
=0.5+0.1368
=0.6368
P(project will be completed in 27 days)=63.7%
PROBLEM:-10
The time estimate in month of all the activities of the project are
given below.
Activity A m b
1-2 0.8 1.0 1.2
2-3 3.7 5.6 9.9
2-4 6.2 6.6 15.4
3-4 2.1 2.7 6.1
4-5 0.8 3.4 3.6
5-6 0.9 1.0 1.1
i) find the expected duration and S.D to each activity.
ii) construct the project network.
iii)Determine the critical path, expected length and expected variance of
the project length.
iv)What is the probability that the project will be completed.
a) two month later the expected
b)three month before the expected
c)what new day has above 90% chances of being met?
SOLUTION:-
Activity A m b te SD σ2
1-2 0.8 1.0 1.2 1 0.067 0.0048
2-3 3.7 5.6 9.9 6 1.033 1.0677
2-4 6.2 6.6 15.4 8 1.533 2.3511
3-4 2.1 2.7 6.1 3.16 0.667 0.4448
4-5 0.8 3.4 3.6 3 0.467 0.2170
5-6 0.9 1.0 1.1 1 0.333 0.001
E1=1,L1=1 E3=7,L3=7
6
2 3
1 8 3.16 E5=13.16, L5=13.16
1 4 5 6
3 1
E1=0, L1=0 E4=10.16, L4=10.16 E6=14.16, L6=14.16
Critical path 1-2-3-4-5-6 and expected length of the critical path is 14.16
Expected variance of the critical path1-2-3-4-5-6 is 1.733
(=0.004+1.067+0.444+0.217+0.001)
SD=(1.733)1/2=1.31
(iv)
(a)
Let tS be the project completion time
P(Project will be completed two month later)=P(tS<= 14.16+2)
= Pt s 16.16
= Pt s t e 16.16 14.16
t s te 2
= P
1.31
= p Z 1.53
= p[ Z 0] P[0 Z 1.53]
=0.5+0.4370
=0.937=93.7%
(iv)
(b)
P(Project will be completed before three month than expected)
= Pt s 11.16
t s t e 11.16 14.16
= P
1.31
= PZ 2.29
P[ Z 2.30] P[2.30 Z ]
= P[0 Z ] P[0 Z 2.30]
=0.5-0.4893
=0.0107
=1.07%
(iv)
(c)
=Standard diviation of the project length
ts= due date, schedule date
te=expected duration of the project length
ts te ts 14.16
z
1.31
Given:
t 14.16
p Z s =90%=0.9
1.31
t 0 14.16
p[ Z 0] P[0 Z ] =0.9
1.31
t s 14.16
P[0 Z ] =0.4
1.31
t s 14.16
P[0 Z ] = P[0 Z 1.287]
1.31
t s 14.16
1.28
1 .303
Ts=15.82 month nearly.
UNIT-V
Non-linear programming method( NLPP or NLP )
If either objective function or constraints are non linear, then it is called non -
linear programming problem. it in short written by NLP or NLPP.
Note:-
Linearity means the variables should be of degree one and their are not
multiplied together.
Local minimum/ Relative minimum
A function of one variable f(x) is said to have a local minimum at x=x0, if f ''(x0)>0
Local maxima/ Relative maxima
A function of one various f(x) is said to have local maxima at x=x0, if f ''(x0)<0
Note:-
If f ''(x)=0, neither maximum nor minimum exist for f(x).
Maxima and minima using higher order derivatives.
When the function consist of more than one variable, we use the hessian matrix
formula.
2 f
H ( x0 )
x y
i j x x0
To decide the nature of function f, we use the following
(I) f(x) is relative minimum at x=x0 ,if H(x0) is positive definite.
(II) f(x) is relative maximum at x=x0 , if H(x0) is negative definite.
(III) There exist a point of inflexion at x=x0 (saddle point), if H(x0) is indefinite.
Necessary and sufficient condition for the existence of
local maxima and minima and point of inflexion.
Necessary condition Sufficient condition Nature of function Conclusion
f’(x0)=0 f’’(x0)=.... Concave Local maximum at
=f(n-1)(x0)=0 and x=x0
f(n)(x0)<0, n even
f’(x0)=0 f’’(x0)=.... Convex Local minimum at
=f(n-1)(x0)=0 and x=x0
f(n)(x0)>0, n even
f’(x0)=0 f’’(x0)=.... - Point of inflexion at
=f(n-1)(x0)=0 and x=x0
f(n)(x0) 0, n even
Formation of non-linear programming problem(NLP)
Problem:-01
An engineering company has received a rush order for a maximum number of two
types of items that can be produced and transported during a two weeks period. The
profit in 100rs on this order is related to number of each type of item manufactured by
the company and is given by 12x1+10x2 – x12-x22+61 where x1 is the number of units in
1000 of type I, x2 is the number of units in 1000 of type II item . because of other
commitments over the next two weeks. The company has available only 60 hours in the
shifting and packing department if is estimated that every 1000 units of the type I and
type II item will require 20hrs and 30hrs respectively in the shifting and packing
department. Given the above information, how many units of each type of item should
the company produce, in order to maximum the profit.
Solution:-
Here x1 is the number of units in 1000 of type I
and x2 is the number of units in 1000 if type II
The profit is given by 12x1+10x2 – x12-x22+61
i.e Max Z= 12x1+10x2 – x12-x22+61
subject to constraints,
Since shifting and packing a unit of item of type I require 20hr
Total time required for shifting and packing of type I item = 20x1
Since shifting and packing a unit of item of type I require 20hr
Total time required for shifting and packing of type II item= 30x2
Total time required for shifting and packing of type I and type II item=20x1+30x2
Maximum available time for shifting and packing type I and type II items =60hr
20x1+30x2≤60
x1,x2≥0
In this problem object function is non-linear and constraints are linear
Therefore the given problem is non- linear programming problem.
Problem:-02
The company sells two types of items A and B. Item A sells for rs.25 per unit. No
quantity discount is given. The sales revenue for item B, decreases as the number of its
unit sold increases and is given by,m30x2-0.3x22, where x2nis the number of unit sold of
item B.The marketing department has only 1200 hrs available for distributing this
items in the next year, further the company estimates the sales time function is non
linear and is given by, x1+0.2x12+3x2+0.35x22, the company can produce 6000 units of
item A and B for sales in the next year, given the above information, how many unit of
each type of item should the company produce.
Solution:-
Here x1 is the number of units sold of type A
and x2 is the number of units sold of type B.
Total profit= sales revenue of item A+ sales revenue of item B
Max Z= sales revenue of item A+ sales revenue of item B
Since Item A sells for rs.25 per unit
Sales revenue of item A = 25x1
Sales revenue of item B=30x2-0.3x2 2
Max Z=25x1+30x2-0.3x22
Since the marketing department has only 1200 hrs for distributing this item next year.
Sale time function is given by x1+0.2x12+3x2+0.35x22
x1+0.2x12+3x2+0.35x22≤1200
The company produce 6000 units of item A and B.
x1+x2=number of item A and B sold
i.e. x1+x2≤ 6000
and x1,x2≥0
Since both objective function and conditions are non linear, therefore It is a NLP.
SOLUTION OF NLP BY GRAPHICAL METHOD
Problem:=01
Solve the following NLP using graphical method
Max Z=2x1+3x2
Sub to constraints
x12+x22≤ 20,
x1.x2≤ 8
and x1,x2≥0
Solution:-
Let us plot the constraints in graph
First constraints becomes, x12+x22= 20
i.e we have to draw the circle with centre (0,0) radius 20
The second constraints becomes, x1.x2=8
i.e we have to draw the rectangular hyperbola
The shaded region is called feasible region
To find the intersection point
solving x12+x22= 20 and x1.x2=8
8
Substitute x1 , we get
x2
64 2
2
x2 20
x2
64+x24= 20x22
x24- 20x22-64=0
(x22)2-20x22+64=0
w2-20w+64=0, w=x22
− ±√ −4
w=
2
20 ± √200 − 256
w=
2
20 ± √144
w=
2
w = 10 ± 26
w=16,4
x22=16,4
x2=4,-4,2,-2 (negative values should be avoided, since x1,x2 are nonnegative)
Sub x2=4,2 in x1x2=8, we get
x1=2,4
i.e the intersection points are (2,4)and (4,2)
Let us find x1,x2 within the region OABCD when the value of objective function is
maximum .
Let us locate the point (x1,x2) using ISO profit function approach
ISO- profit method
Let 2x1+3x2=k
Let k=0
Draw 2x1+3x2=0
Let k=6
Draw 2x1+3x2=6
Let k=12
Draw 2x1+3x2=12
Let k=14
Draw 2x1+3x2=14
Let k=16
Draw 2x1+3x2=16
Draw parallel objective function lines for different constant values of K.
Starting with 0 and so on we find that the ISO profit line with k=16 such as the extreme
boundary points c(2,4) where the value of Z is maximum.
Hence the optimum solution is x1=2, x2=4.
Note:-
In the above problem the objective function line 2x+3y=14, intersecting with
point (4,2), but the next objective function line 2x+3y=16 , intersecting with point (2,4).
Among the points (2,4) gives the maximum for objective function.
Problem:-02
Solve graphically the following NLP
Max Z=8x1-x12+8x2-x22
Subject to constraints
x1+x2≤ 12
x1-x2≥4 and
x1,x2≥0
Solution:-
Let us plot the constraints in graph
Let us draw the first constraint x1+x2= 12
x1=0 x2=12
x2=0 x1=12
It is a line joining two points(0,12) &(12,0)
Let us draw the second constraint x1-x2=4
x1=0 x2=-4
x2=0 x1=4
It is the line joining two points (0,-4)&(4,0)
To find the intersection points
x1+x2= 12, x1-x2=4
Add the above two equations, we have 2 x1 =16
=>x1=8
Substitute the value of x1, we have x2=4
Therefore the intersection point is (8,4)
The shaded region is the feasible region.
Let us plot the objective function
8x1-x12+8x2-x22=0
2.4x1-x12+2.4x2-x22=0
-(x12-2.4x1+42-42)-( x22-2.4x2+42-42)=0
-(( x1-4)2-16)-((x2-4)2-16)=0
-( x1-4)2+16-(x2-4)2+16=0
( x1-4)2+(x2-4)2=32
It is a circle with centre (4,4) and radius (32)1/2
The feasible region is the convex region, the optimum point (x1, x2) must be
somewhere in the convex region A,B,C also it would be the at which the side of the
convex region with tangent to the circle
Z=8x1-x12+8x2-x22
To find the optimum point (x1, x2)
We use gradient method
The gradient of the tangent to the circle can be obtained by differentiating the
equation w.r.t x1 and equating to zero
8x1-x12+8x2-x22=0
2
dx2 dx2
8 2 x1 8 0
dx1 dx1
2
dx dx dx
8 2 x1 8 2 2 . 2 0
dx1 dx2 dx1
2
dx2 dx2 dx2
8 2 x1 8 . 0
dx1 dx2 dx1
dx2 dx
8 2 x1 8 2 x2 . 2 0
dx1 dx1
dx2 2 x1 8
______III
dx1 8 2 x2
Gradient of the line Gradient of the line
x1+x2= 12 x1-x2=4
dx2 dx2
1+ =0 1- =0
dx1 dx1
dx2 dx2
=-1--------IV =1_____V
dx1 dx1
Sub (IV) in (III)
2 x1 8
-1=
8 2 x2
-8+2x2-2x1+8=0
2x2-2x1=0
x2-x1=0---------VI
x1=x2
Solve (VI) and (I)
x1+x2= 12
x2-x1=0
2x2=12
x2=6
x1=6
The intersection point is (6,6)
it does not lies in feasible region, therefore it is not a optimum point
Sub (V)&(III)
2 x1 8
1
8 2 x2
8-2x2-2x1+8=0
2x2+2x1-16=0
x1+x2=8 -----VII
solve (VII)&(II)
x1+x2=8
x1-x2=4
___________
2x1=12
x1=6
x2=2
The intersection point is (6,2)
It lies in the feasible region and satisfy both the constraints
Hence the optimum solution is x1=6,x2=2 and Max Z= 24
Problem :-3
Solve the following NLP problem.
Min Z = x12+x22
Subject to
x1+x2≥ 8
x1+2x2≥ 10
2x1+x2≥ 10
x1,x2≥ 0
Solution:-
Let us plot the constraints in graph
Let us draw the first constraint x1+x2= 8______(1)
x1=0 x2=8
x2=0 x1=8
It is the line joining the points (0,8)&(8,0)
Let us draw the second constraint x1+2x2= 10_____(2)
x1=0 x2=5
x2=0 x1=10
It is the line joining the points(0,5)&(10,0)
Let us draw the third constraint 2x1+x2= 10________(3)
x1=0 x2=10
x2=0 x1=5
It is the line joining the points (5,0)&(0,10)
The required region is unbounded convex region
To find the intersection points
Solve (2)&(3)
2x1+4x2= 20
2x1+x2= 10
_______________
3x2=10
x2=3.3
therefore x1=3.4
The intersection points is E(3.4,3.3)
Solve (3)&(1)
2x1+x2= 10
x1+x2= 8
_______________
x1=2
x2=6
The intersection point is C(2,6)
Solve (1)&(2)
x1+x2= 8
x1+2x2= 10
_________________
-x2=-2
x2=2
x1=6
The intersection point is B (6,2)
The shaded region is feasible region.
Let us draw the objective function in graph
Let x12+x22 =k
The objective function is the circle with centre (0,0)
The optimum point (x1, x2) must lie in the feasible convex region also it would be at
which the side of the convex region with tangent to the x12+x22=k
To find optimum point
We use gradient method
The gradient of the tangent to the circle can be obtained by differentiating the
equation w.r.t x1 and equating to zero
x12+x22=0
2
dx
2 x1 2 0
dx1
2
dx dx
2 x1 2 . 2 0
dx 2 dx1
dx2 dx2
2 x1 2 x2 . 0
dx2 dx1
dx2 x
1 ________(4)
dx1 x2
Gradient line Gradient line Gradient line
x1+x2= 8 x1+2x2= 10 2x1+x2= 10
dx 2 dx2 dx 2
1 0 1 2 0 2 0
dx1 dx1 dx1
dx 2 dx2 1 dx 2
1 -----(5) -----(6) 2 ------(7)
dx1 dx1 2 dx1
Sub (5) in (4)
x1
1
x2
-x2=-x1
x1-x2=0-------(8)
solve (8)&(1)
x1-x2=0
x1+x2=8
__________
2 x1=8
x1=4
x2=4
The intersection point is (4,4)
Sub (6) in (4)
1 x
1
2 x2
-x2=-2x1
-x2+2x1=0---------(9)
Solve( 9)&(2)
2x1-x2=0
2x1+4x2= 20
____________
5 x2=20
x2=4
x1=2
The intersection point is (2,4)
Sub (7) in (4)
x1
2
x2
-2x2+x1=0--------(10)
Solve (10)&(3)
-4x2+2x1=0
2x1+x2= 10
____________________
-5 x2=10
x2=2
x1=4
The intersection point is (4,2)
Since the (2,4),(4,2)does not lie in the feasible region and (4,4) lie in the feasible
region
Therefore the optimum solution is x1=4, x1=4 and Max Z =32
Note:-
In the above problem the final optimum solution is at (4,4) and z=x12+x22=32.
If we plot this objective function, we get the clear picture of the optimum solution.
Problem:-04
Solve the following NLP
min Z =10x1- x12+10x2-x22
subject to
x1+x2≤ 12
x1-x2≤ 6
x1,x2≥ 0
Solution:
Let us plot the constraints in graph
Let us draw first constraint x1+x2= 12------(1)
x1=0 x2=12
x2=0 x1=12
It is the line joining the points(0,12)&(12,0)
Let us draw the second constraints x1-x2= 6------(2)
x1=0 x2=-6
x2=0 x1=6
It is a line joining the points(0,-6)&(6,0)
To find the intersection points
Solve (1)&(2)
x1+x2= 12
x1-x2= 6
___________________
2 x2=6
x2=3
x1=9
The intersection point is C(9,3)
Let us draw the objective function
let 10x1- x12+10x2-x22=0
2.5x1- x12+2.5x2-x22=0
-(x12-2.5x1+52-52)-(x22-2.5x2+52-52)=0
-((x1-5)2-25)-((x2-5)2-25)=0
(x1-5)2-25+(x2-5)2-25=0
(x1-5)2+(x2-5)2=50
It is a circle with centre (5,5) radius 50
The feasible region is the convex region the optimum point(x1,x2) must be
somewhere in the convex region A,B,C also it would be at which circle side of the convex
region with tangent to the circle 10x1- x12+10x2-x22=k.
To find optimum point
We use gradient method
The gradient of the tangent to the circle can be obtained by differentiating the
equation w.r.t x1 and equating to zero
10x1- x12+10x2-x22=0
2
dx dx
10-2x1+10 2 2 0
dx1 dx1
2
dx dx
10 2 x1 2 2 x 2 2 0
dx1 dx1
dx 2 2 x1 10
-------(3)
dx1 10 2 x 2
Gradient of line Gradient of line
x1+x2= 12 x1-x2= 6
dx 2 dx 2
1 0 1 0
dx1 dx1
dx 2 dx2
1 -----(4) 1 -------(5)
dx1 dx1
Sub (4)in (3)
2 x1 10
1
10 2 x 2
-10-2x2-2x1+10=0
2x1-2x2=0
x1-x2=0-------(6)
solve (6)&(1)
x1+x2= 12
x1-x2=0
______________
2x1=12
x1=6
x2=6
The intersection point is (6,6)
It is not in the feasible region, therefore it is not a optimum point
Sub(5) in (3)
2 x1 10
1
10 2 x 2
10-2x2-2x1+10=0
2x2+2x1-20=0
x1+x2=10-----(7)
Solve (7)&(2)
x1+x2=10
x1-x2= 6
_______________
2x1=16
x1=8
x2=2
The intersection point is (8,2)
This point lies in the feasible region and satisfy both the constraint.
Hence the optimum solution is x1=8, x2=2 and max Z=32
Constrained Optimization
The problem of optimizing a continuous and differential function subject to
constraints may be defined as:
Optimize Z=f(x1,x2,...xn)
Subject to the constraints
gi(x1,x2,....xn){<=, >=, =} bi, for i=1,2,3....m
and xj>=0; j=1,2,3...n.
Note
Constrained optimization in matrix notation as follows
Optimize (Max or Min) z=f(x)
subject to constraints
hi(x) {<=,>=,=} 0, and x>=0 for all i=1,2,3...m
where hi(x)=gi(x)-bi
To solve such type of problem, we make use of Lagrange Multiplier method (in
general Kuhn tucker conditions)
Note:-
There are two methods of solution used for solving NLP
(I) Kuhn Tucker Method or Lagrange's Multipliers method
(II) Beale's method
(III) Wolf Method
Kuhn Tucker method of solution to NLP
Problem:-01
Use Graphical Method to Minimum the Distance of the Origin from the Convex
region bounded by the following Constraint.
x1 + x2 ≥ 4
2x1 + x2 ≥5
x1 ,x2 ≥ 0
Verify Kuhn-Tuber Necessary Condition Hold at the point of Minimum Distance.
Solution:-
Let us Draw The Line,
x1 + x2 = 4 --------1
x1 = 0 , x2 = 4
x2 = 0, x1 = 4
The equation (1) is the line joining the points (0,4)& (4,0)
Let us Draw the Line
2x1 + x2 = 5 -------2
x1 = 0 x2 = 5
x2 = 0 x1 =2.5
The equation (2) is the line joining the points (0,5)& (2.5,0)
To find the intersection points
Solve 1 & 2:
x1 + x2 = 4
2x1 + x2 = 5
____________
-x1 = -1
x1 = 1
x2 = 3
The intersection point is (1,3)
The feasible region is a convex bounded region, the problem is of minimizing the
distance of solution point from the origin . i.e we have to minimum the radius of the
circle whose center 0 and touching the feasible region.
Therefore the objective function is
Min z = x12 + x2 2
Gradient of objective function with respect to x1
x12 + x2 2=0
2
dx
2x1 + 2 = 0
dx1
2
dx dx
2x1 + 2 . 2 = 0
dx2 dx1
dx2
2x1 + 2x2 =0
dx1
dx2 x1
--------3
dx1 x2
Gradient Line Gradient Line
x1 + x2 = 4 2x1 + x2 = 5
dx2 dx2
1+ =0 2 0
dx1 dx1
dx2 dx2
= -1 -------- 4 2 5
dx1 dx1
Sub 4 in 3:
x1
-1 =
x2
-x2 + x2 = 0 -----------6
Solve 5 & 7:
x1 - x2 = 0
x1 + x2 = 4
2x2 = 4
x2 = 2
x1 = 2
The solution point is (2,2)
Sub 5 in 3
x1
-2 =
x2
-2x2 + x1 = 0 ---------- 7
Solve 7 & 2 :
-2x2 + x1 = 0
x1 + 2x = 10
___________________
5x1 = 10
x1 = 2
x2 = 1
The solution point is (2,1)
Clearly the solution point (2,1)does not satisfies the first constraint in the given
problem, (2,1) does not lines in feasible region.
Clearly the solution point (2,2) satisfies all the constraints in the given problem,
therefore (2,2) lies in the feasible region.
Verification of Kuhn Tucker Conditions
Since Min f (x) = x12 + x22
x1 + x2 = 4,
=>x1 + x2 -4 =0
Let h1 (x) = x1 + x2 -4
2x1 + x2 = 5
2x1 + x2 - 5=0
Let h2 (x) = 2x1 + x2 -5
Kuhn-tucker Condition for Minimization NLP
Condition -I
f ( x) 2 hi ( x)
i 0 for 1, 2
x J i 1 x j
For j = 1,
f ( x) 2 hi ( x)
i 0
x1 i 1 x1
2 2
(x1 x2 ) h1 x h ( x)
1 2 2 0
x1 x1 x1
2x1 - 1 x1 x 2 4 2 2 x1 x 2 5 0
x1 x1
2x1 - 1 22 0
2x1 - 1 2 2 0 --------------(1)
For j =2,
f x 2
h i x
x2
i1
i
x2
0
x12 x 22 h x
1 1
h x
2 1 0
x 2 x 2 x 2
x1 x 2 4 2 x1 x 2 5
2x2 - 1 2 0
x 2 x 2
2x2 - 1 2 0
2x1 – 1 - 2 = 0 ------------------- (2)
Condition -II.
i hi (x) = 0, for i = 1,2
For i = 1
1 h1 (x) = 0
1 (x1 + x2 - 4) = 0 -------------------- (3)
For i = 2
2 h2 (x) = 0
2 (2x1 + x2 - 5) = 0 ------------------- (4)
Condition -III.
hi(x) 0 fori=1,2.
For i = 1
h1 (x) 0
x1 + x2 – 4 0 -------------------------- (5)
For i = 2
h2 (x) 0
2x1 + x2 – 5 0 ----------------------- (6)
Conditions -IV.
I 0, for I = 1,2
I 0, -------------------(7)
2 0 --------------------(8)
Solve (1),(2)
2x1 - 1 - 2 2 = 0 [sub x1 =2, x2=2 Optimum]
2x2 - 1 - 2=0
1 + 2 2 = 4
1+ 2=4
____________
2 2 = 0
2 =0
1=4
Therefore ( 1 , 2 )= (4,0)
Therefore the solution (x1, x2, 1 , 2)= (2,2,4,0) satisfies all the equation from
(1) –(8).
Hence the Kuhn-tucker conditions are satisfied at the optimal solution point (2,2).
Problem:-01
Use Beale's method to solve quadratic programming problem.
Max Z =2x1+3x2-2x22
subject to
x1+4x2≤ 4
x1+x2≤ 2
and x1,x2≥0
Solution:-
Let us add non-negative slack variables s1,s2 in the given constraints
x1+4x2+S1= 4
x1+x2+S2=2
Initial Basic Feasible Solution is
S1=4
S2=2
XB =(s1,s2)=(4,2) [ Basic variables]
XN=(x1,x2)=(0,0) [Non basic variables]
YB XB x1 x2 S1 S2
S1 4 1 4 1 0
S2 2 1 1 0 1
Let us rewrite constraints terms of non basic variable
From the first row in the table
S1=4-x1-4x2 [ x1, x2 are NB variables, and S1, S2 are Basic variables]
From the second in the table
S2=2-x1-x2
Let us rewrite the objective function in terms of non basic variables
Z =2x1+3x2-2x22
Let us calculate partial derivative of Z with respect to non-basic variable x1
z
=2
x1
Let us calculate partial derivative of Z with respect to non-basic variable x2
z
=3-4x2
x 2
z
2 1
x1 x1 0, x2 0
i.e there will be increase in z when x1 increases
z
3 2
x2 x1 0, x2 0
i.e there will be increase in z when x2 increases
Thus there is greater increase in z with respect to increase in x2 as compared to
increase in x1.
Rule:-
If 1 & 2 <0, optimal solution,
if at least one greater than 0, non-optimal solution .
Since both are positive , therefore the solution is not optimal.
Let us choose the variable to enter the basis
We choose x2 to enter into the basic (due to most positive value of alpha) to
improve the value of objective function.
YB XB x1 x2 S1 S2 = /
S1 4 1 4 1 0 4/|4|=1
S2 2 1 1 0 1 2/|1|=2
To choose the variable leave the basis
x
min Bi yij 0
yij
I. 1
min xBi y 0
ij
| yij |
=min{1,2}
=1
Since it is not desirable to increase the value of the non basic variable x2 beyond the
z
point where become zero.
x2
3-4x2=0
i.e x2 can not be increased beyond 3/4, otherwise x2 will be negative.
3
2
4
A critical value of x2 is given by
x2 min{ 1 , 2 }
=min{1,3/4}
x2=3/4 (corresponding to 2 )
x2= 2
Therefore case II has to be applied
We have to introduce the new free variable its value is zero in the next feasible
solution.
Let us introduce free variable u1 (unrestricted) and the corresponding
z
constraint is u1=3-4x2 [ x2 enters the basis, therefore u1= ]
x 2
4x2+ u1=3 ,
We have to add this new constraint in the given problem
YB XB X1 x2 S1 S2 u1
S1 4 1 4 1 0 0
S2 2 1 1 0 1 0
u1 3 0 [4] 0 0 1
Since x2 enter the basis and u1 leaves the basis. Use usual simplex calculation
gives the following table values.
YB XB X1 X2 S1 S2 u1
S1 1 1 0 1 0 -1
S2 5/4 1 0 0 1 -1/4
x2 ¾ 0 1 0 0 +1/4
In the column u1 multiply the values by -1 [ this is only when we remove free
variable from the last row, not for all table]
YB XB X1 X2 S1 S2 u1
S1 1 1 0 1 0 +1
S2 5/4 1 0 0 1 +1/4
x2 ¾ 0 1 0 0 -1/4
Check for optimality
XB=(s1,s2,x2)=(1,5/4,3/4) [ Basic variables ]
XN=(x1,u1)=(0,0) [Non basic variables]
Let us rewrite the constraints in non basic variables
From the above table first row
x1+s1+u1=1
write the B.V in-terms of N.B.V
s1=1-x1-u1
Similarly from the above table second row
1 5
x1+s2+ u 1
4 4
write the B.V in-terms of N.B.V
5 1
s2= x1 u1
4 4
Also from the above table third row
1 3
x2 u1
4 4
write the B.V in-terms of N.B.V
3 1
x2 u1
4 4
Let us rewrite the objective function in-terms of non basic variable
Z =2x1+3x2-2x22
2
3 u 3 u
z=2x1+3 1 2 1
4 4 4 4
9 u12
Z= 2 x1
8 8
Let us partially differentiate Z with respect to non basic variables x1 and u1
z z 2u1 u1
2
x1 u1 8 4
z z 0
2 1 0 2
x1 x1 0,u1 0 u1 x1 0,u1 0 4
1 0 .i.e there will be an increment in z when x1 increases
2 0 i.e there is no change in z when u1 increase.
Since 1 0 , thus the above solution is not optimal.
Let us choose the variable enters the basis
1 2 0 (corresponding to the variable x1), therefore we choose x1 to enters the basis
YB XB X1 X2 S1 S2 u1 = /
S1 1 1 0 1 0 +1 1/|1|=1
S2 5/4 1 0 0 1 +1/4 (5/4)/|1|=5/4
x2 ¾ 0 1 0 0 -1/4 -
To find the variable leave the basis
1 5
I. 1 min ,
1 4
=1 (corresponding to s1)
z
II. If 0, then the maximum value of x1 can be obtained,and 2 x1
x1
z
Here 20
x1
z
Let 2 2
x1
x1 min{ 1 , 2 }
=min{1,2}
=1
x1= 1 (corresponding variable s1)
Thus case I has to be applied
Therefore s1 leaves the basis
YB XB X1 X2 S1 S2 u1
S1 1 [1] 0 1 0 +1
S2 5/4 1 0 0 1 +1/4
x2 ¾ 0 1 0 0 -1/4
Usual simplex procedure apply
YB XB X1 X2 S1 S2 u1
x1 1 1 0 1 0 1
S2 ¼ 0 0 -1 1 -3/4
x2 ¾ 0 1 0 0 -1/4
[ Note Here do not multiply the last column u1by -1]
Check for optimality again
XB=(x1,s2,x2)=(1,1/4,3/4) [ Basic variables]
XN=(s1,u1)=(0,0) [Non basic variables]
From the first row in the above table
x1+s1+u1=1
x1=1- s1-u1
From the second row in the above table
3 1
-s1+s2-
4 4
1 3
s2= s1
4 4
From the third row in the above table
1 3
x2 u1
4 4
3 1
x2= u1
4 4
objective function
Z =2x1+3x2-2x22
25 1
z 2 s1 2u1 u12
8 8
Let us partially differentiate with respect to s1 and u1
z z
2 , 2
s1 u1
Since 1 0 , 2 0
Therefore the solution is optimal
Hence the optimal solution is
x1=1, x2=3/4 and max z=25/8.
Note:-
Since XB=( x1, x2)=(1,3/4) and XNB=( s1, u1)=(0,0)
25 1 25 1
z 2 s1 2u1 u12 2(0 ) 2(0 ) (0) 2 25 / 8
8 8 8 8
Note:-( Simple procedure as follow)
Step:-01
Write the given quadratic programming problem in standard form by adding
quadratic slack variables .
Step:-02
Form the Lagrange's function for finding Kuhn tucker conditions and get set of
equations.
Step:-03
Add artificial variable in the new set of equation and these becomes new
constraints for the newly formed LPP
Create the new objective function using artificial variables.
The collection of new objective function and constraints form new LPP.
Step:-04
Apply two phase simplex method and check for optimality.
Problem:-01
Use wolf method to solve quadratic programming problem
Max Z=4x1+6x2-2x12-2x1x2-2x22
Subject to constrain
x1+2x2≤2
x1,x2≥0
Solution:-
Step:-01
Note:-
(i) Convert the objective function in to maximization form
Max Z=4x1+6x2-2x12-2x1x2-2x22, it is already in maximization form
(ii) Write all the constraints in '<=' type
x1+2x2≤2, it is already in <= type
Let us convert the non - negative constraints as follows
-x1<=0
-x2<=0
The standard form of quadratic LPP
x1+2x2+q12=2 [ q12 is quadratic slack variable]
Newly added constrains are
-x1+r12=0 and -x2+r22=0 [ r12, r22 are quadratic slack variable]
and x1, x2, q12 , r12, r12≥0
Step:-02
We construct the Lagrange's function L(x,q,r,λ,μ)
Here λ,μ are called Lagrange's multiplier or constant.
L (x1,x2,q1,r1,r2, λ1,μ1, μ2)= 4x1+6x2-2x12-2x1x2-2x22- λ1(x1+2x2+q12-2)
- μ1(-x1+r12)- μ2(-x2+r22)
The necessary and sufficient condition for Kuhn tucker are
( L) 0
x1
4 4 x1 2 x2 1 1 0
( L) 0
x2
6 2 x1 4 x2 22 2 0
L
0
q1
1q1 0
Multiply both sides by q1
2
1q1 0
1 s1 0 [Assume s1=q12]
L
0
1
2
x1 2 x2 q1 2 0
L
0
1
2
x1 r1 0
2
x1 r1
L
0
2
2
x2 r1 0
2
x2 r1
L
0
r1
2 1r1 0
Multiply both by r1 and divide by 2
2
1r1 0
2
1 x1 0 [ x1 r1 ]
L
0
r2
2 2 r2 0
Multiply both sides by r2 and divide by 2
2
2 r2 0
2
2 x2 0 [ x2 r2 ]
Thus new set of equations( Kuhn tucker conditions) are
4 x1 2 x 2 1 1 4 -------------(1)
2 x1 4 x2 21 2 6 ------------(2)
x1 2 x2 s1 2 -------(3) [Here s1=q12]
{1 s1 0, 1r1 0, 2 r2 0} ----------(4) ( this is called complimentary conditions)
and x1, x2, 1 , 1 , 2 , s1 0
Step:-03
Introduce artificial variable A1 and A2 in the first two constraints
respectively and form new objective function .
The modified LP problem becomes
Max Z*=-A1-A2
Add artificial variable only if it does not contain quadratic slack/surplus
variable.
4 x1 2 x2 1 1 A1 4 [it does not contain slack/surplus variable]
2 x1 4 x2 21 2 A2 6 [it does not contain slack/surplus variable]
x1 2 x2 s1 2 [No need to add, it contain slack variable s1]
where x1,x2, λ1, μ1,μ2, A1,A2 ,s1≥0
Initial basic feasible solution of LPP
Let x1=x2=λ1=μ1=μ2=0, we get A1=4,A2 =6, s1=2,
Therefore Max Z*=-4-6=-10
Initial simplex table
Cj 0 0 0 0 0 0 -1 -1
CB XB x1 x2 λ1 μ1 μ2 s1 A1 A2
-1 A1=4 [4] 2 1 -1 0 0 1 0
-1 A2 =6 2 4 2 0 -1 0 0 1
0 s1=2 1 2 0 0 0 1 0 0
Zj 6 6 3 -1 -1 0 1 1
Zj-Cj -6 -6 -3 1 1 0 0 0
Since some Zj -Cj <=0, therefore the solution is not optimal
Rule :- (To select the variable enter into basis)
Here x1,x2 and λ1 are eligible to enter the basis, λ1 cannot enter the basis since
the complementary condition λ1s1=0 does not hold.
Since x1 and x2 equally competitive and complementary conditions
x1μ1 =0, x2μ2 =0 are satisfied
We select x1 enters the basis
Rule :-(To select the variable leaves the basis)
We have to make all A1, A2 equal to zero, i.e it should become non basic
variable. So first we select the variable A1 leaves the basis.
Apply usual simplex procedure , we get
Cj 0 0 0 0 0 0 -1
CB XB x1 x2 λ1 μ1 μ2 S1 A2
0 x1=4 1 ½ 1/4 -1/4 0 0 0
-1 A2 =4 0 3 3/2 1/2 -1 0 1
0 s1=1 0 3/2 -1/4 1/4 0 1 0
Zj 0 3 3/2 1/2 -1 0 1
Z*=-4 Zj -Cj 0 -3 -3/2 -1/2 1 0 -1
[Note: Once A1 leaves the basis, it could not enter basis again, the
corresponding column need not be written.]
Since some Zj -Cj <=0 , therefore the above solution is not optimal.
Rule :- (To select the variable enter into basis)
Here x2, λ1 and μ1are eligible to enter the basis,
λ1 cannot enter the basis since the complementary condition λ1s1=0 does not
hold.
μ1 cannot enter the basis since the complementary condition x1μ1 =0does not
hold.
x2 can enter the basis and the complementary conditions x2μ2 =0 hold
We select x2 to enters the basis.
Rule :-(To select the variable leaves the basis)
If we select A2 as leaving variable, then in the next table s1 remains in
the basic variable column and Cj-Zj value of λ1 will be negative, so in the next
table entering variable will be λ1, but you can not enter since complementary
condition λ1s1=0 does not hold. i.e we stuck at this stage could not move further.
So we select s1 as leaving variable.
Cj 0 0 0 0 0 0 -1
CB XB x1 x2 λ1 μ1 μ2 s1 A2
0 x1=2/3 1 0 1/3 -1/3 0 -1/3 0
-1 A2 =2 0 0 [2] 0 -1 -2 1
0 x2=2/3 0 1 -1/6 1/6 0 2/3 0
Zj 0 0 2 0 -1 -2 1
Z*=2 Zj -Cj 0 0 -2 0 1 2 0
Since Z3-C3 =-2<0, therefore the above table is not optimal
Rule :- (To select the variable enter into basis)
Here λ1 are eligible to enter the basis,
λ1 can enter the basis since the complementary condition λ1s1=0 does not hold.
We select λ1 to enters the basis.
Rule :-(To select the variable leaves the basis)
We have only one variable to leave the basis A2
So we select A2 as leaving variable.
Cj 0 0 0 0 0 0
CB XB x1 x2 λ1 μ1 μ2 S1
0 x1=1/3 1 0 0 -1/3 -1/6 0
1 λ1=1 0 0 1 0 -1/2 -1
0 x2=5/6 0 1 0 1/6 -1/2 1/2
Zj 0 0 0 0 0 0
Z*=0 Zj -Cj 0 0 0 0 0 0
[Note: Once A2 leaves the basis, it could not enter basis again, the
corresponding column need not be written.]
Since all Cj- Zj>=0, therefore the above solution is optimal
The optimum solution is
x1=1/3, x2=5/6, λ1=1,μ1=μ2=s1=0 Min Z*=0
This solution also satisfies the complementary conditions λ1 S1=0, μ1 x1=0,
μ2 x1=0 and the restriction on the sign of Lagrange's multipliers λ1, μ1 and μ2
The optimum solution for the given quadratic problem is
x1=1/3, x2=5/6, λ1=1,μ1=μ2=s1=0
Max Z=4(1/3)+6(5/6)-2(1/3)2-2(1/3)(5/60)-2(5/6)2= 25/6
Problem:-2
Apply Wolfe method to solve the quadratic programming problem
Max Z=2x1+x2-x12
Subject to constrains
2x1+3x2≤6
2x1+x2≤4
and x1,x2≥0
Solution
The standard form of quadratic programming problem
Max Z=2x1+x2-x12
2x1+3x2+q12=6 [ add quadratic slack variable q12]
2x1+x2+q22=4 [add quadratic slack variable q22 ]
Newly added constraints are
-x1+r12=0 and -x2+r22=0 [add quadratic slack variables r12 ,r22 ]
and x1, x2, q12,q22 , r12, r12≥0
We construct the Lagrange's function L (x,q,r,λ,μ)
L (x,q,r, λ ,μ)= 2x1+x2-x12- λ1(2x1+3x2+q12-6)- λ2(2x1+x2+q22-4)
- μ1(-x1+r12)- μ2(-x2+r22)
The necessary and sufficient conditions (Kuhn tucker conditions) are
( L) 0
x1
2 2 x1 21 22 1 0
( L) 0
x2
1 31 2 2 0
L
0
1
2
2 x1 3 x2 q1 6 0 [ Let q12=s1 ]
2 x1 3x2 s1 6 0
L
0
2
2
2 x1 x2 q2 4 0
2 x1 x2 s2 4 0 [ Let q22=s2 ]
L
0
q1
1 (2q1 ) 0
Multiply both sides by q1 and divide by 2
2
1q1 0
1s1 0 [ Since q12=s1 ]
L
0
q2
2 (2q2 ) 0
Multiply both sides by q2 and divide by 2
2
2 q2 0
2 s2 0 [ Since q22=s2 ]
L
0
1
2
x1 r1 0
L
0
2
2
x2 r2 0
L
0
r1
2 1r1 0
Multiply both sides by r1 and divide by 2
2
1r1 0
2
1 x1 0 [ x1 r1 ]
L
0
r2
2 2 r2 0
Multiply both sides by r2 and divide by 2
2
2 r2 0
2
2 x2 0 [ x2 r2 ]
The kuhn tucker conditions are
2 x1 2 x 2 1 1 2 -------------(1)
31 2 1 1 ------------(2)
2 x1 3 x2 s1 6 -------(3)
2 x1 x2 s2 4 --------(4)
1q1 2 q2 1r1 2 r2 0 ------------(5) (these are called complimentary
conditions)
Max Z*=-A1-A2 where A1,A2 , are artificial variables
Subject to constraints
2 x1 21 2 2 1 A1 2
31 2 1 A2 1
2 x1 3x2 s1 6
2 x1 x2 s2 4
x1,x2,λ1,λ2,μ1,μ2,A1,A2,s1,s2≥0
Initial basis feasible solution is
x1=x2=λ1=λ2=μ1=μ2=0
A1=2,A2=1,s1=6,s2=4
Cj 0 0 0 0 0 0 0 0 -1 -1
CB xB x1 x2 λ1 λ2 μ1 μ2 s1 s2 A1 A2
-1 A1=2 [2] 0 2 2 -1 0 0 0 1 0
-1 A2=1 0 0 3 1 0 -1 0 0 0 1
0 s1=6 2 3 0 0 0 0 0 0 0 0
0 s2=4 2 1 0 0 0 0 0 0 0 0
Zj 2 0 5 3 -1 -1 0 0 1 1
Z*=-3 Zj-Cj -2 0 -5 -3 1 1 0 0 -1 -1
Since some Zj-Cj<=0, therefore the solution is not optimal
Here x1 , x2, λ1, λ2 are eligible to enter the basis
λ1 can not enter the basis since complementary condition λ1s1=0 does not hold
λ2 can not enter the basis since complementary condition λ2s2=0 does not hold
x1 can enter basis since complementary condition x1 μ1=0 hold.
We select x1 to enter the basis
We have select A1 as leaving variable.
Cj 0 0 0 0 0 0 0 0 -1
CB xB x1 x2 λ1 λ2 μ1 μ2 s1 s2 A2
0 x1=1 1 0 1 1 -1/2 0 0 0 0
-1 A2=1 0 0 3 1 0 -1 0 0 1
0 s1=4 0 [3] -2 -2 1 0 0 0 0
0 S2=2 0 1 -2 -2 1 0 0 0 0
Zj 0 0 3 1 0 -1 0 0 1
Z*=-1 Zj -Cj 0 0 -3 -1 0 1 0 0 0
Since some Zj-Cj<=0, therefore the solution is not optimal
Here λ1, λ2 x2, μ1 are eligible to enter the basis
λ1 can not enter the basis since complementary condition λ1s1=0 does not hold
λ2 can not enter the basis since complementary condition λ2s2=0 does not hold
μ1 can not enter basis since complementary condition x1 μ1=0 does not hold.
x2 can enter the basis since complementary condition x2 μ2=0 hold.
We select x2 to enter the basis
We have select s1 as leaving variable.
Cj 0 0 0 0 0 0 0 0 -1
CB xB x1 x2 λ1 λ2 μ1 μ2 s1 s2 A2
0 x1=1 1 0 1 1 -1/2 0 0 0 0
-1 A2=1 0 0 [3] 1 0 -1 0 0 1
0 x2=4/3 0 1 -2/3 -2/3 1/3 0 0 0 0
0 s2=2/3 0 0 -4/3 -4/3 2/3 0 0 0 0
Zj 0 0 3 1 0 -1 0 0 1
Z*=-1 Zj Cj 0 0 -3 -1 0 1 0 0 0
Since some Zj-Cj<=0, therefore the solution is not optimal
Here λ1, λ2 ,μ1 are eligible to enter the basis
λ1 can enter the basis since complementary condition λ1s1=0 not hold
λ2 can not enter the basis since complementary condition λ2s2=0 does not hold
μ1 can not enter basis since complementary condition x1 μ1=0 does not hold.
We select λ1 to enter the basis
We have select A2 as leaving variable.
Cj 0 0 0 0 0 0 0 0
CB xB x1 x2 λ1 λ2 μ1 μ2 s1 s2
0 x1=2/3 1 0 0 2/3 -1/2 1/3 0 0
0 λ1=1/3 0 0 1 1/3 0 -1/3 0 0
0 x2=2/3 0 1 0 -4/9 1/3 -2/9 0 0
0 s2=10/9 0 0 0 -8/9 2/3 -4/9 0 0
Zj 0 0 0 0 0 0 0 0
Z*=0 Zj -Cj 0 0 0 0 0 0 0 0
Since all Cj-Zj=0 , therefore the above solution is optimal
The optimal solution is x1=2/3, x2=2/3, λ1=1/3, λ2=0, s1=0, s2=10/9,
μ1= μ2=0 and Max Z*=0
This solution also satisfies the complementary condition λ1 s1=0, λ2 s2=0,
μ1 x1=0, x2μ2=0 and restriction on the sign of Lagrange's multiples λ1, λ2 ,μ1 , μ2.
The optimum solution of the given quadratic problem is given by
Max Z=2x1+x2-x12
=22/9
Problem:-01( Beale's Method)
The operations research team of the ABC company has come up with the
mathematical data(daily basis) needed for two product which the firm manufactures. Its also
has determined that this is a non-linear programming problem, having linear constraints and
objective function which is the sum of a Linear and a quadratic form. The pertinent gathered
by the OR team are:
Max Z=12x+21y+2xy-2x2-2y2
Subject to constrains
i) 8-y≥0
ii) 10-x-y≥0 and x,y≥0
Find the maximum contribution and number of units that can be expected for these two
products which are a part of the firm’s total output.(x and y represent the number of units of
the two products.)
Solution
Let us rewrite the given QPP as follows
Max Z=12x+21y+2xy-2x2-2y2
Subject to constraints
y≤8
x+y≤10
and x,y≥0
The standard form of QPP is
Max Z=12x+21y+2xy-2x2-2y2
Subject to constraints
y +s1=8
x+y+s2 = 10
and x,y,s1 ,s2 ≥0
Initial basic feasible solution is
XB=(x,y)=(8,2)
XN=(s1,s2)=(0,0)
Let us write the constraints in terms of non basic variables.
y=8- s1
x=10-y- s1-s2=10-8- s1-s2=2- s1-s2
Let us write the objective function in terms of none basic variable.
Z=12(2- s1-s2)+21(8- s1)+2(2- s1-s2)-( 2- s1-s2)2-(8- s1)2
Z=244-53s1-28s2+2 s1s2+2s12-2(2 s1-s2)2-2(8- s1)2
Differentiate Z partially with respect to non basic variables.
Z
53 2 s 2 4(2 s1 s 2 ) 4(8 s1 )
s1
Z
13 1
s1 s1 0
s2 0
i.e Z decreases when s1 increases
Z
28 2 s1 4(2 s1 s 2 );
s 2
Z
20 2
s2 s1 0
s2 0
i.e z decreases when s1 increases
Since both the partial derivatives are negative, the current solution is optimum.
Thus the optimum solution x=2, y=8 with max Z=88
Hence in order to have a maximum contribution of Rs88, the ABC company must
expect 2 and 8 units of the two products respectively.
Problems on Maxima or Minima
Problem:-01
A trader receive x units of an item at the beginning of each month. The cost of carrying x
units per month is given by
c1 x 2 c2 (20n x) 2
c( x)
2n 2n
Where c1= cost per day of carrying a unit of item in stock(Rs10)
C2=cost per day of shortage of a unit of item (Rs150)
n= number of units of item to be supplied per day(30)
determine the order quantity x that minimize the cost of inventory
Solution :-
c1 x 2 c2 (20n x) 2
Given c( x)
2n 2n -------(1)
The necessary condition for a function to have either minimum or maximum value at
a point is that its first derivative should be zero .
Differentiate equation (1) with respect to x and assume it as zero
d 2c x 2c (20n x)(0 1)
c( x) 1 2
dx 2n 2n
d c x c (20n x)
c( x) 1 2
dx n n --------(2)
c1 x c2 (20n x)
0
n n
c1 x c2 (20n x) 0
Here c1=10, c2=150 and n=30.
10x 150(600 x) 0
10x 150(600 x) 0
x=(600x150)/160=562.5
At this point the function f(x) may have optimum
Thus the nature of the extreme point given by the second derivative.
Differentiate equation (2) with respect to x, we have
d 2 c( x) c1 c2
10/ 30 150/ 30 1/ 3 5 16/ 3 0
dx2 n n
The value of the second derivative is positive, therefore f(x) has a local minimum at
x=562.5
To find the global minimum
We have to select two extreme values before and after the point x=562.5
say x=0 and infinity.
Substituting the value of x in c(x),we get
C(x=0)=Rs900000
C(562.5)=Rs56249.37;
lim
c(x)=
x
It follows that, a global minimum for c(x) occurs at x=562.5
Problem :-02
A firm has a total revenue function, R=20x-2x2, and a total cost function c=x2-4x+20,
where x represents the quantity. Find the revenue maximizing output level and the
corresponding value of profit, price and total revenue.
Solution:-
Given R(x)=20x-2x2 ----(1) and C(x)= x2-4x+20------(2)
The necessary condition for a revenue function R(x) to have maximum value at a
point is
dR d 2R
0 and 2 0
dx dx
Since R(x)=20x-2x2
Differentiate (1) with respect to x and equivalent it to zero, we have
dR
=20-4x -------(3)
dx
=> 20-4x=0
=> x=5.
Also differentiate (3) with respect to x, we get
d 2R
4( 0)
dx2
Hence the revenue will be maximum at an output level at x=5.
The profit function is given by
Profit=Revenue-Cost
P(x)=R(x)-C(x)=(20x-2x2)-( x2-4x+20)=24x-3x2-20
Thus, the total profit at x=5 will be P(5)=24(5)-3(5)2-20=25.
The price of a product at x=5 is
p(x)=R(x)/x=(20x-2x2)/x=20-2x
p(5)=20-2(5)=10
The maximum revenue at x=5 is R(5)=20(5)-2(5)2=50
Problem:-04
Obtain necessary conditions for the optimum solution of the following problem
Minimize f(x1,x2)= 3e
2 x1
2e x2 5
Subject to constraints
g(x1,x2)= x1+x2-7=0
and x1,x2≥0
solution:-
Let us write the Lagrange's function
L ( x1 , x 2 , ) f ( x1 , x 2 ) g ( x 1 , x 2 )
L ( x 1 , x 2 , ) 3e
2 x1
2e x2 5 ( x1 x2 7)
The necessary conditions for the minimum of f(x1,x2) are given by
L
0
x1
6e 2 x1 1 0
6e 2 x1 1 -------(1)
L
0
x2
2e x2 5 0
2e x2 5 ---------(2)
From (1)and (2), we get
2e x2 5 6e 2 x1 1
log 2e x2 5 log 6e 2 x1 1
log 2 log e x2 5 log 6 log e 2 x1 1
log 2 x2 5 log 6 2 x1 1
2 x1 x2 5 log 2 log 6 1
2 x1 x2 4 log 2 / 6
2 x1 x2 4 log1 / 3
2 x1 x2 4 log 1 log 3
2 x1 x2 4 log 3 -------(3)
L
0
( x1 x2 7) 0
x1 x2 7 --------(4)
Add (3) and (4), we get
3x1=11-log3
=>x1=1/3(11-log3)
Substitute the value of x1 in (4), we get
1/3(11-log3) + x2 7
x2=7-(1/3)(11-log3)
Hence the necessary conditions for the optimum solution is
x1=1/3(11-log3) and
x2=7-(1/3)(11-log3)
To find ?
Sub the value of x2 in (2), we have
(2) 2e x2 5
2e 7(1 / 3)(11log 3)5
2e12(1/ 3)(11log 3)
Problem:05
Solve the following problem by using the method of Lagrange's multipliers.
2 2
Minimize Z= x1 x2 x32
Subject to constraints
i) x1 x 2 3 x3 2
ii) 5 x1 2 x 2 x3 5
and x1,x2≥0
Solution:-
The Lagrange's function is
L ( x , ) x 12 x 22 x 32 1 ( x 1 x 2 3 x 3 2 ) 2 ( 5 x 1 2 x 2 x 3 5 )
The necessary conditions for the minimum of Z gives
L
0
x1
2 x1 1 52 0
L
0
x2
2 x2 1 22 0
L
0
x3
2 x3 31 2 0
L
0
1
( x1 x2 3x3 2) 0
L
0
2
(5x1 2 x2 x3 5) 0
The solution of these simultaneous equations gives
X=(x1,x2,x3)=(37/46,16/46,13/46)
(1 , 2 ) (2 / 23,7 / 23)
and Min Z=193/250
To see that this solution corresponds to the minimum of Z apply the sufficient
condition by having a matrix;
Since m-2,n=3 so n-m=1 and 2n+m=5, only one minor of D of order 5 needs to be
evaluated and it must have a positive sign; (-1)m=(-1)2=1. Since
D 460 0
The extreme point X=(x1,x2,x3) corresponds to the minimum of Z.
Problem:-06
Use the method of Lagrange's multipliers to solve the following NLP problem. Does
the solution maximize or minimize the objective function?
2 2
Optimize Z= 2 x1 x2 3x32 10x1 8 x2 6 x3 100
Subject to constrain
g ( x) x1 x2 x3 20
and x1,x2,x3≥0
Solution
The Lagrange's function can be formulated as
L ( x , , ) 2 x 12 x 22 3 x 32 10 x 1 8 x 2 6 x 3 100 1 ( x 1 x 2 x 3 20 )
The necessary conditions for maximum or minimum are
L
0
x1
4 x1 10 0
x1 ( 10) / 4 -------(1)
L
0
x2
2 x2 8 0
x2 ( 8) / 2 -----(2)
L
0
x3
6 x3 6 0
x3 ( 6) / 6 ----(3)
L
0
( x1 x2 x3 20) 0
x1 x2 x3 20 ------(4)
Putting the values of (1) , (2) and (3) in (4), we get the value of λ,
(4)=> ( 10) / 4 ( 8) / 2 ( 6) / 6 20
[3( 10) 6( 8) 2( 6)] / 12 20
[3 30 6 48 12 2 ] / 12 20
11 90 240
11 330
=> λ=30.
Substituting the value of λ in the other three equations,, we get an extreme point
x1 ( 10) / 4 (30 10) / 4 20 / 4 5
x2 ( 8) / 2 (30 8) / 2 22 / 2 11
x3 (30 6) / 6 24 / 6 4
To prove the sufficient condition whether the extreme point solution gives maximum or
minimum value of the objective function we evaluate (n-1) principle minors as follows;
Since sign of 3 a nd 4 are alternative,
Therefore extreme point x1,x2,x3=5,11,4 is a local maximum.
At this point the value of objective function is Z=281.
Problem:-07
Find the optimum value of the objective function when subject to the following three sets of
constraints separately.
Maximize Z= 10x1-x12+10x2-x2
Subject to constrain
(a)
x1+x2≤14
-x1+x2 ≤6
x1,x2≥0
(b)
x1+x2≤8
-x1+x2 ≤5
x1,x2≥0
(c)
x1+x2≤9
x1-x2≤6
x1,x2≥0
solution
(a) Here the constraints are;
Let g1(x)= x1+x2+s12-14=0
Let g2(x)= -x1+x2+s22-6=0
The Lagrange's function is
2
L ( x , , s ) 10 x 1 x 12 10 x 2 x 22 1 ( x 1 x 2 s 12 14 ) 2 ( x 1 x 2 s 2 6 )
Kuhn-tucker necessary conditions for a maximize problem are
L
10 2 x1 1 2 0
x1
L
10 2 x2 1 2 0
x2
L 2
( x1 x2 s1 14) 0
1
L 2
( x1 x2 s 2 6) 0
2
L
21 s1 0
s1
L
21s 2 0
s 2
The unconstrained solution (ie. λ1=λ2=0) obtained by solving the first equation is
x1=5, x2=5, s12=4, s22=6 and max Z=50
Since both s12 and s22 are positive the solution is feasible. As the solution so obtained
is unconstrained, so to fine whether or not the solution is maximum we test the hessian matrix
for the given objective function as;
Since signs of the principle minors of H are alternating, matrix H is negative definite
and the point x=(4,4) gives the local maximum of the objective function Z.
(b) Here the constraints are
Let g1(x)= x1+x2+s12-8=0
Let g2(x)= -x1+x2+s22-5=0
The Lagrange's function is
2
L ( x , , s ) 10 x 1 x 12 10 x 2 x 22 1 ( x 1 x 2 s 12 8 ) 2 ( x 1 x 2 s 2 5 )
Kuhn-tucker necessary conditions for a maximize problem are
L
10 2 x1 1 2 0
x1
L
10 2 x2 1 2 0
x2
L 2
( x1 x2 s1 8) 0
1
L 2
( x1 x2 s 2 5) 0
2
L
21 s1 0
s1
L
21s 2 0
s 2
The unconstrained solution (ie. λ1=λ2=0) obtained by solving the first equation is
x1=5, x2=5, s12=-2, s22=5 and max Z=50
Since s12=-2 this solution is infeasible. Solving again these equation for s1=λ1=0, we
get x1=4, x2=4, s22=5, λ1=2 and Max Z=48.
This solution satisfies both the constraints and the conditions s1λ1= s2λ2=0 are also
satisfied, therefore the point X=(4,4) gives the maximum of objective function Z.
(c) Here the constraints are
Let g1(x)= x1+x2+s12-9=0
Let g2(x)= -x1+x2+s22+6=0
The Lagrange's function is
2
L ( x , , s ) 10 x 1 x 12 10 x 2 x 22 1 ( x 1 x 2 s 12 9 ) 2 ( x 1 x 2 s 2 6)
Kuhn-tucker necessary conditions for a maximize problem are
L
10 2 x1 1 2 0
x1
L
10 2 x2 1 2 0
x2
L 2
( x1 x2 s1 9) 0
1
L 2
( x1 x2 s 2 6) 0
2
L
21 s1 0
s1
L
21s 2 0
s 2
The unconstrained solution (ie. λ1=λ2=0) obtained by solving the first equation is
x1=8, x2=2, s12=-1, s22=-6 and max Z=50 since both s12 and s22 are negative, the solution is
infeasible.
Solving again these four equation for s1=λ1=0(violating second condition) we get
x1=2, x2=8, s12=-1, λ2=6 and Max Z=32 this solution is also infeasible as s12 is negative.
Solving again these four equation for s1=s2=0(ie. λ1=λ2=0) we get x1=7.5, x2=1.5, λ1=1
λ2=6and Max Z=31.50. since this solution does not violate any of the condition,
Therefore, the point x=(7.5,1.5) gives the maximum of the objective function Z.
Problem :-08
Determine x1 and x2 so as to
Maximize Z=12x1+21x2+2x1x2-2x12-2x22
Subject to constrains
(i) x2≤8
(ii)x1+ x2 ≤8
and x1,x2≥0
Solution
Here f(x1, x2)= 12x1+21x2+2x1 x2-2x12-2x22
Let g1(x1, x2)= x2-8=0
Let g2(x1, x2)=x1+ x2-10=0
The Lagrange's function is
L ( x , s , ) f ( x ) 1 [ g 1 ( x ) s 12 ] 2 [ g 2 ( x ) s 22 ]
Kuhn-tucker necessary conditions can be stated as
2
f g1
(i) x
i 1
i
x j
0 ; j 1, 2
j
(ii) i g 1 ( x ) 0 ; i 1 , 2
12+2x2-4x1-λ2=0
λ1(x2-8)=0
21+2x1-4x2- λ1- λ2=0
λ2(x1+ x2-10)=0
(iii) g 1 ( x ) 0
x2-8≤0
x1+ x2-10≤0
(iv) i 0 ; i 1, 2
These may arise four case
Case 1
If λ1=0 λ2=0, then from condition(i) we have
12+2x2-4x1=0 and 21+2x1-4x2- λ1- λ2=0
Solving these equations we get x1=15/2, x2=9 however, this solution violates condition (iii)
and therefore it may be discarded.
Case 2
λ1≠0 λ2≠0, then from condition(ii) we have
x2-8=0 or x2=8and x1+ x2-10=0 or x1=2
substituting these values in condition (i) we get λ1=-27 λ2=20 however this solution violates
the condition (iv) and therefore may be discarded.
Case 3
λ1≠0 λ2=0, then from condition(ii)and (i) we have
(a) x1+x2=10
(b)2x2-4x1=-12
(c)2x1-4x2=-12+ λ1
Solving these equations we get x1=2, x2=8 and λ1=-16. However this solution violates
the condition(iv) and therefore maybe discarded.
Case 4
λ1=0 λ2≠0, then from condition(i)and (ii) we have
(a) 2x1-4x2=-12
(b)2x1-4x1=-21+ λ1
(c)x1+x2=10
Solving these equations we get x1=17/4, x2=23/4and λ2=13/4. This solution does not
violate any of the kuhn-tucker condition and therefore must be accepted.
Hence the optimum solution of the given problem is x1=17/4, x2=23/4 , λ1=0and
λ2=13/4 and max Z=1734/16.
You might also like
- Computer Based Optimization Method MCA - 305100% (1)Computer Based Optimization Method MCA - 3053 pages
- Integer Programming by Cutting Planes MethodsNo ratings yetInteger Programming by Cutting Planes Methods58 pages
- Module - 7 Lecture Notes - 1 Integer Linear ProgrammingNo ratings yetModule - 7 Lecture Notes - 1 Integer Linear Programming7 pages
- Cap 7 - 3151910-Operations-Research-Theory-And-Applications-By-J.-K.-Sharma-Z-Lib - OrgNo ratings yetCap 7 - 3151910-Operations-Research-Theory-And-Applications-By-J.-K.-Sharma-Z-Lib - Org35 pages
- Submitted By: Submitted To: Dr. Arindam DasNo ratings yetSubmitted By: Submitted To: Dr. Arindam Das11 pages
- Optimization-L4-6 (Integer Programming)No ratings yetOptimization-L4-6 (Integer Programming)58 pages
- CSE 446 Machine Learning: Instructor: Pedro DomingosNo ratings yetCSE 446 Machine Learning: Instructor: Pedro Domingos17 pages
- A Toolbox For Modeling and Optimization in Matlab: October 2004No ratings yetA Toolbox For Modeling and Optimization in Matlab: October 20047 pages
- Dependence of Ferroelectricity On Film ThicknessNo ratings yetDependence of Ferroelectricity On Film Thickness12 pages
- Sol-Gel Fabrication of Oriented PZT PDFNo ratings yetSol-Gel Fabrication of Oriented PZT PDF12 pages
- Another Pedagogy For Pure-Integer GomoryNo ratings yetAnother Pedagogy For Pure-Integer Gomory9 pages
- Integer Programming: Adopted From Taha and Other SourcesNo ratings yetInteger Programming: Adopted From Taha and Other Sources33 pages
- United States Patent (191: Tsunekawa Et A1. (45) Date of PatentNo ratings yetUnited States Patent (191: Tsunekawa Et A1. (45) Date of Patent10 pages
- NPTEL Gomory Cut Algorithm Course Linear Programming ProblemsNo ratings yetNPTEL Gomory Cut Algorithm Course Linear Programming Problems4 pages
- Lab 6 - Learning System Identification Toolbox of Matlab PDFNo ratings yetLab 6 - Learning System Identification Toolbox of Matlab PDF11 pages
- Chapter Two Sampling and Reconstruction: Lecture #5No ratings yetChapter Two Sampling and Reconstruction: Lecture #526 pages
- Module - 7 Lecture Notes - 2 Mixed Integer Programming: y C B XNo ratings yetModule - 7 Lecture Notes - 2 Mixed Integer Programming: y C B X3 pages
- Chapter 3 - Deriving Solutions From A Linedeear Optimization Model PDFNo ratings yetChapter 3 - Deriving Solutions From A Linedeear Optimization Model PDF40 pages
- The Thickness Uniformity of Films Deposited by Magnetron SputteringNo ratings yetThe Thickness Uniformity of Films Deposited by Magnetron Sputtering4 pages
- Operations Research 1 The Two-Phase Simplex Method: Dr. Özgür KabakNo ratings yetOperations Research 1 The Two-Phase Simplex Method: Dr. Özgür Kabak16 pages
- Design and Fabrication of A Lead ZirconateNo ratings yetDesign and Fabrication of A Lead Zirconate13 pages
- Integer simplex method (gomory's cutting plane method) Algorithm & Example-1 (Pure integer)No ratings yetInteger simplex method (gomory's cutting plane method) Algorithm & Example-1 (Pure integer)10 pages
- Evaluation Metrics For Regression ProblemsNo ratings yetEvaluation Metrics For Regression Problems9 pages
- Optimum Solution of Integer Programming Problem by New ApproachNo ratings yetOptimum Solution of Integer Programming Problem by New Approach5 pages
- Modeling and Simulation of Wear in A Pin On Disc TribometerNo ratings yetModeling and Simulation of Wear in A Pin On Disc Tribometer10 pages
- 15-Module - 3 Integer Programming Problems-03-09-2024No ratings yet15-Module - 3 Integer Programming Problems-03-09-20247 pages
- Research Announcements: Outline of An Algorithm For Integer Solutions To Linear ProgramsNo ratings yetResearch Announcements: Outline of An Algorithm For Integer Solutions To Linear Programs4 pages
- 4 - Solving The Linear Programming Model: Example 3: Solve The Following Linear Programming ModelNo ratings yet4 - Solving The Linear Programming Model: Example 3: Solve The Following Linear Programming Model9 pages
- Visvesvaraya Technological University: "File Compression Using Huffman Coding"No ratings yetVisvesvaraya Technological University: "File Compression Using Huffman Coding"5 pages
- A Brief Introduction to MATLAB: Taken From the Book "MATLAB for Beginners: A Gentle Approach"From EverandA Brief Introduction to MATLAB: Taken From the Book "MATLAB for Beginners: A Gentle Approach"2.5/5 (2)
- 10+2 Level Mathematics For All Exams GMAT, GRE, CAT, SAT, ACT, IIT JEE, WBJEE, ISI, CMI, RMO, INMO, KVPY Etc.From Everand10+2 Level Mathematics For All Exams GMAT, GRE, CAT, SAT, ACT, IIT JEE, WBJEE, ISI, CMI, RMO, INMO, KVPY Etc.No ratings yet