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

  • автор:
  • специальность ВАК РФ: 05.13.18
  • научная степень: Кандидатская
  • год, место защиты: 2001, Новосибирск
  • количество страниц: 132 с. : ил
  • автореферат: нет
  • стоимость: 240,00 руб.
  • нашли дешевле: сделаем скидку
  • формат: PDF + TXT (текстовый слой)
pdftxt

действует скидка от количества
2 диссертации по 223 руб.
3, 4 диссертации по 216 руб.
5, 6 диссертаций по 204 руб.
7 и более диссертаций по 192 руб.
Титульный лист Алгоритмическое и программное обеспечение для задачи выбора комплектов оборудования
Оглавление Алгоритмическое и программное обеспечение для задачи выбора комплектов оборудования
Содержание Алгоритмическое и программное обеспечение для задачи выбора комплектов оборудования
Вы всегда можете написать нам и мы предоставим оригиналы страниц диссертации для ознакомления
Оглавление
Введение
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], [], []. Тем не менее внесенные в нее изменения оказываются существенными для получаемой нижней оценки значений целевых функций рассматриваемых задач. Об этом свидетельствуют, в частности, приводимые в заключительной части работы результаты численных экспериментов. Из этих результатов видно, что значения нижних оценок превышают те значения, что приведены в [] для аналогичных классов задач. Вместе с тем значения нижних оценок относительно оптимального решения двойственной задачи существенно выше и находятся в пределах -% от него. Это означает, что получаемая с помощью обобщенной процедуры подъема тупиковая матрица близка к оптимальному решению двойственной задачи, а значительный разрыв между нижней оценкой и оптимальным значением целевой функции связан не с качеством получаемой тупиковой матрицы, а с соответствующим разрывом двойственности у задач рассматриваемого класса. Третья и четвертая главы диссертации посвящены построению и исследованию приближенных эвристических алгоритмов для задачи выбора комплектов оборудования.
Вы всегда можете написать нам и мы предоставим оригиналы страниц диссертации для ознакомления

Рекомендуемые диссертации данного раздела