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

• Автор: Заозерская, Лидия Анатольевна
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Омск
• Количество страниц: 124 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. АНАЛИЗ Е-СТРУКТУРЫ ЗАДАЧ О ПОКРЫТИИ И УПАКОВКЕ МНОЖЕСТВА
1.1. Метод регулярных разбиений и алгоритмы отсечения
1.1.1. Предварительные сведения
1.1.2. Задача о покрытии
1.2. Семейство задач о покрытии Балаша
1.3. Блочно-диагональные задачи о покрытии
1.4. Задача об упаковке
ГЛАВА 2. АЛГОРИТМЫ ПЕРЕБОРА Е-КЛАССОВ И ОТСЕЧЕНИЯ
2.1. Алгоритм перебора Е-классов для решения задачи
о покрытии
2.1.1. Базовый алгоритм
2.1.2. Алгоритм перебора Е-классов с тестированием
2.1.3. Алгоритм перебора Е-классов с групповым анализом задач
2.1.4. Некоторые свойства алгоритма перебора Е-классов
и задачи о покрытии
2.2. Прямые алгоритмы отсечения
2.3. Оценки числа итераций и контрпримеры
для прямых алгоритмов отсечения
2.4. Об Е-структуре задач из многопараметрического семейства
2.5. Программное обеспечение и вычислительный эксперимент

2.5.1. Результаты эксперимента для алгоритма перебора Г-классов
2.5.2. Экспериментальное исследование прямых
алгоритмов отсечения
ГЛАВА 3. РЕГУЛЯРНЫЕ СИСТЕМЫ НЕРАВЕНСТВ
3.1. Индекс регулярного разбиения
3.2. Кубические разбиения и их связь с Ь-разбиениями
3.3. Классификация кубических разбиений
3.4. О регулярности некоторых классов отсечений
3.4.1. Отсечения 1-го алгоритма Гомори
3.4.2. Вполне регулярные отсечения
3.4.3. Отсечения конечного прямого алгоритма
3.4.4. Отсечения г-алгоритма
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

Введение
Диссертация посвящена исследованию задач целочисленного программирования (ЦП) и разработке алгоритмов их решения. К моделям ЦП сводятся многие прикладные задачи, возникающие в экономике, управлении, проектировании и других областях. Условие целочисленности позволяет учесть такие факторы, как неделимость продукции, дискретность процессов, наличие альтернатив, фиксированные доплаты и т.п.
В настоящее время целочисленное программирование представляет собой одно из активно развивающихся направлений дискретной оптимизации. Современная проблематика ЦП охватывает такие вопросы как структура и сложность решения задач, теория двойственности, устойчивость решений, многокритериальные задачи, полиэдральный подход, методы отсечения, ветвей и границ, декомпозиции, множителей Лагранжа, приближенные и гибридные алгоритмы, программное обеспечение, экспериментальные исследования и др. [1,5,7,9,12,17,32,39-47,53-55,57,58,60,62,63,68,69,77,78,80,84,92].
Значительная часть методов решения задач ЦП основана на сведении исходной задачи ЦП к последовательности более ’’легких” задач непрерывной оптимизации. К таким методам относятся методы отсечения, ветвей и границ (типа метода Лэнд и Дойг [40,46]), декомпозиции (с отсечениями Вендерса [35,75,86]), алгоритмы перебора Ь-классов [32] и некоторые другие. Характерными особенностями этих методов являются использование релаксационных множеств, дополнительных линейных ограничений (отсечений) и аппарата непрерывной оптимизации.
Метод отсечения, один из общих подходов к решению задач как непрерывной, так и дискретной оптимизации, получил свое развитие в работах многих авторов, в том числе в [2,21,40,59,60,66,77,80-82,85, 94]. Отличительной чертой метода является генерация и использова-
Л(3);
1 -Чк+2 -хы+1 -з&+з -Х4 -хь -ж6 .. 1 Н со ?5~ 1 ю ~хЪк- ~хЪк
3 2 1 2 1 2 1 2 -1 -1 -1
1 1 1 1
2 2 2 2
1. 1 1 1
2 2 2 2
1 2 1 2 1 2 1 2 0
0 -1 0 0
0 0 -1 0
0 0 0 -1

0 0 -1 0
1 -1 0 0
0 0 0 -1 0
-1 -1 -1 0
-1 -1 0 -1
-1 0 -1 -1
-1 0

Итак, симплексная таблица после решения соответствующей непрерывной задачи имеет вид: