PED

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

INTRODUCCION 
 
La programación dinámica es un método de optimización desarrollado para resolver 
problemas orientados a la toma de decisiones de acuerdo a una serie de pasos dados. 
Es útil para plantear situaciones de la vida cotidiana en lenguaje matemático, incluso, 
para hacer planteamientos teóricos diversos. Está ligada intrínsecamente a la 
investigación de operaciones, y se vale de muchos de sus recursos, por ejemplo, el 
Principio de Optimalidad de Bellman. 
El propósito general de esta técnica, está enfocado en el tratamiento de los problemas 
de manera seccionada, es decir, toma un problema, lo divide en partes, y trata cada una 
en forma recursiva. Ejemplo práctico de esto, puede ser el algoritmo de la ruta corta, el 
cual puede ser resuelto a través de la programación dinámica. 
En el presente trabajo, se dará solución a los ejercicios planteados usando técnicas de 
programación entera y dinámica. Problemas de cubrimiento, de localización de planta, 
o incluso de toma de decisiones basadas en criterios probabilísticos, son algunas de las 
aplicaciones de la programación dinámica. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Solución: 
El problema planteado tiene capacidad de producción definida, por tanto, se trata de un 
problema de ubicación de planta con capacidad limitada. 
La producción origina un costo que no depende del nivel de producción de esa planta. 
Se busca optimizar un criterio económico. 
Para facilitar la interpretación y planteamiento del problema, agrupamos los datos 
conocidos de acuerdo a lo siguiente: 
 
Conjunto de ubicación de las plantas: 
𝐽{𝑛} 
Conjunto que representa la demanda de los clientes: 
𝐼{𝑛} 
Coste fijo de producción de las plantas en 𝑗 𝑝𝑎𝑟𝑎 𝑗 ∈ 𝐽: 𝐶𝐹𝑗 
 
Costo variable de asociado a la producción en 𝑗 𝐶𝑉𝑗 
 
Costo de transporte asociado a la distribución: 𝐶𝑇𝑖𝑗 
 
Cantidad de producto enviada desde la planta 𝑗 al cliente 𝑖: 𝑋𝑖𝑗 
 
Demanda: 𝑏𝑖 
 
Capacidad productiva de la planta localizada en 𝑗: 𝑈𝑗 
 
Variable binaria 𝑦𝑗 = {1: 𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑖𝑟 𝑝𝑙𝑎𝑛𝑡𝑎; 0: 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜 
 
Restricciones: 
 
Cumplir la demanda de cada cliente: 
∑ 𝑋𝑗𝑖 ≥ 𝑏𝑖
𝑗 ∈𝐽
 ; ∀ 𝑖 ∈ 𝐼 
 
El cliente 𝑖 se puede suministrar desde 𝑗 solo si la planta se construye en 𝑗 
∑ 𝑋𝑗𝑖 ≤ 𝑈𝑗𝑦𝑗
𝑗 ∈𝐽
 ; ∀ 𝑗 ∈ 𝐽 
 
 
 
 
La planta no puede exceder su capacidad: 
 
∑ 𝑋𝑗𝑖 ≤ 𝑈𝑗
𝑗 ∈𝐽
 
 
Restricciones sobre las variables: 
 
Dado que 𝑦𝑗 = 0 implica que 𝑋𝑖𝑗 = 0; ∀ 𝑖, 𝑦𝑗 = 1: 
 
 𝑦𝑗 ∈ {0,1}, ∀ 𝑗 ∈ 𝐽 
𝑋𝑖𝑗 ≥ 0 ∀ 𝑖 ∈ 𝐼, ∀ 𝑗 ∈ 𝐽 
 
Función a optimizar: 
 
𝑀𝑖𝑛: ∑ ∑ 𝐶𝑇𝑗𝑖𝑋𝑗𝑖 + ∑ 𝐶𝑉𝑗
3
𝑗 ∈𝐽
+ ∑ 𝐶𝐹𝑗𝑦𝑗
3
𝑗 ∈𝐽
3
𝑖 ∈ 𝐼
3
𝑗 ∈ 𝐽
 
 
Dado el anterior planteamiento, procedemos a construir la función para insertarla en la 
aplicación LINGO. 
 
!definicion de variables; 
sets: 
planta/1..3/:capacidad,cf,cv,y; !subindices en función de j; 
distribucion/1..4/:demanda; !subindices en funcion de i; 
jpi(planta,distribucion):ct,x; !subindices que relacionan j,i; 
endsets 
!conjunto de datos; 
data: 
capacidad=30 25 35; 
demanda=18 15 20 12; 
ct=9 9 7 5 
 7 7 4 6 
 3 4 7 9; 
cf=50000 40000 60000; 
cv=1000 1200 1600; 
enddata 
!funcion objetivo; 
min=@sum(jpi(j,i):x(j,i)*ct(j,i))+@sum(planta(j):cv(j))+@sum(planta(j)
:cf(j)*y(j)); 
!restricciones; 
!cumplir la demanda del cliente; 
@for(distribucion(i):@sum(planta(j):x(j,i))>=demanda(i)); 
!el consumidor i se puede suministrar desde j solo si la planta se 
construye en j; 
@for(planta(j):@sum(distribucion(i):x(j,i))<=capacidad(j)*y(j)); 
!la planta no puede exceder su capacidad; 
@for(planta(j):@sum(distribucion(i):x(j,i))<=capacidad(j)); 
!definicion de variables binarias; 
@for(planta(j):@bin(y)); 
!definicion de variables enteras; 
@for(jpi(j,i):@gin(x)); 
end 
 
 
Al ejecutarla, arroja los siguientes resultados: 
 
Global optimal solution found. 
 Objective value: 114114.0 
 Objective bound: 114114.0 
 Infeasibilities: 0.000000 
 Extended solver steps: 0 
 Total solver iterations: 15 
 Elapsed runtime seconds: 0.08 
 
 Model Class: PILP 
 
 Total variables: 15 
 Nonlinear variables: 0 
 Integer variables: 15 
 
 Total constraints: 11 
 Nonlinear constraints: 0 
 
 Total nonzeros: 54 
 Nonlinear nonzeros: 0 
 
 
 
 Variable Value 
Reduced Cost 
 CAPACIDAD( 1) 30.00000 
0.000000 
 CAPACIDAD( 2) 25.00000 
0.000000 
 CAPACIDAD( 3) 35.00000 
0.000000 
 CF( 1) 50000.00 
0.000000 
 CF( 2) 40000.00 
0.000000 
 CF( 3) 60000.00 
0.000000 
 CV( 1) 1000.000 
0.000000 
 CV( 2) 1200.000 
0.000000 
 CV( 3) 1600.000 
0.000000 
 Y( 1) 1.000000 
50000.00 
 Y( 2) 0.000000 
40000.00 
 Y( 3) 1.000000 
60000.00 
 DEMANDA( 1) 18.00000 
0.000000 
 DEMANDA( 2) 15.00000 
0.000000 
 DEMANDA( 3) 20.00000 
0.000000 
 DEMANDA( 4) 12.00000 
0.000000 
 CT( 1, 1) 9.000000 
0.000000 
 CT( 1, 2) 9.000000 
0.000000 
 CT( 1, 3) 7.000000 
0.000000 
 CT( 1, 4) 5.000000 
0.000000 
 CT( 2, 1) 7.000000 
0.000000 
 CT( 2, 2) 7.000000 
0.000000 
 CT( 2, 3) 4.000000 
0.000000 
 CT( 2, 4) 6.000000 
0.000000 
 CT( 3, 1) 3.000000 
0.000000 
 CT( 3, 2) 4.000000 
0.000000 
 CT( 3, 3) 7.000000 
0.000000 
 CT( 3, 4) 9.000000 
0.000000 
 X( 1, 1) 0.000000 
9.000000 
 X( 1, 2) 0.000000 
9.000000 
 X( 1, 3) 18.00000 
7.000000 
 X( 1, 4) 12.00000 
5.000000 
 X( 2, 1) 0.000000 
7.000000 
 X( 2, 2) 0.000000 
7.000000 
 X( 2, 3) 0.000000 
4.000000 
 X( 2, 4) 0.000000 
6.000000 
 X( 3, 1) 18.00000 
3.000000 
 X( 3, 2) 15.00000 
4.000000 
 X( 3, 3) 2.000000 
7.000000 
 X( 3,
4) 0.000000 
9.000000 
 
 Row Slack or Surplus Dual 
Price 
 1 114114.0 -
1.000000 
 2 0.000000 
0.000000 
 3 0.000000 
0.000000 
 4 0.000000 
0.000000 
 5 0.000000 
0.000000 
 6 0.000000 
0.000000 
 7 0.000000 
0.000000 
 8 0.000000 
0.000000 
 9 0.000000 
0.000000 
 10 25.00000 
0.000000 
 11 0.000000 
0.000000 
 
 
 
Resumimos el resultado en el siguiente cuadro: 
 
Planta Ubicaciones Cantidades Valor 
óptimo 
𝐵𝑟𝑎𝑠𝑖𝑙 
𝐸𝑢𝑟𝑜𝑝𝑎 18 
114.114,00 
𝐴𝑚é𝑟𝑖𝑐𝑎 𝑑𝑒𝑙 𝑆𝑢𝑟 12 
𝑀é𝑥𝑖𝑐𝑜 
𝐴𝑚é𝑟𝑖𝑐𝑎 𝐶𝑒𝑛𝑡𝑟𝑎𝑙 18 
𝐸𝑠𝑡𝑎𝑑𝑜𝑠 𝑈𝑛𝑖𝑑𝑜𝑠 15 
𝐸𝑢𝑟𝑜𝑝𝑎 2 
 
Este plan de envío minimiza los costos y cubre en su totalidad la demanda de cada 
ubicación, y además, no excede la capacidad de cada planta, así que los recursos de 
cada planta que se activa son empleados en forma óptima. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Solución: 
El problema plantea una situación en la cual se requiere construir el menor número 
posible de estaciones de bombeo de agua, optimizando la distancia entre ciudades, para 
garantizar un cubrimiento adecuado. 
Como se trata de una decisión binaria: construir/no construir estación de bombeo, en 
primer lugar, definimos un conjunto de variables cuyos valores serán 0-1: 
Sea 𝑋𝑖 ; 𝑖{1,2,3,4,5,6} el conjunto de ciudades a evaluar: 
𝑋𝑖 = {1: 𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑖𝑟 𝑒𝑠𝑡𝑎𝑐𝑖ó𝑛 𝑑𝑒 𝑏𝑜𝑚𝑏𝑒𝑜; 0: 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜 
Se trata de un problema de minimización debido a que se busca construir la menor 
cantidad de estaciones de bombeo posible. 
Tenemos la siguiente función objetivo: 
𝑀𝑖𝑛 = ∑ 𝑋𝑖
6
𝑖=1
 
Con las siguientes restricciones: 
𝑋1 + 𝑋4 + 𝑋5 ≥ 1 
𝑋2 + 𝑋3 + 𝑋4 ≥ 1 
𝑋3 + 𝑋5 ≥ 1 
𝑋4 + 𝑋6 ≥ 1 
𝑋1 + 𝑋3 ≥ 1 
𝑋3 + 𝑋6 ≥ 1 
Estas restricciones fueron construidas tomando en consideración la condición de tiempo 
establecida en el enunciado, es decir, se tomó en consideración para cada ciudad, 
aquellas distancias cuyo máximo valor iguala esta condición. Esto garantiza que dentro 
de la decisión, queden fuera de consideración aquellas combinaciones en las cuales 
este tiempo se excede, no así aquellas con tiempos menores, debido a que no afectan 
dicha condición. 
Al introducir estas ecuaciones en el software de optimización LINGO, obtenemos el 
siguiente resultado: 
Código introducido en el software: 
!problema de cubrimiento; 
!X<i>= ciudades a ser evaluadas, con i{1,2,3,4,5,6}; 
 
!función objetivo; 
min=x1+x2+x3+x4+x5+x6; 
 
!restricciones por ciudad; 
!ciudad 1; 
x1+x4+x5 >=1; 
!ciudad 2; 
x2+x3+x4 >=1; 
!ciudad 3; 
x3+x5 >=1; 
!ciudad 4; 
x4+x6 >=1; 
!ciudad 5; 
x1+x3 >=1; 
!ciudad 6; 
x3+x6 >=1; 
 
Resultados obtenidos: 
LINGO/WIN64 19.0.32 (3 Dec 2020 ), LINDO API 13.0.4099.242 
 
 Licensee info: Eval Use Only 
 License expires: 22 AUG 2021 
 
 Global optimal solution found. 
 Objective value: 2.000000 
 Infeasibilities: 0.000000 
 Total solver iterations: 7 
 Elapsed runtime seconds: 0.09 
 
 Model Class: LP 
 
 Total variables: 6 
 Nonlinear variables: 0 
 Integer variables: 0 
 
 Total constraints: 7 
 Nonlinear constraints: 0 
 
 Total nonzeros: 20 
 Nonlinear nonzeros: 0 
 
 
 
 Variable Value 
Reduced Cost 
 X1 0.000000 
1.000000 
 X2 0.000000 
1.000000 
 X3 1.000000 
0.000000 
 X4 1.000000 
0.000000 
 X5 0.000000 
0.000000 
 X6 0.000000 
0.000000 
 
 Row Slack or Surplus Dual 
Price 
 1 2.000000 -
1.000000 
 2 0.000000 
0.000000 
 3 1.000000 
0.000000 
 4 0.000000 -
1.000000 
 5 0.000000 -
1.000000 
 6 0.000000 
0.000000 
 7 0.000000 
0.000000 
 
 
Interpretación de los resultados: 
De acuerdo a lo reflejado en el reporte de la aplicación, el mejor valor de la función 
objetivo es: 
𝑍 = 2 
Esto indica, en primer lugar, que el número óptimo de estaciones de bombeo a construir 
son dos. 
En relación a los valores de las variables, aquellas cuyo valor es 1, representan la 
decisión de construcción de la estación de bombeo, de acuerdo al planteamiento inicial 
donde un valor igual a 1 sería interpretado como “construir la estación de bombeo”. En 
este caso, dichas variables son: 
𝑋3, 𝑋4 
 
 
 
En resumen, deben construirse dos estaciones de bombeo, una en la ciudad 3, y otra 
en la ciudad 4. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Solución: 
El problema planteado es del tipo probabilístico, y es posible resolverlo por medio de 
técnicas de programación dinámica probabilística. 
Primeramente, definimos los datos que permitirán abordar el problema adecuadamente: 
Sea 𝑋𝑛 el número de unidades paralelas a instalar del componente 𝑛 
Tenemos que: 
𝑃𝑛(𝑋𝑛) representa la probabilidad de que el componente 𝑛 funcione si se instalan 𝑋𝑛 
unidades paralelas. 
𝐶𝑛(𝑋𝑛) representa el costo de instalar 𝑋𝑛 unidades paralelas del componente 𝑛 
𝐷𝑛 representa el valor monetario disponible para invertir en componentes. 
 
Partiendo de lo anterior, la función objetivo es: 
 
𝐹𝑛(𝑆𝑛, 𝑋𝑛)𝑀𝑎𝑥 {𝑃𝑛(𝑋𝑛)𝑓𝑛+1(𝑆𝑛 − 𝐶𝑛(𝑋𝑛))} 
 
Ahora, evaluamos cada etapa haciendo los cálculos respectivos: 
 
𝑆4 
𝐶𝑜𝑚𝑝𝑜𝑛𝑒𝑛𝑡𝑒 4 − 𝐸𝑡𝑎𝑝𝑎 4 
𝑍 
𝐹4(𝑆4, 𝑋4) = 𝑃4(𝑋4) 
𝑋4 = 1 𝑋4 = 2 𝑋4 = 3 𝐹4(𝑆4) 𝑋4 
200 0,5 − − 0,5 1 
300 0,5 0,7 − 0,7 2 
400 0,5 0,7 0,9 0,9 3 
500 0,5 0,7 0,9 0,9 3 
600 0,5 0,7 0,9 0,9 3 
 
𝑆3 
𝐶𝑜𝑚𝑝𝑜𝑛𝑒𝑛𝑡𝑒 3 − 𝐸𝑡𝑎𝑝𝑎 3 
𝑍 
𝐹3(𝑆3, 𝑋3) = 𝑃3(𝑋3)𝑓4(𝑆3 − 𝐶3(𝑋3)) 
𝑋3 = 1 𝑋3 = 2 𝑋3 = 3 𝐹3(𝑆3) 𝑋3 
300 (0,7)(0,5) = 0,35 − − 0,35 1 
400 (0,7)(0,7) = 0,49 − − 0,49 1 
500 (0,7)(0,9) = 0,63 (0,8)(0,5) = 0,40 − 0,63 1 
600 (0,7)(0,9) = 0,63 (0,8)(0,7) = 0,56 (0,9)(0,5) = 0,45 0,63 1 
700 (0,7)(0,9) = 0,63 (0,8)(0,9) = 0,72 (0,7)(0,9) = 0,63 0,72 2 
 
 
 
 
 
 
 
 
𝑆2 
𝐶𝑜𝑚𝑝𝑜𝑛𝑒𝑛𝑡𝑒 2 − 𝐸𝑡𝑎𝑝𝑎 2 
𝑍 
𝐹2(𝑆2, 𝑋2) = 𝑃2(𝑋2)𝑓3(𝑆2 − 𝐶2(𝑋2)) 
𝑋2 = 1 𝑋2 = 2 𝑋2 = 3 𝐹2(𝑆2) 𝑋2 
500 (0,6)(0,35) = 0,210 − − 0,210 1 
600 (0,6)(0,49) = 0,294 − − 0,294 1 
700 (0,6)(0,63) = 0,378 (0,7)(0,35) = 0,245 − 0,378 1 
800 (0,6)(0,63) = 0,378 (0,7)(0,49) = 0,343 (0,8)(0,35) = 0,280 0,378 1 
900 (0,6)(0,72) = 0,432 (0,7)(0,63) = 0,441 (0,8)(0,49) = 0,392
0,441 2 
 
𝑆1 
𝐶𝑜𝑚𝑝𝑜𝑛𝑒𝑛𝑡𝑒 1 − 𝐸𝑡𝑎𝑝𝑎 1 
𝑍 
𝐹1(𝑆1, 𝑋1) = 𝑃1(𝑋1)𝑓2(𝑆1 − 𝐶1(𝑋1)) 
𝑋3 = 1 𝑋3 = 2 𝑋3 = 3 𝐹3(𝑆3) 𝑋3 
1000 (0,5)(0,441) = 0,2205 (0,6)(0,378) = 0,2268 (0,8)(0,378) = 0,3024 0,3024 3 
 
Probabilidades de que el sistema funcione: 30,24% 
Solución óptima: 
Componente Cantidad Costo 
𝑋1 3 300 
𝑋2 1 200 
𝑋3 1 100 
𝑋4 3 400 
 
 
REFERENCIAS BIBLIOGRAFICAS 
 
Ackoff, R. (1982). Fundamentos de Investigacion Operativa.Mexico: Limusa. 
Bosque, R. (1992). Capítulo 5. PROGRAMACIÓN DINÁMICA. Obtenido de 
http://www.lcc.uma.es/~av/Libro/CAP5.pdf 
Hillier, F. & Liberman, G. (2007). Investigación de operaciones.Mexico: McGraw-Hill 
Moya, M. (1998). Investigacion de Operaciones: La programacion Lineal.Costa Rica: 
EUNED. 
 
 
 
 
 
 
 
 
 
 
 
 
http://www.lcc.uma.es/~av/Libro/CAP5.pdf