Corso RICERCA OPERATIVA USO DI EXCEL PER ANALISI DI SCENARI E OTTIMIZZAZIONE Corso di Laurea in...

transcript

Corso RICERCA OPERATIVACorso RICERCA OPERATIVAUSO DI EXCELUSO DI EXCEL

PER ANALISI DI SCENARI E OTTIMIZZAZIONEPER ANALISI DI SCENARI E OTTIMIZZAZIONE

Corso di Laurea in Ingegneria dei TrasportiCorso di Laurea Magistrale in Ingegneria MeccanicaCorso di Laurea Magistrale in Ingegneria dei Sistemi di Trasporto

Laura PalagiDipartimento di Informatica e Sistemistica “A. Ruberti”

Sapienza Universita` di Roma

Capital Budgeting (Pianificazione degli Investimenti)

Un’azienda deve considerare tre possibili progetti sui cui investire nel corso dell’anno

Definizione del problema

Budget 15 milioni

Ogni progetto richiede un investimento (I)

Iproject 1 8project 2 6project 3 5

Ogni progetto produce un Guadagno (G)

Eproject 1 12project 2 8project 3 7

Consideriamo il problema di Capital Budgeting

Capital budgeting: un possibile scenario

Per ogni progetto

Selezionato (YES = 1)

Non selezionato (NO = 0)

project3

project2

project1

yesInvestimento richiesto =

8 + 0 + 5 = 13

Guadagno ottenuto = 12 + 0 + 7 = 19

E` la migliore possibile ?

Capital budgeting: costruzione del modello

Soluzioni ammissibili

Definiscono le possibili alternative

project3

project2

project1

Per ogni progetto

Selected (YES = 1)

Not selected (NO = 0)

project3

project2

project1

Capital budgeting

Iproject 1 8 0 0 0 1 0 1 1 1project 2 6 0 0 1 0 1 1 0 1project 3 5 0 1 0 0 1 0 1 1total I 0 5 6 8 11 14 13 19

Budget 15 milioni

0Tutte le possibilita`

Non accettabile

Sono tutte compatibili con il budget ?

Un possibile modello di capital budgeting

Eproject 1 12 0 0 0 1 0 1 1project 2 8 0 0 1 0 1 1 0project 3 7 0 1 0 0 1 0 1total E 0 7 8 12 15 20 19

Le scelte ammissibili F=

Miglior valore

Qual e` la migliore rispetto ai guadagni ?

Perche’ e` un modello “sbagliato”

Feasible solutions Rappresentazione esaustiva

2n = numero enorme per valori grandi di n

Non indipendente dai dati

Se i dati cambiano, e` necessario riscrivere ‘ex novo’ tutto il modello

Potrebbe addirittura essere impossibile scriverlo

Un modello “migliore”

Rappresentazione implicita delle soluzioni ammisibili

Indipendente dai dati

1 se il progetto i e` selezionato

0 se il progetto i NON e` selezionato

Variabili di decisione

Vincolo di Budget 8 x1+6 x2+5 x3

Investment for project 1

budget

Un modello “migliore”

1 if project i is selected

0 if project i is not selected

guadagni 12 x1+8 x2+7 x3

earnings for project 1 Earnings for

project 2

Earnings for project 3

Se cambiano i dati, solo I coefficneti dei vncoli e della funzione obiettivo devono essere modificati, ma non le funzioni matematiche, cioe` il modello che rimane lo stesso

Modello matematico di Capital budgeting

Funzione obiettivo

12 x1+8 x2+7 x3maxearnings

Decision variables xi=1 if project i is selected

0 if project i is not selectedi=1,2,3

vincoli8 x1+6 x2+5 x3 15

budget

x1, x2 , x3 1,0

Programmazione lineare intera (PLI)

Il modello di Capital Budget in Excel

B C D E

2 Capital Budgeting3 progetto 1 progetto 2 progetto 34 investimento 8 6 55 guadagno 12 8 76

Possiamo rappresentare i dati del modello in una tabella Excel

Se cambiano i dati, e` necessario modificare solo questa parte della tabella Excel

B C D E

2 Capital Budgeting3 progetto 1 progetto 2 progetto34 investimento 8 6 55 guadagno 12 8 76

7 variabili di dec. 0 1 0

Variabili di decisione (intere) c7,d7,e7

B C D E

2 Capital Budgeting3 project 1 project 2 project 34 investimento 8 6 55 guadagno 12 8 76

