danchun0326.cpp

对偶单纯型算法

#include<stdio.h>
#include<math.h>
#define M 4                                      //标准化后的系数矩阵行数
#define N 5                                      //标准化后的矩阵列数
//double a[M][N],b[N];

int S_minl(double a[M][N])                       //返回最小负数值所在的列 l
{
	int j,l=0;
	double temp;
	temp=a[M-1][0];
	for(j=1;j<N;j++)
	{
		if(temp>a[M-1][j])
		{temp=a[M-1][j];
		l=j;
		}
	}
	//printf("\n");
		if(temp<0)
			return l; 
		else return(-1);                         // 返回 seide 的值，全大于零时返回 -1，迭代结束！
}

int S_minh(double a[M][N],double b[M],int l)     //返回所在列的最小行值 h
{
    int i,h=0;
    double p[M],temp=65535;
    for(i=0;i<M-1;i++)
	{  if(a[i][l]==0)
	   p[i]=65535;
       p[i]=(double)b[i]/a[i][l];
	   if(p[i]<0)
	   {
		    printf("o[%d]==NULL\n",i+1);
			continue;
	   }
	   printf("o[%d]==%lf\n",i+1,temp);
       if(p[i]<temp)
	   {temp=p[i];
	    h=i;
	   }  
	   if(temp<=0)
		   printf("目标函数具有无界值 \n");
	}
	//printf("o(temp)=%lf\t",temp);
	//printf("\n");
    if(temp>0)
	return h;
    else
        return -1;

}

void Solve(double a[M][N],double b[M],int m,int n)      //对所在列行进行高斯消去法进行化简迭代
{
    int i,j;
    double k=a[n][m];
    for(i=0;i<N;i++)
		a[n][i]=a[n][i]/k;                              //对所在行进行单位化
	b[n]/=k;
	i=0;
		for(i=0;i<M;i++)                               //  高斯消去  
		{       if(i==n)
                        continue;
			k=a[i][m];
			for(j=0;j<N;j++)
				a[i][j]-=k*a[n][j];
			b[i]-=k*b[n];
		}
       /* for(i=0;i<M-1;i++)
			printf("X=%lf\t",b[i]);
		    printf("f(X*)=%lf",b[i]);*/
}

void main()
{
int i,j,x,y,c=0;
//double a[M][N],b[N];
static double a[M][N]={1,2,1,0,0,4,0,0,1,0,0,4,0,0,1,
                       -2,-3,0,0,0},b[M]={8,16,12,0};           //初始化
/*printf("please input array a and b after normaled\n");
printf("please input array a\n");
for(i=0;i<M;i++)
for(j=0;j<N;j++)
scanf("%lf",&a[i][j]);
printf("please input array b\n");
for(i=0;i<M;i++)
scanf("%lf",&b[i]);*/

//printf("迭代次数\tN==%d\n",c+1);
//x=S_minl(a);
while(1)
{
	printf("迭代次数\tN==%d\n",c+1);
    x=S_minl(a);
    y=S_minh(a,b,x);
    Solve(a,b,x,y);
    c++;
	printf("lie 列数==%d\thang 行数=%d\n",c,x,y);
    //printf("\n\n迭代次数\tN==%d\nlie 列数==%d\thang 行数=%d\n",c,x,y);
	for(i=0;i<M-1;i++)
			printf("X=%lf\n",b[i]);
		    printf("f(X*)=%lf\n",b[M-1]);
    printf("(OBJECT VALUE IS：)目标函数值是：%lf\n\n",b[M-1]);

    if(x==-1)
	   {
		printf("此时目标函数值已经达到最大\n");
		break;
	
	}
}
//printf("%d",S_minh(a,b,3));
for(i=0;i<M;i++)
{
	for(j=0;j<N;j++)
		printf("%lf\t",a[i][j]);
	//{printf("a[%d][%d]==%lf\t",i+1,j+1,a[i][j]);
	//if(j%2==0)
	//printf("\n");
	//printf("\n");
	//}
}
	printf("\n");
for(i=0;i<M;i++)
printf("b[%d]==%lf\t",i+1,b[i]);	
printf("\n");
}