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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Si el sistema que se tiene es de m-ecuaciones con n-incógnitas, se establece que el número de
soluciones básicas está dado por el número de combinaciones de n-variables tomadas de m en m,
es decir:

Del ejemplo anterior, encontramos los puntos de la a a la e, teniendo las siguientes bases:

siendo 4 incógnitas (x1, x2, y1, y2) y 2 ecuaciones, por lo que:

Con las soluciones básicas y los conceptos del conjunto convexo se pueden resumir las siguientes
tres características:

• Las restricciones factibles forman un conjunto convexo cuyos extremos son
soluciones factibles.

• Si las restricciones definen una solución factible, existe cuando menos una
solución básica factible.
• Si la función objetivo tiene un máximo finito, entonces al menos una de las so-
luciones óptimas es una solución básica factible.

Por esto, se puede concluir lo siguiente:

• La solución existe y es única.

• Existe un número infinito de soluciones y están acotadas.

• Existe un número infinito de soluciones que no están acotadas.

• No existe solución.

116