dcx.cpp

运筹学单纯行程序

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
float fcsz[100][100],d[100][100],x[100];   /* 记录总方程的数组,存放B-1矩阵，解的数组 */
int a[100];                                   /* 记录基础、非基础的解的情况：0为非基础；1为基础 */
float bb[100];                 /* 存放资源数量bi*/
int m,n,s,type;                /* 方程变量,约束数,所有变量个数之和，求最大最小值的类型：0为最小 ；1为最大 */
int sybl,scbl,rgbl;            /* 剩余变量,松弛变量,人工变量 */ 
void Jckxj()                   /* 基础可行解 */
{
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<s;j++)
			if(fcsz[i][j]==1&&a[j]==1)
			{
				x[j]=fcsz[i][s];
				j=s;
			}
	for(i=0;i<s;i++)
		if(a[i]==0) x[i]=0;
}
int Rj()                       /*判断是否为基础的解的情况：0为非基础；1为基础*/
{
int i;
for(i=0;i<s;i++)
	if(fabs(fcsz[n][i])>=0.000001)
	if(fcsz[n][i]<0)
		return 0;
	return 1;
}
int Min()                     /*寻找入基变量*/
{
int i,temp=0;
float min=fcsz[n][0];
for(i=1;i<s;i++)
	if(min>fcsz[n][i])
	{
		min=fcsz[n][i];
		temp=i;
	}
return temp;
}
void JustArtificial()       /*判断人工变量*/
{
int i;
for(i=m+sybl+scbl;i<s;i++)
	if(fabs(x[i])>=0.000001)
	{
		printf("无可行解\n");
		return;
	}
}


int Check(int in)          /* 判断无界情况 */
{
int i;
float max1=-1;
for(i=0;i<n;i++)
if(fabs(fcsz[i][in])>=0.000001&&max1<fcsz[i][s]/fcsz[i][in])
max1=fcsz[i][s]/fcsz[i][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(fcsz[i][in])>=0.000001&&(fcsz[i][s]/fcsz[i][in]>=0)&&min>fcsz[i][s]/fcsz[i][in])
{
	min=fcsz[i][s]/fcsz[i][in];
	*temp=i;
}
for(i=0;i<s;i++)
if(a[i]==1&&fcsz[*temp][i]==1) 
return i;
}


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


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


void Achange(int in,int out)      /* 改变a[]的值 */
{
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+1);
		temp=k+1;
		k=s;
	}
for(j=0;j<=s;j++)
printf("%8.2f",fcsz[i][j]);
printf("\n");
}
printf("检 ");
for(j=0;j<=s;j++)
printf("%8.2f",-fcsz[n][j]);
printf("\n");
}


void cshprint()   /* 初始化打印 */
{
int i;
printf("XB");
for(i=0;i<s;i++)
printf("      X%d",i+1);
printf("      b\n");
Print();
printf("\n");
}



void Result()     /*打印每次变化后的单纯形表*/
{
int i;
printf("X=(");
for(i=0;i<s;i++)
	printf("%8.2f",x[i]);
printf("    )");
if(type==1)
	printf(" Zmax=%f\n\n",fcsz[n][s]);
else 
	printf(" Zmin=%f\n\n",fcsz[n][s]);
}

void PrintResult()             /* 打印最后结果 */
{int i,j;
printf("最优解为(");
for(i=0;i<s;i++)
	printf("%8.2f",x[i]);
    printf("    )\n");
if(type==0) 
	printf("最优值为%f\n",-fcsz[n][s]);
else 
	printf("最优值为%f\n",fcsz[n][s]);

for(i=0;i<n;i++)               /*求B-1矩阵并打印*/
{for(j=s-n+1;j<=s;j++)
d[i][j+n-s-1]=fcsz[i][j-1];}  
printf("矩阵B-1为\n");
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
printf("%8.2f",d[i][j]);
printf("\n");}
}

void Merge(float sy[][100],float sc[][100],float rg[][100],float b[])   /* 合并 */
{
int i,j;
for(i=0;i<n;i++)
{
	for(j=m;j<m+sybl;j++)
	if(sy[i][j-m]!=-1) 
		fcsz[i][j]=0;
	else 
		fcsz[i][j]=-1;
	for(j=m+sybl;j<m+sybl+scbl;j++)
		if(sc[i][j-m-sybl]!=1)
			fcsz[i][j]=0;
		else 
			fcsz[i][j]=1;
	for(j=m+sybl+scbl;j<s;j++)
	if(rg[i][j-m-sybl-scbl]!=1) 
		fcsz[i][j]=0;
	else 
		fcsz[i][j]=1;
	fcsz[i][s]=b[i];
}
for(i=m;i<m+sybl+scbl;i++)
	fcsz[n][i]=0;
for(i=m+sybl+scbl;i<s;i++)
	fcsz[n][i]=100;
fcsz[n][s]=0;
}


