THE UNIVERSITY OF JORDAN
School of Engineering
Department of Civil Engineering
(0951301): Numerical Methods
Dr. Ramia Al-Ajarmeh
Optimization
Optimization
Refer to the Textbook, Chapters 13, 14 and 15
• Optimization involves searching for either the minimum or the
maximum.
• The optimum is the point where the curve is flat. In
mathematical terms, this corresponds to the x value where the
derivative f (x) is equal to zero.
• The second derivative, f (x), indicates whether the optimum is
a minimum or a maximum: if f (x) < 0, the point is a maximum;
if f (x) > 0, the point is a minimum.
Optimization
A function of a single
variable illustrating the
difference between roots
and optima
Optimization
Some common examples of optimization problems in engineering
One-Dimensional Unconstrained Optimization
Refer to the Textbook, Chapter 13
• One-dimensional unconstrained optimization methods are
presented to find the minimum or maximum of a function of a
single variable.
• Optimization in one dimension can be divided into bracketing
and open methods.
• These methods are:
golden-section search
parabolic interpolation
Newton’s method
Brent’s method
One-Dimensional Unconstrained Optimization
• Golden-section search: is an example of a bracketing method that
depends on initial guesses that bracket a single optimum.
• Parabolic interpolation: an alternative approach of bracketing
methods which often converges faster than the golden-section
search, but sometimes diverges.
• Newton’s method: is an open method based on the idea from
calculus that the minimum or maximum can be found by solving
the first derivative f (x) = 0.
• Brent’s method: an advanced hybrid approach that combines the
reliability of the golden-section search with the speed of parabolic
interpolation.
Multi-Dimensional Unconstrained Optimization
Refer to the Textbook, Chapter 14
• Multidimensional unconstrained optimization methods are
presented to find the minimum or maximum of a function of a
several variables.
• Techniques for multidimensional unconstrained optimization
can be classified in a number of ways depending on whether
they require derivative evaluation.
• The approaches that do not require derivative evaluation are
called non-gradient, or direct, methods.
• Those that require derivatives are called gradient, or descent
(or ascent), methods.
Constrained Optimization
Refer to the Textbook, Chapter 15
• Constrained optimization deals with problems where objective
function and constraints are defined.
• For cases of problems where both the objective function and
the constraints are linear, special methods are available that
exploit the linearity of the underlying functions which are called
linear programming methods. They are used in a wide range of
problems in engineering and management.
• Nonlinear constrained optimization is the more general
problem. There are number of software packages can be
employed for this kind of optimization.
Constrained Optimization
Linear Programming
• Linear programming (LP) is an optimization approach that deals
with meeting a desired objective such as maximizing profit or
minimizing cost in the presence of constraints such as limited
resources.
• The term linear connotes that the mathematical functions
representing both the objective and the constraints are linear.
• The term programming does not mean “computer
programming,” but rather, connotes “scheduling” or “setting an
agenda”.
Constrained Optimization
Linear Programming
Standard Form:
The basic linear programming problem consists of two major parts:
the objective function and a set of constraints. For a maximization
problem, the objective function is generally expressed as:
where cj = payoff of each unit of the jth activity that is undertaken
and xj = magnitude of the jth activity. Thus, the value of the objective
function, Z, is the total payoff due to the total number of activities, n.
Constrained Optimization
Linear Programming
Standard Form:
The constraints can be represented generally as:
where
aij = amount of the ith resource that is consumed for each unit of the
jth activity.
bi = amount of the ith resource that is available. That is, the
resources are limited.
The second general type of constraint specifies that all activities
must have a positive value, xi 0
Constrained Optimization
Linear Programming
Graphical Solution:
• For a two-dimensional problem, the solution space is defined as
a plane with x1 measured along the abscissa and x2 along the
ordinate.
• Because they are linear, the constraints can be plotted on this
plane as straight lines.
• If the LP problem was formulated properly (that is, it has a
solution), these constraint lines will delineate a region, called the
feasible solution space, encompassing all possible combinations
of x1 and x2 that obey the constraints and hence represent
feasible solutions.
Constrained Optimization
Linear Programming
Graphical Solution:
• The objective function or a particular value of Z can then be
plotted as another straight line and superimposed on this space.
• The value of Z can then be adjusted until it is at the maximum
value while still touching the feasible space. This value of Z
represents the optimal solution.
• The corresponding values of x1 and x2, where Z touches the
feasible solution space, represent the optimal values for the
activities.
Constrained Optimization
Linear Programming
Example:
A manufacturing company makes two models A and B of a product.
Each piece of Model A requires 9 labour hours for fabricating and 1
labour hour for finishing. Each piece of Model B requires 12 labour
hours for fabricating and 3 labour hours for finishing. For fabricating
and finishing, the maximum labour hours available are 180 and 30
respectively. The company makes a profit of Rs 8000 on each piece
of model A and Rs 12000 on each piece of Model B. How many
pieces of Model A and Model B should be manufactured per week to
realize a maximum profit? What is the maximum profit per week?
Constrained Optimization
Linear Programming
Example Solution:
Constrained Optimization
Linear Programming
Example Solution:
Constrained Optimization
Linear Programming
Example Solution:
Constrained Optimization
Linear Programming
Example Solution:
Constrained Optimization
Linear Programming
Example Solution:
