使用C语言实现单纯形法求解线性规划问题

自动化系上机实验报告（课程名称：运筹学）学生姓名：学号：3/29/20206:21:20PM第1页共11页上机实验报告班级：自动化班专业/方向：自动化姓名：实验成绩(10分制)学号：上机实验名称：使用C语言实现单纯形法求解线性规划问题上机时间：2015年5月20日上机地点：信自234一、实验目的和要求1、目的：掌握单纯形算法的计算步骤，并能熟练使用该方法求解线性规划问题。了解算法程序实现的过程和方法。2、要求：使用熟悉的编程语言编制单纯形算法的程序。独立编程，完成实验，撰写实验报告并总结。二、实验内容和结果1、单纯形算法的步骤及程序流程图。（1）、算法步骤（1）将线性规划化为标准形。（2）用最快的方法确定一个初始基本可行解X（0）。当s·t均为“≤”形式时，以松驰变量做初始基本变量最快。（3）求X（0）中非基本变量xj的检验数σj。若0j，则停止运算，X（0）=X*（表示最优解），否则转下一步。（4）①由}0{maxjjk确定xk进基；②由lklikikiikabaabx}0|{min确定xl出基，其中alk称为主元素；③利用初等变换将alk化为1，并利用alk将同列中其它元素化为0，得新解X（1）。（5）返回（3），直至求得最优解为止。自动化系上机实验报告（课程名称：运筹学）学生姓名：学号：3/29/20206:21:20PM第2页共11页（2）、程序图2、单纯形算法程序的规格说明各段代码功能描述：（1）、定义程序中使用的变量#includestdio.h#includemath.h#definem3/*定义约束条件方程组的个数*/#definen5/*定义未知量的个数*/floatM=1000000.0;floatA[m][n];/*用于记录方程组的数目和系数;*/floatC[n];/*用于存储目标函数中各个变量的系数*/找出初始基可行解列出初始单纯形表计算校验数所有δj=0?对于某个δj0，是否存在Pj=0确定为入基变量确定出基变量计算新的单纯形表已得最优解，结束无最优解，结束自动化系上机实验报告（课程名称：运筹学）学生姓名：学号：3/29/20206:21:20PM第3页共11页floatb[m];/*用于存储常约束条件中的常数*/floatCB[m];/*用于存储基变量的系数*/floatseta[m];/*存放出基与入基的变化情况*/floatdelta[n];/*存储检验数矩阵*/floatx[n];/*存储决策变量*/intnum[m];/*用于存放出基与进基变量的情况*/floatZB=0;/*记录目标函数值*/（2）、定义程序中使用的函数voidinput();voidprint();intdanchunxing1();intdanchunxing2(inta);voiddanchunxing3(inta,intb);(3)、确定入基变量，对于所有校验数均小于等于0，则当前解为最优解。intdanchunxing1(){inti,k=0;intflag=0;floatmax=0;for(i=0;in;i++)if(delta[i]=0)flag=1;else{flag=0;break;}if(flag==1)return-1;for(i=0;in;i++){if(maxdelta[i]){max=delta[i];k=i;}}returnk;}(4)、确定出基变量，如果某个大于0的校验数，对应的列向量中所有元素小于等于0，则线性规划问题无解。intdanchunxing2(inta){inti,k,j;intflag=0;floatmin;k=a;for(i=0;im;i++)if(A[i][k]=0)flag=1;else{flag=0;break;}if(flag==1)自动化系上机实验报告（课程名称：运筹学）学生姓名：学号：3/29/20206:21:20PM第4页共11页{printf(\n该线性规划无最优解!\n);return-1;}for(i=0;im;i++){if(A[i][k]0)seta[i]=b[i]/A[i][k];elseseta[i]=M;}min=M;for(i=0;im;i++){if(min=seta[i]){min=seta[i];j=i;}}num[j]=k+1;CB[j]=C[k];returnj;}(5)、迭代运算，计算新的单纯形表。voiddanchunxing3(intp,intq){inti,j,c,l;floattemp1,temp2,temp3;c=p;/*行号*/l=q;/*列号*/temp1=A[c][l];b[c]=b[c]/temp1;for(j=0;jn;j++)A[c][j]=A[c][j]/temp1;for(i=0;im;i++){if(i!=c)if(A[i][l]!=0){temp2=A[i][l];b[i]=b[i]-b[c]*temp2;for(j=0;jn;j++)A[i][j]=A[i][j]-A[c][j]*temp2;}}temp3=delta[l];for(i=0;in;i++)delta[i]=delta[i]-A[c][i]*temp3;}自动化系上机实验报告（课程名称：运筹学）学生姓名：学号：3/29/20206:21:20PM第5页共11页(6)、输入函数，输入方程组的系数矩阵、初始基变量的数字代码、方程组右边的值矩阵、目标函数各个变量的系数所构成的系数阵。voidprint(){inti,j=0;printf(\n--------------------------------------------------------------------------\n);for(i=0;im;i++){printf(%8.2f\tX(%d)%8.2f,CB[i],num[i],b[i]);for(j=0;jn;j++)printf(%8.2f,A[i][j]);printf(\n);}printf(\n--------------------------------------------------------------------------\n);printf(\t\t\t);for(i=0;in;i++)printf(%8.2f,delta[i]);printf(\n--------------------------------------------------------------------------\n);}voidinput(){inti,j;/*循环变量*/intk;printf(请输入方程组的系数矩阵A(%d行%d列):\n,m,n);for(i=0;im;i++)for(j=0;jn;j++)scanf(%f,&A[i][j]);printf(\n请输入初始基变量的数字代码num矩阵:\n);for(i=0;im;i++)scanf(%d,&num[i]);printf(\n请输入方程组右边的值矩阵b:\n);for(i=0;im;i++)scanf(%f,&b[i]);printf(\n请输入目标函数各个变量的系数所构成的系数阵C:\n);for(i=0;in;i++)scanf(%f,&C[i]);for(i=0;in;i++)delta[i]=C[i];for(i=0;im;i++){k=num[i]-1;CB[i]=C[k];}}(7)、主函数，调用前面定义的函数。自动化系上机实验报告（课程名称：运筹学）学生姓名：学号：3/29/20206:21:20PM第6页共11页main(){inti,j=0;intp,q,temp;input();printf(\n--------------------------------------------------------------------------\n);printf(\tCB\tXB\tb\t);for(i=0;in;i++)printf(X(%d)\t,i+1);for(i=0;in;i++)x[i]=0;printf(\n);while(1){q=danchunxing1();if(q==-1){print();printf(\n所得解已经是最优解!\n);printf(\n最优解为:\n);for(j=0;jm;j++){temp=num[j]-1;x[temp]=b[j];}for(i=0;in;i++){printf(x%d=%.2f,i+1,x[i]);ZB=ZB+x[i]*C[i];}printf(ZB=%.2f,ZB);break;}print();p=danchunxing2(q);printf(\np=%d,q=%d,p,q);if(q==-1)break;danchunxing3(p,q);}}输入:（1）、输入方程组的系数矩阵A(3行5列)（2）、输入初始基变量的数字代码num矩阵（3）、输入方程组右边的值矩阵b（4）、输入目标函数各个变量的系数所构成的系数阵C自动化系上机实验报告（课程名称：运筹学）学生姓名：学号：3/29/20206:21:20PM第7页共11页输出：（1）、输出是否为最优解（2）、输出最优解为多少3、使用所编程序求解如下LP问题并给出结果。P26例5程序运行结果请输入方程组的系数矩阵A(3行5列):221004001005001请输入初始基变量的数字代码num矩阵:345请输入方程组右边的值矩阵b:121615请输入目标函数各个变量的系数所构成的系数阵C:23000--------------------------------------------------------------------------CBXBbX(1)X(2)X(3)X(4)X(5)--------------------------------------------------------------------------0.00X(3)12.002.002.001.000.000.000.00X(4)16.004.000.000.001.000.000.00X(5)15.000.005.000.000.001.00--------------------------------------------------------------------------2.003.000.000.000.00--------------------------------------------------------------------------p=2,q=1--------------------------------------------------------------------------0.00X(3)6.002.000.001.000.00-0.400.00X(4)16.004.000.000.001.000.003.00X(2)3.000.001.000.000.000.202.000.000.000.00-0.60--------------------------------------------------------------------------p=0,q=0--------------------------------------------------------------------------2.00X(1)3.001.000.000.500.00-0.200.00X(4)4.000.000.00-2.001.000.803.00X(2)3.000.001.000.000.000.20-----------------------------------------------------------------------