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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

el taBleau de tucker para el Método SIMplex

El problema de programación lineal escrito en forma estándar es de siguiente:

Se puede reescribir de la siguiente forma:

Las restricciones son ahora un conjunto de relaciones lineales, con la restricción adicional de que
tanto las variables independientes (X) como las dependientes (Y) son no-negativas.
Este problema se puede resumir en una tabla, que en la terminología del método Simplex se llama
tableau de Tucker, de la siguiente forma:

El tableau contiene relaciones lineales que representan a las restricciones y a la función objetivo. La
hilera i de la tabla que se leerá como que es igual a
multiplicar la hilera i de la matriz A por el vector (-X) y sumarle b , es decir,
1
El tableau representará el punto X en el espacio Rn, que se obtiene al hacer cero las variables inde-
pendientes. En el tableau inicial, generalmente, este punto es y el
valor de la función objetivo que se obtiene en ese punto es cero, que es el elemento que aparece en
la última celda de la última columna del tableau. Por ejemplo:

119