#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;
//Двойственность
void DualitySearchFunc(double basis[4]);

int main()
{
    setlocale(LC_ALL, "RUSSIAN");
    double basis[4] = { 0, 0, 0, 0 };            //базисные переменные
    DualitySearchFunc(basis);
    system("pause");
    return 0;
}

//Симплекс метод
void SimplexMethod(double basis[4])
{
    //Заполнение массивов исходных функций
    double func_coef[4] = { -1, 3, -2, 1 };       //исходная функция
    double limit1_coef[5] = { -1, 5, 0, 1, 2 }; //первое ограничение
    double limit2_coef[5] = { 2, -1, 1, 0, 5 };  //второе ограничение
    double diff_symplex[5] = { 0, 0, 0, 0, 0 };  //симлекс разности

    //Определение переменных метода
    double x = -10000;                   //базисные переменные
    double y = -10000;
    int j = 0;                                   //счетчик
    int basis_index1 = 0;                        //номера базисных переменных
    int basis_index2 = 0;                        //
    int choice = 0;
    int check = 1;
    double max_diff_symplex = -1000;             //максимальная симплекс разности
    double min_diff_symplex = 1000;              //минимальная симплекс разности
    double hostitem = 0;                         //ведущий элемент
    double host_column_item = 0;                 //элемент ведущего столбца
    int hostcolumn_index = 0;                    //номер ведущего столбца
    int hostline_index = 0;                      //номер ведущей строки
    int n = 4;                                   //Число переменных
    int m = 2;                                   //Число ограничений

    cout << "Определяем число свободных переменных как n - m, то есть число переменных - число ограничений. Оно равно " << n - m << endl;
    cout << "Число базисных переменных, которое равняется числу ограничений, равно " << m << endl;

    //Определяем базисные переменные
    for (j = 0; j < 4; j++)
    {
        if (limit2_coef[j] == 0 && limit1_coef[j] != 0)
        {
            //поиск значения базвой переменнной
            x = limit1_coef[4] / limit1_coef[j];
            basis[j] = x;
            basis_index1 = j;
            cout << "Найдена базисная переменная: x" << j + 1 << " = " << basis[j] << endl;
        }

        if (limit1_coef[j] == 0 && limit2_coef[j] != 0)
        {
            //поиск значения базвой переменнной
            x = limit2_coef[4] / limit2_coef[j];
            basis[j] = x;
            basis_index2 = j;
            cout << "Найдена базисная переменная: x" << j + 1 << " = " << basis[j] << endl;
        }
    }
    x = -10000;

    cout << "Симплекс таблица\n" << endl;
    cout << setw(26) << 0 << setw(10) << func_coef[0] << setw(10) << func_coef[1] << setw(10) << func_coef[2] << setw(10) << func_coef[3] << endl;
    cout << setw(10) << func_coef[basis_index2] << setw(5) << "x" << basis_index2 + 1 << setw(10) << basis[basis_index2] << setw(10) << limit1_coef[0] << setw(10) << limit1_coef[1] << setw(10) << limit1_coef[2] << setw(10) << limit1_coef[3] << endl;
    cout << setw(10) << func_coef[basis_index1] << setw(5) << "x" << basis_index1 + 1 << setw(10) << basis[basis_index1] << setw(10) << limit2_coef[0] << setw(10) << limit2_coef[1] << setw(10) << limit2_coef[2] << setw(10) << limit2_coef[3] << endl;

    //подсчет симплекс разности
    diff_symplex[0] = 0 - basis[basis_index1] * func_coef[basis_index1] - basis[basis_index2] * func_coef[basis_index2];
    cout << setw(22) << "Симплекс разности" << setw(4) << diff_symplex[0];

    for (j = 0; j < 4; j++)
    {
        diff_symplex[j + 1] = func_coef[j] - limit1_coef[j] * func_coef[basis_index1] - limit2_coef[j] * func_coef[basis_index2];
        cout << setw(10) << diff_symplex[j + 1];
    }

    cout << "\n\nВыберете вариант поиска:\n1) Поиск максимума функции;\n2) Поиск минимума функции;" << endl;
    cin >> choice;

    //По выбору пользователя осуществляется поиск максимума или минимума функции
    while (check > 0)
    {
        check = 0;
        //поиск симплекс разности для расчета максимума
        if (choice == 1)
        {
            max_diff_symplex = 0;

            //поиск max симлекс разности
            for (j = 1; j < 5; j++)
            {
                if (diff_symplex[j] > max_diff_symplex)
                {
                    max_diff_symplex = diff_symplex[j];
                    hostcolumn_index = j;
                }
            }

        }
        //поиск симплекс разности для расчета минимума
        else
        {
            min_diff_symplex = 1000;

            //поиск min симлекс разности
            for (j = 1; j < 5; j++)
            {

                if (min_diff_symplex > diff_symplex[j])
                {
                    min_diff_symplex = diff_symplex[j];
                    hostcolumn_index = j;
                }
            }

        }

        //определение ведущей строки
        if (basis[basis_index2] / limit1_coef[hostcolumn_index - 1] > 0 && limit1_coef[hostcolumn_index - 1] != 0)
            x = basis[basis_index2] / limit1_coef[hostcolumn_index - 1];

        if (basis[basis_index1] / limit2_coef[hostcolumn_index - 1] > 0 && limit2_coef[hostcolumn_index - 1] != 0)
            y = basis[basis_index1] / limit2_coef[hostcolumn_index - 1];

        if ((x > y && y > 0) || x < 0)
        {
            hostline_index = 2;
            hostitem = limit2_coef[hostcolumn_index - 1];
        }
        if ((x < y && x >0) || y < 0)
        {
            hostline_index = 1;
            hostitem = limit1_coef[hostcolumn_index - 1];
        }

        //определение ведущего элемента и пересчет коэффициентов ведущей строки
        if (hostline_index == 1)
        {
            //добавление нового базового элемента
            basis[hostcolumn_index - 1] = basis[basis_index1] / hostitem;

            //обновление ведущей строки
            for (j = 0; j < 4; j++)
                limit1_coef[j] = limit1_coef[j] / hostitem;

            host_column_item = limit2_coef[hostcolumn_index - 1];

            //пересчёт второй строки симплекс таблицы
            basis[basis_index2] = basis[hostcolumn_index - 1] * (-limit2_coef[hostcolumn_index - 1]) + basis[basis_index2];

            for (j = 0; j < 4; j++)
                limit2_coef[j] = limit1_coef[j] * (-host_column_item) + limit2_coef[j];

            //пересчёт строки симплекс разности и запоминание элемента ведущего столбца
            host_column_item = diff_symplex[hostcolumn_index];

            diff_symplex[0] = basis[hostcolumn_index - 1] * (-host_column_item) + diff_symplex[0];

            for (j = 0; j < 4; j++)
                diff_symplex[j + 1] = limit1_coef[j] * (-host_column_item) + diff_symplex[j + 1];

            //удаление старого базисного элемента из массива
            basis[basis_index1] = 0;
            basis_index1 = hostcolumn_index - 1;

            cout << setw(26) << 0 << setw(10) << func_coef[0] << setw(10) << func_coef[1] << setw(10) << func_coef[2] << setw(10) << func_coef[3] << endl;
            cout << setw(10) << func_coef[basis_index2] << setw(5) << "x" << basis_index2 + 1 << setw(10) << basis[basis_index2] << setw(10) << limit1_coef[0] << setw(10) << limit1_coef[1] << setw(10) << limit1_coef[2] << setw(10) << limit1_coef[3] << endl;
            cout << setw(10) << func_coef[basis_index1] << setw(5) << "x" << basis_index1 + 1 << setw(10) << basis[basis_index1] << setw(10) << limit2_coef[0] << setw(10) << limit2_coef[1] << setw(10) << limit2_coef[2] << setw(10) << limit2_coef[3] << endl;
            cout << setw(17) << "Симплекс разности" << setw(9);

            //проверка на последующую итерацию
            if (choice == 1)
            {
                for (j = 0; j < 5; j++)
                {
                    cout << diff_symplex[j] << setw(10);
                    if (diff_symplex[j] > 0)
                        check++;
                }
                cout << "\n\n\n";
            }
            else
            {
                for (j = 0; j < 5; j++)
                {
                    cout << diff_symplex[j] << setw(10);
                    if (diff_symplex[j] < 0)
                        check++;
                }
                cout << "\n\n\n";
            }


        }
        if (hostline_index == 2)
        {
            //добавление нового базового элемента
            basis[hostcolumn_index - 1] = basis[basis_index2] / limit2_coef[hostcolumn_index - 1];

            //обновление ведущей строки
            for (j = 0; j < 4; j++)
                limit2_coef[j] = limit2_coef[j] / hostitem;

            host_column_item = limit1_coef[hostcolumn_index - 1];

            //пересчёт первой строки симплекс таблицы
            basis[basis_index1] = basis[hostcolumn_index - 1] * (-host_column_item) + basis[basis_index1];

            for (j = 0; j < 4; j++)
                limit1_coef[j] = limit2_coef[j] * (-host_column_item) + limit1_coef[j];

            //пересчёт строки симплекс разности и запоминание элемента ведущего столбца
            host_column_item = diff_symplex[hostcolumn_index];

            diff_symplex[0] = basis[hostcolumn_index - 1] * (-host_column_item) + diff_symplex[0];

            for (j = 0; j < 4; j++)
                diff_symplex[j + 1] = limit2_coef[j] * (-host_column_item) + diff_symplex[j + 1];

            //удаление старого базисного элемента из массива
            basis[basis_index2] = 0;
            basis_index2 = hostcolumn_index - 1;

            cout << setw(26) << 0 << setw(10) << func_coef[0] << setw(10) << func_coef[1] << setw(10) << func_coef[2] << setw(10) << func_coef[3] << endl;
            cout << setw(10) << func_coef[basis_index2] << setw(5) << "x" << basis_index2 + 1 << setw(10) << basis[basis_index2] << setw(10) << limit1_coef[0] << setw(10) << limit1_coef[1] << setw(10) << limit1_coef[2] << setw(10) << limit1_coef[3] << endl;
            cout << setw(10) << func_coef[basis_index1] << setw(5) << "x" << basis_index1 + 1 << setw(10) << basis[basis_index1] << setw(10) << limit2_coef[0] << setw(10) << limit2_coef[1] << setw(10) << limit2_coef[2] << setw(10) << limit2_coef[3] << endl;
            cout << setw(17) << "Симплекс разности" << setw(9);

            for (j = 0; j < 5; j++)
                cout << diff_symplex[j] << setw(10);
            cout << "\n\n\n";

            //проверка на последующую итерацию
            if (choice == 1)
            {
                for (j = 1; j < 5; j++)
                    if (diff_symplex[j] > 0)
                        check++;

                cout << endl << endl;
            }
            else
            {
                for (j = 1; j < 5; j++)
                    if (diff_symplex[j] < 0)
                        check++;
                cout << endl << endl;
            }
        }
    }

    //вывод результата работы метода в виде значения функции и точки, в которой оно достигается
    cout << "Для исходной функции" << endl;
    if (choice == 1)
    {
        cout << "Максимум функции = " << -diff_symplex[0] << endl;
        cout << "В точке ( ";
        for (j = 0; j < 4; j++)
        {
            if (j != 3)
                cout << basis[j] << ", ";
            else
                cout << basis[j] << " ";
        }
        cout << ")" << endl;
    }
    if (choice == 2)
    {
        cout << "Минимум функции = " << -diff_symplex[0] << endl;
        cout << "В точке ( ";
        for (j = 0; j < 4; j++)
        {
            if (j != 3)
                cout << basis[j] << ", ";
            else
                cout << basis[j] << " ";
        }
        cout << ")" << endl;
    }
}



