实验三单纯型法.doc

实验3 单纯形法求解线性规划实验内容：用单纯形法求解下列线性规划实验源程序#include#include#includefloat matrix100100,x100; /* 记录总方程的数组,解的数组 */int a100; /* 记录基础,非基础的解的情况,0:非基础,1:基础 */int m,n,s,type; /* 方程变量,约束数,求最大最小值的类型,0:最小 1:最大 */int indexe,indexl,indexg; /* 剩余变量,松弛变量,人工变量 */ void Jckxj()int i,j;for(i=0;in;i+)for(j=0;js;j+)if(matrixij=1&aj=1)xj=matrixis;j=s;for(i=0;is;i+)if(ai=0) xi=0;int Rj()int i;for(i=0;i=0.000001)if(matrixni0) return 0;return 1;int Min()int i,temp=0;float min=matrixn0;for(i=1;imatrixni)min=matrixni;temp=i;return temp;void JustArtificial()int i;for(i=m+indexe+indexl;i=0.000001)printf(No Answern);return;int Check(int in)int i;float max1=-1;for(i=0;i=0.000001&max1matrixis/matrixiin)max1=matrixis/matrixiin;if(max10)return 1;return 0;int SearchOut(int *temp,int in) int i;float min=10000;for(i=0;i=0.000001&(matrixis/matrixiin=0)&minmatrixis/matrixiin)min=matrixis/matrixiin;*temp=i;for(i=0;is;i+)if(ai=1&matrix*tempi=1) return i;void Mto(int in,int temp)int i;for(i=0;i=s;i+)if(i!=in)matrixtempi=matrixtempi/matrixtempin;matrixtempin=1;void Be(int temp,int in)int i,j;float c;for(i=0;i=n;i+)c=matrixiin/matrixtempin;if(i!=temp)for(j=0;j=s;j+)matrixij=matrixij-matrixtempj*c;void Achange(int in,int out)int temp=ain;ain=aout;aout=temp;void Print()int i,j,k,temp=0;for(i=0;in;i+)for(k=temp;ks;k+)if(ak=1)printf(X%d ,k);temp=k+1;k=s;for(j=0;j=s;j+)printf(%8.2f,matrixij);printf(n);printf(Rj );for(j=0;j=s;j+)printf(%8.2f,matrixnj);printf(n);void InitPrint()int i;printf(X);for(i=0;is;i+)printf( a%d,i);printf( bn);Print();printf(n);void Result()int i;printf( ();for(i=0;is;i+)printf(%8.2f,xi);printf( ) );if(type=1)printf( Zmax=%fnn,matrixns);else printf( Zmin=%fnn,matrixns);void PrintResult()if(type=0) printf(The Minimal :%fn,-matrixns);else printf(The Maximum :%fn,matrixns);void Merge(float nget100,float nlet100,float net100,float b)int i,j;for(i=0;in;i+)for(j=m;jm+indexe;j+)if(ngetij-m!=-1) matrixij=0;else matrixij=-1;for(j=m+indexe;jm+indexe+indexl;j+)if(nletij-m-indexe!=1) matrixij=0;else matrixij=1;for(j=m+indexe+indexl;js;j+)if(netij-m-indexe-indexl!=1) matrixij=0;else matrixij=1;matrixis=bi;for(i=m;im+indexe+indexl;i+)matrixni=0;for(i=m+indexe+indexl;is;i+)matrixni=100;matrixns=0;void ProcessA()int i;for(i=0;im+indexe;i+)ai=0;for(i=m+indexe;imn;for(i=0;in;i+)printf(Input b and Restrictor code 0:=n); /* 输入方程右边的值,code的值 */cinbicodei;printf(The XiShun);for(j=0;jmatrixij; /* 输入方程 */printf(The Type 0:Min 1:Max n); /* 输入求最大值还是最小值 */docintype;if(type!=0&type!=1) printf(Error,ReInputn);while(type!=0&type!=1);printf(The Zn); /* 输入z */for(i=0;imatrixni;if(type=1)for(i=0;im;i+)matrixni=-matrixni;void Xartificial()int i,j,k;if(indexg!=0)for(i=m+indexe+indexl;is;i+)for(j=0;jn;j+)if(matrixji=1)for(k=0;k=s;k+)matrixnk=matrixnk-matrixjk*100;j=n;void Process(float c100,int row,int vol)int i;for(i=0;in;i+)if(i!=row) civol=0;void Sstart(float b,int code)int i;float nget100100,nlet100100,net100100; /* 剩余变量数组,松弛变量数组,人工变量数组 */indexe=indexl=indexg=0;for(i=0;in;i+)if(codei=0)nletiindexl+=1; Process(nlet,i,indexl-1);if(codei=1) netiindexg+=1; Process(net,i,indexg-1); if(codei=2)netiindexg+=1;ngetiindexe+=-1;Process(net,i,indexg-1); Process(nget,i,indexe-1);s=indexe+indexl+indexg+m;Merge(nget,nlet,net,b); /* 合并 */ProcessA(); /* 初始化a */InitPrint(); /* 初始化打印 */Xartificial(); /* 消去人工变量 */void Simplix() /* 单纯型算法 */int in,out,temp=0;while(1)Jckxj(); /* 基础可行解 */Print(); /* 打印 */Result(); /* 打印结果 */if(!Rj() in=Min(); /* 求换入基 */else if(indexg!=0) JustArtificial(); /* 判断人工变量 */PrintResult(); /* 打印最后结果 */return;if(Check(in) /* 判断无界情况 */printf(No Delimitionn);return;out=SearchOut(&temp,in); /* 求换出基 */Mto(in,temp); /* 主元化1 */Be(temp,in); /* 初等变换 */Achange(in,out); /* 改变a的值 */void main()int code100; /* 输入符号标记 */float b100; /* 方程右值 */In