Linear programering - Simplex

Hvis du er lidt frisk, så er det jo faktisk ikke særlig svært at lave. Det er jo bare nogle systematiske række-operationer som skal køres igen og igen (rekursivt) indtil der ikke er flere negative koefficienter.

Men prøv:
http://www.lindo.com/dllfeatf.html

Jeg havde noget C++ simplex kode liggende. Her er den konverteret
til C#. De 2 test eksempler returnerer korrekt resultat.

using System;

class MainClass
{
    private static void Simplex(double[,] d, double[] x)
    {
        double[,] dd = new double[d.GetLength(0),d.GetLength(1)];
        int lastrow = d.GetLength(0) - 1;
        int lastcol = d.GetLength(1) - 1;
        for(;;) {
            int q = 0;
            for(int i=0; i<lastcol; i++) if(d[lastrow,i] <= d[lastrow,q]) q=i;
            if(d[lastrow,q] >= 0) break;
            int p = 0;
            while(d[p,lastcol]/d[p,q] <= 0)
            {
                p++;
                if(p>lastrow) throw new Exception("Mo solution");
            }
            for(int j=p; j<lastrow; j++)
                if(d[j,lastcol]/d[j,q] >= 0 &&
                  d[j,lastcol]/d[j,q] <= d[p,lastcol]/d[p,q]) p=j;
            for(int j=0; j<=lastrow; j++)
            {
                for(int i=0; i<=lastcol; i++)
                {
                    if(j!=p)
                        dd[j,i] = d[j,i] - d[p,i]*d[j,q]/d[p,q];
                    else
                        dd[j,i] = d[j,i]/d[p,q];
                }
            }
            d = (double[,])dd.Clone();
        }
        for(int i=0; i<x.Length; i++)
        {
            for(int j=0; j<=lastrow; j++)
            {
                if(d[j,i] != 0 && d[j,i] != 1)
                {
                    x[i] = 0;
                    break;
                }
                if(d[j,i] == 1) x[i] = d[j,lastcol];
            }
        }
    }
    public static void SimplexWrapper(double[,] a, double[] b, double[]c, double[] x)
    {
        if(b.Length != a.GetLength(0)) throw new Exception("Wrong dimension of b");
        if(c.Length != a.GetLength(1)) throw new Exception("Wrong dimension of c");
        if(x.Length != a.GetLength(1)) throw new Exception("Wrong dimension of x");
        double[,] d = new double[a.GetLength(0)+1,a.GetLength(1)+b.Length+2];
        for(int j=0; j<a.GetLength(0); j++)
            for(int i=0; i<a.GetLength(1); i++)
                d[j,i] = a[j,i];
        for(int i=0; i<a.GetLength(1); i++) d[d.GetLength(0)-1,i] = -c[i];
        for(int j=0; j<a.GetLength(0); j++) d[j,d.GetLength(1)-1] = b[j];
        for(int j=0; j<a.GetLength(0)+1; j++)
            for(int i=0; i<a.GetLength(0)+1; i++)
                if(j==i)
                    d[j,a.GetLength(1)+i] = 1;
                else
                    d[j,a.GetLength(1)+i] = 0;
        d[d.GetLength(0)-1,d.GetLength(1)-1] = 0;
        Simplex(d, x);       
    }
    private static void Test1()
    {
        double[,] a = { {2,1}, {0.5,1} };
        double[] b = {2,1};
        double[] c = {1,1};
        double[] x = new double[2];
        SimplexWrapper(a, b, c, x);
        Console.WriteLine(x[0] + " " + x[1]);
    }
    private static void Test2()
    {
        double[,] a = { {3,5}, {1,2}, {2,2} };
        double[] b = {3900,2100,2200};
        double[] c = {700,1000};
        double[] x = new double[2];
        SimplexWrapper(a, b, c, x);
        Console.WriteLine(x[0] + " " + x[1]);
    }
    public static void Main(string[] args)
    {
        Test1();
        Test2();
    }
}

Og det er altså max CX med AX<=B og X>=0 der løses.

arne_V: fornemt