CONCEPTOS BASICOS SOBRE PROGRAMACION ENTER

SESION 1:

CONCEPTOS BASICOS SOBRE PROGRAMACION ENTERA

SANTIAGO JAVEZ VALLADARES

OBJETIVO GENERAL:

1.- Dar a conocer las diferencias que existen entre los modelos lineales con variables continuas y con variables enteras puras y binarias.

Objetivos Específicos:

1.- Explicar las diversas limitantes que existen basadas en variables enteras y binarias.

2.- Dar alcances de cómo diferenciar el uso de las variables enteras y binarias.

3.- Exponer diversos ejemplos base para el uso de modelos enteros.

1.- Programación Entera

La programación entera es una aplicación mas real de los modelos lineales, se caracteriza por la presencia de nuevos tipos de variables como son la Variables Binarias, cuyo valor pueden ser 0 o 1.

Loa modelos de programación entera se pueden dividir en:

1.1.-Programación Entera Pura:

Son modelos similares a los desarrollados en el curso de Investigación de operaciones I, la diferencia es que las variables deben ser enteras puras.

Max (Min)=  C1X1 + C2X2+ C3X3 .....+ CnXn

Sujeto a:

 C1X1 + C2X2+ C3X3 .....+ CnXn  <= (>=)  (=)  B i

No negatividad:

Xi >=0 y Entero

1.2.- Programación Binaria Pura:

Este si es una nueva manera de formular un modelo lineal, se considera variables cuyo valor solo son cero (0) ó uno (1).Estas Variables se usan para considerar posibilidades de elección, por ejemplo decidir la compra de un maquina de cuatro posibles alternativas.

La presencia de estas variables se expresan de la siguiente manera:

Yi   1     Se hace uso de esta posibilidad.

1. No se hace uso de esta posibilidad.

Un ejemplo de un Modelo PL:

Max (Min)=  C1Y1 + C2Y2+ C3Y3 .....+ CnYn

Sujeto a:

 y1 + y2+ y3 .....+ yn  <= (>=)  (=)  B i

No negatividad:

Yi = 0,1

Algunos problemas referentes a este tipo de variables son:

Selección de Inversiones.

Elección de Ruta Corta.

Asignación de personal.

1.3.- Programación Entera Mixta:

Este modelo matemático esta formado por los dos tipos de variables, es decir variables continuas y variables binarias.

La representación tiene el siguiente formato:

Max (Min)=  C1X1 + C2X2+ C3X3 .....+ CnXn  

+ C2 Y1+C2Y2+....+CmYm

Sujeto a:

 C1X1 + C2X2+ C3X3 .....+ CnXn  <= (>=)  (=)  B i

y1 + y2+ y3 .....+ yn  <= (>=)  (=)  B i

No negatividad:

Xi >=0 y Entero

Yi=0,1

2.- Tipos de Limitantes

Algunos Tipos de restricciones que se van a considerar son las siguientes:

2.1.-  Excluyente:

Esta restricción sirve para elegir solo una alternativa de varias posibles.

Ejemplo 1:

Se tiene cuatro productos , elegir solo un producto como máximo:

La restricción es:    y1+y2+y3+y4 <=1

Ejemplo 2:

Una maquina puede producir ó 10 ó 20 ó 30.

X1<=10y1+20y2+30y3

Y1+y2+y3=1

2.2.- Pre-Requisito:

Es cuando se debe hacer una acción y recién la siguiente se puede realizar, por ejemplo:

Solo aquel que ha aprobado Invope I puede llevar Invope II. Las posibilidades se dan en la siguiente tabla:

Claro es que no se puede llevar Invope II sin haber aprobado Invope I, entonces estas posibilidades se pueden expresar:

Invope II   <= Invope I, pasándolo a variables de decisión:

               Y2 <=Y1

2.3.- Restricción Incluyente: esta restricción se  refiere a que dad una opción la otra de todas maneras se debe dar, ejemplo: si el producto 1 se elabora también el producto 3 se tiene que hacer;   y1=y3

2.4.-Enlace variable entera con variable binaria: Es necesaria en muchos casos relacionar estas variables pues tiene una relación directa.

 ejemplo:

Cada vez que se tiene un costo fijo dentro de un enunciado es sinónimo que se va a usar una variable binaria;

Modelo Matemático:

Max= 3x1+6x2-50y1-60y2

Sujeto a:

X1<=20y1

X2<=25y2

No negatividad:

Xi >=0 y entero

Yi= 0 ,1

El uso de Yi es necesario porque si se elabora el producto i se debe pagar el costo fijo correspondiente, si no se paga el costo fijo el producto no se elabora.

LABORATORIO

PARTE A

1.- Elija entre variables: entera,  continua y binaria a usar para las siguientes condiciones:

a) Botellas    (    )

b) horas       (     )

c) Cajas       (     )

d) Metros     (     )

e) Proyecto   (    )

f) Ruta          (    )

g) Mesas      (    )

h) Elección de curso. (     )

2.- Exprese matemáticamente las siguientes expresiones:

a)  Elegir un proyecto como máximo de los siguientes proyectos A, B,C y D.

b) La cantidad máxima del producto A a producir es de 50 unidades y del producto B es de 40

     unidades, elegir solo uno de estos productos.

c) Elabore el modelo PL según la siguiente tabla:

...