单纯形法？写个单纯形法求解器

大家好，今天给各位分享单纯形法的一些知识，其中也会对写个单纯形法求解器进行解释，文章篇幅可能偏长，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在就马上开始吧！

哈哈，我承认我标题党了，这标题有点大，求解器哪是那么容易写的，今天只是突发奇想把单纯形求解方法逻辑实现了一下，求解个三五个方程组的线性规划还可以，大规模的性能上肯定是不行的，所以抱太大希望的大神们看到这就可以回头了，初学者有兴趣可以看看。

说到单纯形法，首先来看看单纯形法的求解步骤，网上有的是，如下：

学过运筹学的这些理论看起来应该都明白，没学过的建议先看看课本。简单举个例子吧

maxz=12x+15yst0.25x+0.5y<=1200.5x+0.5y<=1500.25x<=50x>=0,y>=0

再用目标函数斜率画平行线，比划比划大概就能得出B点是最优解点，那么我们看看用程序怎么求解，首先通过添加松弛变量转换成标准型问题：

min-z=-12x1-15x2st0.25x1+0.5x2+x3=1200.5x1+0.5x2+x4=1500.25x+x5=50x>=0,y>=0

那么用代码怎么描述这个问题呢？我是这么描述的，数组+矩阵

上图里边有个compute方法，没错，这个方法就是计算用的，具体是怎么实现的呢，看下边：

