PROGRAMACION DINAMICA PROBLEMA 1
Enviado por susje27 • 25 de Abril de 2012 • 1.733 Palabras (7 Páginas) • 2.782 Visitas
PROGRAMACION DINAMICA
PROBLEMA 1
Considérese el gráfico que contempla las rutas posibles para ir desde la ciudad 1
hasta la ciudad 10. Cada nodo representa una ciudad y los arcos la infraestructura vial
disponible. La tabla recoge el costo asociado al desplazamiento entre cada par de
nodos para cada una de las etapas. Supondremos que todos los desplazamientos
tienen la misma duración, y que el viaje ha de realizarse en cuatro etapas. Cada una
de ellas se corresponde con un único desplazamiento entre un par de nodos del grafo,
así al finalizar la primera etapa estaremos en una de las ciudades 2, 3 ó 4. La
segunda etapa finalizará en la ciudad 5, la número 6 ó la número7. La tercera jornada
nos llevará a la ciudad 8 o a la número 9. La cuarta etapa permite finalizar el viaje en
la ciudad 10.
WINQSB
Se observa que la ruta más segura y menos costa es la ruta A,D,F,I,J el cual tiene un costo de 11 u.m en la póliza de seguros
PROBLEMA 2
La carga de un avión se distribuye con el propósito de maximizar el ingreso total.
Se consideran 5 elementos y sólo se necesita uno de cada uno. La compañía gana
5000 u.m. por elemento más una bonificación por elemento. El avión puede
transportar 2000 libras.
a) ¿Cuáles elementos deben transportarse?
b) Si se considera un volumen máximo de 120 pies cúbicos. ¿cuáles elementos deben
Transportarse?
WINQSB
POR PESO
El elemento que se debe transportar son los productos C,D,E
POR VOLUMEN
Los elementos que deben transportarse son los productos A y E
PROBLEMA 3
La tabla muestra los datos del siguiente problema de producción e inventario: la
demanda para los meses de enero, febrero, marzo y abril es de 4, 5, 3 y 4 unidades,
respectivamente. Las capacidades de producción son de 6, 4, 7, y 5 unidades; las
capacidades de almacenaje son 4, 3, 2 y 4 unidades respectivamente. Los costos de
preparación varían de un mes a otro y son: 500, 450, 500 y 600 u.m. para enero,
febrero, marzo y abril.
Determinar un programa de producción con el fin de minimizar los costos totales
Relacionados usando Winqsb.
WINQSB
Al resolver el problema se observa que la producción debe ser la siguiente en el mes de enero debe realizar una producción de capacidad de 5 ,en febrero de 4,en marzo de 3 y en abril de 4 para minimizar los costos .
ASUMIENDO INVENTARIO
Al resolver el problema con un inventario de 2 se observa que la producción debe ser la siguiente en el mes de enero debe realizar una producción de capacidad de 3, en febrero de 4,en marzo de 3 y en abril de 4 para minimizar los costos .
PROBLEMA 4
Un operador turístico organiza viajes de vacaciones, que incluyen el alquiler de coches.
Durante las próximas cinco semanas, y en función de los viajes que ha vendido, esta
empresa prevé que debe tener disponibles 8, 6, 10, 7 y 8 coches respectivamente.
El alquiler de los coches se subcontrata a una empresa local, que cobra una cantidad fija
de 50 euros por automóvil por cada nuevo alquiler de un coche, más 150 euros por cada
semana de alquiler de dicho coche.
El operador puede por tanto alquilar coches y asignarlos a los viajes organizados, o
mantenerlos sin usar, o bien devolverlos cuando ya no quiera usarlos (aunque quizás
tenga que volver a alquilarlos más tarde pagando la cantidad fija). ¿Cuál es el número
óptimo de automóviles a alquilar y/o devolver en cada semana de las próximas cinco?
Formule el modelo de programación dinámica.
Resuelve el problema.
SOLUCION
Solicitud de coches por semana
semana 1 semana 2 semana 3 semana 4 semana 5
8 6 10 7 8
Contratación de coches: 50 euros
Alquiler de coches: 100 euros
Formulación:
Etapas (ni): En este caso cada etapa será cada semana, total 5 etapas.
• Función de borde: 1 <= ni <= 5
Estado (Si): número de coches disponibles al comienzo de cada semana.
• Función de borde: 6 <= Si <= 10
Variables de decisión (Xi): número de coches a alquilar o devolver
• Función de borde: -4 <= Xi <= 0 ; 0 <= Xi <= 4
Función recursiva:
• ƒn(s,x) = ƒn(s,x) + ƒn+1(s+1,x+1)
Optimización: minimizar los gastos de alquiler
Etapa 5
Demanda de coches = 5 unidades
S5 X5 = 0 X5 = 1 X5 = -1 X5 = -2 ƒ5(s,x) X5
7 1,250 1,250 1
8 1,200 1,200 0
9 1,200 1,200 -1
10 1,200 1,200 -2
Etapa 4
Demanda de coches = 7 unidades
S4 X4 = 0 X4 = -1 X4 = -2 X4 = -3 ƒ4(s,x) X4
10 2,700 2,550 2,400 2,300 2,300 -3
Etapa 3
Demanda de coches = 10 unidades
S3 X3 = 0 X3 = 1 X3 = 2 X3 = 3 X3 =4 ƒ3(s,x) X3
6 4,000 4,000 4
7 3,950 3,950 3
8 3,900 3,900 2
9 3,850 3,850 1
10 3,800 3,800 0
Etapa 2
Demanda de coches = 6 unidades
S2 X2 = 0 X2 = 1 X2 = 2 X2 = -1 X2 = -2 X2 = -3 X2 = -4 ƒ2(s,x) X2
8 5,100 5,250 5,400 5,000 4,900 4,900 -2
9 5,200 5,350 5,100 5,000 4,900 4,900 -3
10 5,300 5,200 5,100 5,000 4,900 4,900 -4
Etapa 1
Demanda de coches = 8 unidades
S1 X1 = 8 X1 = 9 X1 = 10 ƒ1(s,x) X1
0 6500 6700 6900 6500 8
Solución final
Contratar Retirar Saldo
Semana 01 8 8
Semana 02 2 6
Semana 03 4 10
Semana 04 3 7
Semana 05 1 8
Monto total a gastar es: 6500 euros
se puede observar que la en la semana solo se tiene que contrata 8 automóviles, en la semana 2 de los 8 automóviles alquilados se tiene que retirar 2 ,para la semana 3 se tiene que alquilar 4 , parar la semana 4 se tiene que retirar 3 y para la semana 5 se tiene que contratar 1 para poder cubrir así la demanda de las 4 semanas .el cual nos genera un costo mínimo.
PROBLEMA 5
La presidenta de un partido político de un estado planea las próximas
...