OptimizeMethods

#include <stdio.h>
#include <conio.h>
#include <Windows.h>

#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

void RaiseError(std::string const &_sError)
{
    std::wstring sWError(_sError.begin(), _sError.end());
    MessageBox(nullptr, sWError.c_str(), L"Error", MB_OK);
}

void RaiseError(std::wstring const &_sWError)
{
    MessageBox(nullptr, _sWError.c_str(), L"Error", MB_OK);
}

#define RAISE_ERROR(str) \
    RaiseError(str); \
    _getch(); \
    return 0;

void ToLower(std::string &s)
{
    for (char &c : s)
    {
        c = std::tolower(c);
    }
}

enum class eSolutionState
{
    INITIALIZED = 0,
    FIRSTSTEP,
    SECONDSTEP,
    FINISHED,
    FAILED
} g_eSolutionState(eSolutionState::INITIALIZED);

class CSimplexTable
{
public:
    // заголовки строк и столбцов
    std::vector<size_t> m_RowHeaders; // доп. переменные(базисные)
    std::vector<size_t> m_ColumnHeaders; // исходные переменные(небазисные)

    // данные(целевая функция в первой строке, свободные члены в первом столбце)
    std::vector<std::vector<float>> m_Table;

    bool m_bIsMin;
};

CSimplexTable g_STable;

void PrintTable()
{
    printf("\t%s\t", "Free");

    for (size_t i = 0; i < g_STable.m_ColumnHeaders.size(); i++)
    {
        printf("x%d\t", g_STable.m_ColumnHeaders[i] + 1);
    }

    printf("\n %s\t", "F");

    for (size_t i = 0; i < g_STable.m_ColumnHeaders.size() + 1; i++)
    {
        printf("%0.3f\t", g_STable.m_Table[0][i]);
    }

    for (size_t i = 0; i < g_STable.m_RowHeaders.size(); i++)
    {
        printf("\n X%d \t", g_STable.m_RowHeaders[i] + 1);

        for (size_t j = 0; j < g_STable.m_ColumnHeaders.size() + 1; j++)
        {
            printf("%0.3f\t", g_STable.m_Table[i + 1][j]);
        }
    }

    printf("\n\n");
}

