Introducción a la Programación Discreta

INTRODUCCIÓN A LA PROGRAMACIÓN DISCRETA
Un poco de historia
• Segunda Guerra Mundial:
o Operaciones de gestión de
convoy.
o Despliegue de un radar.
o Operaciones de bombardeo.
o Puesta de minas.
o Operaciones anti-submarino.
• La aplicación de las Matemáticas y del método científico a las
operaciones militares se llamó Investigación Operativa (o Investigación
de Operaciones, del inglésOperations Research).
• Hoy en día, nos referimos también a la IO como Ciencia de la Gestión
(Management Science), aplicando un enfoque científico en la toma de
decisiones. Dicho enfoque pretende diseñar y operar un sistema de la
mejor forma, requiriendo usualmente el uso de recursos limitados, lo
cual nos lleva a la OPTIMIZACIÓN.
• El campo de la optimización está relacionado con lacaracterización de
soluciones y el desarrollo de técnicas algorítmicas para resolver
problemas matemáticos de la forma:

max (min) f ( x)
s.a.
x ∈ X ⊆ Rn

x: denota las variables de decisión.
f ( x) : función objetivo, mide la calidad de la solución.
X: conjunto de soluciones factibles.

1

• La optimización se ha convertido en un componente clave de las
decisiones diarias en actividadescomo la tecnología aeroespacial, la
biotecnología, las finanzas, la energía, las telecomunicaciones e
INTERNET.
• A partir de los años 40, la IO se desarrolla en el campo empresarial.
• En 1947, George Dantzig desarrolla un procedimiento para resolver un
problema de Programación Matemática Lineal (SIMPLEX).
• Un reciente estudio sobre las 500 mayores empresas de EE.UU. revela
que casi el85% usa o ha usado Programación Lineal.
• Existe una gran variedad de problemas o campos dentro de la IO:
Problemas de Caminos Mínimos, Árboles Generadores, Flujos en
Redes, Problema de Emparejamiento (matching), Problema de
Asignación y Transporte, Problema de la Mochila, Problemas de
Empaquetamiento, (set/bin packing), Problemas de Localización,
Problemas de Rutas (Circuitoshamiltonianos/eulerianos).
• Todos ellos están englobados en un área llamada Optimización en
Redes, la cual usa algoritmos específicos para resolver problemas de
optimización a gran escala en campos como las telecomunicaciones,
Internet, el transporte y la logística.

¿Qué es la Programación Discreta (PD)?
• La PD trata el estudio y resolución de problemas discretos (en grafos)
haciendo uso deherramientas de Programación Lineal (entera) y
algoritmos específicos.

2

• Dentro de la Programación Matemática existe una clasificación
atendiendo a la función objetivo y a las restricciones:
⎧
⎧Continua
⎪
⎪
⎪
⎪Prog. Lineal ⎨Entera, 0-1
⎪
Prog. Matemática ⎨
⎪Mixta
⎪
⎪Estocástica: energía, agua, finanzas, etc.
⎩
⎪
⎪Prog. No Lineal: tec. aeroespacial, eléctrica, computación, etc.
⎩• En Programación Discreta nos vamos a centrar fundamentalmente en la
Programación Lineal Entera.

Procedimientos para la resolución de problemas en PD
• Las técnicas usadas para resolver los problemas que surgen en PD son:
o Programación Matemática Lineal Entera.
o Branch & Bound
o Programación Dinámica.
o Metaheurísticas: Tabú Search, Simulated Annealing, Genetic

Algorithms, etc.3

Introducción a la Teoría de Grafos
Desde un punto de vista de aplicaciones reales, la Teoría de Grafos surge
en infinidad de aplicaciones reales.
• Redes de comunicaciones.

• Localización.

• Redes de transporte.

• Caminos óptimos.

• Redes de distribución.

• Emparejamiento.

• Redes eléctricas.

• Asignación y transporte.

• Redes de ordenadores, etc.

• Circuitoseulerianos y
hamiltonianos.
• Análisis de flujo en redes, etc.

• Un grafo G=(V, E) viene definido por un conjunto V de vértices (o
nodos) y un conjunto E de aristas que unen pares de vértices (i, j). Los

vértices se representarán gráficamente mediante un punto o círculo y las
aristas mediante una línea o arco entre dos vértices.
• Definimos N=|V| (ó n) como el número de vértices, de...