Nonlinear Programming

Quadratic Simplex Method

Example

Maximize f(x) = 2x1 + 3x2 –x12 – x22

subject to
x1 + x2 £ 2
2x1 + x2 £ 3

x1, x2 ³ 0.

Solution.

First, find that a given function is concave or convex.
df(x)/dx1 = 2 – 2x1
df(x)/dx2 = 3 – 2x2
d2f(x)/dx12 = – 2
d2f(x)/dx22 = – 2
d2f(x)/dx1.dx2 = 0

H(x) = d2f(x)/dx12 d2f(x)/dx1.dx2
d2f(x)/dx1.dx2 d2f(x)/dx22

H(x) = – 2 0
0 –2

I = 1 0
0 1

l(I) l 0
0 l

H(x) – l(I) – 2 0
–
l 0
0 –2 0 l

H(x) – l(I) – 2 – l 0
0 – 2 – l

Determinant of H(x) – l(I) = 0

(– 2 – l ) X (– 2 – l ) – 0 X 0 = 0
l2 + 4l + 4 = 0
l2 + 2l + 2l + 4 = 0
l(l + 2) + 2(l + 2) = 0
l = –2

Since l is negative, the given problem has a concave objective function.

f (x, l ) = 2x1 + 3x2 –x12 – x22 + l1(2 – x1 – x2) + l2(3 – 2x1 – x2)

Differentiate w.r.t. x1
f x1 = 2 – 2x1 – l1 – 2l2 = – m1.....(i)

Differentiate w.r.t. x2
f x2 = 3 – 2x2 – l1 – l2 = – m2.....(ii)

Where m1 and m2 are surplus variables.

x1, x2, l1, l2, m1, m2 ³ 0
m1x1 = 0, m2x2 = 0

Differentiate w.r.t. l 1
f l1 = 2 – x1 – x2 = S1.....(iii)

Differentiate w.r.t. l 2
f l2 = 3 – 2x1 – x2 = S2.....(iv)

Where S1 and S2 are slack variables.

l1S1 = 0, l2S2 = 0

Kuhn Tucker Conditions are given by

From equations (i), (ii), (iii) & (iv), we get

2x1 + l1 + 2l2 – m1 = 2
2x2 + l1 + l2 – m2 = 3
x1 + x2 + S1 = 2
2x1 + x2 + S2 = 3

Introducing artificial variables A1and A2 to the first two equations to obtain a feasible solution of the problem.

Maximize –A1 –A2

subject to

2x1 + l1 + 2l2 – m1 + A1 = 2
2x2 + l1 + l2 – m2 + A2 = 3
x1 + x2 + S1 = 2
2x1 + x2 + S2 = 3

Now, we solve the above problem by Simplex method.

Table 1

 
 cj 0 0 0 0 0 0 0 0 –1 –1
 
cB Basic variables
B 		x1 x2 m1 m2 S1 S2 l1 l2 A1 A2 Solution values
b (=XB)
–1 A1 2 0 –1 0 0 0 1 2 1 0 2
–1 A2 0 2 0 –1 0 0 1 1 0 1 3
0 S1 1 1 0 0 1 0 0 0 0 0 2
0 S2 2 1 0 0 0 1 0 0 0 0 3
zj–cj
 
 –2 –2 1 1 0 0 –2 –3 0 0
 

If we ensure that the pairs ( li, Si) and (mj, xj) are not basic variables simultaneously then the conditions Sili = 0 and xjmj = 0 will be automatically satisfied.
Although zj – cj is lowest corresponding to l2 column, it can’t be made a basic variable as S2 is already a basic variable. Hence, A1 departs and x1 enters.


Table 2

 
 cj 0 0 0 0 0 0 0 0 –1
 
cB Basic variables
B 		x1 x2 m1 m2 S1 S2 l1 l2 A2 Solution values
b (=XB)
0 x1 1 0 –1/2 0 0 0 1/2 1 0 1
–1 A2 0 2 0 –1 0 0 1 1 1 3
0 S1 0 1 1/2 0 1 0 –1/2 –1 0 1
0 S2 0 1 1 0 0 1 –1 –2 0 1
zj–cj
 
 0 –2 0 1 0 0 –1 –1 0
 

Table 3

 
 cj 0 0 0 0 0 0 0 0 –1
 
cB Basic Variables
B 		x1 x2 m1 m2 S1 S2 l1 l2 A2 Solution values
b (=XB)
0 x1 1 0 –1/2 0 0 0 1/2 1 0 1
–1 A2 0 0 –1 –1 –2 0 2 3 1 1
0 x2 0 1 1/2 0 1 0 –1/2 –1 0 1
0 S2 0 0 1/2 0 –1 1 –1/2 –1 0 0
zj–cj
 
 0 0 1 1 2 0 –2 –3 0
 

Since S2 is a basic variable, l2 can’t be made a basic variable.
Therefore, the variable A2 departs and l1 enters.

Table 4

 
 cj 0 0 0 0 0 0 0 0
 
cB Basic variables
B		 x1 x2 m1 m2 S1 S2 l1 l2 Solution values
b (=XB)
0 x1 1 0 –1/4 1/4 1/2 0 0 1/4 3/4
0 l1 0 0 –1/2 –1/2 –1 0 1 3/2 1/2
0 x2 0 1 1/4 –1/4 1/2 0 0 –1/4 5/4
0 S2 0 0 1/4 –1/4 –3/2 1 0 –1/4 1/4
zj–cj
 
 0 0 0 0 0 0 0 0
 

The values for x1 and x2 are 3/4 and 5/4 respectively.
The associated optimal value of the objective function is f(x) = 2 X 3/4 + 3 X 5/4 – (3/4)2 – (5/4)2 = 25/8

 

Operations Research Contents
   
Copyright © www.universalteacher.com