bool ParseInputToTable(std::string const &_sFunc, std::string const _Equations[], size_t _nEquationCount)
{
    // ошибка всплывает только при парсинге(коряво написанные функция или уравнения)

    auto _ParseConstAndVar = [](std::string &_sDest, float &fConst, char &cVar, size_t &nVar)
    {
        sscanf(_sDest.c_str(), "%f%c%d", &fConst, &cVar, &nVar);

        // стираем строчку
        char sFind[20];
        int nFindLen = sprintf_s(sFind, 20, "%c%d", cVar, nVar);
        _sDest.erase(_sDest.begin(), _sDest.begin() + _sDest.find(sFind) + nFindLen);
    };

    // место для целевой функции
    g_STable.m_Table.push_back(std::vector<float>());

    size_t nMaxVarNumber = 0;

    // парсим уравнения:
    for (size_t iEq = 0; iEq < _nEquationCount; iEq++)
    {
        std::string sEq = _Equations[iEq];

        ToLower(sEq);

        if (sEq.size() < 3)
            return false;

        // 2. нужно убрать конец(знак отношения и число)
        size_t found = sEq.find_first_of("<>=");

        if (found == sEq.npos)
            return false;

        char sOperator[20];
        float fFreeConst;

        bool bNegate = false;

        if (sscanf((sEq.substr(found, sEq.size() - found)).c_str(), "%s %f", sOperator, &fFreeConst) < 2)
            return false;

        sEq.erase(sEq.begin() + found, sEq.end());

        // если оператор >= или >, то меняем знаки
        if (std::string(sOperator).find_first_of(">") != std::string(sOperator).npos)
        {
            bNegate = true;

            fFreeConst = -fFreeConst;
        }

        sEq.erase(std::remove_if(sEq.begin(), sEq.end(),
            [](char c) { return (c =='\r' || c =='\t' || c == ' ' || c == '*' || c == '\n'); }), sEq.end());

        g_STable.m_Table.push_back(std::vector<float>());
        g_STable.m_Table.back().push_back(fFreeConst);

        while (!sEq.empty())
        {
            float fConst;
            char cVar;
            size_t nVar;

            _ParseConstAndVar(sEq, fConst, cVar, nVar);

            if (nMaxVarNumber < nVar)
                nMaxVarNumber = nVar;

            if (bNegate)
                fConst = -fConst;

            // добавляем нолики, если пропущены переменные(x1...x3, добавим x2)
            for (int i = (int)g_STable.m_Table.back().size() - 1; i < (int)nVar - 2; i++)
                g_STable.m_Table.back().push_back(0.0f);

            g_STable.m_Table.back().push_back(fConst);
        }
    }

    // ------------------------------------------------------------------------------------------------

    {
        // парсим функцию:
        std::string sModifiedFunc = _sFunc;
        ToLower(sModifiedFunc);

        // 1. убираем все пробелы и всякие знаки сброса каретки и т.д. + знак умножения
        sModifiedFunc.erase(std::remove_if(sModifiedFunc.begin(), sModifiedFunc.end(),
            //[](char c) { return (!isdigit(c) && !isalpha(c) && c != '+' && c != '-' && c != '>'); }), sModifiedFunc.end());
            [](char c) { return (c =='\r' || c =='\t' || c == ' ' || c == '*' || c == '\n'); }), sModifiedFunc.end());

        if (sModifiedFunc.size() < 3)
            return false;

        // 2. определяем какая функция: минимум или максимум
        std::string sMinOrMax = sModifiedFunc.substr(sModifiedFunc.size() - 3, 3);
        if (sMinOrMax == "min")
            g_STable.m_bIsMin = true;
        else if (sMinOrMax == "max")
            g_STable.m_bIsMin = false;
        else
            return false;

        size_t nPos = sModifiedFunc.find("->");
        if (nPos == sModifiedFunc.npos)
            return false;

        sModifiedFunc.erase(sModifiedFunc.begin() + nPos, sModifiedFunc.end());

        // 3. парсим все иксы и константы к ним

        g_STable.m_Table[0].push_back(0.0f);

        while (!sModifiedFunc.empty())
        {
            float fConst;
            char cVar;
            size_t nVar;

            _ParseConstAndVar(sModifiedFunc, fConst, cVar, nVar);

            if (!g_STable.m_bIsMin)
            {
                // по идее надо...
                fConst = -fConst;
            }

            // добавляем нолики, если пропущены переменные(x1...x3, добавим x2)
            for (int i = (int)g_STable.m_Table[0].size() - 1; i < (int)nVar - 2; i++)
                g_STable.m_Table[0].push_back(0.0f);

            // и добавляем новую
            g_STable.m_Table[0].push_back(fConst);
        }
    }

    // добавляем недостающие коэффициенты
    for (auto &iVector : g_STable.m_Table)
    {
        while (iVector.size() <= nMaxVarNumber)
        {
            iVector.push_back(0.0f);
        }
    }

    // теперь заполняем заголовки(по дефолту)
    for (size_t i = 0; i < nMaxVarNumber; i++)
        g_STable.m_ColumnHeaders.push_back(i);

    for (size_t i = 0; i < _nEquationCount; i++)
        g_STable.m_RowHeaders.push_back(nMaxVarNumber + i);

    // выведем результат парсинга и первичной подготовки:
    PrintTable();

    g_eSolutionState = eSolutionState::INITIALIZED;

    return true;
}

void RecomputeTable(size_t iLeadingRow, size_t iLeadingCol)
{
    // меняем местами
    int nTemp = g_STable.m_RowHeaders[iLeadingRow - 1];
    g_STable.m_RowHeaders[iLeadingRow - 1] = g_STable.m_ColumnHeaders[iLeadingCol - 1];
    g_STable.m_ColumnHeaders[iLeadingCol - 1] = nTemp;

    // и преобразуем таблицу
    std::vector<float> CopyLeadingRow(g_STable.m_ColumnHeaders.size() + 1);
    std::vector<float> CopyLeadingCol(g_STable.m_RowHeaders.size() + 1);

    float fLeadingValue = 1 / g_STable.m_Table[iLeadingRow][iLeadingCol];

    // проход по столбцу
    for (size_t i = 0; i < g_STable.m_RowHeaders.size() + 1; i++)
    {
        CopyLeadingCol[i] = g_STable.m_Table[i][iLeadingCol];

        if (i == iLeadingRow)
            continue;

        g_STable.m_Table[i][iLeadingCol] *= -fLeadingValue;
    }

    // проход по строке
    for (size_t i = 0; i < g_STable.m_ColumnHeaders.size() + 1; i++)
    {
        CopyLeadingRow[i] = g_STable.m_Table[iLeadingRow][i];

        if (i == iLeadingCol)
            continue;

        g_STable.m_Table[iLeadingRow][i] *= fLeadingValue;
    }

    g_STable.m_Table[iLeadingRow][iLeadingCol] = 1 / g_STable.m_Table[iLeadingRow][iLeadingCol];

    // проход по строкам
    for (size_t i = 0; i < g_STable.m_RowHeaders.size() + 1; i++)
    {
        if (i == iLeadingRow)
            continue;

        // проход по столбцам
        for (size_t j = 0; j < g_STable.m_ColumnHeaders.size() + 1; j++)
        {
            if (j == iLeadingCol)
                continue;

            g_STable.m_Table[i][j] = g_STable.m_Table[i][j] - (CopyLeadingCol[i] * CopyLeadingRow[j]) * fLeadingValue;
        }
    }
}

void FirstIterateTable()
{
    // если все свободные - позитивны, то к шагу два переходим
    bool bIsAllPositive = true;

    for (size_t i = 1; i < g_STable.m_RowHeaders.size() + 1; i++)
    {
        if (g_STable.m_Table[i][0] < 0.0f)
        {
            bIsAllPositive = false;
            break;
        }
    }

    if (bIsAllPositive)
    {
        g_eSolutionState = eSolutionState::SECONDSTEP;
        return;
    }

    // если нет, то надо выбрать самый минимальный в свободном, это будет ведущая строчка
    size_t iLeadingRow = -1;
    for (size_t i = 1; i < g_STable.m_RowHeaders.size() + 1; i++)
    {
        if (iLeadingRow == -1 || g_STable.m_Table[i][0] < g_STable.m_Table[iLeadingRow][0])
        {
            iLeadingRow = i;
        }
    }

    // выбираем ведущий столбец, как самый минимальный в ведущей строчке
    size_t iLeadingCol = -1;
    for (size_t i = 1; i < g_STable.m_ColumnHeaders.size() + 1; i++)
    {
        if ((iLeadingCol == -1 || g_STable.m_Table[iLeadingRow][i] < g_STable.m_Table[iLeadingRow][iLeadingCol]) &&
            g_STable.m_Table[iLeadingRow][i] < 0.0f)
        {
            iLeadingCol = i;
        }
    }

    if (iLeadingCol == -1)
    {
        g_eSolutionState = eSolutionState::FAILED;
        return;
    }

    RecomputeTable(iLeadingRow, iLeadingCol);

    PrintTable();
}

void SecondIterateTable()
{
    bool bIsAllPositive = true;

    for (size_t i = 1; i < g_STable.m_ColumnHeaders.size() + 1; i++)
    {
        if (g_STable.m_Table[0][i] < 0.0f)
        {
            bIsAllPositive = false;
            break;
        }
    }

    // нет отрицательных - найдено оптимальное решение
    if (bIsAllPositive)
    {
        g_eSolutionState = eSolutionState::FINISHED;
        return;
    }

    // если есть, то надо улучшать
    size_t iLeadingCol = -1;
    for (size_t i = 1; i < g_STable.m_ColumnHeaders.size() + 1; i++)
    {
        if (iLeadingCol == -1 || g_STable.m_Table[0][i] < g_STable.m_Table[0][iLeadingCol])
        {
            iLeadingCol = i;
        }
    }

    size_t iLeadingRow = -1;
    for (size_t i = 1; i < g_STable.m_RowHeaders.size() + 1; i++)
    {
        if ((iLeadingRow == -1 ||
            g_STable.m_Table[i][0] / g_STable.m_Table[i][iLeadingCol] < g_STable.m_Table[iLeadingRow][0] / g_STable.m_Table[iLeadingRow][iLeadingCol]) &&
            g_STable.m_Table[i][0] >= 0.0f && g_STable.m_Table[i][iLeadingCol] >= 0.0f)
        {
            iLeadingRow = i;
        }
    }

    if (iLeadingRow == -1)
    {
        g_eSolutionState = eSolutionState::FAILED;
        return;
    }

    RecomputeTable(iLeadingRow, iLeadingCol);

    PrintTable();
}

