(全部指针)单纯型法解线性规划问题（两阶段法）.cpp

单纯型法解线性规划问题（两阶段法）指针改写.

/*************************************************************************
                    单纯型法解线性规划问题（两阶段法）      
编程环境：VC++6.0     
方程组输入说明：
变量非负，按提示输入相关参数。
*************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
#define MAX 257 //n=7
#define STP 100000
int base_elem;
int base_out,base_in;
int stop=1; //迭代记数变量
int status; //iterative迭代返回值：1唯一最优，0无界解，-1无穷多最优解 -2迭代超过限制次数
int step=1; //目前阶段 
double **a,*b,*c,*temp_c,max=0; //方程组相关系数
int num_x; //变量个数 
int num_st; //约束方程数
int num_ar=0; //人工变量个数
int *arti; //人工变量下标
double *sigma;
int *base; //基变量下标
int ma_mi; //1为求最大值，2为求最小值 
void Create(); //建立方程组
void iterative(); //单纯型法迭代
void Output(); //输出结果
void Exchange(double *c,double *temp_c); //交换两阶段价值系数
//########################################################################
void main() {
int i,j,k;
b=new double [MAX];c=new double [MAX];temp_c=new double [MAX];
a=new double *[MAX];
for(i=0;i<MAX;i++) *(a+i)=new double[MAX];
arti=new int[MAX];
base=new int[MAX];
sigma=new double [MAX];
////////////////////////////////////////*/
Create();				//建立方程组
/*///////////////////////////////////////////////////////////////////////////////
cout<<"指定变量个数：";
cout<<num_x; 
cout<<"\n输入函数f=max()系数c1-c"<<num_x<<endl;
for(i=1;i<=num_x/2;i++)  cout<<*(c+i);     
cout<<"\n输入约束方程组个数：";         cout<<num_st;
cout<<"\n输入方程系数矩阵：\n";
for(i=1;i<=num_st;i++) 
for(j=1;j<=num_x/2;j++) cout<<*(*(a+i)+j)<<"	"; 
cout<<"\n输入常数项向量b"<<i<<":"<<endl;
for(i=1;i<=num_st/2;i++) cout<<*(b+i)<<"	";  
////////////////////////////////////////////////////////////////////////////////*/
for(i=1;i<=num_x;i++) {	//保存原价值系数，转换为第一阶段价值系数
  k=0;
  for(j=1;j<=num_ar;j++) if(i==*(arti+j)) k=1;
  if(k==1) *(temp_c+i)=-1;
  else *(temp_c+i)=0;
}
Exchange(c,temp_c); 
step++;
iterative();
if(status==-2) {
  puts("迭代超过限制次数强行终止！\n");
  puts("\n按回车结束");
  getchar();
  exit(0);
}
//Output(); 
if(max!=0) {
  puts("\n\n原问题无可行解。\n");
  puts("\n按回车结束");
  getchar();
  exit(0);
} 
Exchange(c,temp_c);//转换为第二阶段价值系数
for(i=1;i<=num_ar;i++) {//把人工变量列全设为0
  c[arti[i]]=0;
  for(j=1;j<=num_st;j++) *(*(a+j)+*(arti+i))=0;
} 
iterative();
	switch(status) {
	case 1:
	  Output();
	  puts("\n\n原问题有唯一最优解。\n");
	  puts("\n按回车结束");
	  getchar();
	  break;
	case 0:
	  puts("\n\n原问题为无界解。\n");
	  puts("\n按回车结束");
	  getchar();
	  break;
	case -1:
	  Output();
	  puts("\n\n原问题有无穷多最优解。\n");
	  puts("\n按回车结束");
	  getchar();
	  break;
	case -2:
	  puts("迭代超过限制次数强行终止！\n");
	  puts("\n按回车结束");
	  getchar();
	  break;
	}//switch
