Álgebra lineal

El álgebra lineal es una rama de las matemáticas que estudia conceptos tales como vectores, matrices,

sistemas de ecuaciones lineales y en su enfoque de manera más formal, espacios vectoriales y sus

transformaciones lineales.

Es un área activa que tiene conexiones con muchas áreas dentro y fuera de las matemáticas, como el análisis

funcional, las ecuaciones diferenciales, la investigación de operaciones, las gráficas por computadora, la

ingeniería, entre otros.

La historia del álgebra lineal moderna se remonta a 1843, cuando William Rowan Hamilton (de quien proviene el

uso del término vector) creó los cuaterniones; y a 1844, cuando Hermann Grassmann publicó su libro Die

lineare Ausdehnungslehre (La teoría lineal de extensión).

RectasEn geometría euclidiana, la recta o la línea recta se extiende en una misma dirección por tanto tiene una sola

dimensión y contiene infinitos puntos; se puede considerar que está compuesta de infinitos segmentos. Dicha

recta también se puede describir como una sucesión continua e indefinida de puntos extendidos en una sola

dimensión, es decir, no posee principio ni fin.

Es uno de los entes geométricos fundamentales, junto al punto y el plano. Son considerados conceptos

apriorísticos ya que su definición solo es posible a partir de la descripción de las características de otros

elementos similares. Un ejemplo de las dificultades de la definición de la recta a partir de puntos es la llamada

paradoja de Zenón de la dicotomía que ilustraba la desaparición de la recta al dividirla en puntos. Así, es posible

elaborar definiciones basándose en los postulados característicos que determinan relaciones entre los entes

fundamentales. Las rectas se suelen denominar con una letra minúscula.

En geometría analítica las líneas rectas pueden ser expresadas mediante una ecuación del tipo y = m x + b,

donde x, y son variables en un plano cartesiano. En dicha expresión m es denominada la "pendiente de la recta"

y está relacionada con la inclinación que toma la recta respecto a un par de ejes que definen el plano. Mientras

que b es el denominado "término independiente" u "ordenada al origen" y es el valor del punto en el cual la recta

corta al eje vertical en el plano.

Caracyeristicas de la recta La recta se prolonga indefinidamente en ambos sentidos.

En geometría euclidiana, la distancia más corta entre dos puntos es la línea recta.

La recta puede definirse como el conjunto de puntos situados a lo largo de la intersección de dos

planos.

Semirrecta

Se le llama semirrecta a cada una de las dos partes en que queda dividida una recta al ser cortada en

cualquiera de sus puntos. Es la parte de una recta conformada por todos los puntos que se ubican hacia un lado

de un punto fijo de la recta, denominado origen, a partir del cual se extiende indefinidamente en una sola

dirección.

Semirrecta opuesta

La semirrecta opuesta de una semirrecta es la otra semirrecta salida de la recta que define la primera.

Cada semirrecta solo tiene una semirrecta opuesta.

Una semirrecta y su semirrecta opuesta tienen el mismo origen.

Semi-espaciosSe denomina semiespacio, a cada una de las dos partes en que un espacio queda dividido por un plano

contenido en él.

El concepto se aplica tanto en el ámbito de la geometría, como respecto a otros ámbitos de la matemáticas en

los que existen conceptos de espacio y plano.

Combinación convexaUna combinación convexa es una combinación lineal de puntos (los cuales pueden ser vectores, escalares o

más en general puntos en un espacio afín) donde todos los coeficientes son no negativos y suman 1. Todas las

posibles combinaciones convexas están dentro de la envoltura convexa de los puntos dados. De hecho, la

colección de todas la combinaciones convexas de puntos en el conjunto constituye la envoltura convexa del

conjunto.

Formalmente, dando un conjunto finito de puntos en un espacio vectorial real, una

combinación convexa de esos puntos es un punto de la forma

donde los números reales satisface y

Dados tres puntos en el plano como se muestra en la

figura, el punto es combinación convexa de los tres puntos, mientras

que no lo es.

