metodo de Gauss Jordan y Metodo Simple

[18.868.391]

Explicacion:
El metodo de Gauss-Jordan utiliza operaciones con matrices para
resolver sistemas de ecuaciones de n numero de variables.
Para aplicar este metodo solo hay que recordar que cada operacion que
se realice se aplicara a toda la fila o a toda la columna en su caso.

Procedimiento:
Primero se debe tener ya el sistema de ecuaciones que se quiere
resolver y que puede ser de n numero de variables por ejemplo:
-3x+3y+2z=1
4x+y-z=2
x-2y+z=3
Y se acomodan los coeficientes y los resultados en una matriz:

El objetivo de este metodo es tratar de convertir la parte de la
matriz donde estan los coeficientes de las variables en una matriz
identidad que es una matriz con puros 0 y 1 pero los 1 estan en
diagonal asi:

Esto se logra mediante simples operaciones de suma, resta y
multiplicacion.
Entoces, si se quiere convertir la primera matriz en la segunda, se
puede observar que el -3 de la primera matriz se tiene que convertir
en un 1, segun la matriz identidad, asi que hay que dividir entre -3,
pero como una operacion se aplica a toda la fila, entonces toda la
primera fila se tiene que dividir entre -3 y queda mas o menos asi:


Despues, como se ve en la matriz identidad, hay que hacer 0 toda la
columna debajo del 1, y se hace multiplicando por algo la fila de
arriba y sumandola a la fila de abajo, en este caso, si se multiplica
por -4 la fila de arriba, la primera multiplicacion es -4x1, que
sumado a la primera coordenada de la fila de abajo da el 0 que se
desea, igualmente, la operacion se realiza con toda la fila por lo que
a cada posicion de la fila de arriba se le multiplica por -4 y se suma
con la correspondiente posicion de la fila de abajo. La siguiente
multiplicacion seria -4x-1 y se sumaria con el 1 de abajo. La matriz
va quedando de la siguiente manera:


(Las R son por Row en ingles)
El siguiente paso para lograr una matriz identidad es obtener el
siguiente 1, que en este caso iria en donde esta el 5 en la segunda
fila. Como ya se trabajo con la primera columna ya no es necesario
tomarla en cuenta puesto que se supone que ya esta bien.
Para lograr un 1, hay que dividir toda la segunda fila (sin tomar en
cuenta la primera columna) entre 5 y la matriz queda asi:

Despues se tienen que hacer 0 los que estan arriba y abajo del 1, que
en este caso seria, para el que esta arriba 1xR2+R1 porque el R1 es un
-1 y al sumarse con el 1 que da de la multiplicacion de 1xR2 da el 0
que se esta buscando.
De igual manera para el que esta debajo es el mismo procedimiento
porque en este ejemplo coincidio que los 2 fueran -1, pero hay que
recordar siempre buscar el numero por el cual multiplicar para que a
la hora de sumar de un 0.

Una vez que se obtuvieron los 0 solo falta obtener el ultimo 1 segun
la matriz identidad. Esto se logra dividiendo entre 2 toda la tercera
fila ignorando ya los que fueron hechos ceros.
La matriz queda de la siguiente manera:

Por ultimo solo se hacen 0 los que estan encima del que acabamos de
hacer 1, en este caso multiplicando por 1/3xR3 y sumandola a R1 para
hacer el 0 que se necesita, y multiplicando -1/3xR3 y sumandolo a R2
para obtener el ultimo 0:

Como se podra notar, una matriz identidad siempre es cuadrada y al
pasarla a nuestra matriz original sobro la columna donde iban los
resultados de cada ecuacion, pues bien, esa ultima columna contiene
los valores de las variables que se estan buscando y en orden, la de
arriba es la primer variable, la de enmedio es la segunda y la ultima
es la tercera.

Método Simple
El método Simplex es un procedimiento iterativo que permite ir
mejorando la solución a cada paso. El proceso concluye cuando no es
posible seguir mejorando más dicha solución.

Partiendo del valor de la función objetivo en un vértice cualquiera,
el método consiste en buscar sucesivamente otro vértice que mejore al
anterior. La búsqueda se hace siempre a través de los lados del
polígono (o de las aristas del poliedro, si el número de variables es
mayor). Cómo el número de vértices (y de aristas) es finito, siempre
se podrá encontrar la solución. (Véase método Gráfico)

El método Simplex se basa en la siguiente propiedad: si la función
objetivo, f, no toma su valor máximo en el vértice A, entonces hay una
arista que parte de A, a lo largo de la cual f aumenta.

