Programmazione Quadraticacse.lab.imtlucca.it/~bemporad/teaching/cpsp/slides/2009/modellisti... ·...

©2009byA.Bemporad /82ControllodiProcessoedeiSistemidiProduzione‐A.a.2008/09

ProgrammazioneQuadratica

1


Programmazionelineare

minimizzaomassimizza

soggettoa

funzioneobiettivo

2


Programmazionequadratica

minimizeormaximize

soggettoa

STESSIVINC

OLIDELL’L

Pfunzioneobiettivo

3


Funzioneobiettivo

Sihannodeiterminiquadratici:

Solitamente,perprogrammazionequadratica(QP)siintendequellaconvessa,ovveroquellapercui

perogni[x1...xn]≠[0...0]

4



Insiemeammissibile

5



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


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


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

$

%%%&


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


Modellomatematico

(modellodiMarkowitz)

(HarryMaxMarkowitz1927‐)

10


Programmazionelinearemista‐intera(MILP)

11




soggettoa

(funzioneobiettivo)

12



Imodellidiprogrammazionelinearesuppongonochelevariabilidiottimizzazionepossanoassumerequalsiasivalorereale

Purtroppoquestaassunzionenonsempreèrealistica.

Esempio: Costruisci11.7scacchiereUtilizza3.6operaiInstalla5.75impiantidiproduzione

xi 2 R

13


Variabilireali

Levariabilipossonoassumerequalsiasivalorereale.Taleipotesièaccettabileinmolticasi.

Proprietàprincipale:lacontinuità

xmin xmax

xlavariabilexpuòassumereunqualsiasivaloreall’internodell’intervallo

Vantaggiodiquestaipotesi:semplicitàcomputazionale

14


Variabiliintere

Possonoassumerevalorisolosuuninsiemediscreto.

Levariabiliintererisultanoutiliinmoltissimeapplicazioni

xmin xmax

xlavariabilexpuòassumeresoloalcunivalori

15


Modellidiprogrammazioneintera

Sonomodelliutilizzatiquando:

1‐Sihannoadisposizionesolouninsiemefinitodiscelte

2‐Sihannovincoliditipologico

Ilmodellorisultanteèidenticoadunprogrammalineare,mahaunvincoloaggiuntivo:levariabilipossonoassumeresoltantovaloriinteri

vincolonaturale

vincolodecisionale

16


Programmazionelinearemistaintera(mixedintegerlinearprogramming,MILP)

NIvariabiliintere


soggettoa

(funzioneobiettivo)

17


ModellisticaMILP

Oltreallevariabilirealicontinue,sihannoadisposizionenuovitipidivariabili:

Sipossonomodellareunagammamoltoestesadinuovivincoli!Inparticolare:

vincolilogici

interebinariesemicontinueSOS(specialorderedsets)...

18


Variabiliintere

Levariabiliinterepossonoassumerevalorisoltantonell’insiemedeinumerinaturaliN ={0,1,2,...}

Èunvincolomoltocomuneedeltuttonaturale.

Esempi:

NumerodipersoneassegnateadunprogettoNumerodiimpiantidiproduzioneimpiegatiNumerodilottiprodotti...

x2N

19


Variabilibinarie

Possonoassumeresoltantoduevalori:0o1

Èilminimolivellodiinformazionecheunavariabilepuòdescrivere:

SI/NO

Sonounostrumentodimodellisticamoltopotente,essendoingradodiesprimeredecisioni,scelte,condizionilogiche,...

VERO/FALSO

20


Variabilisemicontinue

Unavariabilesemicontinuaoènulla,oppureassumeunvaloremaggiorediunacertaquantitàxmin

xmin

xl’insiemedeivaloripossibilièdiscontinuo

0

Permettonodiesprimeredellesituazionirealimoltofrequenti.Esempi:

Sevendo,devovenderealmenounacertaquantitàLivellidiproduzioneminimapergarantireunprofitto

21


Altritipidivariabile

Esistonoaltritipidivariabilenonreale.Adesempio:

Riconoscerleèimportanteperfacilitarelarisoluzionedelproblemadiottimizzazione.

Dalpuntodivistadellasolamodellistica,possiamofocalizzarel’attenzionesoltantosullevariabilicontinueeintere.

SpecialOrderedSetsSOS1eSOS2

22


ModellisticaMILP

Lacomplessitàdellarisoluzionediunproblemadiprogrammazionemistainteralineare(MILP)dipendeinlargamisuradalnumerodivariabiliinterecoinvolte.

Utilizzarelevariabiliintereconparsimonia!

Quandomodelliamodobbiamopertanto:

Dobbiamoquindiindividuarequalivariabilisononecessariamentedamodellarecomeintere,edeventualmentesepossiamoridurneilnumero.

