Сеточный следящий алгоритм решения задачи линейного программирования

Цель работы
Изучить сеточный следящий алгоритм решения задач линейного программирования.
Изучить теорию фейеровских отображений.
Выполнить программную реализацию сеточного следящего алгоритма.
Протестировать работу алгоритма на модельных примерах.

Постановка задачи

Фейеровское отображение

Фейеровский процесс

Псевдопроектирование
проектирование
псевдопроектирование

Идея алгоритма

Поведение при непустом пересечении

Поведение при пустом пересечении

Шаги алгоритма

Программная реализация
Написана программа «SSA» на языке программирования C++, реализующая сеточный следящий алгоритм решения задачи линейного программирования.
Модуль 1: строит кубическую область в виде сетки длинной ребра r предварительно покрывающую область многогранника M.
Модуль 2: находит псевдопроекцию из точки z на пересечение ячейки с многогранником М.
Модуль 3: проводит сравнение полученных данных и сдвигает центр сеточной области в центр ячейки с максимумом целевой функции.

Модельный пример

Тестирование алгоритма
K – параметр алгоритма, первоначальное число ячеек сеточной области.
Время

Результаты эксперимента
Изучен сеточный следящий алгоритм для решения задач линейного программирования на базе фейеровских отображений.
Написана программная реализация алгоритма на языке С++.
Проведен вычислительный эксперимент по тестированию программной реализации на модельном примере и подбору параметра алгоритма K.