( es sin embargo una combinación afín de los tres puntos, así como su envoltura afín es todo el plano.)

PoliedrosUn poliedro es, en el sentido dado por la geometría clásica al término, un cuerpo geométrico cuyas caras son

planas y encierran un volumen finito. La palabra poliedro viene del griego clásico πολύεδρον (polyedron), de la

raíz πολύς (polys), "muchas" y de έδρα (edra), "base", "asiento", "cara".

Los poliedros se conciben como cuerpos tridimensionales, pero hay semejantes topológicos del concepto en

cualquier dimensión. Así, el punto o vértice es el semejante topológico del poliedro en cero dimensiones, una

arista o segmento lo es en 1 dimensión, el polígono para 2 dimensiones; y el polícoro el de cuatro dimensiones.

Todas estas formas son conocidas como politopos, por lo que podemos definir un poliedro como un polítopo

tridimensional.

DefiniciónSe llama poliedro todo cuerpo acotado, limitado por un número finito de superficies planas. Se demuestra que

las superficies planas que limitan un poliedro son polígonos.

Un poliedro convexo es un poliedro P, que a su vez es un conjunto convexo; es decir si contiene dos puntos A y

B, incluye al segmento que ellos determinan.

Representaciones

1- Sea S un poliedro ( o un convexo), un punto "z" de S decimos que es un punto extremo si no existe ningún

par de puntos "x" e "y" de S tales que "z" es combinación lineal conveza.

Es decir, que no existen "x" e "y" de S y un "t" de [0,1] tal que z = x·t + ( 1 - t )·y

2- Caracterización de puntos extremos:

Sea el poliedro S determinado por los puntos "x" de R^n tales que A·x = b y x>=0 sinedo A una matriz real

"mxn" con rango "m" y "b" de R^m. Un punto "x" de S es un punto extremo si y sólo si se puede expresar como:

x = [x_B; x_N] = [B^-1; 0] sinedo A=[B,N], B regular y (B^-1)· b>=0.

Donde x_B representan las componentes asociadas al bloque B y x_N las asociadas al bloque N.

En otras palabras: podemos encontrar una submatriz regular de A, B, cumpliendo todo lo anterior.

Hay una caracterización similar para direcciones extremas, que no escribo porque su notación es tanto o más

tediosa que la anterior.

3- Dadas las caracterizaciones de puntos y direcciones extremas se demuestra que cualquier punto del poliedro

se puede expresar como combinación de éstos.

Metodo simplexEn optimización matemática, el término algoritmo Símplex habitualmente se refiere a un conjunto de métodos

muy usados para resolver problemas de programación lineal, en los cuales se busca el máximo de una función

lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales. El algoritmo Símplex

primal fue desarrollado por el matemático norteamericano George Dantzig en 1947, y procede examinando

vértices adyacentes del poliedro de soluciones. Un algoritmo Símplex es un algoritmo de pivote.

Un método llamado de manera similar, pero no relacionado al anterior, es el método Nelder-Mead (1965) o

método de descenso (o ascenso) símplex; un método numérico que busca un mínimo (o máximo) local de una

función cualquiera examinando en cada paso los vértices de un simplex.

El algoritmo del método Símplex fue elegido como uno de los 10 algoritmos más importantes del s.XX (SIAM

News, Volume 33, Number 4).

DefinicónEl Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver

modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables.

El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón

matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice

vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o

minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará

solución.

Este famosísimo método fue creado en el año de 1947 por el estadounidense George Bernard Dantzig y el ruso

Leonid Vitalievich Kantorovich, con el ánimo de crear un algoritmo capaz de solucionar problemas

de m restricciones y n variables.

Método Simplex Construcción de la primera tabla:

Las columnas de la tabla están dispuestas de la siguiente forma: la primera columna de la tabla

contiene las variables que se encuentran en la base (o variables básicas), esto es, aquellas que toman

valor para proporcionar una solución; la segunda columna recoge los coeficientes que dichas variables

básicas tienen en la función objetivo (esta columna es llamada Cb); la tercera muestra el término