cout<<endl;getch();
} 
//########################################################################
void Exchange(double *c,double *temp_c) {
int i;double* temp;
temp=new double[MAX];
	for(i=1;i<=num_x;i++) {
	  temp[i]=*(temp_c+i);
	  *(temp_c+i)=*(c+i);
	  *(c+i)=temp[i];
	}
delete[] temp;
} 
//########################################################################
void Create() {//输入方程组系数，每个方程输完后回显确认
int i,j,*re_st,tnum_x,num_addv=0,num_ba=0;
re_st=new int [MAX];
ma_mi=1;//printf("请选择：1、求最大值，2、求最小值：(1/2)");
////////////////////////////////////////////////////////////////////////////////
//输入参数形式：
//f=max(和a[i]);
//s.t. AX<=b
////////////////////////////////////////////////////////////////////////////////
cout<<"指定变量个数：";
cin>>num_x; 
cout<<"输入函数f=max()系数c1-c"<<num_x<<endl;for(i=1;i<=num_x;i++)  cin>>*(c+i);     
cout<<"输入约束方程组个数：";         cin>>num_st;
for(i=1;i<=num_st;i++)re_st[i]=3;//cout<<"请选择：1、==，2、>=，3、<= ：(1/2/3)";
cout<<"输入方程系数矩阵：\n";
for(i=1;i<=num_st;i++) 
for(j=1;j<=num_x;j++) cin>>*(*(a+i)+j); 
cout<<"输入常数项向量b"<<i<<":"<<endl;
for(i=1;i<=num_st;i++) cin>>*(b+i);  
cout<<"输入参数完毕!"<<endl;getch();
/////////////////////////////////////////////////////////////////////////////////
tnum_x=num_x;
for(i=1;i<=num_st;i++) {
  switch(re_st[i]) {
  case 1:
  case 3:
   num_x+=1;
   break;
  case 2:
   num_x+=2;
   break;
  }
} 
//化为标准形式
if(ma_mi==2) for(i=1;i<=tnum_x;i++) *(c+i)*=-1; //求最小值时，系数变相反数
for(i=1;i<=num_st;i++) {
  switch(re_st[i]) {
   case 1:
    num_addv++;
    num_ba++;
    num_ar++;
    c[tnum_x+num_addv]=0; 
    base[num_ba]=arti[num_ar]=tnum_x+num_addv;
    for(j=tnum_x+1;j<=num_x;j++) 
     if(j==tnum_x+num_addv) a[i][tnum_x+num_addv]=1;
     else *(*(a+i)+j)=0;
    break;
   case 2:
    num_addv++;
    c[tnum_x+num_addv]=0;
    num_addv++;
    num_ba++;
    num_ar++;
    c[tnum_x+num_addv]=0; 
    base[num_ba]=arti[num_ar]=tnum_x+num_addv;
    for(j=tnum_x+1;j<=num_x;j++) 
     if(j==tnum_x+num_addv-1) a[i][tnum_x+num_addv-1]=-1;
     else if(j==tnum_x+num_addv) a[i][tnum_x+num_addv]=1;
     else *(*(a+i)+j)=0;
    break;
   case 3:
    num_addv++;
    num_ba++;
    c[tnum_x+num_addv]=0;
    base[num_ba]=tnum_x+num_addv;
    for(j=tnum_x+1;j<=num_x;j++) 
     if(j==tnum_x+num_addv) a[i][tnum_x+num_addv]=1;
     else *(*(a+i)+j)=0;
    break;
  }//switch
}//增加松弛变量、剩余变量、人工变量、确定基变量
delete[] re_st;
}
//########################################################################
void iterative() {
int i,j,k,k_a,k_f,l; //k_a,k_f值为0或1，记录当前下标在arti[]或base[]里的搜索结果
double temp;
double *sigma;sigma=new double [MAX];
double value_be; //高斯消元里保存主元素值 
//求检验数sigma
for(i=1;i<=num_x;i++) {
  *(sigma+i)=*(c+i);
  for(j=1;j<=num_st;j++) *(sigma+i)-=*(c+*(base+j))**(*(a+j)+i);
  for(j=1;j<=num_st;j++) if(i==*(base+j)) *(sigma+i)=0;
  switch(step) {
   case 1:
//    cout<<"sigma["<<i%<<"]="<<*(sigma+i)<<"\t";
    break;
   case 2:
    k_a=0;
    for(l=1;l<=num_ar;l++) if(i==*(arti+l)) k_a=1;
//    if(k_a!=1) printf("sigma[%d]=%lg\t",i,*(sigma+i));
    break;
  }
}
//检验检验数sigma是否全小于等于0
k=0;
for(i=1;i<=num_x;i++) {
  if(*(sigma+i)>0) 
  k=1;
}
if(k==0) {
  for(i=1;i<=num_x;i++){//sigma是全小于等于0时，检查是否为无穷多最优解
   k_f=k_a=0;
   for(j=1;j<=num_ar;j++)
   if(i==*(arti+j)) k_a=1;
   if(*(sigma+i)==0&&k_a!=1) {
    for(j=1;j<=num_st;j++) if(i==*(base+j)) k_f=1;
   if(k_f==0) {status=-1;return;}
   }
  }
  status=1; 
  return;
}
for(i=1;i<=num_x;i++) { //检查是否为无界解
  k_f=0;
  if(*(sigma+i)>0) {
   for(j=1;j<=num_st;j++) if(*(*(a+j)+i)>0) k_f=1;
   if(k_f!=1) {status=0;  return;}
  }
} 
//确定换入变量
for(i=1;i<=num_x;i++) { 
  k=0;
  for(j=1;j<=num_st;j++) if(i==*(base+j)) k=1;
  if(k==0&&*(sigma+i)>0) temp=*(sigma+i)-1;
}//temp赋初值
for(i=1;i<=num_x;i++) {
  k=0;
  for(j=1;j<=num_st;j++) if(i==*(base+j)) k=1;
  if(k==0)
   if(*(sigma+i)>temp&&*(sigma+i)>0) {
    base_in=i;
    temp=*(sigma+i);
   }
} 
//确定换出变量
for(i=1;i<=num_st;i++) 
  if((*(*(a+i)+base_in))>0) {
   temp=*(b+i)/(*(*(a+i)+base_in))+1;
   break;
  }//temp赋初值
for(i=1;i<=num_st;i++) {
  if(*(b+i)/(*(*(a+i)+base_in))<=temp&&(*(*(a+i)+base_in))>0) {
   for(j=1;j<=num_ar;j++)
    if(*(base+i)==*(arti+j)) { 
     base_out=*(base+i);
     base_elem=i;
     temp=*(b+i)/(*(*(a+i)+base_in));
     break;
    }
  }//人工变量优先换出
  if(*(b+i)/(*(*(a+i)+base_in))<temp&&(*(*(a+i)+base_in))>0) {
   base_out=*(base+i);
   base_elem=i;
   temp=*(b+i)/(*(*(a+i)+base_in));
  }
} 
//printf(" 基变量：");
//for(i=1;i<=num_st;i++) printf("x[%d] ",*(base+i));
//printf("换入变量：x[%d] 换出变量：x[%d]",base_in,base_out);
//基变量变换，进行新方程初始化后迭代
for(i=1;i<=num_st;i++) {
  if(*(base+i)==base_out) *(base+i)=base_in;
}
//初始化主元素行系数
value_be=a[base_elem][base_in];
b[base_elem]/=value_be;
for(i=1;i<=num_x;i++) *(*(a+base_elem)+i)/=value_be; 
for(i=1;i<=num_st;i++) {
  if(i!=base_elem) {
   *(b+i)-=b[base_elem]*(*(*(a+i)+base_in));
   value_be=(*(*(a+i)+base_in));
   for(j=1;j<=num_x;j++) *(*(a+i)+j)-=*(*(a+base_elem)+j)*value_be;
  }
}
stop++;cout<<"stop="<<stop<<endl;
if(stop>STP) {status=-2; return;}
iterative();
} 
//########################################################################
void Output() {
int i,j;
double *X;X=new double[MAX];
cout<<endl<<"结果如下:"<<endl;
cout<<"\nX=(";
for(i=1;i<=num_x;i++) {
  for(j=1;j<=num_st;j++)
  if(i==*(base+j)) {*(X+i)=*(b+j);break;}
  else *(X+i)=0;
} 
for(i=1;i<=num_x/2;i++) cout<<*(X+i)<<" ";
cout<<")";
for(i=1;i<=num_x;i++) max+=*(c+i)**(X+i);
if(ma_mi==1) cout<<"\nMax f="<<max<<endl;
else cout<<"Min f="<<-max<<endl;
delete[]X; 
}
//########################################################################