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

《使用C语言实现单纯形法求解线性规划问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、自动化系上机实验报告（课程名称：运筹学）学生姓名：学号：上机实验报告班级：自动化班专业/方向：自动化姓名：实验成绩(10分制)学号：上机实验名称：使用C语言实现单纯形法求解线性规划问题上机时间：2015年5月20日上机地点：信自234一、实验目的和要求1、目的：l掌握单纯形算法的计算步骤，并能熟练使用该方法求解线性规划问题。l了解算法à程序实现的过程和方法。2、要求：l使用熟悉的编程语言编制单纯形算法的程序。l独立编程，完成实验，撰写实验报告并总结。二、实验内容和结果1、单纯形算法的步骤及程序流程图。（1）、算法步骤（1）将线性规划化为标准形。（2）用最快的方法确定一个初

2、始基本可行解X（0）。当s·t均为“≤”形式时，以松驰变量做初始基本变量最快。（3）求X（0）中非基本变量xj的检验数σj。若，则停止运算，X（0）=X*（表示最优解），否则转下一步。（4）①由确定xk进基；②由确定xl出基，其中alk称为主元素；③利用初等变换将alk化为1，并利用alk将同列中其它元素化为0，得新解X（1）。（5）返回（3），直至求得最优解为止。7/30/20215:56:31上午第11页共11页自动化系上机实验报告（课程名称：运筹学）学生姓名：学号：（2）、程序图找出初始基可行解列出初始单纯形表计算校验数所有δj<=0?对于某个δj>0，是否存在Pj

3、<=0确定为入基变量确定出基变量计算新的单纯形表已得最优解，结束无最优解，结束2、单纯形算法程序的规格说明各段代码功能描述：（1）、定义程序中使用的变量#include#include#definem3/*定义约束条件方程组的个数*/#definen5/*定义未知量的个数*/floatM=1000000.0;floatA[m][n];/*用于记录方程组的数目和系数;*/floatC[n];/*用于存储目标函数中各个变量的系数*/7/30/20215:56:31上午第11页共11页自动化系上机实验报告（课程名称：运筹学）学生姓名：学号：fl

4、oatb[m];/*用于存储常约束条件中的常数*/floatCB[m];/*用于存储基变量的系数*/floatseta[m];/*存放出基与入基的变化情况*/floatdelta[n];/*存储检验数矩阵*/floatx[n];/*存储决策变量*/intnum[m];/*用于存放出基与进基变量的情况*/floatZB=0;/*记录目标函数值*/（2）、定义程序中使用的函数voidinput();voidprint();intdanchunxing1();intdanchunxing2(inta);voiddanchunxing3(inta,intb);(3)、确定入基变量

5、，对于所有校验数均小于等于0，则当前解为最优解。intdanchunxing1(){inti,k=0;intflag=0;floatmax=0;for(i=0;i

6、,j;intflag=0;floatmin;k=a;for(i=0;i0)seta[i]=b[i]/A[i][k];elseseta[i]=M;}min=M;for(i=0;i=seta[i]){

7、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;j