最优求解器（写个单纯形法求解器）
最优求解器（写个单纯形法求解器）上图里边有个compute方法，没错，这个方法就是计算用的，具体是怎么实现的呢，看下边：那么用代码怎么描述这个问题呢？我是这么描述的，数组 矩阵这题用图解法也很容易再用目标函数斜率画平行线，比划比划大概就能得出B点是最优解点，那么我们看看用程序怎么求解，首先通过添加松弛变量转换成标准型问题：min -z = -12x1 - 15x2st 0.25x1 0.5x2 x3 = 1200.5x1 0.5x2 x4 = 1500.25x x5 = 50x>=0 y>=0
哈哈，我承认我标题党了，这标题有点大，求解器哪是那么容易写的，今天只是突发奇想把单纯形求解方法逻辑实现了一下，求解个三五个方程组的线性规划还可以，大规模的性能上肯定是不行的，所以抱太大希望的大神们看到这就可以回头了，初学者有兴趣可以看看。
说到单纯形法，首先来看看单纯形法的求解步骤，网上有的是，如下：
学过运筹学的这些理论看起来应该都明白，没学过的建议先看看课本。简单举个例子吧
max z = 12x 15y
st 0.25x 0.5y <= 120
0.5x 0.5y <= 150
0.25x <= 50
x>=0 y>=0
这题用图解法也很容易
再用目标函数斜率画平行线，比划比划大概就能得出B点是最优解点，那么我们看看用程序怎么求解，首先通过添加松弛变量转换成标准型问题：
min -z = -12x1 - 15x2
st 0.25x1 0.5x2 x3 = 120
0.5x1 0.5x2 x4 = 150
0.25x x5 = 50
x>=0 y>=0
那么用代码怎么描述这个问题呢？我是这么描述的，数组 矩阵
上图里边有个compute方法，没错，这个方法就是计算用的，具体是怎么实现的呢，看下边：
static void Compute(double[] c double[][] A double[] b)
{
List<double[]> Alist = A.ToList();
Alist.Add(c);
double[][] Anew = Alist.ToArray();
List<int> xb = new List<int>(); //找到基变量 存列索引
for (int i = 0; i < A[0].Length; i )
{
int count1 = 0;
int count0 = 0;
for (int j = 0; j < A.Length; j )
{
if (A[j][i] == 0)
{
count0 ;
}
if (A[j][i] == 1)
{
count1 ;
}
}
if (count1 == 1 && count0 == A.Length - 1)
{
xb.Add(i);
}
}
if (xb.Count() != A.Length)
{
Console.Write("can not find basic variable;");
Console.ReadKey();
return;
}
Console.WriteLine("Print basic variable;");
for (int j = 0; j < A.Length; j )
{
for (int i = 0; i < xb.Count; i )
{
Console.Write(A[j][xb[i]] "\t");
}
Console.WriteLine();
}
List<double> blist = b.ToList();
blist.Add(0); //b初始值
SimplexMethod(Alist xb blist);
}
我们知道，单纯形法求解最重要的就是画好那张单纯形表，初始表大概是这样的
上边的代码其实也就描述到了这一步，找到了最初的基变量索引列表，同时组装了三个参数，xb就是基变量索引列表的参数，blist就是b列对应的list，Alist就是约束条件加上目标函数的xi矩阵，下边的方法SimplexMethod才是核心迭代过程，具体代码如下
private static void SimplexMethod(List<double[]> Alist List<int> xb List<double> blist)
{
double[] juge = Alist.Last();
if (!juge.All(cc => cc >= 0))
{
int cminindex = 0; //找到进基变量索引
for (int i = 0; i < juge.Length; i )
{
if (juge[i] < juge[cminindex])
{
cminindex = i;
}
}
//计算检验数 sate
List<double> sate = new List<double>();
for (int i = 0; i < Alist.Count - 1; i )
{
double satetemp = int.MaxValue;
if (Alist[i][cminindex] != 0)
{
satetemp = blist[i] / Alist[i][cminindex];
}
sate.Add(satetemp);
}
Console.WriteLine("Print redure cost;");
for (int i = 0; i < sate.Count; i )
{
Console.Write(sate[i] "\t");
}
Console.WriteLine();
//找最小检验数索引
int sateminindex = 0;
for (int i = 0; i < sate.Count; i )
{
if (sate[i] < sate[sateminindex])
{
sateminindex = i;
}
}
//确定出基变量 记录索引
int outbasicindex = xb[sateminindex];
Console.WriteLine("To in basic variable index is:" cminindex);
Console.WriteLine("To out basic variable index is:" outbasicindex);
//进基 出基 行列式转换
//将出基变量对应的 进基变量系数转换成1
double[] ss = Alist[sateminindex];
double inNum = ss[cminindex];//进基变量系数
for (int i = 0; i < ss.Length; i )
{
ss[i] = ss[i] / inNum;
}
Print2Array(Alist.ToArray());
Pirnt1Array(blist.ToArray());
blist[sateminindex] = blist[sateminindex] / inNum;
Pirnt1Array(blist.ToArray());
//处理其他进基变量里不是0的系数
for (int i = 0; i < Alist.Count; i )
{
if (i != sateminindex)
{
double inotherNum = Alist[i][cminindex];
if (inotherNum != 0)
{
double[] sother = Alist[i];
for (int j = 0; j < sother.Length; j )//进基变量系数 转换成-1
{
sother[j] = sother[j] / (0 - inotherNum);
sother[j] = ss[j] sother[j];
}
blist[i] = blist[i] / (0 - inotherNum);
blist[i] = blist[sateminindex] blist[i];
for (int k = 0; k < xb.Count; k )
{
if (k != sateminindex && k != xb.Count - 1)//排除进基变量当前行，排除最后一行（目标行）
{
double temp = sother[xb[k]];
if (temp != 0)
{
if (temp != 1)
{
for (int l = 0; l < sother.Length; l )
{
sother[l] = sother[l] / temp;
}
blist[i] = blist[i] / temp;
}
}
}
}
}
}
}
Console.WriteLine("After in basic variable;");
Print2Array(Alist.ToArray());
Pirnt1Array(blist.ToArray());
xb[sateminindex] = cminindex;
Pirnt1Array(xb.ToArray());
SimplexMethod(Alist xb blist);
}
else
{
Console.WriteLine();
Console.WriteLine("基变量索引为：");
Pirnt1Array(xb.ToArray());
Console.WriteLine("对应数值为：");
Pirnt1Array(blist.ToArray());
Console.Read();
}
}
里边的注释基本写得很清楚，首先定义迭代终止条件，就是所有的检验数都大于0的时候，迭代结束。里边的逻辑就是理论里的逻辑，先确定进基变量，然后计算检验数，找最小检验数索引，确定出基变量，然后进行行列式转换（这一步逻辑代码实现的时候还是让我转了半天弯），如果所有的检验数不是都大于0，继续迭代，直到满足条件输出解变量索引及参数值（中间的各种输出是调试时看中间变量用的，仅供参考），最终运行输出的结果如下：
可以看到，最终的基变量是1、0、4，也就是x2、x1、x5，x5是后加的松弛变量，不用考虑，前边x1的值对应120，x2的值对应180。可以回头看看图解法的结果，那个B点的坐标值就是(120 180) 说明我们迭代的逻辑是没问题的。有兴趣的可以拿过去改改参数试一下，我改了俩参数，求解是没问题的，但是可别用来求解大规模的线性规划，本人自知没那么强大，还是别玩火啦。
