Programación entera

INTRODUCCIÓN

El presente trabajo de investigación está hecho con la finalidad de estudiar sobre lo que es la programación entera, su clasificación como son los modelos de programación entera pura, la programación entera binaria, la programación entera mixta y la utilización del software en la solución de problemas de programación entera, temas de gran importancia que nos servirán de mucho para nuestra vida profesional.

La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.

Consiste en optimizar, minimizar o maximizar una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de in-ecuaciones lineales.

La Programación Lineal se clasifica en, programación entera pura donde todas las variables de decisión tienen valores enteros; la programación entera mixta donde algunas de las variables de decisión tienen valores enteros. Las demás cumplen con la suposición de divisibilidad y la programación entera binaria que utiliza variables binarias.

La razón de esta investigación es concientizar a los estudiantes a interesarse por dichos temas ya que son de gran importancia y a través de la práctica perfeccionar el manejo de estos, para así en un futuro como profesionales poder desenvolverse con éxitos en sus labores asignadas.

RESUMEN

Un modelo de programación entera es aquel que contiene restricciones y una función objetivo idénticas a las formuladas en programación lineal, la única diferencia en que una o más variables de decisión deben tomar valor entero en la solución final. Existen tres tipos de modelos de programación entera; programación entera pura, es un modelo entero puro es, como su nombre lo indica, un problema en el que se exige que todas las variables de decisión tengan valores enteros; programación entera binaria en este caso todas las variables de decisión del modelo serán binarias, estos sólo podrán tomar valor uno o cero; programación entera mixta, algunas de las variables de decisión tienen valores enteros. Las demás cumplen la suposición de divisibilidad. Puede parecer que los problemas de programación entera son relativamente fáciles de resolver, pero por lo general resulta mucho más sencillo resolver los problemas de programación lineal que los de programación entera. Una primera idea para resolver un problema de programación entera podría ser resolver el problema lineal del problema entero, y redondear la solución. Hay que tener mucho cuidado pues al hacer esto existen algunos peligros. Se han propuesto muchos métodos para poder resolver este tipo de problemas además de redondear y verificar y el de la simple enumeración de puntos. El método más conocido y eficaz hasta el momento es el branch & bound. Este método resuelve inicialmente el problema sin considerar las restricciones de números enteros. Luego se selecciona una de las variables que debe ser entera agregando dos nuevas restricciones.

MARCO TEÓRICO

PROGRAMACIÓN ENTERA

Los modelos de programación entera son una extensión de los modelos lineales en los que algunas variables toman valores enteros.

Con frecuencia las variables enteras sólo toman valores en 0-1, ya que este tipo de variables permiten representar condiciones lógicas. Este tipo de modelos permite representar sistemas mucho más complejos.

A cambio, la resolución de los mismos se complica excesivamente. No se puede utilizar la suavidad de las funciones para inferir el comportamiento de las mismas cerca del óptimo.

CLASIFICACIÓN:

Existen tres tipos de modelos por programación entera

PURA: Son modelos similares a los de programación entera

Forma General:

Max (Min ) = A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn

Sujeto a : A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi

No negatividad: Xi >= 0 y ENTERO

BINARIA: Estos modelos lineales, las variables sólo toman valores 0 y 1, son usadas para uso probabilístico Donde 0 se rechaza la opción y 1 se acepta la opción

Forma General :

Max (Min ) = A1Y1+A2Y2+A3Y3+A4Y4+A5Y5+..........+AnYn

Sujeto a : y1+y2+y3+y4+..........+yn >= (<=)(=) Bi

No negatividad: yi >= 0 v 1

MIXTA: En estos tipos de modelos , integra las variables puras y las mixtas

Max (Min )

= A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn+A1Y1+A2Y2+A3Y3+A4Y4+A5Y5+..........+AnYn

Sujeto a:

A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi

y1+y2+y3+y4+..........+yn >= (<=)(=) Bi

No negatividad

Xi >= 0 y ENTERO

Xi >= 0 v 1

Tipos de Restricciones Usadas en la Programación Entera Mixta:

1) Excluyentes: Solo sirve para elegir una alternativa de varias posibles

2) Pre-requisito: Cuando necesitas realizar una acción antes de proceder con la siguiente

3) Incluyente: Dicha restricción se da para cuando realizas una acción "A" entonces debes hacer la acción "B"

4) Costo Fijo: Cuando se nombra un costo fijo, es sinónimo de uso de variable mixta.

Ejemplo Aplicativo

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

...