Deberá tenerse en cuenta que este método sólo trabaja para
restricciones que tengan un tipo de desigualdad "≤" y coeficientes
independientes mayores o iguales a 0, y habrá que estandarizar las
mismas para el algoritmo. En caso de que después de éste proceso,
aparezcan (o no varíen) restricciones del tipo "≥" o "=" habrá que
emplear otros métodos, siendo el más común el método de las Dos Fases.



PREPARANDO EL MODELO PARA ADAPTARLO AL MÉTODO SIMPLEX

Esta es la forma estándar del modelo:

Función objetivo: c1·x1 + c2·x2 + ... + cn·xn
Sujeto a: a11·x1 + a12·x2 + ... + a1n·xn = b1
a21·x1 + a22·x2 + ... + a2n·xn = b2
...
am1·x1 + am2·x2 + ... + amn·xn = bm
x1,..., xn ≥ 0
Para ello se deben cumplir las siguientes condiciones:

El objetivo es de la forma de maximización o de minimización.
Todas las restricciones son de igualdad.
Todas las variables son no negativas.
Las constantes a la derecha de las restricciones son no negativas.


Cambio del tipo de optimización.

Si en nuestro modelo, deseamos minimizar, podemos dejarlo tal y como
está, pero deberemos tener en cuenta nuevos criterios para la
condición de parada (deberemos parar de realizar iteraciones cuando en
la fila del valor de la función objetivo sean todos menores o iguales
a 0), así como para la condición de salida de la fila. Con objeto de
no cambiar criterios, se puede convertir el objetivo de minimizar la
función F por el de maximizar F·(-1).

Ventajas: No deberemos preocuparnos por los criterios de parada, o
condición de salida de filas, ya que se mantienen.

Inconvenientes: En el caso de que la función tenga todas sus variables
básicas positivas, y además las restricciones sean de desigualdad "≤",
al hacer el cambio se quedan negativas y en la fila del valor de la
función objetivo se quedan positivos, por lo que se cumple la
condición de parada, y por defecto el valor óptimo que se obtendría es
0.

Solución: En la realidad no existen este tipo de problemas, ya que
para que la solución quedara por encima de 0, alguna restricción
debería tener la condición "≥", y entonces entraríamos en un modelo
para el método de las Dos Fases.



Conversión de signo de los términos independientes (las constantes a
la derecha de las restricciones)

Deberemos preparar nuestro modelo de forma que los términos
independientes de las restricciones sean mayores o iguales a 0, sino
no se puede emplear el método Simplex. Lo único que habría que hacer
es multiplicar por "-1" las restricciones donde los términos
independientes sean menores que 0.

Ventaja: Con ésta simple modificación de los signos en la restricción
podemos aplicar el método Simplex a nuestro modelo.

Inconvenientes: Puede resultar que en las restricciones donde tengamos
que modificar los signos de las constantes, los signos de las
desigualdades fueran ("=", "≤"), quedando ("=","≥") por lo que en
cualquier caso deberemos desarrollar el método de las Dos Fases. Este
inconveniente no es controlable, aunque nos podría beneficiar si sólo
existen términos de desigualdad ("≤","≥"), y los "≥" coincidieran con
restricciones donde el término independiente es negativo.



Todas las restricciones son de igualdad.

Si en nuestro modelo aparece una inecuación con una desigualdad del
tipo "≥", deberemos añadir una nueva variable, llamada variable de
exceso si, con la restricción si ≥ 0. La nueva variable aparece con
coeficiente cero en la función objetivo, y restando en las
inecuaciones.

Surge ahora un problema, veamos como queda una de nuestras
inecuaciones que contenga una desigualdad "≥" :

a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs = b1
Como todo nuestro modelo, está basado en que todas sus variables sean
mayores o iguales que cero, cuando hagamos la primera iteración con el
método Simplex, las variables básicas no estarán en la base y tomarán
valor cero, y el resto el valor que tengan. En este caso nuestra
variable xs, tras hacer cero a x1 y x2, tomará el valor -b1. No
cumpliría la condición de no negatividad, por lo que habrá que añadir
una nueva variable, xr, que aparecerá con coeficiente cero en la
función objetivo, y sumando en la inecuación de la restricción
correspondiente. Quedaría entonces de la siguiente manera:

a11·x1 + a12·x2 ≥ b1 a11·x1 + a12·x2 - 1·xs + 1 ·xr = b1
Este tipo de variables se les llama variables artificiales, y
aparecerán cuando haya inecuaciones con desigualdad ("=","≥"). Esto
nos llevará obligadamente a realizar el método de las Dos Fases, que
se explicará más adelante.

