Matemática III

Sección: 1.05

Ciclo: 2021-1

Proyecto
Teoría de grafos en red de vuelos

Profesor: Rosulo Perez Cupe

César Alejandro Ortiz Martinez (Lider) 201810312 100%
Leonardo Fabricio Yupanqui Mera 202010434 100%
Alberto Alejandro Pelaez Sagastegui 201710620 100%
Nayeli Cibelly Navarro Pizarro 201910240 100%
Rodrigo Gabriel Salazar Alva 202010387 100%

Fecha de entrega
01 de Junio

Junio 2021
 Matemática III

ÍNDICE

ÍNDICE 1

I. INTRODUCCIÓN 4
I.I. Tema del Proyecto 4
I.I. Objetivos 5
I.I.I Objetivo Principal 5
[Link]. Justificación de la elección del tema 6
I.V. Identificación del problema 7

II. MARCO TEÓRICO 10

II.I Antecedentes 11
[Link] Base teórica 12
[Link] Conceptos Clave 20

III. METODOLOGÍA 22
I.I Planteamiento del sistema de ecuaciones 22
[Link] Resolución de sistemas de ecuaciones 23
[Link].I Eliminación Gaussiana con pivote: 23
[Link] Método Crout: 27
[Link] Definición del grafo y la búsqueda de la ruta mas barata 30

IV. DESARROLLO 32
IV.I Interpretación del problema 32
[Link] Planteamiento del problema 32
[Link] Procedimiento 33
[Link].I Asignación de variables 33
[Link] Definición de rutas 34
[Link] Sistema de ecuaciones 35

2
 Matemática III

[Link] Resolución de sistema matricial 37

[Link].I Eliminación Gaussiana (Con pivoteo) 37
[Link] Factorización LU - Crout 40
[Link].V Planteamiento de Grafo y Resolución de camino mínimo 52
[Link] Interpretación de resultados 55

V. CONCLUSIONES 58

VI. BIBLIOGRAFÍA 61

VII. ANEXOS 63

3
 Matemática III

I. INTRODUCCIÓN

I.I. Tema del Proyecto

La cotidianización del transporte aéreo es una de las más importantes

hazañas de la humanidad durante el último siglo que ha resultado en la
creación de complejas redes de aeropuertos profundamente interconectadas
por vuelos tanto a nivel nacional como internacional. Actualmente, existe un
creciente interés por el estudio de estas redes mediante sus
representaciones aproximadas en grafos.

La teoría de grafos es una rama relativamente nueva de investigación de las

matemáticas cuyo objeto de estudio son los grafos, sus propiedades y
conceptos relacionados como caminos y ciclos. Este es un área con
importante solapamiento con el álgebra lineal al frecuentemente emplear
matrices para la representación de sus diversos elementos, especialmente
para su modelamiento y cálculo en computadoras. Mediante la aplicación de
este área se ha podido representar y resolver diversos problemas de la vida
real como la síntesis de circuitos secuenciales y la creación de algoritmos de
motores de búsqueda.

El tema del presente trabajo es la aplicación de la teoría de grafos y álgebra

lineal en redes de vuelos para hallar el camino óptimo entre dos ciudades.
Para este fin, se tomarán como datos los precios de diferentes planes de
vuelo de la aerolínea internacional LATAM con el fin de reconstruir un grafo
pesado en base a un sistema de ecuaciones lineales. Finalmente, con este
grafo aplicaremos el algoritmo de Dijkstra para hallar la ruta de menor costo
entre Lima y Toronto.

4
 Matemática III

I.I. Objetivos

I.I.I Objetivo Principal

- Plantear un sistema de ecuaciones lineales para describir un sistema

de rutas aéreas comerciales y determinar la ruta más barata aplicando
la teoría de grafos.

[Link] Objetivos Particulares

- Recolectar datos reales de rutas de vuelos en aerolíneas comerciales

para construir un sistema de ecuaciones lineales.
- Emplear el álgebra lineal para plantear o replantear el sistema
ecuaciones y verificar que tenga solución
- Implementar scripts para facilitar la resolución de sistemas matriciales
mediante herramientas computacionales como matlab usando los
metodos de eliminacion gaussiana con pivoteo y factorizacion LU
(crout).
- Aplicar el algoritmo de Dijkstra sobre un grafo ponderado para hallar el
trayecto de menor costo.

5
 Matemática III

[Link]. Justificación de la elección del tema

La teoría de grafos es un área con gran potencial para la resolución de

problemas al permitir representar de forma matemática una gran diversidad
de fenómenos como las cadenas de infección de epidemias o redes de
distribución de servicios públicos. No obstante, no siempre se cuenta con
todos los datos listos para un procesamiento directo con algoritmos
computacionales conocidos sino que es necesario inferir o aproximar
modelos en base a datos más complejos. En este sentido, el álgebra lineal
presenta una posible solución a este problema poco explorado que es la
reconstrucción de grafos ponderados en la cual creemos que se debería
profundizar. Asimismo, la información académica disponible sobre la
aplicación de este campo en el análisis de redes de vuelos es bastante
escasa y comúnmente se limita únicamente a la descripción de estas redes
en vez de resolver problemas concretos. Por estos motivos, este trabajo
busca proponer una posible aplicación de estas áreas en la resolución de
problemas concretos con el potencial de que nuestros conocimientos y
resultados obtenidos puedan servir en un futuro como base para otras
investigaciones más profundas en este campo.

6
 Matemática III

I.V. Identificación del problema

Dentro de una subred de aeropuertos en la que opera LATAM Airlanes, esta

