Optimization Techniques

CLASSIFICATION OF OPTIMIZATION
TECHNIQUES

 Based on number of objective functions

 Single objective
 Multi objective
 Based on constraints
 Unconstrained
 Constrained
 Nature of functions
 Non Linear Programming
 Linear Programming
 Geometric Programming
 Quadratic Programming
 Permissible value of Design variables
 Real valued
 Integer Programming
 TECHNIQUES TO BE DISCUSSED
 Constrained Optimization Techniques
Linear Programming
 Graphical LP Solution (2 variables)
 Simplex Method
 Duality Method
 Transportation and Assignment Models
 Goal Programming (Multiple Objectives)
 Integer Programming
Unconstrained Optimization Techniques
(Non Linear and Single variable)
Region Elimination Method
Point Estimation Method
Gradient Method
 TECHNIQUES TO BE DISCUSSED

Unconstrained Optimization Techniques

(Non Linear and Multi variable)
Gradient Based Methods
Direct Search methods
 Constrained Optimization Techniques (Non Linear)
 KKT (Karush-Kuhn-Tucker) Conditions
 Feasible Direction Method
 Quadratic Programming
 Evolutionary Algorithms
 Genetic Algorithm
 Simulated Annealing Algorithm
GRAPHICAL METHOD
 Steps for solving the LPP by Graphical method

Determination of the feasible solution space

Draw the variable constraints (for e.g. the non negativity

restrictions on the decision variables restrict the solution
space to the first quadrant only)

Draw the main constraints by changing the inequalities

into equations and graph the resulting straight lines.

Draw an arrow in the direction of the inequality.

Find the direction towards which the objective function

is optimum and hence find the optimum solution.
 Example 1
Optimal
Solution
y
4

Maximize x+y
3
Subject to: x + 2 y  2 Feasible
Region
x3 2

y4
1
x0 y0
0 x
0 1 2 3
 Example 2
Maximize Z = x + 5y

Subject to: -x + 3y ≤ 10 y
8 Optimal
x+y  6 Solution

x-y  2 6

x0 y0 ( 2, 4 )
4
( 0, 10/3 )
The Vertices are :
2 PF ( 4, 2 )
(0, 0), (2, 0), (4, 2), (2, 4),
x
0
(0,10/3) 2
0 4 6 8
 The value of the objective function is computed at
these are:

Z=0 at (0, 0)

Z=2 at (2, 0)

Z = 14 at (4, 2)

Z = 22 at (2 ,4)

Z = 50/3 at (0, 10/3)

Obviously, the maximum occurs at vertex (2, 4) with the

maximum value 22. Hence,
Optimal Solution: x=2, y=4, z=22.
 Example 3

y
40

Minimize x + 1/3 y
30
Subject to: x + y  20 Feasible
-2 x + 5 y  150 20 Region

x5
10
x0 y0
x
0
Optimal
Solution 0 10 20 30 40
 Special Cases Unbounded
solution
Alternative
Optima

Infeasible
solution
 SIMPLEX METHOD

 The Simplex Method is an iterative method which

moves from one vertex to another vertex (in the
direction of optimum improvement) until the optimal
solution is reached
Requirements of Simplex method

• All constraints are of ≤ type

• All right-hand-side values (bj, j=1, …,m) must

be non-negative

• All the variables are nonnegative

13
Changing inequalities into equations (using SLACK
and SURPLUS variables)

SLACK VARIABLE: A slack variable is used to change a (  )

inequality to equation.

SURPLUS VARIABLE: A surplus variable to change a (≥)

inequality to equation.

Note :
• The slack and surplus variables are always non-negative

• If the RHS of the equation is negative then multiply both

sides of the equation by -1.

14
Example 1:

Write the following LPP in the standard form:

Maximize z = x1 + x2
subject to
x1 + 2x2  6 --- (1)

2x1 + x2 ≥ 16 --- (2)

x1 , x2 ≥ 0

16
Change all inequalities into equations by using slack or
surplus variables
Slack variable

x1 + 2x2 + s1 = 6