Del mismo modo, si la inecuación tiene una desigualdad del tipo "≤",
deberemos añadir una nueva variable, llamada variable de holgura si,
con la restricción si "≥" 0 . La nueva variable aparece con
coeficiente cero en la función objetivo, y sumando en las
inecuaciones.

A modo resumen podemos dejar esta tabla, según la desigualdad que
aparezca, y con el valor que deben estar las nuevas variables.

Tipo de desigualdad Tipo de variable que aparece
≥ - exceso + artificial
= + artificial
≤ + holgura


DESARROLLANDO EL MÉTODO SIMPLEX

Una vez que hemos estandarizado nuestro modelo, puede ocurrir que
necesitemos aplicar el método Simplex o el método de las Dos Fases.
Véase en la figura como debemos actuar para llegar a la solución de
nuestro problema.






Explicaremos paso a paso los puntos de cada método, concretando los
aspectos que hay que tener en cuenta.


Método Simplex

- Construcción de la primera tabla: En la primera columna de la tabla
aparecerá lo que llamaremos base, en la segunda el coeficiente que
tiene en la función objetivo cada variable que aparece en la base
(llamaremos a esta columna Cb), en la tercera el término independiente
de cada restricción (P0), y a partir de ésta columna aparecerán cada
una de las variables de la función objetivo (Pi). Para tener una
visión más clara de la tabla, incluiremos una fila en la que pondremos
cada uno de los nombres de las columnas. Sobre ésta tabla que tenemos
incluiremos dos nuevas filas: una que será la que liderará la tabla
donde aparecerán las constantes de los coeficientes de la función
objetivo, y otra que será la última fila, donde tomará valor la
función objetivo. Nuestra tabla final tendrá tantas filas como
restricciones.



Tabla
C1 C2 ... Cn
Base Cb P0 P1 P2 ... Pn
Pi1 Ci1 bi1 a11 a12 ... a1n
Pi2 Ci2 bi2 a21 a22 ... a2n
... ... ... ... ... ... ...
Pim Cim bim am1 am2 ... amn
Z Z0 Z1-C1 Z2-C2 ... Zn-Cn


Los valores de la fila Z se obtienen de la siguiente forma: El valor
Z0 será el de sustituir Cim en la función objetivo (y cero si no
aparece en la base). El resto de columnas se obtiene restando a este
valor el del coeficiente que aparece en la primera fila de la tabla.

Se observará al realizar el método Simplex, que en esta primera tabla,
en la base estarán las variables de holgura.

- Condición de parada: Comprobaremos si debemos de dar una nueva
iteración o no, que lo sabremos si en la fila Z aparece algún valor
negativo. Si no aparece ninguno, es que hemos llegado a la solución
óptima del problema.

- Elección de la variable que entra: Si no se ha dado la condición de
parada, debemos seleccionar una variable para que entre en la base en
la siguiente tabla. Para ello nos fijamos en los valores estrictamente
negativos de la fila Z, y el menor de ellos será el que nos de la
variable entrante.

- Elección de la variable que sale: Una vez obtenida la variable
entrante, obtendremos la variable que sale, sin más que seleccionar
aquella fila cuyo cociente P0/Pj sea el menor de los estrictamente
positivos (teniendo en cuenta que sólo se hará cuando Pj sea mayor de
0). La intersección entre la columna entrante y la fila saliente nos
determinará el elemento pivote.

- Actualización de la tabla: Las filas correspondientes a la función
objetivo y a los títulos permanecerán inalterados en la nueva tabla.
El resto deberá calcularse de dos formas diferentes:

Si es la fila pivote cada nuevo elemento se calculará:

Nuevo Elemento Fila Pivote = Elemento Fila Pivote actual / Pivote.

Para el resto de elementos de filas se calculará:

Nuevo Elemento Fila = Elemento Fila Pivote actual - (Elemento Columna
Pivote en la fila actual * Nuevo Elemento Fila).

Método de las Dos Fases

Éste método difiere del Simplex en que primero hay que resolver un
problema auxiliar que trata de minimizar la suma de las variables
artificiales. Una vez resuelto este primer problema y reorganizar la
tabla final, pasamos a la segunda fase, que consiste en realizar el
método Simplex normal.

FASE 1

En esta primera fase, se realiza todo de igual manera que en el método
Simplex normal, excepto la construcción de la primera tabla, la
condición de parada y la preparación de la tabla que pasará a la fase
2.

