通用对偶单纯形法的C语言程序.doc

#include#include#define MAX_N 100#define M 1000000.0;int m,n;float AMAX_NMAX_N,CMAX_N,bMAX_N,setaMAX_N,CZMAX_N;int numMAX_N;int GetOutCow()/求换出基int i,k;int flag;float min=0;for(i=0;i=0) flag=1;elseflag=0;break;if(flag=1)return -1;for(i=0;im;i+)if(bibi)min=bi;k=i;return k; int GetInCow(int p)/求换入基int i,j;int flag=0;float min;for(j=0;j=0)flag=1;elseflag=0;break;if(flag=1)printf(n原线性规划问题无可行解！n);return -1;for(j=0;jn;j+)if(Apj0)setaj=CZj/Apj;elsesetaj=M;min=M;for(j=0;j=setaj)min=setaj;i=j;nump=i+1;return i; void change(int p,int q)/计算新的单纯形表int i,j;float temp1,temp2,temp3;temp1=Apq;for(i=0;im;i+)if(i!=p)if(Aiq!=0)temp2=Aiq/temp1;for(j=0;jn;j+)Aij=Aij-Apj*temp2;bi=bi-bp*temp2;temp3=CZq/temp1;for(i=0;in;i+)CZi=CZi-Api*temp3;for(j=0;jn;j+)Apj=Apj/temp1;bp=bp/temp1; void print1()int i;printf(n-n);printf(t);for(i=1;i=n;i+)printf(X(%d)t,i);printf(RHSn);printf(-n);printf(t);for(i=0;in;i+)printf(%.3ft,-Ci);printf(n-n);void print2()int i,j;printf(n-n);for(i=0;im;i+)printf(X(%d)t,numi);for(j=0;jn;j+)printf(%.3ft,Aij);printf(%.3fn,bi);printf(n-n);printf(cj-zjt);for(i=0;in;i+)printf(%.3ft,CZi);printf(n-n);void Input()int i,j;printf(请输入约束条件的个数:n);scanf(%d,&m);printf(请输入变量的个数：n);scanf(%d,&n);printf(请输入方程组的系数矩阵A(%d行 %d列):n,m,n);for(i=0;im;i+)for(j=0;jn;j+)scanf(%f,&Aij);printf(n请输入初始基变量的数字代码num矩阵：n);for(i=0;im;i+)scanf(%d,&numi);printf(n请输入方程组右边的值矩阵b:n);for(i=0;im;i+)scanf(%f,&bi);printf(n请输入目标函数各个变量的系数阵C:n);for(i=0;in;i+)scanf(%f,&Ci);void main()int i,j;int p,q;float z=0;Input();for(i=0;im;i+)if(Ainumi-1=0) bi=-bi; for(j=0;jn;j+) Aij=-Aij;for(i=0;in;i+)CZi=-Ci;print1();print2();while(1)p=GetOutCow();if(p=-1)printf(n所得解已经是最优解！n);for(i=0;im;i+)z+=bi*Cnumi-1;for(i=0;im;i+)printf(X(%d)=%.3ft,numi,bi);printf(z=%.3fn,z);break;q=GetInCow(p);if(q=-1)break;change(p,q);print2();if(flag=1)return -1;for(i=0;im;i+)if(bibi)min=bi;k=i;return k; int GetInCow(int p)/求换入基int i,j;int flag=0;float min;for(j=0;j=0)flag=1;elseflag=0;break;if(flag=1)printf(n原线性规划问题无可行解！n);return -1;for(j=0;jn;j+)if(Apj0)setaj=CZj/Apj;elsesetaj=M;min=M;for(j=0;j=setaj)min=setaj;i=j;nump=i+1;return i; void change(int p,int q)/计算新的单纯形表int i,j;float temp1,temp2,temp3;temp1=Apq;for(i=0;im;i+)if(i!=p)if(Aiq!=0)temp2=Aiq/temp1;for(j=0;jn;j+)Aij=Aij-Apj*temp2;bi=bi-bp*temp2;temp3=CZq/temp1;for(i=0;in;i+)CZi=CZi-Api*temp3;for(j=0;jn;j+)Apj=Apj/temp1;bp=bp/temp1; void print1()int i;printf(n-n);printf(t);for(i=1;i=n;i+)printf(X(%d)t,i);printf(RHSn);printf(-n);printf(t);for(i=0;in;i+)printf(%.3ft,-Ci);printf(n-n);void print2()int i,j;printf(n-n);for(i=0;im;i+)printf(X(%d)t,numi);for(j=0;jn;j+)printf(%.3ft,Aij);printf(%.3fn,bi);printf(n-n);printf(cj-zjt);for(i=0;in;i+)printf(%.3ft,CZi);printf(n-n);void Input()int i,j;printf(请输入约束条件的个数:n);scanf(%d,&m);printf(请输入变量的个数：n);scanf(%d,&n);printf(请输入方程组的系数矩阵A(%d行 %d列):n,m,n);for(i=0;im;i+)for(j=0;jn;j+)scanf(%f,&Aij);printf(n请输入初始基变量的数字代码num矩阵：n);for(i=0;im;i+)scanf(%d,&numi);printf(n请输入方程组右边的值矩阵b:n);for(i=0;im;i+)scanf(%f,&bi);printf(n请输入目标函数各个变量的系数阵C:n);for(i=0;in;i+)scanf(%f,&Ci);void main()int i,j;int p,q;float z=0;Input();for(i=0;im;i+)if(Ainumi-1=0) bi=-bi; for(j=0;jn;j+) Aij=-Aij;for(i=0;in;i+)CZi=-Ci;print1();print2();while(1)p=GetOutCow();if(p=