自动化系上机实验报告（课程名称：运筹学） 学生姓名： 学号：
上 机 实 验 报 告
班级：自动化班 姓名： 学号： 专业/方向：自动化 实 验 成 绩 (10分制) 上机实验名称：使用C语言实现单纯形法求解线性规划问题 上机时间：2015年5月20日 上机地点：信自234 一、实验目的和要求
1、目的：
? 掌握单纯形算法的计算步骤，并能熟练使用该方法求解线性规划问题。 ? 了解算法?程序实现的过程和方法。 2、要求：
? 使用熟悉的编程语言编制单纯形算法的程序。 ? 独立编程，完成实验，撰写实验报告并总结。
二、实验内容和结果
1、单纯形算法的步骤及程序流程图。 （1）、算法步骤
（1）将线性规划化为标准形。 （2）用最快的方法确定一个初始基本可行解X（0）。当s·t均为“≤”形式时，以松驰变量做初始基本变量最快。 （3）求X（0）中非基本变量xj的检验数σj。若??j?0，则停止运算，X（0）=X*（表示最优解），否则转下一步。 （4）①由?k?max{?j?0}确定xk进基； j②由xk?min{ibib|aik?0}?l确定xl出基，其中alk称为主元素； aikalk③利用初等变换将alk化为1，并利用alk将同列中其它元素化为0，得新解X（1）。 （5）返回（3），直至求得最优解为止。 6/2/2015 11:31:56 PM 第 1 页 共 11 页
自动化系上机实验报告（课程名称：运筹学） 学生姓名： 学号：
（2）、程序图 找出初始基可行解列出初始单纯形表 计算校验数 所有δj<=0? 已得最优解，结束 计算新的单纯形表 对于某个δj>0，是否存在Pj<=0 无最优解，结束 确定为入基变量 确定出基变量 2、单纯形算法程序的规格说明 各段代码功能描述：
（1）、定义程序中使用的变量 #include
#define m 3 /*定义约束条件方程组的个数*/ #define n 5 /*定义未知量的个数*/ float M=1000000.0;
float A[m][n]; /*用于记录方程组的数目和系数;*/
float C[n]; /*用于存储目标函数中各个变量的系数*/
6/2/2015 11:31:56 PM 第 2 页 共 11 页
自动化系上机实验报告（课程名称：运筹学） 学生姓名： 学号：
float b[m]; /*用于存储常约束条件中的常数*/ float CB[m]; /*用于存储基变量的系数*/
float seta[m]; /*存放出基与入基的变化情况*/ float delta[n]; /*存储检验数矩阵*/ float x[n]; /*存储决策变量*/
int num[m]; /*用于存放出基与进基变量的情况*/ float ZB=0; /*记录目标函数值*/ （2）、定义程序中使用的函数 void input(); void print();
int danchunxing1(); int danchunxing2(int a);
void danchunxing3(int a,int b);
(3)、确定入基变量，对于所有校验数均小于等于0，则当前解为最优解。 int danchunxing1() {
int i,k=0; int flag=0; float max=0; for(i=0;i else {flag=0;break;} if(flag==1) return -1; for(i=0;i { max =delta[i];k=i;} } return k; } (4)、确定出基变量，如果某个大于0的校验数，对应的列向量中所有元素小于等于0，则线性规划问题无解。 int danchunxing2(int a) { int i,k,j; int flag=0; float min; k=a; for(i=0;i else {flag=0;break;} if(flag==1) 6/2/2015 11:31:56 PM 第 3 页 共 11 页 自动化系上机实验报告（课程名称：运筹学） 学生姓名： 学号： {printf(\该线性规划无最优解!\\n\for(i=0;i if(A[i][k]>0) seta[i]=b[i]/A[i][k]; else seta[i]=M; } min=M; for(i=0;i if(min>=seta[i]) {min=seta[i];j=i;} } num[j]=k+1; CB[j]=C[k]; return j; } (5)、迭代运算，计算新的单纯形表。 void danchunxing3(int p,int q) { int i,j,c,l; float temp1,temp2,temp3; c=p;/*行号*/ l=q;/*列号*/ temp1=A[c][l]; b[c]=b[c]/temp1; for(j=0;j A[c][j]=A[c][j]/temp1; for(i=0;i if(i!=c) if(A[i][l]!=0) { temp2=A[i][l]; b[i]=b[i]-b[c]*temp2; for(j=0;j A[i][j]=A[i][j]-A[c][j]*temp2; } } temp3=delta[l]; for(i=0;i delta[i]=delta[i]-A[c][i]*temp3; } 6/2/2015 11:31:56 PM 第 4 页 共 11 页 自动化系上机实验报告（课程名称：运筹学） 学生姓名： 学号： (6)、输入函数，输入方程组的系数矩阵、初始基变量的数字代码、方程组右边的值矩阵、目标函数各个变量的系数所构成的系数阵。 void print() { int i,j=0; printf(\for(i=0;i printf(\ for(j=0;j printf(\ printf(\} printf(\printf(\for(i=0;i printf(\ printf(\} void input() { int i,j; /*循环变量*/ int k; printf(\请输入方程组的系数矩阵A(%d行%d列):\\n\for(i=0;i printf(\请输入初始基变量的数字代码num矩阵:\\n\for(i=0;i scanf(\ printf(\请输入方程组右边的值矩阵b:\\n\for(i=0;i printf(\请输入目标函数各个变量的系数所构成的系数阵C:\\n\for(i=0;i k=num[i]-1; CB[i]=C[k]; }} (7)、主函数，调用前面定义的函数。 6/2/2015 11:31:56 PM 第 5 页 共 11 页