Non-linear Programming

Problem
 Classical Optimization
• Classical optimization theory uses differential
calculus to determine points of maxima and
minima for unconstrained and constrained
functions.

• This chapter develops necessary and sufficient

conditions for determining maxima and
minima of unconstrained and constrained
functions.

2
 Quadratic forms
Consider the function
f (X ) = a x + a x +L+ a x +
2
11 1
2
22 2
2
nn n

a12 x1 x2 + L + an−1,n xn−1 xn

The above function is called the quadratic or quadratic
form in n-variables.
The above function can be written in the form XTAX,
where X = [x1, x2, …, xn]T be a n-vector and A = (aij) be a
n × n symmetric matrix.
3
 Quadratic forms
Then the quadratic form
Q( X ) = X T A X = ∑ aii xi2 + 2 ∑∑ aij xi x j
i 1≤i ≤ j ≤ n

(or the matrix A (symmetric matrix)) is called

• Positive semi definite if XTAX ≥ 0 for all X ≠ 0.
• Positive definite if XTAX > 0 for all X ≠ 0.
• Negative semi definite if XT A X ≤ 0 for all X ≠ 0.
• Negative definite if XTA X < 0 for all X ≠ 0.
The above quantities of the quadratic form depend on the symmetric
matrix A, therefore we have

4
 Eigenvalue Test
Since matrix A is a real symmetric matrix in XTAX, it
follows that its eigenvalues ( λi) are real. Then XTAX is
Positive definite (positive semi definite) if λi > 0
(λi ≥ 0) i =1, 2, …,n.

Negative definite (negative semi definite) if λi < 0 ,

(λi ≤ 0) i=1,2,…,n

Indefinite, if A has both positive and negative eigenvalues.

5
Matrix minor test
A necessary and sufficient condition for A (any square
matrix ) to be :
Positive definite (positive semi definite) is that all the n
principal minors of A are > 0 ( ≥ 0).

Negative definite (negative semi definite) if kth principal

minor of A has the sign of (-1)k, k = 1, 2, …,n
(kth principal minor of A is zero or has the sign of (-1)k,
k=1,2,…,n )

Indefinite, if none of the above cases happen

6
Examples : Decide the definiteness of the following
quadratic functions:

(1) x12 + 3 x 22 + 5 x 32

(2) − 7 x − 10x − 7 x + 4 x1x2 − 2 x1x3 + 4 x2 x3

2
1
2
2
2
3

(3) x −x
1
2 2
2

7
 Local maximum/Local minimum

Let f (X) = f (x1, x2,…,xn) be a real-valued function of the n variables

x1, x2, …, xn (we assume that f (X) is at least twice differentiable ).
A point X0 is said to be a local maximum of f (X) if there exists an
ε > 0 such that
r
f ( X 0 + h ) ≤ f ( X 0 ) for all h j ≤ ε
r r
Here h = (h1 , h2 ,.., hn ) , X 0 = ( x1 , x2 ,.., xn ) and X 0 + h = ( x10 + h1 , x20 + h2 ,.., xn0 + hn )T .
T 0 0 0 T

A point X0 is said to be a local minimum of f (X) if there exists an

ε > 0 such that r
f ( X 0 + h ) ≥ f ( X 0 ) for all h j ≤ ε
8
 Absolute maximum/Absolute minimum

X0 is called an absolute maximum or global maximum of f (X) if

f (X ) ≤ f (X0) ∀ X.
X0 is called an absolute minimum or global minimum of f (X) if

f (X ) ≥ f (X0) ∀ X.

Taylor Series expansion for functions of several variables

1 T
f ( X 0 + h) − f ( X 0 ) = ∇f ( X 0 )h + h Hh + L
2
Theorem
A necessary condition for X0 to be an optimum
point of f (X) is that ∇f ( X 0 ) = 0
∂f
(that is all the first order partial derivatives are
∂xi
zero at X0.)

Definition: A point X0 for which ∇f ( X 0 ) = 0 is called

a stationary point of f (X) (potential candidate for
local maximum or local minimum).

10
 Theorem

Let X0 be a stationary point of f (X). A sufficient condition

for X0 to be a
local minimum of f (X) is that the Hessian matrix
H(X0) is positive definite;
local maximum of f (X) is that the Hessian matrix
H(X0) is negative definite.

11
 Hessian matrix

 ∂2 f ∂2 f ∂2 f 
 . . 
 ∂x 2
1 ∂x1∂x2 ∂x1∂xn 
 ∂2 f ∂2 f ∂2 f 
 . . 
 ∂x2 ∂x1 ∂x22 ∂x2 ∂xn 
H ( x) =  .
.
 
 . 
 2 
 ∂ f ∂2 f
. . .
∂2 f 
 ∂xn ∂x1 ∂xn ∂x2 ∂xn2 

12
 Example 1
Examine the following function for extreme
points

f (x1, x2,x3) = x1 +2 x3 +x2 x3 –x12 – x 22 – x32

13
Definition:

A function f (X):
n →
is said to be convex function if

domain of f is a convex set and for every X, Y in the domain
f((1-λ) X + λY) ≤ (1-λ) f (X)+ λ f (Y)
for all 0 ≤ λ ≤ 1.

14
In words, this means that if we take any two points x,y ,
then f evaluated at any convex combination of these two
points should be no larger than the same convex
combination of f ( x ) and f ( y ).

Geometrically, the line segment connecting ( x, f ( x )) to

( y, f ( y )) must sit above the graph of f.

15
Convex Function
f is said to be strictly convex if for each pair of points
X, Y on the graph,
f ((1-λ) X + λ Y) < (1-λ) f (X)+ λ f (Y)
for all λ such that 0 < λ < 1.

f is called concave (strictly concave) if – f is convex

(strictly convex).
Examples:
Convex functions: exp(ax); ax+b; x log(x), x>0
Concave functions: ax+b; log(x), x>0
17
A twice differential function f (X):
n →
is said to be
convex function if and only if the Hessian is positive semi
definite for all X.

18
Convexity test for function of one variable
A function of one variable f(x) is

d2 f
convex if 2
≥0
dx

d2 f
concave if 2
≤0
dx

19
Convexity test for functions of 2 variables

quantity convex Strictly concave Strictly

convex concave

fxx fyy - (fxy)2 ≥0 >0 ≥0 >0

fxx ≥0 >0 ≤0 <0

fyy ≥0 >0 ≤0 <0

20
Example: Show that the following function is
convex

f (x1, x2) = -2 x1 x2 +x12 + 2x22

21
Theorem: Let f(X) = XTAX be a positive semi-
definite quadratic form defined over a convex set
S. Then f(X) is a convex function over S.

22
Show that the Sum of two convex functions is
convex.

Use the definition of convex functions to show

that the function is convex over the convex set S

f (x1, x2) = -2 x1 x2 +x12 + 2x22

23
Constraint Optimization
Problems
Constrained optimization Problems
Karush–Kuhn–Tucker (KKT) conditions:

Consider the problem

maximize z = f(X) = f (x1, x2,…, xn)
subject to g(X) ≤ 0 ⇒ [g1(X) ≤ 0
g2(X) ≤ 0
.
gm(X) ≤ 0]
(the non-negativity restrictions, if any, are included in the
above).
25
We define the Lagrangian function
L(X, S, λ) = f(X) – λ [g(X) + s2]
where s, s12, s22,..,sm2 ,are the non negative slack variables
added to g1(X) ≤ 0 ,…. gm(X) ≤ 0 to make them into
equalities. Therefore
L(X, S, λ) = f(X) – [λ1{g1(X) + s12} + λ2{g2(X) +s22}
+… +λm{gm(x) + sm2}]

26
 KKT conditions …
• KKT necessary conditions for optimality are given
by ,
∂L
= ∇f ( X ) − λ∇g ( X ) = 0
∂X
∂L
= − 2 λ i S i = 0, i = 1, 2, ..., m
∂S i
∂L
= −( g ( X ) + S 2 ) = 0
∂λ

27
 KKT conditions …

The KKT necessary conditions for maximization

problem are :
λ≥0
∇f ( X ) − λ ∇g ( X ) = 0
λi g i ( X ) = 0
gi ( X ) ≤ 0 i=1,2…m

