Below mentioned methods can be used to solve and optimization

problem with constraints.

Graphical optimization method

It is the simplest and rather

convenient method to solve an optimization problem involving one or two design

variables. If the optimization problem is a function of single design variable,

then optimum solution can be acquired by plotting the objective function and

finding maxima or minima. As for optimization problems involving two design

variables, firstly feasible region is identified by plotting constraint functions.

Then contours (contour represents the curve comprised of points with same value

for objective function) of objective function are drawn and optimum value is

found by visual assessment.

-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-

Optimality criteria method

Optimality criteria are the

condition an objective function must satisfy at its minimum point. Only minimum

for an objective function can be found by using optimality criteria i.e. it

cannot be used to find maximum of objective function. To find maximum of

function, first minimize it and then multiply it by -1 for maximization.

For unconstrained problems

The first order optimality

condition for local minimum of an unconstrained optimality problem f(x) with

single design variable around optimum point is given as

?f () = 0

Where ?f () is the gradient of function f(x).

Points that satisfy this condition are called stationary points.

This condition is necessary but not

sufficient to find minimum as it tells that function value in proximity of is not increasing.

Sufficient condition for minimum

of f(x) is given as

= 0

Where represents hessian matrix.

·

If hessian matrix is positive definite,

stationary point is local maximum.

·

If hessian matrix is negative definite,

stationary point is local minimum.

·

If hessian matrix is indefinite, stationary

point is inflexion point.

·

If hessian matrix is semi-definite, sufficient

conditions are inconclusive.

For constrained problems

Lagrangian

function combines the constraints (equality/inequality) and objective function.

The function is formulated such that the necessary conditions for its minimum

are same as that for constrained problem.

Before

the function definition, all the inequality constraints if any are converted to

equality constraints such that

+ = 0

Where represent the inequality constraint and is known as slack variable. It is squared to

avoid addition of negative number to inequality constraint.

Therefore the Lagrangian function is written

as

L (x, u, v,

s) = f(x) + (x) + +(x)

Here

x is vector of design variables

u ? 0 is

vector of Lagrangian multipliers for inequality constraints

v is

vector of Lagrangian multipliers for equality constraints

s is

vector of slack variables

As above mentioned function is unconstrained, necessary

conditions for its minimum are

Karush-Kuhn-Tucker (KT)

conditions are first order necessary conditions for the minimization of

objective function having constraints on design variables.

Gradient conditions for

optimality of constrained minimization problem is given as

f + + = 0

Here and , i=1,…,p are the

Lagrange multipliers associated with constraints 0 (inequality

constraints) and = 0 (equality

constraints).

Last

set of conditions i.e. are called complementary slackness. It shows

that either or. If

the slack variable that is is zero then the subsequent constraint is

active with a positive Lagrange multiplier . If

the Lagrange multiplier is zero, then the corresponding constraint is

inactive. This shows that first set of condition involve only active inequality

constraints.

For a point to be minimum of a function subjected to equality constraints and inequality

constraints, below mentioned conditions are necessary.

·

should be a regular point

·

Gradient condition f() + + = 0 must be satisfied

·

Constraints should be satisfied at optimum.

·

Switching conditions must be met.

·

Slack

variables must satisfy feasibility conditions i.e.

·

Lagrangian

multipliers should always have positive sign

Linear programming

An optimization problem which has

linear cost/objective function and linear constraint equations is called linear

programming problem. The constraint equations can either be of equality,

inequality or both. But most of the real life optimization problems are of

non-linear type. These problems can be transformed in the linear type problems

by converting them in succession of linear programs. Non-linear problems can

also be converted to linear programming problems by linearizing the objective

function about a known point.

Standard for of linear

programming (L.P) problem can be stated as

Minimize

Subjected to

constraints

Where is mxn matrix consisting of constraints

coefficients.

Is a vector of design variables.

Is a vector comprising of objective function

coefficients.

Vector consisting of

R.H.S of constraint equations.

It can be seen that the

standard for of LP problems is of minimization, i.e. goal is to minimize

objective / cost function. Also all the constraints are linear having R.H.S

positive. Furthermore all the design variables are limited to non-negative.

Conversion to standard LP form

To transform a given optimization

problem to the stand LP form, following steps should be taken

·

If objective function/cost function is of

maximization, convert it into minimization type by multiplying it by -1.

·

Standard LP form entails that there must be

positive constant on right hand side of constraints. It there is a negative

constant, multiply it by negative sign.

·

For less than type constraints, slack variable

is added to convert the constraint to equality. Polarity of slack variable

should be kept positive.

·

To convert greater than type constraints to

equality, positive surplus variable is added.

·

In case of unrestricted variables, they are

written in term of the difference between two new variables. If the difference

if positive, the original variable is positive and vice versa.

·

If a constant is present in objective function

either it can simply be ignored during solving problem as objective function is

not affected by a constant. After obtaining solution, optimum value is altered

to account for constant. Or a duplicate design variable is multiplied by

constant and corresponding constraint to design variable is set with value 1.

Linear programming problems are

convex problems. When LP problems are in their standard form, they stand for n no. of constraint equations and m no.

of optimization variables.

Following cases may arise

·

If m=n, solution can be obtained without

consideration of objective function with only solving constraint equations.

·

If m>n, this represents the case that some

constraints are linearly dependent on other constraints.

·

When m