Optimisation Models PDF

Siamak Naderi Optimisation Models Lecturer – Siamak Naderi [email protected] WBS 0.207 – https://my.wbs.ac.uk/-/academic/346556/home/ 3 Linear Programming and Optimisation What is optimisation? Optimisation is f...

Siamak Naderi Optimisation Models Lecturer – Siamak Naderi [email protected] WBS 0.207 – https://my.wbs.ac.uk/-/academic/346556/home/ 3 Linear Programming and Optimisation What is optimisation? Optimisation is finding the best solution. Find the fastest route 4 Linear Programming and Optimisation What is optimisation? Optimisation is finding the best solution. In industry, - Maximise profits - Minimise costs - Design the best product to maximise sales, etc. 5 Linear Programming and Optimisation Linear Programming is a tool for modelling and solving optimisation problems. It is used in many types of organisations to solve a wide variety of problems. Linear Real World Programming Problem Model - Finance, - Marketing, “ In a survey of Fortune 500 firms, 85% of - Transportation, - Manufacturing, those responding said that they use LP.” - Health-Care… (Winston& Albright, 2012) 6 Some Typical Linear Programming Applications Production Planning Develop a production plan which – satisfies specified sales demand, – satisfies limitations on production capacity, – maximises total production profit. Some Typical Linear Programming Applications Logistics Determine a distribution system which – meets customer demand, – minimises transportation costs. https://scoopnets.com/businesses/what-how-of-supply-chain-management/627/ Some Typical Linear Programming Applications Financial Planning Establish an investment portfolio which – meets the total investment amount, – meets any restrictions of investing in the available alternatives, – maximises return on investment. Some Typical Linear Programming Applications Marketing Determine the media mix (TV, radio, social media, newspapers advs) which: – meets a fixed budget, – maximises advertisement effectiveness. https://smartcomm.net.au/multi-channel-marketing/ Typical Linear Programming Applications What do these applications have in common? – All are concerned with maximising or minimising some quantity, called the objective of the problem. – Search for the best strategy – All have constraints which limit the degree to which the objective function can be pursued. Linear Programming (LP) Three parts of LP models – Seek to optimise an objective function (e.g., maximise returns, minimise costs) – By modifying a set of decision variables (e.g., product mix, delivery quantity) The values of these variables determine the value of the objective function such as total cost and revenue. – Subject to a set of constraints (labour, funds, materials, time) Formulation of LP Models Problem formulation is the process of translating the verbal statement of a problem into a mathematical statement.  Define decision variables  Decision variables should describe the decisions to be made. e.g., number of products produced each week.  In order to formulate mathematical equality and inequalities, we define decision variables usually expressed in terms of x and y (or 𝑥1 and 𝑥2 ). 13 Linear Programming (LP) All mathematical functions in LP model should be linear functions. Objective function must be linear. Constraints must be linear equalities or inequalities. – “≤ ” or “≥ ” or “=” 14 Linear Programming (LP) Concepts of linear function and linear inequality: Linear Function: A function f(x1, x2, …, xn) of x1, x2, …, xn is a linear function if and only if for some set of constants, c 1, c2, …, cn, f(x1, x2, …, xn) = c1x1 + c2x2 + … + cnxn. For example, f(x1,x2) = 2x1 - x2 is a linear function of x1 and x2, but f(x1,x2) = x1x2 is not a linear function of x1 and x2. LP Example : Marketing Problem  ABS company is planning a radio and TV advertising campaign. They want to maximise the overall rating.  Each radio advert provides 200 rating and each TV advert provides 600 rating.  Costs: Each radio advert costs £200. Each TV advert costs £800.  Restrictions:  There should be at least 60 adverts.  No more than 50 radio adverts.  There should be at least as many radio as TV adverts.  The total budget is £34,000 16 LP Example : Marketing Problem Determine the Decision Variables These are the variables over which the decision makers have control, and for which the optimum values need to be found. R: Number of radio adverts; T: Number of TV adverts Determine the Constraints Restrictions on the values of decision variables. Need to be expressed as mathematical formulae, with: – the decision variables on the left hand side – a value on the right hand side 17 LP Example : Marketing Problem Constraints: There are 4 constraints for this problem.  There should be at least 60 adverts 𝑅 + 𝑇 ≥ 60  No more than 50 radio adverts 𝑅 ≤ 50  At least as many radio as TV adverts 𝑅≥𝑇 𝑅−𝑇 ≥0 18 LP Example: Marketing Problem Constraints: There are 4 constraints for this problem.  Budget £34,000: Cost of a radio advert: £200 Cost of a TV advert: £800 200𝑅 + 800𝑇 ≤ 34000  We must also specify that R and T cannot be negative (non-negativity constraints): 𝑅, 𝑇 ≥ 0 19 LP Example: Marketing Problem Determine the Objective Function ABS company wants to maximise the overall rating. Ratings: Radio advert: 200 TV advert: 600 Objective Function: 𝑚𝑎𝑥𝑖𝑚𝑖𝑠𝑒 200𝑅 + 600𝑇 20 Marketing Problem: LP Model maximise 200 R + 600 T Decision variables: R: number of radio adverts subject to: R + T ≥ 60 T: number of TV adverts R ≤ 50 R – T ≥0 200 R + 800 T ≤ 34,000 R, T ≥ 0 LP requires that…  Objective function is linear.  Constraints are linear.  Decision variables are continuous. In Linear Programming, we also assume that problem parameters (such as demand) are known with certainty.