Problema 3

Considere el problema de programacion de la produccion de un producto las 3 semanas siguientes. El costo unitario de produccion es de $100 para las 2 primeras semanas y $150 para las dos ultimas. Las demas semanales son 5,3 y 8 unidades respectivamente y tienen que ser satisfechas. Las plantas pueden producir un maximo de 7 semanales, Ademas, se oueden emplear horas extras durante 2 ultimas semanas, esto incrementa la produccion en 2 unidades por semana, pero el costo de produccion sube en $20 por unidad extra. El exceso de produccion se puede almacenar a un costo unitario de $3 por semana. Si al inicio se tiene 1 unidad de inventario y se desea tener al final 2 unidades¿cual debe ser el plan de produccion?

Problema 2

Dado el siguiente problema de mochila:
Max = 5x1+4x2^2+2x3^3
sa 4x1+3x2+2x3<=8
xi>=0

Programacion Dinamica Deterministica

Problema 1
Cierto estudiante desea destinar los siete dias de la semana proxima a estudiar cuatro cursos. Necesita al menos un dia para cada curso y el puntaje que puede lograr se da en la siguiente tabla:
¿Cuantos dias debe estudiar cada curso para lograr un puntaje?

Programacion Dinamica

Programación Dinámica

El matemático Richard Bellman  (1920–1984) inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.

Bellman estudió matemáticas en la Universidad de Brooklyn, donde obtuvo una diplomatura, y luego en la Universidad de Wisconsin, donde obtuvo su licenciatura. Posteriormente comenzó a trabajar en el Laboratorio Nacional Los Álamos en el campo de la física teórica. En 1946 obtuvo su doctorado en la Universidad de Princeton. También ejerció la docencia en la universidad del sur de California(EE. UU.), fue socio de la Academia Americana de las Artes y las Ciencias (1975) y de la Academia Nacional Americana de Ingeniería (1977). En 1979 el IEEE le otorgó la medalla de honor por su contribución a la teoría de los sistemas de control y de los procesos de decisión, en especial por su contribución con la programación dinámica y por la ecuación de Bellman.

La programación dinámica es una técnica que se utiliza para resolver diversos problemas de optimización. Esta técnica llega a la solución trabajando hacia atrás partiendo del final del problema hacia el principio, por lo que un problema enorme e inmanejable se convierte en una serie de problemas más pequeños y manejables.

La programación dinámica es un procedimiento matemático diseñado principalmente para mejorar la eficiencia de cálculo de problemas de programación matemática seleccionados, descomponiéndolos en subproblemas de menor tamaño y por consiguiente más fáciles de calcular. Los resuelve en etapas en donde cada etapa interviene una variable de optimización. Los cálculos en las diferentes etapas se enlazan a través de cálculos recursivos de manera que se genere una solución optima factible a todo el problema.

Programacion Dinamica

PROBLEMAS DE PLE

1.       Stocko puede invertir cuando mucho en dos inversiones

·         X1+x2+x3+x4<=2

2.       Si stocko invierte en 2, entonces también debe invertir en 1

·         X2<=x1 o bien x2-x1<=0

3.       Si stocko invierte en 2,  no puede invertir en 4

·         X2+x4<=1

4.       De los 3 nuevos producto deben escogerse a lo más 1

·         X1+x2+x3<=1

5.       Solo una de las dos plantas debe asignarse para la producción de 1 producto

·         Y1+y2<=1x1 , x1=1

6.       Para producir el producto 3 y 4 se debe de producir 1 y 2

·         Y3+y4<=y1+y2

7.       Si se hace en proyecto 1 y 2 no debe de hacerse el proyecto 3

·         Y1+y2-2y3>=2

8.       Para fabricar un producto 2 se tienen que hacer dos productos 1

·         Y2>=2y1

9.       Para hacer el producto 3 tengo que hacer el 1 y el 2, pero no el 4

·         Y3>=y1+y2, y3+y4<=1

10.   Si escojo hacer el producto 1, no debo de hacer el producto 2 y 3

·         Y1+y2+3<=1

Practica de programacion entera

Problema 1.-

