Optimisation and its applications An overview

Optimisation is the act of obtaining the best result under given circumstances. In the design , construction and maintenance of any engineering system, engineers have to take many technological and managerial decisions at several stages. The goal of such decisions is either to minimise the effort required or to maximise the desired benefit.

Optimisation can be defined as the process of finding the conditions that give the maximum value or minimum value of a function. A number of optimisation methods have been developed for solving different types of optimsation problems

Historical Development The existence of optimsation methods can be traced to the days of Newton, Lagrange, Cauchy, Leibnitz, Bernoulii, Euler etc., Very little progress was made until the middle of the twentieth century. Then High speed digital computers made implementation of optimisation procedures possible.

Historical Developments (contd.,)

Von Neumann gave the foundations for game theory in the year 1928 Development of Simplex method by Dantzig in 1947 Kuhn and Tucker conditions for NLP in 1951 Bellmanns principle of optimality in 1957

Developments in Numerical methods of unconstrained optimisation have been made in the UK in the 1960s.

Historical Developments (contd.,) Duffin, Zener and Peterson developed Geometric Programming during1960s. Gomory gave his cutting plane method for Integer programming. Goal programming was proposed by Charnes and Cooper in 1961. Simulated annealing, genetic algorithms and neural network methods came during the last decade.

Engineering applications of optimisation

Some typical applications from different engineering disciplines are given below: 1. Design of aircraft and aerospace structures for minimum weight 2. Finding the optimal trajectories of space vehicles Design of civil engineering structures such as frames, foundations, bridges, towers, chimneys

3.

Engineering applications of optimisation (contd.,)

4. Minimum-weight design of structures earthquake, wind, and other types of random loading for

5. Design of water resources systems for maximum benefit 6. Optimal design of structures

7. Optimum design of linkages, cams, gears, machine tools and other mechanical components

Engineering applications of optimisation (contd.,)

8. Selection of machining conditions in metal-cutting processes for minimum production cost 9. Design of material handling equipment such as conveyors, trucks, cranes for minimum cost 10. Design of pumps, turbines and heat transfer equipment for maximum efficiency

11. Optimum design of electrical machinery such as motors, generators, and transformers 12. Optimum design of electrical networks

Engineering applications of optimisation (contd.,)

13. Shortest route taken by a salesperson visiting various cities during one tour 14. Optimal production planning, controlling and scheduling 15. Optimum equipment and plants design of chemical processing

16. Design of optimum pipeline networks for process industries

Engineering applications of optimisation (contd.,)

17. Selection of a site for industry

18. Planning of maintenance and replacement of equipment to reduce operating costs 19. Inventory control

20. Allocation of resources or services among several activities to maximise the benefit

Engineering applications of optimisation (contd.,)

21. Controlling the waiting and idle times and queuing in production lines to reduce costs 22. Planning the best strategy to obtain maximum profit in the presence of a competitor 23. Optimum design of control systems

Methods of Optimisation Techniques

Mathematical Programming Techniques
Calculus methods Calculus of variations

Stochastic Techniques
Markov Processes

Process Statistical Methods

Regression Analysis Cluster Analysis, recognition pattern

Statistical Decision Theory

Nonlinear Programming
Geometric Programming Linear Programming Dynamic Programming

Queuing Theory
Renewal Theory Simulation methods Reliability Theory

Design of Experiments

Integer Programming
Stochastic Programming Separable Programming Multi objective Programming

Network methods: CPM and PERT

Game Theory Simulated Annealing Genetic Algorithms

Classification of optimisation problems

(i) Based on the existence of constraints:

Constrained optimisation problem and unconstrained optimisation problem

(ii) Based on the nature of design variables: Parameter or static optimisation problem and trajectory or dynamic optimisation problem

(iii) Based on physical structure of the problem:

Optimal control problem and nonoptimal control problem

Classification of Optimisation problems (contd.,) (iv) Based on the nature of equations involved:
Linear Programming
Nonlinear Programming

Geometric programming
Quadratic programming

(v) Based on the permissible values of the design variables:

Integer programming

Real value programming

Classification of Optimisation problems (contd.,)

(vi) Based on the deterministic nature of the variables: Stochastic programming (vii) Based on the separability of the objective functions and constraint functions: Separable programming (viii) Based on the number of objective functions to be optimised: Single objective programming Multi objective programming

Classical optimisation Techniques

To find the optimum solution of continuous and differential functions. These methods make use of the techniques of differential calculus in locating optimum points. ( maxima and minima) These methods have limited scope in practical applications because practical problems involve objective functions which are not continuous and/or differentiable.

Linear Programming
This is applicable for the problems in which the objective function and the constraints are linear functions of the key variables. Applications: Product mix problem Optimal production planning in a manufacturing firm Make or buy decisions in metal working industries Minimising trim loss in paper mill Optimal routing of messages in communication network Routing of aircraft and ship Transportation problem and assignment problem

Methods to solve LP models

Graphical Method Simplex method - with slack variables only - Big M Method - Two Phase Method Dual Simplex method Revised simplex method Decomposition principle Karmarkars method (50 times faster than simplex)

Sensitivity

Analysis/Post

optimal

analysis

To know the sensitivity of the optimality of a LP model with respect to the changes made in the parameters and characteristics of a LP model
(i) (ii) (iii) (iv) Making changes in the RHS constants of the constraints Making changes in the objective function coefficients Adding a new constraint Adding a new variable -Also the resources used in the model may be classified as abundant and scarce and unit worth of a resource may also be calculated.

