// 單純形法.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]/*約束系數(shù)*/,b[T]/*資源常數(shù)*/,CB[T]/*初始級(jí)變量*/, Cn[N]/*目標(biāo)函數(shù)系數(shù)*/;
int Bt[T];
MNode Mf;
//***********************
void Find_Mf()
{	int i;
	int max,min;
	float th[T] /*進(jìn)級(jí)出級(jí)變量*/;
	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];//改變基變量在目標(biāo)函數(shù)中的系數(shù)

}
//*****************************
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("請(qǐng)輸入目標(biāo)函數(shù)的系數(shù)：");
	for(i=0;i<N;i++)
		scanf("%f",&c[i]);
	printf("請(qǐng)輸入線性規(guī)劃問(wèn)題的約束矩陣：\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++)//求檢驗(yàn)數(shù)		
	{	sum=0;
		for(i=0;i<T;i++)
			sum+=CB[i]*a[i][j];
		Cn[j]=c[j]-sum;//確定初始檢驗(yàn)數(shù)
	}
	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("目標(biāo)函數(shù)的基解為:");
	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目標(biāo)函數(shù)的值為：max_Z= %.2f\n",max_Z);
	return 0;
}