Post on 17-Feb-2019
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
ProgrammazioneQuadratica
1
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionelineare
minimizzaomassimizza
soggettoa
funzioneobiettivo
2
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionequadratica
minimizeormaximize
soggettoa
STESSIVINC
OLIDELL’L
Pfunzioneobiettivo
3
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Funzioneobiettivo
Sihannodeiterminiquadratici:
Solitamente,perprogrammazionequadratica(QP)siintendequellaconvessa,ovveroquellapercui
perogni[x1...xn]≠[0...0]
4
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionequadratica
Insiemeammissibile
5
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionequadratica
AnchelaprogrammazionequadraticaèmoltodiffusanelleapplicazionievaririsolutoriQPsonodisponibiliinmoltipacchettisoftwareperl’ottimizzazione
Xpress‐MP,Cplex,Matlab,OOQP,LOQO,NAG,...
Applicazioni:
•Economia(es:selezionediportafogliotitoli)•Ingegneria(es:automazionediprocesso)•...
H.D.MittelmannandP.Spellucci,“DecisionTreeforOptimizationSoftware”,WorldWideWeb,http://plato.asu.edu/guide.html
6
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
MatlabOptimizationToolboxQP
EsistonorisolutoriQPmoltopiùefficienti!
7
E[P ] =N!
i=1
Cxi(1 + p̄i)
P =N!
i=1
Cxi(1 + pi)
p̄i = E[pi]
N!
i=1
xi = 1
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Sceltaportafogliotitoli(MeanVariancePortfolioSelection)
8
xi=frazionediportafogliodainvestirenell’i‐esimotitolo
pi=ritornodiinvestimentodell’i‐esimotitolo(stocastico)
Valoredelportafogliodopoilperiododiinvestimento:
C=capitaletotaleinvestito
Valoreattesodelportafogliodopoilperiododiinvestimento:
E[(P ! E[P ])2] = E[(CN!
i=1
xi(pi ! p̄i))2] = C2n!
i,j=1
!ijxixj = C2x!!x
E[(p! p̄)!(p! p̄)] = ! =
!
"""#
!11 !12 . . . !1N
!12 !22 . . . !2N...
.... . .
...!1N !2N . . . !NN
$
%%%&
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Sceltaportafogliotitoli
9
Matricedicovarianzadelritornodiinvestimento:
Varianzadelritornodiinvestimentocomplessivo:
Obiettivo:minimizzareilrischiodiinvestimento,cioèlavarianzadelritornodiinvestimento
min x!!x
s.t.N!
i=1
p̄ixi ! Pmin
N!
i=1
xi = 1
xi ! 0
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Modellomatematico
(modellodiMarkowitz)
(HarryMaxMarkowitz1927‐)
10
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionelinearemista‐intera(MILP)
11
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionelineare
minimizzaomassimizza
soggettoa
(funzioneobiettivo)
12
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionelineare
Imodellidiprogrammazionelinearesuppongonochelevariabilidiottimizzazionepossanoassumerequalsiasivalorereale
Purtroppoquestaassunzionenonsempreèrealistica.
Esempio: Costruisci11.7scacchiereUtilizza3.6operaiInstalla5.75impiantidiproduzione
xi 2 R
13
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Variabilireali
Levariabilipossonoassumerequalsiasivalorereale.Taleipotesièaccettabileinmolticasi.
Proprietàprincipale:lacontinuità
xmin xmax
xlavariabilexpuòassumereunqualsiasivaloreall’internodell’intervallo
Vantaggiodiquestaipotesi:semplicitàcomputazionale
14
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Variabiliintere
Possonoassumerevalorisolosuuninsiemediscreto.
Levariabiliintererisultanoutiliinmoltissimeapplicazioni
xmin xmax
xlavariabilexpuòassumeresoloalcunivalori
15
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Modellidiprogrammazioneintera
Sonomodelliutilizzatiquando:
1‐Sihannoadisposizionesolouninsiemefinitodiscelte
2‐Sihannovincoliditipologico
Ilmodellorisultanteèidenticoadunprogrammalineare,mahaunvincoloaggiuntivo:levariabilipossonoassumeresoltantovaloriinteri
vincolonaturale
vincolodecisionale
16
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionelinearemistaintera(mixedintegerlinearprogramming,MILP)
NIvariabiliintere
minimizzaomassimizza
soggettoa
(funzioneobiettivo)
17
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
ModellisticaMILP
Oltreallevariabilirealicontinue,sihannoadisposizionenuovitipidivariabili:
Sipossonomodellareunagammamoltoestesadinuovivincoli!Inparticolare:
vincolilogici
interebinariesemicontinueSOS(specialorderedsets)...
18
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Variabiliintere
Levariabiliinterepossonoassumerevalorisoltantonell’insiemedeinumerinaturaliN ={0,1,2,...}
Èunvincolomoltocomuneedeltuttonaturale.
Esempi:
NumerodipersoneassegnateadunprogettoNumerodiimpiantidiproduzioneimpiegatiNumerodilottiprodotti...
x2N
19
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Variabilibinarie
Possonoassumeresoltantoduevalori:0o1
Èilminimolivellodiinformazionecheunavariabilepuòdescrivere:
SI/NO
Sonounostrumentodimodellisticamoltopotente,essendoingradodiesprimeredecisioni,scelte,condizionilogiche,...
VERO/FALSO
20
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Variabilisemicontinue
Unavariabilesemicontinuaoènulla,oppureassumeunvaloremaggiorediunacertaquantitàxmin
xmin
xl’insiemedeivaloripossibilièdiscontinuo
0
Permettonodiesprimeredellesituazionirealimoltofrequenti.Esempi:
Sevendo,devovenderealmenounacertaquantitàLivellidiproduzioneminimapergarantireunprofitto
21
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Altritipidivariabile
Esistonoaltritipidivariabilenonreale.Adesempio:
Riconoscerleèimportanteperfacilitarelarisoluzionedelproblemadiottimizzazione.
Dalpuntodivistadellasolamodellistica,possiamofocalizzarel’attenzionesoltantosullevariabilicontinueeintere.
SpecialOrderedSetsSOS1eSOS2
22
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
ModellisticaMILP
Lacomplessitàdellarisoluzionediunproblemadiprogrammazionemistainteralineare(MILP)dipendeinlargamisuradalnumerodivariabiliinterecoinvolte.
Utilizzarelevariabiliintereconparsimonia!
Quandomodelliamodobbiamopertanto:
Dobbiamoquindiindividuarequalivariabilisononecessariamentedamodellarecomeintere,edeventualmentesepossiamoridurneilnumero.
23
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Vincolilogici
Levariabilibinariepermettonodiprenderedelledecisioniditipo:
•Fare/nonfareunaqualcheoperazione
•Sceglierefrapiùopzioni
•Implicazioni
•Vincoliditipo“oquestooquello”
Arricchisconomoltissimoillinguaggiomodellistico!
24
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Fare/nonfare
Sonoivincolilogicipiùcomuni...
Vengonomodellatisemplicementedaunavariabilebinariab 2 {0,1}:fareseb=0,nonfareseb=1
Esempio:
Possiamoaffittaretreaulediverseperfarelezione,A,BeC.L’aulaAha15postiecosta300€,l’aulaBha20ecosta380€,l’aulaCha25postiecosta470€.Ogniannodobbiamodeciderequaliauleaffittare.
Posti=15*prendiA+20*prendiB+25*prendiCCosto=300*prendiA+380*prendiB+470*prendiC
prendiA,prendiB,prendiC2 {0,1}
25
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Vincolidiscelta
Esprimonolasceltafraunnumerofinitodipossibilità.
scegli1+scegli2+scegli3·1
esprimeilfattochepossiamosceglierealpiùunafraleopzioni1,2,3.Infatti:
scegli1 0 1 0 1 0 1 0 1scegli2 0 0 1 1 0 0 1 1scegli3 0 0 0 0 1 1 1 1
ok ok ok no ok no no no
26
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Vincolidiscelta
Altretipologiediscelta:
=sceglinealpiù2fra3scegli1+scegli2+scegli3·2
=sceglinealpiùmfraN
=sceglineesattamentemfraN
Vincolodi“oresclusivo”
scegli1+scegli2+scegli3=1=devosceglierenecessariamenteunaeunasolaopzione
27
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Implicazioni
Comemodellarerelazionicheintercorronofrasceltediverse?
PossiamoordinareiPCodallaIBM,odallaDELLodallaASUS,eimonitorodallaPHILIPS,odallaSONYodallaNEC.SecompriamoiPCdallaIBM,alloradobbiamocomprareimonitordallaSONY
equivalealvincolologico[pcIBM=1]![monitorSONY=1]
Esempio:
pcIBM+pcDELL+pcASUS=1
monitorPHILIPS+monitorSONY+monitorNEC=1
pcIBM·monitorSONY
28
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Implicazionibase
SivedechenonèpossibileordinareiPCdallaIBMenonordinareimonitordallaSONY
pcIBM 0 1 0 1monitorSONY 0 0 1 1
ok no ok okpcIBM·monitorSONY
[pcIBM=1]![monitorSONY=1]
29
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Altreimplicazioni
Rendonolamodellisticamoltoversatile!
“SefacciamoilprogettoA,alloradobbiamofareancheiprogettiBeC”
“SefacciamoilprogettoA,alloradobbiamofareilprogettoBmanonilprogettoC”
“SefacciamoiprogettiBeC,alloradobbiamofareancheilprogettoA”
b¸ ac¸a
b¸a1‐c¸a
a¸b+c‐1
a,b,c2{0,1}
30
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Condizionilogiche
Notal’equivalenzacomediseguaglianzalinearediunarelazionelogica,èimmediatosostituire“A”con“nonA”semplicementesostituendoAcon(1‐A)
Perverificarechelatraduzioneindiseguaglianzaècorretta,èsufficientescriverelatabelladiveritàecontrollaretuttiicasi.
“SenonfacciamoilprogettoA,alloradobbiamofareilprogettoBmanonilprogettoC”
b¸a1‐c¸a
b¸1‐a1‐c¸1‐a
31
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Condizionilogiche
a+b+c+d·1a+b+c+d=2b¸aa+b·1a+b¸1a=bb¸aandc¸ab+c¸aa¸banda¸ca¸b+c‐11‐b
AlpiùunafraA,B,C,DEsattamenteduefraA,B,C,DSeAalloraBSeAalloranonBSenonAalloraBAseesoloseBSeAalloraBeCSeAalloraBoppureCSeBoppureCalloraASeBeCalloraANonB
Alcunecondizioniricorrenti:
a,b,c,d2 {0,1}
32
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Linearizzazionedifunzioniobiettivo
33
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
FunzioniobiettivoMinMax
VogliamocomprarealcuneazioniditipoTecnologico,Costruzioni,TrasportieModa.Vogliamominimizzareilrischiomassimosulbreve,medioelungotermine
Esempio:acquistodiazioni
breve medio lungo
Tecnologico 3.3 2 1
Costruzioni 2.1 1.2 3
Trasporti 2 2.2 2
Moda 1.5 2 3
misuredirischio
34
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
FunzioniobiettivoMinMaxAbbiamotrefunzionidirischio!
“minimizzareilrischiomassimo”
35
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
FunzioniobiettivoMinMax
Comerendereilproblemalineare?
s ¸max{Breve,Medio,Lungo}
srappresentaunupper‐bounddelmassimofraBreve,MedioeLungo
s=max{Breve,Medio,Lungo}
Èfaciledimostrare(perassurdo)cheall’ottimosiha:
36
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Funzioniobiettivorazionali
Abbiamogiàvistovincolisullaqualitàedimiscela‐zione,chesonovincolisulrapportodivariabili
Vediamoadessocometrattarerapportidivariabilinellafunzioneobiettivo
Esempio:vincolosullaqualità
Supponendo,èpossibileriscrivereilvincolo
comevincololineare:
37
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Funzioniobiettivorazionali
“LadittaMetalliS.p.A.haricevutounordinedi500tonnellatediacciaiodausareperlacostruzionediunanave.L’acciaiodeveaveredeterminatecaratteristichedicomposizione.
Ladittadisponedisettetipidiversidimaterialegrezzodautilizzareperlaproduzionediquestoacciaio.L’obiettivoèdeterminarelacomposizionecheminimizzalapercentualedizolfo,soddisfacendoivincolisullecaratteristichedicomposizione.”
Esempio:
38
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Datiadisposizione
Mat.grezzo C% Cu% Mn% Tons S%
Iron1 2.5 0 1.3 400 0.5
Iron2 3 0 0.8 300 0.76
Iron3 0 0.3 0 600 0.3
Copper1 0 90 0 500 1.2
Copper2 0 96 1.2 200 1.1
Aluminium1 0 0.4 1.2 300 0.3
Aluminium2 0 0.6 0 250 0.45
Composizioni%,quantitàdisponibili,%dizolfo
39
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Funzioneobiettivorazionale
sogg.a:
rappresentanoivincolioriginalidelproblema
funzionenon‐linearedellevariabili!
40
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Cambiodivariabili
1) abbiamoaggiuntounanuovavariabile:d
2) abbiamoabbandonatolevecchievariabiliusej
persostituirleconlenuovevariabilixj
41
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Cambiodivariabili
Considerandolavariabiledcomelibera,otteniamounvincololinearesullevariabilixj:
nuovovincololinearedaaggiungerealproblema
Moltiplicandoivincolioriginaliadestraeasinistraperlaquantitàd(d>0),otteniamodeivincoliequivalentiinx,d:
42
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Cambiodivariabili
Funzioneobiettivo:
ProgrammaLineare
Tuttiivincoli(=quellioriginali+ilnuovovincolo)possonoessereespressicomeuninsiemedidisuguaglianzelinearisullevariabilixj,d.
43
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Costifissi
K
C
Costo
Èuntipomoltocomunedifunzionedicosto,utileognivoltachesiabbiauncostobasesoloperilfattodiutilizzareunacertarisorsa
x
K>0
44
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
CostifissiIntroduciamounavariabilebinaria:
sex¸0allorab=1sex=0allorab=0
Verifichiamo:
1) sex>0alloranonpuòcheessereb=1
2) sex =0,allorabèlibera.Quandoperòminimizzia‐moilcosto,essendoK >0,all’ottimoavremob=0
Condizioni:
45
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Costivariabili1(economiesofscale)
Considerailseguenteesempio:iprezzidellegnosonofissaticomesegue:
0‐100kg 0.99€/kg100‐200kg 0.95€/kg200‐400kg 0.90€/kg+400kg 0.80€/kg
scaladeiprezzi
Comeesprimerelafunzionedicosto?
Nota:nonvengonoeffettuatiscontiinblocco!Iprimi100kgsonosemprepagati99€,indipendentementedalfattochesenecomprinoquantitàmaggiori
46
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Costivariabili1
100 200 400
Costo
C1
C2
C3C4
Occorreintrodurredellevariabilicontinuex1,x2,x3,x4ebinarieb1,b2,b3,b4
x
x =x1+x2+x3+x4
xi =quantitàacquistataalprezzoCi
b1 =1b1 =0
b2 =1b2 =0
b3 =1b3 =0
b4 =1b4 =0
47
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Costivariabili1
48
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Costivariabili1
[1000][1100][1110][1111]
x1=100,x2=100,x3minoredi200
Esempio:
49
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Costiconvessilineariatratti
CostoC1
C2C3
C4
x
Icostilineariatrattieconvessipossonoessererappresentatisenzaintrodurrevariabilibinarie!
50
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Costiconvessilineariatratti
C(x)
x
Èfacileosservareche:
(ingenerale:ognifunzionelineareatratticonvessapuòessererappresentatacomemaxdifunzioniaffini,eviceversa)
51
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
CosticonvessilineariatrattiC(x)
x
Lavariabilesrappresentaunupper‐bounddelmassimo
Comeperlefunzioniobiettivominmax,èfaciledimostrare(perassurdo)cheall’ottimosiha:
s
Riformulazionecomeprogrammalineare:
52
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Costivariabili2
Considerailseguenteesempio:iprezzidellegnosonofissaticomesegue:
0‐100kg 0.99€/kg100‐200kg 0.95€/kg200‐400kg 0.90€/kg+400kg 0.80€/kg
scaladeiprezzi
Comeesprimerelafunzionedicosto?
Nota:vengonoeffettuatiscontiinblocco!Maggioreèlaquantitàacquistata,minoreèilcostoperkg
53
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Costivariabili2
100 200 400
Costo
C1
C2
C3C4
x
x =x1+x2+x3+x4
xi =quantitàacquistataalprezzoCi
b1 =1b1 =0
b2 =1b2 =0
b3 =1b3 =0
b4 =1b4 =0
54
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Costivariabili2
Definiamolevariabilibexesattamentecomeprima:
eriscriviamoilcostocome:
55
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Ilvincolob1¸b2¸b3¸b4imponecheleunichecombi‐nazionipossibilisiano
Costivariabili2
OK,mailcostononèlineare!
[1000],[1100],[1110],[1111]
) unosoltantodeiquattroterminisarànonnullo
Abbiamoilprodottofravariabilicontinueebinarie
56
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Prodottovariabilicontinue‐binarie
Tecnicadel“big‐M”:
puòesseremodellatocome
sottol’ipotesicheMsiasceltosufficientementegrande,inmodochesiasemprex· M
x¸0z¸0
b2{0,1}
57
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Prodottovariabilicontinue‐binarie
b=0 b=1
x¸0z¸0
b2{0,1}
z=0 z=x
58
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Vincolidicardinalità(counting)
Èunvincolo(moltoricorrente)chelimitailnumerodisceltediscretechepossiamodecidere.
Associamoadogniopzionei,i=1,2,...,N,unavariabilebinariabi,bi2{0,1}
PossiamosceglierealpiùMopzioni
DobbiamoscegliereesattamenteMopzioni
DobbiamosceglierealmenoMopzioni
59
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Vincolidi“or”logicoAnchequestisonovincolimoltoricorrenti.Hannobisognodivariabilibinarieperesseremodellati.
Siamointeressatiadinvestiredeldenaroperscopipubblicitari,alfinediottenereunbuonimpattocommercialeinTVoinradio...
Bastachesiasoddisfattoalmenounodeiduevincoli
Esempio:
60
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Vincolidi“or”logico
Impattominimo=1.5
TV Radio Costo
Mediaset 0.5 0.3 250
RAI 0.4 0.35 200
RadioCapital
0.0 0.5 50
MTV 0.3 0.2 100
61
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Vincolidi“or”logico
Vincolisullevariabilibuy(i):
62
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Vincolidi“or”logico
Sealmenounodeiduevincolièsoddisfatto,alloraesisteunvaloredellavariabilebinariabammissibile.Viceversa,seentrambeivincolinonpossonoesseresoddisfatti,nonesistonovaloriammissibiliperb.
Regioneammissibile(nonconvessa)
buy(1)
buy(2)
63
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionestocastica
64
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Incertezzadeidatidelproblema
•Finoraabbiamoipotizzatocheidatidelproblemadiottimizzazione(es.A,b,cdiunproblemaLP)fosseronoticonprecisione
•Spessoperòinpraticasihannomoltesituazioniincuitalidatinonsonodeterministici,mapiuttostostocastici,cioèdescrittidafunzionidiprobabilità
•Questoaccadeadesempioquandoidatidelproblemasarannonotisoltantonelfuturo(es:domandadiuncliente,prezzodelmateriale,ecc.)
65
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionestocastica(2stadi)
•Nellamodellazionea2stadi,lasequenzadelledecisionipuòessererappresentatacomesegue:
stadio
eventorandom
decisioni
1 2!
inizialexricorsioney
•!=variabilerandom
•x=variabiledidecisionepresaprimachel’evento!sisiamanifestato
•y=variabiledidecisionepresadopochel’evento! sisaràmanifestato,equindidaessodipendente.Permettedieffettuarehedging.
66
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionestocastica(2stadi)
Esempio:Significatodellevariabiliinproblemigerarchicidipianificazione(hierarchicalplanningproblems)
•Stadio1(variabilex):decisionistrategicheeglobali,conimpattoalungotermine.
Esempi:investimenti,capacitàproduttive,ecc.Inquestocasoladomandadelclientepuòesseretrattatacomeincerta.
•Stadio2(variabiley):variabilioperative,decisioniabrevetermineinrispostaacomelevariabilistocastiche!sisonorealizzate(adesempioladomandadelcliente).
Esempi:quantitatividiproduzione,schedulazionedellemacchine,ecc.
67
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionestocastica(2stadi)
•Considerailseguenteproblemadiprogrammazionelinearestocasticaadue‐stadiconricorsione
•!=variabilerandom
•x=variabiledidecisionepresaprimachel’evento!sisiamanifestato
•y=variabiledidecisionepresadopochel’evento! sisaràmanifestato,equindidaessodipendente
Nota:
68
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionestocastica(2stadi)
•Supponiamocheilvettore!possaassumeresolounnumerofinitodivaloripossibili(detti“scenari”)
•Sianolerispettiveprobabilità(seequiprobabilipi=1/S)
•Allora,possiamoriscrivere
Lastrutturaparticolare(esparsa)delproblemapuòesseresfruttatadairisolutori
matricedeivincoli termininoti
costox y1y2...yS
equindiilproblemadiottimizzazionestocasticacome
69
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Esempio
•Unmunicipalizzatadevegestiregliacquistidigasperl’annoincorsoeilprossimo.
•Ilgaspuòesserecomprato,vendutoeimmagazzinato
•Asecondadellecondizioniclimatiche,iprezzidiacquistoperquantitativodigaseladomandacambiano:
Clima Probabilitàp Costogasc Domandad
Normale 1/3 5 100
Freddo 1/3 7 120
Moltofreddo 1/3 9 130
•Supponiamochenell’annoincorsocisiaunclima“normale”,mentreilclimadell’annoprossimoèincerto
•Quantogasdobbiamocomprarequest’anno?Quantodobbiamocomprarneperimmagazzinarlo?Quantodovremocomprarnel’annoprossimo?
http://stoprog.org/spintroduction.html
70
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Esempio
•Èunproblemadiprogrammazionelinearestocasticaaduestadi
•Variabili:
‐!=variabilerandom“clima”(3possibilivalori)
‐x=variabiledidecisionepresaprimachel’evento! sisiamanifestato x1=acquistodigasdarivenderesubito(anno1)
x2=acquistodigasdaimmagazzinare(anno1)
‐y=variabiledidecisionepresadopochel’evento! sisaràmanifestato
y1j =utilizzodigasimmagazzinato(anno2)
y2j =acquistodiulterioregasdarivenderesubito(anno2)j=1,2,3
71
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Esempio
•Funzionecosto:
•Vincoli:
‐Soddisfacimentodomanda:
‐Disponibilitàdigasimmagazzinato:
‐Ilgassipuòsolocomprareoprelevaredallostoccaggio:
72
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Esempio
•Risultato:costo=1236.67,x1=100,x2=100y11=100,y21=0,y12=100,y22=20,y13=100,y23=30
•Confermacheilcostomedioè(1100+1240+1370)/3=1236.67
•Calcoliamoilcostoperognirealizzazionediscenario:
Clima Azionestage2 Costototale
Normale nessunacquistoaggiuntivo 1100
Freddo compra20unitàalcostodi7perunità 1240
Moltofreddo compra30unitàalcostodi9perunità 1370
73
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Esempio
•Soluzioneeuristica:rimpiazzareicoefficienticonirispettivivaloriattesi:
•Risultato:x1=100,x2=116.67,y1=116.67,y2=0.Lasoluzioneperònonèammissibilenelcaso“freddo”e“moltofreddo”.Inognicasoconvienericalcolarey2dopochel’eventostocasticosièpalesato
Clima Azionestage2 Costototale
Normale nessuna(eccessodi16.67inmagazzino) 1200
Freddo compra3.33unitàalcostodi7perunità 1223.33
Moltofreddo compra13.33unitàalcostodi9perunità 1320
•Ilcostomedioè1247.78
74
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Esempio
•Soluzioneeuristica:ottimizzareogniscenario,poiprenderecomevariabilidecisionalilamediadegliottimizzatori:
Clima Azionestage2 Costototale
Normale compra16.67unitàalcostodi5perunità 1083.33
Freddo compra36.67unitàa7perunità 1256.67
Moltofreddo compra46.67unitàa9perunità 1420
•Ilcostomedioè1253.33
•Risultato:x1=100,x2=83.33,y1=83.33,y2=33.33.Lasoluzioneperònonèammissibilenelcaso“moltofreddo”.Inognicasoconvienericalcolarey2dopochel’eventostocasticosièpalesato
75
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionestocastica(multi‐stadio)
•Nellamodellazionemulti‐stadioconricorsione,lasequenzadelledecisionipuòessererappresentatacomesegue:
stadio
eventorandom
decisioni
1 2
!2
N‐1 N
x1x2x3xN‐1xN
!3 !N
•Inquestocasosisupponecheipossibilivaloriassumibilida!sianoorganizzatisecondoun“albero”
•Gliscenarisonodatidatuttiipercorsipossibilisull’albero,adesempio[!22,!33]conprobabilitàp=p22p33.
1,1
2,1
2,2
2,3
3,1
3,2
3,3
3,4
!21,p21
!22,p22
!23,p23
!31,p31
!32,p32
!33,p33
!34,p34
76
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Programmazionestocastica(multi‐stadio)
•Adogninododell’alberovieneassegnataunavariabiledidecisionexijcherappresentaladecisionechesarebbepresasecivenissimoatrovarenelnodo(i,j)dell’alberodegliscenari
x11
x21
x22
x23
x31
x32
x33
x34
•Conquestocostruttovieneimpostounvincolodicausalità(onon‐anticipatività)delledecisioni:lasceltaxijpresaallostadioi,nonconoscendoancoraqualesaràlarealizzazionefuturadell’eventorandom,èindipendendentedaqualepercorsoverràseguitoneglistadisuccessivii+1,...,N.
• x11rappresentaladecisionepresaprimachel’eventorandomsiiniziamanifestare
77
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Linguaggidimodellisticaperprogrammazionestocastica
•MOSEL+Xpress‐SP,commerciale
•SMI(StochasticModelingInterface),open‐source
•Lamaggiorpartedeilinguaggidimodellisticamenzionatiinprecedenza(AMPL,GAMS,ecc.)supportaestensioniperlarappresentazionediproblemidiottimizzazionestocastica
•SMPS(StochasticMathematicalProgrammingSystem),èunaversionediMPSperrappresentareproblemidiottimizzazionestocastica
[1]J.R.BirgeandF.Louveaux,“IntroductiontoStochasticProgramming”,SpringerVerlag,1997
Bibliografia:
78
©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09
Fine
79