Разработка и анализ алгоритмов целочисленного линейного программирования с использованием L-разбиения

• Автор: Колосов, Антон Павлович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Омск
• Количество страниц: 111 с. : ил.

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

1 Некоторые методы анализа и решения задач целочисленного программирования

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

1.2 Ь разбиение и его свойства

1.3 Метод перебора Ь классов

1.4 Двойственные дробные алгоритмы отсечения .

1.5 Унимодулярные преобразования

2 Построение оценок числа итераций

2.1 Анализ алгоритмов для семейств задач

на плоскости

2.2 Оценки числа итераций алгоритмов в пмерном случае
2.3 О выборе производящей строки в первом
алгоритме Гомори
3 Исследование вопросов устойчивости алгоритмов
3.1 О неустойчивости некоторых алгоритмов отсечения.
3.2 Зависимость числа итераций первого алгоритма Гомори от целевой функции.
4 Алгоритмы перебора классов для задачи планирования производства с интервальными данными
4.1 Дискретная задача планирования производства с
интервальными данными.
4.2 Алгоритм перебора Ь классов.
4.3 Алгоритмы приближенного решения задачи
4.4 Экспериментальные исследования
Заключение
Литература


Получены экспоненциальные оценки числа итераций этих алгоритмов при решении предложенных задач, определены унимодулярпые преобразования, повышающие их эффективность. На основе одного из построенных семейств задач доказана неустойчивость первого алгоритма Гомори но релаксационному множеству. Разработаны и апробированы алгоритмы перебора Ь - классов для решения дискретной задачи планирования производства с интервальными данными. Практическая ценность. Предложенные алгоритмы перебора Ь - классов для решения дискретной задачи планирования производства в стандартной и интервальной постановках применимы в случае задач достаточно большой размерности. Результаты работы нашли применение в лаборатории дискретной оптимизации ОФ ИМ СО РАН при исследовании алгоритмов отсечения и перебора Ь - классов, в частности, при изучении вопросов их устойчивости. Кроме того, полученные результаты используются в учебном процессе на кафедре прикладной и вычислительной математики ОмГУ нм. Ф. М. Достоевского при подготовке специалистов по методам оптимизации и исследованию операций. Апробация работы. Результаты диссертации докладывались на XXIX Региональной научной студенческой конференции ОмГУ «Молодежь третьего тысячелетия» (Омск, ), III Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, ), XIII Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, ), IV Всероссийской научной молодежной конференции «Под знаком Сигма» (Омск, ), Российской конференции «Дискретная оптимизация и исследование операций» (Владивосток, ), VI Международной научно-технической конференции «Динамика систем, механизмов и машин» (Омск, ), XIV Байкальской международной школе-семинаре (Иркутск-Северобайкальск, ), а также па научных семинарах в Омском филиале Института математики им. С.Л. Соболева СО РАН, Омском государственном университете им. Ф. М. Достоевского (-) и Институте вычислительной математики и математической геофизики СО РАН. Публикации. Основные результаты диссертации опубликованы в научных работах [9-,,,,], три из них - в изданиях из списка ВАК. Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы (1 наименование). Объем диссертации - 2 страниц. Вводится понятие дробного накрытия задачи, даётся определение Ь - разбиения и отмечается ряд его свойств, которые используются при исследовании задач и алгоритмов. Описаны базовый алгоритм перебора Ь - классов и лексикографический двойственный симплекс-метод (ЛДСМ) для задачи линейного программирования (ЛП), применяемый в исследуемых алгоритмах. Рассматриваются двойственные дробные алгоритмы отсечения для задачи ЦЛП. Описываются унимодулярные преобразования и их свойства, приводятся примеры известных унимодулярных преобразований. Во второй главе исследуются предложенные нами семейства' задач ЦЛП для анализа алгоритмов отсечения, перебора Ь- классов и метода ветвей и границ (схема Лэнд и Дойг). Изучаются семейства трудных задач Ал (а), #2 (а) на плоскости, требующих для своего решения экспоненциального от длины входа числа итераций и показывается, чаю их решение существенно облегчается, если предварительно использовать унимодуляр-ные преобразования. Аналогичное исследование проведено для построенных в работе семейств К*(а) и К^(а) в пространстве К". Исследована зависимость эффективности алгоритмов отсечения от правила выбора производящей строки. В третьей главе рассматриваются вопросы устойчивости для первого алгоритма отсечения Гомори. Приводятся некоторые сведения об устойчивости алгоритмов, отмечен ряд известных результатов. Описаны семейства задач ЦЛП, доказывающие неустойчивость первого алгоритма Гомори при малых изменениях релаксационного множества задачи. Показано, что применение у ни модулярного преобразования улучшает поведение алгоритма Гомори при решении задач данного семейства. Установлено, что число итераций первого алгоритма Гомори может сильно возрасти при некоторых изменениях коэффициентов целевой функции.