Algebra II (Español)

Curso de fuentes OpenUCLM

Primero presentamos los conceptos de cono poliédrico y politopo. A continuación, de manera similar al curso de álgebra I, un algoritmo que obtiene el cono dual de un cono dado y todas sus facetas de cualquier dimensión, nos permite resolver todos los problemas discutidos de álgebra lineal utilizando el concepto de dualidad como un nuevo punto de vista. Este punto de vista de la dualidad nos permite resolver la membresía del cono de un vector y la intersección de conos de una manera muy simple. Además, el algoritmo proporciona el cono dual en su forma más simple, es decir, como un espacio lineal con su base más un cono agudo con sus bordes. Se discute la compatibilidad de un sistema lineal de desigualdades y se obtienen todas las soluciones de los sistemas lineales de desigualdades. Además, las soluciones de todos los subsistemas, incluidas todas las ecuaciones desde el primero hasta cualquiera de ellos, se obtienen a la vez. El concepto de cono asociado con un politopo nos permite obtener todos los vértices y todas las facetas de cualquier dimensión de un politopo. Se obtiene el conjunto de todas las soluciones factibles de un problema de programación lineal y todas sus soluciones óptimas, y el algoritmo detecta la inviabilidad. Finalmente, se presenta un ejemplo de un problema de suministro de agua para mostrar la importancia de estos métodos en el diseño de ingeniería.

Autores	Enrique Castillo
Fecha	06/10/2019	Idioma	Castellano

Me Gusta

En este primer bloque se realizará la presentación del curso del G9, exponiendo la estructura de bloques del mismo y su planificación secuencial.

A course of Algebra including cones, polytopes and systems of linear inequalities.

Enrique Castillo

A course of Algebra including cones, polytopes and systems of linear inequalities. It includes some examples of engineering applications.

Motivación

Enrique Castillo

Se motiva el curso, describiendo en qué consiste y las grandes diferencias que presenta frente a un curso tradicional de álgebra. Los conceptos que se presentan no suelen ser objeto de cursos de álgebra al nivel de primer curso de carrera. La idea es utilizar un único algoritmo para resolver todos los problemas que se analizan, aportando la idea de la dualidad, que permite ver estos problemas desde una perspectiva diferente, mucho más rica y que sugiere directamente cómo resolver los problemas que se plantean. Como curiosidad especial se muestra cómo resolver sistemas de ecuaciones lineales con desigualdades, es decir, sistemas de inecuaciones lineales.

En este primer bloque se presentan las estructuras algebráicas de polítopo y cono, mostrando algunos ejemplos ilustrativos que faciliten su comprensión. Se presenta también el concepto de cono dual de un cono dado. Como elemento fundamental para el desarrollo del curso se describe el algoritmo de obtención del cono dual de un cono dado, que aunque diseñado para obtener el cono dual, servirá de base para resolver todos los demás problemas que se presentan en el curso. Se muestra que el espacio vectorial es un caso particular de cono y que basta añadir un generador más a la base para poder expresar los vectores del espacio vectorial como cono, es decir, generado por combinaciones lineales no negativas. Finalmente, se define la forma estándar de un cono como suma de sus componentes de espacio vectorial y de cono agudo, lo que permite expresar el cono en su forma mínima.

Conos y polítopos

Enrique Castillo

En esta lección se definen los conceptos de cono y polítopo. El primero generaliza el de espacio vectorial y ambos tienen mucha importancia en la práctica profesional. Algunos resultados de este capítulo sorprenderán al lector, en especial, el que un espacio vectorial de dimensión n es un cono generado por n+1 vectores.

Algoritmo para obtener el cono dual de un cono

Enrique Castillo

En esta lección se presenta el algoritmo de dualidad con el que se van a resolver todos los problemas que van a plantearse en este curso y los que se plantearon en el primero. El algoritmo recibe el nombre de algoritmo gamma, y obtiene el cono dual de un cono dado. Para ello, se describe, paso a paso, el algoritmo con ejemplos. Se muestra además que el cono dual resultante está en forma estándar, es decir, en su forma mínima (suma de un subespacio y un cono agudo, del que se obtienen una base y sus aristas, respectivamente).

