写个单纯形法求解器?

写个单纯形法求解器?哈哈,我承认我标题党了,这标题有点大,求解器哪是那么容易写的,今天只是突发奇想把单纯形求解方法逻辑实现了一下,求解个三五个方程组的线性规划还可以

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

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

写个单纯形法求解器?

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

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 = -12×1 – 15×2
st 0.25×1 + 0.5×2 + x3 = 120
0.5×1 + 0.5×2 + 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) ,说明我们迭代的逻辑是没问题的。有兴趣的可以拿过去改改参数试一下,我改了俩参数,求解是没问题的,但是可别用来求解大规模的线性规划,本人自知没那么强大,还是别玩火啦。

今天的文章写个单纯形法求解器?分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/8018.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注