#include<stdio.h>
#include<conio.h>
#define F 3
#define J 11
int K,M,N,Q=10000,Type,Get,Let,Et,Code[50],XB[50],IA,IAA[50],Indexg,Indexl,Indexe;
float Sum,A[50][50],B[50],C[50];
void initiate();
void System_exit();
void solve();
void Show_Information();
void Read_data();
void Contral_input();
void judge();
void Read_object();


/******   initiate variables function  ******/
void initiate()
{
 int i,j;
 Indexg=K;
 Indexl=Indexg+Get;
 Indexe=Indexl+Let;;
 for(i=0;i<M+1;i++)
    for(j=K;j<N+1;j++)
	A[i][j]=0;
 for(i=0;i<M;i++)
    A[i][N]=B[i];
 for(i=0;i<M;i++)
    {/*Indexg+=Code[i];*/
     switch(Code[i])
       {case 0:	{
		 XB[i]=Indexl;
		 A[i][Indexl++]=1;
		 break;
		};
	case 1:	{XB[i]=Indexe;
		 IAA[IA++]=i;
		 A[i][Indexe++]=1;
		 A[i][Indexg++]=-1;
		 break;
		};
	case 2:	{XB[i]=Indexe;
		 IAA[IA++]=i;
		 A[i][Indexe++]=1;
		 break;
		};
       }
     }
 for(j=0;j<K;j++)
     if(Type)
	 A[M][j]=-C[j];
     else
	 A[M][j]=C[j];
 for(j=K;j<=N;j++)
    A[M][j]=0;
 if(Type)
    for(j=K+Get+Let;j<N;j++)
       A[M][j]=Q;
 else
    for(j=K+Get+Let;j<N;j++)
       A[M][j]=Q;
 Sum=0;
 for(j=0;j<=N;j++)
    {Sum=0;
     for(i=0;i<IA;i++)
     Sum=Sum+A[IAA[i]][j];
     A[M][j]=A[M][j]-Sum*Q;
    }
 return;
}
void  solve()
{
 int i,j,mark=1,minus,minusmark,basic=0,dividemark,temp;
 int tem1[15],tem2[15];
 float H,P,divide;
 for(i=0;i<15;i++)
    {tem1[i]=0;tem2[i]=0;}
 while(1)
    {mark=0;
     minusmark=0;
     minus=0;divide=65535;
     dividemark=0;
     printf("Basic solution %d is",++basic);
     for(i=0;i<M;i++)
	printf("Basic variable %d = X( %d )= %f\n",i+1,XB[i]+1,A[i][N]);
     printf("Current value of the object equation is:      %f",A[M][N]);
     getch();
     for(i=0;i<M;i++)
	{for(j=i+1;j<M;j++)
	    if(XB[i]==XB[j])
		System_exit();
	}
     for(j=0;j<N;j++)
	{
	 if(A[M][j]<-6e-8)
	     mark++;
	 if(A[M][j]<minus)
	     {minus=A[M][j];
	      minusmark=j;
	     }
	}
     if(mark==0)
	{for(i=0;i<M;i++)
	    if(XB[i]>=M) System_exit();
	 break;
	}
     for(i=0;i<M;i++)
	{if(A[i][minusmark]==0)  continue;
	 if(A[i][N]/A[i][minusmark]<=0) continue;
	 if(A[i][N]/A[i][minusmark]<divide)
	    {divide=A[i][N]/A[i][minusmark];
	     dividemark=i;
	    }
	}
     if(minusmark>XB[dividemark]) System_exit();
     XB[dividemark]=minusmark;
     if(divide<0)
	 printf("There is no solution because of no boundary!");
     P=A[dividemark][minusmark];
     for(j=0;j<N+1;j++)
	A[dividemark][j]=A[dividemark][j]/P;
     for(i=0;i<M+1;i++)
	{H=A[i][minusmark];
	 if(i==dividemark)
	 continue;
	 for(j=0;j<N+1;j++)
	    A[i][j]=A[i][j]-H*A[dividemark][j];
	}
    }
 printf("*************************************The last basic solution is optimal!************************************* ");
 return;
}
void System_exit()
{printf("There is no answer is this question!Program Exit");
 getch();
 exit(0);
}
void Show_Information()
{textbackground(BLACK);
 textcolor(WHITE);clrscr();
 printf("     #                                                             \n");
 printf("     # 1-- Max of the linear program              \n");
 printf("                                                                 \n");
 printf("     #  2-- Min of the linear program               \n");
 
 printf("     #  3-- Quit the program                            \n");

 printf("     #   Please Select:                                    \n");

 gotoxy(24,14);
}
void Read_data()
{textbackground(BLACK);
 textcolor(WHITE);
 clrscr();
printf("Please enter the number of variables:");
 scanf("%d",&K); 
printf("Please enter the number of the subjective equation :");
 scanf("%d",&M);
 Read_object();
 printf("\nThe subjective equations is:\n");
 Contral_input();
 N=K+Let+2*Get+Et;
}
void Show_biao()
{int i;
 printf("\n [     ]*X1");
 for(i=1;i<K;i++)
    {printf("+[     ]*");
     printf("X%d",i+1);
    }
}

void Contral_input()
{int y,i,j;
 for(i=0;i<M;i++)
    {Show_biao();printf(" =[     ]");
     y=wherey();
     for(j=0;j<K;j++)
	{gotoxy(F+j*J,y);scanf("%f",&A[i][j]);
	}
     gotoxy(F+j*J-2,y); judge(i);
     gotoxy(F+j*J+1,y); scanf("%f",&B[i]);
    }
 for(i=0;i<M;i++)
    if(Code[i]==0) Let++;
    else if(Code[i]==1) Get++;
    else if(Code[i]==2) Et++;
}
void judge(int i)
{char c;
 scanf("%c",&c);
 scanf("%c",&c);
 if(c=='<') Code[i]=0;
 else if(c=='>') Code[i]=1;
 else Code[i]=2;
}
void Read_object()
{int y,i;
 if(Type) printf("Max z=");
 else printf("Min z=");
 Show_biao();
 y=wherey();
 for(i=0;i<K;i++)
    {gotoxy(F+i*J,y);scanf("%f",&C[i]);}
}
void main()
{
 int i,j,tp=1;
 char c;
 while(tp)
    {Show_Information();
     c=getch();
     switch(c)
       {case '1' : Type=1;Read_data();tp=0;break;
	case '2' : Type=0;Read_data();tp=0;break;	
	case '3' : exit(0);
       }
    }
 printf("WnWn#################Please check the data you just input!Wn#########################Wn ");
 getch();
 if(Type)
    printf("solution to the 'max' problem!Wn");
 else
    printf("solution to the 'min' problem!Wn");
 printf("WnThe object equation is :Wn");
 for(j=0;j<K;j++)
     {printf("(%f)X%d ",C[j],j+1);
      if(j!=K-1)
	  printf("+");
     }
 printf("WnWnThe suject equation is :");
 for(i=0;i<M;i++)
     {printf("\nNumber %d suject equation is: %d   %f  ",i+1,Code[i],B[i]);
      for(j=0;j<K;j++)
	 {printf("(%f)X%d ",A[i][j],j+1);
	  if(j!=K-1)
	  printf("+");
	 }
     }
 initiate();
 solve();
 if(!Type)
     A[M][N]=-A[M][N];
     printf("The optimal value of the original objective function is:   %f  ",A[M][N]);
     getch();
}