These conditions apply to the minimization case as well,

except that λ≤ 0.
28
 KKT conditions …
In scalar notation, this is given by
λi ≥ 0 i=1,2,….m

∂f ∂g1 ∂g 2 ∂g m
− λ1 − λ2 − .. − λm =0
∂x j ∂x j ∂x j ∂x j
j = 1, 2, . . . , n
λi g i ( X ) = 0 i=1,2,….m
gi ( X ) ≤ 0 i=1,2,….m

29
IMPORTANT: The KKT condition can be satisfied at a local minimum (or max.),
a global minimum (or max.) as well as at a saddle point.

We can use the KKT condition to characterize all the stationary points
of the problem, and then perform some additional testing to determine
the optimal solutions of the problem.

30
 Sufficiency of the KKT conditions:

Required conditions
Sense of optimization Objective function Solution space
maximization Concave Convex set
minimization Convex Convex set

31
Example: Use the KKT conditions to find the optimal
solution for the following problem:
maximize f(x1, x2) = x1+ 2x2 – x23
subject to x1 + x2 ≤ 1
x1 ≥0
x2 ≥ 0

32
Solution: Here there are three constraints ,
g1(x1,x2) = x1+x2 - 1 ≤ 0
g2(x1,x2) = -x1 ≤0
g3(x1,x2) = -x2 ≤0
The KKT necessary conditions for maximization
problem are :
λi ≥ 0 ∇ f ( X ) − λ ∇ g ( X ) = 0
λi g i ( X ) = 0
gi ( X ) ≤ 0 i=1,2…m

33
Hence the KKT conditions become
∂f ∂g1 ∂g 2 ∂g 3
− λ1 − λ2 − λ3 =0
∂x1 ∂x1 ∂x1 ∂x1
∂f ∂g 1 ∂g 2 ∂g 3
− λ1 − λ2 − λ3 =0
∂x 2 ∂x 2 ∂x 2 ∂x 2
λ1g1(x1,x2) = 0
λ2g2(x1,x2) = 0 (note: f is concave, gi are
λ3g3(x1,x2) = 0 convex, maximization problem
g1(x1,x2) ≤ 0 ⇒these KKT conditions are
g2(x1,x2) ≤ 0 sufficient at the optimum point)
g3(x1,x2) ≤ 0 and λ1≥0, λ2≥0, λ3≥0
34
i.e. 1 – λ1 + λ2 = 0 (1)
2 – 3x22 – λ1 + λ3 = 0 (2)
λ1(x1 + x2 – 1) = 0 (3)
λ2 x1 =0 (4)
λ3 x2 =0 (5)
x1 + x2 – 1 ≤ 0 (6)
x1 ≥0 (7)
x2 ≥0 (8) λ1 ≥ 0 (9)
λ2 ≥0 (10) and λ3 ≥ 0 (11)

35
(1) gives λ1 = 1 + λ2 ≥ 1 >0 (using 10)
Hence (3) gives x1 + x2 = 1 (12)
Thus both x1, x2 cannot be zero, therefore let x1>0, then (4)
gives λ2 = 0. therefore λ1 = 1
if now x2 = 0, then (2) gives 2 – 0 – 1 + λ3 = 0
=> λ3 < 0 not possible
Therefore x2 > 0, hence (5) gives λ3 = 0 and then (2) gives
x22 = 1/3 => x2 =1/√3.
And so x1 = 1- 1/√3. Therefore
Max f = 1 - 1/√3 + 2/√3 – 1/3√3 = 1 + 2/3√3.
36
Example: Use the KKT conditions to derive an optimal
solution for the following problem:
minimize f (x1, x2) = x12+ x2
subject to x12 + x22 ≤ 9
x1 + x2 ≤ 1
Solution: Here there are two constraints,
g1(x1,x2) = x12+x22 - 9 ≤ 0
g2(x1,x2) = x1 + x2 -1 ≤ 0

37
Thus the KKT conditions are:
λ1 ≤ 0, λ2 ≤ 0 as it is a minimization problem

2x1 - 2λ1x1 - λ2 = 0
1 - 2λ1x2 - λ2 = 0
λ1 ( x + x − 9) = 0
2
1
2
2