empresa desea ofrecer el plan de vuelo más económico para un vuelo con
partida desde Lima y arrive en Toronto para poder competir en el mercado de
transporte aéreo sabiendo que este es un destino con creciente popularidad.
Lamentablemente, para poder calcular la ruta óptima no se cuenta con los
datos exactos para los costos para viajar de un aeropuerto a otro. No
obstante, si sabe el costo de múltiples rutas ya existentes entre estos dos
destinos y alrededores con diferentes escalas dentro de esta subred. Nuestro
objetivo es calcular los precios de vuelo entre aeropuertos elegidos a partir
de los precios de las rutas conocidas, con el fin de construir un grafo
apropiado para uso en algoritmos de búsqueda de caminos mínimos y
determinar de esta manera cuál es la ruta que LATAM Airlines debería
implementar, de no estar disponible aun, y enfocarse.

Para el planteamiento de este problema, no se toma en cuenta los

descuentos proporcionados por la aerolínea, ya que estos varían
dependiendo de la temporada y dificultan el planteamiento de un sistema
lineal. Asimismo, se asume que el costo de viaje entre dos aeropuertos
adyacentes es el mismo en ambas direcciones. Los datos recolectados de
LATAM airlines el 15 de Mayo de 2021 son los siguientes:

7
 Matemática III

Figura 1
Rutas alternativas para el viaje de Lima a Toronto.

Nota. Elaboración propia con Matlab.

8
 Matemática III

Figura 2
Tabla de precios reales tomados de la página de LATAM.

Nota. Elaboración propia.

Figura 3
Tabla descriptiva de los vuelos que se toman por ruta.

Nota. Elaboración propia.

9
 Matemática III

Teniendo en cuenta los datos recolectados, estableceremos un sistema de

ecuaciones para calcular el precio de cada vuelo entre cada par de
aeropuertos directamente conectados. Luego, resolveremos el sistema de
ecuaciones empleando eliminación gaussiana con pivoteo y factorización LU
(crout). El grafo ponderado construido se usará como input para hallar la ruta
mínima mediante el algoritmo de Dijkstra.

II. MARCO TEÓRICO

II.I Antecedentes

La teoría de grafos es una área de las matemáticas que ha recibido especial

atención en los últimos años debido a su capacidad de simplificar en gran
medida el proceso de modelación de sistemas complejos como el
movimiento de partículas atómicas, redes eléctricas o modelos
epidemiológicos de contagio. Su aplicación tiene gran potencial en el campo
del transporte y la definición de nuevas rutas aéreas. Algunas trabajos
previos relacionados se describen a continuación:

En Puchades V., Mula J. y Rodríguez A. (2008) se estudia el caso de la

empresa Semacaf Maquinas de Cafe S.L la cual que pertenece al rubro de la
distribución. En este trabajo, Rodriguez aplica el algoritmo del “Problema del
Viajante”, para determinar mediante el uso de grafos, rutas alternativas que
permitan optimizar la tarea de reparto reduciendo costos y tiempo. Si bien
este trabajo no se centra especialmente en rutas de vuelo, nos muestra el
potencial que tienen los grafos en el área de transporte en general.

Asimismo, en Restrepo C., Hernán J., Sanchez C. y Jairo J. (2004) se abarca

el problema de rutas mínimas al buscar determinaron las distancias más
cortas de las rutas de la ciudad de Santa Rosa de Cabal mediante la

10
 Matemática III

aplicación de la teoría de grafos junto al algoritmo dijkstra. Este trabajo tiene

un objetivo similar al del presente trabajo pero se trabaja con el caso ideal de
un grafo pesado ya conocido.

11
 Matemática III

Por otro lado, en Guamanga J. y Granada A. (2019) propusieron mejoras en

el algoritmo de Dijkstra para mejorar la conectividad aérea de latinoamérica
y el Caribe. En su trabajo, ellos aplicaron la teoría de redes sociales junto a la
teoría de grafos para optimizar el proceso de selección de rutas, obteniendo
como resultado el aumento de los vuelos comerciales.

Por último, trabajos más actuales como Gomez R., Zuluaga A. y Espinoza J.
(2015) demuestran el potencial de la teoría de grafos para diseñar una red de
distribución de productos cárnicos lo más eficientemente posible teniendo en
cuenta el tiempo y distancia de los pedidos de los clientes.

[Link] Base teórica

Teoría de grafos - El acertijo de los “puentes de Köningsberg (1736)

En 1736, Leonhard Euler publicó un artículo donde resolvió este problema

definiendo los conceptos que sentaron las bases de lo que actualmente se
conoce como la teoría de grafos.

La ciudad de Königsberg, en Prusia Oriental, estaba dividida en cuatro zonas

por el río Pregel. Siete puentes comunicaban estas regiones, tal y como se
muestra en el dibujo. Los habitantes de dicha ciudad debían recorrer grandes
trayectos tratando de encontrar una forma de caminar por la ciudad,
cruzando cada puente una sola vez, y regresar al lugar de partida. (Rosen,
2012)

Definición de grafo (no dirigido):

12
 Matemática III

Un grafo G se puede definir como un par (V , E) donde V es un conjunto de

vértices y E un conjunto de aristas.(Galvin, 2009)

Dentro del contexto de grafos los vértices (o también llamado nodos) se

entiende como los elementos principales de un grafo cuya naturaleza es
discreta y cuyo significado varía dependiendo del sistema que se desea
modelar, mientras que las aristas son las conexiones entre pares de nodos
que representan la existencia de una relación entre estos.

Para ejemplificar, para resolver el acertijo previamente mencionado, Euler

