Page 117 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Figura 5.5. Región no factible

Observando la figura 5.5, el conjunto de soluciones del sistema de desigualdades no determina nin-
guna región factible, ya que se tienen dos regiones, lo cual solo satisface a alguna restricción sin po-
der formar una región para el conjunto de restricciones. Este tipo de problemas carece de solución.

Método de gauSS

Como ya se comentó anteriormente, el algoritmo Simplex se sustenta en el método de Gauss, en
donde cada cambio de base se localiza la intersección de una recta, un plano o un hiperplano con
otra recta, plano o hiperplano.

Para poder entender mejor el conjunto de intersecciones de Ax = b, es necesario hablar acerca de
las variables básicas. Una variable básica genera el espacio. La forma más sencilla de ver las varia-
bles básicas es la matriz identidad, que siempre formará una base.

Cambio de base

Para poder entender mejor el conjunto de soluciones de Ax = b, es necesario hablar acerca de las
variables básicas (VB) y las no básicas (VNB). En un sistema de n ecuaciones con m incógnitas se
puede añadir un conjunto de n variables en las cuales forman una base ortonormal. En este caso, si
se tiene Ax = b, se pueden añadir las variables de la siguiente forma: Ax + Iy = b, donde el vector y
forma una base ortonormal.

111