independiente de cada restricción (P0); a partir de ésta aparece una columna por cada una de las

variables de decisión y holgura presentes en la función objetivo (Pj). Para tener una visión más clara de

la tabla, se incluye una fila que contiene los títulos de cada una de las columnas.

Sobre esta tabla se agregan dos nuevas filas: una de ellas, que lidera la tabla, donde aparecen los

coeficientes de las variables de la función objetivo, y una última fila que recoge el valor la función

objetivo y los costes reducidos Zj - Cj.

Los costes reducidos muestran la posibilidad de mejora en la solución Z0. Por este motivo también son

llamados valores indicadores.

Se muestra a continuación el aspecto general de la tabla del método Simplex:

Tabla

      C1 C2 ... Cn

Base Cb P0 P1 P2 ... Pn

P1 Cb1 b1 a11 a12 ... a1n

P2 Cb2 b2 a21 a22 ... a2n

... ... ... ... ... ... ...

Pm Cbm bm am1 am2 ... amn

Z   Z0 Z1-C1 Z2-C2 ... Zn-Cn

Todos los valores incluidos en la tabla vendrán dados por el modelo del problema salvo los valores de

la fila Z (o fila indicadora). Estos se obtienen de la siguiente forma: Zj = Σ(Cbi·Pj) para i = 1..m, donde si

j = 0, P0 = bi y C0 = 0, y en caso contrario Pj = aij.

Se observa, al realizar el método Simplex, que en esta primera tabla ocupan la base todas las variables

de holgura y por ello (todos los coeficientes de las variables de holgura son 0 en la función objetivo) el

valor inicial de Z es cero.

Por este mismo motivo tampoco es necesario realizar los cálculos de los costes reducidos en la primera

tabla, pudiéndose determinar directamente como el cambio de signo de los coeficientes de cada

variable en la función objetivo, esto es, -Cj.

Condición de parada:

Se cumple la condición de parada cuando la fila indicadora no contiene ningún valor negativo entre los

costes reducidos (cuando el objetivo es la maximización), esto es, no existe posibilidad de mejora.

Si no se cumple la condición de parada es necesario realizar una iteración más del algoritmo, esto es,

determinar la variable que se vuelve básica y la que deja de serlo, encontrar el elemento pivote,

actualizar los valores de la tabla y comprobar si se cumple nuevamente la condición de parada.

Es también posible determinar que el problema no se encuentra acotado y su solución siempre

resultará mejorable. En tal caso no es necesario continuar iterando indefinidamente y se puede finalizar

el algoritmo. Esta situación ocurre cuando en la columna de la variable entrante a la base todos los

valores son negativos o nulos.

Elección de la variable que entra a la base:

Cuando una variable se vuelve básica, es decir, entra en la base, comienza a formar parte de la

solución. Observando los costes reducidos en la fila Z, se decide que entra a la base la variable de la

columna en la que éste sea el de menor valor (o de mayor valor absoluto) entre los negativos.

Elección de la variable que sale de la base:

Una vez obtenida la variable entrante, se determina que sale de la base la variable que se encuentre en

aquella fila cuyo cociente P0/Pj sea el menor de los estrictamente positivos (teniendo en cuenta que

esta operación se hará únicamente cuando Pj sea superior a 0).

Elemento pivote:

El elemento pivote de la tabla queda marcado por la intersección entre la columna de la variable

entrante y la fila de la variable saliente.

Actualización de la tabla:

Las filas correspondientes a la función objetivo y a los títulos permanecerán inalteradas en la nueva

tabla. El resto de valores deberán calcularse como se explica a continuación:

o En la fila del elemento pivote cada nuevo elemento se calcula como:

Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote.

o En el resto de las filas cada elemento se calcula:

Nuevo Elemento Fila = Anterior Elemento Fila - (Anterior Elemento Fila en Columna Pivote *

Nuevo Elemento Fila Pivote).

De esta forma se consigue que todos los elementos de la columna de la variable entrante sean nulos