λ2 ( x1 + x2 − 1) = 0

x12 + x22 ≤ 9
x1 + x2 ≤ 1

38
 Now λ1 = 0 (from 2) gives λ2 = 1 Not possible.

Hence λ1 ≠ 0 and so x +x =9
2
1
2
2
(5)

Assume λ2 = 0. So (1st equation of ) (2) gives

2 x1 (1 − λ1 ) = 0 Since λ1 ≤ 0 we get x1= 0

From (5), we get x2 = ± 3

2nd equation of (2) says (with λ1 < 0, λ2 = 0 ) x2 = -3

Thus the optimal solution is: The optimal value is :
1
x1 = 0, x2 = − 3, λ1 = − , λ2 = 0 z = −3
6 39
Tutorial Problems

40
Use the KKT conditions to find an optimal solution of the
following problem:

(1) Maximize f(x) = 20x1 + 10 x2

Subject to x12 + x22 ≤ 1
x1 + 2x2 ≤ 2
x1 ≥ 0, x2 ≥ 0

x1 = 2/√5, x2 = 1/√5

41
(2) Maximize f(x) = xy
Subject to x + y2 ≤ 2
x ≥ 0, y ≥ 0

42
(3) Min f(x) = (x-4)2 + (y-4)2
Subject to x + y ≤ 4
x+3y ≤ 9

43
Quadratic Programming

44
Quadratic Programming …
A quadratic programming problem is a non-linear
programming problem of the form
Maximize z = CX + X T DX
subject to AX ≤ b, X ≥ 0
where X = [ x1, x2 ,..., xn ] , b = [b1 , b2 ,..., bn ] , C = [c1, c2 ,..., cn ]
T T

 a11 a12 . . a1n  d11 d12 . . d1n 

a a . . a  d d 
 21 22 2n 
 21 22 . . d2n 

A=  .  D= . 
   
 .   . 
am1 am2 . . amn  dn1 dn2 . . dnn 
Quadratic Programming …

Assume that the n × n matrix D is symmetric and

negative-definite or negative semi-definite
matrix.

This means that the objective function is a

concave function.

Since the constraints are linear, the feasible region

is a convex set.
46
Quadratic Programming …

In scalar notation, the quadratic programming

problem reads:
n n
Maximize z = ∑ c j x j + ∑ d jj x 2j + 2 ∑ ∑d x xj
ij i
j =1 j =1 1≤ i < j ≤ n

subject to a11 x1 + a12 x 2 + . . . + a1 n x n ≤ b1

a 21 x1 + a 22 x 2 + . . . + a 2 n x n ≤ b 2
M
a m 1 x1 + a m 2 x 2 + . . . + a m n x n ≤ b m
x1 , x 2 , . . . , x n ≥ 0

47
Wolfe’s Method to solve a Quadratic Programming
Problem:

The solution to this problem is based on the KKT

conditions. Since the objective function is
concave and the solution space is convex, the
KKT conditions are also sufficient for optimum.

Since there are m + n constraints, we have m + n

Lagrange multipliers; the first m of them are
denoted by λ1, λ2 , …, λm and the last n of them
are denoted by µ1, µ2 , …, µn.
48
Wolfe’s Method…

The KKT (necessary) conditions are:

1. λ1, λ2 ,. . ., λm , µ1, µ2 ,. . ., µn ≥ 0
n m
2 . c j + 2 ∑ d ij xi − ∑ λi a ij + µ j = 0 , j = 1, 2 , . . . , n
i =1 i =1

 n 
3. λi  ∑ aij x j − bi  = 0, i = 1, 2,. . ., m
 j =1 
µ j x j = 0 , j = 1, 2,. . ., n
n
4. ∑a x
j =1
ij j ≤ bi , i = 1, 2,. . ., m and x j ≥ 0, j = 1, 2,. . ., n

49
 Wolfe’s Method…

Denoting the (non-negative) slack variable for the ith constraint

n

∑j =1
a ij x j ≤ b i
by si, the 3rd condition can be written in an equivalent form
as:
3. λi si = 0, i = 1, 2,. . ., m
µ j x j = 0 , j = 1, 2,. . ., n
(Referred to as " Restricted Basis " conditions).

