Operation Research

7.7 Optimization of unconstrained problem: An extreme point of a function f ( x) defines

either a maximum of a minimum of the function. Mathematically, a point x 0=(x1 , x 2 , … … .. , x n )
is a maximum if f (x 0+ h)≤ f ( x0 ) for all h=(h1 , h2 , … … , h j , … … , hn ) such that h j is sufficiently
small for all j. In other words, x 0 is a minimum if the value of f at every point in the
neighborhood of x 0 does not exceed f (x 0). In similar manner, x 0 is a minimum if for h as defined
f (x 0+h)≥ f ( x0 ).

⋮ ⋮⋮

⋮ ⋮ ⋮ ⋮⋮ ⋮

⋮ ⋮ ⋮ ⋮ ⋮ ⋮⋮ ⋮

o a x 1 x 2 x3 x 4 x5 x 6 b

Figure illustrates the maxima and minima of a single variable function f (x) over the interval
[a , b]. The points x 1 , x 2 , x 3 , x 4 and x 6 are all extrema of f (x). These include x 1 , x 3 and x 6 as
maxima and x 2 and x 4 as minima. Because of

f ( x 6 ) =max ⁡{f ( x 1 ) , f ( x3 ) , f ( x 6) }

f (x 6) is called global or absolute maximum, f (x 1) and f (x 3) are local or relative maxima.

Similarly, f ( x 4 ) is a local minimum and f ( x 2 ) is a global or absolute minimum.

Although x 1 is a maximum point, it differs from remaining local maxima in that the value of f

corresponding to at least one point in the neighborhood of x 1 is equal to f ( x 1 ). In the respect, x 1 is

called a weak maximum compared with x 3, for example where f ( x 3 ) defines a strong maximum.
A weak maximum thus implies alternative maxima. Similar result may be developed for the
weak maximum at x 4 . In general, x 0 is a weak maximum if f (x 0+ h)≤ f ( x0 ) and a strong

maximum if f ( x 0 +h ) <f ( x 0). where h is as defined earlier.

Page 1
 Operation Research

Similarly, x 0 is a weak minimum if f (x 0+ h)≥ f (x0 ) and a strong minimum if f ( x 0 +h ) >f (x 0).
where h is as defined earlier.

In the figure the first derivative of f vanishes at all extrema. How ever, this property is also
satisfied at inflection and saddle points, such as x 5. If a point with zero slope is not on extrema,
then it must automatically be an inflection or a saddle point.

7.8Necessary and sufficient conditions: The necessary and sufficient conditions for an n-
variable function f (x) to have extrema is assumed that the first and second partial derivatives of
f ( x) are continuous at every x with:

'
A necessary condition for x 0 to be an extreme point of f (x) is that ∇ f ( x 0 )=0 or f ( x 0 )=0.

Because the necessary condition is also satisfied for inflection and saddle points. It is more
appropriate to refer to the points obtained from the solution of ∇ f ( x 0 )=0 as stationary points.

A sufficient condition for a stationary point x 0 to be an extremum is for the Hessian matrix H
evaluated at x 0 defined as

∂2 f
H ( x 0 )=
| ∂ xi ∂ x j |
∂2 f ∂2 f ∂2 f

[ ]
⋯
∂ x 21 ∂ x1 ∂ x2 ∂ x1 ∂ xn
∂2 f ∂2 f ∂2 f
⇒ H ( x 0 )= …
∂ x2 ∂ x1 ∂ x22 ∂ x2 ∂ xn
∂⃛2 f ∂⃛2 f ∂⃛2 f
…
∂ xn ∂ x1 ∂ xn ∂ x2 ∂ x 2n

(i) x 0 is a minimum point if H ( x 0 ) is positive definite. i.e, if the value of all principal

minor determinant of H ( x 0 ) are positive non negative.

(ii) x 0 is a maximum point if H ( x 0 ) is negative definite. i.e, if the values of principal

minor determinant of H ( x 0 ) has the sign (−1)k , k=0,1,2 , … . ,n

Page 2
 Operation Research

(iii) x 0 is a inflection or saddle point if H ( x 0 ) is indefinite. i.e, if H ( x 0 ) is neither positive

definite nor non negative definite.

If f ( x) is a function of single variable and x 0 is a stationary point then the sufficient condition for
extremais that

(i) x 0 is a minimum if f ' ' ( x 0 ) >0

(ii) x 0 is a maximum if f ' ' ( x 0 ) <0

''
If in the single variable function f ( x 0 )=0, higher order derivatives must be compute and if at a
''
stationary point x 0 of f (x), the first (n−1) derivatives vanish and f ( x 0 ) ≠ 0 and if n is even then
x 0 is an extreme point and

(i) x 0 is a minimum if f n ( x 0 ) > 0

(ii) x 0 is a maximum if f n ( x 0 ) < 0

and (iii) if n is odd then neither a maximumnor a minimum and x 0 is a point of inflection or
saddle point.

Example-12. Find the maximum or minimum value of the function f ( x )=12 x 5−45 x 4 + 40 x3 +5 .

Solution: There is a maximum or minimum if

f ' (x )=0 (necessary condition)

⇒ 60 x 4 −180 x 3 +120 x 2=0

⇒ x=0 or x=1 or x=2

Now, f ' ' ( x ) =240 x 3 −540 x 2 +240 x at x=1 , f ' ' ( x )=−60<0

∴ f (x ) has a relative maximum at x=1 and maximum value

¿ 12−45+40+ 5=12

At x=2 , f ' ' ( x )=240> 0

Page 3
 Operation Research

∴ f (x ) has a relative minimum at x=2 and minimum value

¿ 12.25 −45. 24 + 40.23 +5=−11

At x=0 , f '' ( x ) =0 so higher derivative must be compute and

f ' ' ' ( x )=720 x 2−1080 x+ 240

∴ f ' ' ' ( 0 )=240≠ 0

Since odd derivative at x=0 is non zero.

∴ f (x ) has neither a maxima nor minima at x=0 so x=0 is a point of inflection.

