EJERCICIOS 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.

	PRODUCTO  A	PRODUCTO C
CAPACIDAD	7 UNIDADES		DISP.
SECADO		4H/UNIDAD	22 H/SEM.
PULIDO	2 H/UNIDAD	3 H/UNIDAD	19 H/SEM.
UTILIDAD	$1/UNIDAD	$3/UNIDAD

 V.D.

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

Modelo de P.L.E.

Maximizar (z) = x1 + 3x2

Sujeto a:

                        x1   <= 7

                        4x2 <= 22

               2x1 + 3x2 <= 19

no negatividad: Xi>=0 y entero.

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.

	ESPACIO   DE     TIEMPO
	8 a.m.	10 a.m	12 m
Columbus	10	6	6
Denver	9	10	9
Los Ángeles	14	11	10
Nueva York	18	15	10

V.D

   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.

GENERADOR	COSTO FIJO DE CONEXIÓN	COSTO POR PERIODO POR MEGAWATT USADO	CAPACIDAD MAXIMA EN CADA PERIODO ( MW )
A	$ 3000	$ 5	2100
B	2000	4	1800
C	1000	7	3000

V.D.

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)

      

Restricciones:

Demanda en el periodo 1:

  xa1 +xb1+xc1 >= 2900

Demanda en el periodo 2:

xa2+xb2+xc2>= 3900

Capacidad de generador A:

 xa1 <= 2100y1( enlace variable entera con variable binaria)

 xa2<=2100y1( enlace variable entera con variable binaria)

Capacidad de generador B:

xb1<=1800y2( enlace variable entera con variable binaria)

xb2<=1800y2( enlace variable entera con variable binaria)

Capacidad de generador C:

xc1<=3000y3( enlace variable entera con variable binaria)

xc2<=3000y3( enlace variable entera con variable binaria)

Función Objetivo:

Minimizar(z)= 5(x11+x12) +4(x21+x22) + 7(x31+x32) +3000(y1)+2000(y2) + 1000(y3)

PROBLEMA PERT/CPM

D) PROBALIDAD DE QUE EL PROYECTO TERMINE EN 23 DIAS:   99.16 %

   

   Z = 2.39

PROBLEMA PERT/CPM

CINCO EJEMPLOS DE VARIABLES DE PROGRAMACION ENTERA

PROGRAMACION ENTERA (Resumen)

Programación Entera es un termino general para los modelos de programación matemática que presentan condiciones de integridad (condiciones que estipulan que algunas o todas las variables de decisión deben tener valores enteros). Ya hemos apuntado que los modelos de programación lineal entera son modelos de programación lineal que tienen la característica adicional de que algunas de las variables de decisión deben tener valores enteros. Existen diversas clasificaciones de esta categoría de modelos.

Programas Enteros Puros

Un modelo entero puro (PLE) es, como su nombre lo indica, un problema en el que se exige que todas las variables de decisión tengan valores enteros. Por ejemplo

Min 6×1 + 5×2 + 4×3

s.a. 108×1 + 92×2 + 58×3 >= 576

7×1 + 18×2 + 22×3 >= 83

x1, x2, x3 ><0 y enteros

Es un modelo entero puro. Sin las restricciones adicionales de que x1, x2, x3 sean enteros (o sea las condiciones de integralidad) seria un problema de programación lineal

Programas Enteros Mixtos

Un problema en el que solo se requieren que algunas variables tengan valores enteros mientras que otras pueden asumir cualquier numero no negativo (es decir, cualquier valor continuo) se llama programación lineal entera mixta (PLEM). Por ejemplo, supóngase que en el problema anterior solo x1 y x2 deben ser enteros y x3 no. El problema resultante es:

Min 6×1 + 5×2 + 4×3

s.a. 108×1 + 92×2 + 58×3 >= 576

7×1 - 18×2 + 22×3 >= 83

x1, x2, x3 >=0; x1 y x2 enteros

Programas Enteros 0–1

En algunos problemas se restringe el valor de las variables a 0 o 1. Dichos problemas se llaman binarios o programas lineales enteros 0–1. Son de particular interés debido a que se pueden usar las variables 0–1 para representar decisiones dicotómicas (sí o no). Diversos problemas de asignación, ubicación de plantas, planes de producción y elaboración de cartera, son de programación lineal entera 0–1.

Existen dos métodos para generar las restricciones especiales que fuercen la solución óptima del problema, hacia la solución óptima entera deseada:

- Método de ramificar y acotar.

- Método de planos de corte.

En ambos métodos las restricciones agregadas eliminan partes del espacio de soluciones, pero nunca alguno de los puntos enteros factibles. Desafortunadamente, ninguno de los dos métodos es efectivo en la solución de problemas de programación lineal entera. No obstante los métodos de ramificar y acotar son mucho mejores en cuanto al calculo se refiere que los métodos de plano de corte. Por esta razón, la mayoría de los códigos comerciales se basan en el procedimiento de ramificar y acotar.

TRABAJO PERT 13/04/2011

Invope

PERT CPM

Hola =D

saludos a todos!!! suerte con el curso ;)