23


Vincolilogici

Levariabilibinariepermettonodiprenderedelledecisioniditipo:

•Fare/nonfareunaqualcheoperazione

•Sceglierefrapiùopzioni

•Implicazioni

•Vincoliditipo“oquestooquello”

Arricchisconomoltissimoillinguaggiomodellistico!

24


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


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


Vincolidiscelta

Altretipologiediscelta:

=sceglinealpiù2fra3scegli1+scegli2+scegli3·2

=sceglinealpiùmfraN

=sceglineesattamentemfraN

Vincolodi“oresclusivo”

scegli1+scegli2+scegli3=1=devosceglierenecessariamenteunaeunasolaopzione

27


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


Implicazionibase

SivedechenonèpossibileordinareiPCdallaIBMenonordinareimonitordallaSONY

pcIBM 0 1 0 1monitorSONY 0 0 1 1

ok no ok okpcIBM·monitorSONY

[pcIBM=1]![monitorSONY=1]

29


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


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


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


Linearizzazionedifunzioniobiettivo

33


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


FunzioniobiettivoMinMaxAbbiamotrefunzionidirischio!

“minimizzareilrischiomassimo”

35


FunzioniobiettivoMinMax

Comerendereilproblemalineare?

s ¸max{Breve,Medio,Lungo}

srappresentaunupper‐bounddelmassimofraBreve,MedioeLungo

s=max{Breve,Medio,Lungo}

Èfaciledimostrare(perassurdo)cheall’ottimosiha:

36


Funzioniobiettivorazionali

Abbiamogiàvistovincolisullaqualitàedimiscela‐zione,chesonovincolisulrapportodivariabili

Vediamoadessocometrattarerapportidivariabilinellafunzioneobiettivo

Esempio:vincolosullaqualità

Supponendo,èpossibileriscrivereilvincolo

comevincololineare:

37


Funzioniobiettivorazionali

“LadittaMetalliS.p.A.haricevutounordinedi500tonnellatediacciaiodausareperlacostruzionediunanave.L’acciaiodeveaveredeterminatecaratteristichedicomposizione.

Ladittadisponedisettetipidiversidimaterialegrezzodautilizzareperlaproduzionediquestoacciaio.L’obiettivoèdeterminarelacomposizionecheminimizzalapercentualedizolfo,soddisfacendoivincolisullecaratteristichedicomposizione.”

Esempio:

38


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


Funzioneobiettivorazionale

sogg.a:

rappresentanoivincolioriginalidelproblema

funzionenon‐linearedellevariabili!

40


Cambiodivariabili

1) abbiamoaggiuntounanuovavariabile:d

2) abbiamoabbandonatolevecchievariabiliusej

persostituirleconlenuovevariabilixj

41


Cambiodivariabili

Considerandolavariabiledcomelibera,otteniamounvincololinearesullevariabilixj:

nuovovincololinearedaaggiungerealproblema

Moltiplicandoivincolioriginaliadestraeasinistraperlaquantitàd(d>0),otteniamodeivincoliequivalentiinx,d:

42


Cambiodivariabili

Funzioneobiettivo:

ProgrammaLineare

Tuttiivincoli(=quellioriginali+ilnuovovincolo)possonoessereespressicomeuninsiemedidisuguaglianzelinearisullevariabilixj,d.

43


Costifissi

K

C

Costo

Èuntipomoltocomunedifunzionedicosto,utileognivoltachesiabbiauncostobasesoloperilfattodiutilizzareunacertarisorsa

x

K>0

44


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


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


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


Costivariabili1

48


Costivariabili1

[1000][1100][1110][1111]

x1=100,x2=100,x3minoredi200

Esempio:

49


Costiconvessilineariatratti

CostoC1

C2C3

C4

x

Icostilineariatrattieconvessipossonoessererappresentatisenzaintrodurrevariabilibinarie!

50


Costiconvessilineariatratti

C(x)

x

Èfacileosservareche:

(ingenerale:ognifunzionelineareatratticonvessapuòessererappresentatacomemaxdifunzioniaffini,eviceversa)

51


CosticonvessilineariatrattiC(x)

x

Lavariabilesrappresentaunupper‐bounddelmassimo

Comeperlefunzioniobiettivominmax,èfaciledimostrare(perassurdo)cheall’ottimosiha:

s

Riformulazionecomeprogrammalineare:

52


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


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


Costivariabili2

Definiamolevariabilibexesattamentecomeprima:

eriscriviamoilcostocome:

55


Ilvincolob1¸b2¸b3¸b4imponecheleunichecombi‐nazionipossibilisiano

Costivariabili2

OK,mailcostononèlineare!

[1000],[1100],[1110],[1111]

) unosoltantodeiquattroterminisarànonnullo