- Construcción de la primera tabla: Se hace de la misma forma que la
tabla inicial del método Simplex, pero con algunas diferencias. La
fila de la función objetivo cambia para la primera fase, ya que cambia
la función objetivo, por lo tanto aparecerán todos los términos a cero
excepto aquellos que sean variables artificiales, que tendrán valor
"-1" debido a que se está minimizando la suma de dichas variables
(recuerde que minimizar F es igual que maximizar F·(-1)).

La otra diferencia para la primera tabla radica en la forma de
calcular la fila Z. Ahora tendremos que hacer el cálculo de la
siguiente forma: Se sumarán los productos Cb·Pj para todas las filas y
al resultado se le restará el valor que aparezca (según la columna que
se éste haciendo) en la fila de la función objetivo.



Tabla
C0 C1 C2 ... Cn-k ... Cn
Base Cb P0 P1 P2 ... Pn-k ... Pn
Pi1 Ci1 bi1 a11 a12 ... a1n-k ... a1n
Pi2 Ci2 bi2 a21 a22 ... a2n-k ... a2n
... ... ... ... ... ... ... ... ...
Pim Cim bim am1 am2 ... amn-k ... amn
Z Z0 Z1 Z2 ... Zn-k ... Zn
Siendo Zj = Σ(Cb·Pj) - Cj y los Cj = 0 para todo j comprendido entre 0
y n-k (variables de decisión, holgura y exceso), y Cj = -1 para todo j
comprendido entre n-k y n (variables artificiales).



- Condición de parada: La condición de parada es la misma que en el
método Simplex normal. La diferencia estriba en que pueden ocurrir dos
casos cuando se produce la parada: la función toma un valor 0, que
significa que el problema original tiene solución, o que tome un valor
distinto, indicando que nuestro modelo no tiene solución.

- 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. Deberemos eliminar las
columnas de las variables artificiales, modificar la fila de la
función objetivo por la original, y calcular la fila Z de la misma
forma que en la primera tabla de la fase 1.



IDENTIFICANDO CASOS ANÓMALOS Y SOLUCIONES

Obtención de la solución: Cuando se ha dado la condición de parada,
obtenemos el valor de las variables básicas que están en la base y el
valor óptimo que toma la función que están en la base mirando la
columna P0. En el caso de que estemos minimizando, se multiplicará por
"-1" el valor óptimo.

Infinitas soluciones: Cumplida la condición de parada, si se observa
que alguna variable que no está en la base, tiene un 0 en la fila Z,
quiere decir que existe otra solución que da el mismo valor óptimo
para la función objetivo. Si estamos ante este caso, estamos ante un
problema que admite infinitas soluciones, todas ellas comprendidas
dentro del segmento (o porción del plano, o región del espacio,
dependiendo del número de variables del problema) que define Ax+By=Z0.
Si se desea se puede hacer otra iteración haciendo entrar en la base a
la variable que tiene el 0 en la fila Z, y se obtendrá otra solución.

Solución ilimitada: Si al intentar buscar la variable que debe
abandonar la base, nos encontramos que toda la columna de la variable
entrante tiene todos sus elementos negativos o nulos, estamos ante un
problema que tiene solución ilimitada. No hay valor óptimo concreto,
ya que al aumentar el valor de las variables se aumenta el valor de la
función objetivo, y no viola ninguna restricción.

No existe solución: En el caso de que no exista solución, seguro que
tendremos que realizar las dos fases, por lo que al término de la
primera sabremos si estamos en tal situación.

Empate de variable entrante: Se puede optar por cualquiera de ellas,
sin que afecte a la solución final, el inconveniente que presenta es
que según por cual se opte se harán más o menos iteraciones. Se
aconseja que se opte a favor de las variables básicas, ya que son
aquellas las que quedarán en la base cuando se alcance la solución con
estos métodos.

Empate de variable saliente: Se puede nuevamente optar por cualquiera
de ellas, aunque se puede dar el caso degenerado y entrar en ciclos
perpetuos. Para evitarlos en la medida de lo posible, discriminaremos
a favor de las variables básicas haciendo que se queden en la base.
Ante el caso de estar en la primera fase (del método de las Dos
Fases), se optará por sacar en caso de empate las variables
artificiales.

Curiosidad Fase 1: Al finalizar la fase 1, si el problema original
tiene solución, todas las variables artificiales, en la fila Z deben
tener el valor "1".

¿Pivote puede ser 0?: No, ya que siempre se realizan los cocientes
entre valores no negativos y mayores que cero.