50
Wolfe’s Method…

Also condition(s) (2) can be rewritten as:

n m
− 2 ∑ d ij xi + ∑ λ i a ij − µ j = c j ,
i =1 i =1

j = 1, 2 , . . . , n

and condition(s) (4) can be rewritten as:

n
4. ∑a
j =1
ij x j + si = bi , i = 1, 2,. . ., m

x j ≥ 0 , j = 1, 2,. . ., n

51
 Wolfe’s Method…
Thus we have to find a solution of the following m + n
linear equations in the 2n + m unknowns x j , λi , µ j
n m
− 2 ∑ d ij xi + ∑ λ i a ij − µ j = c j , j = 1, 2 , . . . , n
i =1 i =1
n

∑j =1
a ij x j + s i = b i , i = 1, 2 , . . . , m

λ i si = 0 , i = 1, 2 , . . . , m ,
µ j x j = 0 , j = 1, 2 , . . . , n
λ i ≥ 0 , si ≥ 0 , i = 1, 2 , . . . , m ,
µ j ≥ 0, x j ≥ 0 , j = 1, 2 , . . . , n

52
Wolfe’s Method…

Since we are interested only in a " feasible solution“

of the above system of linear equations, we use
Phase-I method to find such a feasible solution. By
the sufficiency of the KKT conditions, it will be
automatically the optimum solution of the given
quadratic programming problem.

53
Example-1:

Maximize z = 8x1 + 4x2 − x − x

2
1
2
2

subject to x1 + x 2 ≤ 2
x1 , x 2 ≥ 0.

54
Denoting the Lagrange multipliers by λ1, µ1, and µ2,
the KKT conditions are:
1. λ1 , µ1 , µ 2 ≥ 0
2. 8 − 2 x1 − λ1 + µ1 = 0
4 − 2 x2 − λ1 + µ 2 = 0
i.e. 2 x1 + λ1 − µ1 =8
2 x2 + λ1 − µ2 = 4
3. x1 + x2 + s1 = 2, λ1s1 = µ1 x1 = µ 2 x2 = 0
All variables ≥ 0.

55
Introducing artificial variables R1, R2, we thus have to
Minimize r = R1 + R 2
subject to the constraints

2 x1 + λ1 − µ 1 + R1 =8
2 x 2 + λ1 − µ2 + R2 =4
x1 + x 2 + S1 = 2

λ 1 S 1 = µ 1 x1 = µ 2 x 2 = 0

All variables ≥ 0 (We solve by " Modified Simplex " Algorithm).

56
Basic r x1 x2 λ 1 µ1 µ2 R1 R2 s1 Sol
2 2 2 -1 -1 0 0 0 12
r 1 0 0 0 0 0 -1 -1 0 0
R1 0 2 0 1 -1 0 1 0 0 8
R2 0 0 2 1 0 -1 0 1 0 4
S1 0 1 1 0 0 0 0 0 1 2
r 1 0 0 2 -1 -1 0 0 -2 8
R1 0 0 -2 1 -1 0 1 0 -2 4
R2 0 0 2 1 0 -1 0 1 0 4
x1 0 1 1 0 0 0 0 0 1 2
r 1 0 4 0 1 -1 -2 0 2 0
λ1 0 0 -2 1 -1 0 1 0 -2 4
R2 0 0 4 0 1 -1 -1 1 2 0
57
x1 0 1 1 0 0 0 0 0 1 2
Thus we have got the feasible solution
x1 = 2, x2 = 0, λ1 = 4, µ1 = 0, µ2 = 0
and the optimal value is: z = 12

58
Example-2

Maximize z = 8x1 − x + 2x2 + x3

2
1

subject to

x1 + 3 x 2 + 2 x 3 ≤ 12
x1 , x 2 , x 3 ≥ 0

59
Example-2: Solution

Denoting the Lagrange multipliers by λ1,µ1, µ2, and µ3,