Algoritmo para obtener el cono dual de un cono dado en forma estándar

Enrique Castillo

En esta lección se explica, en detalle, cómo modificar el algoritmo gamma si es cono inicial, del que se desea al dual, está en forma estándar. Se muestra que el uso de estas pequeñas modificaciones reduce la complejidad del algoritmo.

Cono en forma estándar

Enrique Castillo

En esta lección estudiamos cómo podemos representar un cono en una forma muy especial, llamada la forma estándar de un cono que representa el cono como la suma de un espacio lineal más un cono agudo.

Este segundo bloque está enfocado a las aplicaciones algebráicas del algoritmo, que incluyen: el problema de la pertenencia de un vector a un cono y la intersección de dos conos. El primero de ellos es un problema complejo por implicar combinaciones lineales no negativas, es decir, sistemas de inecuaciones lineales, cuyas soluciones no suelen ser conocidas por los alumnos ni estudiarse en cursos estándar de álgebra. El uso del algoritmo, explicado en el bloque anterior, permite resolver el problema de forma muy elegante y evitar tener que resolver estos sistemas. La intersección de conos es otro problema de cierta complejidad, ya que implica también los sistemas de inecuaciones, resolviéndolo de una forma ingeniosa. También puede resolverse dándose cuenta de que dicha intersección es el cono dual del dual de uno de ellos en el otro, lo que sugiere de forma directa cómo resolverlo.

Pertenencia de un vector a un cono poliédrico convexo

Enrique Castillo

En esta lección se explica cómo utilizar el algoritmo gamma para saber si un vector pertenece a un cono. En realidad se obtienen unas fórmulas que permiten saberlo para cualquier cono. La idea es considerar el cono inicial como el dual de su dual.

Intersección de dos conos poliédricos convexos

Enrique Castillo

En esta lección se aplica el algoritmo gamma para determinar la intersección de dos conos. Para ello, se considera el primero o el segundo cono como el dual de su dual. De esta forma el problema se reduce a obtener el dual del dual de un cono en otro cono.

Este bloque se centra en los sistemas lineales de inecuaciones, incluyendo los sistemas homogéneos y los completos. También se explica cómo pueden resolverse simultáneamente todos los subsistemas de un sistema dado, así cómo analizar la compatibilidad de un sistema, es decir, si tiene o no tiene solución.

Sistemas homogéneos de inecuaciones lineales

Enrique Castillo

En esta lección se resuelven los sistemas lineales de inecuaciones, para lo que se escribe cada una de las ecuaciones como producto escalar del vector de sus coeficientes por el vector de las incógnitas. De esta forma, queda claro que la solución es el cono dual del cono generado por los vectores fila de los coeficientes.

Sistemas completos de inecuaciones lineales

Enrique Castillo

En esta lección se resuelve un sistema completo de inecuaciones lineales mediante el algoritmo gamma. Se utiliza una incógnita nueva, que convierte el sistema en uno homogéneo más una inecuación no homogénea. La elección de ésta última inecuación se hace de forma que no se altere la solución del sistema inicial. Se utiliza además, por conveniencia una inecuación redundante, resultando un sistema homogéneo más la inecuación no homogénea. Por tanto, se resuelve primero el sistema homogéneo y, luego, se eliminan las soluciones que no cumplen la nueva inecuación.

Compatibilidad de un sistema lineal de inecuaciones

Enrique Castillo

En esta lección se analiza la compatibilidad de un sistema lineal de inecuaciones sin resolverlo, es decir, se obtienen las condiciones necesarias y suficientes que deben satisfacer los términos independientes para que el sistema sea compatible. Para ello, se resuelve primero un caso particular y se muestra cómo reducir un caso cualquiera a este caso particular. La idea consiste en escribir el caso particular de forma que se ponga de manifiesto que el vector de los términos independientes en caso de existir solución debe ser una combinación lineal no negativa de los vectores columna de los coeficientes, con coeficientes las incógnitas. Ello reduce el problema a un problema de pertenencia de un vector, el de los términos independientes, a un cono, el generado por las columnas de la matriz de coeficientes del sistema.

