Исследование устойчивости задач и алгоритмов целочисленного программирования на основе регулярных разбиений

• Автор: Девятерикова, Марина Владимировна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Омск
• Количество страниц: 97 с. : ил

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

Глава 1. Вопросы устойчивости в дискретной

оптимизации

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

1.2 Основные результаты по устойчивости задач дискретной оптимизации

1.3 Метод регулярных разбиений

1.4 Г-структура задач целочисленного программирования и

ее свойства
Глава 2. Исследование устойчивости задач целочисленного программирования на основе Г-разбиения

2.1 Анализ общей задачи целочисленного программирования

2.2 Оценки для целочисленного выпуклого программирования
2.3 Задачи булева программирования
2.4 Некоторые специальные задачи
Глава 3. Разработка и исследование алгоритмов перебора Г-классов
3.1 Задачи с интервальными данными
3.2 Метод перебора Г-классов
3.3 Алгоритмы перебора Г-классов для задач ЦП с интервальными данными

3.4 Приближенные алгоритмы
3.5 Результаты вычислительного эксперимента
Заключение
Список литературы

Введение
Диссертация посвящена исследованию устойчивости задач и алгоритмов целочисленного программирования (ЦП), а также разработке алгоритмов для решения задач ЦП с интервальными исходными данными. В частности, рассмотрены задачи выпуклого целочисленного и булева программирования и некоторые специальные задачи целочисленного линейного программирования.
К задачам целочисленного программирования сводятся многие задачи, возникающие в экономике, управлении, планировании и других областях [45, 55, 57, 61, 68, 71]. Условие целочисленности позволяет учесть такие факторы как неделимость объектов, наличие альтернатив, дискретность процессов и т.д.
В настоящее время в целочисленном программировании развиваются такие направления как исследование структуры и сложности решения задач, теория двойственности, устойчивость решений, многокритериальные задачи, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, множителей Лагранжа, приближенные и гибридные алгоритмы. Этим вопросам посвящены многие статьи и монографии [2-6, 20, 23, 26-28, 39, 40, 45-47, 55-57, 61, 62, 68, 69, 71, 82, 93, 94].
Значительная часть методов решения задач ЦП основана на использовании релаксационных множеств, дополнительных линейных ограничений (отсечений) и аппарата непрерывной оптимизации. Релаксационное множество задачи ЦП определяется системой ограничений, получающейся из исходной путем исключения условия целочисленности. В процессе решения задачи оно последовательно изменяется с помощью вводимых дополнительных линейных ограничений до получения

2.1. Анализ общей задачи целочисленного программирования
В этой главе мы будем рассматривать задачу целочисленного программирования в лексикографической постановке вида:
найти г* — 1ехтах{ф1^п), (2.1)
где О, - замкнутое, ограниченное множество в Вп.
Для исследования вопросов устойчивости задач ЦП нами получены новые свойства Д-структуры на основе выделения нескольких вариантов расположения Д-классов пространства В" относительно релаксационного множества задачи, при этом особую роль играют смежные Д-классы. Далее будет показано, что при достаточно малых изменениях релаксационного множества его Д-разбиение может содержать только Д-классы исходного множества и смежные к исходному релаксационному множеству Д-классы. В связи с этим возникает вопрос о количестве смежных к О Д-классов. В теоремах 2.1-2.2 получены верхние оценки числа смежных к релаксационному множеству задачи (2.1) Д-классов.
Теорема 2.1 Пусть О - замкнутое, ограниченное множество в Вп, для которого существует г* = 1ехтах (О П Zn) и П* = 0. Тогда число смежных с П Ь-классов V таких, что V У г* , равно п.
Доказательство. Рассмотрим следующие Д-классы 14:
14 = {ж £ Вп : хх = = гк_х,г*к < хк < гк + 1 },к = 1 ,...,п.
Нетрудно проверить, что любой Д-класс 14 является смежным с О и 14 >- г*. Покажем, что других Д-классов, удовлетворяющих этим условиям, нет. Предположим противное, т.е. найдется смежный с П класс V , V' у г*,У' ф 14, к = 1,...,п. Тогда существует номер д £ {1,...,п} такой, что V’ С {ж £ Ип : х = ...,жд_1 = > г* + 1}. Так как
V' - смежный с О, то р(П, V') = 0. Поскольку О - замкнутое, ограниченное множество, то существует точка у £ П, для которой р(у,У') = 0.