programación dinamica--

8/17/2019 Programación Dinamica--

1/31

IO2 Rosa Delgadillo

Programación Dinámica

Conceptos y formulación


2/31

IO2- RosaDelgadillo

Programación DinámicaConceptosMotivaciónFormalización del Modelo deProgramación Dinámica

strategia de solución!emplos


3/31

IO2- RosaDelgadillo

Programación Dinámica"ran cantidad de situaciones #ue sedesea modelar presentan naturalezadinámica

sto es$ las decisiones de un periodode tiempo se ven afectadas por las

decisiones de los periodos anterioresy las decisiones del periodo actualafectarán el comportamiento futuro%


4/31

IO2- RosaDelgadillo

Programación DinámicaDos enfo#ues #ue dependen de losre#uerimientos y a&stracción #uese realice en el modelamientopueden ser contemplados'

(sumir #ue el efecto dinámico espoco relevante y solo considerarmodelos de un periodoConsiderar el efecto dinámico dentrodel modelo


5/31

IO2- RosaDelgadillo

Programación Dinámica)a programación dinámica tam&i*nse conoce como programación enm+ltiples etapas%,e &asa en el uso de funcionesrecursivas y en un principio deoptimalidad desarrollado por R%-ellman #ue es una aplicación delprincipio de inducción%


6/31

IO2- RosaDelgadillo

Programación Dinámica)a programación dinámica .donde eltiempo da el carácter dinámico/ es un

caso particular de la programaciónrecursiva%l modelo recursivo presenta una forma

alternativa e#uivalente de escri&ir lamayor0a de los modelos de programaciónmatemática$ proporcionando unmecanismo de solución%


7/31

IO2- RosaDelgadillo

Motivación!emplo'Considere una familia #ue está plani1cando sus vacaciones ydesea via!ar a trav*s del Per+% Para ello a elegido n ciudadespara visitar en un cierto orden% l n+mero de d0as dedicados avisitar cada ciudad de&e ser determinado en la plani1cación% )afamilia dispone de m d0as para sus vacaciones% De acuerdo alinter*s tur0stico y las preferencias familiares$ a cada ciudad se le

a asignado una función de utilidad #ue representa elgrado de satisfacción de la familia asociado a la visita de laciudad i cuando se dedican d0as asignados a esa ciudad$ elcual de&e ser entero%

,e asume #ue'l tiempo de via!e entre ciudades es desprecia&le

)os d0as son dedicados completamente a una ciudadl orden de las ciudades #ue se visitarán corresponde al

0ndice asignado

)( ii x g

i x


8/31

IO2- RosaDelgadillo

MotivaciónModelo de programación matemática' es el n+mero de d0as a dedicar a la visita de la

ciudad iM 'Má3imo n+mero de d0as disponi&les de vacaciones

' 4tilidad perci&ida si d0as son dedicados a la visitade la ciudad in ' 5+mero de ciudades a visitar

)( ii x g

i x

i x

ni x

M x

a s

x g Max

i

n

ii

n

iii

,...,1 entero, ,0

..

)( (P1)

1

1

=≥

≤∑

∑

=

=


9/31

IO2- RosaDelgadillo

MotivaciónModelo de programación Dinámicas necesario o&servar #ue el n+mero de d0as dedicados a

visitar una ciudad afectará al n+mero de d0as posi&les #ue sededicarán a la visita de otras ciudades .caracter0sticadinámica/,upongamos #ue la familia llega a la +ltima ciudad #ue #uer0avisitar .ciudad n / y #ue dispone de d0as de vacaciones

6Cuál es la me!or decisión #ue ellos pueden tomar en esemomento7 sto es 6 cuántos d0as le dedicarán a la +ltimaciudad7%

,i se asume #ue es una función creciente en entoncesla decisión será dedicar d0as disponi&les a la +ltima ciudad%4na función #ue representa la utilidad de la me!or alternativaen la ciudad n es dado por'

i y

)( nn x g n xn y

{ })()(0

nn y x

nn x g y f Maxnn ≤≤

=


10/31

IO2- RosaDelgadillo

MotivaciónPero$ #ue ocurre en la ciudad n 897,upongamos #ue e3isten d0as disponi&les antes de

visitar la ciudad n89 . y la ciudad n /% n este momento lafamilia de&e decidir cuantos d0as dedicar a la ciudad n89y a la ciudad n.

Por tanto si ay d0as disponi&le para am&as ciudades$#uedarán si se decide dedicar d0as a laciudad n 89

la función #ue representa la utilidad de la me!or

alternativa escogida para la ciudad n 89 . y la ciudad n /es'

1−n x11 −− − nn x y

{ })()()( 11110

1111

−−−−

≤≤

−− −+=

−−

nnnnn y x

nn x y f x g y f Maxnn

1−n y

1−n y


11/31

IO2- RosaDelgadillo

Motivacióny$ #ue ocurre en la ciudad i 75uevamente supongamos #ue e3isten d0as disponi&les

antes de visitar la ciudad i . y las ciudades i :9$ ;$ n) $estos d0as de&en ser distri&uidos entre esas ciudades deforma a ma3imizar la utilidad asociada a esas ciudades%

)a función #ue representa la utilidad de la me!oralternativa escogida para la ciudad i . y las ciudades i :9$ ;$ n / es'

