#include<stdio.h> 
#include<math.h> 
#include<iostream.h> 
float matrix[100][100],x[100]; /* 記錄總方程的數組,解的數組 */ 
int a[100]; /* 記錄基礎,非基礎的解的情況,0:非基礎,1:基礎 */ 
int m,n,s,type; /* 方程變量,約束數,求最大最小值的類型,0:最小 1:最大 */ 
int indexe,indexl,indexg; /* 剩余變量,松弛變量,人工變量 */ 
void Jckxj() 
{ 
int i,j; 
for(i=0;i<n;i++) 
for(j=0;j<s;j++) 
if(matrix[j]==1&&a[j]==1){ 
x[j]=matrix; 
j=s; 
} 
for(i=0;i<s;i++) 
if(a==0) x=0; 
} 

int Rj() 
{ 
int i; 
for(i=0;i<s;i++) 
if(fabs(matrix[n])>=0.000001) 
if(matrix[n]<0) return 0; 
return 1; 
} 

int Min() 
{ 
int i,temp=0; 
float min=matrix[n][0]; 
for(i=1;i<s;i++) 
if(min>matrix[n]){ 
min=matrix[n]; 
temp=i; 
} 
return temp; 
} 

void JustArtificial() 
{ 
int i; 
for(i=m+indexe+indexl;i<s;i++) 
if(fabs(x)>=0.000001){ 
printf("No Answern"); 
return; 
} 
} 

int Check(int in) 
{ 
int i; 
float max1=-1; 
for(i=0;i<n;i++) 
if(fabs(matrix[in])>=0.000001&&max1<matrix/matrix[in]) 
max1=matrix/matrix[in]; 
if(max1<0) 
return 1; 
return 0; 
} 

int SearchOut(int *temp,int in) 
{ 
int i; 
float min=10000; 
for(i=0;i<n;i++) 
if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)&&min>matrix/matrix[in]){ 
min=matrix/matrix[in]; 
*temp=i; 
} 
for(i=0;i<s;i++) 
if(a==1&&matrix[*temp]==1) return i; 
} 

void Mto(int in,int temp) 
{ 
int i; 
for(i=0;i<=s;i++) 
if(i!=in) 
matrix[temp]=matrix[temp]/matrix[temp][in]; 
matrix[temp][in]=1; 
} 

void Be(int temp,int in) 
{ 
int i,j; 
float c; 
for(i=0;i<=n;i++){ 
c=matrix[in]/matrix[temp][in]; 
if(i!=temp) 
for(j=0;j<=s;j++) 
matrix[j]=matrix[j]-matrix[temp][j]*c; 
} 
} 

void Achange(int in,int out) 
{ 
int temp=a[in]; 
a[in]=a[out]; 
a[out]=temp; 
} 

void Print() 
{ 
int i,j,k,temp=0; 
for(i=0;i<n;i++){ 
for(k=temp;k<s;k++) 
if(a[k]==1){ 
printf("X%d ",k); 
temp=k+1; 
k=s; 
} 
for(j=0;j<=s;j++) 
printf("%8.2f",matrix[j]); 
printf("n"); 
} 
printf("Rj "); 
for(j=0;j<=s;j++) 
printf("%8.2f",matrix[n][j]); 
printf("n"); 
} 

void InitPrint() 
{ 
int i; 
printf("X"); 
for(i=0;i<s;i++) 
printf(" a%d",i); 
printf(" bn"); 
Print(); 
printf("n"); 
} 

void Result() 
{ 
int i; 
printf(" ("); 
for(i=0;i<s;i++) 
printf("%8.2f",x); 
printf(" ) "); 
if(type==1) 
printf(" Zmax=%fnn",matrix[n]); 
else printf(" Zmin=%fnn",matrix[n]); 
} 

void PrintResult() 
{ 
if(type==0) printf("The Minimal :%fn",-matrix[n]); 
else printf("The Maximum :%fn",matrix[n]); 
} 

