simplex.c

这是运筹学中关于单纯形算法的c程序

#define X 5
#define Y 7
void xi_max(int *m2,
            int *mn1,
            float *c,
            int *is,
            int *ir,
            int *j0,
            float (*a)[X][Y] )
{
	int j;
	*c=0;
	for(j=1; j<=*is; j++)
	{
		if( (*a)[*ir][j] - *c > 0 )
		{
			*c = (*a)[*ir][j];
			*j0 = j;
			
		}		
	}
	
}  /* End of Func */

int xi_sm( int m, int n,
           int m2,
           int mn1,
           int l1,
           float (*a)[X][Y],
           int(*k)[],
           float (*x)[]   )
{
	int i, m1, mn, j0, i0, j;
	float c, g;
	m1 = m + 1;
	mn = m + n;
	for (i=1; i<=m; i++)
	{
		(*k)[i] = n + i;
	lo :
		if(l1 - 1 == 0)
		xi_max(&m2, &mn1, &c, &mn, &m1, &j0, a);
		else
		{
		loop :
			if(l1 - 50 == 0)
			xi_max(&m2, &mn1, &c, &n, &m2, &j0, a);
			else
			xi_max(&m2, &mn1, &c, &mn, &m2, &j0, a);
		}
		
		c = c - 1e-8;
		if( (c<=0) && (l1==1) && ( (*a)[m1][mn1] - 1e-8 > 0)    )
		{
			printf(" \n **** NOT MINZ = 0 NO-SOLUTION ********\n");
			return(-1);
		}
		if( (c<0) && (l1==1) )
		{
			l1 = 50;
			goto loop ;
		}
		if ( c<=0 )
		{
			for(i=1; i<=m; i++ )
			     (*x)[i] = (*a)[i][mn1];
			printf(" \n **** OPTIMAL - SOLUTION **** \n");
			for(i=1; i<=m; i++ )
			printf(" \n I = %d, X[i] = %f \n", (*k)[i], (*x)[i] );
			printf(" \n F = %f \n ", (*a)[m2][mn1]);
			return (0); 
		} 
	c = 1e8;
	for(i=1; i<=m; i++)
	{
		if( (*a)[i][j0] > 1e-8)
		{
			g=(*a)[i][mn1]/(*a)[i][j0];
			if( g - c < 0 )
			{ c=g; i0=i; }
		}
	}
 }
	if(c==1e+8)
	{
		printf(" \n ***** LP-NO-SOLUTION **** \n");
		return (-3);
	} 
	(*k)[i0] = j0;
	for(j=1; j<= mn1; j++)
	{
		if( ( j == j0 ) || ( l1 == 50 ) && ( n<j ) && ( j<mn1 ) )
		     continue;
		g=(*a)[i0][j]/(*a)[i0][j0];
		(*a)[i0][j] = g;
		for(i=1; i<=m2; i++)
		{
			if( (i==i0) || ( !(l1==1) && (i==m1) )    )
				continue;
			(*a)[i][j] = (*a)[i][j] - (*a)[i][j0]*g;
			
		}
	}
	for(i=1; i<=m2; i++)
	       (*a)[i][j0] = 0;
	(*a)[i0][j0] = 1;
	goto lo ;
	  
}/* End of Func */


#include <stdio.h>
#include <math.h>

main()
{
	float a[5][7]={   { 0, 0, 0, 0, 0, 0,  0},
					  { 0, 3,-4, 3, 1, 0, 12},
					  { 0, 3, 0, 6, 0, 1, 12},
					  { 0, 0, 0, 0, 0, 0,  0},
					  { 0,69, 0,144,0, 0,300}
		          };
	int k[3];
	float x[3];
	int rtn;
	rtn = xi_sm( 2, 3, 4, 6, 0, &a, &k, &x);
} /* End of main */