salvo el de la fila de la variable saliente cuyo valor será 1. (Es análogo a utilizar el método de Gauss-

Jordan para resolver sistemas de ecuaciones lineales).

Método de las Dos FasesEl método de las Dos Fases se utiliza cuando aparecen variables artificiales en la forma canónica o estándar del

problema. La primera fase trata de resolver el problema auxiliar Z' de minimizar la suma de las variables

artificiales y conseguir que sea cero (con objeto de evitar incongruencias matemáticas). Una vez resuelto este

primer problema, y siempre y cuando el resultado sea el esperado, se reorganiza la tabla resultante para

utilizarla en la segunda fase sobre el problema original.

En caso contrario el problema no es factible, es decir, no tiene solución y no será necesario continuar con la

segunda fase.

FASE 1Esta primera fase es muy similar al método Simplex, con la excepción de la construcción de la primera tabla,

además de la necesidad de estudiar el resultado obtenido para determinar si se desarrolla la segunda fase.

En tal caso, la última tabla de esta fase será, con algunas modificaciones, la utilizada como tabla inicial para la

segunda fase.

Construcción de la primera tabla:

Se elabora de manera análoga a la tabla inicial del método Simplex, pero con algunas diferencias.

Como se ha comentado, en esta primera fase se resuelve un problema auxiliar (la minimización de la

suma de las variables artificiales) con una función objetivo auxiliar. Por lo tanto en la primera fila de la

tabla, donde se muestran los coeficientes de las variables de la función objetivo, aparecerán todos los

términos a cero excepto los coeficientes de variables artificiales. El valor de cada uno de estos

coeficientes es "-1" debido a que se está minimizando la suma de dichas variables (recuerde que

minimizar Z' es igual que maximizar (-1)·Z').

La otra diferencia para la primera tabla radica en que ahora sí es necesario calcular la fila Z (o

fila indicadora).

Tabla

    C0 C1 C2 ... Cn-k ... Cn

Base Cb P0 P1 P2 ... Pn-k ... Pn

P1 Cb1 b1 a11 a12 ... a1n-k ... a1n

P2 Cb2 b2 a21 a22 ... a2n-k ... a2n

... ... ... ... ... ... ... ... ...

Pm Cbm bm am1 am2 ... amn-k ... amn

Z   Z0 Z1 Z2 ... Zn-k ... Zn

Siendo Zj = Σ(Cbi·Pj) - Cj para i = 1..m, donde si j = 0, P0 = bi y C0 = 0, y en caso contrario Pj = aij.

Condición de parada y paso a la fase 2:

La condición de parada es la misma que en el método Simplex normal. Esto es, cuando en la fila

indicadora ninguno de los valores de los costes reducidos es negativo (ya que tal y como se ha

planteado el objetivo es la maximización de (-1)·Z').

Cumplida la condición de parada es necesario determinar si es posible pasar a la segunda fase para

obtener la solución óptima del problema original. Esto se hace observando el resultado obtenido en la

primera fase: si su valor es 0, significa que el problema original tiene solución y es posible calcularla, en

caso contrario indica que se trata de un problema no factible y no tiene solución.

FASE 2La segunda fase del método de las Dos Fases se desarrolla exactamente igual que el método Simplex, con la

salvedad de que antes de iniciar las iteraciones hay que eliminar las columnas correspondientes a las variables

artificiales, y reconstruir la tabla inicial.

Eliminar Columna de variables artificiales:

Si hemos llegado a la conclusión de que el problema original tiene solución, debemos preparar nuestra

tabla para la segunda fase. Este paso es muy sencillo, se trata únicamente de eliminar las columnas

correspondientes a las variables artificiales.

Construcción de la tabla inicial:

La tabla inicial en este caso se mantiene casi igual a la última tabla de la primera fase. Únicamente

habrá que modificar la fila de la función objetivo por la del problema original y calcular nuevamente la

fila Z (de la misma forma que en la primera tabla de la fase 1).

A partir de este punto, todas las iteraciones hasta llegar a la solución óptima del problema no presentan ninguna

diferencia con el método Simplex.