BIENVENIDOS

INVESTIGACIÓN
DE
OPERACIONES
M. Sc. Juan C.
Zerna Torres
 CONTENIDO
Desarrollo Modelización
Introducción Histórico Matemática Clasificación

M. Sc. Juan Carlos Zerna Torres

 CONTENIDO
Desarrollo Modelización
Introducción Histórico Matemática Clasificación

 ¿Qué es I/O?

 Definiciones

 Etapas

 Importancia

M. Sc. Juan Carlos Zerna Torres

 CONTENIDO
Desarrollo Modelización
Introducción Histórico Matemática Clasificación

 Prog. Lineal

 Prog. Dinámica

 Prog. Entera

M. Sc. Juan Carlos Zerna Torres

 CONTENIDO
Desarrollo Modelización
Introducción Histórico Matemática Clasificación

 ¿Qué es un
modelo?
 Problema de
producción.
 Construcción y
Resolución de
modelos

M. Sc. Juan Carlos Zerna Torres

 CONTENIDO
Desarrollo Modelización
Introducción Histórico Matemática Clasificación

 Modelo general

 Problemas
Lineales
 Problemas
Enteros Mixtos
 Problemas
No Lineales

M. Sc. Juan Carlos Zerna Torres

¿Qué es la Investigación de Operaciones?
La IO consiste en el uso de métodos analíticos avanzados que ayudan en la toma de decisiones.

Sentido Modelo
común matemático
Intuición Vs. Metodología formal

Estos métodos analíticos incluyen:

 Optimización: encontrar la mejor decisión posible de entre un conjunto de alternativas.
 Simulación: imitación de la realidad (comportamientos, materiales, ideas, …) que ahorra tiempo y costos.
 Probabilidad y estadística: ayuda a resumir / analizar información, medir riesgos, realizar predicciones,
etc.
Definiciones
La teoría de la optimización (también denominada programación matemática) intenta dar respuesta a un tipo
general de problemas de la forma:

 
𝑴𝒂𝒙 ( 𝑴𝒊𝒏 ) 𝒇 ( 𝒙)
𝒏
 
𝒙 ∈ 𝜴⊆ 𝑰 𝑹
 x = (x1,...,xn) es un vector que representa a las variables de decisión.
 f(x) es llamada función objetivo y mide la calidad de las decisiones.
 Ω es el conjunto de decisiones factibles o restricciones del problema. Muchas veces se puede expresar Ω como
un sistema de igualdades y/o desigualdades.
 Un problema de optimización trata entonces de tomar una decisión óptima para maximizar (ganancias,
velocidad, eficiencia, etc.) o minimizar (costos, tiempo, riesgo, error, etc.) un criterio determinado. Las
restricciones significan que no cualquier decisión es posible.
Definición según F. Hillier & G. Lieberman

Mathematical programming uses a mathematical model to describe the

problem of concern. The word programming does not refer here to
computer programming; rather, it is essentially a synonym for planning.
Thus, mathematical programming involves the planning of activities to
obtain an optimal result, i.e., a result that reaches the specified goal
best (according to the mathematical model) among all feasible
alternatives.
- Frederick Hillier & Gerald Lieberman
ETAPAS DE LA PROGRAMACIÓN MATEMÁTICA
La programación matemática es una potente técnica de modelado usada para la toma de decisiones. Generalmente
se deben cubrir las siguientes etapas:

 La primera etapa consiste en identificar las posibles decisiones que pueden tomarse; esto lleva a identificar las
variables de decisión. Normalmente estas variables son de carácter cuantitativo (pero también pueden ser de tipo
cualitativo, por ejemplo, para identificar decisiones de tipo SI o NO).

 La segunda etapa supone determinar qué decisiones resultan factibles; esto conduce a un conjunto de restricciones
que se determinan teniendo presente la naturaleza del problema en cuestión.

 En la tercera etapa, se calcula el coste/beneficio asociado a cada decisión factible; esto supone determinar una
función objetivo que asigna, a cada conjunto de variables de decisión, un valor de coste/beneficio total.

El conjunto de todos estos elementos define el problema de optimización.

M. Sc. Juan Carlos Zerna Torres
IMPORTANCIA DE LA PROGRAMACIÓN MATEMÁTICA
 La gente optimiza: las compañías aéreas planifican a la tripulación y sus aviones de forma que minimizan sus
