Programacion Entera

Investigación Operativa 1
Capítulo 6: Programación entera

ÍNDICE
1. Clasificación de los problemas de programación entera. 2. Aplicaciones de programación entera. 3. Solución computacional de problemas de programación entera.

2

1. Clasificación de los problemas de programación entera (1)
A diferencia de los problemas planteados hasta ahora, donde se usaban variables reales(programación lineal real), ahora se hará uso de variables enteras (programación lineal entera). Un caso particular de las variables enteras son las variables binarias.

Es posible usar diversos tipos de variables en la formulación de los modelos matemáticos (programación lineal entera mixta).
3

1. Clasificación de los problemas de programación entera (2)
• Problemas generales • Problemas binarios• Problemas mixtos

4

Problemas generales (1)
Las variables de los problemas generales de programación entera deben asumir valores enteros. Las variables enteras pueden tener cotas superiores e inferiores pero no están restringidas a un subconjunto específico de valores y, por lo general, no existe una estructura especial para el problema.

5

Problemas generales (2)
Problema 1 • Lacompañía TODO HOGAR produce dos productos muy apreciados con los restauradores de casas: candelabros y ventiladores de techo de estilo antiguo. • Tanto los candelabros como los ventiladores requieren un proceso de producción de dos pasos que involucran cableado y ensamble.

6

Problemas generales (3)
Problema 1 (continuación) • Se requieren 2 horas para cablear cada candelabro y 3 horas paracablear un ventilador de techo. El cableado final de los candelabros y ventiladores requiere 6 y 5 horas, respectivamente. • La capacidad de producción es tal que sólo están disponibles 12 horas de cableado y 30 horas de ensamble. • Cada candelabro producido reditúa a la firma I/. 7.00 y cada ventilador I/. 6.00.
7

Problemas generales (4)
Variables de decisión X1: número de candelabros que seproducen y venden X2: número de ventiladores de techo que se producen y venden

Maximizar Z = 7 X1 + 6 X2 (maximizar utilidades) Sujeta a 2X1 + 3X2 ≤ 12 (horas de cableado) 6X1 + 5X2 ≤ 30 (horas de ensamble) Con X1, X2 ≥ 0 y enteros
8

Problemas binarios (1)
Los problemas binarios de programación lineal entera tienen variables que sólo pueden tomar valores 0 o 1. Las variables binarias, enesencia se plantean en situaciones del tipo “todo o nada” o “hacerlo o no hacerlo”.

9

Problemas binarios (2)
Problema 2 Supongamos que una persona está interesada en elegir entre un conjunto de inversiones (1, 2, 3, 4, 5, 6, 7) y quiere hacer un modelo binario para tomar la decisión. Modelar las siguientes restricciones:
a) b) c) d) No se puede invertir en todas. Si se elige la 3 no sepuede elegir la 1. La inversión 4 se puede elegir sólo si se elige la 2. Se eligen las inversiones 2 y 5 o ninguna de las dos.
10

Problemas binarios (3)
Problema 2 (continuación) a) No se puede invertir en todas. X1 + X 2 + X3 + X 4 + X5 + X 6 + X7 ≤ 6 b) Si se elige la 3 no se puede elegir la 1. X1 + X 3 ≤ 1 c) La inversión 4 se puede elegir sólo si se elige la 2. X4 – X 2 ≤ 0 d) Se eligenlas inversiones 2 y 5 o ninguna de las dos. X2 – X 5 = 0
11

Problemas mixtos
Los problemas en los que se requiere que algunas, pero no todas las variables, sean enteras, se denominan problemas mixtos de programación lineal entera. Estos problemas permiten la combinación de variables enteras y reales. Las variables enteras pueden ser generales o binarias, dependiendo de la situación que serepresenta.

12

2. Aplicaciones de Programación entera
2.1 2.2 2.3 2.4 2.5 Problema de cargo fijo Problema de recubrimiento de conjuntos Restricciones inclusivas o distributivas Restricciones si ... entonces Funciones lineales por segmentos

13

2.1 Problema de cargo fijo (1)
Problema 3 La compañía TRANSPORTES tiene tres alternativas para ubicar un nuevo almacén (Piura, Trujillo y...