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

• Автор: Щербина, Олег Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1979
• Место защиты: Москва
• Количество страниц: 127 с. : ил.

СОДЕРЖАНИЕ
Введение

Глава I. Локальные алгоритмы решения квазиблочных задач дискретного программирования.
§1. Основные определения
§2. Прикладные квазиблочные задачи
§3. Локальный алгоритм как частная реализация метода
последовательного анализа вариантов
§%. Связь локального алгоритма с постоптимальным анализом
в дискретном программировании
§5. Эффективная реализация и структурная оптимизация
локального алгоритма
Глава П.Исследование эффективности локального алгоритма .
§1. Сравнение оценок эффективности при решении задач дискретного программирования с помощью локального
алгоритма
§2. Оценка эффективности локального алгоритма при использовании постоптимального анализа
§3. Оценки эффективности локального алгоритма ..
§4. Исследование эффективности локального алгоритма с помощью машинного эксперимента
Глава Ш. Исследование свойств квазиблочных матриц.
§1. Необходимое условие к -квазиблочности матрицы и
оценка числа всевозможных к -квазиблочных матриц....69 §2. Оценка максимального числа слабо связанных блоков для
данной матрицы

§3. Оценки числа всевозможных разбиений данной матрицы
на слабо связанные блоки
§4. Оценка числа всевозможных разбиений матрицы инциден-
ций задачи оптимального оезервирования на блоки
§5. Задача оптимального разбиения матрицы инциденций задачи оптимального резервирования на слабо связанные блоки
3 а кл в ч е н и е
Литература
ПРИЛОЇЕНИЕ

ВВЕДЕНИЕ
В настоящее время весьма актуальной является задача разработки методов решения задач дискретного программирования большой размерности, которые появляются во многих приложениях исследования операций [I] . К настоящему времени разработано немало перспективных алгоритмов в дискретном программировании [2-28] , однако большие размеры задач - камень преткновения для них: "Достижения в применении, вычислительных аспектах и теории целочисленного программирования значительны..., однако размеры задачи остаются главным ограничением" [29^ .
В связи с этим возникает проблема разработки методов декомпозиции в целочисленном программировании, т.е. сведения решения исходной задачи целочисленного программирования к решению ряда задач меньших размеров, которые уже могут быть решены с помощью известных алгоритмов.
Метод декомпозиции впервые был использован для решения задач смешанного целочисленного программирования в £зоД , впоследствие этот метод подвергся модификации в работе [31] , другие алгоритмы декомпозиции для решения задач специальной структуры предложены в работах £32 - 3^ .
Аддитивный алгоритм Балаша £35,363 модифицирован авторами работы [37] для решения задачи целочисленного программирования, имеющей следующий вид:
£ == С ЭС. —» пьиг.
при ограничениях

т.е. существует допустимое решение
с большим значением ЦФ всей задачи (1.4)-(1.б), чем значение ЦФ для предполагавшегося оптимальным решения (Х'.Д ХЛ)-
Противоречие. Таким образом, если решить задачу ДП С1.56)—С1.58) для всевозможных наборов то, по крайней мере, для одного
из наборов ^s■fz оптимальное решение (если оно су-
ществует) войдет в оптимальное решение задачи (ІЛ)-(і.б). Если же задача (1.56)-(1.58) ни для одного набора решений не
имеет, то не имеет решения и вся задача (ІЛ)-(І.б). На первом шаге отсеиваются все неперспективные варианты, для которых - не оптимальное решение задачи (1.56)-(1.58) при фиксированном
Аналогично можно показать для & -го шага ЛА (УС- , что, по крайней мере, для одного из наборов оптимальное решение (если оно существует) войдет в оптимальное
решение задачи (1.4)-(1.б). Если же задача 2^ ^ не имеет решений ни для одного из наборов 7г+і, то не имеет решения и
вся задача (1.4)-(1.б). Так отсеиваются все неконкурентноспособные варианты на 'Ъ -м шаге.
Все эти рассуждения проводились в предположении, что вектор-перемычка 3C.fi известен. На самом деле этот вектор - искомый (имеется в виду вектор, соответствующий оптимальному решению). Однако таких векторов конечное число

можно их все перебрать и найти для каждого из них оптимальное решение XI ъ задачи 2 •