{ })()()( 10

iiiii

y x

ii x y f x g y f Maxii

−+=+

≤≤

i y


12/31

IO2- RosaDelgadillo

MotivaciónFinalmente$ en todas las ciudades se supone #ue e3isten


13/31

IO2- RosaDelgadillo

Formalización del modelo deProgramación Dinámica

n el e!emplo anterior se o&servó #ue el a&orda!e de laformulación de los su&pro&lemas relacionados partieron desdela +ltima ciudad a la primera ciudad$ este forma es conocidacomo formulación hacia atrás o backward % ,in em&argo esposi&le acer una formulación hacia delante o forward.

l concepto de programación dinámica se &asa en el uso deecuaciones funcionales y el principio de Optimalidad deBellman)as ecuaciones funcionales corresponden a '

Funciones #ue dan cuenta de la función o&!etivo .desde la etapa >asta el 1n del orizonte/

)a función de interrelación entre estados de dos etapasconsecutivas)as condiciones de &orde


14/31

IO2- RosaDelgadillo


Modelo general de la formulación backward:

Donde ' ?aria&le de decisión de la etapa >8esima' ?aria&le de estado al comienzo de la etapa >8esima

' Función de transformación ' Función de Optimización ' Función de recursión en etapa >8esima ' spacio de soluciones facti&les de la etapa >8esima M ' ?alor inicial de Y $ o condición de &orde F ' ?alor 1nal de la función f

k y

{ }

F y f

M y

nnk x yT

y f x y H y f

nn

k k k

k k k k k y A x

k k Maxk k k

=

=

−==

=

++

+

++

∈

)(

1,....,1, ),(y

))(,,()(

11

1

1k

11)(

k x

k T k H

k f

)( k k y A


15/31

IO2- RosaDelgadillo

Formalización del modelo de

Programación Dinámica)a formulación anterior presenta algunas

caracter0sticas importantes')a formulación tiene el concepto derecursividad$ #ue es la generalización delconcepto dinámico del modelo)as condiciones de &orde M y F permiten o&tener la solución e3plicita delmodelo)a función corresponde a la funcióno&!etivo desde la etapa k asta la etapa1nal n

k H


16/31

IO2- RosaDelgadillo

Formalización del modelo de

Programación Dinámica)a función de transformaciónesta&lece la relación entre las varia&les

de estado y para dos periodosconsecutivos%l con!unto representa al con!unto de

restricciones asociadas a la varia&le dedecisión de la etapa >%

),( k k k x yT

1−k yk y

k A


17/31

IO2- RosaDelgadillo


)a solución del su&pro&lema deoptimización en la etapa k $ es una

solución param*trica en la varia&le deestado $ ya #ue f es función de ella%,e denomina pol0tica óptima de la etapa! a la solución óptima de las etapas k $k :9$;$ n para un determinado estadoinicial en la etapa k

