单纯形法.cpp

用c实现的单纯算法！！ 输入标准矩阵就可以了！！

// 单纯形法.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "math.h"
#define MAXSIZE 10
#define N 6
#define T 3
#define ERROR 0
#define OK 1
typedef struct{
	int row,col;
	float data;
}MNode;
float c[N],a[T][N]/*约束系数*/,b[T]/*资源常数*/,CB[T]/*初始级变量*/, Cn[N]/*目标函数系数*/;
int Bt[T];
MNode Mf;
//***********************
void Find_Mf()
{	int i;
	int max,min;
	float th[T] /*进级出级变量*/;
	max=0;
	for(i=1;i<N;i++)
		if(Cn[i]>Cn[max]) max=i;
	Mf.col =max;//主元所在的列
	for(i=0;i<T;i++)
	{
		if(a[i][Mf.col]>0) th[i]=b[i]/a[i][Mf.col];
		else th[i]=-1;
		if(i==0) min=0;
		else 
		{
			if((th[i]>0)&&(th[i]<th[min])) min=i;
		}
	}
	Mf.row=min;//主元所在行
	Mf.data=a[Mf.row][Mf.col];
	Bt[Mf.row]=Mf.col ;//改变基变量
	CB[Mf.row]=c[Mf.col];//改变基变量在目标函数中的系数

}
//*****************************
void Chang_process()
{
	int i,j;
	float t;
	for(j=0;j<N;j++)
		a[Mf.row][j]=a[Mf.row][j]/Mf.data;
	b[Mf.row]=b[Mf.row]/Mf.data;
	for(i=0;i<T;i++)
	{
		if(i==Mf.row) continue;
		t=a[i][Mf.col];
		b[i]=b[Mf.row]*(-t)+b[i];
		for(j=0;j<N;j++)
			a[i][j]=a[Mf.row][j]*(-t)+a[i][j];
		
	}
	for(j=0;j<N;j++)
		Cn[j]=(-Cn[Mf.col])*a[Mf.row][j]+Cn[j];
}
//**************************************	
int Initialize()
{	int i,j,k,flag;
	float sum=0;
	printf("请输入目标函数的系数：");
	for(i=0;i<N;i++)
		scanf("%f",&c[i]);
	printf("请输入线性规划问题的约束矩阵：\n");
	for(i=0;i<T;i++)
	{	for(j=0;j<N;j++)
			scanf("%f",&a[i][j]);
		scanf("%f",&b[i]);
	}
	for(i=0;i<T;i++)//找单位矩阵
		for(j=0;j<N;j++)
		{	
			if(a[i][j]==1)
			{	flag=0;
				for(k=0;k<T;k++)
				{	if(k==i) continue;
					if(a[k][j]!=0) flag=1;
				}
				if(flag==0) { Bt[i]=j+1;break;	}//确定初始基
				
			}
			if(j==N-1) return ERROR;
			
		}

	for(j=0;j<N;j++)//求检验数		
	{	sum=0;
		for(i=0;i<T;i++)
			sum+=CB[i]*a[i][j];
		Cn[j]=c[j]-sum;//确定初始检验数
	}
	for(j=0;j<N;j++)
		if(Cn[j]>0) break;
	return OK;
}
//*****************************************************
int main(int argc, char* argv[])
{	
	float max_Z,sum=0;
	int i,j,Circle_num=0;

	if(!Initialize()) {	printf("ERROR!!!\n");return 0;}
	while(j<N) 
	{	Circle_num++;
		Find_Mf();
		Chang_process();
		for(j=0;j<N;j++)
			if(Cn[j]>0) break;
		if(Circle_num==2) 
		{
			for(i=0;i<T;i++)
			{	printf("\n%.2f  ",b[i]);
				for(j=0;j<N;j++)
					printf("%.2f ",a[i][j]);
				printf("\n");
			}
			for(j=0;j<N;i++)
				printf("%.2f",c[j]);
			printf("\n");
		}
	}
	printf("目标函数的基解为:");
	sum=0;
	for(i=0;i<T;i++)			
	{	sum+=CB[i]*b[i];
		printf("\nx%d=%.2f",Bt[i]+1,b[i]);
	}
	max_Z=sum;
	printf("\n目标函数的值为：max_Z= %.2f\n",max_Z);
	return 0;
}