INTRODUCTION TO
OPTIMIZATION
► What is optimization?
► Modelling of an Optimization Problem
► Classes of optimization problems
► Optimization Algrithms
Optimization!
Optimization holds an important place in both
practical and theoretical worlds, as understanding
the timing and magnitude of actions to be carried out
helps achieve a goal in the best possible way.
7
What is OPTIMIZATION?
• The word “optimum” is Latin, and meaning “the best or most favorable point.”
• To optimize: to bring whatever we are dealing with towards its ultimate state
• Optimization is the act of obtaining the best result under given circumstances.
• Optimization theory is the branch of mathematics encompassing the quantitative study
of optima and methods for finding them.
8
Where would we use optimization?
► Pack all the items into as few bins as possible:
Bins
Items
9
Where would we use optimization?
► A delivry person has 6 packages to deliver, and wants to take the shortest route:
10
Where would we use optimization?
• Shortest route taken by a salesperson visiting various cities during one tour
• Airline companies schedule crews and aircraft to minimize cost.
• Selection of machining conditions in metal-cutting processes for minimum production cost
• Optimum design of electrical networks
• Controlling the waiting and idle times and queueing in production lines to reduce the costs
• Planning the best strategy to obtain maximum profit in the presence of a competitor
11
Optimization Problems
Optimization problems occur in most disciplines :
► engineering,
► physics,
► mathematics,
► economics,
► administration,
► commerce,
► social sciences,
► politics.
12
Optimization Problems (contd.)
• Optimization problem: Maximizing or minimizing some function relative to
some set, often representing a range of choices available in a certain
situation.
• The function allows comparison of the different choices for determining
which might be “best”
• Common applications: Minimal cost, maximal profit, best approximation,
optimal design, optimal management or control,
13
Modeling of an Optimization Problem
➢ The ultimate goal of all such decisions is either to minimize the effort
required or to maximize the desired benefit.
➢ Optimization can be defined as the process of finding the conditions that
give the maximum or minimum value of a function.
➢ Modeling is the process of identifying and expressing in mathematical
terms the objective, the variables, and the constraints of the problem.
14
Modeling of an Optimization Problem (contd.)
• Objective : a quantitative measure of the performance of the system under study.
✓ This objective could be profit, time, potential energy, or any quantity or
combination of quantities that can be represented by a single number.
• The design variables are the components of the system for which we want to find
values
• The constraints are the functions that describe the relationships among the
variables and that define the allowable values for the variables
15
Classes of Optimization Problems
Optimization problems (OPs) can be classified in several ways:
▫ Existence of constraints: constrained or an unconstrained OPs,
depending upon the presence or not of constraints,
▫ Nature of the equations: linear, quadratic, polynomial, non-linear
OP depending upon the nature of the objective functions and the
constraints,
▫ Nature of the variables: depending upon the values permitted for
the design variables, OPs can be classified as integer or real valued,
and deterministic or stochastic.
16
Classes of Optimization Problems (contd.)
▪ Number of objectives: most optimization problems have a single objective function,
however, there are interesting cases when optimal decisions need to be taken in the
presence of trade-offs between two or more conflicting objectives, we deal with a multi-
objective optimization
▪ Time dependence: some problems are static (do not change over time) while some are
dynamic (continual adjustments must be made as changes occur).
17
Classes of Optimization Problems
Optimization Constrained OP
problems Existence of
classification constraints Unconstrained OP
criterions
Linear
Nature of Non-linear
equations Quadratic
Polynomial
Deterministic
Nature of Stochastic
variables Discrete OP
Continuous OP
Single-objective OP
Number of
objectives Multi-objective OP
Static OP
Time dependency 18
Dynamic OP
► Integer linear programming
Single objective Multi-objective
𝐸𝐷 = 1,1
(x1, x2) = (1, 1)
z(x) = 3 3
𝐸𝑂 =
6
19
19
► Continuous linear programming
Single Multi-objective
objective
(x1, x2) = (20, 0) 𝐸𝐷 = 20, 0 , (0, 14.285)
z(x) = 40
40 14.285
𝐸𝑂 =
20 71.428
20
Solve Optimization Porblems
▪ There are many ways to solve an optimization problem:
► Analytical method
► Graphical method
► Numerical method
21
Solve Optimization Porblems
Analytical methods
▪ Analytical methods are based on the classical techniques of differential calculus,
▪ The maximum or minimum of a performance criterion is determined by finding the values of
parameters x1, x2, . . . , xn that cause the derivatives of f(x1, x2, . . . , xn ) with respect to x1, x2, . . . ,
xn to assume zero values.
▪ Cannot be applied to highly nonlinear problems or to problems where the number of
independent parameters exceeds two or three.
22
Solve Optimization Porblems
Graphical methods
▪ A graphical method can be used to plot the function to be maximized or
minimized if the number of variables does not exceed two,
▪ It provides a visualization of how a solution for an optimization problem is
obtained
23
Solve Optimization Porblems
Numerical methods
▪ In numerical methods, iterative numerical procedures are used to
generate a series of progressively improved solutions to the
optimization problem, starting with an initial estimate for the solution.
▪ The process is terminated when some convergence criterion is
satisfied.
▪ Numerical methods can be used to solve highly complex optimization
problems of the type that cannot be solved analytically
24
Optimization Algorithms
• Optimization algorithms are solution techniques for optimization problems
• An optimization algorithm is a procedure which is executed iteratively by
comparing various solutions till an optimum or a satisfactory solution is found.
25
Optimization Algorithms
Good algorithms should possess the following properties:
► Robustness: to perform well on a wide variety of problems in
their class, for all reasonable choices of the initial variables.
► Efficiency: should not require too much computer time or
storage
► Accuracy: should be able to identify a solution with
precision, without being overly sensitive to errors in the
data
26
Process of Optimization Design
● Is the design optimal?
● Is the design feasible? · Is the design
reasonable?
● What design variables are most
important to the design
performances?
● How would the further improvement
be made by modifying the
optimization model?
27