k y


18/31

IO2- RosaDelgadillo

Formalización del modelode Programación Dinámica

Principio de optimalidad de -ellman'"na solución óptima tiene la propiedad #uecual#uiera sea el estado inicial y la decisióninicial las decisiones para las etapas posterioresdeben constituir una pol$tica óptima con respectoal estado resultante de la primera decisión.

s decir' las decisiones involucradas desde unaetapa en adelante sólo dependen del estadoinicial de la etapa y no de la decisiones previas%


19/31

IO2- RosaDelgadillo


n general es posi&le esta&lecerciertas reglas para construir unmodelo de programación dinámicae#uivalente al modelo deoptimización P9@ asociado a las

de1niciones de etapas$ estado$función de transformación yfunción de recursión'


20/31

IO2- RosaDelgadillo


Cada varia&le de decisión .o con!unto de ellas/de1ne una etapa del modelo de PD%"eneralmente se esta&lece una relación uno a

uno entre las varia&les y las etapas%)a función o&!etivo corresponde a la función derecursión% Por tanto$ para cada etapa la funciónde recursión de&e corresponder a la funcióno&!etivo desde esa etapa asta la etapa 1nal%

l n+mero de varia&les de estado del modelocorresponde al n+mero de restricciones #ueinvolucran a varia&les en más de una etapa%)as restricciones #ue solo afectan a una etapano generan varia&les de estado%


21/31

IO2- RosaDelgadillo


)as varia&les de estado tienen unainterpretación asociada al valor disponi&lesdel lado derec o ce cada restricción en unaetapa determinada . olgura residual/%

l valor de la condición de &orde esasignado de acuerdo a la forma de la funcióno&!etivo y a la decisión tomada al 1nal de la+ltima etapa . si la F%O% es aditiva y

si es multiplicativa/%

1+n f

01 =+n f 11 =+n f


22/31

IO2- RosaDelgadillo

strategia de solución

!emplo'Para el e!emplo anterior considere tres

ciudades y el n+mero de d0asdisponi&les para vacaciones de A% lasfunciones de utilidad son $

$

Considere #ue el orden de vista de lasciudades está prede1nido .9$ 2$ y luegoB/ %

2/111 2)( x x g =

2/122 )( x x g =

2/133 3)( x x g =


23/31

IO2- RosaDelgadillo

strategia de solucióntapaB

)os d0as #ue se pueden dedicar a la

ciudad B son $9$2$B$ y A%,i la familia dispone de d0as$entonces puede dedicar desde a

a esta ciudad%

l su&pro&lema #ue de&e serresuelto entonces es'

3 y3 y

{ })(3)( 3342/130

3333

x y f x y f Max y x

−+=

≤≤


24/31

IO2- RosaDelgadillo

strategia de solución)a función $ ya #ue independientemente deln+mero de d0as #ue #ueden despu*s de visitar la ultimaciudad$ esto no reporta ninguna utilidad%

)a ta&la muestra la solución del su&pro&lema

y B % BE % BE9 % BE2 % BEB % BE % BEA & B f B. y B/

$ 8 8 8 8 8 $

9 $ B$ 8 8 8 8 9 B$

2 $ B$ $2 8 8 8 2 $2

B $ B$ $2 A$2 8 8 B A$2

$ B$ $2 A$2 G$ 8 G$

A $ B$ $2 A$2 G$ G$H9 A G$H9

0)( 44 = y f

03)()( 2/1333433 +=−+ x x y f x g


25/31

IO2- RosaDelgadillo

strategia de solucióntapa2n esta etapa se resuelve el pro&lema de cuantos

d0as dedicar a la ciudad 2 y a la ciudad B$ enforma con!unta% Dado #ue la decisión tomada enesta etapa afecta a la etapa B$ ya #ue)os d0as disponi&les en esta etapa tam&i*n son'

$9$2$B$ $A@ el su&pro&lema a ser resuelto es'

2 x223 x y y −=

{ })(1)( 2232/1

20

2222

x y f x y f Max y x−+=

≤≤


26/31

IO2- RosaDelgadillo

strategia de solución)a función y dado #ue se tiene'

)a ta&la muestra la solución del su&pro&lema