the KKT conditions are:
1. λ1 , µ1 , µ 2 , µ 3 ≥ 0
2. 8 − 2 x1 − λ1 + µ1 = 0
2 − 3λ1 + µ2 = 0
1 − 2 λ1 + µ3 = 0
i.e. 2 x1 + λ1 − µ1 =8
3λ1 − µ 2 =2
2 λ1 − µ3 = 1
60
3. x1 + 3 x2 + 2 x3 + S1 = 12,
λ1S1 = 0
µ1 x1 = µ 2 x2 = µ3 x3 = 0 All variables ≥ 0.

Solving this by " Modified Simplex Algorithm

61
Basic r x1 x2 x3 λ1 µ1 µ2 µ3 R1 R2 R3 S1 Sol
2 0 0 6 -1 -1 -1 0 0 0 0 11
r 1 0 0 0 0 0 0 0 -1 -1 -1 0 0
R1 0 2 0 0 1 -1 0 0 1 0 0 0 8
R2 0 0 0 0 3 0 -1 0 0 1 0 0 2
R3 0 0 0 0 2 0 0 -1 0 0 1 0 1
S1 0 1 3 2 0 0 0 0 0 0 0 1 12

Since λ1 S1 = 0 and S1 is in the basis, λ1 cannot enter.

So we allow x1 to enter the basis and of course by minimum
ratio test R1 leaves the basis.

62
Basic r x1 x2 x3 λ1 µ1 µ2 µ3 R1 R2 R3 S1 Sol

r 1 0 0 0 5 0 -1 -1 -1 0 0 0 3

x1 0 1 0 0 1/2 -1/2 0 0 1/2 0 0 0 4

R2 0 0 0 0 3 0 -1 0 0 1 0 0 2
R3 0 0 0 0 2 0 0 -1 0 0 1 0 1
S1 0 0 3 2 -1/2 1/2 0 0 -1/2 0 0 1 8

Since λ1 S1 = 0 and S1 is in the basis, λ1 cannot enter.

So we allow x2 to enter the basis and of course by minimum
ratio test S1 leaves the basis.

63
Basic r x1 x2 x3 λ1 µ1 µ2 µ3 R1 R2 R3 S1 Sol

r 1 0 0 0 5 0 -1 -1 -1 0 0 0 3

x1 0 1 0 0 1/2 -1/2 0 0 1/2 0 0 0 4

R2 0 0 0 0 3 0 -1 0 0 1 0 0 2
R3 0 0 0 0 2 0 0 -1 0 0 1 0 1
x2 0 0 1 2/3 -1/6 1/6 0 0 -1/6 0 0 1/3 8/3

As S1 is not in the basis, now λ1 enters the basis .

And by minimum ratio test R3 leaves the basis.

64
Basic r x1 x2 x3 λ1 µ1 µ2 µ3 R1 R2 R3 S1 Sol

r 1 0 0 0 0 0 -1 3/2 -1 0 -5/2 0 1/2

x1 0 1 0 0 0 -1/2 0 1/4 1/2 0 -1/4 0 15/4

R2 0 0 0 0 0 0 -1 3/2 0 1 -3/2 0 1/2
λ1 0 0 0 0 1 0 0 -1/2 0 0 1/2 0 1/2
x2 0 0 1 2/3 0 1/6 0 -1/12 -1/6 0 1/12 1/3 11/4

Now µ3 enters the basis .

And by minimum ratio test R2 leaves the basis.

65
Basic r x1 x2 x3 λ1 µ1 µ2 µ3 R1 R2 R3 S1 Sol

r 1 0 0 0 0 0 0 0 -1 -1 -1 0 0

x1 0 1 0 0 0 -1/2 1/6 0 1/2 -1/6 0 0 11/3

µ3 0 0 0 0 0 0 -2/3 1 0 2/3 -1 0 1/3
λ1 0 0 0 0 1 0 -1/3 0 0 1/3 0 0 2/3
x2 0 0 1 2/3 0 1/6 -1/18 0 -1/6 1/18 0 1/3 25/9

This is the end of Phase I. Thus the optimal

Thus the optimal solution is: value z is: 193
11 25 9
x1 = , x2 = , x3 = 0
3 9
66
Example-3

Maximize z = 6x1 + 3x2 − 2x − 4x1x2 − 3x

2
1
2
2

