PROGRAMACION DINAMICA PROBLEMA 1

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

...