creó un grafo G=(V , E) donde V ={a , b , c , d } era el conjunto de vértices
donde cada vértices representaba una zona de la ciudad y
E={e 1 ,e 2 , e3 , e 4 , e5 , e6 , e 7 } era el conjunto de artistas que representan la
existencia de un puente entre cada par de ciudades como se muestra en la
Figura 4.

Figura 4
Representación de Euler del problema

Nota. Adaptado de Galvin, 2009, Discrete Mathematics, Spring 2009 Graph

theory notation ([Link]
[Link]).

13
 Matemática III

Donde las incidencias de las aristas son:

e 1=e 2={a , b }
e 3=e 4 ={b . c }
e 5={a , d }
e 6={b , d }
e 7={c , d }

Definición de grafo ponderado (no dirigido):

Un grafo ponderado se puede entender como una extensión de la definición
previa de grafo donde todo elemento e ∈ E cumple con tener exactamente una
solución con la función de peso asociada al grafo (Rosen, 2012):
w (e)=PESO
El peso de una arista es un número (por lo general perteneciente a los
reales) que describe alguna propiedad de los vértices que conecta.

En el ejemplo anterior de Euler, su grafo podría ser extendido a un grafo

ponderado en el que el peso de cada arista representa la longitud de cada
puente en metros.

Definición de camino:
Un camino en un grafo se define como una sucesión finita alternada de
vértices y aristas pertenecientes al grafo donde se cumple que cada arista
conecta al vértice anterior y siguiente a esta en la sucesión. Los caminos se
pueden representar matemáticamente como (Rosen, 2012):
π n :a , b , c , d , e , f , g , h…

Donde n es el número de vértices que se recorre en el camino y

a , b , c , d ,e , f , g ,h representa la sucesión de vértices y aristas recorridas.

14
 Matemática III

El costo de un camino se entiende como la sumatoria de los pesos de todas

las aristas recorridas en este.
e ∈E
w (r )= ∑ w (e)
e

Matriz de adyacencia:
Una matriz de adyacencia es una representación matricial de un grafo
simple.

Para un grafo ponderado simple (simple = máximo una arista conecta cada
par de vértices) la matriz de adyacencia se construye como una matriz A de
dimensionesn x n donde n=¿ V ∨¿ . (Rosen, 2012)

Cada elemento Ai , jse define como:

● Ai , j=∞o Ai , j=0 si los vértices i y j no están conectados (Matlab usa 0)
● Ai , j=w(ei , j) si los vértices i y j están conectados, donde e i , j es la
arista que los conecta

Figura 5
Matriz de adyacencia

Nota. Adaptado de Grafo Ponderado[Imagen] por dar15, 2011, Matriz de

adyacencia ([Link]

Algoritmo de Dijkstra:

15
 Matemática III

El algoritmo de Dijkstra resuelve el problema de encontrar el camino mínimo

desde un origen a un destino. Resulta que uno puede encontrar el camino
mínimo desde un origen dado a todos los vértices de un grafo al mismo
tiempo; de ahí, este problema a veces se llama el problema del camino
mínimo con un origen único. De hecho, este algoritmo se puede utilizar para
entregar el conjunto de aristas que conectan todos los vértices tal que la
suma de las longitudes de las aristas desde el origen hasta cada nodo sea
mínimo. ( Rodríguez, 2009)

Proceso para el algoritmo de Dijkstra :

El algoritmo requiere como datos de entrada un grafo ponderado
G=(V , E , w), un vértice de origen s y un vértice de fin u.

El objeto resultante del algoritmo es un árbol generador T con el camino

mínimo con raíz s.

Los detalles de la implementación de este algoritmo se pueden ver descritos

a continuación en la Figura 6 que contienen un pseudocódigo
correspondiente.

16
 Matemática III

Figura 6
Pseudocódigo del algoritmo de Dijkstra

Nota. Adaptado de Algoritmo: DIJKSTRA por Rodriguez, 2009. .Problemas

De Optimización En Árboles Generadores, Universidad Politécnica de Madrid
([Link]
descargas/Memoria_Teoria.pdf)

17
 Matemática III

Eliminacion Gaussiana con pivoteo:

Este es un método para la resolución de un sistema de ecuaciones en su

forma matricial Ax=b.

Este método se basa en la sustitución de un sistema de ecuaciones lineales

por una matriz escalonada superior. Para ello, teniendo un sistema matricial
definido como Ax=b se define una nueva matriz extendida como Ab= A∨b.
Mediante operaciones elementales el sistema se simplifica a una forma
escalonada, semejante a la de la Figura 7. (Rosen, 2012)

Figura 7
Ejemplo de matriz escalonada

Nota. Elaboración propia.

Con esta matriz se puede crear un nuevo sistema equivalente A ' x=b '
fácilmente resoluble de forma inversa: empezando de la ecuación inferior a la
superior resolviendo un nuevo valor(es) de x i en cada paso.

18
 Matemática III

Método Crout - Factorización LU:

Este es otro método para la resolución de un sistema de ecuaciones en su
forma matricial Ax=b. En este caso, este método se basa en la
descomposición de la matriz A en el producto de L(matriz triangular inferior) y
U(matriz triangular superior). Este proceso consiste en dos partes principales
(Rosen, 2012):

● Cálculo de la matriz L mediante eliminación por columnas

usando operaciones elementales.

Figura 8
Cálculo de L.

Nota. Elaboración propia.

● Construcción de la matriz triangular superior U mediante

elementos obtenidos durante el proceso anterior: Con la
formación de la matriz escalonada de L se obtuvieron
u12 ,u13 y u 23las cuales forman a ser parte de la matriz U.

19
 Matemática III

Figura 9
Construcción de U

Nota. Elaboración propia.

Una vez obtenido este resultado se vuelve fácil resolver el sistema de

ecuaciones como dos sistemas encadenados con matrices triangulares:

LZ=b ; Donde Ux=Z

El sistema Ux=Z se resuelve de forma inversa (de la ecuación inferior a
superior) y posteriormente LZ=b se resuelve de forma directa (de la
ecuación superior a inferior)

[Link] Conceptos Clave

● Red de vuelos: Modelo de rutas de transporte aéreo representable

mediante un grafo como el que se puede apreciar en la Figura 10. El
conjunto de vértices V representa los aeropuertos de la red y el
conjunto de aristas E representa la existencia entre un vuelo existente
entre un par de aeropuertos. El pesow (e) de una arista e puede
representar diferentes características dependiendo del contexto.
Algunas definiciones comunes son: precio, tiempo y distancia.

20
 Matemática III

Figura 10
Ejemplo de red de vuelos

Nota. Adaptado de Grafos con pesos por Antony, 2011, Algoritmos de

caminos más cortos ([Link]
-caminos-m-s-cortos).

● Ruta de vuelo: Pasaje comparable que lleva de un destino u a un

destino v con 0 a múltiples escalas intermedias. Esta se puede
representar como un camino dentro de una red de vuelos.

21
 Matemática III

III. METODOLOGÍA

Para resolver el problema usamos la metodología planteada en el diagrama

de la Figura 11.
Figura 11
Metodología

Nota. Elaboración propia.

I.I Planteamiento del sistema de ecuaciones

El planteamiento del sistema de ecuaciones lineales se realiza mediante el

planteamiento de las ecuaciones lineales de pesos de cada ruta. El costo
total de una ruta se puede representar como la sumatoria de los pesos de
todas sus aristas:

22
 Matemática III

a∈ A
w (r )= ∑ w (a)
a

Teniendo aristas etiquetadas, esto también se puede representar como la

ecuación lineal:
c 1 x 1 +c 2 x 2 +c 3 x3 .. c n x n=k
Donde k =w (r ) es el costo total de la ruta, x irepresenta el costo de la arista a i
y c ies un coeficiente que indica cuantas veces la ruta pasa por la arista a i.
Con ello, es posible representar esto como una sistema matricial Cx=K .
Asimismo, cabe denotar que, asumiendo todas las rutas a lo máximo cada
arista una única vez, la matriz C será una matriz de 1’s y 0’s donde 1
representa que el camino recorre la arista correspondiente y un 0 que no.

[Link] Resolución de sistemas de ecuaciones

Para resolver los sistemas de ecuaciones obtenidos se usa la factorización o

descomposición para adquirir las soluciones más eficientemente. Por ende,
se usará los siguientes métodos de factorización:

[Link].I Eliminación Gaussiana con pivote:

Teniendo un sistema matricial definido como Ax=b se define una nueva

matriz extendida como Ab= A∨b.

Sobre este nuevo sistema se aplica el siguiente algoritmo:

1. El contexto se define como la submatriz de Abconstruida como

n ,m
Contexto=(a ij )i , j =kdonde a ijson los elementos de Ab, n=¿número de
filas y m=¿ número de columnas.

El contexto se inicia como como la totalidad de la matriz Ab (k =1)

23
 Matemática III

2. Mientras k ≥ n y k ≥m se elimina la siguiente columna:

a. Pivoteo: Se busca dentro del contexto cuál es el major valor de
la primera columna. En caso de ser distinto al actual se
intercalan las filas.

Figura 12
Ejemplo de pasos intermedios - Eliminacion Gaussiana

Nota. Elaboración propia.

b. Eliminación: El elemento pivote se define como el primer

elemento del contexto actual ( piv=akk ). Para cada fila posterior
a k +1 se calcula el coeficiente de eliminación¿ c como el
coeficiente por el que se debe multiplicar el elemento pivote
para que, al sumarlo con el primer elemento de esta fila el
resultado sea 0. Con este valor se realiza la operación entre
filas: f =f −c∗f k.

c. Reducción de contexto: Una vez finalizado los cálculos

correspondientes se reduce el contexto incrementando k en 1

3. La matriz resultante es el resultado. Su forma debe ser semejante a la

mostrada en la Figura 13.

24
 Matemática III

Figura 13
Resultado - Eliminacion Gaussiana

Nota. Elaboración Propia.

Una vez obtenido este resultado se vuelve fácil resolver el sistema de

ecuaciones de forma inversa (de abajo hacia arriba).

Este algoritmo se ha implementado en la script Gauss_Pivoteo_Parcial.m

en matlab para su uso durante el desarrollo:

25
Matemática III

26
 Matemática III

[Link] Método Crout:

Existen diferente algoritmos para hallar las matrices LU de un sistema Ax=b

de tipo crout. En este caso, el algoritmo que se usará es el siguiente:

1. El contexto se define como la submatriz de A construida como

n
Contexto=(a ij )i , j =kdonde a ijson los elementos de A , n=¿número de filas
y columnas.

2. Se define la matriz U inicial como una matriz identidad de dimensiones

de A .

3. Mientras k ≥ nse siguen calculando las matrices:

a. Recuperación de U:
Se recupera la primera fila del contexto actual y se divide por un
coeficiente ¿ s tal que el primer elemento de la fila sea igual a 1.
La fila obtenida de esta división se pone en las posiciones
correspondientes en la matriz U.

b. Cálculo de L:
El elemento pivote se define como el primer elemento del
contexto actual ( piv=akk ). Para cada columna posterior a k +1 se
calcula el coeficiente de eliminación¿ r como el coeficiente por
el que se debe multiplicar el elemento pivote para que, al
sumarlo con el primer elemento de esta columna el resultado
sea 0. Con este valor se realiza la operación entre filas:
c=c−r∗c k.

27
 Matemática III

c. Reducción de contexto: Una vez finalizado los cálculos

correspondientes se reduce el contexto incrementando k en 1

4. La matriz modificada de A es L y la matriz U es su matriz U

correspondiente.

Una vez obtenido este resultado se vuelve fácil resolver el sistema de

ecuaciones como dos sistemas encadenados con matrices triangulares:

LZ=b ; Donde Ux=Z

Este algoritmo se ha implementado en la script crout.m en matlab para su

uso durante el desarrollo:

28
Matemática III

29
 Matemática III

[Link] Definición del grafo y la búsqueda de la ruta mas barata

Una vez que encontremos la solución al sistema de ecuaciones planteado, se

procede a la construcción del grafo la búsqueda de la ruta más barata,
utilizando el los siguientes scripts:

Script para la definición de matriz de adyacencia en base a los pesos

hallados:

30
 Matemática III

Asimismo, para aplicar Dijkstra se usará la función shortestpath (G,a,b) de

matlab para aplicar el algoritmo de Dijkstra en un grafo G y hallar la ruta de
menor peso entre a y b y su valor.

La función shortestpah usa este algoritmo por defecto para grafos

ponderados con todos sus pesos no negativos.

31
 Matemática III

IV. DESARROLLO

IV.I Interpretación del problema

Tenemos diferentes rutas para la red de vuelo de una aerolínea

(representada por el grafo de la figura N 1). A partir de los precios de cada
ruta, hallaremos el precio de un boleto de avión entre todos los aeropuertos
adyacentes (conectados por una arista) para reconstruir el grafo. Con el grafo
resultante, calcularemos la ruta de mínimo costo entre Lima y Toronto
aplicando el algoritmo de Dijkstra.

[Link] Planteamiento del problema

Para resolver el problema, representamos el sistema en su forma matricial.

Posteriormente, resolvemos la matriz aumentada empleando el método de
eliminación gaussiana con pivoteo y metodo de factorizacion LU crout, y
como resultados obtendremos los precios de vuelo.

Con el fin de hacer el sistema matricial resoluble, se han realizado ajustes a

los precios de cada ruta:
Figura 14
Tabla descriptiva de los vuelos que se toman por ruta

32
 Matemática III

Nota. Elaboración propia.

ruta 1: Lima - Nueva York - Toronto, con un precio de $765.98

ruta 2: Lima - México - Toronto, con un precio de $786.4
ruta 3: Colombia - Nueva York - Toronto, con un precio de $812.79
ruta 4: 2 vuelos distintos, Lima - Colombia - Nueva York y México - Nueva
York - Toronto, con un precio de $1427.99 por los 2.
ruta 5: Lima - Colombia - Nueva York - Toronto, con un precio de $1119.39
ruta 6: Lima - México - Nueva York - Toronto, con un precio de $945.69
ruta 7: México - Nueva York - Toronto, con un precio de $564.99

[Link] Procedimiento

[Link].I Asignación de variables

Para poder representar los precios de las rutas de vuelo de forma algebraica
es necesario poder diferenciar cada aristas del grafo con lo que a
continuación asignamos una etiqueta a cada vuelo entre aeropuertos
adyacentes y su costo:

Lima - Nueva York = a1

Lima - Colombia = a2
Lima - México = a3
Colombia - Nueva York = a4
Nueva York - Toronto = a5
Nueva York - México = a6
México - Toronto = a7

Asimismo, para representar el peso correspondiente a cada arista (a i) se usar

la siguiente notación:

33
 Matemática III

x i=w (a i)

[Link] Definición de rutas

ruta 1: Lima - Nueva York - Toronto, con un precio de $765.98

ruta 2: Lima - México - Toronto, con un precio de $786.4.
ruta 3: Colombia - Nueva York - Toronto, con un precio de $812.79
ruta 4: 2 vuelos distintos, Lima - Colombia - Nueva York y México - Nueva
York - Toronto, con un precio de $1427.99 por los 2.
ruta 5: Lima - Colombia - Nueva York - Toronto, con un precio de $1119.39
ruta 6: Lima - México - Nueva York - Toronto, con un precio de $945.69
ruta 7: México - Nueva York - Toronto, con un precio de $564.99

De esta forma, nuestras rutas serían las siguientes:

ruta 1 = π 2 : Lima , a 1 , NuevaY ork , a5 ,Toronto con w (ruta 1)=765.98

ruta 2 = π 2 : Lima , a 3 , México , a7 , Toronto con w (ruta 2)=786.4
ruta 3 = π 2 :Colombia , a4 , NuevaYork , a5 ,Toronto con w (ruta 3)=812.79
ruta 4 = π 2 : Lima , a 2 , Colombia , a4 , Nueva York +
π 2 : México , a6 , Nueva York , a5 ,Toronto con w (ruta 4)=1427.99
ruta 5 = π 3 : Lima , a 2 , Colombia , a 4 , Nueva York , a 5 , Toronto
con w (ruta 5)=1119.39
ruta 6 = π 3 : Lima , a 3 , México , a6 , NuevaYork , a5 , Toronto
con w (ruta 6)=9 4 5.69
ruta 7 = π 2 : México , a6 , Nueva York , a5 ,Toronto con w (ruta 6)=564.99

Sabiendo que el costo de una ruta es la suma de los costos de todos los
vuelos intermedios presentes en esta podemos plantear la ecuación lineal de
una ruta como:

34
 Matemática III

a∈ A
w (r )= ∑ w (a)
a

Donde A es el conjunto de todas las aristas pertenecientes a la ruta.

De esta forma obtenemos una ecuación lineal por ruta:

ruta 1: x 1+ x5 =$ 765.98
ruta 2: x 3 + x7 =$ 786.4
ruta 3: x 4 + x 5=$ 812.79
ruta 4: x 2+ x 4 + x 6+ x5 =$ 1427.99
ruta 5: x 2+ x 4 + x 5=$ 1119.39
ruta 6: x 3 + x 6+ x 5=$ 945.69
ruta 7: x 6 + x 5=$ 564.99

[Link] Sistema de ecuaciones

En base a las ecuaciones de peso de cada ruta podemos plantear el

siguiente sistema de ecuaciones como su recolección, representada en la
Figura 15.

Figura 15
Sistema de ecuaciones

Nota. Elaboración propia.

35
 Matemática III

Para poder crear una matriz, completamos con 0’s el sistema de ecuaciones
para incluir todas las incógnitas de forma ordenada. El sistema de
ecuaciones resultante se aprecia en la Figura 16.

Figura 16
Sistema de ecuaciones rellenado con ceros

Nota. Elaboración propia.

Con este sistema resultante es posible reescribir en su forma matricial como

se muestra a continuación.

Figura 17
Sistema matricial

Nota. Elaboración propia.

36
 Matemática III

[Link] Resolución de sistema matricial

[Link].I Eliminación Gaussiana (Con pivoteo)

Para resolver por eliminación gaussiana primero se plantea la Matriz

Aumentada mostrada en la Figura 16.
Figura 18
Matriz aumentada

Nota. Elaboración propia.

Utilizando Gauss_Pivoteo_Parcial.m con esta matriz como input obtenemos

la matriz escalonada:

37
 Matemática III

(...)

38
 Matemática III

Obteniendo como resultado el sistema equivalente Ax=bsiguiente:

39
 Matemática III

Mediante resolución inversa (ecuaciones lineales de abajo hacia arriba) del

sistema de matriz escalonada hallado obtenemos los costos resultantes:

[Link] Factorización LU - Crout

Para resolver mediante crout usaremos la script crout.m previamente

mencionada. Para ello, primero planteamos el sistema matricial LUx = b en
matlab de la siguiente forma:

40
 Matemática III

No obstante, si se intenta resolver el sistema matricial planteado

directamente mediante la función creada crout.m, el resultado dará error al
haber casos en los que se dividirá entre 0 por el algoritmo utilizado,
resultando en Nan’s y Inf’s como se muestra a continuación. Es necesario
realizar un pivoteo.

41
Matemática III

42
 Matemática III

Inicio de problema desde paso 3 al tener que dividir entre 0:

(...)

Resultado

43
 Matemática III

Por lo tanto, es necesario hacer un reordenamiento de la matriz. Para ello se

ha usado como función auxiliar la función integrada de matlab lu para
recuperar la matriz de reordenamiento P mostrada a continuación:

44
 Matemática III

Utilizamos la matriz “P” para ordenar las filas de ambas matrices: Matrix_coef
y Matriz_precios. Primero, multiplicamos la matriz de permutaciones por la
matriz de coeficiente.

Obtenemos nuestra nueva matriz de coeficientes:

45
 Matemática III

Posteriormente, multiplicamos la matriz de permutaciones por la matriz

precios
Obtenemos nuestra nueva matriz de precios:

46
 Matemática III

A continuación, factorizamos la nueva matriz de coeficientes (Matriz_Coef_P)

por el método de Crout.

47
 Matemática III

(...)

48
 Matemática III

Obtenemos el siguiente sistema expresado en su forma matricial

Figura 19
Sistema LUx = b.
L U X b

Nota. Elaboración propia.

49
 Matemática III

Donde b=¿ Matriz_Precios:

Reemplazando con Ux=Z

Figura 20
Sistema LZ = b.
L Z b

Nota. Elaboración propia.

LZ=b
−1 −1
L LZ=L b
−1
IZ=L b
−1
Z=L b

Calculamos Z:
resolvemos el sistema LZ=Matriz¿ :

50
 Matemática III

Con los valores de Z ahora resolvemos el sistema Ux=Z :

Figura 21
Sistema Ux = Z.
U X Z

Nota. Elaboración propia.

−1 −1
U Ux=U Z
−1
Ix=U Z
−1
x=U Z

51
 Matemática III

De esta forma, los precios obtenidos mediante corut son los anteriores.

[Link].V Planteamiento de Grafo y Resolución de camino mínimo

Al comparar los resultados obtenidos con ambos métodos encontramos que

la diferencia entre estos es mínima o nula con lo que trabajaremos con estas
como si fueran iguales. Con esta matriz X de pesos de hallada, podemos
reconstruir la matriz de adyacencia ponderada remplazando como:
Mi, j:
● Si existe un a k tal que incide en nodo i y nodo j ⇒ M i , j=a k
● Caso contrario ⇒ M i , j=0

Con esto obtenemos la matriz de adyacencia:

Donde:

52
 Matemática III

1:Lima, 2:Nueva York; 3: Toronto, 4: Mexico, 5:Colombio

De esta forma, nuestro grafo estaría representado de la siguiente manera

usando el siguiente código de matlab:

Figura 22
Grafo ponderado reconstruido

Nota. Elaboración propia usando Matlab.

53
 Matemática III

Finalmente procederemos a calcular la ruta más económica, empleando el

algoritmo dijkstra con la función integrada de Matlab shortestpath:
Figura 23
Ruta mínima

Nota. Elaboración propia usando Matlab.

54
 Matemática III

Obteniendo como resultado la siguiente ruta:

RUTA OPTIMA: LIMA, NUEVA YORK, TORONTO

PRECIO: 765.98 $

[Link] Interpretación de resultados

En base a los resultados del procedimiento podemos determinar que la ruta

de costo mínimo dentro de la subred de vuelos en la que se trabaja es Lima-
Nueva York-Toronto con costo de 765.98 $:
r = π 2 : Lima , a 1 , NuevaYork , a5 , Toronto
w (r )=765.98

Este resultado implica que el curso de acción aconsejado para LATAM

Airlines es priorizar sus recursos a esta ruta específica a fin de poder
competir en el mercado de compañías de vuelo internacional: una mayor
cantidad de aviones y frecuencia de vuelos a fin de poder maximizar sus
ganancias.

55
 Matemática III

El proceso realizado le garantiza a LATAM Airlines que dentro de la subred

escogida, no existe ninguna otra ruta más barata posible al haber obtenido
este resultado tomando en consideración todos los pesos de las aristas para
el algoritmo de optimización, donde estos pesos representan el precio
aproximado de un viaje entre cada par de aeropuertos directamente
conectados por algún vuelo.

Asimismo, el grafo resultante del procedimiento realizado es un elemento de

gran valor para la compañía LATAM ya que puede ser utilizado para resolver
múltiples consultas relacionadas al planeamiento de vuelos. Por ejemplo, en
caso de querer hallar la ruta mínima entre cualquier otro par de aeropuertos
pertenecientes a la subred, esto se podría resolver fácilmente aplicando
nuevamente el algoritmo de Dikstra pero con diferentes nodos iniciales y
finales. Además, de este grafo se puede deducir información valiosa como
que Nueva York es un aeropuerto central al ser el que tiene la mayor
cantidad de conexiones/aristas.

Estos vuelos se han obtenido mediante la resolución de las ecuaciones

lineales de los precios de las rutas conocidas usando dos métodos distintos:
eliminación gaussiana con pivoteo y crout. La diferencia entre los resultados
obtenidos entre estos métodos es despreciable debido al uso de
relativamente pocas variables y datos iniciales con pocas cifras significativas.
En el caso de usar datos iniciales más exactos, entonces la diferencia en
errores de aproximación entre ambos métodos probablemente sería más
visible En dicho caso el mejor método sería una factorización LU (crout), pero
con la adición de un pivoteo ya que, como se ha podido ver durante la
resolución de este problema, cuando se trabajan con matrices con múltiples
ceros, no usar pivote puede causar problemas.

56
 Matemática III

Si bien este modelo da información útil a LATAM Airlines, es importante

tomar en consideración que para poder crear este modelo se han necesitado
realizar reajustes en los precios exactos de las rutas para hacer que el
sistema sea resoluble. Este es evidente por ejemplo en la diferencia de costo
en la ruta Lima-Nueva York-Toronto: 765.98−745.97=$ 20.01.

En este sentido, si bien el modelo creado es una buena representación de

las redes de vuelos, esta es aproximada al haber sido necesarios ciertos
ajustes y suposiciones para facilitar el planteamiento y desarrollo del sistema
lineal. En caso de querer aplicar esto con la mayor fidelidad posible se
debería:

1. Trabajar en rangos de error al resolver los sistemas (el precio por el

que se valúa el costo de una vuelo entre dos aeropuertos adyacentes
no es fijo, varía de acuerdo a múltiples variables: temporada, ruta en la
que se encuentra, paquetes, etc.)

2. Tener en consideración los descuentos dados por los viajes en escala.

Esto es algo más complicado de modelar mediante sistemas lineales.

Una posible sugerencia sería agregar una columna al sistema matricial

en la que se considere el descuento como una variable a hallar
proporcional al número de escalas (que se agregaría como otro
elemento a la ecuación:

c 1 x 1 +c 2 x 2 +c 3 x3 .. c n x n +dn=k ;
d=¿coeficiente negativo igual al descuento por cantidad de escala en
el vuelo

57
 Matemática III

Si bien esta podría resultar una mejor aproximaciones, no

necesariamente reflejan con gran fidelidad casos extremos: viajes con
múltiples escalas de bajo costo podrían tener llegar a tener costos
negativos que es algo que no podría pasar.

58
 Matemática III

V. CONCLUSIONES

En base a nuestras experiencia en el proceso de investigación para el

planteamiento de este proyecto hemos encontrado que la información
disponible en relación a la teoría de grafos y su aplicación en actividades de
programación de redes de vuelos es escasa, debido en gran medida al
hecho de que esta es un área relativamente nueva de la investigación
matemáticas. Por esto, esperamos que las conclusiones e ideas propuestas
en este documento sean de ayuda para futuras investigaciones.

Respecto a la metodología utilizada en este proyecto, podemos concluir que

el modelamiento de sistemas de la vida real mediante sistemas matriciales y
teoría de grafos es un proceso complejo que no siempre se puede hacer de
forma exacta sino que muchas veces es necesario hacer aproximaciones y
reajustes. Esto se debe a que los datos recolectados de manera empírica
muchas veces no se ajustan idealmente a los parámetros del modelo que se
quiere diseñar. En este proyecto, por ejemplo, durante el proceso de
construcción del sistema de ecuaciones se tuvieron que realizar ajustes en
los precios, debido a que el sistema obtenido era incompatible.

Asimismo, hemos podido apreciar que las herramientas computacionales y

programación tales como Matlab son una indispensable y poderosa
herramienta para cualquier matemático en la actualidad al proveer una forma
confiable y rápida de resolver problemas. Esto lo hemos podido apreciar
durante todo el proceso de nuestro proyecto al usar scripts como
Gauss_Pivoteo_Parcial.m para resolver largas operaciones rápidamente y
con la seguridad de que los resultados sean correctos. No obstante, es
importante no olvidar que no son suficientes por sí solas, sino que requieren

59
 Matemática III

de una fuerte base teórica por parte del usuario para su correcto
aprovechamiento. Esto lo hemos vivido durante el desarrollo de nuestro
proyecto al encontrar que que algunos métodos aprendidos en clase no
fueron suficiente para solucionar algunas partes del problema. En la etapa de
resolución del sistema, por ejemplo, no se pudo aplicar la factorización de
Crout con el método enseñado (implementado en crout.m) directamente
debido a que daba errores al dividir entre 0. Por lo tanto, fue necesario
aplicar un reordenamiento en la matriz de coeficientes, para lo que fue
necesario utilizar una función ya definida en el matlab y que integraba una
matriz especial para este reordenamiento.

Otra conclusión a la que hemos llegado es que, los sistemas matriciales y la

teoría de grafos son herramientas extremadamente útiles para el
modelamiento de rutas más cortas, precios más baratos y periodos de tiempo
más costos, y nos permite entender la relación entre nodos con cierta
aproximación, tomando en cuenta que siempre existirá un error. En este
sentido, como se ha podido ver durante el desarrollo de este proyecto, el
sistema que hemos planteado es uno que hace suposiciones necesarias
para linealizar el sistema y garantizar su resolubilidad como asumir que no
hay descuentos por escalas, algo frecuente en la vida real pero cuyo
modelamiento como incógnita es extremadamente complicado como parte de
un sistema lineal. No obstante, aun con estas aproximaciones y correcciones,
se ha llegado a construir un modelo aproximado que es útil y relevante al
tener aplicaciones en la vida real como resolver el problema que se planteó
como objetivo del proyecto de forma efectiva.

Finalmente, como posibles extensiones y mejoras para este proyecto

tenemos tres sugerencias principales. En primer lugar, si bien en esta
ocasión se ha trabajado con una red y conjunto de rutas relativamente
pequeño por las restricciones de tiempo y espacio, es posible extrapolar este

60
 Matemática III

método a sistemas más grandes para resolver problemas más complejos.

Por ejemplo, se podría intentar modelar la red de latinoamérica en base a
este modelo para hallar la ruta óptima entre cualquier par de países. Por otro
lado, es posible intentar incluir más variables en este sistema como los
descuentos por el número de escalas, habiendo una posible solución para
este factor en la sección de interpretación de resultados. Para finalizar,
trabajar con rangos de error sería una forma posible mejora para poder
representar la realidad de los precios con mayor fidelidad sin necesidad de
reajustes o que estos sean mínimos.

61
 Matemática III

VI. BIBLIOGRAFÍA

1. Alaba, F. (s.f.). Optimal Crout method in solving systems of linear

equations: A computer Approach. Academia. Disponible en:
[Link]
[Link]?Expires=1621986785&Signature=UCPYx4y-
klWbqGSB~DDJoxenFmpQvKlSvkPB8MCp~Wj4Zz9MjFTkHO~Ru2A0
LAcKaRBArfsiZLut~1qfFyVID9LSdbwu~0dIA7dZ--vXaqm-
rECFCp7xrCHnRW2z3cXnE1AAKFtNpffzC0Yq28

2. Antony, (2011). Algoritmos de caminos más cortos. SlideServe.

Disponible en: [Link]
caminos-m-s-cortos

3. Baroudi, U., Bin-Yahya, M., Alshammari, M., & Yaqoub, U. (2018, junio
14). Ticket-based QoS routing optimization using genetic algorithm for
WSN applications in smart grid. Disponible en:
[Link]

4. dar15, (2011). Prácticas sesión 13. [Link]. Disponible en:

[Link]

5. Galvin, D., (2009). Discrete Mathematics, Spring 2009 Graph theory

notation. Disponible en:
[Link]
.pdf

62
 Matemática III

6. Guamanga Dorado, J., y Granada Ortega, A. (2019). ¿Qué tan

Conectado Está El Continente Americano Y El Caribe En Términos De
Vuelos Comerciales? Un Enfoque Con Redes. Universidad Icesi.
Disponible en:
[Link]
1/[Link]

7. Puchades Cortés, V., Mula Bru, J., y Rodríguez Villalobos, A. (2008,

Diciembre). Revista de Métodos Cuantitativos para la Economía y la
Empresa. Redalyc. Disponible en: [Link]
id=233117226002

8. Restrepo, C., Hernán, J., Sánchez, C., y Jairo, J. (2004, Diciembre

26). Aplicación De La Teoría De Grafos Y El Algoritmo De Dijkstra
Para Determinar Las Distancias Y Las Rutas Más Cortas En Una
Ciudad. Redalyc. Disponible en: [Link]
id=84911640035

9. Rodríguez Gálvez, M. (2009).Problemas De Optimización En Árboles

Generadores, Universidad Politécnica de [Link] en:
[Link]
os/descargas/Memoria_Teoria.pdf

10. Rosen, K., (2012). Discrete mathematics and its applications by

Rosen, Kenneth. 7th ed. McGraw-Hill, p.651-660.

63
 Matemática III

VII. ANEXOS

Anexo 1: Página oficial de Latam de donde se recogieron los precios de las

rutas.

Anexo 2: ruta 1

Anexo 3: ruta 2

64
 Matemática III

Anexo 4: ruta 3

Anexo 5: ruta 4.1

Anexo 6: ruta 4.2

Anexo 7: ruta 5

Anexo 8: ruta 6

65
 Matemática III

Anexo 9: ruta 7

66