Fac
ulta
d de
Cie
ncia
s So
cial
es y
Jur
ídic
as
UNIVERSIDAD DE JAÉN Facultad de Ciencias Sociales y Jurídicas
Trabajo Fin de Grado
Resolución de Problemas de
Investigación
Operativa Mediante Diferentes
Softwares: Ventajas e
Inconvenientes
Alumno: Cristina Martínez Gómez
Junio, 2017
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 1
ABSTRACT
The study and development in Operations Research have allowed a great
advance in the business world, since its application facilitates the decision making,
considering the limited availability of resources.
This development has had a great boom thanks to the technological advances,
since it allows us to carry out its resolution faster and more secure. In addition, to
process a large amount of data, otherwise it would not be possible, or it would be very
tedious to get and obtain the solution.
In this work the theoretical knowledge acquired during the degree will be
developed, as well as new concepts in which they will be deepened, applied to computer
tools, such as R® or POM-QM®, which facilitate the resolution and development of a
wide variety of Operations Research problems, as well as an investigation of their
operation, evaluating possible advantages and disadvantages.
RESUMEN
El estudio y el desarrollo en la Investigación Operativa han permitido un gran
avance en el mundo empresarial, ya que su aplicación facilita la toma de decisiones,
considerando la disponibilidad limitada de recursos.
Este desarrollo ha tenido un gran auge gracias a los avances tecnológicos, ya que
permite llevar a cabo su resolución más rápida y segura. Además de procesar una gran
cantidad de datos, de forma que de otra manera no fuese posible, o fuese muy tedioso su
desarrollo y la obtención de la solución.
En este trabajo se desarrollarán los conocimientos teóricos adquiridos durante el
grado, así como nuevos conceptos en los que se profundizarán, aplicados a herramientas
informáticas, como R® o POM-QM®, las cuales pueden facilitar la resolución y el
desarrollo de una amplia variedad de problemas de Investigación Operativa, así como
una investigación de su funcionamiento, evaluando posibles ventajas e inconvenientes.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 2
ÍNDICE
Contenido 1. INTRODUCCIÓN ................................................................................................................ 3
2. PROGRAMACIÓN LINEAL................................................................................................ 4
2. 1. DEFINICIÓN DEL PROBLEMA .................................................................................. 4
2. 2. RESOLUCIÓN GRÁFICA ............................................................................................ 6
2. 3. MÉTODO SIMPLEX .................................................................................................... 9
2. 4. RESOLUCIÓN CON R® Y POM-QM® ..................................................................... 12
2. 4. PROBLEMAS AVANZADOS .................................................................................... 22
I) PROGRAMACIÓN POR METAS ...................................................................................... 22
3. PROGRAMACIÓN NO LINEAL ....................................................................................... 32
4. PROBLEMAS DE REDES ................................................................................................. 34
4. 1. PROBLEMA DEL TRANSPORTE ...................................................................................... 35
4. 2. PROBLEMAS DE ASIGNACIÓN ...................................................................................... 40
5. 3. ÁRBOL DE COSTE MÍNIMO ........................................................................................... 43
5. 4. ARBORESCENCIA DE COSTE MÍNIMO ........................................................................... 48
5. 5. ÁRBOL DEL CAMINO MÁS CORTO ................................................................................ 50
5. 6. PROBLEMA DE FLUJO MÁXIMO.................................................................................... 54
5. CONCLUSIÓN ................................................................................................................... 58
6. BIBLIOGRAFÍA ................................................................................................................ 59
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 3
1. INTRODUCCIÓN
El estudio de la optimización de la programación matemática es muy interesante
actualmente, debido a su gran versatilidad para la aplicación en el mundo empresarial.
El estudio de esta rama ha sido posible a lo largo del grado, en diferentes asignaturas, si
bien en algunas, con mayor profundidad.
No obstante, si consideramos objetivamente, el mundo tecnológico actual en el que
nos encontramos, el desarrollo de este ámbito se lleva en gran medida a través del uso
de herramientas informáticas. El conocimiento teórico de esta disciplina permite tener
los fundamentos básicos necesarios para un desarrollo e investigación de mayor
profundidad. Esta investigación puede verse facilitada con el uso de softwares
informáticos, además de poder avanzar a una gran velocidad en su desarrollo y
aplicación.
Además de contar con muchos tipos de programas informáticos desde hace años, el
incesante aumento del volumen de softwares hasta la actualidad, nos abre la posibilidad
de elegir entre una enorme variedad de herramientas informáticas, que nos ayudan a la
puesta en práctica de Investigación Operativa. Muchas de ellas se desarrollan para un
uso en concreto, de forma que sean específicas y abarquen dicho campo en su totalidad,
mientras que otras se desenvuelven de forma genérica para poder englobar diferentes
ámbitos. Considerando esta gran variedad de softwares, así como la incesante evolución
de ambas clases de programas, el uso de un conjunto de las herramientas informáticas,
nos puede llevar a la aplicación práctica completa de esta rama, sopesando las
desventajas o errores que puedan esconderse en ellas, con el uso de otras, y así poder
complementarse mutuamente.
De forma más concreta, a lo largo de su estudio en la Universidad, se ha
desarrollado su aplicación con el uso de hojas de cálculo Excel. Han sido de gran
utilidad, además de permitir que profundicemos en el aprendizaje de este software, son
muy usadas actualmente en el mundo laboral. Por todo ello, el mayor estudio e
investigación de las herramientas actuales puede ser muy interesante, ya que con el
conocimiento básico de algunas de ellas, podremos desarrollar muchos otros tipos de
problemas. Este puede ser el caso del software informático R® (The R Project for
Statistical Computing), el cual es muy usado en la actualidad, no solo en esta materia,
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 4
sino en una gran variedad ámbitos, estudios, investigaciones etc. que podremos
comprender si estudiamos los cimientos de esta herramienta.
Este proyecto se basará en el estudio e investigación de diferentes softwares
informáticos, que permitan aplicar y facilitar la resolución de diferentes problemas de
Investigación Operativa, como la programación lineal, y que su uso en conjunto, nos
permita eliminar las barreras que otros presenten, además de sustentarse en una
investigación más extensa y profunda desarrollada con el departamento de Estadística e
Investigación Operativa de la Universidad de Jaén durante el curso 2016 – 2017 basada
en el aprendizaje e investigación de estas herramientas.
2. PROGRAMACIÓN LINEAL
2. 1. DEFINICIÓN DEL PROBLEMA
El hecho de tener una serie de recursos limitados en el mundo empresarial hace
que una organización deba de plantearse cómo distribuir estos recursos de forma que se
puedan utilizar de manera óptima y conseguir así el máximo resultado que esta pueda
lograr, ya sea mediante una minimización del coste que pueda tener a partir de las
tareas, recursos, actividades etc. a desarrollar, o mediante la obtención del máximo
beneficio posible a través de su actividad principal o actividades secundarias que lleve a
cabo.
Este problema se empezó a desenvolver por varios grupos de científicos de
múltiples áreas a partir de la 2º Guerra Mundial con el pretexto de maximizar los
suministros y optimizando los recorridos para conseguir hacer los transportes con el
menor tiempo posible, pero evitando el riesgo existente por la presencia de submarinos
alemanes. Tras la 2º Guerra Mundial, la evolución de esta rama se ha visto muy
favorecida con la aparición de los ordenadores proporcionando la resolución de
problemas mucho más complejos y con una mayor rapidez de cálculo (Frías
Bustamante, M. P. y Martínez Rodríguez, A.M., 2006).
Un problema común al que se deben de enfrentar los gerentes de una empresa es
la toma de decisiones y la formulación de modelos para decidir cómo administrar los
recursos de los que disponen, anteriormente esto se basaba casi en su totalidad en la
intuición o en experiencias pasadas, siendo esta de gran utilidad, pero tenía el gran
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 5
inconveniente, en ocasiones, de falta de información de las distintas situaciones o
circunstancias en las que pudiera encontrarse la organización.
A lo largo del grado hemos visto cómo solucionar este problema a partir de una
perspectiva más objetiva utilizando un modelo simbólico, es decir, aplicando las
matemáticas para representar las relaciones existentes entre los distintos datos de
interés. En concreto nos basamos en modelos de decisión para mostrar diferentes
decisiones a través de variables. Nosotros no podemos decidir o elegir algunos datos o
hechos a los que se enfrenta una empresa, como por ejemplo podría ser el coste de sus
materias primas, pero sí que podemos decidir sobre la cantidad a comprar de cada tipo
de estas (Eppen, G.D., Gould, F.J., Schmidt, C.P., Moore, J.H., Weatherford, L.R.,
2000).
El estudio de la Investigación Operativa nos ha ayudado a poder modelar
situaciones empresariales complejas, aplicar técnicas para su resolución y comunicar de
forma efectiva los resultados obtenidos. Los modelos de decisión nos permiten describir
una situación, junto con las correspondientes variables, determinando cuál es su
influencia, los podremos utiliza para conseguir un objetivo en concreto.
La Investigación Operativa se sirve de muchas ramas como las Matemáticas, la
Estadística, la Probabilidad o la Economía para poder resolver modelos de optimización
o modelos de predicción. En especial, en el grado hemos centrado el estudio en los
modelos de optimización.
Hoy en día es más frecuente el uso de modelos de optimización para tomar
decisiones debido a la mayor comprensión de esta metodología en las diferentes ramas,
una mayor dificultad de los problemas que queremos resolver y la presencia y desarrollo
de nuevos algoritmos. Los modelos de Investigación Operativa deben de ser una
abstracción de la realidad, capaces de identificar los factores que son determinantes en
el comportamiento de nuestro sistema, de forma esquemática se resume en la Figura 2.1.
Es muy interesante la gran variedad de ámbitos que hemos podido encontrar
investigando dónde se aplica la Investigación Operativa, aparte de logística empresarial,
suministro de agua, sector bancario, servicio de correos…, se ha llegado a plantear
incluso para el sector sanitario, por ejemplo, como cuestiona el profesor Andrés Ramos
de la Universidad Pontificia Comillas de Madrid: “si tuviéramos que llevar a cabo un
tratamiento de cáncer de cerebro, ¿Dónde se debería de aplicar radioterapia para
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 6
maximizar el impacto en las células cancerígenas y minimizar el daño en otras
células?”. Otro ejemplo podría ser su aplicación al ámbito agropecuario (Céspedes, N.,
2007). Podemos observar que tener un conocimiento avanzado de esta materia y su
mayor indagación nos abre un amplio abanico de soluciones a diversas cuestiones.
Figura 2.1: Identificación de factores
Fuente: http://www.investigaciondeoperaciones.net
2. 2. RESOLUCIÓN GRÁFICA
La búsqueda del punto óptimo se puede llevar a cabo mediante muchos métodos.
Sabemos que se basa en calcular una zona factible, es decir, esa región donde todos los
puntos que incluye cumplen con las restricciones y posteriormente buscamos de estos
puntos cual es el que optimiza la función objetivo.
Aparte de las resoluciones teóricas, así como las investigadas en este proyecto con el
empleo de herramientas informáticas, en muchas ocasiones puede ser de gran utilidad su
MODELO
SITUACIÓN DECISIONES
RESULTADOS
ANÁLISIS
CONOCIMIENTO
PREVIO
AB
ST
RA
CC
IÓN
INT
ER
PR
ET
AC
IÓN
JUICIO EJECUTIVO
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 7
representación gráfica, ya que podremos ver cuál es esta región factible y nos ayudará a
su mejor entendimiento.
Cuando tratamos ejercicios de dos variables, POM-QM® nos muestra directamente
su región factible y su punto óptimo, no obstante, sería interesante mostrar la resolución
de un ejercicio que contenga tres variables, es decir, hacer un gráfica en 3D. Para ello
hemos necesitado buscar otro software informático que nos permita realizar esta función
y por tanto su estudio.
Nos centramos en la representación gráfica de tres variables mediante el software
informático Mathematica®. A lo largo del grado, hemos utilizado en alguna ocasión este
programa, no obstante, no hemos podido aplicarlo a la representación gráfica de
regiones factibles que es nuestro objetivo actual, por ello vamos a desarrollar un breve
estudio y aplicación para la realización de gráficas en 3D.
Utilizaremos para su desarrollo un ejemplo ilustrativo
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 7𝑥 + 3𝑦 + 3𝑧
Sujeto a:
60𝑥 + 25𝑦 + 20𝑧 ≤ 100.000
60𝑥 ≤ 1.000
𝑦 ≤ 1.000
𝑧 ≤ 1.500
En primer lugar, dibujaremos la región factible usando RegionPlot3D, es muy
importante escribir los argumentos en Mathematica® tal cual, ya que una mínima
variación en su escritura puede provocar que sea erróneo el resto del ejercicio. Con este
comando podremos introducir las restricciones para que dibuje la región factible el
software. Además deberemos de indicar entre qué valores oscilará las variables. Por
último, podremos usar PlotStyle dentro de esta función para que nos dibuje la región del
color que queramos y pueda observarse con claridad (Ipanaqué Chero, R. y Velesmoro
León, R., 2005).
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 8
Podemos ver que cada restricción se separa usando && y entre corchetes
indicaremos cada variable y entre que valores se encuentran, es decir, para la x se estará
entre 0 como mínimo y 1.100 como máximo. Una vez definidos los argumentos
obtendremos la región factible en 3D (Figura 2.2).
Figura 2.2: Región factible en Mathematica®
El objetivo es conocer el punto donde se maximiza la función objetivo, por
tanto, debemos de representar el plano de la función (Figura 2.3). Para ello deberemos
de usar la función ContourPlot3D” y al igual que antes también debemos especificar
entre qué valores se encontrarán las variables.
Figura 2.3: Función objetivo en Mathematica®
Una gran ventaja que nos ofrece Mathematica® en la representación de gráficas
3D es que son interactivas, quiere decir que podremos moverlas para poder ver la
gráfica desde distintas perspectivas en función de nuestra preferencia.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 9
Para poder ver con claridad el punto dónde se corta la región factible con la
función objetivo deberemos de representarlas a la vez juntas, para ello le pedimos al
software que nos muestre conjuntamente ambas usando Show incluyendo el nombre que
le hayamos asignado a cada una separadas entre una coma (Figura 2.4).
Figura 2.4: Representación punto óptimo
Si resolvemos este problema con R® o con POM-QM®, muestra que la solución
óptima se encuentra para 𝑥 = 750, 𝑦 = 1.000 𝑦 𝑧 = 1.500 punto donde podemos ver
que corta la representación de la función objetivo con la región factible.
2. 3. MÉTODO SIMPLEX
Durante el grado hemos estudiado estos problemas y como solucionarlos en
distintas materias, sobre todo, en Investigación Operativa nos centramos en cómo
plantear los modelos matemáticos cuyo objetivo es optimizar una función objetivo
lineal o función económica teniendo en cuenta que las variables tienen que verificar una
serie de restricciones (ecuaciones o inecuaciones lineales), incluyendo las restricciones
de no negatividad, es decir, hemos llevado a cabo el estudio de la programación lineal
que forma parte de la programación matemática o teoría de optimización (Martín
Martín, Q., 2003).
Definición
𝑀𝑎𝑥 𝑧 = 𝑐𝑇𝑋
s. a.
𝐴𝑋 ≤ 𝑏, 𝑋 ≥ 0
Siendo
𝑧: 𝑙𝑎 𝑓𝑢𝑛𝑐𝑖ó𝑛 𝑜𝑏𝑗𝑒𝑡𝑖𝑣𝑜
𝑐 = (𝑐1, … , 𝑐𝑛)𝑇: 𝑉𝑒𝑐𝑡𝑜𝑟 𝑑𝑒 𝑐𝑜𝑒𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑒𝑠 𝑑𝑒 𝑙𝑎 𝑓𝑢𝑛𝑐𝑖ó𝑛 𝑜𝑏𝑗𝑒𝑡𝑖𝑣𝑜.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 10
𝑋 = (𝑥1, … , 𝑥𝑛)𝑇: 𝑣𝑒𝑐𝑡𝑜𝑟 𝑑𝑒 𝑙𝑎𝑠 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠 𝑑𝑒 𝑑𝑒𝑐𝑖𝑠𝑖ó𝑛.
𝐴 = (… , 𝑎𝑖𝑗 , … ): 𝑚𝑎𝑡𝑟𝑖𝑧 𝑑𝑒 𝑐𝑜𝑒𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑒𝑠 𝑡é𝑐𝑛𝑖𝑐𝑜𝑠 (𝑖 = 1, 2, … , 𝑚; 𝑗 = 1, 2, … , 𝑛).
𝑏 = (𝑏1, … , 𝑏𝑚)𝑇: 𝑣𝑒𝑐𝑡𝑜𝑟 𝑑𝑒 𝑑𝑒𝑚𝑎𝑛𝑑𝑎𝑠 (𝑟𝑒𝑐𝑢𝑟𝑠𝑜𝑠).
El conjunto de soluciones factibles de un problema de programación lineal viene dado
por:
𝑋 = {𝑥 ∈ 𝑅𝑛 / 𝐴𝑥 ≤ 𝑏 , 𝑥 ≥ 0 }
Podemos obtener todas las soluciones básicas factibles y evaluar el objetivo en
ellas, pero en la mayoría de los casos resulta complejo, y es necesario dedicarle mucho
tiempo para obtener la solución óptima, por ello, hemos utilizado una herramienta
desarrolla por G.B. Dantzing en 1951 llamada el método del Simplex. Este algoritmo
nos permite a partir de una solución básica factible inicial llegar hasta la solución
óptima del problema, así como las soluciones alternativas del problema en caso de que
existan.
Es curioso un hecho real en la vida de Dantzing, cuando aún solo era un
estudiante llegó un día tarde a clase y observó en la pizarra dos problemas estadísticos
que no tenía solución aún. Dantzing pensó que se trataban de ejercicios para casa, y tras
el día de clase, los intentó hacer como cualquiera otro de sus deberes, si bien se
percataba de que eran algo más complejos de lo normal, obtuvo solución para ambos y
se los mostro a su profesor. Un tiempo después su profesor le visitó dándole la noticia
de que publicaría una de sus soluciones en una revista. Esta historia nos sirve de
ejemplo motivador y nos muestra la fuerza del pensamiento positivo (Morales Medina
M.A., 2006).
El Método del Simplex lo hemos desarrollado con la ayuda de la denominada
tabla del Simplex que nos facilita la introducción y la conglomeración de una serie de
datos simplificando la utilización del cálculo manual y el análisis de sensibilidad.
Posteriormente estudiamos la asociación existente entre los problemas primales, es
decir, de los problemas de programación lineal, a los problemas duales, y como obtener
la solución dual a partir del problema primal o viceversa, ya que a cada problema primal
de maximización (o minimización) se le asocia un problema de programación lineal de
minimización (o de maximización) con varias propiedades.
Definición
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 11
𝑃𝑟𝑖𝑚𝑎𝑙 𝐷𝑢𝑎𝑙
𝑀𝑎𝑥 𝑧 = 𝑐𝑇 𝑋 𝑀𝑖𝑛 𝑧 = 𝑌𝑇𝑏
𝑠. 𝑎. s. a.
𝐴𝑋 ≤ 𝑏 𝐴𝑇𝑌 ≥ 𝑐
𝑋 ≥ 0 𝑌 ≥ 0
Se obtiene que,
𝐴𝑚𝑥𝑛 → 𝐴𝑇𝑛𝑥𝑚
De donde se observa que hay tantas variables en el problema dual como restricciones en
el primal y tantas restricciones en el dual como variables hay en el primal.
El sentido de las desigualdades del problema dual (≤) viene determinado por las
restricciones de no negatividad, X ≥ 0, del problema primal.
La solución de ambos problemas está relacionada, o ninguno de ellos tiene
solución (puede ser por diferentes motivos), o en caso de que tengan solución, los
valores óptimos coincidirán y aplicando el método simplex a cualquiera de los dos
problemas obtendremos la solución de ambos, es decir, con aplicar el método en uno de
los dos es suficiente, ya que así obtendremos la solución (Guerrero Salas, H., 2009).
Debido al escaso tiempo que tenemos para estudiar esta rama, la resolución de
los problemas de decisión mediante herramientas informáticas solo lo hemos podido
desarrollar brevemente a través de hojas de cálculo electrónicas de Excel con el uso de
Solve. Esta herramienta es sencilla de usar y fiable pero aumenta su dificultad si
nuestros problemas son más complejos y queremos usar un mayor número de datos.
Hay una gran variedad de softwares informáticos que podríamos usar y que ofrecen una
gran estabilidad como puede ser el caso del R® u otros que destacan por su fácil
comprensión y un uso intuitivo, por el ejemplo, el POM-QM®. Ambos programas son
potentes herramientas de trabajo que su uso podría facilitarnos la realización de los
problemas y darnos mucha información en determinadas situaciones, por ello considero
la importancia de profundizar en el estudio e investigación de estas herramientas,
además de aquellos softwares complementarios a los anteriores, ya que si bien estos
tienen ciertas desventajas, podrían compensarse y obtener así una información
completa, a través el conocimiento y utilización de un amplio abanico de softwares.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 12
2. 4. RESOLUCIÓN CON R® Y POM-QM®
Uno de los principales motivos para llevar a cabo una investigación y estudio del
software informático R® ha sido la libre disposición para su uso, a diferencia de la
mayoría de los programas, esto supone una gran ventaja ya que cualquier problema
resuelto a través de esta herramienta podrá ser visto por cualquier otra persona al no
tener dificultades para obtener el software y poder ejecutar así el correspondiente script.
R® es un programa muy versátil que permite resolver una enorme variedad de
problemas no solo desde el punto de vista de la Investigación Operativa, sino además
desde el punto de vista de la Estadística, la Econometría… un conocimiento de
programación básico con R® permite que posteriormente se pueda interpretar y entender
con un escaso esfuerzo su metodología. Esto ha dado lugar a un gran uso y una eleva
importancia en muchos ámbitos en la actualidad.
POM-QM® a pesar de no ser un software de libre uso y necesitar licencia para
poder usarlo, la Universidad de Jaén tiene licencia como software virtualizado y
podemos acceder a él desde la página web. La principal ventaja de este software es su
fácil uso ya que a partir de unas simples indicaciones, el programa nos pide los datos
necesarios de forma muy concreta y ofrece una rápida solución, además de información
complementaria en muchas ocasiones (análisis de sensibilidad, soluciones alternativas,
gráficas de dos variables…).
A pesar de la mayor complejidad de R®, nos encontramos con un programa
mucho más estable que nos permitirá resolver una gran cantidad de problemas gracias a
la variedad de paquetes que contiene, destinados a muchos y diferentes ámbitos.
Además se trata de un software gratuito y con código fuente de libre acceso.
Es un programa que está orientado a objetos, es decir, a partir de una consola
introduciremos código asociado a estos, los cuales se refieren a variables, datos,
funciones o resultados. La información que contiene R® está estructurada en paquetes y
según nuestro objetivo podremos utilizar el más conveniente.
Para descargar paquetes lo podremos hacer desde R®, en la opción de instalar
paquetes, pero además cada vez que queramos usar un paquete deberemos de cargarlo
cliqueando en la interfaz “paquetes/ cargar paquetes” y seleccionamos el paquete que
se quiera ejecutar. Todo esto también lo podemos hacer a través de líneas de comando,
para instalar un paquete usaremos install.packages(“nombre del paquete”) y para
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 13
cagarlo utilizaremos la instrucción library(nombre paquete), por ejemplo, si se quiere
descargar y cargar el paquete lpSolve se utiliza el siguiente script:
A través de la página web https://www.r-project.org/ hay una sección llamada
“Packages”, podremos acceder a una tabla con los paquetes disponibles ordenados
según la fecha de publicación o por nombre. Esta página es muy útil ya que cliqueando
en cualquiera de los paquetes podremos acceder a un pdf donde explica todas las
funciones que cada uno abarca, la bibliografía de estos paquetes y sus autores.
Además también tenemos a nuestra disposición otra página de ayuda,
http://rseek.org/, siendo un buscador de R® mediante el cual podremos encontrar todos
los paquetes relacionados buscando sobre un tema específico.
Resolución con R®
Para la aplicación en R® utilizaremos el paquete lpSolve para dar solución a la
programación lineal entera, continua o mixta, donde se encuentra la función lp que se
trata de una función para la resolución de problemas de programación lineal y entera
Función:
lp (direction = "min", objective.in, const.mat,
const.dir, const.rhs,
compute.sens=0,
all.int=FALSE)
Argumentos de la función lp:
direction: indica la dirección de optimización "min" (defecto) o "max" .
objective.in: es un vector numérico formado por los coeficientes de la función
objetivo.
const.mat: matriz compuesta por los coeficientes de las restricciones, cada fila es una
restricción y cada columna una variable.
const.dir: es un vector de caracteres que indica las direcciones de las restricciones,
cada valor debe ser "<", "≤", "=", ">", o "≥".
const.rhs: vector de valores numéricos para los lados derechos de las restricciones.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 14
compute.sens: es un valor numérico que indica si se desea hacer análisis de
sensibilidad: por defecto 0 (no); cualquier valor no nulo (sí).
all.int: respuesta a la pregunta ¿son todas las variables enteras? Por defecto es
FALSE. Para problemas de programación lineal enteros hay que escribir all.int =
TRUE.
Salidas de la función lp
$direction: dirección de optimización del problema (0 = minimizar, 1 = maximizar).
$x.count: número de variables en la función objetivo.
$objective: vector con los coeficientes de la función objetivo.
$const.count: número de restricciones.
$constraints: matriz de tasas de uso.
$int.count: número de variables enteras.
$int.vec: vector con los índices de las variables enteras.
$objval: valor óptimo de la función objetivo.
$solution: vector con los valores óptimos de las variables de decisión.
$compute.sens: proporciona el valor numérico a la pregunta ¿calculo sensibilidad?
que se dio en la llamada a la función. Si es un valor distinto de cero, el objeto contiene
los resultados del análisis de sensibilidad.
$sens.coef.from: proporciona los límites inferiores de los intervalos de variación
de los coeficientes de la función objetivo, para que la solución proporcionada siga
siendo óptima.
$sens.coef.to: proporciona los límites superiores de los intervalos de variación de
los coeficientes de la función objetivo, para que la solución obtenida siga siendo óptima.
$duals: Proporciona los valores de los costos reducidos en la tabla óptima del
Simplex.
$duals.from: proporciona los límites inferiores de los intervalos de variación de los
coeficientes de la función objetivo del problema dual (o equivalentemente, de los
recursos del problema primal), para que la solución proporcionada siga siendo óptima.
$duals.to: proporciona los límites superiores de los intervalos de variación de los
coeficientes de la función objetivo del problema dual (o equivalentemente, de los
recursos del problema primal), para que la solución proporcionada siga siendo óptima.
$status: número que indica: 0= éxito, 2=solución no factible, 3=solución no acotada.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 15
Aplicación práctica
A ejemplo ilustrativo hemos utilizado el siguiente problema propuesto por S.
Hillier, F., y J. Lieberman, G. (2010).
PROTRAC, INC.
“PROTRAC, Inc. Produce dos líneas de maquinaria pesada. Una de sus líneas
de productos, llamada equipo de excavación, se utiliza de manera primordial en
aplicaciones de construcción. La otra línea, denominada equipo para la silvicultura,
está destinada a la industria maderera. Tanto la máquina más grande de la línea del
equipo de excavación (la E-9), como la mayor de toda la línea de equipo para la
silvicultura (la F-9), son fabricadas en los mismos departamentos y con el mismo
equipo. Empleando las proyecciones económicas correspondientes al siguiente mes, el
gerente de mercadotecnia de PROTRAC ha considerado que durante ese periodo será
posible vender todas las E-9 y F-9 que la compañía sea capaz de producir. La gerencia
tiene que recomendar ahora una meta de producción para el mes próximo. Es decir,
¿Cuántas E-9 y F-9 deberás fabricar si la dirección de PROTRAC desea maximizar la
contribución del mes entrante a las ganancias (es decir, el margen de contribución,
definido como los ingresos menos los costos variables)?.
La toma de esta decisión requiere la consideración de los siguientes factores
importantes:
El margen de contribución unitaria de PROTRAC es de 5.000€ por cada E-9
vendida y 4.000€ por cada F-9.
Cada producto pasa por las operaciones de maquinado, tanto en el departamento A
como en el B.
Para la producción correspondiente al mes próximo, estos dos departamentos
tienen tiempos disponibles de 150 y 160 horas, respectivamente. La fabricación de cada
E-9 requiere 10 horas de maquinado en el departamento A y 20 horas en el
departamento B, mientras que la de cada F-9 requiere 15 horas en el departamento A y
10 en el B.
Para que la administración cumpla un acuerdo concertado con el sindicato, las
horas totales de trabajo invertidas en la prueba de productos terminados del siguiente
mes no deben ser mas allá del 10% inferior a una meta convenida de 150 horas. Estas
pruebas se llevan a cabo en un tercer departamento y no tienen nada que ver con las
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 16
actividades de los departamentos A y B. Cada E-9 es sometida a pruebas durante 30
horas y cada F-9 durante 10. Dado que el 10% de 150 es 15, las horas destinadas a las
pruebas no pueden ser menores que 135.
Con el fin de mantener su posición actual en el mercado, la alta gerencia ha
decretado como política operativa que: deberá construirse cuando menos una F-9 por
cada tres E-9 que sean fabricadas.
Uno de los principales distribuidores ha ordenado un total de cuando menos cinco E-9
y F-9 (en cualquier combinación) para el próximo mes, por lo cual tendrá que
producirse al menos esa cantidad.
A partir de estas consideraciones, el problema de la gerencia es decidir cuantas E-9 y
F-9 fabricará el próximo mes. En términos de modelos, la gerencia intenta determinar
la mezcla de productos óptima, también llamada plan de producción óptimo.
Definiremos en primer lugar nuestras variables de la siguiente forma:
x1= Unidades de E-9
x2= Unidades de F-9
Por tanto el planteamiento de nuestro problema es:
Función objetivo”
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 5.000𝑥1 + 4.000𝑥2
Sujeto a:
10𝑥1 + 15𝑥2 ≤ 150 𝑃𝑎𝑟𝑎 𝑒𝑙 𝑑𝑒𝑝𝑎𝑟𝑡𝑎𝑚𝑒𝑛𝑡𝑜 𝐴
20𝑥1 + 10𝑥2 ≤ 160 𝑃𝑎𝑟𝑎 𝑒𝑙 𝑑𝑒𝑝𝑎𝑟𝑡𝑎𝑚𝑒𝑛𝑡𝑜 𝐵
30𝑥1 + 10𝑥2 ≥ 135
𝑥1 ≤ 3𝑥2
𝑥1 + 𝑥2 ≥ 5
𝑥1, 𝑥2 ≥ 0
Comenzamos con la instalación del paquete utilizando el comando
install.packages(“lpSolve”) y lo cargaremos con library(lpSolve).
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 17
A continuación introducimos la función objetivo mediante un vector y las
restricciones del ejercicio utilizando una matriz, podemos introducir los datos por
columnas o por filas, aplicado al ejercicio práctico se obtiene que,
La dirección y las disponibilidades de cada una de las restricciones se podrán
hacer mediante vectores. Tanto el orden para introducir las direcciones, como las
disponibilidades, se harán al igual que el orden de las restricciones que se hayan
introducido antes mediante la matriz.
Para nombrar a las disponibilidades suele utilizarse en muchos casos rhs, esto
quiere decir: “right hand side” que significa “a mano derecha”, ya que son los valores
que se encuentran a la derecha de la restricción.
Ejecutamos la función una vez que se han introducido los argumentos definidos
anteriormente.
Todos estos argumentos son fáciles de recordar ya que a medida que escribamos
el principio de su nombre, R® nos mostrará una serie de sugerencias de posibles
opciones que puedan ser, basándose en las primeras letras que hemos escrito de nuestra
palabra.
Para ver de forma práctica las salidas de esta función, podemos usar $solution.
R® nos dará el valor de las variables, en el ejercicio práctico, se obtiene fabricar 4’5
máquinas de E-9 y 7 de F-9. Si queremos saber el valor de la función objetivo lo
obtendremos con $objval, se observa por tanto un valor de 50.500€.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 18
No obstante, podríamos plantearnos la siguiente pregunta: ¿Cómo se puede
producir 4’5 máquinas? Esto es difícil de cumplirlo en la vida real, pero esto podremos
solucionarlo con el siguiente argumento en la función lp.
Indicando all.int = TRUE conseguimos que R® nos muestre valores enteros para las
variables y al mostrarnos la resolución comprobamos que ahora sería fabricar 5 E-9 y 6
F-9 con un valor para la función objetivo de 49.000€. Aunque el valor sea menor, un
empresario debe de considerar valores que sean de utilidad, y a pesar de que la solución
óptima es 4’5 máquinas debemos de considerar producir 5, ya que aunque no sea la
óptima, sigue siendo factible y tiene una mayor utilidad al poder aplicarla en la vida
real.
R® no muestra directamente el precio sombra, pero podemos obtener a través del
comando $duals que proporciona el valor de los costos reducidos en la tabla óptima del
simplex. También podemos calcular los límites inferiores y superiores de los
coeficientes de nuestras variables de la función objetivo para que nuestra solución siga
siendo óptima mediante $sens.coef.from (límite inferior) $sens.coef.to (límite superior).
Es decir, la solución no variará mientras que el coeficiente de x1, que
actualmente tiene el valor de 4.000, se encuentre entre (2.666’66 - 8.000) y el
coeficiente de x2, con valor 5.000, se encuentre entre (2.500 - 7.500).
Otras salidas que podemos obtener de R® anteriormente comentadas,
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 19
Resolución con POM-QM®
Llevaremos a cabo también su resolución con POM-QM®, analizando su
resultado y la información que nos ofrece. En primer lugar debemos de indicarle que
vamos a resolver un problema de programación lineal, ya que POM-QM® nos permite
seleccionar el tipo de ejercicio que vamos a resolver (problemas de asignación,
problemas de transporte, teoría de juegos, programación mixta, problemas de redes…)
Una vez que abrimos el módulo de programación lineal, crearemos una nueva
hoja en la cual debemos de indicar a la izquierda el número de restricciones del
problema, el número de variables, y si queremos maximizar o minimizar. A la derecha
podemos elegir el nombre de cada fila y columna, aunque posteriormente esto se puede
modificar, y además nos explica que no es necesario incluir las restricciones de no
negatividad en “oveview”, como se observa en la Figura 2.5.
Figura 2.5: Creación de datos para programación lineal en POM QM®
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 20
Ofrece una tabla del simplex donde de forma sencilla e intuitiva podemos incluir
la información necesaria sobre las restricciones y de la función objetivo para que nos
pueda resolver nuestro problema. En la primera fila indicaremos el nombre de las
variables y debajo sus correspondientes coeficientes mostrando en la última columna la
función objetivo que se quiere maximizar, en nuestro caso: 𝑀𝑎𝑥 5000𝐸 − 9 +
4000𝐹 − 9. En el resto de las filas se apuntarán las restricciones a las que está sujeta la
función objetivo, sin ser necesario que se incluyan las restricciones de no negatividad.
Una vez introducidos los datos podremos darle a Solve para que nos muestre la solución
(Figura 2.6).
Figura 2.6: Datos de PROTRAC en POM-QM®
En la última fila de la tabla aparecerá la solución en azul, dando el valor de cada
variable y el valor de la función objetivo, en nuestro caso tendríamos que producir 4’5
máquinas de E-9 y 7 de F-9, consiguiendo un beneficio de 50.500€.
En la última columna calcula los precios sombra, con los cuales podremos saber
cuánto aumentaría el beneficio si tuviésemos una unidad más disponible para esa
restricción (Figura 2.7).
Podemos observar que si se dispusiese de una hora más para el departamento A,
es decir, un total de 151 horas, el beneficio de 50.500€ aumentaría en 150€,
consiguiendo que sea de 50.650€.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 21
Figura 2.7: Solución PROTRAC en POM-QM®
Además POM-QM® proporciona la correspondiente gráfica de forma directa,
siempre que nuestro problema trate dos variables. Aparece coloreada la región factible
señalando con un círculo la esquina en la que se maximiza la función, pero también
podemos saber el valor de cada variable y de la función objetivo en cada punto de corte
en la tabla que nos ofrece a la derecha, por ejemplo, en el punto (1’5 - 9) Z sería igual a
43.500€ o en el punto (6’8571 – 2’2857) se consigue un valor de 43.428’57€ (ver figura
2.8).
Figura 2.8: Gráfica PROTRAC en POM-QM®
Por último, muestra también una tabla donde indica el valor de cada variable que
se ha introducido e indicado inicialmente, el coeficiente de cada una de ellas y los
valores entre los que puede oscilar cada uno de los coeficientes para que la solución no
varíe. En el ejercicio en concreto E-9 deberá de estar entre (2.666’66-8.000) y F-9 entre
(2500-7500) (Figura 2.9).
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 22
Figura 2.9: Análisis de PROTRAC en POM-QM®
Podemos observar que, de forma muy rápida y sencilla, se obtiene el resultado,
además de un análisis de la solución.
2. 4. PROBLEMAS AVANZADOS
I) PROGRAMACIÓN POR METAS
La mayoría de las situaciones reales se caracterizan por metas y objetivos
múltiples más que por un único objetivo. Las metas pueden ser compatibles, pero muy a
menudo son conflictivas entre ellas, es decir, conseguir alguna es contrario a la
consecución de otra. Para resolver este problema podemos utilizar la programación por
metas.
Como ya hemos estudiado en Investigación Operativa, buscamos minimizar las
desviaciones de nuestras metas y nos podemos enfrentar a diferentes tipos de
situaciones: que se alcance la meta, por tanto no tendrá valor las desviaciones, que se
quede por debajo de la meta, por tanto tendremos una desviación negativa o que nos
quedemos por encima con una desviación positiva.
La programación por metas fue introducida a partir del 1950 por Charnes y
Cooper, la cual se desarrollaría a partir de 1970. Actualmente se usa en campos como el
de la economía, industrial, agricultura, medioambiental etc. (Chavez Quisbert, N.,
2011).
Podemos diferenciar entre dos tipos de restricciones: las restricciones duras que
requieren ser cumplidas de forma estricta, y las restricciones blandas que pueden
admitir desvíos a la meta establecida.
Definición
𝑃𝑜𝑠𝑖𝑏𝑙𝑒𝑠 𝑓𝑜𝑟𝑚𝑎𝑠 𝑖𝑛𝑖𝑐𝑖𝑎𝑙𝑒𝑠 𝑑𝑒 𝑢𝑛𝑎 𝑚𝑒𝑡𝑎
𝑓𝑖(𝑥) ≥ 𝑡𝑖 𝑓𝑖 (𝑥) ≤ 𝑡𝑖 𝑓𝑖(𝑥) = 𝑡𝑖
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 23
𝑀𝑒𝑡𝑎 𝑡𝑟𝑎𝑛𝑠𝑓𝑜𝑟𝑚𝑎𝑑𝑎
𝑓𝑖(𝑥) + 𝑛𝑖 − 𝑝𝑖 = 𝑡𝑖
𝑉𝑎𝑟𝑖𝑎𝑏𝑙𝑒 𝑑𝑒 𝑑𝑒𝑐𝑖𝑠𝑖ó𝑛 𝑛𝑜 𝑑𝑒𝑠𝑒𝑎𝑑𝑎 (𝑎 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟)
𝑛𝑖 𝑝𝑖 𝑛𝑖 + 𝑝𝑖
Dónde:
𝑓𝑖(𝑥) es una función del vector x de las variables de decisión,
𝑡𝑖 el nivel de aspiración asociado a dicho atributo,
𝑛𝑖 y 𝑝𝑖 son las variables de desviación negativa y positiva, respectivamente.
La desviación negativa cuantifica la falta de una meta con respecto al nivel al
que se aspira, mientras que la desviación positiva cuantifica la cantidad sobrepasada con
respecto a la cantidad buscada. Por tanto se buscará aquella solución más cercana a las
metas que se aspira.
Resolución con R®
En este caso, para la resolución de la programación por metas, R® cuenta con un
paquete específico, llamado goalprog. Este se puede descargar y cargar como hemos
explicado en apartados anteriores. Dentro de este se encuentra la función llgp que
permite resolver un problema de programación de objetivos lineales lexicográficos
(LLGP) usando el algoritmo simplex primario modificado.
Función
llgp(coefficients, targets, achievements,)
Argumentos de la función llgp
Coefficients: una matriz de coeficientes para las funciones objetivo lineales.
Targets: Un vector de valores meta para las funciones objetivo.
Achievements: un marco de datos con las variables de desviación para cada objetivo
junto con el nivel de prioridad.
Salidas de la función llgp
$out: salida de la función llgp obteniendo;
Decision variables: valor de las variables de decisión.
Summary of objectives : valor de las metas para el valor obtenido de las variables
de decisión. Con el nombre de Objective. también proporciona cuánto se ha superado
del valor deseado (Over), en cuanto se ha quedado por debajo (Under) y el valor que
se deseaba (Target).
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 24
Achievement function: valor de las desviaciones a minimizar. Cero indicarán que
se ha conseguido el objetivo o meta y si son positivas que no se ha alcanzado el objetivo
o meta.
Aplicación práctica
Utilizamos un ejemplo ilustrativo para investigar el desarrollo de este tipo de
problemas a partir de softwares informáticos.
1. 20𝑥1 + 15𝑥2 + 25𝑥3 ≥ 100
2. 6𝑥1 + 4𝑥2 + 11𝑥3 = 50
3. 8𝑥1 + 7𝑥2 + 5𝑥3 ≥ 75
Comenzaremos indicando a R® los datos del problema en particular, igual que
hemos podido hacer para la programación lineal, pero en este caso en vez de tener
restricciones, consideramos metas que habrá que introducir a partir de una matriz
quedando la siguiente expresión,
Lo siguiente que se debe indicar es el valor de las disponibilidades, es decir, en
este caso el valor que se quiere que alcancen las metas, nuevamente se podrá indicar
usando un vector,
La dirección de las metas no se podrá indicar como antes, ya que vamos a
utilizar lo que en R® se llama data.frame() para agrupar datos de distinto tipo pero que
deben de tener la misma longitud, es decir, podemos crear bases de datos. En primer
lugar tendremos que enumerar las metas, es decir, los objetivos, usando el comando
objective indicamos el número de metas, en nuestro caso son tres. En segundo lugar,
indicamos la prioridad que tienen cada una usando priority, y también con un vector, en
concreto, la prioridad es por el orden de las metas escritas.
Podemos ver que las metas pueden ser “≥”, “≤” o “=”, para reflejarlo en
data.frame está formado por dos partes. Utilizando p=() y n=() introducimos las
desviaciones positivas y negativas que queremos minimizar, así le daremos valor a la n
cuando queramos que sea ≥ y se hará asignándole el valor 1, en caso de que sea ≤
tendremos que indicar en el orden que le corresponde, 0 para n y 1 para p. En este caso,
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 25
también podemos ver, que una de nuestras metas es = por tanto deberemos de darle
valor 1 a ambos.
Con esto sería suficiente para seguir calculando las metas, pero data.frame nos
permite que podamos introducir los datos de las metas indicando el nombre de cada una
de ellas, es decir, si primera meta es del beneficio, la segunda de trabajadores y la
tercera del beneficio del año siguiente, podemos utilizar el siguiente comando para
obtener esta base de datos que podrá ser mejor comprendida visualmente (Figura 2.10).
Figura 2.10: Vista objetos nombrados en R®
Es muy importante tener en cuenta, que aparte de que podemos crear objetos con
el nombre que queramos, los comandos que R® tiene y que debemos de definir cuando
sean apropiados, deben de ser escritos tal y como R® los recoge, ya que en caso
contrario no registrará adecuadamente los datos.
Pasamos a resolver el ejercicio con la función llgp, indicamos los argumentos
que nos pide; coefficients donde se indican las metas que se habían introducido con la
matriz, targets para indicar las disponibilidades y achievements donde se introduce el
data.frame.
Pedimos que muestre la solución con el comando Ejercicio$out y en este caso
obtenemos bastantes datos que vamos a analizar en detalle
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 26
En la primera parte Decisión variables observamos la solución óptima, en este
caso tenemos que x1= 5, x2= 5 y x3= 0. En el siguiente apartado Summary of objectives
muestra primero el objetivo que conseguimos con cada meta, y en las siguiente
columnas la cantidad que hemos quedado por abajo, por arriba y la meta que estábamos
buscando, es decir, de la primera meta que era: 20𝑥1 + 15𝑥2 + 25𝑥3 ≥ 100,
conseguimos que tenga un valor de 175 usando el valor de las variables que hemos
obtenido, es decir tenemos una cantidad de 75 euros por encima de la que se buscaba
inicialmente. Pero esto es correcto, ya que la meta era conseguir 100 euros o más
cantidad.
En el segundo caso la meta era: 6𝑥1 + 4𝑥2 + 11𝑥3 = 50, conseguimos
exactamente el valor de 50 en este caso, por tanto para “over” y “under” nos muestran
un valor de 0, logramos así que nuestra meta se cumpla ya que se buscaba exactamente
el valor de 50 trabajadores.
Por último, teníamos que 8𝑥1 + 7𝑥2 + 5𝑥3 ≥ 75, se obtiene 75 exactos para
esta meta como podemos ver, por tanto se cumplen las tres metas que teníamos para este
problema con la solución que nos ha ofrecido R®.
Hemos resuelto un ejercicio con tres metas según la prioridad que nos ha
indicado el ejercicio, no obstante, también podemos encontrarnos con algún caso en que
en vez de seguir un orden de prioridades, nos indiquen que alguna meta es más
importante que las demás según una proporción que se indique, es decir, nos dan pesos
para las metas, por ejemplo.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 27
Si consideramos el ejercicio anterior suponiendo que la segunda meta es dos
veces más importante que la primera y la tercera cuatro veces más importante que la
primera su resolución en R® sería de forma diferente.
Inicialmente indicaremos los datos como lo hemos hecho con anterioridad hasta
tener que definir data.frame donde introducimos las prioridades, en este caso por
igual,es decir, dándole a cada meta la prioridad de 1, para luego poder indicar cada uno
de nuestros pesos de cada meta utilizando el comando w o weights como vector.
Comprobamos que los datos introducidos de los objetos son los buscados
visualizando el cuadro de contenidos que nos ofrece R® (Figura 2.11).
Figura 2.11: Tabla objetos introducidos en R®
Esta supone la única modificación que deberíamos de hacer para optimizar
nuestros pesos, ya que la restante parte de la función necesaria es la mismo que se ha
usado anteriormente para calcular las metas y su consiguiente cumplimiento, que en este
caso se consigue con los valores para las variables de: x1=0, x2=1’0088, x3=8’7719.
Estos ejemplos anteriores se tratan de ejercicios con metas flexibles, sin
embargo, también podemos encontrarnos con ejercicios en los cuales es necesario que
se cumplan de forma obligatoria una serie de restricciones que por tanto serán llamadas
restricciones rígidas. Su resolución con R® es muy similar a la anterior y jugaremos con
el vector de prioridades para indicar las restricciones que son rígidas.
Aplicación práctica
Rígidas
𝑥1 + 𝑥2 + 𝑥3 ≤ 55
𝑥3 ≥ 10
Flexibles
0′05𝑥1 + 0′02 𝑥3 ≥ 0′15
0′03𝑥2 + 0′02𝑥3 ≥ 0′1
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 28
Es importante tener en cuenta el tipo de restricción en el momento de definir el
data.frame. Para aquellas que se traten de rígidas tendrán todas la prioridad 1 ya que
son las que deberán de cumplirse en primer lugar, para el resto de restricciones flexibles
se le asignará según el orden de prioridad que tengan, es decir, si tenemos dos
restricciones rígidas se le indica a cada una la prioridad 1, y las otras dos flexibles se les
asignará según su prioridad, en este caso la restricción: 0′05𝑥1 + 0′02 𝑥3 ≥ 0′15
tendrá la prioridad 2 y la restricción: 0’03𝑥2 + 0’02𝑥3 ≥ 0’1 tendrá la prioridad 3.
Para terminar con la resolución de este problema se llevará a cabo como los
anteriores obteniendo así el resultado y determinando el cumplimiento o no de las
restricciones
Conseguimos que se cumplan las cuatro restricciones con un valor para las
variables de x1=0, x2=0, x3=10. La primera restricción quedará por debajo de la
disponibilidad en 45 unidades y la segunda se consigue el valor exacto de 10,
cumpliendo por tanto las dos restricciones rígidas que se necesitaban conseguir.
Además, las otras dos restricciones flexibles con las que contábamos también se
cumplen quedando la primera 0’05 y la segunda 0’1 unidades por encima de las
disponibilidades.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 29
Resolucion con POM-QM®
Este tipo de problemas también pueden solucionar con el software POM-QM®,
que hemos utilizado en otros ejemplos que como ya sabemos su uso suele ser más
sencillo e intuitivo. Empezamos en primer lugar con la resolución de nuestro problema
de prioridades planteado.
1. 20𝑥1 + 15𝑥2 + 25𝑥3 ≥ 100
2. 6𝑥1 + 4𝑥2 + 11𝑥3 = 50
3. 8𝑥1 + 7𝑥2 + 5𝑥3 ≥ 75
A diferencia de R®, no necesitaremos introducir comandos, sino que deberemos
de seleccionar la opción adecuada en la pantalla principal, que en este caso se trata de
Goal Programming. Nos aparecerá una ventana donde pide que indiquemos el número
de metas que queremos cumplir, que sería de 4 y el número de variables que queremos
optimizar, es decir, 3 variables.
POM-QM® mostrará una tabla donde debemos de rellenar con nuestros datos de
interés. Nos ofrece dos columnas llamadas Wt(d+) y Wt(d-) en estas columnas se les
tendrá que dar valor en función de que busquemos en cada meta, es decir, la positiva, en
nuestro caso es la primera, que es la llamada anteriormente pi, tendrá el valor 1 cuando
queramos minimizar la prioridad, y d- es la desviación ni que se ha explicado en el
anterior punto.
Esto se debe a que cuando resolvemos un problema por metas o prioridades,
introducimos en cada meta dos desviaciones, por tanto se trata de minimizar aquella
desviación que vaya en contra de nuestra meta, es decir, si mi meta es 8𝑥1 + 7𝑥2 +
5𝑥3 ≥ 75, introducimos los tipos de desviaciones que nos podemos encontrar: d- y d+ ,
quedando una expresión tal que 8𝑥1 + 7𝑥2 + 5𝑥3 − 𝑑+ + 𝑑− = 75. Si d+ adquiere
un valor muy elevado irá a favor de nuestro objetivo ya que elevará el valor de la
izquierda en comparación a la disponibilidad de 75, sin embargo, necesitamos que d-
tenga el mínimo valor posible.
De esta forma en nuestro ejemplo, para la primera meta, 20𝑥1 + 15𝑥2 +
25𝑥3 ≥ 100, tendremos que minimizar la desviación negativa en este caso llamada
“Wt(d-)”, por ello se le dará valor, a diferencia de Wt(d+) que se le asignará 0 ya que no
nos interesa su minimización.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 30
Con la tercera meta nos encontramos ante un ejemplo muy similar a la primera
ya que también se trata de buscar que nuestra expresión 8𝑥1 + 7𝑥2 + 5𝑥3 sea mayor
que 75. La diferencia se observa en la segunda meta porque queremos que 6𝑥1 + 4𝑥2 +
11𝑥3 sea igual a 50, es decir, necesitamos que el resultado que se obtenga de nuestra
expresión tenga la mínima desviación tanto positiva como negativa, por tanto, en este
caso tendremos que darle valor a Wt(d+) y Wt(d-).
Otra de las columnas que observamos en POM-QM® son llamadas Prty(d+) y
Prty(d-) donde debemos de indicar la prioridad que tiene la minimización de cada
desviación, es decir, para la primera meta se indicará que tiene prioridad 1 en la
columna de Prty(d-), sin embargo, como no tenemos desviaciones positivas se
mantendrá 0 para la prioridad de d+ en la columna Prty(d+).
La segunda prioridad al tratarse nuevamente de una igualdad se tendrá que
indicar tanto para la desviación positiva como para la desviación negativa. El resto de
datos necesarios, coeficientes de nuestras variables y disponibilidades se introducirán
como anteriormente hemos indicado (Figura 2.12)
Figura 2.12: Introducción de datos de metas en POM-QM®
Con estos pasos ya obtendríamos nuestra solución que coincide con la obtenida
anteriormente en R®. Además POM-QM® nos muestra directamente una tabla resumen
denominada Summary con el resultado de las variables, x1= 5, x2= 5 y x3= 0, y un
análisis de las metas donde podemos observar el valor de las desviaciones, es decir, d+
(row i) para la primera meta tiene un valor de 75 unidades, quiere decir que para la
primera meta superamos la disponibilidad de 100 que tenemos, en 75 unidades,
cumpliéndose este objetivo. Las otras dos metas, a diferencia de esta, tienen el valor de
0 para d+ (row i) y d- (row i), es decir, se llega exactamente a las disponibilidades de 50
y 75 para la segunda y tercera meta respectivamente, sin tener así ninguna desviación
(Figura 2.13).
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 31
Figura 2.13: Resultado de metas en POM-QM®
De igual forma POM-QM® permite resolver problemas que se tengan tanto
restricciones flexibles como rígidas, esto es gracias a la opción que tenemos para indicar
la prioridad que tiene cada restricción. Tras un estudio previo, podemos concluir, que
para su resolución únicamente es necesario introducir las variables rígidas como
siempre, es decir, ignorando las prioridades y los pesos, por tanto, tendrá un valor de
cero en estas casillas, pero usando la opción de Goal Programming. A las demás
restricciones se les asignará la prioridad que les corresponda al igual que el anterior
ejercicio de metas.
Viendo un caso práctico usaremos el mismo que hemos utilizado para R®.
Rígidas
𝑥1 + 𝑥2 + 𝑥3 ≤ 55
𝑥3 ≥ 10
Flexibles
0′05𝑥1 + 0′02 𝑥3 ≥ 0′15
0′03𝑥2 + 0′02𝑥3 ≥ 0′1
Una vez que indicamos el número de variables de restricciones en POM-QM®
deberemos de rellenar la tabla que nos muestra, de esta forma, sabemos que las dos
primeras restricciones rígidas tendrá la prioridad 0, y las dos flexibles se les asignará su
correspondiente prioridad y desviaciones, es decir, en el primer caso se trata de la
prioridad número uno e indicaremos que se minimice la desviación negativa, ya que
queremos que la expresión sea mayor que la disponibilidad que tenemos. Al igual
ocurre en la segunda meta flexible, la única diferencia es que tiene una prioridad por
debajo de la primera, es decir, se le indicará una prioridad de número dos (Figura 2.14)
Figura 2.14: Introducción de restricciones rígidas y flexibles en POM-QM®
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 32
Tras la adecuada anotación de nuestros datos pasaremos a resolverlo pulsando en
Solve donde mostrará una tabla igual que la anterior (Figura 2.15), ya que nos
encontramos en la misma opción de POM-QM®, donde se observará que el valor de
nuestras variables es de x1=0, x2=0 y x3=10. Además observamos que para la primera
restricción nos encontramos por debajo de la disponibilidad de 55 en 45 unidades ya
que se alcanza el valor de 10 para esta restricción, por tanto se cumpliría. En el caso de
la segunda meta se llega al valor exacto de 10, sin embargo, para las dos metas restantes
nos encontramos por debajo de las disponibilidades en 0’05 y 0’1, pero como se
necesitaba no sobrepasar las disponibilidades, se cumpliría con nuestros objetivos, por
tanto, la solución coincide con la obtenida en R®.
Figura 2.15: Solución restricciones rígidas y flexibles en POM-QM®
3. PROGRAMACIÓN NO LINEAL
La programación no lineal, al igual que la programación lineal, se basa en la
optimización de una función objetivo sujeta a unas restricciones pero a diferencia de las
anteriores serán no lineales algunas de ellas, por ejemplo, cuadráticas, cúbicas etc.
Definición
Podemos considerar el problema de programación no lineal como,
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥)
s. a.
𝑔𝑖(𝑥) ≤ 0 𝑖 = 1,2 … , 𝑚
ℎ𝑗(𝑥) = 0 𝑗 = 1,2 … , 𝑙
Debido a la mayor complejidad de estos problemas, además del escaso tiempo
del que se dispone en la asignatura, no se pudieron estudiar estos problemas en la teoría
ni en la práctica para llevar a cabo su resolución.
Tras una previa investigación teórica concluimos que una de las principales
diferencias de la programación no lineal con respecto a la programación lineal, es que el
punto óptimo no tiene por qué encontrarse en los puntos extremos de nuestra región
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 33
factible, es más, puede encontrarse en el interior de nuestra región mientras que en el
caso de la programación lineal nunca se encontrará en el interior.
En este proyecto nos centramos principalmente en la resolución de este tipo de
problemas mediante el uso de softwares informáticos ya que será mucho más sencillo
una vez que ya hemos adquirido ciertos conocimientos básicos de estas herramientas.
Resolución con R®
Para su aplicación en R® usaremos la función constrOptim para minimizar una función
sujeta a restricciones de desigualdad.
Función
constrOptim(theta, f, grad, ui, ci)
Argumentos de la función constrOptim
Theta: valor de partida numérico (vector) (de longitud p): debe estar en la región
factible.
f: función para minimizar.
grad: gradiente de f (una función también), o NULL.
ui: matriz de restricción (k x p).
ci: vector de restricción de longitud k.
Salidas de la función constrOptim
$par: valor de las variables de decisión que optimiza la función objetivo.
$value: valor que alcanza la función objetivo con el valor obtenido para las variables
de decisión.
Aplicación práctica
Empezamos aplicándolo con el uso de R® mediante la resolución de un ejemplo,
de forma que se pueda ver en la práctica.
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝐶𝑜𝑠𝑡𝑒 = 20.000 − 440𝑥1 − 300𝑥2 + 20𝑥12 + 12𝑥2
2 + 𝑥1𝑥2
s. a.
𝑥1 + 𝑥2 = 100
Para llevar a cabo la resolución de este problema en R®, comenzamos introduciendo los
datos que nos ofrece el problema, es decir, vamos a definir la función que queremos
minimizar, pero en este caso utilizando el comando function para definir el objeto,
donde indicaremos el nombre de las variables, x1 y x2, y a continuación entre corchetes
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 34
debemos de introducir la función objetivo, 20.000 − 440x1 − 300x2 + 20x12 + 12x2
2 +
x1x2, teniendo en cuenta la adecuada escritura en R®.
Para la introducción de las restricciones se usará una matriz y para las
disponibilidades se define el objeto mediante un vector.
Una vez que introducimos los objetos podemos pasar a su resolución, en este
caso, utilizaremos el paquete llamado constrOptim.
En este paquete se pueden definir varios argumentos, nos centramos en aquellos de
nuestro interés para la resolución del ejercicio.
Directamente al ejecutar el comando mediante “run” o usando “ctrl+r” nos
mostrará todos los resultados, si queremos en concreto el valor de nuestras variables
podremos fijarnos en $par donde observamos que x1= 26’5537 y x2=73’4463. Para el
valor que tomará la función objetivo se mostrará en $value que en este caso será de
1.029.060 unidades.
4. PROBLEMAS DE REDES
Hay situaciones donde los problemas estudiados se pueden representar mediante
redes, habiéndose desarrollado algoritmos específicos para su resolución. Para
comprender esto, comenzaremos estudiando en que se basan los problemas de redes.
Su investigación comenzó a desarrollarse en el pasado, con el famoso problema
de los siete puentes de la ciudad de Koenigsberg. La investigación fue desarrollada por
Euler cuyo objetivo era encontrar el itinerario más corto que deberían de recorrer los
habitantes de la isla Kueiphof, que se encontraba rodeada por un río, pasando solo una
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 35
vez por cada uno de los siete puentes construidos para los habitantes y que así pudiesen
volver a su punto de partida. Si imaginamos cada trozo de tierra que unían esos puentes
como un punto y cada puente por un trazo podremos obtener algo similar a lo que se
conoce como grafo (Fontenla Cadavid, M., 2014).
Definición
Definiremos una serie de conceptos previos para el estudio de estos problemas.
Grafo: “Llamaremos grafo a un par {V, A}, donde V es un conjunto de
elementos llamados vértices o nodos y 𝐴 ⸦ 𝑉 𝑥 𝑉 otro conjunto cuyos elementos son los
arcos. Si (𝑎, 𝑏) es un elemento de A, 𝑎 se llama origen y 𝑏 extremo” (Rodríguez
Huertas, R. y Gámez Mellado, A., 2002).
Red: grafo cuyos arcos tienen asociada alguna medida.
Red bilateral: red que admite ambas orientaciones en los arcos que serán
llamados en este caso aristas.
Red dirigida: red sin aristas, es decir, no admite ambas orientaciones en los
arcos.
De forma resumida una red o grafo dirigido se compone de (Kong, M., 2010):
“Un conjunto finito de símbolos, llamados nodos o estados: a, b,…
Para cada nodo n hay asociados cero o más nodos sucesores: s1, s2,…, sn en
donde cada asociación es formalmente el par ordenado (n, si), o n, si, llamado
arco dirigido de n al nodo sucesor s.
Cada arco es valorado”.
Una vez que hemos definido el concepto de red vamos a estudiar problemas
asociados como son: la búsqueda de menor recorrido, del menor coste, de asignación
eficiente…
4. 1. PROBLEMA DEL TRANSPORTE
Un tipo de ejercicio que podemos encontrarnos dentro de los problemas de redes
son los llamados, problemas de transporte, que a pesar de tratarse de una variante de
problemas de la programación lineal, contarán con su propio algoritmo para que puedan
ser resueltos de forma más eficiente.
Definición
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 36
“Se llama red de transporte a todo grafo 𝐺 = (𝑉, Γ) orientado, conexo y sin bucles, en
el que aparecen varios elementos asociados a los vértices y a los arcos que constituye
el grafo” (Martínez Rodríguez A.M., 2017).
Elementos asociados a los arcos son:
𝑰𝒊𝒋: mínima cantidad de transporte (flujo) que puede pasar por el arco (𝑖, 𝑗).
𝑲𝒊𝒋: máxima cantidad de transporte (flujo) que puede pasar por el arco (𝑖, 𝑗).
𝑪𝒊𝒋: coste de una unidad al pasar por el arco (𝑖, 𝑗).
Elementos asociados a los vértices:
𝒅𝒊: demanda o disponibilidad del vértice 𝑉𝑖. Si la demanda es positiva el vértice se
llamará sumidero o de destino, si es nula punto de tránsito, y si es negativa fuente u
origen.
Por tanto, se supone que 𝑚 orígenes (fuentes o entradas) tienen que surtir a 𝑛
centros de consumo (sumideros o salidas). La capacidad de oferta del origen i es de ai
(𝑖 = 1, 2 . . . , 𝑚) y la demanda en el centro de consumo j es 𝑏𝑗 (𝑗 = 1, 2, . . . , 𝑛). Se
supone que cij es el costo de enviar una unidad del producto del origen i al centro de
consumo j. El problema se reduce a determinar cuántas unidades del producto deben
enviarse del origen i al centro de consumo j, tal que se minimicen los costos totales de
distribución, se satisfaga la demanda del centro de consumo j y no se exceda la
capacidad de oferta del origen i.
La estructura de transporte es tal que,
mín Z = ∑ ∑ 𝑐𝑖𝑗𝑓𝑖𝑗
𝑛
𝑗=1
𝑚
𝑖=1
∑ 𝑓𝑖𝑗 = 𝑎𝑖
𝑛
𝑗=1
𝑖 = 1, … , 𝑚
∑ 𝑓𝑖𝑗 = 𝑏𝑗
𝑚
𝑖=1
𝑗 = 1, … 𝑛
𝑓𝑖𝑗 ≥ 0 ∀𝑖 , 𝑗
Nuestro objetivo es el desarrollo y resolución de estos problemas mediante
softwares informáticos. Empezaremos por R®, y posteriormente utilizaremos POM-
QM®.
Resolución con R®
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 37
R® cuenta con una función específica, que se encuentra en el paquete lpSolve
para la resolución de este tipo de problemas, en concreto, lp.transport, la cual se basa en
valores enteros y además su objetivo será minimizar nuestro problema.
Función
lp.transport(cost.mat, direction="min",
row.signs, row.rhs, col.signs,
col.rhs, integers = 1)
Argumentos de la función lp.transport
cost.mat: matriz de costes; cada elemento es el coste de transportar un elemento de la
fuente i al destino j.
direction: indicar si se trata de minimizar o maximizar "min" o "max".
row.signs: vector de caracteres para indicar la dirección de las restricciones de fila:
cada caracter debe ser alguno de los siguientes "<," "≤," "=," ">," o "≥".
row.rhs: vector de valores numéricos para los lados derechos de las restricciones.
col.signs: vector de cadenas de caracteres dando la dirección de las restricciones de
columna: cada carácter debe ser alguno de "<," "≤," "=," ">," o "≥".
col.rhs: vector de valores para los lados derechos de las restricciones de la columna.
Integers: vector de enteros. Su longitud será el número de variables enteras.
Predeterminado: todas las variables son enteras. Si se indica en NULL no se tendrá en
cuenta de ser ninguna variable entera.
Salidas de la función lp.transport
$objval: valor que alcanza la función objetivo.
$solution: cantidad transportada desde cada origen a cada destino.
Aplicación práctica de la función lp.transport
Planteamos el desarrollo de un ejercicio práctico que se basa en la necesidad de
transportar los motores fabricados en Amsterdam (A), Amberes (B) y El Havre (C) a los
puntos donde se demandan, en concreto, en Alemania (1), Francia(2), Bélgica (3),
Países Bajos (4). Las cantidades ofertadas se recogen en la Figura 4.1, las demandas en
la Figura 4.2 y para entender la relación entre la cantidad demandada y ofertada con
respecto a los costes no basaremos en la Figura 4.3 que recoge los datos de forma clara
y esquemática.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 38
Figura 4.1: Cantidad oferta por ciudad.
PLANTA CANTIDAD DE MOTORES
1 400 2 900 3 200 4 500
Figura 4.2: Cantidad demandada por ciudad
Puerto Motores disponibles
A 500 B 700 C 800
Figura 4.3: Demanda, oferta y coste
DESTINO ORIGEN DEMANDA
1 2 3 4 A 120 130 41 62 500 B 61 40 100 110 700 C 102.50 90 122 42 800
OFERTA 400 900 200 500
En primer lugar debemos de introducir los objetos en R® como hasta ahora,
usando una matriz para indicar el coste del transporte y vectores para las
disponibilidades de la oferta, de la demanda y de la dirección. En este último caso en
particular, debemos de pensar que buscamos satisfacer la demanda, por tanto, tenemos
que cumplir la disponibilidad indicada o superar este valor, por ello su dirección será
“≥”. Mientras que para la oferta es lógico pensar que no podemos transportar más
cantidad de la fabricada por ello se indica “≤”.
Para usar la función lp.transport necesitamos definir los nuevos argumentos llamados
row.signs, row.rhs, col.signs, y col.rhs, definidos anteriormente.
Podemos obtener de R® el coste total del transporte, así como la cantidad que se
transporte a cada ciudad y desde que punto es transportada, mostrándose en una tabla
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 39
fácilmente de interpretar que nos confecciona el software (Figura 4.4), de esta forma
observamos, por ejemplo, que se transportan desde Amsterdam a Alemania 300
unidades y 100 unidades de Bélgica a Alemania, satisfaciendo la demanda total de
Alemania de 400 unidades.
Figura 4.4: Solución transporte en R®
Resolución con POM-QM®
Para la resolución de este tipo de ejercicios desde POM-QM® es necesario que lo
indiquemos en el software a través de la opción que nos ofrece llamada Transportation
Method (Location) y nos pedirá que indiquemos el número de fuentes (es decir, las
ofertas) y el número de destinatarios. Por último, es necesario que indiquemos el coste
del transporte en la tabla que nos mostrará POM-QM® y sea posible su resolución
obteniéndola en un cuadro (Figura 4.5).
Figura 4.5: Solución de Transporte en POM-QM®
La solución obtenida se puede observar que es la misma que conseguimos en
R®, aunque si es cierto que POM-QM® nos muestra además dos tablas adicionales con
un análisis del resultado obtenido así como el coste de cada transporte y el coste por
cada unidad, es decir, en el primero de los caso que se transporta desde Source 1 a
Destination 1 la cantidad de 300 unidades, le corresponde un coste total de 36.000
unidades monetarias. Esto viene del resultado de multiplicar las unidades transportadas
(300 unidades) por el coste por unidad que nos indicaba el problema inicialmente (120
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 40
unidades monetarias). Así POM-QM® nos mostrará un resumen detallado para cada uno
de los transportes obteniendo el coste total de 121.450 unidades monetarias.
4. 2. PROBLEMAS DE ASIGNACIÓN
Los problemas de asignación cuentan con una estructura similar a lo problemas
de transporte, pero tienen varias diferencias con respecto a estos. No se trata de
encontrar la cantidad óptima para transportar, sino que la oferta y la demanda es de uno.
Para entenderlo más claramente, podemos poner el ejemplo de asignar personas a una
tarea de un conjunto que tengamos, se si hace la asignación tendrá el valor de uno y en
caso contrario se le dará el valor de cero.
Este es un caso especial de los problemas de transporte, en el que las personas son las
fuentes y las tareas los destinos, mientras que la oferta y la demanda se trata de 1 (y 0).
Definición
mín Z = ∑ ∑ 𝑐𝑖𝑗𝑓𝑖𝑗
𝑛
𝑗=1
𝑚
𝑖=1
s. a.
∑ 𝑓𝑖𝑗 = 1
𝑛
𝑗=1
𝑖 = 1, … , 𝑚
∑ 𝑓𝑖𝑗 = 1
𝑚
𝑖=1
𝑗 = 1, … 𝑛
𝑓𝑖𝑗 ≥ 0 ∀𝑖 , 𝑗
Las variables 𝑓𝑖𝑗 sólo pueden tomar el valor 0 o 1. Toman el valor 1 si el origen
i se hace corresponder al destino j, y 0 en caso contrario. Este tipo de problemas son
lineales, con una estructura de transporte, en el que la oferta de cada origen es de valor
uno y la demanda de cada destino también es de valor uno.
Resolución con R®
Será de forma similar a la llevada a cabo durante el transporte, pero igual que en
este caso, contará con una función específica para este tipo de problemas, lp.assign, la
cual también se puede encontrar en el paquete lpSolve.
Función
lp.assign (cost.mat, direction = "min")
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 41
Argumentos de la función lp.assign
cost.mat: matriz de costes: el ij-ésimo elemento es el coste de asignar la fuente i al
destino j.
direction: dirección de la función objetivo "min" (el valor predeterminado) o
"máx".
Salidas de la función lp.assign
$solution: para mostrar la tabla que contiene la asignación óptima.
Aplicación práctica
Para ilustrar este tipo de ejercicio mediante un software informático usaremos el
siguiente caso: hay una serie de directivos que queremos que visiten cuatro plantas,
teniendo en cuenta el coste de visita de cada uno de ellos por cada una de las plantas,
debemos de elegir la asignación óptima de visita para minimizar el coste final (Figura
4.6).
Figura 4.6: Coste por visita de cada directivo
PLANTA
Vicepresidente 1 2 3 4
Finanzas 24 10 21 11
Mercadotecnia 14 22 10 15
Operaciones 15 17 20 19
Personal 11 19 14 13
Empezaremos a resolver este problema usando R® cargando el paquete lpSolve e
incluyendo los costes que tenemos de asignación por cada directivo en cada planta
usando una matriz.
El comando que utilizaremos para llevar a cabo su resolución se denomina
lp.assign en el cual simplemente nos pedirá que introduzcamos la matriz de los costes y
la dirección, es decir, si nuestro objetivo en este caso es de maximizar o de minimizar.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 42
Cuando le pidamos a R® la solución del ejercicio mostrará una tabla completada
con unos y ceros. Como ya hemos explicado al principio, en los casos que encontremos
unos será porque se deberá de hacer la asignación de ese directivo a la planta donde nos
indica y en los casos que nos encontremos con ceros no habrá asignación.
De esta forma, el directivo de finanzas irá a la planta dos, el directivo de
mercadotecnia se encargará de la planta tres, el de operaciones de la planta uno y por
último el directivo de personal será destinado a la planta número cuatro.
Resolución con POM-QM®
Si lo llevamos a cabo usando POM-QM®, nos encontramos ante la misma
situación que en el transporte, de forma que indicando la sección correspondiente
Assignment nos pedirá el número de máquinas y el número de trabajos, que
corresponden con el número de directivos y el número de plantas a visitar
respectivamente.
Introducimos los datos en la tabla que nos mostrará POM-QM® y pulsando sobre
Solve obtendremos el resultado de la asignación como del coste que al que se llega con
dicha asignación (Figura 4.7).
Figura 4.7: Solución Asignación POM-QM®
Podemos ver que el resultado es el mismo que el obtenido en R® solo que en este
caso saldrá expresado en color azul Assign con el coste correspondiente. En la esquina
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 43
superior de la izquierda nos aparecerá el coste total obteniendo así como toda la
información necesaria para la resolución de este ejercicio.
5. 3. ÁRBOL DE COSTE MÍNIMO
Este tipo de problemas aparecieron por la necesidad de crear una red eléctrica
entre unas ciudades teniendo en cuenta la distancia que había entre cada una de ellas, de
forma que Boruvka formuló y resolvió este tipo de problemas en 1926. Posteriormente
Robert C. Prim descubrió un nuevo algoritmo para la resolución de estos problemas en
1957 que denominó Prim. Además, este problema también fue resuelto por Joseph B.
Kruskal, mediante el algoritmo llamado Kruskal (Piedra Hernández, V. S. y Paternostro
Movilla, C. A., 2009).
Por tanto, se trata de un grafo formado por nodos, que en nuestro problema
inicial se tratarían de nuestras ciudades unidas por los arcos no dirigidos con la
correspondiente distancia que separa a cada ciudad, con el objetivo de poder hacer la
distribución de electricidad con el menor recorrido posible.
Definición
Matriz de Costo:
Sea el grafo 𝐺 = (𝑉, 𝛤), definimos la matriz de costo 𝐶 = ( 𝑐𝑖𝑗) donde
𝑐𝑖𝑗 = { 𝑐𝑜𝑠𝑡𝑜 𝑑𝑒 𝑝𝑎𝑠𝑜 𝑑𝑒 𝑉𝑖 𝑎 𝑉𝑗 𝑠𝑖 (𝑉𝑖 , 𝑉𝑗 ) 𝑜 )𝑉𝑖 , 𝑉𝑗 ( ∈ 𝛤∞ 𝑒𝑛 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
Una vez introducidos los costos planteamos el localizar el árbol generador de mínimo
costo siendo,
grafo 𝐺 = (𝑉, 𝛤), 𝑐𝑜𝑛 𝑐𝑎𝑟𝑑 (𝑉 ) = 𝑛, y sea C la matriz de costos.
Consideramos los elementos de C sobre la matriz principal. Sea �̂� el conjunto de
elementos de C sobre la diagonal principal ordenados de menor a mayor.
Sea 𝑇𝑛 × 𝑛 la matriz de adyacencia del árbol.
Resolución con R®
Para este tipo de problemas se han desarrollado varios tipos de algoritmos que en
R® también están disponibles mediante el paquete optrees,
que permite encontrar árboles óptimos en gráficos ponderados. En particular, este
paquete ofrece herramientas de solución para los problemas de árbol de expansión de
costo mínimo, problemas de arborescencia de costos mínimos, problemas de árbol de
trayecto más cortos y problema de árbol de corte mínimo.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 44
Función
Podemos utilizar dentro de la misma función tres tipos diferentes de algoritmos para su
resolución
getMinimumSpanningTree(nodes, arcs, algorithm =
"Prim")
getMinimumSpanningTree(nodes, arcs, algorithm =
"Kruskal")
getMinimumSpanningTree(nodes, arcs, algorithm =
"Boruvka")
Argumentos de la función getMinimumSpanningTree
nodes: vector donde se incluyen el número de nodos.
arcs: matriz donde se recoge el valor de cada uno de los arcos.
algorithm: algoritmo con el que se quiere resolver la función (Prim, Kruskal o
Boruvka).
Salidas de la función getMinimumSpanningTree
Este tipo de funciones nos mostrarán directamente la soluciones sin necesidad de
ningún comando adicional como en los casos anteriores.
Aplicación práctica
Para su puesta en práctica usaremos el ejemplo del libro de Alonso Revenga
J.M. Flujo en Redes y Gestión de Proyectos, pp. 43 que pretende crear una red de
carreteras rurales entre unos parajes naturales (Figura 4.8).
Figura 4.8: Ejercicio árbol de mínimo costo
30
15 23
10 14 21
25
17 28
32
P1
P3
P2
P4
P6
P5
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 45
Comenzaremos usando el algoritmo denominado Prim, el cual empezará
arbitrariamente en un nodo de nuestro grafo e irá conectándose con el resto a través de
los arcos que tienen la menor distancia consiguiendo un árbol de expansión cuyo coste
sea mínimo.
En primer lugar deberemos de indicar a R® el número de nodos que tenemos y la
distancia entre cada uno de ellos usando una matriz para esto último. Los datos de la
matriz se introducirán indicando el número de los dos nodos que vayamos a indicar y a
continuación la distancia entre ellos.
Una vez que hemos introducido nuestros objetos usaremos el siguiente comando
especificando que lo vamos a resolver usando el algoritmo de Prim e introduciendo los
nodos que anteriormente indicamos cuantos tenemos y los arcos definidos por la matriz.
Directamente obtenemos la solución además de poder verlo esquemáticamente
en la esquina inferior de la derecha marcando de rojo el camino óptimo a seguir (Figura
4.9).
Figura 4.9: Árbol de mínimo coste R ®
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 46
Además esta solución también muestra en una tabla, indicando el tipo de
algoritmo usado y teniendo en cuenta la distancia que se recorrerá con dicho camino,
calculando la distancia total óptima que se recorrerá que en nuestro caso.
Otro algoritmo que podemos usar para resolver estos problemas es el llamado
algoritmo de Kruskal que se basa en conectar arcos y no nodos como era el caso del
algoritmo de Prim, por tanto, ya no es necesario elegir un nodo de partida, sino que se
empezará con el arco con menor distancia.
Introduciendo de igual manera los datos y usando el mismo script podremos
resolver el problema con este algoritmo indicándolo en vez de escribir Prim.
Se observa que el resultado es el mismo, solo que en este caso no comienza por
el nodo uno, sino que ha comenzado por el arco de menor distancia que en nuestro caso
se trata del arco comprendido entre el nodo 3 y 4 con un peso de 10.
Por último también podremos usar el algoritmo Boruvka considerando a cada
nodo como un componente y seleccionará los arcos de menor coste que inciden en él.
Este proceso se repite con cada componente hasta conseguir así el árbol de costo
mínimo.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 47
Usando este algoritmo en R® llegaremos a la misma conclusión que con los
anteriores a pesar de usar diferentes algoritmos.
Este tipo de ejercicios también podrán llevarse a cabo mediante POM-QM®,
pero la diferencia con respecto R®, es que no podremos elegir el algoritmo que
queremos usar.
Resolución con POM QM®
Seleccionamos en POM QM® la sección correspondiente NetWork y al abrir una
nueva pestaña en esta sección podremos elegir entre tres tipos de problemas Minimum
Spanning Tree, Shortest Route y Maximal Flow. En este caso deberemos de
seleccionar Minimum Spanning Tree y nos pedirá en concreto el número de ramas, es
decir, el número de arcos que tiene el grafo, siendo 10 en el caso que estamos
desarrollando.
En POM-QM® se generará una tabla para que indiquemos de dos en dos nodos
la distancia que hay entre ellos, es decir, al igual que en R® se hace mediante un matriz
en POM-QM® se hará mediante una tabla de forma más simple.
La primera tabla que nos ofrece este programa como solución es la que incluye
los datos que hemos introducimos junto con dos columnas más llamadas Include y
Cost. La primera se usará para poder marcar con una Y aquellos caminos por los que se
pase en la solución y en dicho caso se rellenarán las casillas correspondientes de Cost
para poder sumar así el coste total de los caminos por los que se pasa. Para poder ver la
solución de forma más clara, POM-QM® ofrece una tabla que podemos desplegar en la
esquina inferior de la izquierda, conteniendo toda la informa necesaria sobre la solución
y coincidiendo con la solución obtenida en R® (Figura 4.10).
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 48
Figura 4.10: Solución Árbol de Costo Mínimo en POM-QM®
5. 4. ARBORESCENCIA DE COSTE MÍNIMO
Este tipo de ejercicios parten del problema tratado anteriormente pero con la
condición de que el grafo es dirigido, es decir, los arcos suelen representarse con una
flecha indicando en la dirección.
Definición
Sea el grafo 𝐺 = (𝑉, 𝛤), 𝑐𝑜𝑛 𝑐𝑎𝑟𝑑 (𝑉 ) = 𝑛, y sea C la matriz de costos.
Fijar V0 (raíz de la arborescencia) y construir una arborescencia T. Sea T la matriz
booleana de la arborescencia construida.
Etiquetar cada vértice Vi con 𝑑𝑖 = 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑖𝑎 (𝑐𝑜𝑠𝑡𝑜) de V0 a Vi en T (cuando 𝑉0 =
𝑉𝑖 , 𝑑𝑖 = 0).
Para todo 𝑖, 𝑗, 𝑖 ≠ 𝑗, (𝑉𝑖 , 𝑉𝑗 ) ∈ 𝛤 𝑠𝑒𝑎 𝑠𝑖𝑗 = 𝑑𝑗 − 𝑑𝑖 − 𝑐𝑖𝑗 .
Escoger 𝑠𝑟𝑘 = 𝑚á𝑥 (𝑠𝑖𝑗).
Resolución con R®
Para la resolución de este tipo de problemas usaremos la función
getMinimumArborescence donde usará el algoritmo de Edmonds para la resolución de
este tipo de ejercicios que se encuentra dentro del paquete optrees, explicado en el
apartado anterior.
Función
getMinimumArborescence(nodes,arcs,algorithm =
"Edmonds")
Argumentos de la función getMinimumArborescence
nodes: vector donde se incluyen el número de nodos.
arcs: matriz donde se recoge el valor de cada uno de los arcos.
algorithm: algoritmo con el que se quiere resolver la función (Edmonds).
Salidas de la función getMinimumArborescence
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 49
Al igual que en el caso anterior, este tipo de funciones nos mostrarán directamente la
soluciones sin necesidad de ningún comando adicional como en los casos anteriores.
Aplicación práctica de la función getMinimumArborescence
Si consideramos el mismo ejercicio anterior pero en este caso dirigido en la
siguiente dirección contamos con el grafo que se muestra en la Figura 4.11.
Figura 4.11: Ejemplo dirigido
30
15 23
25
10 21
17 28
32
Empezamos como los demás problemas, indicando el número de nodos y la
matriz correspondiente de los nodos con sus arcos, en este caso, la introducción de estos
datos coincidirá con la definición de los datos realizada para el árbol de coste mínimo,
teniendo en cuenta que la introducción de datos de la matriz para este tipo de ejercicios
habrá que considerar la dirección de los arcos para ponerla de tal forma en la matriz.
Lo importante será la función que usaremos, getMinimumArborescence, el cual pedirá
que indiquemos el vector que contiene el número de nodos, la matriz de nuestro grafo y
el algoritmo a usar (Edmonds).
La solución aparecerá expresada de forma similar al anterior, ejemplo, por un
lado contaremos con la tabla resumen donde nos indica por los arcos que pasamos y el
coste total que se tiene con dicho camino y a la derecha podremos ver el dibujo de este
camino señalado en rojo además de marcarnos la dirección, ya que los arcos son
representados mediante flechas. En este caso en particular el camino a seguir será por
los nodos: 1-2, 1-3, 3-4, 4-5 y 5-6 con un coste total de 85 (Figura 4.12).
P1
P3
P2
P4
P6
P5
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 50
Figura 4.12: Arborescencia de coste mínimo R ®
Este tipo de ejercicios no pueden ser resueltos con POM-QM® ya que no cuenta
con una sección para este tipo de problemas, por tanto, observamos que el paquete
optrees de R nos da una serie de funciones más completas que con las que nos podemos
encontrar en el software de POM QM®.
5. 5. ÁRBOL DEL CAMINO MÁS CORTO
En muchas ocasiones nuestro objetivo es encontrar el camino más corto entre
dos nodos, de forma que se recorra la menor distancia posible, nos centraremos en
buscar todos los caminos más cortos desde un nodo inicial a los demás.
Definición
Se busca determinar un camino de longitud mínima entre un vértice de origen y un
destino en un grafo.
Tenemos un grafo con n vértices (numerados 1, 2, . . . , n).
Para cada arco (i, j) existe un número dij ≥ 0 que representa la distancia (coste,
tiempo...) desde el vértice i al vértice j.
Si no existe el arco (i, j) se dice que ambos vértices no están conectados directamente y
la distancia asociada es 𝑑𝑖𝑗 = +∞.
Pueden existir los arcos (i, j) y (j, i) pero las distancias ser distintas, es decir 𝑑𝑖𝑗 ≠ 𝑑𝑗𝑖.
Resolución con R®
El algoritmo Dijkstra podrá ser aplicado en R® con nuestro paquete optrees gracias al
comando getShortestPathTree en el cual, a partir de la definición previa de nuestros
nodos y las distancias, ofrece la opción de elegir el algoritmo que queremos usar para
este tipo de problemas.
Función
getShortestPathTree(nodes, arcs, algorithm)
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 51
Argumentos de la función getShortestPathTree
nodes: vector donde se incluyen el número de nodos.
arcs: matriz donde se recoge el valor de cada uno de los arcos.
algorithm: algoritmo con el que se quiere resolver la función (Dijkstra o Bellman-
Ford).
Salidas de la función getShortestPathTree
Mostrará directamente las soluciones sin necesidad de ningún comando adicional como
en los casos anteriores.
Aplicación práctica de la función getShortestPathTree
Utilizando de ejemplo el ejercicio que hemos resuelto en los apartados
anteriores, la indicación de los datos será de forma idéntica, pasando a introducir el
comando getShortestPathTree que nos pedirá que indiquemos los nodos, la matriz de
los pesos y el algoritmo con el cual resolverá nuestro ejercicio.
R® mostrará la solución tanto de forma esquemática, indicando en rojo los
caminos más cortos desde el nodo uno a cada uno de los demás nodos, así como en una
tabla resumen (Figura 4.13).
Figura 4.13: Solución camino más corto R®
La solución que obtenemos es que el menor camino que nos lleva desde el nodo
uno al nodo dos es de 25, del nodo uno al nodo tres 15, del nodo uno al nodo cuatro 25 (
acumulado de sumar 15, del nodo uno al tres, y 10, del nodo tres al cuatro), del nodo
uno al cinco 30 y del nodo uno al seis 51( resultante de sumar 30, del nodo uno al cinco,
y 21, del nodo cinco al seis).
Otra forma de resolver este tipo de problemas sería mediante la aplicación del
algoritmo de Bellman-Ford. Este algoritmo tiene el mismo objetivo que el algoritmo de
Dijkstra e intenta dar solución a este tipo de problemas, pero su gran diferencia, es que
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 52
intenta solventar el principal problema que nos encontramos con el algoritmo de
Dijkstra, es decir, no poder resolver problemas con arcos negativos. Aparte de poder
resolver ejercicios con arcos negativos, el algoritmo de Bellman-Ford se basa, al igual
que el algoritmo de Dijkstra, en encontrar el camino más corto desde uno nodo inicial a
cada uno de los restantes nodos.
Para poder ver este tipo de ejercicio con un ejemplo práctico usaremos el
problema anterior cambiando algunos arcos con pesos negativos (Figura 4.14).
Figura 4.14: Ejemplo arcos negativos
30
-15 23
25 10 21
17 28
-32
Podemos resolver este ejercicio introduciendo tanto el número de nodos como
los datos correspondientes a los pesos con una matriz como hemos hecho en el caso
anterior. Además el script será el mismo, solo tendremos que tener en cuenta, que en
este caso con pesos negativos deberemos de usar el algoritmo de Bellman-Ford cuando
R® nos pida que indiquemos con que algoritmo queremos resolver el problema.
Obviamente el resultado cambiará para algunos caminos, como es el caso de la
distancia más corta entre el nodo uno y tres que tendremos de resultado -15. Otro
ejemplo sería en el caso de ir del nodo uno al cuatro, que en este ejemplo decidiremos ir
del uno al dos y del dos al cuatro, ya que este último arco tiene un valor negativo de 32
y compensará con creces pasar por este, asumiendo el valor del arco inicial del nodo
uno al dos con 25 positivo (Figura 4.15).
P1
P3
P2
P4
P6
P5
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 53
Figura 4.15: Solución en R® con Bellman-Ford
En el caso de intentar hacer un problema con arcos negativos usando el
algoritmo de Dijkstra R® nos mostrará un mensaje de error indicando que dicho
algoritmo no puede procesar pesos negativos.
Resolución con POM-QM®
Este tipo de problemas si pueden resolverse con POM-QM® a diferencia del
anterior tipo de problema, para ello este software cuenta con una sección en concreto
dentro de Networks llamada Shortest Route, no obstante, no podremos elegir el tipo de
algoritmo que queremos aplicar a diferencia del software R®, ya que POM-QM® sólo
nos permite elegir el tipo de problema que queremos solucionar.
Para su resolución será necesario que indiquemos el número de arcos que tiene el grafo
y si se trata de un problema dirigido o no dirigido. Una vez que le hemos indicado a
POM-QM® la información inicial que necesita, de nuevo tendremos que introducir los
datos acerca de las distancias que hay entre cada nodo, es decir, resultará una tabla
como la mostrada en la figura.
Lo primero que POM-QM® muestra es una tabla donde se refleja el camino más
corto desde el nodo uno (inicial) al seis (final), sumando los pesos por los que pasa.
Para ver el camino más corto para cada uno de los nodos desde el nodo inicial uno,
podremos desplegar la tabla que aparece en la esquina inferior de la izquierda, en la cual
se muestra de forma detallada el camino más corto para cada caso. Debido a que hemos
indicado que se trata de un problema dirigido, en la tabla que nos mostrará POM-QM®
aparecerá escrito No path en aquellas casillas que no corresponde su cálculo, es decir,
aquellas que irían en contra de la dirección señalada (figura 4.16).
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 54
Figura 4.16: Solución camino más corto POM-QM®
Si quisiéramos resolver un ejercicio con pesos negativos POM-QM® no podría
ser una opción, ya que directamente si intentamos meter algún valor con signo negativo
en la tabla inicial de introducción datos, nos mostrará una ventana indicando que no
permite que se indiquen valores negativos. Por tanto, sabemos que POM-QM® no
utiliza el algoritmo de Bellman-Ford para resolver este tipo de problemas.
5. 6. PROBLEMA DE FLUJO MÁXIMO
Supongamos que somos los gerentes de una empresa de electricidad y queremos
llevar la electricidad de nuestra empresa hasta la ciudad que nos demanda la necesidad.
En este caso nuestro objetivo sería tratar de transportar la mayor cantidad posible de
electricidad. Tendremos en cuenta que debemos de pasar por unos nodos y por tanto por
unos arcos para llegar a mi nodo destino, así cada arco tendrá una capacidad máxima
que puede transportar. Por tanto, nuestro objetivo se trata de transportar la cantidad
máxima posible de electricidad sujeta a las limitaciones que presenta la capacidad
mostrada en un grafo.
Este tipo de problemas nos pueden servir de mucha ayuda sobre todo en el
ámbito empresarial a la hora de hacer algún tipo de distribución con la mayor capacidad
posible, además de ser problemas que puedan presentar grandes variantes dentro de esta
misma categoría, por tanto, sería interesante un previo y rápido estudio antes de
comenzar con su resolución mediante los softwares informáticos.
Definición
En primer lugar, tenemos que considerar que en este tipo de problemas se
contará con tres tipos de nodos, un nodo fuente del cual saldrá el flujo y del cual solo
parten arcos, un nodo destino que es el generador de la demanda y por tanto solo le
llegan arcos y los nodos de transición por los cuales pasarán nuestros flujos y por tanto
de ellos saldrán y les llegarán arcos.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 55
Cuando el flujo llega a un nodo de transición puede ser que ocurran tres cosas,
que simplemente pase el flujo y salga la misma cantidad que entró, que en el momento
en que entra el flujo en el nodo de transición no salga y que la cantidad que entre en este
nodo sea menor a la que vaya a salir de él, es decir, en este último caso el nodo
aumentaría la cantidad recepcionada.
Los arcos en estos problemas suelen ser dirigidos ya que nuestro objetivo es ir
desde un punto de origen a un punto de destino. La información que podemos tener
sobre los arcos puede ser variada, por un lado nos indicarán la capacidad máxima que
tendrá cada uno, en algunas ocasiones puede ser que los arcos también tengan una
cantidad mínima que deberá de pasar por este y también pueden llevar un coste asociado
por cada unidad que pase por el arco.
Si nuestro objetivo se trata de maximizar el flujo de una red consideraremos un
único nodo de origen y un único nodo de destino siendo el resto de los nodos de
transición sin aumentar su capacidad y sin suponer ningún coste.
Resolución con R®
Para llevar la resolución de este tipo de problemas en R® usaremos el paquete
igraph donde encontraremos la función llamada max_flow, la cual permite calcular el
flujo máximo entre dos vértices en un grafo, con una capacidad de flujo dada.
Función
max_flow(graph, source, target, capacity = NULL)
Argumentos de la función max_flow
graph: el grafo.
source: nodo que es el de origen.
target: nodo que es el sumidero.
capacity: vector que da la capacidad de los arcos. Si es NULL (por defecto) la
capacidad es la que se asigna en los atributos definidos en el grafo.
Salidas de la función max_flow
La salida que muestra es una lista con los siguientes valores:
value: un escalar con el valor del flujo máximo.
flow: un vector con los flujos de cada arco.
cut: un vector con los vértices en el corte
partition1: los nodos de una de las dos particiones del corte
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 56
partition2: los vértices de la segunda partición del corte.
stats: una lista con información sobre los algoritmos utilizados.
Aplicación práctica de la función max_flow
Considerando que la empresa Energy quiere transportar energía desde su central
hasta la ciudad más cercana, tendrá que pasar para ello por cuatro nodos de transición.
Queremos maximizar el flujo de energía siendo la central el nodo uno, la ciudad el nodo
seis y el resto, así como sus arcos, vienen representados en la Figura 4.17.
Figura 4.17: Grafo de electricidad
9
10 8
5
6 15
20
Para la introducción de los grafos se debe indicar cada uno de los arcos que
contiene a través de un vector para cada uno, utilizando el comando “rbind” que permite
agruparlos. Usaremos el mismo ejemplo planteado anteriormente para poder comprobar
que el resultado obtenido coincide realizándolo a través de esta función.
A continuación debemos de dar nombre las columnas para posteriormente poder
crear el grafo mediante la función graph_from_data_frame indicándole los arcos que
anteriormente hemos introducidos y nombrado.
A diferencia de la anterior función no nos muestra directamente el grafo
representado, no obstante, podemos crearlo usando la función plot e indicando el grafo
que se quiera representar, a continuación se muestra el comando necesario para su
representación, así como el resultado gráfico obtenido con ella (Figura 4.18).
1
6
2
5 3
4
4
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 57
Figura 4.18: Representación grafo con Plot en R®
La representación del grafo es solamente opcional, ya que podemos resolver el
ejercicio sin necesidad de hacer esta representación, sin embargo, con ella se puede
observar con bastante claridad el problema.
Una vez indicados todos los datos necesarios del problema pasamos a su
resolución con la función max_flow en la cual debemos de indicar el nodo de origen en
source, el nodo de destino target y el grafo en graph. También se puede indicar su
capacidad en capacity, sin embargo, si ya la hemos indicado, como es nuestro caso, no
le introducimos los valores usando NULL y así considere los indicados anteriormente,
Al introducir la función no se mostrará directamente la solución, sino que
debemos pedir que la muestre mediante el comando $value el cual mostrará el flujo y el
comando $flow que mostrará los flujos en los arcos.
Para el ejercicio puesto en práctica se obtiene un flujo de 17 y los flujos de los
arcos del nodo 1-2, 1-3, 2-4, 2-5, 3-4, 3-5, 4-6 y 5-6 es de 7, 10, 2, 5, 6, 4, 8 y 9
respectivamente.
Resolución con POM-QM®
El problema de máximo flujo puede ser resuelto mediante POM-QM® ya que
cuenta con una pestaña específica para este tipo de ejercicios dentro de la opción de
Networks llamada Maximal Flow.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 58
Debemos de indicar, como anteriormente, el número de ramas con las que
cuenta nuestro problema, y a partir de esta información, introducimos la capacidad que
tendrá cada uno de los arcos.
En este caso también se incluye una columna llamada Reverse Capacity en la
cual se podrá indicar si hubiese capacidades negativas, ya que en la columna anterior de
Capacity, no nos deja indicar valores negativos.
Una vez que obtenemos la solución POM-QM® nos mostrará una tabla (Figura
4.19) con el flujo máximo posible y cada uno de los arcos con sus capacidades. No
obstante, también nos permite ver un tabla donde se muestran los caminos con cada
capacidad que tendrán cada uno y por tanto el flujo acumulado, siendo el máximo que
se pueda transportar.
Figura 4.19: Solución flujo máximo POM-QM®
5. CONCLUSIÓN
A partir de los conocimientos básicos adquiridos durante el estudio teórico de
Investigación Operativa en el grado, se ha podido desarrollar esta investigación para su
aplicación en diferente softwares, que nos permite concluir y demostrar que lo ideal es
poder usar un conjunto de ellos, que permita obtener una información completa y detalla
sobre los posibles problemas a los que nos enfrentemos, como evitar algunos errores
que pudiesen contener.
Tras este proyecto, podemos observar como R® nos permite realizar una gran
variedad de problemas, no solo ofrece una gran cantidad de paquetes para la
Investigación Operativa, sino que también (aunque no se haya llevado a cabo en este
estudio) en muchas otras ramas. POM-QM® ofrece una metodología muy sencilla de
entender, pero no podemos resolver todos los tipos de problemas que hemos planteado,
al menos, en esta investigación, a pesar de ser un software orientado principalmente al
ámbito de la Investigación Operativa.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 59
Una de las partes más importantes y que considero que da mucho valor al
software R® es el hecho de que sea un programa formado por aportaciones de muchas
personas, es decir, está formado por los paquetes que desarrollan y lo aportan al
software para un uso colectivo de los demás. Esto ha permitido que las deficiencias del
software puedan ser compensadas por otra persona. No obstante, hay que considerar,
que debido a que estas aportaciones, aunque en la mayoría de sus son casos correctas y
completas, pueden surgir errores en algunas de ellas, pero por ello se han desarrollado
una gran variedad paquetes, gracias a la gran cantidad de aportaciones que se pueden
hacer, como con otros softwares, para asegurar su correcto funcionamiento.
Es interesante destacar también la facilidad para obtener el software R® ya que
se puede conseguir de forma gratuita, a diferencia de POM-QM®, el cual no es libre y
necesitamos una licencia. Aunque la Universidad facilita el acceso a algunos de estos
programas, en ocasiones no se obtiene el rendimiento deseado, ya sea por la versión
disponible o por compatibilidades con los ordenadores personales.
Aunque la forma de trabajar con POM-QM® sea más sencilla a priori que R®,
una vez que se adquieren los conocimientos básicos sobre su funcionamiento se
convierte en un software más sencillo de lo que inicialmente se pueda pensar, ya que si
se comprende el uso de los paquetes y se sabe obtener información sobre ellos, puede
volverse, en la mayoría de los casos, un programa rutinario.
Finalmente, esta investigación nos ha permitido profundizar en un tema que
actualmente es la realidad en el mundo laboral y que nos ayudará a poder
desenvolvernos ante diferentes situaciones con los softwares informáticos que puedan
ser necesarios en un futuro utilizar.
6. BIBLIOGRAFÍA
Alonso Revenga, J.M. (2008), Flujo en Redes y Gestión de Proyectos,
Universidad Complutense de Madrid, Ed: Gesbiblo, S.L.
Céspedes Trujillo, N. (2007), Programación Lineal: su aplicación a los
procesos agropecuarios, Cuba, Ed: Universitaria.
Chavez Quisbert, N. (2011) “Modelos de programación lineal y no lineal con
multiobjetivos”, Revistas Bolivianas, La Paz. Disponible on line:
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 60
http://www.revistasbolivianas.org.bo/scielo.php?pid=S9876-
67892011000100007&script=sci_arttext
Eppen, G.D., Gould, F.J., Schmidt, C.P., Moore, J.H., Weatherford, L.R. (2000),
Investigación de Operaciones en la Ciencia Administrativa, México, Ed: Pearson.
Fontenla Cadavid, M. (2014), Optimal Trees, Coruña, Disponible on line:
http://eio.usc.es/pub/mte/descargas/ProyectosFinMaster/Proyecto_1075.pdf.
Frías Bustamante, M., Martínez Rodríguez, A. (2006), Programación Lineal
Una Introducción, Universidad de Jaén, Ed: Grupo Editorial Universitario.
Guerrero Salas, H. (2009), Programación Lineal aplicada, Bogotá, Ed: Ecoe
Ediciones.
Ipanaqué Chero, R. y Velesmoro León, R. (2005), BREVE MANUAL DE
MATHEMATICA 5., Perú, Ed: grupo eumed.net. Disponible on line:
http://www3.uji.es/~planelle/APUNTS/IAQ/manual_math.pdf.
Kong, M. (2010), Investigación de operaciones: programación lineal.
Problemas de transporte. Análisis de redes, Perú, Ed: Fondo Editorial de la Pontificia
Universidad Católica del Perú.
Martín Martín, Q. (2003), Investigación Operativa. Salamanca, Ed: Salamanca:
Hespérides, D.L.
Martínez Rodríguez, A.M. (2017), Redes de Transporte, disponible en la
plataforma de la Universidad de Jaén, Ampliación de Investigación Operativa.
Morales Medina, M.A. (2006), La leyenda de Dantzig. Disponible on line:
http://gaussianos.com/la-leyenda-de-dantzig/.
PHPSimplex (2006), Teoría del método simplex, Teoría. Disponible on line:
http://www.phpsimplex.com/teoria_metodo_simplex.htm.
Piedra Hernández, V. S. y Paternostro Movilla, C. A. (2009), Aplicaciones de la
Tería de Grafos en la Informática, Bogotá, Disponible on line:
http://javeriana.edu.co/biblos/tesis/ciencias/tesis341.pdf
Ramos, A. Investigación Operativa y Optimización, Universidad Pontificia
Comillas Madrid. Disponible on line:
https://www.iit.comillas.edu/aramos/simio/transpa/t_mod1_ar.pdf.
R Seek. Disponible on line: http://rseek.org/.
Resolución de problemas de Investigación Operativa mediante diferentes softwares
2017
Página 61
Rodriguez Huertas, R. y Gámez Mellado, A. (2002), Investigación Operativa
Teoría, Ejercicios y Prácticas con ordenador, Universidad de Cádiz, pp. 133- 155 Ed:
Servicio de Publicaciones de la Universidad de Cádiz.
S. Hillier, F., J. Lieberman, G. (2010), Introducción a la Investigación de
Operaciones, Stanford University, Ed: McGraw-Hill Interamericana.
The R Project for Statistical Computing. Disponible on line: https://www.r-
project.org/.