Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

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

Автор:   •  Февраль 26, 2020  •  Реферат  •  777 Слов (4 Страниц)  •  475 Просмотры

Страница 1 из 4

Задание на выпускную квалификационную работу (диссертацию) магистратуры ИВТ по профилю АСУ на 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 на каждой итерации.  Найти аналитические зависимости верхней границы времени поиска решения методом динамического программирования от размерности задачи о ранце.  

...

Скачать:   txt (9.3 Kb)   pdf (186.3 Kb)   docx (151 Kb)  
Продолжить читать еще 3 страниц(ы) »
Доступно только на Essays.club