Example-13. Find the relative maximum or minimum of the function

f ( x 1 , x 2 ) =x1 +2 x 2+ x 1 x2− x21−x 22

Solution: The necessary condition for relative maximum or minimum is

∂f ∂f
=0 , =0
∂ x1 ∂ x2

⇒ 1+ x 2−2 x 1=0and 2+ x 1−2 x2 =0

4 5
⇒ x 1= , x 2=
3 3

∴ x0 = ( 43 , 53 )
are stationary points.

For the sufficient condition, the Hessian matrix is obtained by

∂2 f ∂2 f

H ( x 0 )=
[ ∂ x 21
∂2 f
∂ x2 ∂ x1
∂ x1 ∂ x2
2
∂ f
∂ x 22
] x 1=

x 2=
4
3
5
3
= −2 1
[ 1 −2 ]

Page 4
 Operation Research

Principal minor determinants are |−2|=−2 and [−21 −21 ]=4−1=3

Since the principal minor determinant has the sign (−1 )i ,i=1, 2. i.e, has alternative sign starting

with negative sign. So H ( x 0 ) is negative definite and f ( x 1 , x 2 ) has a local maximum at

x 0= ( 43 , 53 )

∴ Maximum value

4 5 4 5 16 25 22
¿ +2 × + × − − =
3 3 3 3 9 9 9
Example-14. Find the relative maximum or minimum of the function

f ( x )=f ( x 1 , x 2 , x 3 )=x 1 +2 x 3 + x 2 x 3−x 21−x 22−x 23

Solution: The necessary condition for relative maximum or minimum is

∂f (x)
=0
∂x

∂f ∂f ∂f
⇒ =0 , =0 , =0
∂ x1 ∂ x2 ∂ x3

⇒ 1−2 x 1=0 , x 3−2 x2 =0 , x 2−2 x 3=0

1 2 4
⇒ x 1= , x 2= , x3 =
2 3 3

∴ x0 = ( 12 , 23 , 43 )
are stationary points.

Page 5
 Operation Research

For the sufficient condition, the Hessian matrix is obtained by

∂2 f ∂2 f ∂2 f

[ ]
∂ x 21 ∂ x1 ∂ x2 ∂ x1 ∂ x3
−2 0 0
H ( x 0 )=
∂2 f
∂ x2 ∂ x1
2
∂ f
∂2 f
∂ x22
∂2 f
∂2 f
∂ x2 ∂ x3
∂2 f
0 [
= 0 −2 1
1 −2 ]
∂ x3 ∂ x1 ∂ x3 ∂ x2 ∂ x 23

Principal minor determinants are |−2|=−2 , [−20 −20 ]=4 and

−2 0 0

[ ]
0 −2 1 =−2 ( 4−1 )=−6
0 1 −2

Since the principal minor determinant has the sign (−1 )i ,i=1, 2,3. i.e, has alternative sign

starting with negative sign. So H ( x 0 ) is negative definite and f ( x 1 , x 2 , x3 ) has a local maximum at

1 2 4
x 0= ( , ,
2 3 3 )
∴ The maximum value

1 4 2 4 1 4 16 7
¿ +2 × + × − − − =
2 3 3 3 4 9 9 12
Example-15. Find the relative maximum, minimum or saddle point of the function

f ( x 1 , x 2 ) =x31 + x 32−3 x 1−12 x2 +25

Solution: The necessary condition for relative maximum or minimum is

∂f ∂f
=0 , =0
∂ x1 ∂ x2

⇒ 3 x 21−3=0and 3 x 22−12=0

Page 6
 Operation Research

⇒ x 1=± 1 and x 2=± 2

∴ x0 =( 1 ,2 ) or (−1 ,−2 ) or (−1 , 2 ) or ( 1 ,−2 ) are stationary points.

For the sufficient condition, the Hessian matrix is obtained by

∂2 f ∂2 f

[
H ( x 0 )=
∂ x 21
∂2 f
∂ x2 ∂ x1
∂ x1 ∂ x2
∂ f2

∂ x 22
][
=
6 x1 0
0 6 x2 ]
At x 0=(1 ,2), H ( x 0 )= [ 60 120 ] has principal minor determinants 6 and 72 both are positive. So,
H ( x 0 ) is positive definite and hence f (x) has relative minimum at x 0=(1 ,2).

0
At x 0=(−1 ,−2), H ( x 0 )= [−60 −12 ]
has principal minor determinants −6 and 72 with sign

(−1 )i ,i=1, 2. So, H ( x 0 ) is negative definite and hence f (x) has relative maximum at
x 0=(−1 ,−2).

At x 0=(−1 ,2), H ( x 0 )= [−60 120 ] has principal minor determinants −6 and 72. So H ( x ) is 0

indefinite.

At x 0=(1 ,−2), H ( x 0 )= [ 60 0
−12 ]
has principal minor determinants −6 and 72. So H ( x 0 ) is

indefinite and hence f ( x) has saddle point at (−1 , 2) and (1 ,−2) points.

Example-16. Verify that the function

f ( x 1 , x 2 , x3 ) =2 x 1 x2 x 3−4 x 1 x3 −2 x 2 x3 + x 21 + x 22+ x 23−2 x 1−4 x2 + 4 x 3 has the stationary points

( 1 ,2 , 0 ) , ( 0 , 3 ,1 ) , ( 0 ,1 ,−1 ) , ( 2 ,1 , 1 ) and (2 , 3 ,−1). Use the sufficiently condition to find the
extreme points.

Solution: The necessary condition for extreme points

Page 7
 Operation Research

∂f
=0 ⇒ 2 x 2 x 3−4 x 3+2 x 1−2=0

}
∂ x1
⇒ ∂ f =0 ⇒ 2 x 1 x 3−2 x 3+2 x 2−4=0 ( 1)
∂ x2
∂f
=0 ⇒ 2 x1 x 2−4 x 1 +2 x3 + 4=0
∂ x3

