运筹学实验-单纯形法上机报告.docx

《运筹学实验-单纯形法上机报告.docx》由会员分享，可在线阅读，更多相关《运筹学实验-单纯形法上机报告.docx（30页珍藏版）》请在优知文库上搜索。

1、单纯形法一大M法实验报告目录一、实验目的3二、单纯形法及大M法41. 单纯形法(SimplexMethod)4(1) 单纯形法是解线性规划问题的一个重要方法4(2) 用程序进行运算前，要将目标函数及约束方程变成标准形式。4(3) )对于标准形式的线性规划问题。用单纯形法计算步骤的框图4(4) 在程序运算过程中，采用单纯形表显示运算过程。52. 大M法5三、数据结构及模块设计61 .以下是程序中用到的数据结构：62 .模块设计：6四、详细设计71. 文件格式定义72. VOidread()读取约束矩阵、目标函数73. voidPrint()单纯形表显示函数84. VOidiniJehange()

2、初始矩阵变换，加入松弛变量和人工变量115. voidCOmPUte_value()计算检验数136. intbesJResult()判断是否得到最优解，唯一最优1,无穷多最优2,无界3,无可行5,未得到返回4147. voidin_base()进基选子函数158. VoidoUJbaSe()出基选择子函数159. voidrowhange()行变换子函数16五、程序测试及结果171. 第1题17(1) 原题17(2)文件存储17(3) 读取17(4) 初始变换18(5)运算过程18(6)运算结果182. 第2题19(1) 原题19(2)文件存储19(3) 读取19(4) 初始变换20(5)运

3、算过程20(6)运算结果213 .第3题22(1) 原题22(2)文件存储22(3) 读取22(4)初始变换23(5)运算过程23(6)运算结果234 .第2题24(1) 原题24（2）文件存储24（3）读取24（4）初始变换25（5）运算过程25（6）运算结果265 .第2题26（1） 原题26（2）文件存储26（3） 读取27（4）初始变换27（5）运算过程28（6）运算结果28六、工作分配及实验感想291. 工作分配292. 实验感想29一、实验目的使用目前熟悉的语言，实现所学的单纯形法之大M法，并正确运算测试结果。本组成员使用C语言实现。二、单纯形法及大M法1.单纯形法(Simplex

4、Method)（1）单纯形法是解线性规划问题的一个重要方法。其原理的基本框架为：第一步：将LP线性规划变标准型，确定一个初始可行解（顶点）。第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。第三步：从初始基可行解向相邻的基可行解（顶点）转换，且使目标值有所改善一目标函数值增加，重复第二和第三步直到找到最优解。（2）用程序进行运算前，要将目标函数及约束方程变成标准形式。maxz=CXAX=bX0(,b =(016 , C =(2,3,0,0,0) U对于非标准形式须作如下变换:a) b) c) d) e)目标函数为极小值min Z=CX时，转换为max Z=-CX形式;在约束方程中有

5、 在约束方程中有 在约束方程中有 所有的人工变量,“辽”时，在加上一个松弛变量；“2”时，采用减去一个松弛变量，再加上一个人工变量;“二”时，加上一个人工变量；松弛变量的目标函数系数置为0。（3）对于标准形式的线性规划问题。用单纯形法计算步骤的框图添加松弛变量、人工变 量,列出初始单纯形表所有6j0无界解令 6 k=max 6 j计算非基变量 各列的检验数6j基变量中 有非零的 人工变量/ I无*解I无穷多最优解对所有aik0计算 i=baik令 1=min iXi为换包变量Hlk为主兀素唯一最优解N/某非基变N一量检验数TZz迭代运算 用非拳变量Kk替换基变量电. 对主元素行（第1行），令b

6、aufb；aij/akf为 对主元素列（第k列），令IfaI;Of其它兀素 表中其它行列元素令aij1Walkaik-*aijbi-b1alkaik-bi（4）在程序运算过程中，采用单纯形表显示运算过程。Cjf（目标系数）Clm+lCnCb基变量XB右端项bX1+lXnClXibi1%亦+1abnC2IIX2IIb2II1a2,b+12,rI1IIIIICmIXmIt11I1b+1&m,nCj-Zj（检验量纺CAn+1n2.大M法（1）方法：在约束条件中，加入人工变量后，要求目标函数不受影响，目标函数中人工变量的系数取-M（M为系统所能表示范围内的一个非常大的值本程序取100OOo0）,其运算