7 variabili di dec. 0 1 0

Variabili di decisione (intere) c7,d7,e7

Dobbiamo ora definire nuove celle nella tabella Excel che consentano di definire il modello matematico:

1. Variabili di decisione: dobbiamo assegnare dei valori inziali (stima iniziale) che consentano di valutare le funzioni

B C D E

2 Capital Budgeting3 project 1 project 2 project 34 investement 8 6 55 earning 12 8 76

7 guess 0 1 08 total investment 6 15 budget9 total earning 8

Objective C5*C7+D5*D7+E5*E

Integer decision variables c7,d7,e7

Constraint C4*C7+D4*D7+E4*E7

Dobbiamo ora definire delle celle nella tabella Excel che consentano di definire il modello matematico

B C D E

7 variabili decisione 0 1 08 spesa totale 6 15 budget

r.h.s = budget

Valore l.h.s. del vincolo C4*C7+D4*D7+E4*E7

B C D E

7 variabili decisione 0 1 08 costo totale 6 15 budget9 funzione obiettivo 8

Funzione obiettivo C5*C7+D5*D7+E5*E

B C D E

7 guess 0 1 08 total investment 6 15 budget9 total earning 8

Objective C5*C7+D5*D7+E5*E

Integer decision variables c7,d7,e7

Solving Capital Budget with Excel

Objective function

Variables (b6,c6,d6) are 0-1

x1 x2 x3<= 1 x1 x2 x3>= 0 x1 x2 x3 int

italian

english

Excel: an easy platform to optimizationExcel has an optimization toolbox: Solver

Solver

Add-ins

Solving PL with ExcelIn the main menù select Tools (Strumenti) and then Solver (solutore)

Solving PL with Excel

It will appear a dialog window like below

Objective function

Tipo di problema (max o min)

Decision variables

Constraints

Let now fill in

Setting the objective function

Objective function PTOT = c9

The value can be set easily by clicking the corresponding cell (it puts the address $c$)

Setting the initial guess

We need to give an initial value (also zero is feasible) = guess

Cells C8 and D8 contains the value of the variables. At the end of the optimization process they contain the optimal value

Setting the constraints

Clich Add (Aggiungi)

Window of constraints

Setting the constraints

Italian English

Address of the cell or a constant

Address of the cell

Constraint can be of the type A B

A Int (integer value)

A bin (binary value 0,1)

Setting the options

We must Assume Linear Model (use simplex method) and non-negative variables (in alternative we can define the additional constraints c8, d8 0).

Clicking Options (Opzioni) the window of parameters appears

Setting the options

Maximum time allowed to obtain a solution

Maximum iterations of the algorithm to obtain a solution

It uses an algorithm for linear problems (simplex)

More complex models (non linear)

Solve LP con Excel

We can start optimization

Click the button Solve (Risolvi)

Final result with Excel

Guess initial values have been substituted by the optimal ones

The “algorithmic” solution is the same obtained with the graphical solution

Changing the options for LP

Reducing time

Reducing iterations

Reducing or increasing tolerance

Same solution

Changing the options for LP

Same solution

Change the model

In general this is not true

Objective function

Variables (b6,c6,d6) are 0-1

x1 x2 x3<= 1 x1 x2 x3>= 0 x1 x2 x3 int

italian

english

Changing the options for ILP

Reducing time

Reducing iterations

same solution but the Solver is not able to certify optimality

Changing the options for ILP

Increasing Tolerance

SOLUTION CHANGES

Optimality declared, but it is not true

Production planning

An engineering factory produces two types of tools: pliers and spanners.

Pliers cost to the production 1.5 € eachSpanners cost to the production 1 € each

Pliers are sold at 6 € eachSpanners are sold at 5 € each

How much should the factory produce to maximize its profit ?

Production costs

Selling price

Objective function

A possible scenario

Assume that we are constructing

PTOT= number of pliers * unit profit for pliers +

number of spanners * unit profit for spanners

15000 pliers

15000 spanners

Let us define the data of the problem

4,5 = (6 – 1,5) unit profit for pliers 4 = (5 – 1) unit profit for spanners

unit profit = selling price – unit cost

Objective function = total profit PTOT

A possible scenario (2)

CH = number of spanners to be produced

PI = number of pliers to be produced

PTOT = 4 CH + 4,5 PI = 4 * 15000 + 4,5 * 15000 =

Equation of the overall profit