staticvoidCompute(double[]c,double[][]A,double[]b)\n{\nList<double[]>Alist=A.ToList();\nAlist.Add(c);\ndouble[][]Anew=Alist.ToArray();\n\nList<int>xb=newList<int>();//找到基变量存列索引\nfor(inti=0;i<A[0].Length;i++)\n{\nintcount1=0;\nintcount0=0;\nfor(intj=0;j<A.Length;j++)\n{\nif(A[j][i]==0)\n{\ncount0++;\n}\nif(A[j][i]==1)\n{\ncount1++;\n}\n}\nif(count1==1&&count0==A.Length-1)\n{\nxb.Add(i);\n}\n}\nif(xb.Count()!=A.Length)\n{\nConsole.Write("cannotfindbasicvariable;");\nConsole.ReadKey();\nreturn;\n}\nConsole.WriteLine("Printbasicvariable;");\nfor(intj=0;j<A.Length;j++)\n{\nfor(inti=0;i<xb.Count;i++)\n{\nConsole.Write(A[j][xb[i]]+"\\t");\n}\nConsole.WriteLine();\n}\n\nList<double>blist=b.ToList();\nblist.Add(0);//b初始值\n\nSimplexMethod(Alist,xb,blist);\n\n}

我们知道，单纯形法求解最重要的就是画好那张单纯形表，初始表大概是这样的

上边的代码其实也就描述到了这一步，找到了最初的基变量索引列表，同时组装了三个参数，xb就是基变量索引列表的参数，blist就是b列对应的list，Alist就是约束条件加上目标函数的xi矩阵，下边的方法SimplexMethod才是核心迭代过程，具体代码如下

privatestaticvoidSimplexMethod(List<double[]>Alist,List<int>xb,List<double>blist)\n{\ndouble[]juge=Alist.Last();\nif(!juge.All(cc=>cc>=0))\n{\nintcminindex=0;//找到进基变量索引\n\nfor(inti=0;i<juge.Length;i++)\n{\nif(juge[i]<juge[cminindex])\n{\ncminindex=i;\n}\n}\n\n//计算检验数sate\nList<double>sate=newList<double>();\nfor(inti=0;i<Alist.Count-1;i++)\n{\ndoublesatetemp=int.MaxValue;\nif(Alist[i][cminindex]!=0)\n{\nsatetemp=blist[i]/Alist[i][cminindex];\n}\nsate.Add(satetemp);\n}\nConsole.WriteLine("Printredurecost;");\nfor(inti=0;i<sate.Count;i++)\n{\nConsole.Write(sate[i]+"\\t");\n}\nConsole.WriteLine();\n\n//找最小检验数索引\nintsateminindex=0;\nfor(inti=0;i<sate.Count;i++)\n{\nif(sate[i]<sate[sateminindex])\n{\nsateminindex=i;\n}\n}\n\n//确定出基变量记录索引\nintoutbasicindex=xb[sateminindex];\nConsole.WriteLine("Toinbasicvariableindexis:"+cminindex);\nConsole.WriteLine("Tooutbasicvariableindexis:"+outbasicindex);\n\n//进基出基行列式转换\n//将出基变量对应的进基变量系数转换成1\ndouble[]ss=Alist[sateminindex];\ndoubleinNum=ss[cminindex];//进基变量系数\nfor(inti=0;i<ss.Length;i++)\n{\nss[i]=ss[i]/inNum;\n}\nPrint2Array(Alist.ToArray());\nPirnt1Array(blist.ToArray());\nblist[sateminindex]=blist[sateminindex]/inNum;\nPirnt1Array(blist.ToArray());\n\n//处理其他进基变量里不是0的系数\nfor(inti=0;i<Alist.Count;i++)\n{\nif(i!=sateminindex)\n{\ndoubleinotherNum=Alist[i][cminindex];\nif(inotherNum!=0)\n{\ndouble[]sother=Alist[i];\nfor(intj=0;j<sother.Length;j++)//进基变量系数转换成-1\n{\nsother[j]=sother[j]/(0-inotherNum);\nsother[j]=ss[j]+sother[j];\n}\nblist[i]=blist[i]/(0-inotherNum);\nblist[i]=blist[sateminindex]+blist[i];\n\nfor(intk=0;k<xb.Count;k++)\n{\nif(k!=sateminindex&&k!=xb.Count-1)//排除进基变量当前行，排除最后一行（目标行）\n{\ndoubletemp=sother[xb[k]];\nif(temp!=0)\n{\nif(temp!=1)\n{\nfor(intl=0;l<sother.Length;l++)\n{\nsother[l]=sother[l]/temp;\n}\nblist[i]=blist[i]/temp;\n}\n}\n}\n}\n}\n}\n}\nConsole.WriteLine("Afterinbasicvariable;");\nPrint2Array(Alist.ToArray());\nPirnt1Array(blist.ToArray());\nxb[sateminindex]=cminindex;\nPirnt1Array(xb.ToArray());\n\nSimplexMethod(Alist,xb,blist);\n}\nelse\n{\nConsole.WriteLine();\nConsole.WriteLine("基变量索引为：");\nPirnt1Array(xb.ToArray());\nConsole.WriteLine("对应数值为：");\nPirnt1Array(blist.ToArray());\nConsole.Read();\n}\n}

里边的注释基本写得很清楚，首先定义迭代终止条件，就是所有的检验数都大于0的时候，迭代结束。里边的逻辑就是理论里的逻辑，先确定进基变量，然后计算检验数，找最小检验数索引，确定出基变量，然后进行行列式转换（这一步逻辑代码实现的时候还是让我转了半天弯），如果所有的检验数不是都大于0，继续迭代，直到满足条件输出解变量索引及参数值（中间的各种输出是调试时看中间变量用的，仅供参考），最终运行输出的结果如下：

可以看到，最终的基变量是1、0、4，也就是x2、x1、x5，x5是后加的松弛变量，不用考虑，前边x1的值对应120，x2的值对应180。可以回头看看图解法的结果，那个B点的坐标值就是(120,180),说明我们迭代的逻辑是没问题的。有兴趣的可以拿过去改改参数试一下，我改了俩参数，求解是没问题的，但是可别用来求解大规模的线性规划，本人自知没那么强大，还是别玩火啦。

文章到此结束，如果本次分享的单纯形法和写个单纯形法求解器的问题解决了您的问题，那么我们由衷的感到高兴！