Una firma elabora dos productos, A y C. La capacidad de la línea A es de 7 unidades diarias. Cada unidad de C requiere 4 horas de secado, y hay un total de 22 horas disponibles al día para secado. Además, cada unidad de A requiere 2 horas de pulido y cada una de C, 3 horas. Diariamente hay un total de 19 horas de pulido disponibles. Las unidades A producen una utilidad de $1 y $3 las unidades de C, cada una. La firma quiere determinar el plan de producción diario que maximice la utilidad. Los productos A y C sólo se pueden fabricar en cantidades enteras.  El costo de alquiler de una secadora es de $150 y de una pulidora es de $300, además se desea  elaborar solo uno de los productos A ó C. Formule el plan como PLE.

Xi= Número de unidades del producto i(i= A,B=1,2) a elaborar

MAX     1X1+3X2-150Y1-300Y2
CAPACIDAD	X1<=7
SECADO	4X2<=22Y1
PULIDO	2X1+3X2<=19Y2
BINARIA	Y1+Y2<=1



Problema 2.- Programación en una aerolínea.  Alpha Airline desea programar no más de un vuelo desde Chicago hasta cada una de las siguientes ciudades: Columbus, Denver, Los Ángeles y Nueva  York. Los horarios  de salida disponible son 8, 10 y 12 de la mañana. Alpha arrienda los aviones al costo de $5000 hasta las 10, y de $3000 después de las 10 y está en posibilidad de arrendar cuando mucho 2 por horario de salida. En la tabla 2 se presenta la aportación a las utilidades en miles de dólares esperadas por vuelo  antes de los costos de arrendamiento. Elabore un modelo para una programa que maximice las utilidades, si además se debe cumplir con lo siguiente:

a)      Si sale un vuela a Columbus a las 8 a.m. ya no debe salir un vuelo a Denver a las 10 a.m..

b)      Si sale un avión a los Ángeles a las 10 a.m. también debe salir un vuelo a Columbus a las 12 m.

c)      Saldrá un vuelo hacia Nueva York solo si sale antes un vuelo hacia Columbus.



Xij= 0 si el avión no sale a la hora i(i=8,10,12=1,2,3) hacia la ciudad j(j=Columbus,Denver, Los Angeles, Nueva York=1,2,3,4)

        1 si el avión sale a la hora i(i=8,10,12=1,2,3) hacia la ciudad j(j=Columbus,Denver,LA, NY)

<><><><>

MAX[10x11+6x21+6x31+9x12+10x22+9x32+14x13+11x23+10x33+18x14+15x24+10x34
-5(x11+x12+x13+x14+x21+x22+x23+x24)-3(x31+x32+x33+x34)]*1000
Columbus	x11 + x21 + x31 <=1 y1		x11+x22<=1
Denver	x12 + x22 + x32<=1
Los Angeles	x13 + x23 + x33<= 1		x23=x31
Nueva York	x14 + x24 +x34 <= 1y4		y4<=y1
08:00 a.m.	x11+ x12x13+x14<=2y5
10:00 a.m.	x31+x32+x33+x34<=2y6
12 m	x21+x22+x23+x24<=2y7

Problema 3.- Un problema de instalación  Un problema que afronta todos los días un electricista consiste en decidir qué  generadores conectar. El electricista en cuestión tiene tres generadores con las características que se muestran en la tabla 3. Hay dos periodos en el día. En el primero se necesitan 2900 megawatts. En el segundo. 3900 megawatts. Un generador que se conecte para el primer periodo  puede  ser usado en el segundo sin causar un nuevo gasto de conexión. Todos los generadores principales (como lo son A, B y C de la figura ) son apagados al término del día. Si se usa el generador A  también puede usarse el generador C,no se usa generador B si se usa generador A.  Formule este problema como un PLEM.

Xij= Número de megawatts a usar del generador i(i=A,B,C) en el periódo j(j=1,2).

Yi=  0 No arranca el generador i(i=A,B,C)

        1 Si arranca el generador i(i=A,B,C)

<><><><>

MIN 5(x11+x12) +4(x21+x22) + 7(x31+x32) +3000y1+2000y2 + 1000y3
P1	x11+x21+x31>=2900
P2	x12+x22+x32>=3900
A	x11<=2100y1
	x12<=2100y1
B	x21<=1800y2
	x22<=1800y2
C	x31<=3000y3
	x32<=3000y3
Binaria	y1+y3<=2
	y2-y1<=1