Metodo simplex

[pic]

Campus Sur

Ingeniería en Sistemas Computacionales.

Temas Selectos de Ingeniería en Sistemas Computacionales I.

08/Agosto/2001.

Introducción.

Los programas matemáticosimplican a un conjunto de variables relacionadas por un conjunto de ecuaciones matemáticas (restricciones) y una función objetivo que contiene a las variables y que debe maximizarse respetando lasrestricciones dadas, de aquí que si todas las ecuaciones en juego son simples combinaciones lineales de las variables, se tenga un programa lineal.

Para resolver este tipo de ecuaciones, o programaslineales se emplea el método simplex el cual consiste en una región convexa definida por intersecciones de semiplanos, este método consiste en agregar variables de holgura a cada un de las ecuacioneslineales con la finalidad de convertirlas en igualdades, luego se hace una tabla con los coeficientes de estas igualdades incluyendo a la función objetivo a la cual se le cambia el signo, formando asíun matriz de coeficientes.

De esta matriz se selecciona un elemento [p][q], después se multiplica la p-ésima fila por un escalar apropiado y se suma a todas las filas restantes para llenar laq-esima columna de ceros excepto el elemento de la fila q que se pone a 1y así sucesivamente hasta que se llega a una matriz que tiene en su diagonal principal solamente 1 maximizando así la funciónobjetivo.

Lo siguiente es un algoritmo que nos permite implementar el método simplex en donde primero se toman los valores de los coeficientes, se crea la matriz se obtienen la columna del pivotey posteriormente la fila, se guardan los elementos se transforman y se imprimen para finalizar liberando el espacio de las variables.

Algoritmo en C del Método Simplex.

int main ( ) {unsigned n,e,*x;
float *c,**a,*h,*v;
unsigned i,j,bi,bj;

Toma de datos.

printf ("Num. var.: ");
scanf ("%u",&n);
printf ("Num. inec.: ");
scanf ("%u",&e);
c = calloc ( n+1, sizeof(...