void PrintResult()
{
    float fResult = g_STable.m_Table[0][0];
    if (g_STable.m_bIsMin)
        fResult = -fResult;

    printf("F = %0.3f\n\n", fResult);

    // здесь надо взять m_ColumnHeaders.size() переменных первых, но только тех, которые в m_RowHeaders
    std::vector<float> Variables(g_STable.m_ColumnHeaders.size(), 0.0f);

    for (size_t i = 0; i < g_STable.m_RowHeaders.size(); i++)
    {
        if (g_STable.m_RowHeaders[i] < g_STable.m_ColumnHeaders.size())
        Variables[g_STable.m_RowHeaders[i]] = g_STable.m_Table[i + 1][0];
    }

    int iCountVar = 0;
    for (float const iVar : Variables)
    {
        printf("x%d = %0.3f\n", iCountVar + 1, iVar);

        iCountVar++;
    }
}

int main()
{
    // на вход подаётся функция и какое-то количество условий ограничивающих

    // Целевая функция:
    std::string sFunc = "1 * x1 + 1 * x2 + 1 * x3 + 1 * x4 + 1 * x5 + 1 * x6 + 1 * x7 + 1 * x8 + 1 * x9 + 1 * x10 + 1 * x11 + 1 * x12 + 1 * x13 + 1 * x14 + 1 * x15 -> max";

    // теперь на вход подаются условия:
    std::string sEquations[] =
    {
        "0.3    x1 + 0.25   x2 + 0.2    x3 + 0.166  x4 + 0.143  x5 + 0.125  x6 + 0.111  x7 + 0.1    x8 + 0.09   x9 + 0.083  x10 + 0.077     x11 + 0.0714    x12 + 0.0666    x13 + 0.0625    x14 + 0.0588 x15 = 14",
        "0.25   x1 + 0.2    x2 + 0.166  x3 + 0.143  x4 + 0.125  x5 + 0.111  x6 + 0.1    x7 + 0.09   x8 + 0.083  x9 + 0.077  x10 + 0.0714    x11 + 0.0666    x12 + 0.0625    x13 + 0.0588    x14 + 0.0555 x15 = 13",
        "0.2    x1 + 0.166  x2 + 0.143  x3 + 0.125  x4 + 0.111  x5 + 0.1    x6 + 0.09   x7 + 0.083  x8 + 0.077  x9 + 0.0714 x10 + 0.0666    x11 + 0.0625    x12 + 0.0588    x13 + 0.0555    x14 + 0.0526 x15 = 12",
        "0.166  x1 + 0.143  x2 + 0.125  x3 + 0.111  x4 + 0.1    x5 + 0.09   x6 + 0.083  x7 + 0.077  x8 + 0.0714 x9 + 0.0666 x10 + 0.0625    x11 + 0.0588    x12 + 0.0555    x13 + 0.0526    x14 + 0.05   x15 = 11",
        "0.143  x1 + 0.125  x2 + 0.111  x3 + 0.1    x4 + 0.09   x5 + 0.083  x6 + 0.077  x7 + 0.0714 x8 + 0.0666 x9 + 0.0625 x10 + 0.0588    x11 + 0.0555    x12 + 0.0526    x13 + 0.05      x14 + 0.0476 x15 = 10"
    };

    /*
    // Целевая функция:
    std::string sFunc = "2 * x1 + 5 * x2 + 3 * x3 + 8 * x4 -> min";

    // теперь на вход подаются условия:
    std::string sEquations[] =
    {
        "3 * x1 + 6 * x2 - 4 * x3 + 1 * x4 <= 12",
        "4 * x1 - 13 * x2 + 10 * x3 + 5 * x4 >= 6",
        "3 * x1 + 7 * x2 + 1 * x3 >= 1"
    };
    */

    // теперь надо их распарсить в табличку
    if (!ParseInputToTable(sFunc, sEquations, ARRAYSIZE(sEquations)))
    {
        RAISE_ERROR("Parse error!");
    }

    while (g_eSolutionState != eSolutionState::FINISHED)
    {
        if (g_eSolutionState != eSolutionState::SECONDSTEP)
        {
            FirstIterateTable();
        }
        else
        {
            SecondIterateTable();
        }

        if (g_eSolutionState == eSolutionState::FAILED)
        {
            RAISE_ERROR("It is not possible to solve!");
        }
    }

    // state = finished
    PrintResult();

    _getch();
    return 0;
};