Campus Sur

Ingeniería en Sistemas Computacionales.

Temas Selectos de Ingeniería en Sistemas Computacionales I.

08/Agosto/2001.

Introducción.

Los programas matemáticos implican 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 las restricciones 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 programas lineales 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 ecuaciones lineales 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 la q-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ón objetivo.

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 pivote y 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( float)); a = calloc ( e+1, sizeof( float*)); x = calloc ( e+1, sizeof( unsigned)); h = calloc ( n+1, sizeof( float)); v = calloc ( e+1, sizeof( float)); for ( i=0;i<n;i++) { printf ("Coef. x(%u) en la ec. del Maximo:",i+1); scanf ("%f",&c[i]); } for ( j=0;j<e;j++) { a[j] = calloc ( n+1, sizeof(float)); for ( i=0;i<n;i++) { printf ("Coef. x(%u) en la %u ec.:",i+1,j+1); scanf ("%f",&a[j][i]); } printf ("Term.Indep. de la %u ec.:",j+1); scanf ("%f",&a[j][n]); printf ("Subindice de variable aux. de la inecuacion h(i)"); scanf ("%u",&x[j]); x[j]--; }

Preparación de la matriz de datos.

for ( i=0; i<=n;i++ ){ a[e][i]=-c[i]; for ( j=0;j<e;j++){ a[e][i]+=a[j][i]*c[x[j]]; }

} for (i=0; i< n; i++ ){ printf ("c(%u)= %7.2f\n", i+1,c[i]); }

Obtención de la columna del elemento pivote.

bi=1; for ( i=0;i<n;i++){ if ( a[e][i]< a[e][bi] ) bi=i; } if ( a[e][bi]>=0 ) break;

Obtención de la fila del elemento pivote.

bj=1; for ( j=0;j<e;j++){ if ( a[j][n]*a[bj][bi] < a[bj][n]*a[j][bi] ) bj=j; } printf ("+"); for ( i=0;i<n+2;i++) printf ("--------"); printf ("+\n"); for ( j=0; j< e; j++){ printf ("| x%u | %7.2f | ",x[j]+1,a[j][n] ); for ( i=0; i<n; i++ ){ if ((i==bi)&&(j==bj)) { printf ("%7.2f*",a[j][i] ); } else { printf ("%7.2f ",a[j][i] ); } } printf("|\n"); } printf ("+"); for ( i=0;i<n+2;i++) printf ("--------"); printf ("+\n"); printf (" | %7.2f | ",a[e][n] ); for ( i=0; i<n; i++ ){ printf ("%7.2f ",a[e][i] ); } printf("|\n\n");

Guardar los datos de la fila y columna.

for (i=0;i<=n;i++ ){ h[i]=a[bj][i]; } for ( j=0;j<=e;j++ ){ v[j]=a[j][bi]; } for (i=0;i<=n;i++ ){ for ( j=0;j<=e;j++ ){ a[j][i] -= h[i]*v[j]/h[bi]; } } for (i=0;i<=n;i++ ){ a[bj][i]=h[i]/v[bj]; } x[bj]= bi; }

Se muestra la solución.

printf ("+"); for ( i=0;i<n+2;i++) printf ("--------"); printf ("+\n"); for ( j=0; j< e; j++){ printf ("| x%u | %7.2f | ",x[j]+1,a[j][n] ); for ( i=0; i<n; i++ ){ printf ("%7.2f ",a[j][i] ); } printf("|\n"); }printf ("+"); for ( i=0;i<n+2;i++) printf ("--------"); printf ("+\n"); printf (" | %7.2f | ",a[e][n] ); for ( i=0; i<n; i++ ){ printf ("%7.2f ",a[e][i] ); } printf("|\n\n"); printf ("\nSolucion:\n"); for ( j=0; j<e; j++){ printf ("x%u=%7.2f\n",x[j]+1,a[j][n]); }

Se libera el espacio de variables.

for ( j=0; j<=e; j++) free(a[j]); free(c); free(a); free(x); free(h); free(v); return 0;}