( 1 ,2 , 0 ) , ( 0 , 3 ,1 ) , ( 0 ,1 ,−1 ) , ( 2 ,1 , 1 ) and (2 , 3 ,−1) are satisfies the system of equation (1). So

these points are the solution of the system and hence they are stationary points.

For the sufficient condition, the Hessian matrix is obtained by

∂2 f ∂2 f ∂2 f

[ ]
∂ x 21 ∂ x1 ∂ x2 ∂ x1 ∂ x3
2 2 x3 2 x 2−4
H ( x 0 )=
∂2 f
∂ x2 ∂ x1
2
∂ f
∂2 f
∂ x22
∂2 f
∂2 f
∂ x2 ∂ x3
∂ f 2
=
[ 2 x3 2
2 x 2−4 2 x 1−2
2 x1
2 ]
∂ x3 ∂ x1 ∂ x3 ∂ x2 ∂ x 23

2 0 0

[ ]
At ( 1 ,2 , 0 ) , H ( x 0 ) = 0 2 2 has the principal minor determinant ∆ 1=|2|=2 ,
0 0 2

2 0 0
∆ 2= 2 0
[ ]
0 2 [ ]
=4 and ∆ 3= 0 2 2 =8 all are positive. So H ( x 0 ) is positive definite and hence
0 0 2
( 1 ,2 , 0 ) is a minimum point.

2 2 2

[ ]
At ( 0 , 3 ,1 ) , H ( x 0) = 2 2 0 has the principal minor determinant ∆ 1=|2|=2 ,
2 −2 2

Page 8
 Operation Research

2 2 2
∆ 2=
2 2
[ ]
2 2 [ ]
=0 and ∆ 3= 2 2 0 =−16 . So H ( x 0 ) is indefinite and hence ( 0 , 3 ,1 ) is inflection
2 −2 2
point.

Similarly, we can show that ( 0 , 1 ,−1 ) , (2 , 1 ,1 ) and (2 , 3 ,−1).are inflection points.

7.9Optimization of unconstrained problems: When some constraints are imposed on the

variables of a continuous function is called constraint problem. The imposed constraints may be
equality type, inequality type or mixed type. In this section we find the optimization of the non
linear programming problem which is imposed of some differentiable objective function and
constraints. There are different methods to obtained the optimization of constrained problems.

7.10Lagrangian method for equality constrained problems:

Consider the problem

Optimize z=f ( x)

Subject to gi ( x ) =bi

x≥0

The Lagrangian method for identifying the stationary points of optimization problems with
equality constraints can be developed formally as follows:

Let hi ( x )=gi ( x ) −bi=0

L ( x , λ ) =f ( x )−∑ λ i h i ( x )
i

The function L is called the Lagrange function and the perimeters λ i the Lagrange multipliers.

∂L ∂L
The equation =0 and =0 for all i given the necessary conditions for determining
∂ λi ∂ xi

stationary points of f (x) subject to gi ( x ) =bi .

The sufficient conditions for the Lagrangian method will be stated as follows

Page 9
 Operation Research

O⋮ P
H B = ⃛T
[
P ⋮ Q
⃛ ]( m +n) ×(m+n )

where O is an m× m null matrix.

∇ h1 (x)
P=
[ ]
⋮
∇ h m (x)
and Q=
∂2 L( x , λ)
[
∂ xi ∂ x j ]
for alli and j

The matrix H B is called the bordered Hessian matrix function L ( x , λ ) and the bordered Hessian
matrix H B evaluated at ( x 0 , λ 0) then

(i) x 0 is maximum point if, starting with the principal minor determinant of order
(2 m+ 1), the last (n−m) principal minor determinants of H B form an alternating sign
pattern starting with (−1 )m +1, where m is the number of constraints and n is the
number of variables.
(ii) x 0 is miniimum point if, starting with the principal minor determinant of order

(2 m+ 1), the last (n−m) principal minor determinants of H B have the sign of (−1 )m.

These conditions are sufficient for identifying an extreme point.

Other conditions exist that are both necessary and sufficient for identifying an extreme points.
The disadvantage is that this procedure may be computationally in tractable. Define the matrix

O P
∆=
[ T
P Q−μI ]
Evaluated at the stationary point ( x 0 , λ 0). Where μ is an unknown parameter. Consider the
determinant |∆| then each of the real (n−m) roots μi of the polynomial |∆|=0 must be

(i) Negative if x 0 is a maximum point.

(ii) Positive if x 0 is a miniimum point.

Example-17. Solve the non linear programming problem

Maximize z=4 x 1−x 21+ 8 x 2−x 22

Page 10
 Operation Research

Subject to x 1+ x2=2

x1 , x2 ≥ 0

Solution: Let the objective function

z=f ( x1 , x2 ) =4 x 1−x 21 +8 x 2−x 22 and h ( x 1 , x 2 )=x 1 + x 2−2=0

The Lagrangian function

L ( x1 , x 2 , λ ) =f ( x 1 , x 2 )− λ h ( x1 , x 2)

⇒ L ( x 1 , x 2 , λ )=4 x1 −x21 +8 x 2−x 22−λ ( x 1+ x 2−2)

The necessary conditions for maxima or minima

∂L
=4−2 x 1−λ=0
∂ x1

∂L
=8−2 x 2− λ=0
∂ x2

∂L
=− ( x1 + x 2−2 ) =0
∂λ

The solution to these simultaneous equations yields

x 0=( x 1 , x 2 )=(0 , 2) and λ=4

The bordered Hessian matrix is

∂h ∂h

[ ]
0
∂ x1 ∂ x2
0 1 1
H B ( x0 )=
[ O P
T
P Q
=
∂h
∂
∂h
]
x1
∂2 L
∂ x21
∂2 L
∂2 L
∂ x1 ∂ x2
∂2 L
[
= 1 −2 0
1 0 −2 ]
∂ x2 ∂ x2 ∂ x1 ∂ x22

Page 11
 Operation Research

Since m=1 and n=2⇒ n−m=1