Parametric Linear Programming

To find out the range for objective function coefficients so that the optimality remains unaffected. To find out the range for right hand side constants of constraints so that the optimality remains unaffected.

Nonlinear Programming
- It is an extension of linear programming. - The objective function may be nonlinear and the constraints may be linear or nonlinear.

Lagrangean method
Lagrangean method is used to solve a NLP where the objective function is nonlinear and the constraint is in linear equation form.

Kuhn-Tucker conditions
KT conditions are used to solve a NLP where the Objective function is in nonlinear form and constraint is in nonlinear inequality form.

Quadratic Programming
Quadratic Programming is a NLP problem in which the highest order of the polynomial of the objective function is restricted to 2.

Such quadratic programming problems are solved using Wolfes method. The QPP is converted into a LPP and solved using suitable simplex method.

Separable Programming
Separable programming problem is a NLP where the objective function consists of linear and nonlinear term as well as the constraint will also consist of linear and nonlinear term. In such problems the nonlinear terms are converted into equivalent sum of linear terms using piece wise linearisation and the problem becomes a LPP and it is solved using simplex with restricted basis method.

Stochastic programming or Chance-constrained programming

Such problems deal with situations where some or all of the parameters of the optimisation problem are described by stochastic (random or probabilistic) variables. The stochastic model is converted into an equivalent deterministic model and solved.

Integer Programming
Integer Linear programming is a LPP where the optimal solution for the key variables are to be obtained in terms of integers. Methods used: Gomoris cutting plane method Branch and Bound method

Dynamic programming
-Also known multistage programming -Bellmanns optimality condition is used. Terms used in DP: Stage State Variable Recursive function (Forward/Backward) More amount of computations to be made

Applications of Dynamic Programming

Capital Budgeting problem Reliability improvement problem Shortest route problem Inventory control/production control Linear programming Design of a gear train Minimum cost pipe network

Goal Programming or Multiobjective programming

-It is an extension of Linear programming. -Suitably formulated into a LPP and solved. Three types: (i) Single goal programming (ii) Multi goal programming with equal priorities (iii) Multi goal programming with different priorities

Network Techniques
(i) CPM and PERT Project networks (i) Shortest path model

(i) Minimum spanning tree problem Kruskals Algorithm

(iv) Maximal Flow Problem - MFP Algorithm

Sequencing
Optimal sequence of a few jobs to be processed under a few machines so that elapsed time and the idle times are minimised. Types: N Jobs x 2 machines N jobs x 3 machines N Jobs x m machines m jobs x 2 machines

Game Theory
-Two person Zero sum game -Maxi-min and Mini-max criteria -Pure strategy and Mixed strategy -Value of the game and the optimal strategies are found out. Types: (i) Games with saddle point (ii) Method of sub games (iii) Graphical method (iv) Matrix method

Queuing Models
Characteristics of a queuing model Arrival pattern Service pattern No. of service channel Service order No. of customers served Population

Applications of queuing models

- Queuing model with customers will be studied. -Customers dont refer only to persons. -Customers may also be machines to be repaired/programs waiting to be executed by computers/jobs waiting to be processed etc. - Idle time or the waiting time of the customers and the service personnel will be identified

Monte Carlo simulation

-Used for queuing models with random distribution. -Random numbers are generated. -Using random numbers, frequency distribution of arrival and service the queue will be simulated. -Idle time of the customers and the service counter will be identified to take further decision.

Design of Experiments or Experimental Design

Terms: Factors Levels Replication Interaction Response Treatment condition Degrees of freedom

DOE is used for parameter optimisation of a process or a product

The significant factors can be identified. The levels of the factors may be fixed to have an optimum response value. It is known as parameter design

It is also known as Design for Robustness

DOE for friction welding

The reduction of RPN with respect to low tensile strength and weld crack can be achieved by optimising the process parameters. In order to optimise the process parameters, Design of Experiments (DOE) was used as explained below. Upset force, friction force, burn off and spindle speed are the major causes of weld crack and low tensile strength. These parameters were optimised using 2 level DOE involving multiple factors. The experimental factors of the DOE are upset force, friction force, burn off length and spindle speed.

Factors and levels of DOE

Upset force Factors /Levels (Tons)

Friction force (Tons)

Burn off (mm)

Spindle speed (rpm)

1
2

0.712
1.03

0.3516
0.415

4
4.5

2100
2300

Initial RPN

Sl.No.
1

Failure Mode
Low Tensile strength

RPN
160

Weld crack

120

Due to the FMEA that was carried out for friction welding in the manufacture of engine valves, the RPN for the different failure modes were reduced and are shown below. RPN Values

Sl.N Failure Mode o. 1 Low Tensile strength 2 Weld crack

Initial RPN 160 120

Improved RPN 32 40

One factor at a time DOE

Full factorial DOE Taguchis DOE

Steps in Taguchis DOE

- Decide on the number of factors and levels - Consider interaction if any - Find out the degrees of freedom based on factors, levels and interaction. - Choose the proper Orthogonal Array which should be greater than or equal to the degrees of freedom.

Conclusion
- The optimisation techniques available are plenty. - A given problem must be properly understood to identify the function to be optimised, key variables to be optimised, constraints if any and accordingly the problem has to be formulated. - A suitable optimisation technique/model must be selected accordingly to derive the maximum benefit from these available techniques.

Thank you