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 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)

DEFINICIÓN Y MODELOS DE PROGRAMACIÓN ENTERA

Un modelo de programación entera es un modelo que contiene restricciones y una función objetivo idénticas a las formuladas por planeación lineal. La única diferencia es que una o más variables de decisión tienen que tomar un valor entero en la solución final.

Existen tres tipos de modelos de programación entera

• Pura.

• Mixta.

• Binaria.

PROGRAMACIÓN ENTERA PURA

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 6x1 + 5x2+ 4x3

s.a 108x1 + 92x2 + 58x3 >= 576

7x1 + 18x2 + 22x3 >=83

X1, x2, x3 >= 0 y entonces

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

Ejemplo

Corte de Madera

Una marquetería debe enmarcar 175 cuadros de 119+96 cm. En el mercado puede comprar varillas de moldura indicada con longitud de 300cm.

¿Cómo deben captarse las varillas para obtener los marcos requeridos al menor sobrante posible?

Solución

Modalidades en corte

Xi: Numero de varillas estándar cortadas en la modalidad i (i= 1,2,3 )

Para 175 marcos se necesitan 350 piezas de cada longitud.

Minimizar: 62x1 + 1x2 + 30x3 longitud sobrante

Sujeta a:

2x1 + 1x2 ≥ 350 piezas de longitus 119

2x2 + 3x3 ≥ 350 piezas de longitud 90

PROGRAMACIÓN ENTERA BINARIA

En este caso todas las variables de decisión del modelo serán binarias, esto es sólo podrán tomar valor uno o cero. Existe una amplia gama de problemas donde este tipo de modelo son aplicables. Algunos ejemplos pueden ser:

• Ubicación

...