2x1 + x2 – s2 = 16
Surplus variable

Hence the standard form of the LPP :

Maximize z = x1 + x2
subject to
x1 + 2x2 + s1 = 6

2x1 + x2 – s2 = 16

x1 , x 2 , s1 , s 2 ≥ 0

17
Example 2

Write the following Linear programming problem in

the standard form:
Min z = 3x1 + x2 – x3

Subject to
2x1 – x2+x3  6

x1 + 3x2 -7x3 ≥ -16

x1 ≥ 0, x2 ≤ 0

18
Standard Form
x2 ≤ 0
We will introduce a new variable y2 , defined by
y2 = -x2 , and we will replace x2 by –y2 in the LPP

since x2 ≤ 0  y2 ≥ 0
Unrestricted variables

The unrestricted variables can be written as a function

of two non negative variables.

Here x3 is unrestricted in sign, we introduce two new variables

x3+ ≥ 0 and x3- ≥ 0, and define
x3= x3+- x3-

19
Objective function : 3x1 - y2 – (x3+- x3-)

Constraints:

2x1 – x2+x3  6
 2x1 + y2 + (x3+- x3-) + s1 = 6
x1 + 3x2 -7x3 ≥ -16
 -x1 - 3x2 +7x3 ≤ 16
 -x1 + 3y2 +7(x3+- x3-) + s2 = 16
with
x1 ≥ 0, y2 ≥ 0, x3+ ≥ 0, x3- ≥ 0, s1 ≥ 0, s2 ≥ 0

20
 The LPP in the standard form is:

Min. Z = 3x1 - y2 – (x3+- x3-)

Subject to

2x1 + y2 + (x3+- x3-) + s1 = 6

-x1 + 3y2 +7(x3+- x3-) + s2 = 16
x1 ≥ 0, y2 ≥ 0, x3+ ≥ 0, x3- ≥ 0,
s1 ≥ 0, s2 ≥ 0

21
 Iterative Process of Simplex method

Direction depends on the largest rate of improvement in z

Example
Example
 Simplex Tableau

Non-basic (Zero) variables

Basic variables Basic solutions

Pivot element
Problem Set 3B (Q2)
MATRIX Formulation
in
LPP
LPP (standard form)

Max (or Min) z  c1 x1  c2 x2  ...  cn xn

Subject to
a11 x1  a12 x2  ...  a1n xn  b1
a21 x1  a22 x2  ...  a2 n xn  b2
.
.
am1 x1  am 2 x2  ...  amn xn  bm
x1 , x2 ,..., xn  0, b1 , b2 ,..., bm  0
Using the notations

C   c1 c2 . . cn 
 x,1   b1 
 a11 a12 . . a1n  b 
a  x 
a22 . . a2 n   2  2
 21 b . 
A .  X  . 
   
   . 
 .  .
 xn  bm 
 am1 am 2 . . amn 
Represented as:

 1 c   z   0 
   
 0 A   X  b 
Let B is a m x m non-singular sub-matrix of the
coefficient matrix A.
Let XB be the corresponding set of basic variables
with cB as its associated objective vector. The
corresponding solution (and the objective function
value ) may be computed as follows:

1 -cB   z  0
  X    
0 B   B b 
1
 z  1  CB  0
 X   0  b
 B  B   
  z  1 CB B  0
1

X   1   
 B  0 B  
b

 z  C B B b  C B X B 
1

X    1    B 1 b 
 B  B b   
The general simplex tableau:

 1 cB B   1 c   z   1 cB B   0 
1 1

 1        1   
 0 B   0 A   X   0 B  b 

Multiplying out the matrices, we get

 1 cB B A - C 
1
 z   cB B b 1

 1    1 
0 B A  X  B b 
In matrix form the new tableau will look like
Basic z X Solution
1 1
z 1 cB B A  C cB B b
1
XB 0 1
B A B b
 And in the z-row, the coefficient of xj will be
1
cBB Aj  c j  z j  c j
Finally the solution entry in the z-row will
be 1
cB b
B

