Aaaaa

Contenido

TIPOS DE MODELOS PARA PROGRAMACION LINEAL ENTERA 3
INTERPRETACION GRAFICA 4
COMENTARIOS 7
SOLUCIONES REDONDEADAS 7
APLICACIONES A LA VARIABLE 0-1 9
CONDICIONES LOGICAS 12
No más de k de entre n alternativas 12
Decisiones dependientes 13
Restricciones de aportaciones 14
PROBLEMA DE UBICACION DE LOS ALMACENES STECO. 15
METODOS DE PROGRAMACION ENTERA 20
ALGORITMO DEBIFURCACION Y ACOTAMIENTO 20

CAPITULO I

PROGRAMACIÓN LINEAL ENTERA

INTRODUCCIÓN

❖ En este capítulo veremos problemas que se podrían formular y resolver como problemas de programación lineal, excepto por la desagradable circunstancia de que se requiere que algunas o todas las variables tomen valores enteros.
❖ Dichos problemas se llaman PE (Programación Entera).
❖ La programación enteraha llegado a ser un área muy especializada de la ciencia de la administración.
❖ En este curso sólo la tocaremos en forma superficial, veremos la importancia del tema y algunos métodos de resolución más útiles.
❖ Vimos en los capítulos anteriores que las variables podían tomar valores fraccionados, tales como 6.34. Pero hay casos en el mundo real que no es posible esto y deben ser enteros.❖ En el fondo es que existen muchos problemas administrativos importantes que serian de programación lineal si no fuera por el requerimiento de que sean enteros los valores de algunas variables de decisión, en los que no se pueden encontrar una buena solución mediante el uso del método simplex seguido del redondeo de los valores óptimos resultantes para las variables de decisión. Estosproblemas deben ser resueltos mediante algoritmos especialmente diseñados para resolver problemas de programación entera.

1 TIPOS DE MODELOS PARA PROGRAMACION LINEAL ENTERA

Programación entera es un término general para los modelos de programación matemática que presentan condiciones de ser enteros (condiciones que estipulan que algunas o todas las variables de decisión deben tener valoresenteros). Existen diversas clasificaciones de esta categoría de modelos.

□ Un modelo entero puro (PEP) 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

Minimizar 6X1 + 5X2 + 4X3

Sujeto a 108X1 + 92X2 + 58X3 ≥ 576

7X1 + 18X2 + 22X3 ≥ 83X1, X2, X3 ≥ enteros

es un modelo entero puro.
□ Un problema en el que sólo se requiere que algunas variables tengan valores enteros mientras que otras pueden asumir cualquier número no negativos (es decir, cualquier valore 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.

Elproblema resultante es

Minimizar 6X1 + 5X2 + 4X3

Sujeto a 108X1 + 92X2 + 58X3 ≥ 576

7X1 + 18X2 + 22X3 ≥ 83

X1, X2, X3 ≥ 0 ; X1 y X2 enteros.

□ En algunos casos se restringe el valor de las variables a 0 ó 1. Dichos problemas se llaman binarios o programación lineal entera 0-1. Son de interés debido a que se pueden usar las variables 0-1 pararepresentar decisiones dicotómicas (sí o no).

Diversos problemas de asignación, ubicación de planta, planes de producción y de construcción, son de programación lineal entera 0-1. Las variables 0-1 se pueden encontrar tanto en problemas de PEP como PLEM.

A menudo se consideran problemas de programación lineal (PL) que se comienzan como PEP o PLEM, ignorando las restricciones enteras. Aestos problemas de PL se les llama aproximaciones en las PEP o PLEM correspondientes.

2 INTERPRETACION GRAFICA

Considérese el siguiente problema

Maximizar 18E + 6F

Sujeto a E + F ≥ 5 (1)

42.8E + 100F ≤ 800 (2)

20E + 6F ≤ 142 (3)

30E + 10F ≥ 132 (4)...