7、过程同单纯形法。（2）理由：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。三、数据结构及模块设计1 .程序中用到的数据结构：# defineM20最大20个变量# defineN40/40个约束方程# defineMax100oOOO大MdoubleDMN;系数矩阵double目标函数系数doubleCbMJ基向量系数doubleBM;约束常数doubleVaIUeN;检验数intXbMJ基向量doubleX0M;可行解intopMJ/约束方程符号01一=”、2intm,r/矩阵行数、列数intbegin_n;初始变量数intIn_BaseX=-l;进基变

8、量intin_n=-1;进基列标示intout_m=-1;出基行标示intOUt_BaseX=l;出基变量intbest;最优函数返回值Charname30;文件名intManX_num=0;人工变量数目intManXistMW人工变量存放数组2 .模块设计：voidread。;读取方程子函数voidPrint();显示单纯表子函数voidinit_change();初始变换子函数voidComPUIe_value();计算检验数子函数intbest_Result();判断是否得到最优解子函数voidin_base();进基选子函数voidOUJbaSe();出基选择子函数voidrow_ch

9、ange();行变换子函数四、详细设计1. 文件格式定义格式：（行数/约束方程数：列数/变量数：）mn（约束矩阵:符号：0小于，1等于，2大于B值）DllD12D13.DnloplblD21D22D23.Dn2op2b2DmlD2mDm3.DnmOPmbm（最大值/最小值：1最大，2最小）max/min目标函数的变量系数：ClC2C3.Cn例：320.60.50120000.40.10400000.406000125102. Voidreado读取约束矩阵、目标函数voidread()FILE*fp;文件inti=0j=0,k;fp=fopen(name,r);if(fp!=NULL)读变量数

10、目和约束方程个数m,nfscanf(fp,%d,&m);fscanf(fp,%d,&n);)begin_n=n;初始(未经过标准化)变量数置为n,for(i=0;im;i+)按行读取约束矩阵，约束方程符号，常数值for(j=0;jn;j+)读取约束矩阵if(fp!=NULL)fscanf(fp,%lffcDij);elsePrintf(error);if(fp!=NULL)/读约束方程符号fscanf(fp,*%d,opi);elsePrinIf(error);if(fp!=NULL)/读取常数值fscanf(fp,%lf,Bi);elsePrintf(error)；)if(fp!=NULL)

11、读取目标函数类型fscanf(fp,%dType);elsePrintfCerrO，)；for(k=0;kvn;k+)读取目标函数变量系数if(fp!=NULL)fscanf(fp,%l,feCk);elsePrintfCerror);fclose(fp);)/voidread()3. VOidPrinto单纯形表显示函数voidprint()inti=0J=0;voidIine-V(int);/竖线子函数voidline_R(int);横线子函数voidln()W换行子函数voidSPaCe();空格子函数ln();第1条直线line_R(15+n*5);111();显示第1行“CIClC2

12、C3space(6);printf(,C);space(7);line_V(l);fbr(i=O;in;i+)if(Ci=-Max)printf(-M);elsePrintfe%5.11r,Ci);In();第2条直线line-R(15n*5);ln();显示第2行“CbXbBXlX2X3printf(,CbXbB);line_V(l);fbr(i=O;in;i+)printf(X%-2d,1,i+l);n();第3条直线line_R(I5+n*5);ln();显示第3部分wCblXblBllDllD12D13/“Cb2Xb2B2D21D22D23/44Cb3Xb3B3D31D32D33/，fdr(i=O;im;i+)if(Cbil=-Max)printf(-M);elseprintf(,%-5.01,Cbi);printf(,X%-2d,Xbi+l);printf(,%5.01f,Bi);line_V(l);fbr(j=O;jn;j+)printf(%5.11,Drijl);n();第4条直线line_R(15+n*5);ln();显示第4行“ValueValuelValue2Value3.”space(5);printf(,Value);space(4);line_V(l);fbr(i=O;iMax当Value值达到M数量级时，用a