Programación Entera

INVESTIGACIÓN
OPERATIVA 1
Capítulo 7:
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.

04/02/15

2

1. Clasificación de los problemas
de programación entera
A diferencia de los problemas planteados hasta ahora,
donde se usaban variablesreales (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).
04/02/15

3

1. Clasificación de los problemas
de programación entera
• Problemasgenerales
• Problemas binarios
• Problemas mixtos

04/02/15

4

Problemas generales
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.04/02/15

5

Problemas generales
Ejemplo 7.1
Modelo de
Costo
avión
(millones
de $)

Capacidad
(pasajeros)

Tiempo de
mantenimiento
(horas por mes)

A

10

350

25

B

15

450

15

C

12

400

15

04/02/15

6

Problemas generales
Ejemplo 7.1 (continuación)
Capacidad de transporte mínima: 3,400 pasajeros
Tiempo total disponible de mantenimiento: 250horas mensuales
Disponibilidad de aviones modelo C: 5
04/02/15

7

Problemas generales
Ejemplo 7.1 (continuación)
Variables de decisión
Xj : número de aviones del modelo j que se comprarán
Donde j = 1, 2, 3 (1 = A, 2 = B, 3 = C)
Función objetivo
Minimizar los costos de adquisición de los aviones
Minimizar Z = 10 X1 + 15 X2 + 12 X3 

04/02/15

8

Problemas generales
Ejemplo 7.1(continuación)
Restricciones
Requerimiento mínimo de capacidad
350 X1 + 450 X2 + 400 X3  3400
Disponibilidad de tiempo de mantenimiento
25 X1 + 15 X2 + 15 X3  250
Disponibilidad del modelo C
X3  5
Rango de existencia
Xj  0 y enteros
04/02/15

9

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

04/02/15

10

Problemas binarios
Ejemplo 7.2
El entrenador trata de escoger una alineación inicial
para el equipo de básquetbol que dirige.
El equipo consta de siete jugadores que han sido
evaluados (en una escala de 1 = pobre a 3 = excelente)
de acuerdo a su manejo de lapelota, sus tiros, su rebote
y sus habilidades defensivas.

04/02/15

11

Problemas binarios
Ejemplo 7.2 (continuación)
Jugador

Posición

Manejo
de la
pelota

1

Defensa

3

3

1

3

2

Centro

2

1

3

2

3

Defensa / Ataque

2

3

2

2

4

Ataque / Centro

1

3

3

1

5

Defensa / Ataque

1

3

1

2

6

Ataque / Centro3

1

2

3

7

Defensa / Ataque
04/02/15

3

2

2

1

Tiros Rebote

Marca

12

Problemas binarios
Ejemplo 7.2 (continuación)
La alineación inicial de cinco jugadores debe satisfacer las
restricciones siguientes:
– Por lo menos 4 jugadores del equipo inicial deben poder jugar
en la defensa (D), por lo menos 2 miembros debe poder jugar
al ataque (A) y por lo menos1 jugador del equipo inicial debe
poder jugar en el centro (C).
– El nivel medio del manejo de la pelota, de los tiros, y del
rebote de la alineación inicial debe ser por lo menos igual a
10.
– Si inicia el jugador 3, entonces el jugador 6 no podrá iniciar.
– Si el jugador 1 inicia, entonces los jugadores 4 y 5 deben
iniciar al mismo tiempo.
– Ya sea el jugador 2 o el jugador 3 debe...