In terms of the components xj , the new tableau will look like

Basic z xj Solution
1
z 1 cB B1 Aj  c j cB B b
1 1
XB 0 B Aj B b
Consider the following LPP
Maximize z  x1  x2  2 x3
subject to 2 x1  2 x2  3x3  5
x1  x2  x3  3
x1  x2  x3  2
x1 , x2 , x3  0
 After introducing the slack variables s1 , s2 , s3 to the
respective constraints, the problem becomes

Maximize z  x1  x2  2 x3
Subject to 2 x1  2 x2  3x3  s1 5
x1  x2  x3  s2 3
x1  x2  x3  s3  2
x1 , x2 , x3 , s1 , s2 , s3  0
So the starting simplex tableau is

Basic z x1 x2 x3 S1 S2 S3 Sol

z 1 -1 1 -2 0 0 0 0
S1 0 2 -2 3 1 0 0 5
S2 0 1 1 -1 0 1 0 3
S3 0 1 -1 1 0 0 1 2
 After we apply the Simplex method a portion of
the tableau is as follows:

Basic z x1 x2 x3 s1 s2 s3 Sol

z 1 1 1 0
x2 0 1 3 0
s3 0 0 1 1
x3 0 1 2 0

Find the missing numbers.

Simplex Table

Basic z xj Solution
1
z 1 cB B1 Aj  c j cB B b
1 1
XB 0 B Aj B b
 x ,s ,x
Since 2 3 3are the basic variables in the final tableau
in that order, the basic matrix B is formed by the columns
corresponding to these variables in the starting tableau in that
order.
 2 0 3  1 3 0 
  1 
B  0 1 1 
B   1 0  1
  1 1 1  1 2 0
The new column corresponding to x1 in the final tableau is

1 3 0   2   5 
1     
B A1  0 1 1  1    2 
1 2 0 1   4
So the starting simplex tableau is

Basic z x1 x2 x3 S1 S2 S3 Sol

z 1 -1 1 -2 0 0 0 0
S1 0 2 -2 3 1 0 0 5
S2 0 1 1 -1 0 1 0 3
S3 0 1 -1 1 0 0 1 2
 All these are shown below.
Answer:

Basic z x1 x2 x3 s1 s2 s3 Sol

z 1 1 1 0
x2 0 5 1 3 0
s3 0 2 0 1 1
x3 0 4 1 2 0
The solution column (in the constraint equations) in
the final tableau is
1 3 0 5  14 
1      
B b  0 1 1 3   5  Now CB   1 0 2
1 2 0  2 11
1
Thus entry below x1 in z-row is CB B A1  c1 = 3-1=2
Entries below x2, x3 in z-row are zero as they are
basic variables.
14 
  =8
solution z = CB B b   1 0 2 5
1
 
11
 All these are shown below.
Answer:

Basic z x1 x2 x3 s1 s2 s3 Sol

z 1 2 0 0 1 1 0 8
x2 0 5 1 0 1 3 0 14
s3 0 2 0 0 0 1 1 5
x3 0 4 0 1 1 2 0 11
Consider the following LPP
Maximize z  4 x1  3x2  x3  2 x4
subject to

4 x1  2 x2  x3  x4  5
3x1  x2  2 x3  x4  4
x1 , x2 , x3 , x4  0
After introducing the slack variables s1 , s2
to the respective constraints, the problem becomes

Maximize z  4 x1  3x2  x3  2 x4
subject to

4 x1  2 x2  x3  x4  s1 5
3x1  x2  2 x3  x4  s2  4
x1 , x2 , x3 , x4 , s1 , s2  0
 After we apply the Simplex method a portion of
the final tableau is as follows:

Basic z x1 x2 x3 x4 s1 s2 Sol

z
x2 1 -1
x4 -1 2

Find the missing entries.

Answer:

Basic z x1 x2 x3 x4 s1 s2 Sol

z 1 3 0 2 0 1 1 9
x2 0 1 1 -1 0 1 -1 1
x4 0 2 0 3 1 -1 2 3
Thanks..