Last 1 principal minor determinants is

0 1 1
B

[
∴|H |= 1 −2 0 =4>0
1 0 −2 ]
∴Last n−m=1 principal minor determinant has positive value 4 which is of sign

(−1 )m +1=+ve

∴ z=f ( x1 , x2 ) has a maximum at x 0=(0 , 2) and maximum value of

z=4 ×0−0+8 × 2−4=12

∴ The solution is x 1=0 , x 2=2 and maximum z=12.

Example-18. Solve the non linear programming problem

Maximize z=4 x 1+6 x 2−2 x 21−−2 x 1 x 2−2 x22

Subject to x 1+ 2 x 2=2

x1 , x2 ≥ 0

Solution: Let the objective function

z=f ( x1 , x2 ) =4 x 1 +6 x 2−2 x21 −−2 x 1 x2 −2 x 22 and h ( x 1 , x 2 )=x 1 +2 x 2−2=0

The Lagrangian function

L ( x1 , x 2 , λ ) =f ( x 1 , x 2 )− λ h ( x1 , x 2)

⇒ L ( x 1 , x 2 , λ )=4 x1 +6 x 2−2 x 21−−2 x1 x 2−2 x 22− λ( x 1+ 2 x 2−2)

The necessary conditions for maxima or minima

Page 12
 Operation Research

∂L
=4−4 x 1−2 x 2−λ=0
∂ x1

∂L
=6−2 x 1−4 x 2−2 λ=0
∂ x2

∂L
=− ( x1 +2 x 2−2 )=0
∂λ

The solution to these simultaneous equations yields

x 0=( x 1 , x 2 )= ( 13 , 56 ) and λ=1

The bordered Hessian matrix is

∂h ∂h

[ ]
0
∂ x1 ∂ x2
0 1 2
H B ( x0 )=
[ O P
T
P Q
=
∂h
]
∂ x1
∂h
∂2 L
∂ x21
∂2 L
∂2 L
∂ x1 ∂ x2
∂2 L
[
= 1 −4 −2
2 −2 −4 ]
∂ x2 ∂ x2 ∂ x1 ∂ x22

Since m=1 and n=2⇒ n−m=1

Last 1 principal minor determinants is

0 1 2

[
∴|H B|= 1 −4 −2 =12>0
2 −2 −4 ]
∴Last n−m=1 principal minor determinant has positive value 12 which is of sign

(−1 )m +1=+ve

∴ z=f ( x1 , x2 ) has a maximum at x 0= ( 31 , 56 )and maximum value of

1 5 1 1 5 25 25
z=4 × + 6 × −2 × −−2 × × −2 × =
3 6 9 3 6 36 6

Page 13
 Operation Research

1 5 25
∴ The solution is x 1= , x 2= and maximum z= .
3 6 6

Example-19. Solve the non linear programming problem

2
Maximize z=5 x 1+ x 2− ( x1 −x2 )

Subject to x 1+ x2=4

x1 , x2 ≥ 0

Solution: Let the objective function

z=f ( x1 , x2 ) =5 x1 + x 2−( x 1−x 2 )2 and h ( x 1 , x 2 )=x 1 + x 2−4=0

The Lagrangian function

L ( x1 , x 2 , λ ) =f ( x 1 , x 2 )− λ h ( x1 , x 2)

⇒ L ( x 1 , x 2 , λ )=5 x 1+ x 2−( x 1−x 2 )2− λ( x 1+ x2 −4)

The necessary conditions

∂L
=5−2 ( x 1−x 2 )− λ=0
∂ x1

∂L
=1+2 ( x 1−x 2) −λ=0
∂ x2

∂L
=− ( x1 + x 2−4 ) =0
∂λ

The solution to these simultaneous equations yields

x 0 = ( x 1 , x 2 )= ( 52 , 32 ) and λ=3
The bordered Hessian matrix is

Page 14
 Operation Research

∂h ∂h

[ ]
0
∂ x1 ∂ x2
0 1 1
[
H B ( x0 )=
O P
T
P Q
=
∂h
]
∂ x1
∂h
∂2 L
∂ x21
∂2 L
∂2 L
∂ x1 ∂ x2
∂2 L
[
= 1 −2 2
1 2 2 ]
∂ x2 ∂ x2 ∂ x1 ∂ x22

Since m=1 and n=2⇒ n−m=1

Last 1 principal minor determinants is

0 1 1

[
∴|H B|= 1 −2 2 =4 >0
1 2 2 ]
∴Last n−m=1 principal minor determinant has positive value 4 which is of sign

(−1 )m +1=+ve

∴ z=f ( x1 , x2 ) has a maximum at x 0= ( 52 , 32 ) and maximum value of

5 3 5 3 2
z=5 × + − − =13
2 2 2 2 ( )
5 3
∴ The solution is x 1= , x 2= and maximum z=13.
2 2

Example-20. Solve the non linear programming problem

Minimize z=2 x 21−24 x 1+ 2 x 22−8 x 2 +2 x 23−12 x 3+ 200

Subject to x 1+ x2 + x 3=11

x1, x2 , x3≥ 0

Solution: Let the objective function

z=f ( x1 , x2 , x3 ) =2 x21 −24 x 1+2 x 22−8 x 2+ 2 x 23−12 x3 +200 and

Page 15
 Operation Research

h ( x 1 , x 2 , x 3 )=x 1 + x 2+ x3 −11=0

The Lagrangian function

L ( x1 , x 2 , λ ) =f ( x 1 , x 2 )− λ h ( x1 , x 2 , x 3 )

⇒ L ( x 1 , x 2 , λ )=2 x21 −24 x 1+2 x 22−8 x 2+ 2 x 23−12 x 3+ 200−λ ( x1 + x 2 + x 3−11)

The necessary conditions for stationary points

∂L
=4 x1 −24−λ=0
∂ x1

∂L
=4 x 2−8− λ=0
∂ x2

∂L
=4 x 3−12−λ=0
∂ x3

∂L
=− ( x1 + x 2 + x 3−11 ) =0
∂λ

The solution to these simultaneous equations yields the stationary points

x 0=( x 1 , x 2 , x 3 ) =( 6 , 2, 3 ) and λ=0

The sufficient condition for stationary point to be a minimum. Here number of constraint m=1
and number of variables n=3.

∴ n−m=3−1=2. If last two principal minor determinant of the bordered Hessian matrix are
negative than x 0 will be a minimum.

Page 16
 Operation Research

∂h ∂h ∂h

[ ]
0 ∂ x1 ∂ x2 ∂ x3
∂h
∂2 L 2
∂ L ∂2 L 0 1 1 1
∂ x1
B O P
H ( x0 )= T[
P Q
=
∂h
∂ x2
]
∂h
∂ x21
∂2 L
∂ x2 ∂ x1
∂2 L
∂ x1 ∂ x2
∂2 L
∂ x1 ∂ x3
∂2 L
∂ x22 ∂ x 2 ∂ x 3
∂2 L ∂2 L
=
1
1
1
[ ]
4
0
0
0
4
0
0
0
4

∂ x3 ∂ x3 ∂ x1 ∂ x 3 ∂ x 2 ∂ x 23

0 1 1
∆ =
1 0 4[ ]
∴ 3 1 4 0 =−8< 0

0 1 1 1
∆ 4= 1
1
1
[ ] 4
0
0
0
4
0
0 =−48<0
0
4

Since ∆ 3< 0 and ∆ 4 <0 the stationary point x 0=(6 , 2, 3) is a minimum and minimum value of
z=102

∴ The solution is x 1=6 , x 2=2 , x 3=3 and minimum z=102.

Example-21. Solve the non linear programming problem

Minimize z=2 x 21+ x 22 +3 x 23+10 x 1 +8 x2 +6 x 3

Subject to x 1+ x2 + x 3=20

x1, x2 , x3≥ 0

Solution: Let the objective function

z=f ( x1 , x2 , x3 ) =2 x21 + x 22 +3 x23 +10 x 1+ 8 x 2 +6 x 3 and

h ( x 1 , x 2 , x 3 )=x 1 + x 2+ x3 −20=0

The Lagrangian function

Page 17
 Operation Research

L ( x1 , x 2 , x 3 , λ ) =f ( x 1 , x 2 ) −λ h ( x 1 , x 2 , x 3 )

⇒ L ( x 1 , x 2 , x 3 , λ )=2 x 21+ x 22 +3 x 23+10 x 1 +8 x2 +6 x 3−λ ( x 1+ x 2 + x 3−20)

The necessary conditions for stationary points

∂L
=4 x1 +10−λ=0
∂ x1

∂L
=2 x 2+8−λ=0
∂ x2

∂L
=6 x 3 +6−λ=0
∂ x3

∂L
=− ( x1 + x 2 + x 3−20 ) =0
∂λ

The solution to these simultaneous equations yields the stationary points

x 0=( x 1 , x 2 , x 3 ) =( 5 ,11, 4 ) and λ=30

Here, number of constraint m=1 and number of variables n=3. The sufficient condition for
stationary point x 0 to be a minimum is that last 3−1=2 principal minor determinant i.e, ∆ 3 and
∆ 4 of the bordered Hessian matrix are negative i.e, has sign of the form (−1 )m =(−1)1=−ve.

∂h ∂h ∂h

[ ]
0 ∂ x1 ∂ x2 ∂ x3
∂h
∂2 L 2
∂ L ∂2 L 0 1 1 1
∂ x1
O P
H B ( x0 )= T
P Q[ =
∂h
∂ x2
]
∂h
∂ x21
∂2 L
∂ x2 ∂ x1
∂2 L
∂ x1 ∂ x2
∂2 L
∂ x1 ∂ x3
∂2 L
∂ x22 ∂ x 2 ∂ x 3
∂2 L ∂2 L
=
1
1
1
[ ]
4
0
0
0
2
0
0
0
6

∂ x3 ∂ x3 ∂ x1 ∂ x 3 ∂ x 2 ∂ x 23

0 1 1

[ ]
∴ ∆ 3= 1 4 0 =−6<0
1 0 2

Page 18
 Operation Research

0 1 1 1
∆ 4= 1
1
1
[ ] 4
0
0
0
2
0
0 =−44< 0
0
6

Since ∆ 3< 0 and ∆ 4 <0 the stationary point x 0=(5 ,11, 4) is a minimum and minimum value of
z=381

∴ The solution is x 1=5 , x2 =11 , x 3=4 and minimum z=381.

Example-22. Using the method of Lagrangian multipliers. Solve the non linear programming
problem

Minimize z=6 x 1 +8 x2 −x21 −x22

Subject to 4 x1 +3 x 2=16

3 x 1+5 x 2=15

x1 , x2 ≥ 0

Solution: Let the objective function

z=f ( x1 , x2 ) =6 x 1+ 8 x 2−x 21−x 22 and

h1 ( x 1 , x 2 )=4 x 1+3 x 2−16=0

h2 ( x 1 , x 2 )=3 x 1+ 5 x 2−15=0

The Lagrangian function

L ( x1 , x 2 , λ1 , λ2 )=f ( x 1 , x 2 )−λ 1 h1 ( x 1 , x 2 )−λ 2 h2 ( x 1 , x 2 )

⇒ L ( x 1 , x 2 , λ1 , λ2 ) =6 x1 +8 x 2−x 21−x 22−λ 1 ( 4 x 1+3 x 2−16 )−λ 2( 3 x 1 +5 x2 −15)

The necessary conditions for stationary point

Page 19
 Operation Research

∂L
=6−2 x 1−4 λ 1−3 λ2=0
∂ x1

∂L
=8−2 x 2−3 λ 1−5 λ2=0
∂ x2

∂L
=−( 4 x1 +3 x 2−16 ) =0
∂ λ1

∂L
=−( 3 x 1+5 x 2−15 ) =0
∂ λ2