void Merge(float nget[][100],float nlet[][100],float net[][100],float b[]) 
{ 
int i,j; 
for(i=0;i<n;i++){ 
for(j=m;j<m+indexe;j++) 
if(nget[j-m]!=-1) matrix[j]=0; 
else matrix[j]=-1; 
for(j=m+indexe;j<m+indexe+indexl;j++) 
if(nlet[j-m-indexe]!=1) matrix[j]=0; 
else matrix[j]=1; 
for(j=m+indexe+indexl;j<s;j++) 
if(net[j-m-indexe-indexl]!=1) matrix[j]=0; 
else matrix[j]=1; 
matrix=b; 
} 

for(i=m;i<m+indexe+indexl;i++) 
matrix[n]=0; 
for(i=m+indexe+indexl;i<s;i++) 
matrix[n]=100; 
matrix[n]=0; 
} 

void ProcessA() 
{ 
int i; 
for(i=0;i<m+indexe;i++) 
a=0; 
for(i=m+indexe;i<s;i++) 
a=1; 
} 

void Input(float b[],int code[]) 
{ 
int i=0,j=0; 
printf("The equator Variable and Restrictorn"); /* 輸入方程變量和約束數 */ 
cin>>m>>n; 
for(i=0;i<n;i++){ 
printf("Input b[] and Restrictor code 0:<= 1:= 2:>=n"); /* 輸入方程右邊的值,code的值 */ 
cin>>b>>code; 
printf("The XiShun"); 
for(j=0;j<m;j++) 
cin>>matrix[j]; /* 輸入方程 */ 
} 
printf("The Type 0:Min 1:Max n"); /* 輸入求最大值還是最小值 */ 
do{ 
cin>>type; 
if(type!=0&&type!=1) printf("Error,ReInputn"); 
}while(type!=0&&type!=1); 
printf("The Zn"); /* 輸入z */ 
for(i=0;i<m;i++) 
cin>>matrix[n]; 
if(type==1) 
for(i=0;i<m;i++) 
matrix[n]=-matrix[n]; 
} 

void Xartificial() 
{ 
int i,j,k; 
if(indexg!=0){ 
for(i=m+indexe+indexl;i<s;i++){ 
for(j=0;j<n;j++) 
if(matrix[j]==1){ 
for(k=0;k<=s;k++) 
matrix[n][k]=matrix[n][k]-matrix[j][k]*100; 
j=n; 
} 
} 
} 
} 

void Process(float c[][100],int row,int vol) 
{ 
int i; 
for(i=0;i<n;i++) 
if(i!=row) c[vol]=0; 
} 

void Sstart(float b[],int code[]) 
{ 
int i; 
float nget[100][100],nlet[100][100],net[100][100]; /* 剩余變量數組,松弛變量數組,人工變量數組 */ 
indexe=indexl=indexg=0; 
for(i=0;i<n;i++){ 
if(code==0){nlet[indexl++]=1; Process(nlet,i,indexl-1);} 
if(code==1){ net[indexg++]=1; Process(net,i,indexg-1); } 
if(code==2){ 
net[indexg++]=1; 
nget[indexe++]=-1; 
Process(net,i,indexg-1); Process(nget,i,indexe-1); 
} 
} 
s=indexe+indexl+indexg+m; 
Merge(nget,nlet,net,b); /* 合并 */ 
ProcessA(); /* 初始化a[] */ 
InitPrint(); /* 初始化打印 */ 
Xartificial(); /* 消去人工變量 */ 
} 

void Simplix() /* 單純型算法 */ 
{ 
int in,out,temp=0; 
while(1){ 
Jckxj(); /* 基礎可行解 */ 
Print(); /* 打印 */ 
Result(); /* 打印結果 */ 
if(!Rj()) in=Min(); /* 求換入基 */ 
else { 
if(indexg!=0) JustArtificial(); /* 判斷人工變量 */ 
PrintResult(); /* 打印最后結果 */ 
return; 
} 
if(Check(in)){ /* 判斷無界情況 */ 
printf("No Delimitionn"); 
return; 
} 
out=SearchOut(&temp,in); /* 求換出基 */ 
Mto(in,temp); /* 主元化1 */ 
Be(temp,in); /* 初等變換 */ 
Achange(in,out); /* 改變a[]的值 */ 
} 
} 

void main() 
{ 
int code[100]; /* 輸入符號標記 */ 
float b[100]; /* 方程右值 */ 
Input(b,code); /* 初始化 */ 
Sstart(b,code); /* 化標準型 */ 
Simplix(); /* 單純型算法 */ 
}