subject to x1 + x 2 ≤ 1
2 x1 + 3 x 2 ≤ 4
x1 , x 2 ≥ 0

67
Denoting the Lagrange multipliers by λ1, λ2, µ1, and µ2,
the KKT conditions are:

1. λ1 , λ 2 , µ1 , µ 2 ≥ 0
2. 6 − 4 x1 − 4 x2 − λ1 − 2 λ2 + µ1 = 0
3 − 4 x1 − 6 x2 − λ1 − 3λ2 + µ 2 = 0
i.e. 4 x1 + 4 x2 + λ1 + 2 λ2 − µ1 = 6
4 x1 + 6 x2 + λ1 + 3λ2 − µ 2 = 3

68
 3. x1 + x2 + S1 = 1,
2 x1 + 3 x2 + S 2 = 4,
λ1S1 = λ2 S 2 = 0
µ1 x1 = µ 2 x2 = 0
and all variables ≥ 0.

Solving this by " Modified Simplex Algorithm ", the

optimal solution is:
x1 = 1, x2 = 0 and the optimal z = 4.

69
Basic r x1 x2 λ 1 λ 2 µ1 µ2 R1 R2 S1 S2 Sol
8 10 2 5 -1 -1 0 0 0 0 9
r 1 0 0 0 0 0 0 -1 -1 0 0 0
R1 0 4 4 1 2 -1 0 1 0 0 0 6
R2 0 4 6 1 3 0 -1 0 1 0 0 3
S1 0 1 1 0 0 0 0 0 0 1 0 1
S2 0 2 3 0 0 0 0 0 0 0 1 4
r 1 4/3 0 1/3 0 -1 2/3 0 -5/3 0 0 4
R1 0 4/3 0 1/3 0 -1 2/3 1 -2/3 0 0 4
x2 0 2/3 1 1/6 1/2 0 -1/6 0 1/6 0 0 1/2
S1 0 1/3 0 -1/6 –1/2 0 1/6 0 -1/6 1 0 1/2
S2 0 0 0 -1/2 -3/2 0 1/2 0 -1/2 0 1 5/2
70
Basic r x1 x2 λ1 λ 2 µ1 µ2 R1 R2 S1 S2 Sol
r 1 0 -2 0 -1 -1 1 0 -2 0 0 3
R1 0 4 4 1 2 -1 0 1 0 0 0 6
x1 0 1 3/2 1/4 3/4 0 -1/4 0 1/4 0 0 3/4
S1 0 0 -1/2 -1/4–3/4 0 1/4 0 -1/4 1 0 1/4
S2 0 0 0 -1/2 -3/2 0 1/2 0 -1/2 0 1 5/2
r 1 0 0 1 2 -1 0 0 -1 -4 0 2
R1 0 0 0 1 2 -1 0 1 0 -4 0 2
x1 0 1 1 0 0 0 0 0 0 1 0 1
µ2 0 0 -2 -1 –3 0 1 0 -1 4 0 1
S2 0 0 1 0 0 0 0 0 0 -2 1 71
2
Basic r x1 x2 λ1 λ 2 µ1 µ2 R1 R2 S1 S2 Sol
r 1 0 0 0 0 0 0 -1 -1 0 0 0

λ1 0 0 0 1 2 -1 0 1 0 -4 0 2
x1 0 1 1 0 0 0 0 0 0 1 0 1
µ2 0 0 -2 0 –1 -1 1 1 -1 0 0 3
S2 0 0 1 0 0 0 0 0 0 -2 1 2

Thus the optimum solution is:

x1 = 1, x2 = 0, λ1 = 2, λ2 = 0, µ1 = 0, µ2 = 3

And the optimal value is: z = 4

72
Solve the following quadratic programming problem
Maximize z = 20x1 + 50x2 − 20x12 + 18x1 x2 − 5x22

subject to
x1 + x 2 ≤ 6
x1 + 4 x 2 ≤ 18
x1 , x 2 ≥ 0
Max z = 224
Using Excel solver, the opt solution is: x1=2, x2=4

73
Remark:
If the problem is a minimization problem, say, Minimize z,
we convert it into a maximization problem, Maximize -z.

74