#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#define M 30000
int r,c; //global parameter row and colum;
int turn = 1;
int variable = 0; //自变量个数,初始化为零,在main函数中设定
int restriction = 0; //约赖条件个数
int maxormin = 0;
int loose = 0; //松驰变量
int remain = 0; //剩余变量
int dummy = 0; //虚拟变量
void title()
{
cout<<"------------------------------------------------------------------------------"<<endl<<endl;
cout<<" 塑性加工优化单纯形(大M法)计算"<<endl<<endl;
cout<<" programmed by:黄俊"<<endl;
cout<<"------------------------------------------------------------------------------"<<endl;
}
float **acquireM(int row1, int colomn1) //creat a matrix
{
int i;
float **ptr1;
ptr1 = new float *[row1];
for(i = 0; i <= row1; i++)
ptr1[i] = new float [colomn1];
return ptr1;
}
/*int numconvert(int i)
{
if(i > 0 && i < c)
{
if(i < r)
i = i + (c - r);
else
i = i - r + 1;
}
else i = -1;
return i;
}*/
void inputobject(float *Min, int temp)
{
int i;
if(maxormin==1)
cout<<"Min = a(";
else
cout<<"Max = a(";
for(i=0; i<temp-1; i++)
{
cout<<i+1<<")X"<<i+1<<"+a(";
}
cout<<temp<<")"<<endl;
for(i=0; i<temp; i++)
{
cout<<"a("<<i+1<<")"<<endl;
cin>>Min[i];
}
if(maxormin==1)
cout<<"目标函数为: Min = ";
else
cout<<"目标函数为: Max = ";
for(i=0; i<temp-1; i++)
{
cout<<Min[i]<<" X"<<i+1<<" + ";
}
cout<<Min[temp-1]<<" 对吗?";
getchar();
if(maxormin==2)
{
cout<<"\n目标函数被转化为: Min = ";
for(i=0; i<temp-1; i++)
{
Min[i]=(-1)*Min[i];
cout<<Min[i]<<" X"<<i+1<<" + ";
}
Min[temp-1]=(-1)*Min[temp-1];
cout<<Min[temp-1]<<endl<<endl;
}
}
void inputstrain(float **strain, int *xx)
{
int i,j;
for(i=0; i<restriction; i++)
{
cout<<"第"<<i+1<<"个约束条件:\t";
for(j=0; j<variable; j++)
{
cout<<"+a("<<i+1<<","<<j+1<<")X("<<j+1<<")";
}
cout<<" >=或< "<<"b("<<i+1<<")"<<endl;
for(j=0; j<variable+2; j++)
{
if(j==variable)
{
do
{
cout<<"等于号请输0,小于号请输1,大于号请输2"<<endl;
cin>>strain[i][j];
if(strain[i][j]==0)
{
dummy++;
cout<<"=\n";
}
else if(strain[i][j]==1)
{
loose++;
cout<<"<\n";
}
else if(strain[i][j]==2)
{
remain++;
dummy++;
cout<<">\n";
}
else
cout<<"输入不对,请重输"<<endl;
}while( strain[i][j]!= 0 && strain[i][j] != 1 && strain[i][j] != 2 );
}
else
{
cout<<"a("<<i+1<<","<<j+1<<") ?"<<endl;
cin>>strain[i][j];
}
}
}
for(i=0; i<restriction; i++)
{
cout<<"\t";
for(j=0; j<variable+2; j++)
{
if(j==variable)
{
if(strain[i][j]==1)
cout<<"<\t";
else if (strain[i][j]==2)
cout<<">\t";
else
cout<<"=\t";
}
else
cout<<strain[i][j]<<"\t";
}
cout<<endl;
}
cout<<"对吗?";
getchar();
r = restriction+1;
c = variable+restriction+remain+1;
for(i=0;i<restriction;i++)
xx[i]=i+variable+1;
}
int initiateM(float **ptr, float **strain, float *Min) //初始化单纯形表
{
int i, j, i1=1, j1=1;
for(i = 0; i < r-1; i++)
ptr[i][0] = strain[i][variable+1];
ptr[r-1][0] = 0;
for(i = 0; i < r-1; i++) //初始化非基变量列
{
for(j = 1; j <= variable; j++)
{
ptr[i][j] = strain[i][j-1];
}
}
for(j=1;j<=variable;j++)
{
ptr[r-1][j]=Min[j-1];
for(i=0;i<r-1;i++)
{
if(strain[i][variable]==0 || strain[i][variable]==2)
ptr[r-1][j]-=strain[i][j-1]*M;
}
}
j = variable+1;
for(i = 0; i < restriction; i++)
{
if(strain[i][variable] == 2)
{
ptr[i][j] = (-1);
ptr[r-1][j] = M;
j++;
}
}
for(i=0; i<r; i++) //初始化基变量列
{
j1=1;
for(j = variable+remain+1; j < c; j++)
{
if(i1 == j1)
ptr[i][j]=1;
else
ptr[i][j]=0;
j1++;
}
i1++;
}
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
cout<<ptr[i][j]<<"\t";
}
cout<<endl;
}
system("cls");
title();
cout<<endl;
}
/*void initiateM1(float **ptr)
{
ptr[0][0]=12;ptr[0][1]=1;ptr[0][2]=0;ptr[0][3]=0;ptr[0][4]=0;ptr[0][5]=2;ptr[0][6]=2;
ptr[1][0]=8; ptr[1][1]=0;ptr[1][2]=1;ptr[1][3]=0;ptr[1][4]=0;ptr[1][5]=1;ptr[1][6]=2;
ptr[2][0]=16;ptr[2][1]=0;ptr[2][2]=0;ptr[2][3]=1; ptr[2][4]=0;ptr[2][5]=4;ptr[2][6]=0;
ptr[3][0]=12;ptr[3][1]=0;ptr[3][2]=0;ptr[3][3]=0;ptr[3][4]=1;ptr[3][5]=0;ptr[3][6]=4;
ptr[4][0]=0; ptr[4][1]=0;ptr[4][2]=0;ptr[4][3]=0;ptr[4][4]=0;ptr[4][5]=-2;ptr[4][6]=-3;
}
void initiateM2(float **ptr)
{
ptr[0][0]=9;ptr[0][1]=1;ptr[0][2]=0;ptr[0][3]=2;ptr[0][4]=2;ptr[0][5]=1;ptr[0][6]=2;ptr[0][7]=-1;ptr[0][8]=0;
ptr[1][0]=19; ptr[1][1]=0;ptr[1][2]=1;ptr[1][3]=3;ptr[1][4]=1;ptr[1][5]=3;ptr[1][6]=2;ptr[1][7]=0;ptr[1][8]=-1;
ptr[2][0]=0;ptr[2][1]=0;ptr[2][2]=0;ptr[2][3]=-100; ptr[2][4]=-50;ptr[2][5]=-98;ptr[2][6]=-108;ptr[2][7]=35;ptr[2][8]=30;
}
*/
void output(float **ptr, int *xx)
{
int i, j;
cout<<"------------------------------------------------------------------------------"<<endl;
cout<<"基变量\tB\t";
for(j = 1; j < c; j++)
cout<<"X"<<j<<"\t";
cout<<endl;
cout<<"------------------------------------------------------------------------------"<<endl;
for(i = 0; i < r-1; i++)
{
cout<<" X"<<xx[i]<<"\t";
for(j = 0; j < c; j++)
cout<<ptr[i][j]<<"\t";
cout<<endl;
}
cout<<"------------------------------------------------------------------------------"<<endl;
cout<<" δi\t\t";
for(j = 1; j < c; j++)
cout<<ptr[r-1][j]<<"\t";
cout<<endl;
cout<<"------------------------------------------------------------------------------"<<endl;
}
int process2(float **ptr) //第二步,确定换入变量
{
int j, value = 1;
float min;
cout<<"第二步:确定换入变量\t\t\t\t\t\t第"<<turn<<"轮"<<endl;
if(c-r > 1)
{
min = ptr[r-1][1];
for(j = 1; j < c; j++)
{
if(min >= ptr[r-1][j])
{
min = ptr[r-1][j];
value = j;
}
}
}
else
{
cout<<"没有非基变量,无法求解!"<<endl;
exit(1);
}
cout<<"换入变量X"<<value<<":"<<min<<endl<<endl;
cout<<"按任意键继续..."<<endl;
getchar();
return value;
}
int process3(float **ptr, int value, int *xx) //第三步,确定主元与换出变量
{
int i, j, row, flag = 0;
float min, k[r-1];
cout<<"第三步:确定主元与换出变量\t\t\t\t\t第"<<turn<<"轮"<<endl;
for(i = 0; i < r-1; i++) //creat k[i] to inherit θ
{
if(ptr[i][value] > 0)
{
k[i] = ((ptr[i][0])/(ptr[i][value]));
flag = 1;
}
else
k[i] = 0;
}
if(flag == 0)
{
row = -1;
min = 0;
}
else
{
for(i = 0; i< r-1; i++) //find first non-zero θ
{
if(k[i] != 0)
{
row = i;
cout<<"θ"<<i+1<<"= "<<k[i]<<"\t";
min = k[i];
break;
}
}
if(i != r-2 && r != 1) //find min non-zero θ
{
for(j = i+1; j< r-1; j++)
{
if( k[j] != 0)
{
cout<<"θ"<<j+1<<"= "<<k[j]<<"\t";
if(k[j] <= min)
{
row = j;
min = k[j];
}
}
}
}
}
cout<<endl<<"θr= min(";
for(i = 0; i < r-1; i++)
if(k[i] != 0)
cout<<k[i]<<",";
cout<<"\b)="<<min<<endl;
cout<<"主元为: a("<<row+1<<","<<value<<")\t换出变量为: X"<<xx[row]<<endl;
xx[row] = value;
cout<<"按任意键继续..."<<endl;
getchar();
return row;
}
void process4(float **ptr, int m, int n)
{
int i, j;
float temp;
temp = ptr[m][n];
for(j = 0; j < c; j++)
ptr[m][j] = ptr[m][j]/temp;
cout<<"第四步:用行变换求出新的单纯形表\t\t\t\t第"<<turn<<"轮"<<endl;
if( m != 0)
for(i = 0; i < m; i++)
{
if(ptr[i][n] != 0)
{
temp = ptr[i][n];
for(j = 0; j < c; j++)
{
ptr[i][j] = ptr[i][j]-ptr[m][j]*temp;
}
}
}
if(m != r-2)
for(i = m+1; i < r-1; i++)
{
if(ptr[i][n] != 0)
{
temp = ptr[i][n];
for(j = 0; j < c; j++)
{
ptr[i][j] = ptr[i][j]-ptr[m][j]*temp;
}
}
}
if(ptr[r-1][n] != 0)
{
temp = ptr[r-1][n];
for(j = 1; j < c; j++)
ptr[r-1][j] = ptr[r-1][j]-ptr[m][j]*temp;
}
}
float result(float **ptr, float *pts, int *xx, float *Min)
{
int i, j , m, n, i1 = 1;
float S=0;
for(i=1;i<=variable;i++)
{
for(j=0;j<restriction;j++)
{
if(xx[j]==i)
pts[i-1]=ptr[j][0];
}
}
for(i = 0; i < variable; i++)
{
cout<<"X"<<i+1<<" = "<<pts[i]<<"\t";
}
if(maxormin == 1)
{
for(i=0;i<variable;i++)
{
S+=pts[i]*Min[i];
}
i++;
S+=Min[i];
}
else
{
for(i=0;i<=variable;i++)
{
Min[i]=(-Min[i]);
}
for(i=0;i<variable;i++)
{
S+=pts[i]*Min[i];
}
i++;
S+=Min[i];
}
return S;
}
int main()
{
int i, j, row, column, flag, *xx;
float **pter,**strain, *pts, *Min,temp;
title();
cout<<"输入自变量个数"<<endl;
cin>>variable;
cout<<"输入约束条件个数"<<endl;
cin>>restriction;
r=restriction+1;
cout<<"求最小值输入1,求最大值输入2"<<endl;
do
{
cin>>maxormin;
if(maxormin != 1 && maxormin != 2)
cout<<"输入不对,请重输"<<endl;
}while( maxormin != 1 && maxormin != 2 );
Min = new float [variable + 1];
xx = new int [restriction];
cout<<"请输入目标函数:"<<endl;
inputobject(Min,variable + 1);
cout<<"请输入约束条件:"<<endl;
strain = acquireM(restriction,variable+2);
inputstrain(strain,xx);
pter = acquireM(r,c);
pts = new float [variable];
initiateM(pter,strain,Min);
cout<<"第一步:作出初始单纯形表\t\t\t\t\t第"<<turn<<"轮"<<endl;
output(pter,xx);
cout<<"按任意键继续..."<<endl;
getchar();
flag = 0;
column = process2(pter);
row = process3(pter, column,xx);
if(row < 0)
exit(1);
process4(pter, row, column);
output(pter,xx);
for(j = 1; j < c; j++)
if(pter[r-1][j] < 0)
{
flag = 1;
cout<<"判别数δ存在非负:"<<pter[r-1][j]<<endl;
cout<<"重复第二步到第四步。"<<endl;
turn++;
break;
}
cout<<"按任意键开始新的一轮..."<<endl;
getchar();
for(j = 1; j < c; j++)
if(pter[r-1][j] < 0)
{
flag = 1;
break;
}
while(flag == 1)
{
flag = 0;
column = process2(pter);
row = process3(pter, column,xx);
if(row < 0)
exit(1);
process4(pter, row, column);
output(pter,xx);
for(j = 1; j < c; j++)
if(pter[r-1][j] < 0)
{
flag = 1;
cout<<"判别数δ存在非负:"<<pter[r-1][j]<<endl;
cout<<"重复第二步到第四步。"<<endl;
turn++;
break;
}
if(flag == 0)
cout<<"判别数δ均为正,计算完成。"<<endl;
else
{
cout<<"按任意键开始新的一轮..."<<endl;
getchar();
}
}
temp = result(pter, pts, xx, Min);
if(maxormin==1)
cout<<"目标函数的极小值为: MinS = ";
else
cout<<"目标函数的极大值为: MaxS = ";
cout<<temp<<endl;
cout<<"按任意键退出..."<<endl;
getchar();
return 0;
}