Formally:

variables

output of our model

Unit profit of spanners

Unit profit of pliers

127500

Is this the best value ?

First use of Excel for data storing

We use an Excel table to summarize data and objective

B C D23 Spanners Pliers4 Selling price 5 65 Cost 1 1,56 Profit 4 4,578 Production 15000 150009 Total profit 127500

PTOT = 4 CH + 4,5 PI

Profit equation

C9 = C6 * C8 + D6 * D8

Excel formula

CH = D8 = number of pliers

PI = C8 = number of spanners

4,5= unit profit pliers = D4 – D5

4 = unit profit spanners = C4-C5

Constraints

Every point in the non negative quadrant is a possible feasible solution (a possible production planning)

2 4 6 8 10 12 14 16

246810

Spanners (thousands)

Pliers (thousands)

In practice: constraints exist that limit the productionIn principle: the more I produce the more I gain !

}0:{ xxF

(25000)

overall profit(68000)

(127500)

A standard constraint: the budget one

Budget constraint: the overall cost must not greater than € 18000

CTOT= overall cost

CH = D8 = number of pliers

PI = C8 = number of spanners

CTOT = 1 CH +1,5 PI

Unit cost spanner

Unit cost pliers

Cost equationC11 = C5 * C8 + D5 * D8

CTOT = 1 CH + 1,5 PI budget =18000 Budget constraint

1 B C D23 spanners pliers4 unit price 5 65 unit cost 1 1,56 unit profit 4 4,578 production 4000 2000910 profit 2500011 overall cost 700012 Budget 1800013 difference 11000

Geometric view of the constraint

Let draw the set F of the feasible solutions

In the plane (PI, CH), first draw the equation of the

Feasible region All non negative points “below” the line

budget constraint

1 CH + 1,5 PI = 18

CTOT = 20000

CTOT = 7000 18000: ammissibile

> 18000: non ammissibile

CTOT = 37500

1*CH + 1,5* PI = 18

2 4 6 8 10 12 14 16

246810

Geometric view of the problem

We need to find the “right” solution among the feasible ones

“right”

It satisfies the budget constraint

It maximizes the profit

Points in the red area satisfies the budget constraint, which is the better one ?

2 4 6 8 10 12 14 16

246810

1*CH + 1,5* PI = 18

Scenarios with Excel

7 spanners pliers8 production 4000 20009 total profit 25000

10 total cost 700011 Budget 18000

difference 11000

Let us see with different scenarios

10 total cost 37500 11 budget 1800012 difference -19500

10 total cost 18000 11 budget 18000

difference 0

10 total cost 17000 11 budget 18000

difference 1000

feasible Not feasible

feasible feasibleBest among the three feasible. Is the optimum ? By chance ?

Limit of the “What If” approach

The scenarios are too many: infinite solutions !

It is not possible to look over all of them !!

We may wonder if may be better when the number of solutions is finite

This is not always true, let see with an example

Construction of a good model:general rules

xi=1 if project i is selected

0 if project i is not selected

Definition of the objectives

12 x1+8 x2+7 x3

Definition of the decision variables

maxearnings

Definition of the constraints

8 x1+6 x2+5 x3 15budget

i=1,2,3

Geometric view of the production problem

The scenarios are too many

2 4 6 8 10 12 14 16

246810

1*CH + 1,5* PI = 18

PTOT =

Actual best value

Draw the line of the profit PTOT

4 CH + 4,5 PI = 69

We must find another method

Depict the feasible region F (red area)

Geometric view of the problem

2 4 6 8 10 12 14 16

246810

1*CH + 1,5* PI = 18

Growing direction

PTOT = 72

Draw the line of the profit PTOT

4 CH + 4,5 PI

For growing values of

PTOT =

PTOT = 18

18PTOT = 0

PTOT =

Optimum !!

Old best value

Another constraint: technology

To produce 1000 pliers or 1000 spanners is required 1 hour of usage of a plant

CH = D8= number of spanners

PI = C8= number of pliers

The plant can work for a maximum of 14 hours per day

HTOT = total hours nedeed

HTOT = 0.001 CH + 0.001 PI

Equation of the total hoursC11 = C7 * C8 + D7 * D8

Technological constraintHTOT = 0.001 CH + 0.001 PI max_hours=14

B C D E23 spanner pliers4 unit price 5 65 unit cost 1 1,56 unit profit 4 4,57 unit hour 0,001 0,0018 total amount 4000 20009 toal profit 25000

10 total cost 7000 18000 budgettotal hours 6 14 max hours

2 4 6 8 10 12 16 18

1*CH + 1* PI = 14hours 16

> 14: not feasible

Geometric view of the technological constraint

0.001 CH + 0.001 PI 14 1 CH + 1 PI 14000

In the plane (PI, CH), first draw the equation of the technological constraint

Feasible region of the technological constraint

14: feasible

hours 6

Mixing the two constraints

We must put together budget and technological constraints.

Both must be satisfiedSpanner Plier

Both violated

8 production 15000 150009 total profit 127500

10 total cost Budget working h. Max H.11 37500 18000 30 14

budget violated technological satisfied

Budget satisfied technological violated

Both satisfied

Geometric view of both constraints

142 4 6 8 10 12 16 18

1*CH + 1* PI = 14

1*CH + 1,5* PI = 18

Hours: feasible Budget: not feasible

Hours: not feasible Budget: feasible

Feasible set F

Hours: not feasible Budget: not feasible

Hours: feasible Budget: feasible

Not feasible points

Final feasible region

Feasible solutions (CH,PI) satisfy:

PI 0 Non negativity

1 CH + 1,5 PI 18

1 CH + 1 PI 14

budget

Which is the best value for (CH,PI)* among the feasible ones ?

The best one (CH,PI)* maximizes the profit

4 CH + 4,5 PI

1CH + 1,5PI = 18CH

246810

142 4 6 8 10 12 16 18

1CH + 1PI = 14

Linear Programming

1CH + 1,5 PI 18

1 CH + 1 PI 14

budget

CH 0 PI 0 Non negativity

LINEAR PROGRAMMING (LP)

Max or Min of one linear objective function

Constraints are linear equalities (=) or inequalities ( = )

max 4CH + 4,5PI

CH, PIR

Objective function profit

constraints

CH,PI Real decision variables CH, PIR

Construction of a good model:general rules

Definition of the objectives

Definition of the decision variables

4 x1+4,5 x2max profit

Definition of the constraints

x1+ 1,5 x2 18 budget

CH, PIR x1 , x2 R

x1+ x2 14 hours

x1 , x2 0

The name is not important

Graphical solution for LP

1 CH + 1,5 PI = 18

246810

142 4 6 8 10 12 16 18

1CH + 1PI = 14

Let choice a feasible point

The profit PTOT is

4CH + 4,5PI = 34 (34000 €)

Better solution must have a value of PTOT 34

The idea is looking for solutions that satisfy also the “new fictitious” constrait 4CH + 4,5PI 34.

Production 4000 4000Profit 34000

total cost Budget total hours Max hours10000 18000 8 14

(4,4) (4000 spanners e 4000 pliers)

PTOT = 34

1 CH + 1,5 PI = 18

246810

142 4 6 8 10 12 16 18

1CH + 1PI = 14

4 CH + 4,5 PI = 34

Draw the new feasible region F’

Let choice (2,10).

Production 2000 10000profit 53000

total cost Budget hours Max Hours17000 18000 12 14

with Excel

A better solution (if any) must be in the new feasible region F’

The profit PTOT is now

4CH + 4,5PI = 53 (53000 €)

PTOT = 53

The feasible region F” is more and more narrow (violet region)

1 CH + 1,5 PI = 18

246810

142 4 6 8 10 12 16 18

1CH + 1PI = 144 CH + 4,5 PI = 53

Increasing values of PTOT

The region with the constraint PTOT > 60 is empty !!!

Behind this point (6,8) with PTOT = 60, there are non more feasible better points

PTOT =

The point (6,8) is the best feasible one

Graphical solution of LP: summary

1. Draw the constraints and the feasible region

2. Choice a feasible point

3. Draw the line of the objective function passing for this point

4. Parallel move the line of the objective function in the direction of better values

5. The last feasible point “touched” by the line is the optimal solution

When the number of variables is two:

Solution of LP

We use Excel Solver (www.frontsys.com)

http://www.frontsys.com/

Graphical solution can be applied only when the number of variables is two

Real problems has usually more than two variables

Many standard software exist to solve LP problems of different level of complexity

Computer must be used as a tool to tackle large quantities of data and arithmetic

Corso RICERCA OPERATIVA USO DI EXCEL PER ANALISI DI SCENARI E OTTIMIZZAZIONE Corso di Laurea in...

Documents