Programación entera

INSTITUTO TECNOLOGICO DE PACHUCA
(I.T.P)

MATERIA: INVESTIGACIÓN DE OPERACIONES I

PROFESOR: MARTINEZ SOLIS LUIS IGNACIO

CARRERA: INGENIERIA INDUSTRIAL

SEMESTRE: 5°

UNIDAD: 4° “PROGRAMACIÓN ENTERA”



FECHA: 29/MAYOL/2012
INDICE
Página

Temas:

4.1 INTRODUCCIÓN Y CASOS DEAPLICACIÓN……………………………………… 1

4.2 DEFINICIÓN Y MODELOS DE PROGRAMACIÓN ENTERA Y BINARIO……… 2 a 6

4.3 MÉTODO DE GOMORY………………………………………………………………….. 7

4.4 MÉTODO DE BIFURCACIÓN Y ACOTACIÓN………………………………………7 a 11

4.5 USO DE SOFTWARE…………………………………………………………………….. 12

INTRODUCCIÓN Y CASOS DE APLICACIÓN

Sus pioneros fueron Wagner (1950) y Manne (1959). Tradicionalmente estos modelos se han consideradocomo subclases de la programación lineal, sin embargo, las variables de decisión que aparecen en ellos sólo toman valores enteros, por lo que realmente deben considerarse como problemas de programación entera. El número de modelos lineales enteros y sus métodos de solución es en la actualidad bastante extenso, lo que nos ha llevado a hacer una selección considerando aquellos que creemos másinteresantes y que aparecen con mayor frecuencia en la realidad.
No siempre es admisible que las variables de un PL tomen valores continuos, existen:
• Decisiones dicotómicas (si-no)
• Decisiones que deben tomarse en unidades discretas
Si se requiere que todas las variables sean enteras, se dice que se habla de Programación Lineal Entera Pura; si se necesita que algunas de las variables de decisiónsean números enteros, se tiene un problema de Programación Lineal Entera Mixta.
En algunas aplicaciones, sólo se permite que todas las variables tomen valores de cero o uno, hablamos en estos casos de Programación Lineal Entera Binaria (Digital); si se requiere que solamente algunas de las variables tomen valores de cero o uno, se tiene un problema de Programación Lineal Entera Binaria Mixta.1

DEFINICIÓN Y MODELOS DE PROGRAMACIÓN ENTERA Y BINARIO

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 de las variables de decisión tienen que tomar un valor entero en 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 cómo 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 enteros

* Es un modelo entero puro. Sin las restriccionesadicionales x1, x2, x3 sean enteros (o sea las condiciones de integralidad) sería un problema de programación lineal

2

Ejemplo:

Corte de madera

Una marquetería debe enmarcar 175 cuadros de 119x96 cm. En el mercado puede comparar varillas de la moldura indicada con longitud de 300 cm. ¿Cómo deben cortase las varillas para obtener los marcos requeridos, obteniendo el menor sobrante posible?Solución

Modalidades de corte
X1: Número 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 longitud 119
2x2 + 3x3 ≥350 piezas de longitud 90PROGRAMACIÓN ENTERA MIXTA
Algunas de las variables de decisión tienen valores enteros. Las demás cumplen con la suposición de divisibilidad.
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...