costes; los inversores se crean carteras (portafolios) para maximizar su rentabilidad evitando un riesgo elevado; las
industrias intentan maximizar la eficiencia en el diseño y operación de sus procesos de producción, etc.

 La naturaleza optimiza: Los sistemas físicos tienden a un estado de mínima energía; los rayos de luz viajan de tal
forma que su tiempo de llegada es mínimo; etc.

 Ejemplos reales de aplicaciones exitosas de la PM:

 Premios Edelman: www.informs-org/Prices/EdelmanPrizeDetalis.html, a ellos concurren empresas y

organizaciones de todo el mundo compitiendo por tales galardones a la excelencia en la aplicación práctica de
la IO.
 www.scienceofbetter.org
 http://www.orchampions.org/

M. Sc. Juan Carlos Zerna Torres

IMPORTANCIA DE LA PROGRAMACIÓN MATEMÁTICA
 Mediante un Decision Support System, Continental Airlines ahorró $40M en el 2001, generando decisiones óptimas
para reorganizar su flota.

 La empresa FORD, utilizando técnicas de programación matemática, optimizó la forma en la que diseñaba y
probaba vehículos prototipo, ahorrando $250M.

 La empresa UPS usó la PM para rediseñar su red de repartos y así ahorrar $87M entre 2000 y 2002, y otros $189M
estimados hasta 2010.

 La cadena NBC usó la PM para mejorar sus estrategias de oferta de espacio publicitario incrementando su
beneficio en mas de $200M.

 La compañía AT&T se ahorró más de $100M a finales de los 90’s optimizando la capacidad de restablecimiento de
su red de telecomunicaciones tras un fallo del sistema.

 British Telecom usa técnicas de PM para optimizar la planificación de los 40000 ingenieros/informáticos de su
plantilla. Espera ahorrar $250M cada año.

M. Sc. Juan Carlos Zerna Torres

Desarrollo Histórico
Los métodos de la programación matemática han tenido el siguiente desarrollo:

Programación Lineal:
1938: Kantorovich --- Planeación estratégica, Asignación óptima de recursos humanos (“Métodos matemáticos para la
organización y la producción” 1939, Nobel de Economía 1975 ).
1947: Dantzig -------- Método Simplex (NP).
1984: Karmarkar ---- Método proyectivo (Algoritmo de punto interior).

Programación Dinámica:
1960: Bellman.

Programación Entera:
1950: Dantzig, Gomory.
 Modelización Matemática
 Un objeto M es un modelo de una realidad R para un observador O, si O puede obtener estudiando M las
respuestas a las preguntas que se hace sobre R.

 Así, una misma realidad puede ser representada por diferentes modelos, en función de las preguntas que nos
hagamos acerca de ésta.

Simplificación
Modelo
de la realidad
 Modelización Matemática
El modelo es la parte más
importante a la hora de resolver
un problema. Desde el punto de
vista científico, el estudio de un
sistema real debe cumplir el
siguiente círculo virtuoso
 UN PROBLEMA DE PRODUCCIÓN
Un carpintero desea determinar la cantidad de sillas y mesas que
debe producir el siguiente día para maximizar su ganancia.
Cuenta con 38 m2 de madera y dispone de 8 horas diarias para
trabajar.
Se requiere 4 m2 y 1 hora/hombre para confeccionar cada silla, y de
9.5 m2 de madera y 1 hora/hombre para confeccionar cada mesa.
Se supone que se vende todo lo que se produce y que el beneficio
por silla vendida es de $4, y por cada mesa de $8.5.
¿Cuántas sillas y mesas se debe producir?
 UN PROBLEMA DE PRODUCCIÓN
 Hacer el modelo matemático significa interpretar lo mejor posible
la realidad a través de abstracciones matemáticas.

 Por ejemplo, en el problema de producción planteado, podemos

definir la variable x1 que indicará el número de sillas y x2 el
número de mesas que se deberán producir.

 Veamos cómo se deben relacionar estas variables para cumplir

con las condiciones del problema:

 ¿Como ponemos en fórmulas matemáticas que la máxima

cantidad de madera que podemos usar es 38 m2 ?
 UN PROBLEMA DE PRODUCCIÓN
 ¿Cómo ponemos en fórmulas matemáticas que la máxima
cantidad de madera que podemos usar es 38 m2 ?
 
𝟒 𝒙 𝟏 +𝟗 .𝟓 𝒙 𝟐 ≤ 𝟑𝟖
 ¿Cómo expresamos que el máximo número de horas/hombre que