void ProcessA()             /* 初始化a[] */
{
int i;
for(i=0;i<m+sybl;i++)
a[i]=0;
for(i=m+sybl;i<s;i++)
a[i]=1;
}


void Input(float b[],int code[])
{
int i=0,j=0;
printf("输入变量个数和约束条件个数\n"); /* 输入变量个数和约束数 */
cin>>m>>n;
for(i=0;i<n;i++)
{
	printf("输入第%d约束条件右边的值和约束类型（0为<= ；1为= ；2为>=）\n",i+1); /* 输入约束条件右边的值,code的值 */
	cin>>b[i]>>code[i];
        bb[i]=b[i];
	printf("输入第%d约束条件系数\n",i+1);
	for(j=0;j<m;j++)
		cin>>fcsz[i][j];   /* 输入约束条件*/
}
printf("输入求最大值还是最小值（0为Min ；1为Max ）\n"); /* 输入求最大值还是最小值 */
do
{
	cin>>type;
	if(type!=0&&type!=1)
		printf("输入错误\n");
}while(type!=0&&type!=1);
printf("输入Z的各个系数\n"); /* 输入z*/
for(i=0;i<m;i++)
	cin>>fcsz[n][i];
	if(type==1)
		for(i=0;i<m;i++)
			fcsz[n][i]=-fcsz[n][i];
}


void Xartificial()     /* 消去人工变量 */
{
int i,j,k;
if(rgbl!=0)
{
	for(i=m+sybl+scbl;i<s;i++)
	{
		for(j=0;j<n;j++)
			if(fcsz[j][i]==1)
			{
				for(k=0;k<=s;k++)
					fcsz[n][k]=fcsz[n][k]-fcsz[j][k]*100;
				j=n;
			}
	}
}
}



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



void standardize(float b[],int code[])             /* 化标准型 */
{
int i;
float sy[100][100],sc[100][100],rg[100][100]; /* 剩余变量数组,松弛变量数组,人工变量数组 */
sybl=scbl=rgbl=0;
for(i=0;i<n;i++)
{
if(code[i]==0)
{
	sc[i][scbl++]=1; Process(sc,i,scbl-1);
}
if(code[i]==1)
{ 
	rg[i][rgbl++]=1; Process(rg,i,rgbl-1); 
}
if(code[i]==2)
{
	rg[i][rgbl++]=1;
	sy[i][sybl++]=-1;
	Process(rg,i,rgbl-1); 
	Process(sy,i,sybl-1);
}
}
s=sybl+scbl+rgbl+m;
Merge(sy,sc,rg,b);   /* 合并 */
ProcessA();               /* 初始化a[] */
cshprint();               /* 初始化打印 */
Xartificial();            /* 消去人工变量 */
}


void simple()             /* 单纯型算法 */
{ 
int in,out,temp=0;
while(1){
Jckxj();                 /* 基础可行解 */
Print();                 /* 打印 */
Result();                /* 打印结果 */
if(!Rj()) in=Min();      /* 求换入基 */
else {
if(rgbl!=0) JustArtificial();    /* 判断人工变量 */
PrintResult();                   /* 打印最后结果 */
return;
}
if(Check(in)){                   /* 判断无界情况 */
printf("无界解\n");
return;
}
out=SearchOut(&temp,in);         /* 求换出基 */
Mto(in,temp);                    /* 主元化1 */
Be(temp,in);                     /* 初等变换 */
Achange(in,out);                 /* 改变a[]的值 */
}
}
void lmdfx()
{float c[100][100];
int i,j;
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
c[i][j]=(fcsz[j][s]-d[j][i]*bb[i])/d[j][i];
}
printf("资源数量bi的变化范围:如有#不考虑此数\n");
for(i=0;i<n;i++)
{printf("b%d",i+1);
{for(j=0;j<n;j++)
if(d[j][i]>=0)
{printf(">=%f",-c[i][j]);
printf("\n");}
else
{printf("<=%f",-c[i][j]);
printf("\n");}}}
}

void main()
{
int code[100];          /* 输入符号标记 */
float b[100];           /* 方程右值 */
Input(b,code);          /* 初始化 */
standardize(b,code);    /* 化标准型 */
simple();               /* 单纯型算法 */ 
lmdfx();                /*灵敏度分析*/       
}