//Двойственность
void DualitySearchFunc(double basis[4])
{
    //Заполнение массивов исходных функций
    double func_coef[4] = { -1, 3, -2, 1 };            //исходная функция
    double limits_coef[2][5] =
    { { -1, 5, 0, 1, 2 }, //ограничения функций
      {2, -1, 1, 0, 5} };
    double duality_func_coef[2];                      //двойственная функция
    double duality_limits_coef[4][2];                 //ограничения двойственной функции
    int i = 0; int j = 0; int k = 0;               //счетчики
    double optimal[2][2];       //матрица из компонентов оптимального базиса
    double determinant = 0;               //определитель
    double optimal_T[2][2];               //транспонированная
    double optimal_inv[2][2];                         //обратная
    short choice = 0;                     //выбор пользователя
    double y1, y2;
    cout << "Что вы ищете для исходной функции?" << endl;
    cout << "1) Определение максимума " << endl;
    cout << "2) Определение минимума " << endl;
    cin >> choice;
    //заполнение коэффициентов двойственной функции
    duality_func_coef[0] = limits_coef[0][4];
    duality_func_coef[1] = limits_coef[1][4];

    //заполнение коэффициентов ограничений двойственной функции
    for (j = 0; j < 4; j++)
        for (i = 0; i < 2; i++)
            duality_limits_coef[j][i] = limits_coef[i][j];

    //вывод получившейся двойственной задачи по отношению к исходной
    cout << "\nФункция, двойственная к исходной имеет следующий вид:\n";
    cout << "fдв. = " << duality_func_coef[0] << "y1" << " + " << duality_func_coef[1] << "y2 " << endl;
    cout << "\nОграничения для функции, двойственной к исходной, имеют следующий вид:\n";
    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < 2; j++)
        {
            if (j == 0)
            {
                if (duality_limits_coef[i][j] >= 0)
                    cout << setw(6) << right << "(" << duality_limits_coef[i][j] << ")*" << "y" << j + 1 << setw(2) << "+";
                else if (duality_limits_coef[i][j] < 0)
                    cout << setw(5) << right << "(" << duality_limits_coef[i][j] << ")*" << "y" << j + 1 << setw(2) << "+";
            }
            else
            {
                if (duality_limits_coef[i][j] >= 0)
                    cout << setw(3) << right << "(" << duality_limits_coef[i][j] << ")*" << "y" << j + 1 << " ";
                else if (duality_limits_coef[i][j] < 0)
                    cout << setw(2) << right << "(" << duality_limits_coef[i][j] << ")*" << "y" << j + 1 << " ";
            }
        }
        if (choice == 1)
            cout << " >=" << setw(3) << right << func_coef[i] << endl;
        else
            cout << " <=" << setw(3) << right << func_coef[i] << endl;
    }
    //применение симплекс метода для двойственной функции
    SimplexMethod(basis);

    //составление матрицы из компонентов векторов, входящих в оптимальный базис
    for (j = 3; j > -1; j--)
    {
        if (basis[j] != 0)
        {
            optimal[0][k] = limits_coef[0][j];
            optimal[1][k] = limits_coef[1][j];
            ++k;
        }
    }

    //поиск обратной матрицы

    //подсчет определителя
    determinant = optimal[0][0] * optimal[1][1] - optimal[0][1] * optimal[1][0];

    //транспонирование
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            optimal_T[i][j] = optimal[j][i];
    //высчитывание обратной матрциы
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            optimal_inv[i][j] = pow((-1), i + j + 2) * optimal_T[1 - i][1 - j] / determinant;
    k = 0;

    //подсчет оптимальных значений y1 и y2
    for (j = 0; j < 4; j++)
    {
        //перемножение полученной матрицы с коэффициентами исходной функции
        if (basis[j] != 0 && k != 0)
        {
            optimal_inv[0][0] = func_coef[j] * optimal_inv[0][0];
            optimal_inv[0][1] = func_coef[j] * optimal_inv[0][1];
            k++;
        }
        if (basis[j] != 0 && k == 0)
        {
            optimal_inv[1][0] = func_coef[j] * optimal_inv[1][0];
            optimal_inv[1][1] = func_coef[j] * optimal_inv[1][1];
            k++;
        }
    }

    y1 = optimal_inv[0][0] + optimal_inv[1][0];
    y2 = optimal_inv[0][1] + optimal_inv[1][1];
    cout << "Для двойственной функции" << endl;
    cout << "y1 = " << y1 << endl;
    cout << "y2 = " << y2 << endl;
    cout << "Ее значение  fдв. = " << duality_func_coef[0] * y1 + duality_func_coef[1] * y2 << endl;
    cout << "Результаты в точности совпали." << endl;
}