The solution to these simultaneous equations yields the stationary point

x 0=( x 1 , x 2 )= ( 3511 , 1211 ).

The sufficient condition for stationary point x 0 to be a minimum if the bordered Hessian matrix
determinant has sign of the form (−1 )m i.e, positive

∂h 1 ∂h 1

[ ]
0 0 ∂ x1 ∂ x2
0 0 ∂h 2 ∂h 2 0 0 4 3
O P
[
H B ( x0 )= T
P Q
=
∂h 1
∂ x1
∂h 1
] ∂h 2
∂ x1
∂h 2
∂ x1 ∂ x2
∂2 L ∂2 L
∂ x1 ∂ x 1 ∂ x 2
2

2
∂ L 2
∂ L
[
= 0
4
3
3
0

5
3
−2 0
5

0 −2
]
∂ x2 ∂ x2 ∂ x 2 ∂ x 1 ∂ x22

0 0 4 3
∴|H B|= 0
4
3
[ 3
0

5
3
−2 0
5 =121> 0

0 −2
]
Since |H B|>0 , x 0= ( 3511 , 1211 )is a minimum point and minimum value of
Page 20
 Operation Research

1997
z=
121

35 12 1997
∴ The solution is x 1= , x 2= and minimum z= .
11 11 121

Example-23. Solve the non linear programming problem using Lagrangian multipliers

Optimize z=x 21−10 x 1+ x 22−6 x 2 + x 23−4 x 3

Subject to x 1+ x2 + x 3=7

x1, x2 , x3≥ 0

Solution: Let the objective function

z=f ( x1 , x2 , x3 ) =x 21−10 x1 + x 22−6 x 2 + x 23−4 x 3 and

h ( x 1 , x 2 , x 3 )=x 1 + x 2+ x3 −7=0

The Lagrangian function

L ( x1 , x 2 , x 3 , λ ) =f ( x 1 , x 2 ) −λ h ( x 1 , x 2 , x 3 )

⇒ L ( x 1 , x 2 , x 3 , λ )=x 21−10 x 1+ x 22−6 x 2 + x 23−4 x3 −λ( x 1 + x 2+ x 3 −7)

The necessary conditions for stationary points

∂L
=2 x1 −10−λ=0
∂ x1

∂L
=2 x 2−6− λ=0
∂ x2

∂L
=2 x 3−4−λ=0
∂ x3

∂L
=− ( x1 + x 2 + x 3−7 ) =0
∂λ

The solution to these simultaneous equations yields the stationary points

Page 21
 Operation Research

x 0=( x 1 , x 2 , x 3 ) =( 4 ,2 , 1 ) and λ=−2

The necessary conditions for a maximum or minimum at x 0. Here, number of constraint m=1
and number of variables n=3. The bordered Hessian matrix is

∂h ∂h ∂h

[ ]
0 ∂ x1 ∂ x2 ∂ x3
∂h
∂2 L 2
∂ L ∂2 L 0 1 1 1
∂ x1
H B ( x0 )=[ O P
PT Q
=]∂h
∂ x2
∂h
∂ x21
∂2 L
∂ x2 ∂ x1
∂2 L
∂ x1 ∂ x2
∂2 L
∂ x1 ∂ x3
∂2 L
∂ x22 ∂ x 2 ∂ x 3
∂2 L ∂2 L
=
1
1
1
[ ]
2
0
0
0
2
0
0
0
2

∂ x3 ∂ x3 ∂ x1 ∂ x 3 ∂ x 2 ∂ x 23

Last n−m=3−1=2 principal minor determinants starting with order 2 m+ 1=3.

0 1 1

[ ]
∴ ∆ 3= 1 2 0 =−4 <0
1 0 2

0 1 1 1

[ ]
∆ 4= 1
1
1
2
0
0
0
2
0
0 =−12< 0
0
2

Since, the principal minor determinant ∆ 3< 0 and ∆ 4 <0 . i.e, sign of last two principal minor is

(−1 )m =(−1)1=−ve.the stationary point x 0=(5 ,11, 4) is a minimum point of the objective
function with minimum z=−35

∴ The solution is x 1=4 , x 2=2, x 3=1and minimum z=−35.

Example-24. Solve the non linear programming problem

Optimize z=4 x 21+2 x 22+ x23 −4 x 1 x 2

Subject to x 1+ x2 + x 3=15

Page 22
 Operation Research

2 x1 −x2 +2 x 3=20

x1 , x2 , x3 ≥ 0

Solution: Let the objective function

z=f ( x1 , x2 , x3 ) =4 x21 +2 x 22+ x 23−4 x 1 x 2 and

h1 ( x 1 , x 2 , x 3 )=x 1 + x 2+ x 3−15=0

h2 ( x 1 , x 2 , x 3 )=2 x 1−x 2+ 2 x 3−20=0

The Lagrangian function

L ( x1 , x 2 , x 3 , λ1 , λ2 ) =f ( x 1 , x 2 , x 3 )−λ 1 h 1 ( x 1 , x 2 , x 3 )− λ2 h2 ( x 1 , x 2 , x 3 )

¿ 4 x21 +2 x 22+ x 23−4 x 1 x 2−λ 1 ( x 1 + x 2+ x 3−15 )−λ 2 (2 x 1−x 2 +2 x 3−20)

The necessary conditions for stationary point

∂L
=8 x 1−4 x2 −λ1−2 λ2 =0
∂ x1

∂L
=4 x 2−4 x 1−λ 1+ λ2=0
∂ x2

∂L
=2 x 3−λ1−2 λ 2=0
∂ x3

∂L
=−( x 1+ x2 + x 3−15 ) =0
∂ λ1

∂L
=−( 2 x1 −x2 +2 x 3−20 ) =0
∂ λ2

The solution to these simultaneous equations yields the stationary point

Page 23
 Operation Research

( 339 , 103 , 8 )and λ=( λ , λ )=( 409 , 529 )

x 0= ( x 1 , x 2 , x 3 ) = 1 2

The sufficient condition for a maximum or minimum at stationary point x 0. The bordered
Hessian matrix

∂ h1 ∂ h1 ∂h 1

[ ]
0 0 ∂ x1 ∂ x2 ∂ x3
0 0 ∂ h2 ∂ h2 ∂h 2
∂ x1 ∂ x2 ∂ x3
∂2 L 2
O P ∂h 1 ∂ h2 ∂ L ∂2 L
B
H ( x0 )= T
P Q [
=
∂ x1 ] ∂ x1 ∂ x 21 ∂ x1 ∂ x2 ∂ x 1 ∂ x3
∂h 1 ∂ h2 ∂2 L ∂2 L ∂2 L
∂ x2 ∂ x2 ∂ x2 ∂ x1 ∂ x 22 ∂ x2 ∂ x3
∂h 1 ∂ h2 ∂2 L ∂2 L ∂2 L
2
∂ x3 ∂ x3 ∂ x3 ∂ x1 ∂ x3 ∂ x2 ∂ x3

0 0 1 1 1

[
¿ 1
1
1
0 0
2
−1
2
2 −1 2
8 0 0
0 4 0
0 0 2
]
Here, number of constraint m=2 and number of variables n=3. ∴ n−m=3−2=1 minor of
order 2 m+ 1=5.

0 0 1 1 3
0
∴|H B|= 1
1
3
[ ] 0
5
2
1
5
2
0
0
2
0
2
0
1
0 =460> 0
0
2

m 2
∴|H B| has sign (−1 ) =(−1) =+ ve

The stationary point x 0= ( 339 , 103 , 8)is a minimum point with minimum value of

Page 24
 Operation Research

33 2 10 2 ( )2 33 10 820
z=4 ( ) ( )
9
+2
3
+ 8 −4 × × =
9 3 9

33 10 820
∴ The solution is x 1= , x = , x =8 and minimum z= .
9 2 3 3 9

Example-25. Solve the non linear programming problem using the method of Lagrangian
multipliers

Minimize z=x 21 + x 22+ x 23

Subject to x 1+ x2 +3 x 3=2

5 x 1+2 x 2+ x3 =5

x1, x2 , x3≥ 0

Solution: Let the objective function

z=f ( x1 , x2 , x3 ) =x 21+ x 22 + x 23 and

h1 ( x 1 , x 2 , x 3 )=x 1 + x 2+3 x 3−2=0

h2 ( x 1 , x 2 , x 3 )=5 x 1+ 2 x 2 + x 3−5=0

The Lagrangian function

L ( x1 , x 2 , x 3 , λ1 , λ2 ) =f ( x 1 , x 2 , x 3 )−λ 1 h 1 ( x 1 , x 2 , x 3 )− λ2 h2 ( x 1 , x 2 , x 3 )

⇒ L ( x 1 , x 2 , x 3 , λ 1 , λ2 ) =x 21+ x 22 + x 23−λ1 ( x 1+ x 2 +3 x 3−2 ) −λ2 (5 x 1+2 x 2+ x3 −5)

The necessary conditions for stationary point

∂L
=2 x1 −λ1−5 λ 2=0
∂ x1

Page 25
 Operation Research

∂L
=2 x 2−λ1−2 λ 2=0
∂ x2

∂L
=2 x 3−3 λ1− λ2=0
∂ x3

∂L
=−( x 1+ x2 +3 x 3−2 ) =0
∂ λ1

∂L
=−( 5 x 1+2 x 2+ x3 −5 )=0
∂ λ2

The solution to these simultaneous equations yields the stationary point

( 3746 , 238 , 1346 )and λ=( λ , λ )=( 232 , 237 )

x 0= ( x 1 , x 2 , x 3 ) = 1 2

The sufficient condition for stationary point x 0 to be a minimum. The bordered Hessian matrix

∂ h1 ∂ h1 ∂h 1

[ ]
0 0 ∂ x1 ∂ x2 ∂ x3
0 0 ∂ h2 ∂ h2 ∂h 2
∂ x1 ∂ x2 ∂ x3 0 0 1 1 3

H B ( x0 )= [ O P
T
P Q
=
∂h 1
∂ x1
∂h 1
∂ x2
] ∂ h2
∂ x1
∂ h2
∂ x2
∂2 L
∂ x 21
∂2 L
∂ x2 ∂ x1
2
∂ L
∂ x1 ∂ x2
∂2 L
∂ x 22
∂2 L
∂ x 1 ∂ x3
∂2 L
∂ x2 ∂ x3
0
=1
1
3
[ ]
0
5
2
1
5
2
0
0
2
0
2
0
1
0
0
2

∂h 1 ∂ h2 ∂2 L ∂2 L ∂2 L
2
∂ x3 ∂ x3 ∂ x3 ∂ x1 ∂ x3 ∂ x2 ∂ x3

Here, number of constraint m=2 and number of variables n=3. ∴ n−m=3−2=1 minor of
order 2 m+ 1=5. Thus we need to check the determinant of H B only, which must have the sign of

(−1 )m =(−1)2=+ ve at a minimum.

Page 26
 Operation Research

0 0 1 1 3
0
∴|H B|= 1
1
3
[ ] 0
5
2
1
5
2
0
0
2
0
2
0
1
0 =460> 0
0
2

37 8 13
The stationary point x 0= ( , ,
46 23 46 )
is a minimum with minimum value of

37 2 8 2 13 2 897
z= ( ) ( )( )
46
+
23
+
46
=
1058

37 8 13 897
∴ The solution is x 1= , x 2= , x 3 = and minimum z= .
46 23 46 1058

Example-26. Solve the non linear programming problem using the method of Lagrangian
multipliers

Minimize z=x 21 + x 22+ x 23

Subject to 4 x1 + x 22 +2 x 3=14

x1, x2 , x3≥ 0

Also write the feasible solution.

Solution: Let the objective function

z=f ( x1 , x2 , x3 ) =x 21+ x 22 + x 23 and