y 2 % 2E % 2E9 % 2E2 % 2EB % BE % 2EA & 2 f 2 . y 2/

$ 8 8 8 8 8 $

9 B$ 9$ 8 8 8 8 B$2 $2 $ 9$ 9 8 8 8 $2

B A$2 A$2 $ 9 9$HB 8 8 9 A$2

G$ G$2 A$GA $HB 2$ 8 9 G$2

A G$H9 H$ G$G9 A$ H A$ 2$2B 9 H$

)()( 33223 x f x y f =−

)()()( 2232/1

222322 x y f x x y f x g −+=−+

{ })()()( 3343333 x y f x g Max y f −+={ })()()()( 32243322

0,

22

32232

x x y f x g x g Max x f x x

y x x−−++=

≥≤+


27/31

IO2- RosaDelgadillo

strategia de solucióntapa9n esta etapa el n+mero de d0as disponi&les es

conocido$ con lo #ue el su&pro&lema a resolver es'

J la ta&la es'

y 9 % 9E % 9E9 % 9E2 % 9EB % 9E % 9EA & 9 f 9 . y 9/A H$ K$2 K$ G H$H H$ $ H 9 K$2

)( 1 y

)(2)()( 1122/1

111211 x y f x x y f x g −+=−+

{ })(2)( 1122/115

011

1

11

x y f x y f Max y

y x

−+=

=

≤≤


28/31

IO2- RosaDelgadillo

strategia de soluciónsolución)a determinación de la pol0tica óptima deasignación de d0as de visita a todas las ciudadeses o&tenido recursivamente$ partiendo de yo&servando en la etapa 2 el valor óptimo para

$el cual es $ por lo #ue a ora $ de la

o&servación en la etapa B .ta&la B/ se tiene #uepara el valor optimo esPor lo tanto la pol0tica óptima es dedicar un d0a ala ciudad 9 y 2@ y B d0as a la ciudad B%O&teni*ndose una utilidad de

1*1

=

x4*112 =−= x y y

1*2 = x 3*223 =−= x y y

43 = y3*3 = x

20,8)( 11 = y f


29/31

IO2- RosaDelgadillo

!emplos' (signación de recursosl propietario de B tiendas a comprado A cestas de cerezas$

para satisfacer la demanda en las diferentes tiendas% lpropietario desea determinar la forma de distri&uir loscanastos$ de manera de ma3imizar el &ene1cio total% )os

retornos .utilidades/ en función del n+mero de canastosdistri&uidos .se asume vendidos/ en las B tiendas están dadosen la siguiente ta&la%

Cantidad de canastos Lienda

9 2 B A

9 B H 92 9B

2 A 9 99 99 99

B G 99 92 92


30/31

IO2- RosaDelgadillo

!emplos' Modelo de Plani1cación de laProducción e Inventario

4na empresa de&e decidir su pol0tica de producción einventario para los pró3imos tres meses% )a empresa aad#uirido algunos compromisos de entrega para estosmeses'B$2$y unidades respectivamente% n el proceso

productivo se incurre en algunos costos #ue están asociadoscon la producción y el almacenamiento% stos se indican en lasiguiente ta&la

(suma #ue el inventario inicial es

Mes (lmacenamiento

. Nunidad8mes/

Producción. Nunidad/

9 9 92 B 9A

B 2 2


31/31

IO2 Rosa

!emplos' Modelo de Reemplazo de un#uipo

4na empresa posee un e#uipo de B a os de uso$ y deseadeterminar la pol0tica de reemplazo para los pró3imos Ba os% ,eg+n los antecedentes recopilados$ el valor de une#uipo nuevo es de M 9 $ los costos de operación y el

valor de rescate del e#uipo son entregados en la ta&la

5ota% Considere #ue el e#uipo no puede operar más allá del a o G%

dad Operación.M Na os/

Rescate.M /

9 9 $ H $

2 $ A $

B G $ B $

H $ 2 $

A K $ 9 $

G KA$ $

programación dinamica--

Documents