Abbiamoilprodottofravariabilicontinueebinarie

56


Prodottovariabilicontinue‐binarie

Tecnicadel“big‐M”:

puòesseremodellatocome

sottol’ipotesicheMsiasceltosufficientementegrande,inmodochesiasemprex· M

x¸0z¸0

b2{0,1}

57


Prodottovariabilicontinue‐binarie

b=0 b=1

x¸0z¸0

b2{0,1}

z=0 z=x

58


Vincolidicardinalità(counting)

Èunvincolo(moltoricorrente)chelimitailnumerodisceltediscretechepossiamodecidere.

Associamoadogniopzionei,i=1,2,...,N,unavariabilebinariabi,bi2{0,1}

PossiamosceglierealpiùMopzioni

DobbiamoscegliereesattamenteMopzioni

DobbiamosceglierealmenoMopzioni

59


Vincolidi“or”logicoAnchequestisonovincolimoltoricorrenti.Hannobisognodivariabilibinarieperesseremodellati.

Siamointeressatiadinvestiredeldenaroperscopipubblicitari,alfinediottenereunbuonimpattocommercialeinTVoinradio...

Bastachesiasoddisfattoalmenounodeiduevincoli

Esempio:

60


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



Vincolisullevariabilibuy(i):

62



Sealmenounodeiduevincolièsoddisfatto,alloraesisteunvaloredellavariabilebinariabammissibile.Viceversa,seentrambeivincolinonpossonoesseresoddisfatti,nonesistonovaloriammissibiliperb.

Regioneammissibile(nonconvessa)

buy(1)

buy(2)

63


Programmazionestocastica

64


Incertezzadeidatidelproblema

•Finoraabbiamoipotizzatocheidatidelproblemadiottimizzazione(es.A,b,cdiunproblemaLP)fosseronoticonprecisione

•Spessoperòinpraticasihannomoltesituazioniincuitalidatinonsonodeterministici,mapiuttostostocastici,cioèdescrittidafunzionidiprobabilità

•Questoaccadeadesempioquandoidatidelproblemasarannonotisoltantonelfuturo(es:domandadiuncliente,prezzodelmateriale,ecc.)

65


Programmazionestocastica(2stadi)

•Nellamodellazionea2stadi,lasequenzadelledecisionipuòessererappresentatacomesegue:

stadio

eventorandom

decisioni

1 2!

inizialexricorsioney

•!=variabilerandom

•x=variabiledidecisionepresaprimachel’evento!sisiamanifestato

•y=variabiledidecisionepresadopochel’evento! sisaràmanifestato,equindidaessodipendente.Permettedieffettuarehedging.

66



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



•Considerailseguenteproblemadiprogrammazionelinearestocasticaadue‐stadiconricorsione

•!=variabilerandom

•x=variabiledidecisionepresaprimachel’evento!sisiamanifestato

•y=variabiledidecisionepresadopochel’evento! sisaràmanifestato,equindidaessodipendente

Nota:

68



•Supponiamocheilvettore!possaassumeresolounnumerofinitodivaloripossibili(detti“scenari”)

•Sianolerispettiveprobabilità(seequiprobabilipi=1/S)

•Allora,possiamoriscrivere

Lastrutturaparticolare(esparsa)delproblemapuòesseresfruttatadairisolutori

matricedeivincoli termininoti

costox y1y2...yS

equindiilproblemadiottimizzazionestocasticacome

69


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


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


Esempio

•Funzionecosto:

•Vincoli:

‐Soddisfacimentodomanda:

‐Disponibilitàdigasimmagazzinato:

‐Ilgassipuòsolocomprareoprelevaredallostoccaggio:

72


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


Esempio

•Soluzioneeuristica:rimpiazzareicoefficienticonirispettivivaloriattesi:

•Risultato:x1=100,x2=116.67,y1=116.67,y2=0.Lasoluzioneperònonèammissibilenelcaso“freddo”e“moltofreddo”.Inognicasoconvienericalcolarey2dopochel’eventostocasticosièpalesato


Normale nessuna(eccessodi16.67inmagazzino) 1200

Freddo compra3.33unitàalcostodi7perunità 1223.33

Moltofreddo compra13.33unitàalcostodi9perunità 1320

•Ilcostomedioè1247.78

74


Esempio

•Soluzioneeuristica:ottimizzareogniscenario,poiprenderecomevariabilidecisionalilamediadegliottimizzatori:


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


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


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


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


Fine

79

Programmazione Quadraticacse.lab.imtlucca.it/~bemporad/teaching/cpsp/slides/2009/modellisti... ·...

Documents

Transcript of Programmazione Quadraticacse.lab.imtlucca.it/~bemporad/teaching/cpsp/slides/2009/modellisti... ·...