Алгоритмическое и программное обеспечение для задачи выбора комплектов оборудования

• Автор: Гончаров, Евгений Николаевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Новосибирск
• Количество страниц: 132 с. : ил

Оглавление
Введение

1 Задача выбора комплектов оборудования и ее связь с задачей размещения

1.1 Содержательная постановка задачи

1.2 Математическая постановка задачи.

1.3 Обзор задач, обобщающих простейшую задачу размещения

1.3.1 Модель размещения производства с двухэтапной обработкой продукции

1.3.2 Задача размещения предприятий и складов

1.3.3 Двухэшелонная задача размещения.

1.3.4 Задачи минимизации полиномов от булевых переменных и выбора множества строк.

1.3.5 Двухуровневая задача стандартизации.

2 Точные алгоритмы
2.1 Общие характеристики метода ветвей и границ
2.2 Квазитупиковый алгоритм нахождения нижней оценки для
целевой функции.
2.2.1 Об алгоритме нахождения нижних оценок задачи
в общем случае
2.2.2 Алгоритм вычисления верхней оценки
2.2.3 Результаты тестовых расчетов .
2.3 Нижняя оценка для значений полинома от булевых переменных .
2.3.1 Алгоритм построения приближенного решения задачи минимизации полинома от булевых переменных
2.3.2 Результаты вычислительных экспериментов
3 Вероятностные жадные алгоритмы
3.1 Вероятностные жадные алгоритмы.
3.2 Алгоритм Лидер группы.
3.3 Условия дополняющей нежесткости
3.4 Алгоритм Случайный аутсайдер
3.5 Принцип ветвления
4 Вероятностные алгоритмы поиска с запретами
4.1 Вероятностный алгоритм поиска с запретами
4.2 Цепи Маркова
4.3 Варианты вероятностного алгоритма поиска с запретами .
4.4 Вычислительные эксперименты
Заключение
Литература


В. Шамардиным |] изучалась двухуровневая задача стандартизации в следующей постановке. Пусть I = {1,. J = {1,. X — множество всех векторов х Ф 0 с компонентами 0 и 1; уу — переменная выбора потребителем у изделия г (Уц ? У{х) — множество возможных вариантов у потребительского выбора. У] ~ 1 > Уху ^ ^ Ь 4 ? В принятых обозначениях двухуровневая модель выбора номенклатуры изделий имеет следующий вид. В [] была установлена эквивалентность задачи выбора комплектов оборудования и двухуровневой задачи стандартизации. Эта обобщающая задача и есть задача (1)-(5). Особенности приведенных выше моделей не являются существенными в смысле общей сложности задач, и представленные в данной диссертации методы решения могут быть применены к ним после соответствующей модификации. Вторая глава посвящена построению и исследованию точных алгоритмов решения задачи выбора комплектов оборудования. Эта задача принадлежит к классу труднорешаемых задач [], и потому маловероятно, что удастся найти эффективный алгоритм ее решения. В данной диссертации для точного решения задачи выбора комплектов оборудования применяется метод ветвей и границ []. В разделе 2. Большое значение для успешности работы метода ветвей и границ имеет эффективность вычисления нижней оценки для целевой функции. В разделе 2. С этой целью рассматривается релак-сированная задача, получаемая заменой условия булевости переменных задачи на условие их неотрицательности. Для нахождения нижней оценки рассматривается двойственная ей задача и ищется ее приближенное решение, основанное на построении так называемого квазитупикового решения двойственной задачи. Показывается, что временная сложность этого алгоритма равна 0(ILJ(L -f logl)). В разделе 2. Однако, в этом случае для определенной части изделий множество комплектов, в которое они входят, является одноточечным. Эта специфика данной задачи является существенной и может быть использована при нахождении нижней границы. В разделе 2. При построении этого алгоритма используется жадный алгоритм с временной сложностью 0(ЛЪ). В разделе 2. Приводятся также результаты вычислительных экспериментов, позволяющие судить о качестве метода ветвей и границ, использующего рассмотренные алгоритмы вычисления нижней оценки целевой функции. В разделе 2. Алгоритм состоит в построении матрицы, аналогичной но свойствам тупиковой матрице в так называемой процедуре подъема [7], [] и названной в силу этого также тупиковой. Предлагается, кроме того, алгоритм нахождения приближенного решения задачи, основанный на использовании свойств тупиковой матрицы. В [] и [] приведено определение тупиковой матрицы и подробное описание алгоритма ее построения. Обобщенное определение тупиковой матрицы и описание общей схемы ее построения в случае задачи выбора множества строк даны в [7]. С помощью вычислительных экспериментов исследуется точность нижних оценок, получаемых при использовании различных правил построения тупиковой матрицы. Рассматриваемый в настоящей диссертации обобщенный алгоритм принципиально не отличается от алгоритмов из [7], [], []. Тем не менее внесенные в нее изменения оказываются существенными для получаемой нижней оценки значений целевых функций рассматриваемых задач. Об этом свидетельствуют, в частности, приводимые в заключительной части работы результаты численных экспериментов. Из этих результатов видно, что значения нижних оценок превышают те значения, что приведены в [] для аналогичных классов задач. Вместе с тем значения нижних оценок относительно оптимального решения двойственной задачи существенно выше и находятся в пределах -% от него. Это означает, что получаемая с помощью обобщенной процедуры подъема тупиковая матрица близка к оптимальному решению двойственной задачи, а значительный разрыв между нижней оценкой и оптимальным значением целевой функции связан не с качеством получаемой тупиковой матрицы, а с соответствующим разрывом двойственности у задач рассматриваемого класса. Третья и четвертая главы диссертации посвящены построению и исследованию приближенных эвристических алгоритмов для задачи выбора комплектов оборудования.