h ( x 1 , x 2 , x 3 )=4 x 1+ x22 +2 x 3−14=0

The Lagrangian function

L ( x1 , x 2 , x 3 , λ ) =f ( x 1 , x 2 , x 3 ) −λ h ( x 1 , x 2 , x 3 )

⇒ L ( x 1 , x 2 , x 3 , λ )=x 21 + x 22+ x 23− λ ( 4 x 1 + x 22+ 2 x 3−14 )

The necessary conditions for stationary point

Page 27
 Operation Research

∂L
=2 x1 −4 λ=0
∂ x1

∂L
=2 x 2−3 x 2 λ=0
∂ x2

∂L
=2 x 3−2 λ=0
∂ x3

∂L
=−( 4 x1 + x 22 +2 x 3−14 ) =0
∂λ

The solution to these simultaneous equations yields the stationary point

( x 0 , λ0 )1=( x 1 , x 2 , x 3 , λ ) =(2 , 2 ,1 , 1)

( x 0 , λ0 )2=(2 ,−2 , 1, 1)

14 7 7
(
( x 0 , λ0 )3= 5 ,0 , 5 , 5 )
The sufficient condition for stationary points to be a minimum. The bordered Hessian matrix

∂h ∂h ∂h

[ ]
0 ∂ x1 ∂ x2 ∂ x3
∂h
∂2 L 2
∂ L ∂2 L
∂ x1
O P ∂ x21 ∂ x1 ∂ x2 ∂ x1 ∂ x3
H B ( x0 )= [ PT Q
= ]
∂h ∂2 L ∂2 L ∂2 L
∂ x2 ∂ x2 ∂ x1 ∂ x22 ∂ x 2 ∂ x 3
∂h ∂2 L ∂2 L ∂2 L
∂ x3 ∂ x3 ∂ x1 ∂ x 3 ∂ x 2 ∂ x 23

0 4 2 x2 2
¿
[ 4 2
2 x2 0
2 0
0
2−2 λ
0
0
0
2
]
Page 28
 Operation Research

Here, number of constraint m=1 and number of variables n=3.For a stationary point to be
minimum, the sign of the last n−m=3−1=2 principal minor determinants starting with order
2 m+ 1=3 must be that of (−1 )m =(−1)1=−ve .

Thus for ( x 0 , λ0 )1=(2 ,2 , 1 ,1)

0 4 4 2
\ H=
4
4
2
[ ] 2
0
0
0
0
0
0
0
2

0 4 4
∴ 3 4 2
∆ =
4 0 [ ] 0 =−32<0 and
0

0 4 4 2

[ ]
∆ 4= 4
4
2
2
0
0
0 0 =−64<0
0 0
0 2

This shows that (2 , 2, 1 ,1)is a minimum point.

Thus for ( x 0 , λ0 )1=(2 ,−2 , 1, 1)

0 4 −4 2
\ H=
[
4 2 0 0
−4 0 0 0
2 0 0 2
]
0 4 −4

[
∴ ∆ 3= 4 2 0 =−32<0 and
−4 0 0 ]
0 4 −4 2

[
∆ 4= 4 2 0
−4 0 0
2 0 0
]
0 =−64<0
0
2

This shows that (2 ,−2 , 1 ,1)is a minimum point.

Page 29
 Operation Research

Thus for ( x 0 , λ0 )1= ( 145 , 0 , 75 , 75 )=(2.8 , 0 ,1.4 ,1.4 )

0 4 0 2
\ H=
0
4

2
[ 0
0
2 0
−.8
0
0
0
2
]
0 4 0

[ ]
∴ ∆ 3= 4 2 0 =12.8>0 and
0 0 0

0 4 0 2

[
∆ 4= 4 2 0
0 0 −.8
2 0 0
0
2
]
0 =32<0

This shows that (2.8 , 0 , 1.4 , 1.4) does not satisfy the sufficient conditions of either a maximum
or a minimum does not mean that it is not an extreme point. This follows because the given
conditions are sufficient only.

Consider the polynomial equation

∂h ∂h ∂h

[ ]
0 ∂ x1 ∂ x2 ∂ x3
∂h 2
∂ L ∂2 L ∂2 L
∂ x1 −μ
O P ∂ x 21 ∂ x1 ∂ x2 ∂ x1 ∂ x 3
∆= [ T
P Q−μI
=
∂h ] ∂2 L ∂2 L
−μ
∂2 L
∂ x2 ∂ x 2 ∂ x1 ∂ x 22 ∂ x2 ∂ x3
∂2 L 2
∂h ∂ L ∂2 L
−μ
∂ x3 ∂ x 3 ∂ x1 ∂ x 3 ∂ x 2 ∂ x 23

Page 30
 Operation Research

0 4 2 x2 2
¿
[ 4 2−μ 0
2 x 2 0 2−2 λ−μ
2 0 0
0
0
2−μ
]
2 8
For ( x 0 , λ0 )1=( 2 , 2 ,1 , 1 ) ,|∆|=0⇒ |∆|=9 μ −26 μ+ 16=0 has roots μ=2 or . Because all μ>0.
9

( x 0 )1=(2 ,2 , 1) is a minimum point with minimum z=9.

2 8
For ( x 0 , λ0 )2=( 2 ,−2, 1 ,1 ) ,|∆|=0⇒ |∆|=9 μ −26 μ+16=0 has roots μ=2 or . Because all μ>0.
9

( x 0 )1=(2 ,−2 , 1) is a minimum point with minimum z=9.

For ( x 0 , λ0 )3= ( 145 ,0 , 75 , 75 ) ,|∆|=0 ⇒|∆|=5 μ −6 μ−8=0 has roots μ=2 or 0.8 which means that
2

14 7
( x 0 )3=( 5 ,0 , 5 ) is not a extreme point.

Here ( x 0 )1=(2 ,2 , 1) is only feasible solution.

∴ Feasible solution x 1=2 , x 2=2, x 3=1 and minimumz=9.

Page 31