- simplex_method.c - алгоритм написанный на базе статьи из репозитория. На данный момент выдает некорректные результаты
- simplex.py - модифицированная реализация на языке программирования Python. Является эталоном. Параллельна(можно переносить на С)
- problem_generator - алгоритм генерации "правильных" случайных симплекс таблиц
- папка babazka_version - содержит алгоритм, который не только работает, но еще и возвращает правильные результаты
В данном репозитории находится версия симплекс метода, написанная с использованием MPI. Текущая реализация не является оптимальной и причина тому не очень правильно составленная перессылка данных. Изображение отображает временные затраты, на некоторые участки кода, из которых видно, что наибольшее количество времени тратиться на инициализацию данных и конечный сбор результатов.
Данный косяк можно обойте распаралелив и рассылку. К примеру, в случае с 12 процессами, мастер рассылает по трети данных: себе, четвертому и восьмому процессу. После получения, каждый из них, рассылает данные находящимся выше них(по нумерации) трем процессам. Аналогично и при получение, не все данные тут же шлются мастеру, а схлопываются по чуть-чуть.
Также для ускорения можно воспользоваться MPI структурами.
Генерация исходных данных происходит по хитрому алгоритму, который обеспечивает большое количество итераций при решении симплекс метода. Алгоритм вроде бы построен для размещения точек в пространстве многогранника, расположенного в многомерном пространстве так, чтобы область не была близка к нулевым значениям.