Ecuaciones de un poliedro

Enrique Castillo

En esta lección, puesto que se ha mostrado que la solución general de un sistema de inecuaciones lineales es un poliedro, se invierte el método de resolución de sistemas completos de inecuaciones para obtener las ecuaciones de un poliedro.

Conjuntos de soluciones de los sistemas lineales de inecuaciones

Enrique Castillo

En esta lección se hace una discusión completa de los diferentes tipos de soluciones que pueden aparecer al resolver los sistemas lineales de inecuaciones, considerando todos los diferentes casos posibles.

Cono asociado a un polítopo. Facetas de conos y poolítopos

Enrique Castillo

En esta lección se define el concepto de cono asociado a un polítopo, lo que permite obtener las hipercaras o facetas de cualquier dimensión de un polítopo a partir de las del cono asociado, que vienen dadas por el algoritmo gamma.

Con objeto de motivar y de ilustrar la potencia del algoritmo de ortogonalización y de las aplicaciones algebraicas, este bloque está dedicado a la presentación de aplicaciones a la ingeniería, tales como las redes de abastecimiento de agua, aunque su aplicación a otras redes, como las de tráfico, de información, etc., es idéntico. Se incluyen también aplicaciones al problema de los planos inclinados con masas y poleas, y a los circuitos eléctricos.

Ejemplo de sistemas lineales de inecuaciones. Redes de abastecimiento de agua

Enrique Castillo

En esta lección se presenta el problema de abastecimiento de agua como un problema de sistemas de inecuaciones lineales completo. Se utilizan algunos ejemplos muy simples, para ilustrar los conceptos y mostrar cuáles son las ecuaciones, las incógnitas, los datos del problema, etc. Se interpretan físicamente los significados de las condiciones de compatibilidad y de las soluciones y se muestra que no es necesario utilizar el algoritmo, ya que los vectores básicos de la solución corresponden al número de huecos del sistema de abastecimiento. A partir de la solución, se obtienen resultados ingenieriles de gran valor.

Ejemplo de programación lineal. El problema de la fábrica de mesas

Enrique Castillo

En esta lección se plantea un problema de programación lineal en el que se optimiza la fabricación de mesas de dos tipos. En vez de obtener una única solución, que es lo que hacen los programas estándar de programación lineal, se obtienen todas las soluciones.

Aplicación a la programación lineal

Enrique Castillo

En esta lección se presenta un ejemplo de un cubo truncado y aplicaciones para obtener todas las soluciones de los problemas de programación lineal.

Este bloque se proporciona una serie de exámenes tipo con sus soluciones, para facilitar que el alumno pueda comprobar si ha entendido el material explicado en los diferentes temas del curso. Corresponden al tipo de examen que hemos utilizado en la Universidad de Castilla-La Mancha durante 20 años y que se han mostrado como muy satisfactorios.

Examen 2015

Enrique Castillo

Examen 2016

Enrique Castillo

Examen 2017

Enrique Castillo

Con objeto de facilitar la utilización de los métodos descritos en este curso y de que los alumnos puedan trabajar no sólo los los ejercicios y problemas planteados, sino otras aplicaciones, se presenta aquí una aplicación informática que implementa el algoritmo de ortogonalización. Finalmente, se da una lista de referencias bibliográficas.

Cómo usar la ortogonalización y los algoritmos gamma de doble cono

Enrique Castillo

Este video describe la aplicación que implementa los dos algoritmos descritos en los dos cursos de álgebra por Enrique Castillo.
El primero es el algoritmo de ortogonalización que obtiene el subespacio ortogonal a un subespacio lineal dado.
El segundo es el algoritmo de doble cono, que obtiene el doble cono de un cono dado.

Bibliografía

Enrique Castillo

Ejemplos de archivos de datos.

Algoritmo de ortogonalización

Enrique Castillo