Сравнительный анализ эффективности «классической» версии динамического программирования при поиске глобально оптимального решения зад

Задание на выпускную квалификационную работу (диссертацию) магистратуры ИВТ по профилю АСУ на 2018/2020 гг.

1. Название и содержательная постановка задачи.

1.1. Название: Сравнительный анализ эффективности «классической» версии динамического программирования при поиске глобально оптимального решения задачи о ранце, и его композитной версии, использующей для вычисления верхних оценок целевой функции технологию линейного программирования и переиндексацию переменных в порядке убывания отношения Сi/ai.

1.2. Исходные данные:

Применительно к задаче о ранце – 4 типа исходных данных:

• коэффициенты целевой функции (стоимость предметов, укладываемых в ранец);
• коэффициенты ограничения (объем предметов, укладываемых в ранец);
• объем ранца;
• булевы переменные.

       Применительно к алгоритму, реализующему динамическое программирование применительно к задаче о ранце:

• дерево поиска;
• куст дерева поиска, высота которого определяет число одновременно вводимых в базис переменных;
• используемые методы вычисления оценок;
• используемые методы отсечения бесперспективных векторов переменных;
• время поиска решения.

1. Формальная постановка задачи

1. Обозначения.

Применительно к задаче о ранце:

Сi -  i - й коэффициент целевой функции;

ai -  i - й коэффициент ограничения;

b - объем ранца;

          zi  - i-я булева переменная.

       Применительно к алгоритму, реализующему фронтальный спуск по дереву ветвлений:

     G(X, U) - дерево поиска;

G’ (X’, U’) -   куст дерева поиска, высота h которого определяет число 2h одновременно вводимых в базис переменных;

T - время поиска решения.

1. Формальная постановка задачи

1. Формальная постановка задачи о ранце

           [pic 1]

1. Вычисление нижней оценки величины F частичного плана

[pic 2]

1. Вычисление упрощенной верхней оценки величины F частичного плана

Верхняя оценка величины F при условии, что в базис введено подмножество Z’ϵ Z переменных ниже определяется выражением:

[pic 3]

где I(Z’) обозначает множество индексов введенных в базис булевых переменных; I(Z) – множество индексов всех булевых переменных решаемой задачи.

1. Вычисление уточнённой верхней оценки величины F частичного плана

[pic 4]

[pic 5]

1. Аналитическая зависимость времени поиска решения  от размерности задачи о ранце

Время решения в этом случае определяется двумя факторами – затратами времени на вычисление оценок t1 и на их сравнение t2 на каждой итерации.  Найти аналитические зависимости верхней границы времени поиска решения методом динамического программирования от размерности задачи о ранце.