Advertisement
baadgeorge

Untitled

Dec 21st, 2021
961
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 16.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6. //Двойственность
  7. void DualitySearchFunc(double basis[4]);
  8.  
  9. int main()
  10. {
  11.     setlocale(LC_ALL, "RUSSIAN");
  12.     double basis[4] = { 0, 0, 0, 0 };            //базисные переменные
  13.     DualitySearchFunc(basis);
  14.     system("pause");
  15.     return 0;
  16. }
  17.  
  18. //Симплекс метод
  19. void SimplexMethod(double basis[4])
  20. {
  21.     //Заполнение массивов исходных функций
  22.     double func_coef[4] = { -1, 3, -2, 1 };       //исходная функция
  23.     double limit1_coef[5] = { -1, 5, 0, 1, 2 }; //первое ограничение
  24.     double limit2_coef[5] = { 2, -1, 1, 0, 5 };  //второе ограничение
  25.     double diff_symplex[5] = { 0, 0, 0, 0, 0 };  //симлекс разности
  26.  
  27.     //Определение переменных метода
  28.     double x = -10000;                   //базисные переменные
  29.     double y = -10000;
  30.     int j = 0;                                   //счетчик
  31.     int basis_index1 = 0;                        //номера базисных переменных
  32.     int basis_index2 = 0;                        //
  33.     int choice = 0;
  34.     int check = 1;
  35.     double max_diff_symplex = -1000;             //максимальная симплекс разности
  36.     double min_diff_symplex = 1000;              //минимальная симплекс разности
  37.     double hostitem = 0;                         //ведущий элемент
  38.     double host_column_item = 0;                 //элемент ведущего столбца
  39.     int hostcolumn_index = 0;                    //номер ведущего столбца
  40.     int hostline_index = 0;                      //номер ведущей строки
  41.     int n = 4;                                   //Число переменных
  42.     int m = 2;                                   //Число ограничений
  43.  
  44.     cout << "Определяем число свободных переменных как n - m, то есть число переменных - число ограничений. Оно равно " << n - m << endl;
  45.     cout << "Число базисных переменных, которое равняется числу ограничений, равно " << m << endl;
  46.  
  47.     //Определяем базисные переменные
  48.     for (j = 0; j < 4; j++)
  49.     {
  50.         if (limit2_coef[j] == 0 && limit1_coef[j] != 0)
  51.         {
  52.             //поиск значения базвой переменнной
  53.             x = limit1_coef[4] / limit1_coef[j];
  54.             basis[j] = x;
  55.             basis_index1 = j;
  56.             cout << "Найдена базисная переменная: x" << j + 1 << " = " << basis[j] << endl;
  57.         }
  58.  
  59.         if (limit1_coef[j] == 0 && limit2_coef[j] != 0)
  60.         {
  61.             //поиск значения базвой переменнной
  62.             x = limit2_coef[4] / limit2_coef[j];
  63.             basis[j] = x;
  64.             basis_index2 = j;
  65.             cout << "Найдена базисная переменная: x" << j + 1 << " = " << basis[j] << endl;
  66.         }
  67.     }
  68.     x = -10000;
  69.  
  70.     cout << "Симплекс таблица\n" << endl;
  71.     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;
  72.     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;
  73.     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;
  74.  
  75.     //подсчет симплекс разности
  76.     diff_symplex[0] = 0 - basis[basis_index1] * func_coef[basis_index1] - basis[basis_index2] * func_coef[basis_index2];
  77.     cout << setw(22) << "Симплекс разности" << setw(4) << diff_symplex[0];
  78.  
  79.     for (j = 0; j < 4; j++)
  80.     {
  81.         diff_symplex[j + 1] = func_coef[j] - limit1_coef[j] * func_coef[basis_index1] - limit2_coef[j] * func_coef[basis_index2];
  82.         cout << setw(10) << diff_symplex[j + 1];
  83.     }
  84.  
  85.     cout << "\n\nВыберете вариант поиска:\n1) Поиск максимума функции;\n2) Поиск минимума функции;" << endl;
  86.     cin >> choice;
  87.  
  88.     //По выбору пользователя осуществляется поиск максимума или минимума функции
  89.     while (check > 0)
  90.     {
  91.         check = 0;
  92.         //поиск симплекс разности для расчета максимума
  93.         if (choice == 1)
  94.         {
  95.             max_diff_symplex = 0;
  96.  
  97.             //поиск max симлекс разности
  98.             for (j = 1; j < 5; j++)
  99.             {
  100.                 if (diff_symplex[j] > max_diff_symplex)
  101.                 {
  102.                     max_diff_symplex = diff_symplex[j];
  103.                     hostcolumn_index = j;
  104.                 }
  105.             }
  106.  
  107.         }
  108.         //поиск симплекс разности для расчета минимума
  109.         else
  110.         {
  111.             min_diff_symplex = 1000;
  112.  
  113.             //поиск min симлекс разности
  114.             for (j = 1; j < 5; j++)
  115.             {
  116.  
  117.                 if (min_diff_symplex > diff_symplex[j])
  118.                 {
  119.                     min_diff_symplex = diff_symplex[j];
  120.                     hostcolumn_index = j;
  121.                 }
  122.             }
  123.  
  124.         }
  125.  
  126.         //определение ведущей строки
  127.         if (basis[basis_index2] / limit1_coef[hostcolumn_index - 1] > 0 && limit1_coef[hostcolumn_index - 1] != 0)
  128.             x = basis[basis_index2] / limit1_coef[hostcolumn_index - 1];
  129.  
  130.         if (basis[basis_index1] / limit2_coef[hostcolumn_index - 1] > 0 && limit2_coef[hostcolumn_index - 1] != 0)
  131.             y = basis[basis_index1] / limit2_coef[hostcolumn_index - 1];
  132.  
  133.         if ((x > y && y > 0) || x < 0)
  134.         {
  135.             hostline_index = 2;
  136.             hostitem = limit2_coef[hostcolumn_index - 1];
  137.         }
  138.         if ((x < y && x >0) || y < 0)
  139.         {
  140.             hostline_index = 1;
  141.             hostitem = limit1_coef[hostcolumn_index - 1];
  142.         }
  143.  
  144.         //определение ведущего элемента и пересчет коэффициентов ведущей строки
  145.         if (hostline_index == 1)
  146.         {
  147.             //добавление нового базового элемента
  148.             basis[hostcolumn_index - 1] = basis[basis_index1] / hostitem;
  149.  
  150.             //обновление ведущей строки
  151.             for (j = 0; j < 4; j++)
  152.                 limit1_coef[j] = limit1_coef[j] / hostitem;
  153.  
  154.             host_column_item = limit2_coef[hostcolumn_index - 1];
  155.  
  156.             //пересчёт второй строки симплекс таблицы
  157.             basis[basis_index2] = basis[hostcolumn_index - 1] * (-limit2_coef[hostcolumn_index - 1]) + basis[basis_index2];
  158.  
  159.             for (j = 0; j < 4; j++)
  160.                 limit2_coef[j] = limit1_coef[j] * (-host_column_item) + limit2_coef[j];
  161.  
  162.             //пересчёт строки симплекс разности и запоминание элемента ведущего столбца
  163.             host_column_item = diff_symplex[hostcolumn_index];
  164.  
  165.             diff_symplex[0] = basis[hostcolumn_index - 1] * (-host_column_item) + diff_symplex[0];
  166.  
  167.             for (j = 0; j < 4; j++)
  168.                 diff_symplex[j + 1] = limit1_coef[j] * (-host_column_item) + diff_symplex[j + 1];
  169.  
  170.             //удаление старого базисного элемента из массива
  171.             basis[basis_index1] = 0;
  172.             basis_index1 = hostcolumn_index - 1;
  173.  
  174.             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;
  175.             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;
  176.             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;
  177.             cout << setw(17) << "Симплекс разности" << setw(9);
  178.  
  179.             //проверка на последующую итерацию
  180.             if (choice == 1)
  181.             {
  182.                 for (j = 0; j < 5; j++)
  183.                 {
  184.                     cout << diff_symplex[j] << setw(10);
  185.                     if (diff_symplex[j] > 0)
  186.                         check++;
  187.                 }
  188.                 cout << "\n\n\n";
  189.             }
  190.             else
  191.             {
  192.                 for (j = 0; j < 5; j++)
  193.                 {
  194.                     cout << diff_symplex[j] << setw(10);
  195.                     if (diff_symplex[j] < 0)
  196.                         check++;
  197.                 }
  198.                 cout << "\n\n\n";
  199.             }
  200.  
  201.  
  202.         }
  203.         if (hostline_index == 2)
  204.         {
  205.             //добавление нового базового элемента
  206.             basis[hostcolumn_index - 1] = basis[basis_index2] / limit2_coef[hostcolumn_index - 1];
  207.  
  208.             //обновление ведущей строки
  209.             for (j = 0; j < 4; j++)
  210.                 limit2_coef[j] = limit2_coef[j] / hostitem;
  211.  
  212.             host_column_item = limit1_coef[hostcolumn_index - 1];
  213.  
  214.             //пересчёт первой строки симплекс таблицы
  215.             basis[basis_index1] = basis[hostcolumn_index - 1] * (-host_column_item) + basis[basis_index1];
  216.  
  217.             for (j = 0; j < 4; j++)
  218.                 limit1_coef[j] = limit2_coef[j] * (-host_column_item) + limit1_coef[j];
  219.  
  220.             //пересчёт строки симплекс разности и запоминание элемента ведущего столбца
  221.             host_column_item = diff_symplex[hostcolumn_index];
  222.  
  223.             diff_symplex[0] = basis[hostcolumn_index - 1] * (-host_column_item) + diff_symplex[0];
  224.  
  225.             for (j = 0; j < 4; j++)
  226.                 diff_symplex[j + 1] = limit2_coef[j] * (-host_column_item) + diff_symplex[j + 1];
  227.  
  228.             //удаление старого базисного элемента из массива
  229.             basis[basis_index2] = 0;
  230.             basis_index2 = hostcolumn_index - 1;
  231.  
  232.             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;
  233.             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;
  234.             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;
  235.             cout << setw(17) << "Симплекс разности" << setw(9);
  236.  
  237.             for (j = 0; j < 5; j++)
  238.                 cout << diff_symplex[j] << setw(10);
  239.             cout << "\n\n\n";
  240.  
  241.             //проверка на последующую итерацию
  242.             if (choice == 1)
  243.             {
  244.                 for (j = 1; j < 5; j++)
  245.                     if (diff_symplex[j] > 0)
  246.                         check++;
  247.  
  248.                 cout << endl << endl;
  249.             }
  250.             else
  251.             {
  252.                 for (j = 1; j < 5; j++)
  253.                     if (diff_symplex[j] < 0)
  254.                         check++;
  255.                 cout << endl << endl;
  256.             }
  257.         }
  258.     }
  259.  
  260.     //вывод результата работы метода в виде значения функции и точки, в которой оно достигается
  261.     cout << "Для исходной функции" << endl;
  262.     if (choice == 1)
  263.     {
  264.         cout << "Максимум функции = " << -diff_symplex[0] << endl;
  265.         cout << "В точке ( ";
  266.         for (j = 0; j < 4; j++)
  267.         {
  268.             if (j != 3)
  269.                 cout << basis[j] << ", ";
  270.             else
  271.                 cout << basis[j] << " ";
  272.         }
  273.         cout << ")" << endl;
  274.     }
  275.     if (choice == 2)
  276.     {
  277.         cout << "Минимум функции = " << -diff_symplex[0] << endl;
  278.         cout << "В точке ( ";
  279.         for (j = 0; j < 4; j++)
  280.         {
  281.             if (j != 3)
  282.                 cout << basis[j] << ", ";
  283.             else
  284.                 cout << basis[j] << " ";
  285.         }
  286.         cout << ")" << endl;
  287.     }
  288. }
  289.  
  290.  
  291.  
  292. //Двойственность
  293. void DualitySearchFunc(double basis[4])
  294. {
  295.     //Заполнение массивов исходных функций
  296.     double func_coef[4] = { -1, 3, -2, 1 };            //исходная функция
  297.     double limits_coef[2][5] =
  298.     { { -1, 5, 0, 1, 2 }, //ограничения функций
  299.       {2, -1, 1, 0, 5} };
  300.     double duality_func_coef[2];                      //двойственная функция
  301.     double duality_limits_coef[4][2];                 //ограничения двойственной функции
  302.     int i = 0; int j = 0; int k = 0;               //счетчики
  303.     double optimal[2][2];       //матрица из компонентов оптимального базиса
  304.     double determinant = 0;               //определитель
  305.     double optimal_T[2][2];               //транспонированная
  306.     double optimal_inv[2][2];                         //обратная
  307.     short choice = 0;                     //выбор пользователя
  308.     double y1, y2;
  309.     cout << "Что вы ищете для исходной функции?" << endl;
  310.     cout << "1) Определение максимума " << endl;
  311.     cout << "2) Определение минимума " << endl;
  312.     cin >> choice;
  313.     //заполнение коэффициентов двойственной функции
  314.     duality_func_coef[0] = limits_coef[0][4];
  315.     duality_func_coef[1] = limits_coef[1][4];
  316.  
  317.     //заполнение коэффициентов ограничений двойственной функции
  318.     for (j = 0; j < 4; j++)
  319.         for (i = 0; i < 2; i++)
  320.             duality_limits_coef[j][i] = limits_coef[i][j];
  321.  
  322.     //вывод получившейся двойственной задачи по отношению к исходной
  323.     cout << "\nФункция, двойственная к исходной имеет следующий вид:\n";
  324.     cout << "fдв. = " << duality_func_coef[0] << "y1" << " + " << duality_func_coef[1] << "y2 " << endl;
  325.     cout << "\nОграничения для функции, двойственной к исходной, имеют следующий вид:\n";
  326.     for (i = 0; i < 4; i++)
  327.     {
  328.         for (j = 0; j < 2; j++)
  329.         {
  330.             if (j == 0)
  331.             {
  332.                 if (duality_limits_coef[i][j] >= 0)
  333.                     cout << setw(6) << right << "(" << duality_limits_coef[i][j] << ")*" << "y" << j + 1 << setw(2) << "+";
  334.                 else if (duality_limits_coef[i][j] < 0)
  335.                     cout << setw(5) << right << "(" << duality_limits_coef[i][j] << ")*" << "y" << j + 1 << setw(2) << "+";
  336.             }
  337.             else
  338.             {
  339.                 if (duality_limits_coef[i][j] >= 0)
  340.                     cout << setw(3) << right << "(" << duality_limits_coef[i][j] << ")*" << "y" << j + 1 << " ";
  341.                 else if (duality_limits_coef[i][j] < 0)
  342.                     cout << setw(2) << right << "(" << duality_limits_coef[i][j] << ")*" << "y" << j + 1 << " ";
  343.             }
  344.         }
  345.         if (choice == 1)
  346.             cout << " >=" << setw(3) << right << func_coef[i] << endl;
  347.         else
  348.             cout << " <=" << setw(3) << right << func_coef[i] << endl;
  349.     }
  350.     //применение симплекс метода для двойственной функции
  351.     SimplexMethod(basis);
  352.  
  353.     //составление матрицы из компонентов векторов, входящих в оптимальный базис
  354.     for (j = 3; j > -1; j--)
  355.     {
  356.         if (basis[j] != 0)
  357.         {
  358.             optimal[0][k] = limits_coef[0][j];
  359.             optimal[1][k] = limits_coef[1][j];
  360.             ++k;
  361.         }
  362.     }
  363.  
  364.     //поиск обратной матрицы
  365.  
  366.     //подсчет определителя
  367.     determinant = optimal[0][0] * optimal[1][1] - optimal[0][1] * optimal[1][0];
  368.  
  369.     //транспонирование
  370.     for (i = 0; i < 2; i++)
  371.         for (j = 0; j < 2; j++)
  372.             optimal_T[i][j] = optimal[j][i];
  373.     //высчитывание обратной матрциы
  374.     for (i = 0; i < 2; i++)
  375.         for (j = 0; j < 2; j++)
  376.             optimal_inv[i][j] = pow((-1), i + j + 2) * optimal_T[1 - i][1 - j] / determinant;
  377.     k = 0;
  378.  
  379.     //подсчет оптимальных значений y1 и y2
  380.     for (j = 0; j < 4; j++)
  381.     {
  382.         //перемножение полученной матрицы с коэффициентами исходной функции
  383.         if (basis[j] != 0 && k != 0)
  384.         {
  385.             optimal_inv[0][0] = func_coef[j] * optimal_inv[0][0];
  386.             optimal_inv[0][1] = func_coef[j] * optimal_inv[0][1];
  387.             k++;
  388.         }
  389.         if (basis[j] != 0 && k == 0)
  390.         {
  391.             optimal_inv[1][0] = func_coef[j] * optimal_inv[1][0];
  392.             optimal_inv[1][1] = func_coef[j] * optimal_inv[1][1];
  393.             k++;
  394.         }
  395.     }
  396.  
  397.     y1 = optimal_inv[0][0] + optimal_inv[1][0];
  398.     y2 = optimal_inv[0][1] + optimal_inv[1][1];
  399.     cout << "Для двойственной функции" << endl;
  400.     cout << "y1 = " << y1 << endl;
  401.     cout << "y2 = " << y2 << endl;
  402.     cout << "Ее значение  fдв. = " << duality_func_coef[0] * y1 + duality_func_coef[1] * y2 << endl;
  403.     cout << "Результаты в точности совпали." << endl;
  404. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement