运筹学实验-单纯形法上机报告.docx
单纯形法一大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()初始矩阵变换，加入松弛变量和人工变量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)运算过程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.单纯形法(SimplexMethod)（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形式;在约束方程中有 在约束方程中有 在约束方程中有 所有的人工变量,“辽”时，在加上一个松弛变量；“2”时，采用减去一个松弛变量，再加上一个人工变量;“二”时，加上一个人工变量；松弛变量的目标函数系数置为0。（3）对于标准形式的线性规划问题。用单纯形法计算步骤的框图添加松弛变量、人工变 量,列出初始单纯形表所有6j0无界解令 6 k=max 6 j计算非基变量 各列的检验数6j基变量中 有非零的 人工变量/ I无*解I无穷多最优解对所有aik>0计算 i=baik令 1=min iXi为换包变量Hlk为主兀素唯一最优解N/某非基变N一量检验数TZz迭代运算 用非拳变量Kk替换基变量电. 对主元素行（第1行），令baufb；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）,其运算过程同单纯形法。（2）理由：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。三、数据结构及模块设计1 .程序中用到的数据结构：# defineM20最大20个变量# defineN40/40个约束方程# defineMax100oOOO大MdoubleDMN;系数矩阵double目标函数系数doubleCbMJ基向量系数doubleBM;约束常数doubleVaIUeN;检验数intXbMJ基向量doubleX0M;可行解intopMJ/约束方程符号01一"=”、2">intm,r/矩阵行数、列数intbegin_n;初始变量数intIn_BaseX=-l;进基变量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_change();行变换子函数四、详细设计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)读变量数目和约束方程个数m,nfscanf(fp,"%d",&m);fscanf(fp,"%d",&n);)begin_n=n;初始(未经过标准化)变量数置为n,for(i=0;i<m;i+)按行读取约束矩阵，约束方程符号，常数值for(j=0;j<n;j+)读取约束矩阵if(fp!=NULL)fscanf(fp,'%lf<fcDij);elsePrintf("error");if(fp!=NULL)/读约束方程符号fscanf(fp,*'%d",opi);elsePrinIf("error");if(fp!=NULL)/读取常数值fscanf(fp,"%lf,Bi);elsePrintf("error")；)if(fp!=NULL)读取目标函数类型fscanf(fp,"%d"Type);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行“CIClC2C3space(6);printf(',C");space(7);line_V(l);fbr(i=O;i<n;i+)if(Ci=-Max)printf("-M");elsePrintfe%5.11r,Ci);In();第2条直线line-R(15÷n*5);ln();显示第2行“CbXbBXlX2X3printf(',CbXbB");line_V(l);fbr(i=O;i<n;i+)printf("X%-2d,1,i+l);n();第3条直线line_R(I5+n*5);ln();显示第3部分wCblXblBllDllD12D13/“Cb2Xb2B2D21D22D23/44Cb3Xb3B3D31D32D33/，fdr(i=O;i<m;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;j<n;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;i<n;i+)if(Valuei>Max当Value值达到M数量级时，用aM+b表示intk=(int)(ValueiMax);doublel=Valuei-k*Max;if(l>Max2)k+;I-=Max;1if(k=O)printf('r");elseif(k=l)printf(Mm);elsePrinIf("%dM",k);if(l=0)printf(,");elseif(l>0)PrimfC+%-LOlf',1);elseprintf(',%-2.01,l);)elseif(Valuei<-Max2)当ValUe值达到M数量级时，用aM+b表示intk=(int)(ValueiMax);doublel=Valuei-k*Max;if(l<-Max2)k-;l+=Max;)if(k=O)printf('r");elseif(k=-l)printf(-M");elseprinlf(,%dM,k);if(l=0)p11nlf(");elseif(l>0)printf(',+%-1.01F,l);elseif(l<0)printf(,%-2.01f,l);)else/正常显示printf(,r%4.11f',Value11);ln();第5条直线line.R(15+n*5);ln();显示第5行“X(0)=(XI,X2,X3.)”Space(I);Primf("X(O)=C);fbr(i=0;i<n-l;i+)printf(',%.21f',X0i);1printf(',%.U,XOi);printf(,);ln();line_R(15+n*5);第6条直线ln()；*横线*voidline_R(intn)inti;for(i=0;i<n;i+)PrinIf("-")；*竖线*voidline_V(intn)inti;fbr(i=O;i<n;i+)pnntf('T');*KV格,*voidspace(intn)inti;for(i=0;i<n;i+)p11ntf("");*换行*voidln()printf(,n”)；4. VOidiniJChangeo初始矩阵变换，加入松弛变量和人工变量voidinit_change()inti=0,j;intbase_variable(intx);/判断是否为基变量的子函数对">="约束方程，减去松弛变量，目标系数为0for(i=0;i<m;i+)if(opi=2)n+;Cn-l=O;fbr(j=O;j<m;j+)if(j=i)DUll11-i=-i;elseDjn-ll=O;fdr(i=O;i<m;i+)对有“>二"和"="约束方程，加上人工变量，目标系数为Mif(opi=2opi=l)n+÷ManXisUManX_num=n-l;/将人工变量下标存入人工变量表ManX_num+;/人工变量数目加1Xbi=n-1;Cn-1=-Max;人工变量的系数去-MCbi=Cn-l;fbr(j=O;j<m;j+)if(j=i)DUHn-H=I;elseDjln-ll=O;11对有"<="约束方程，加上松弛变量，目标系数为0elsen+÷Xbi=n-1;C(n-1=0;Cbi=Cn-H;fbr(j=O;j<m;j+)if(j=i)Djln-ll=l;elseDjn-11=0;如果是求最小值，则通过将目标函数各变量系数去相反数if(Type=2)for(i=0;in;i+)读取目标函数变量系数Ci=-c11l;)初始可行解fbr(i=O;i<n;i+)if(j=base_variable(i)!=-1)XOi=Bj;elseX0i=0;)/init_change()inibase_variable(inlx)*判断是否为基变量，若是，返回下标，否则返回/*intj；fbr(j=O;j<m;j+)if(x=Xbj)returnj;)return-1;15. voidComPUte_value()计算检验数voidcompute_value()inti,j,k;intbase_variable(intx);/判断是否为基变量的子函数for(i=O:i<n;i+)if(j=base_variable(i)!=-l)/基变量的检验数为OVaIuei=O;else非基变量Xi的检验数为Ci-Cb*Dmidoublesum=O;for(k=0;k<m;k+)sum+=Cbk*Dki;Valuei=Ci-sum;)/compute_value()6. intbesjResult()判断是否得到最优解。intbest_Result()唯,最优1,无穷多最优2,无界3,无可行5,未得到返回4inti;intless=。,more=。,equal=。;/检验数各种情况的数目小于0,大于0,等于0；intOnlyjnore=-I;/当只有一个检验数大于0时，记录进基变量的列数for(i=0;i<n;i+)统计大于0,等于0,小于0个数if(Va!uei<O)less+;elseif(Valuei=O)equal+;elseif(Valuei>O)more+;only_more=i;if(more=0)无检验数大于0若基解中有人工变量不为0,则无可行解for(i=0;i<ManX_num;i+)if(XOManXJistl!=O)return5;非基变量检验数至少一个等于0,得到无穷多最优解fbr(i=O;i<n;i+)if(Valuei!=0&&base_variable(i)!=-1)return2;检验数全部小于0,得到唯一最优解elsereturn1;/检验数只有1个大于0,并且无出基变量，得到无界解elseif(more=1)for(i=0;i<m;i+)是否进基变量所在列的所有D值都小于0if(Dionly-more>0)return4;有一个大于0,不能判断return3;全部小于0,无出基变量，得到无界解1检验数至少有2个大于0,不能判断elsereturn4;)/best_Resu!t()fvoidin_base()；进基选子函数voidout_base();出基选择子函数voidrow_change();行变换子函数7. voidin_baseQ进基选子函数voidin_base()doublemax=0;inti;intmaxIUm=-1;初始最大的检验数下标为-1for(i=0;i<n;i+)冒泡算法，求的最大检验数下标if(Valuei>max)max=Valuci;max_num=i;in_n=i;11In_BaseX=max_num;存到全局变量In_BaseX)/in_base()8. VOidOUt_base()出基选择子函数voidout_base()doubletempiM;inti;intin=In_BaseX;doublemin=Max;intmin_num=-l;/初始最小B/Dij下标为-1for(i=0;i<m;i+)计算B/Dij的值D值为零，Dif(Diin>O)tempril=BiDfiin;elsetempil=Max;1for(i=0;ivm;i+)(冒泡算法，求最小B/Dij下标if(tempi<min)min=tempil;min-num=Xbi;out_m=i;11OUI_BaseX=min_num;存到全局变量OULBaSeX)/out_base()9. VOidrow_change()行变换子函数voidrow_change()intij;doubletemp;Xbout_m=In_BaseX;进基变量进基对出基行变换，包括系数矩阵和B值temp=Dout_min_n;for(j=0y<ny+)Dout_mj=Dout_mjtemp;Bout_m=Bout_m/temp;对其他行变换for(i=0;i<m;i+)/不是出基行，并且其对应进基列值不为0,变换if(i!=out_m&&Diin_n!=0)double倍数for(j=0;j<n;j+)/系数矩阵变换DiUl=DiU-m*Dout-mU;Bi=Bi-m*Bout_m;/B值变换11for(i=0;i<m;i+)更新Cb的值Cbi=CXbi;for(i=0;i<n;i+)更新当前可行解if(j=base_variable)!=-l)/基变量值为对应B值XOi=Bj;else/其他变量值为0X0i=0;)/row_change()五、程序测试及结果1.第1题(1)原题11M港+oXz/SrtO6zf+o"/QobOXk6处。42+51Xz44山X*:/上>0年卜仙，二弼"0KX2,0(2)文件存储"Jliul.txt-记事本文件(F)福(E)侬9)查看(V)帮助（三）320.60.50120000.40.10400000.40600012510(3)读取EnterfilenameIiul.txtCII25.010.0CbXbBIIXlX20Xl12000Ia0.60.50Xl4000BI0.40.10Xl6000Ia0.00.4UalueIB0.00.0X<0>=<0.00,0.0>初始变换CII25.010.00.00.00.0CbXbBIIXlX2X3X4X50X312000IB0.60.51.00.00.00X44000BI0.40.10.01.00.00X56000BI0.00.40.00.01.0UalueII25.010.00.00.00.0X<0)=<0.00,0.00,12000.00,4000.00,6000.0)（5）运算过程Xl进基X4出基C：25.010.00.00.00.0CbXbB：XlX2X3X4×S0X36000：0.00.31.0-1.50.025Xl10000：1.00.30.02.50.00XS6000：0.00.40.00.01.0Ualue：0.03.80.0-62.50.1X<0>=<10000.00,0.00,6000.00,0.006000.0>（6）运算结果X2进基X5出基CI25.010.00.00.00.0CbXbBIXl×2X3X4XS0X3750I0.00.01.0-1.5-0.925Xl6250I1.00.00.02.5-0.610X215000I0.01.00.00.02.5UalueI0.00.00.0-62.E；-9.4×<0>-<6250.00.15000.,00,7519.00,.0.00,0.0>得到唯一最优解！maxZ"306250.00(1)原题yruv)c)="4。I+92+4。/§七3。J4%升2%+O+Qls%gSt4%+29G十42%Caao<l÷欠2+3小2WSX/£Xi工炉XBCCI欠WX>KOC/(2)文件存储二Iiu2.txt-记事本文件(F)g(E)格式(O)4(V)帮助（三）44210600621010002130400100010001002000010500000100160204030(3)读取EnterFHeliu2.t×tnameC!60.020.040.030.0CbXbBXlX2X3X4Xl600IZlCI-t2.01.02.0Xl1000Iz*caOUNU1.02.0Xl400oOca4O1.U3.02.0Xl100S1.0(3.U0.00.0Xl200S0.01.U0.00.0Xl50IGlQI0.0UU1.00.0Xl1000.0w-w0.01.0Ualue!0.00.00.00.0X<0>=<0.00,0.00,0.00,0.0>初始变换CBI60.020.040.030.00.00.00.00.00.00.00.0CbXbBIiXl×2X3×4XS×6X7X8X9×10Xll0X5600a4.02.01.02.01.00.00.00.00.00.00.00X61000a6.02.01.02.00.01.00.00.00.00.00.00X?400aB2.01.03.02.00.00.01.00.00.00.00.00×8100J1.00.00.00.00.00.00.01.00.00.00.00X9200aB0.01.00.00.00.00.00.00.01.00.00.00X1050Ia0.00.01.00.00.00.00.00.00.01.00.00Xll100a0.00.00.01.00.00.00.00.00.00.01.0UalueII60.020.040.030.00.00.00.00.00.00.00.0X<0>=<0.00,0.0(L0.0CL0.0EL600.,00,1000.00,.400.00,100.00,200)0,50.00,100.0>II（5）运算过程Xl进基X8出基C:60.020.040.030.00.00.00.00.00.00.00.0CbXbB!XlX2X3X4X5X6X7X8X9X10Xll0X5200!0.02.01.02.01.00.00.0-4.00.00.00.00×6400!0.02.01.02.00.01.00.0-6.00.00.00.00X7200!0.01.03.02.00.00.01.0-2.00.00.00.060Xl100I1.00.00.00.00.00.00.01.00.00.00.00X9200I0.01.00.00.00.00.00.00.01.00.00.00X1050J0.00.01.00.00.00.00.00.00.01.00.00Xll100：0.00.00.01.00.00.00.00.00.00.01.0Ualue!0.020.040.030.00.00.00.0-60.00.00.00.0X<0>=<00.00,0.00,0.00,0.00,200.00,400.00,200.00,0.00,200.00,50.00,100.0X3进基X10出基C!60.020.040.030.00.00.00.00.00.00.00.0CbXbB：XlX2X3X4X5X6X7X8X9X10×110X5150!0.02.00.02.01.00.00.0-4.00.0-1.00.00X6350!0.02.00.02.00.01.00.0-6.00.0-1.00.00X750：0.01.00.02.00.00.01.0-2.00.0-3.00.060Xl100!1.00.00.00.00.00.00.01.00.00.00.00X9200：0.01.00.00.00.00.00.00.01.00.00.040X350!0.00.01.00.00.00.00.00.00.01.00.00Xll100I0.00.00.01.00.00.00.00.00.00.01.0Ualue!0.020.00.030.00.00.00.0-60.00.0-40.00.0X<0><100.00,0.00,50.00,0.00,150.00,350.00,50.00,0.00,200.00,0.00,100.0>X4进基X7出基C!60.020.040.030.00.00.00.00.00.00.00.0CbXbB!XlX2X3X4X5X6X7X8X9X10Xll0X5100!0.01.00.00.01.00.0-1.0-2.00.02.00.00X6300:0.01.00.00.00.01.0-1.0-4.00.02.00.030X425S0.00.50.01.00.00.00.5-1.00.0-1.50.060Xl100：1.00.00.00.00.00.00.01.00.00.00.0X9200:0.01.00.00.00.00.00.00.01.00.00.040X350!0.00.01.00.00.00.00.00.00.01.00.0WXll75:0.0-0.50.00.00.00.0-0.51.00.01.51.0Ualue：0.05.00.00.00.00.015.0-30.00.05.00.0X<0>=<100.00,0.00,5(L0025.00,.100.00,300.00,0.00,0.00,200.0E1,0.00,75.0>X2进基X4出基C!60.020.040.030.00.00.00.00.00.00.00.0CbXbB!XlX2X3X4X5X6X7X8X9X10Xll0X550!0.00.00.0-2.01.00.0-2.00.00.05.00.00X6250!0.00.00.0-2.00.01.0-2.0-2.00.05.00.020X250:0.01.00.02.00.00.01.0-2.00.0-3.00.060Xl100!1.00.00.00.00.00.00.01.00.00.00.00X9150：0.00.00.0-2.00.00.0-1.02.01.03.00.040X350S0.00.01.00.00.00.00.00.00.01.00.00Xll100!0.00.00.01.00.00.00.00.00.00.01.0Ualue:0.00.00.0-10.00.00.0-20.,0-20.0e1.020.00.0X<0>三<100.00,50.00,5闻.00,0.00,.50.00j.250.130,0.00,0.,00,150.00,0.00,100.0>（6）运算结果X10进基X5出基C：60.020.040