podemos usar es de 8?
 
𝒙𝟏 + 𝒙 𝟐 ≤ 𝟖
 ¿Cuál es la función de utilidad que tenemos que maximizar?

Max   𝒛 =𝟒 𝒙 𝟏 +𝟖 .𝟓 𝒙 𝟐
 
 UN PROBLEMA DE PRODUCCIÓN
Resumiendo: tenemos el modelo de optimización (veremos más
adelante qué es un modelo de programación lineal) que resuelve
este problema.

Max   𝒛 =𝟒 𝒙 𝟏 +𝟖 .𝟓 𝒙 𝟐
 

 
𝒔 .𝒕 . 𝟒 𝒙 𝟏+𝟗 . 𝟓 𝒙𝟐 ≤𝟑𝟖
 
𝒙𝟏 + 𝒙 𝟐 ≤ 𝟖
 
𝒙𝟏 ≥ 𝟎 , 𝒙 𝟐 ≥ 𝟎
UN PROBLEMA DE PRODUCCIÓN

 
𝟒 𝒙 𝟏 +𝟗 .𝟓 𝒙 𝟐=𝟑𝟖

 
𝒙𝟏 + 𝒙 𝟐=𝟖
CONSTRUCCIÓN & RESOLUCIÓN DE UN MODELO MATEMÁTICO

Modelización Construcción y elaboración del modelo:

Se dirá que se ha resuelto el modelo
Resolución cuando hayamos podido responder a
las preguntas que nos movieron a
formularlo.
Una vez obtenidos los resultados,
Explotación estos deben ser interpretados y
deben analizarse las implicaciones
para la gestión del sistema afectado.
 PROGRAMACIÓN MATEMÁTICA MODELO GENERAL

Un problema de programación matemática general puede expresarse

como:
 
𝑴 𝒊𝒏 ( 𝑴𝒂𝒙 ) : 𝒇 (𝒙 ) Función objetivo
𝒔 . 𝒂 .𝒉 (𝑿 )=𝟎
 

Restricciones del
 
𝒈( 𝑿 )≤ 𝟎 problema
𝒏
 
𝑿⊆𝕽 Variables continuas, discretas, binarias
CLASIFICACIÓN DE LOS PROBLEMAS DE PROGRAMACIÓN MATEMÁTICA

La forma de resolver los problemas de programación matemática depende de la estructura de

estos problemas. Se pueden clasificar en:
•PROBLEMAS DE PROGRAMACION LINEAL (LP)
•PROBLEMAS DE PROGRAMACION ENTERA MIXTA (MIP)
•PROBLEMAS NO LINEALES (Otros)

Problemas lineales (LP):

 𝑴𝒊𝒏( 𝑴𝒂𝒙 ): 𝒁=𝒄𝑻 𝒙 Función objetivo y restricciones lineales

𝒔 .𝒕 . 𝑨𝒙 ≤ 𝒃
 
Simplex (hasta 50,000 ecuaciones)
Métodos de
 
𝒙 ∈ 𝕽𝒏 solución Punto interior (50,000-100,000 ecuaciones)
CLASIFICACIÓN DE LOS PROBLEMAS DE PROGRAMACIÓN MATEMÁTICA

Problemas enteros mixtos (MIP):

Son aquellos problemas con la estructura de un problema de programación

lineal, pero con la característica de que algunas (o todas) las variables de
decisión deben tomar valores enteros.
Métodos de solución:

 Branch and Bound (Ramificación y acotamiento).

 Método de los planos de corte de Gomory.

 Heurísticas y metaheurísticas.

 Métodos basados en la teoría poliedral.

CLASIFICACIÓN DE LOS PROBLEMAS DE PROGRAMACIÓN MATEMÁTICA

Problemas no lineales:

Son aquellos problemas con características no lineales en su función objetivo o

en sus restricciones.

Métodos de solución:

 Metaheurísticas (Simulated annealing, Tabu Search,

 Algoritmos genéticos, GRASP, colonia de hormigas, etc)
 Descomposición de Benders generalizada
 Aproximación exterior (Outer approximation)
 Plano de corte generalizado
 Métodos basados en consideraciones lógicas.
Muchas gracias!!!!!!
y una vez más
Bienvenidos!!!!!!!!

M. Sc. Juan Carlos Zerna Torres