Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement