simplex.cs

线性规划中的单纯形法

                    value = -1.0;
                }
                else
                {
                    value = double.Parse(temp);
                }
                constraints[i - 1, index2 - 1] = value;
            }
        }
        //基向量初始值
        for (int i = 0; i < pivotVar.GetLength(0); i++)
        {
            pivotVar[i] = -1;
        }
    }
    //进行单纯形法计算,返回值-1表示有唯一最优解，-2表示有无穷多最优解，－3表示没有最优解
    public int Go()
    {
        InitialPivotVar();
        int i;
        do
        {
            i = ExchangePivotColumn();
        } while (i != -1 && i != -2 && i != -3);
        return i;
    }
    //以数组中(i,j)元素为基础将j列变成基向量
    private void CreatePivotColumn(int i, int j)
    {
        double temp = constraints[i, j];
        //第i行的第j个元素化为1            
        for (int m = 0; m < constraints.GetLength(1); m++)
        {
            constraints[i, m] /= temp;
        }
        //将其他行的第j个元素化为0
        for (int n = 0; n < constraints.GetLength(0); n++)
        {
            if (n != i && Math.Abs(constraints[n, j] - 0.0) > 0.000001)
            {
                temp = constraints[n, j];
                for (int k = 0; k < constraints.GetLength(1); k++)
                {
                    constraints[n, k] -= (constraints[i, k] * temp);
                }
            }
        }
    }
    //初始时找出基变量
    private void InitialPivotVar()
    {
        //初始时从最后一个变量往第一个变量寻找基变量，确定基变量
        for (int i = constraints.GetLength(1) - 2; i >= 0; i--)
        {
            int index = isPivotColumn(i);
            if (index != -1 && pivotVar[index] == -1)
            {
                pivotVar[index] = i;
            }
        }
    }
    //判断第j列是否是基向量，若是返回唯一的1所在的行i，否则返回-1
    private int isPivotColumn(int j)
    {
        int row = -1;
        for (int i = 0; i < constraints.GetLength(0); i++)
        {
            if (constraints[i, j] > 0.00001)
            {
                if (row == -1)
                {
                    row = i;
                }
                else
                {
                    return -1;
                }
            }
        }
        if (row != -1)
        {
            double temp = constraints[row, j];
            for (int k = 0; k < constraints.GetLength(1); k++)
            {
                constraints[row, k] /= temp;
            }
        }
        return row;
    }
    //计算delta，判断替换的基向量和最优解情况，返回替换基向量的列标j,若无最优解返回-1
    private int Delta()
    {
        int column = -1;
        double dlt = 0.0;
        for (int i = 0; i < pivotVar.GetLength(0); i++)
        {
            dlt += c[pivotVar[i]] * constraints[i, 0];
        }
        dlt = c[0] - dlt;
        column = 0;
        //找出最大的delta
        for (int j = 1; j < constraints.GetLength(1) - 1; j++)
        {
            double sum = 0.0;
            for (int i = 0; i < pivotVar.GetLength(0); i++)
            {
                sum += c[pivotVar[i]] * constraints[i, j];
            }
            sum = c[j] - sum;
            if (sum > dlt)
            {
                dlt = sum;
                column = j;
            }
        }
        if (dlt > 0)
        {
            for (int j = 0; j < pivotVar.GetLength(0); j++)
            {
                if (constraints[j, column] > 0.0)
                {
                    //第column列有大于0的元素
                    return column;
                }
            }
            //第column列无大于0的元素,原问题无解
            return -2;
        }
        else
        {
            //无大于0的delta,已求得最优解
            return -1;
        }
    }
    //根据返回的delta值，做基向量替换
    private int ExchangePivotColumn()
    {
        int j = Delta();
        int row = -1;
        //若所有delta均小于等于0，则已得到最优解
        if (j == -1)
        {
            optimalResult = 0.0;
            for (int i = 0; i < pivotVar.GetLength(0); i++)
            {
                optimalResult += c[pivotVar[i]] * constraints[i, constraints.GetLength(1) - 1];
            }
            optimalResult += cst;
            if (isMin == true)
            {
                optimalResult = -optimalResult;
            }
            //判断所有非基变量的delta是否都小于0，若是，则有唯一最优解
            //若非基变量的delta有0，则有无穷多最优解
            for (int i = 0; i < constraints.GetLength(1) - 1; i++)
            {
                bool isNonPivotVar = true;
                for (int k = 0; k < pivotVar.GetLength(0); k++)
                {
                    if (pivotVar[k] == i)
                    {
                        isNonPivotVar = false;
                        break;
                    }
                }
                if (isNonPivotVar == true)
                {
                    double dlt = 0.0;
                    for (int m = 0; m < pivotVar.GetLength(0); m++)
                    {
                        dlt += c[pivotVar[m]] * constraints[m, i];
                    }
                    dlt = c[i] - dlt;
                    if (Math.Abs(dlt - 0.0) < 0.00001)
                    {
                        //有无穷多最优解
                        return -2;
                    }
                }
            }
            //有唯一最优解
            return -1;
        }
        else if (j == -2)
        {
            //无最优解
            return -3;
        }
        else
        {
            double min = 0.0;
            if (constraints[0, j] > 0.0)
            {
                min = constraints[0, constraints.GetLength(1) - 1] / constraints[0, j];
                row = 0;
            }
            for (int i = 1; i < constraints.GetLength(0); i++)
            {
                if (constraints[i, j] > 0.0)
                {
                    double temp = constraints[i, constraints.GetLength(1) - 1] / constraints[i, j];
                    if (min - 0.0 < 0.00001)
                    {
                        min = temp;
                    }
                    else if (temp < min)
                    {
                        min = temp;
                        row = i;
                    }
                }
            }
            //如果theta都小于0，则已得到最优解
            if (row == -1)
            {
                optimalResult = 0.0;
                for (int i = 0; i < pivotVar.GetLength(0); i++)
                {
                    optimalResult += c[pivotVar[i]] * constraints[i, constraints.GetLength(1) - 1];
                }
                optimalResult += cst;
                if (isMin == true)
                {
                    optimalResult = -optimalResult;
                }
                return -1;
            }
            CreatePivotColumn(row, j);
            pivotVar[row] = j;
            return j;
        }
    }
    //确定原始输入变量中有多少基变量
    private List<int> InitialPivotVarRows(string[] splitQuestion)
    {
        List<int> pVarRows = new List<int>();
        for (int i = 1; i < splitQuestion.GetLength(0); i++)
        {
            bool isPivotRow = false;
            string constraint = splitQuestion[i];
            for (int j = 0; j < constraint.Length; j++)
            {
                if (constraint[j] == 'x')
                {
                    isPivotRow = true;
                    string search = constraint[j].ToString() + constraint[j + 1].ToString();
                    for (int k = 1; k < splitQuestion.GetLength(0); k++)
                    {
                        if (k != i)
                        {
                            if (splitQuestion[k].Contains(search))
                            {
                                isPivotRow = false;
                                break;
                            }
                        }
                    }
                }
                if (isPivotRow)
                {
                    pVarRows.Add(i);
                    break;
                }
            }
        }
        for (int i = 1; i < splitQuestion.GetLength(0); i++)
        {
            string constraint = splitQuestion[i];
            if (constraint.Contains("<") && !pVarRows.Contains(i))
            {
                pVarRows.Add(i);
            }
        }
        return pVarRows;
    }
}