simplex.cs

线性规划中的单纯形法

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

//contact to me,[e-mail],QQ:445194766
//线性规划中的单纯形法
class Simplex
{
    //目标函数中的价值系数
    private double[] c;
    //约束方程的增广系数矩阵
    private double[,] constraints;
    //基变量
    private int[] pivotVar;
    //最优解;
    private double optimalResult;
    //是否是求最小值
    private bool isMin = false;
    //初始x的个数
    private int xNum = 0;
    //目标函数中的常数项
    private double cst = 0.0;
    //属性
    public int[] PivotVar
    {
        get
        {
            return pivotVar;
        }
    }
    public double[] PivotVarValue
    {
        get
        {
            double[] value = new double[pivotVar.GetLength(0)];
            for (int i = 0; i < pivotVar.GetLength(0); i++)
            {
                value[i] = constraints[i, constraints.GetLength(1) - 1];
            }
            return value;
        }
    }
    public double OptimalResult
    {
        get
        {
            return Math.Round(optimalResult, 5);
        }
    }
    public double[] X
    {
        get
        {
            double[] x = new double[xNum];
            for (int i = 0; i < PivotVar.GetLength(0); i++)
            {
                int index = PivotVar[i];
                if (index < xNum)
                {
                    x[index] = Math.Round(PivotVarValue[i], 5);
                }
            }
            return x;
        }
    }
    //初始化
    public Simplex(string question)
    {
        question = question.ToLower();
        question = question.Replace(" ", "");
        string[] splitQuestion;
        int maxX = 1;
        int nonEqualNum = 0;
        List<int> lessEqualRows = new List<int>();
        for (int i = 0; i < question.Length; i++)
        {
            if (question[i] == 'x' || question[i] == 'X')
            {
                int outResult;
                if (Int32.TryParse(question[i - 1].ToString(), out outResult) == true || question[i - 1] == '+' || question[i - 1] == '-')
                {
                    int temp = Int32.Parse((question[i + 1]).ToString());
                    if (temp > maxX)
                    {
                        maxX = temp;
                    }
                }
            }
            else if (question[i] == '<' || question[i] == '>')
            {
                nonEqualNum++;
            }
        }
        splitQuestion = question.Split(new char[] { ';' });
        #region 若是求最小值，则将求最小值问题转化为求最大值问题
        if (splitQuestion[0].Substring(0, 3) == "min")
        {
            isMin = true;
            string temp = "max-" + splitQuestion[0][3] + '=';
            if (splitQuestion[0][5] != '-')
            {
                temp += '-';
            }
            for (int i = 5; i < splitQuestion[0].Length; i++)
            {
                if (splitQuestion[0][i] == '+')
                {
                    temp += '-';
                }
                else if (splitQuestion[0][i] == '-')
                {
                    temp += '+';
                }
                else
                {
                    temp += splitQuestion[0][i];
                }
            }
            splitQuestion[0] = temp;
        }
        #endregion
        #region 若等号右边为负数，则改变不等号符号,+、－符号互换
        for (int i = 1; i < splitQuestion.GetLength(0); i++)
        {
            string constraint = splitQuestion[i];
            int index = constraint.IndexOf('=');
            if (constraint[index + 1] == '-')
            {
                string temp1 = "";
                string temp2 = "";
                string temp3 = "";
                string temp4 = "";
                string[] splitConstraint = constraint.Split(new char[] { '+' }, StringSplitOptions.RemoveEmptyEntries);
                for (int j = 0; j < splitConstraint.GetLength(0); j++)
                {
                    splitConstraint[j] = splitConstraint[j].Replace('-', '+');
                    if (j != splitConstraint.GetLength(0) - 1)
                    {
                        temp1 = splitConstraint[j] + '-';
                    }
                    else
                    {
                        temp1 = splitConstraint[j];
                    }
                    temp2 += temp1;
                }
                //若第一个字符为+,将其除去，否则加上-
                if (temp2[0] == '+')
                {
                    temp2 = temp2.Substring(1);
                }
                else
                {
                    temp2 = '-' + temp2;
                }
                //=后第一个字符为+,将其去除
                index = temp2.IndexOf('=');
                temp3 = temp2.Remove(index + 1);
                temp4 = temp2.Substring(index + 2);
                temp2 = temp3 + temp4;

                if (temp2.IndexOf('>') != -1)
                {
                    temp2 = temp2.Replace('>', '<');
                }
                else if (temp2.IndexOf('<') != -1)
                {
                    temp2 = temp2.Replace('<', '>');
                }
                constraint = temp2;
                splitQuestion[i] = constraint;
            }
        }
        #endregion
        int rows = splitQuestion.GetLength(0) - 1;
        int columns = maxX + nonEqualNum;
        xNum = maxX;
        List<int> pivotVarRows = new List<int>();
        pivotVarRows = InitialPivotVarRows(splitQuestion);
        //若没有初始基变量，引入一个负的很大的数M=-1.0E10和rows-pivotVarRows.GetLength(0)个人工变量
        int rlt = rows - pivotVarRows.Count;
        if (rlt > 0)
        {
            for (int j = 0; j < rlt; j++)
            {
                columns++;
                splitQuestion[0] += ("+Mx" + columns);
                for (int k = 1; k < splitQuestion.GetLength(0); k++)
                {
                    if (!pivotVarRows.Contains(k))
                    {
                        int index = splitQuestion[k].IndexOf('>');
                        if (index == -1)
                        {
                            index = splitQuestion[k].IndexOf('=');
                        }
                        splitQuestion[k] = splitQuestion[k].Insert(index, "+x" + columns);
                        pivotVarRows.Add(k);
                        break;
                    }
                }
            }
        }

        c = new double[columns];
        constraints = new double[rows, columns + 1];
        pivotVar = new int[rows];
        //从字符串中提取目标函数的价值系数
        string target = splitQuestion[0];
        target = target.Substring(target.IndexOf('=') + 1);
        target = target.Replace("-", "+-");
        string[] splitTarget = target.Split(new char[] { '+' }, StringSplitOptions.RemoveEmptyEntries);
        for (int i = 0; i < splitTarget.GetLength(0); i++)
        {
            if (splitTarget[i].Contains("x"))
            {
                int index = Int32.Parse((splitTarget[i].Substring(splitTarget[i].IndexOf('x') + 1)).ToString());
                double value;
                string temp = splitTarget[i].Substring(0, splitTarget[i].IndexOf('x'));
                if (temp == "")
                {
                    value = 1.0;
                }
                else if (temp == "-")
                {
                    value = -1.0;
                }
                else if (temp == "M")
                {
                    value = -1.0E10;
                }
                else
                {
                    value = double.Parse(temp);
                }
                c[index - 1] = value;
            }
            else
            {
                cst = Convert.ToDouble(splitTarget[i]);
            }
        }
        //从字符串中提取增广矩阵
        int addedVarPos = maxX;
        for (int i = 1; i < splitQuestion.GetLength(0); i++)
        {
            string constraint = splitQuestion[i];
            constraints[i - 1, constraints.GetLength(1) - 1] = double.Parse(constraint.Substring(constraint.IndexOf('=') + 1));
            int index = constraint.IndexOf('<');
            if (index != -1)
            {
                constraints[i - 1, addedVarPos] = 1.0;
                addedVarPos++;
            }
            else if ((index = constraint.IndexOf('>')) != -1)
            {
                constraints[i - 1, addedVarPos] = -1.0;
                addedVarPos++;
            }
            else
            {
                index = constraint.IndexOf('=');
            }
            constraint = constraint.Substring(0, index);
            constraint = constraint.Replace("-", "+-");
            string[] splitConstraint = constraint.Split(new char[] { '+' }, StringSplitOptions.RemoveEmptyEntries);
            for (int j = 0; j < splitConstraint.GetLength(0); j++)
            {
                int index2 = Int32.Parse((splitConstraint[j].Substring(splitConstraint[j].IndexOf('x') + 1)).ToString());
                double value;
                string temp = splitConstraint[j].Substring(0, splitConstraint[j].IndexOf('x'));
                if (temp == "")
                {
                    value = 1.0;
                }
                else if (temp == "-")
                {