Date post: | 01-May-2015 |
Category: |
Documents |
Upload: | norina-bondi |
View: | 225 times |
Download: | 2 times |
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
Data
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)
1
0
1
project3
project2
project1
yes
no
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
0
0
0
project3
project2
project1
no
no
no
Per ogni progetto
Selected (YES = 1)
Not selected (NO = 0)
1
0
1
project3
project2
project1
yes
no
yes
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
1
1
1
,
1
0
1
,
0
1
1
,
1
1
0
,
0
0
1
,
0
1
0
'
1
0
0
'
0
0
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
1
0
1
,
0
1
1
,
1
1
0
,
0
0
1
,
0
1
0
'
1
0
0
'
0
0
0
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
xi=
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
15
Investment for project 2
budget
Investment for project 3
Un modello “migliore”
xi=
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
data
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
Il modello di Capital Budget in Excel
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
Il modello di Capital Budget in Excel
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
7
Integer decision variables c7,d7,e7
Constraint C4*C7+D4*D7+E4*E7
data
Dobbiamo ora definire delle celle nella tabella Excel che consentano di definire il modello matematico
B C D E
2 Capital Budgeting3 progetto 1 progetto 2 progetto 34 investimento 8 6 55 guadagno 12 8 76
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
2 Capital Budgeting3 progetto 1 progetto 2 progetto 34 investimento 8 6 55 guadagno 12 8 76
7 variabili decisione 0 1 08 costo totale 6 15 budget9 funzione obiettivo 8
Funzione obiettivo C5*C7+D5*D7+E5*E
7
B C D E
2 Capital Budgeting3 progetto 1 progetto 2 progetto 34 investimento 8 6 55 guadagno 12 8 76
7 guess 0 1 08 total investment 6 15 budget9 total earning 8
Objective C5*C7+D5*D7+E5*E
7
Integer decision variables c7,d7,e7
data
Solving Capital Budget with Excel
Objective function
Solving Capital Budget with Excel
Variables (b6,c6,d6) are 0-1
Solving Capital Budget with Excel
x1 x2 x3<= 1 x1 x2 x3>= 0 x1 x2 x3 int
italian
english
Solving Capital Budget with Excel
Solving Capital Budget with Excel
Excel: an easy platform to optimizationExcel has an optimization toolbox: Solver
Solver
Add-ins
Tools
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
Solving Capital Budget with Excel
Objective function
Solving Capital Budget with Excel
Variables (b6,c6,d6) are 0-1
Solving Capital Budget with Excel
x1 x2 x3<= 1 x1 x2 x3>= 0 x1 x2 x3 int
italian
english
Solving Capital Budget with Excel
Solving Capital Budget with Excel
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
15000
15000
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
Tools
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
1416
12
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
Tools
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
12
CH
PI
2 4 6 8 10 12 14 16
246810
1416
18
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 ?
CH
12
PI
2 4 6 8 10 12 14 16
246810
1416
18
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
7 spanners pliers8 production 15000 150009 total profit 127500
10 total cost 37500 11 budget 1800012 difference -19500
7 spanners pliers8 production 15000 20009 total profit 69000
10 total cost 18000 11 budget 18000
difference 0
7 spanners pliers8 production 2000 100009 total profit 53000
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
12
CH
PI
2 4 6 8 10 12 14 16
246810
1416
18
1*CH + 1,5* PI = 18
PTOT =
69
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
12
CH
PI
2 4 6 8 10 12 14 16
246810
1416
18
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
0
PTOT =
56
56
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
tools
14
PI
12
2468
10
14CH
2 4 6 8 10 12 16 18
1*CH + 1* PI = 14hours 16
> 14: not feasible
16
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
8 production 2000 120009 total profit 62000
10 total cost Budget working h. Max H.11 20000 18000 14 14
Budget satisfied technological violated
8 production 14000 20009 total profit 65000
10 total cost Budget working h. Max H.11 17000 18000 16 14
Both satisfied
8 production 4000 20009 total profit 25000
10 total cost Budget working h. Max H.11 7000 18000 6 14
Geometric view of both constraints
CH
PI
1412
2468
10
16
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:
CH 0
PI 0 Non negativity
1 CH + 1,5 PI 18
1 CH + 1 PI 14
budget
hours
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
PI
1412
246810
16
142 4 6 8 10 12 16 18
1CH + 1PI = 14
F
Linear Programming
1CH + 1,5 PI 18
1 CH + 1 PI 14
budget
hours
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
PI
CH
1 CH + 1,5 PI = 18
1412
246810
16
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
Graphical solution for LP
PI
1 CH + 1,5 PI = 18
1412
246810
16
142 4 6 8 10 12 16 18
1CH + 1PI = 14
CH
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’
F’
The profit PTOT is now
4CH + 4,5PI = 53 (53000 €)
PTOT = 53
Graphical solution for LP
CH
The feasible region F” is more and more narrow (violet region)
PI
1 CH + 1,5 PI = 18
1412
246810
16
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 =
60
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