СОДЕРЇАНИЕ Введе ниє .........
стр
4
Глава I. Локальные алгоритмы решения квазиблочных задач дискретного программирования.
§1. Основные определения....................................... ГО
§2. Прикладные квазиблочные задачи............................. 22
§3. Локальный алгоритм как частная реализация метода
последовательного анализа вариантов.........................32
§Ф. Связь локального алгоритма с постоптимальным анализом
в дискретном программировании.............................. 36
§5. Эффективная реализация и структурная оптимизация
локального алгоритма....................................... 41
Глава П.Исследование эффективности локального алгоритма .
§1. Сравнение оценок эффективности при решении задач дискретного программирования с помощью локального
алгоритма................................................ 49
§2. Оценка эффективности локального алгоритма при использовании постоптималъного анализа......................г........ 54
§3. Оценки эффективности локального алгоритма ••••*. 50
§4. Исследование эффективности локального алгоритма с помощью машинного эксперимента............................ 66
Глава Ш. Исследование свойств квазиблочных матриц.
§1. Необходимое условие к -квазиблочности матрицы и
оценка числа всевозможных к -квазиблочных матриц....69 §2. Оценка максимального числа слабо связанных блоков для
данной матрицы............................................. 73
§3. Оценки числа всевозможных разбиений данной матрицы
на слабо связанные блоки................................. 79
§4. Оценка числа всевозможных разбиений матрицы инциден-
ций задачи оптимального оезервирования на блоки 82
§5. Задача оптимального разбиения матрицы инциденций задачи оптимального резервирования на слабо связанные блоки........................................................... 88
3 а к л ю ч е н и е ...................................... 92
1 и т е р а т у р а ........................................... 94
ПРШГОЇЕНИЕ.........................................................101
- 4 -
ВВЕДЕНИЕ
В настоящее время весьма актуальной является задача разработки методов решения задач дискретного программирования большой размерности, которые появляются во многих приложениях исследования операций [I] . К настоящему времени разработано немало перспективных алгоритмов в дискретном программировании [2-28^ , однако большие размеры задач - камень преткновения для них: ’’Достижения в применении, вычислительных аспектах и теории целочисленного программирования значительны..., однако размеры задачи остаются главным ограничением" [29^ .
В связи с этим возникает проблема разработки методов декомпозиции в целочисленном программировании, т.е. сведения решения исходной задачи целочисленного программирования к решению ряда задач меньших размеров, которые уже могут быть решены с помощью известных алгоритмов.
Метод декомпозиции впервые был использован для решения задач смешанного целочисленного программирования в , впоследствие
мы декомпозиции для решения задач специальной структуры предложены в работах £32 - 34^ .
Аддитивный алгоритм Балаша £35,36] модифицирован авторами ра-
этот метод подвергся модификации в работе
другие алгорит-
решения задачи целочисленного программирования,
имеющей следующий вид:
при ограничениях
- 5 -
где матрица /I имеет блочную структуру.
В [зв] построена динамическая модель развития отрасли пластмасс, имеющая блочную структуру.
Среди задач дискретного программирования, возникающих на практике, достаточно много задач с разреженными матрицами условий [39] , которые поддаются разбиению на слабо связанные блоки Ст.е. имеют квазиблочную структуру). Для решения подобных задач может быть использован локальный алгоритм. Отметим, что алгоритм декомпозиции задач линейного программирования с квазиблочной структурой предложен в [Ю] .
Первоначально локальные алгоритмы были введены и исследованы для решения задач дискретного анализа [41 - 44] . Идея локальных алгоритмов состоит в следующем. Пусть нужно решить задачу выбора из элементов данного конечного множества элементов с определенными свойствами (например, из множества допустимых решений задачи дискретного программирования нужно выбрать оптимальные решения) . В данном множестве вводится понятие близости, на его основе определяется окрестность элемента (множество элементов, близких к этому элементу). Локальный алгоритм на каждом шаге изучает окрестности элементов (а не все элементы множества) и накапливает о них информацию, которая затем используется на последующих шагах алгоритма.
Впервые локальный алгоритм применен к задачам булевского линейного программирования в [45] ♦ В [46, 47] локальный алгоритм модифицирован для решения квазиблочных задач с дополнительными ограничениями. Исследованию локальных алгоритмов посвящены также работы [48,49] . Отметим, что эффективность локального алгоритма, вопросы его конкретной реализации, свойства квазиблочных матриц совершенно не были исследованы.
Перейдем к постановке задаче. Рассматривается локальный алго-
(*)
- б -
ритм в сочетании с алгоритмом дискретного программирова-
ния, имеющим оценку эффективности у(п), для решения /с -квази-блочной задачи 2^, дискретного программирования с гъ булевскими переменными. Локальный алгоритм сводит решение задачи Г к решению к пакетов задач 4 У»* . /7 /. Задачи
/ -у (£)? ” ^ ^
УГ г } каждого пакета можно упорядочить Сструктуризовать) и решать их согласно этому упорядочению, используя при решении задач информацию, полученную в процессе решения задач предшествующих. Возникают следующие задачи: I. Задача структурной оптимизации локального алгоритма (УСу ; 2. Сравнить ¥(п) и (п>^)~ оценку эффективности локального алгоритма (УС у ; 3. Найти
Ему(п' к1 Еосу(ъ *), (^уМ^где Л
матрица условий линейной задачи 2 ; 4. Найти оценки для
Ш71 , где К д - множество всех разбиений на к слабо
связанных блоков матрицы Д ; 5. Оценить к(А) - число слабо связанных блоков, на которые можно разбить Д ; 6. Найти к ,
^б/^дтакие, что (^1, к )=1п£ПгС (п.,кК нахождение опти-
. ^ «с/?«'
мального разбиения).
Итак, изложим основные цели работы:
1. Структурная оптимизация локальных алгоритмов на классе квазиблочных задач дискретного программирования.
2. Исследование эффективности локальных алгоритмов на классе квазиблочных задач дискретного программирования (оценки эффективности определяются согласно [50 - 52^).
3. Выяснение влияния характеристик квазиблочных задач на эффективность их решения и исследование комбинаторных свойств квазиблочных матриц.
4. Машинная реализация локальных алгоритмов и анализ их реальных вычислительных возможностей.
Перейдем к изложению структуры работы.
- 7 -
В главе I рассматриваются вопросы эффективной реализации локальных алгоритмов решения квазиблочных задач дискретного программирования. В §1 даются основные определения, необходимые для дальнейших рассмотрений: излагается локальный алгоритм, дается определение квазиблочных матриц, приводится алгоритм разбиения на слабо связанные блоки произвольной матрицы, описывается метод неявного перебора , даются определения оценок эффективности алгоритмов. В §2 выделен класс прикладных задач с квазиблочной структурой - класс задач оптимального резервирования ресурса, распределенного во времени, частными случаями которых является задача оптимального предварительного резервирования гостиничных номеров, задача оптимального резервирования ресурсов на турбазах, задача оптимальной аренды складских помещений £53,54] , задача оптимального выбора научно-исследовательских проектов [55] , задача оптимального планирования электроснабжения при аварии, задача оптимальной госпитализации больных и др. В §3 показывается, что локальный алгоритм является частной реализацией общей схемы последовательного анализа вариантов [56,57] . В §4 вскрывается связь локального алгоритма с постоптимальным анализом в дискретном программировании [58 - 68] , показывается, что эффективность локального алгоритма будет тем выше, чем выше эффективность процедуры постоптимального анализа, используемой в сочетании с локальным алгоритмом. В §5 связь между локальным алгоритмом и постоптимальным анализом используется при эффективной реализации и структурной оптимизации локального алгоритма. Здесь рассматриваются различные варианты организации вычислительного процесса. В частном случае, когда каждый блок задачи содержит по одному ограничению, постоптимальный анализ реализуется совсем просто, т.к. задачи внутри блоков представляют собой задачи о ранце, для решения которых используется метод динамического программирования.
- 8 -
Глава П посвящена исследованию эффективности локального алгоритма решения квазиблочных задач дискретного программирования.
В §1 сравниваются оценки эффективности локального алгоритма при решении задач булевского линейного программирования в следующих двух случаях: I) когда задачи внутри блоков решаются с помощью полного перебора. В этом случае показывается, что локальный алгоритм в сочетании с полным перебором эффективнее полного перебора; 2) когда задачи внутри блоков решаются с помощью неявного перебора. Здесь показывается, что при достаточно небольшой перемычке между блоками локальный алгоритм в сочетании с неявным перебором эффективнее неявного перебора. В §2 находится оценка эффективности постоптимального анализа при решении пакета задач булевского линейного программирования методом неявного перебора и на основе этой оценки находится оценка эффективности локального алгоритма в сочетании с постоптимальным анализом для неявного перебора. В §3 исследуются оценки эффективности локального алгоритма в сочетании с полным перебором: найдены экстремальные значения оценок эффективности и среднее значение оценки эффективности локального алгоритма на классе квазиблочных задач дискретного программирования. В §4 исследуется эффективность локального алгоритма с помощью машинного эксперимента для класса задач оптимального резервирования. Данные задач порождаются с помощью генератора случайных чисел. Машинный эксперимент показывает, что локальный алгоритм эффективен при достаточно небольших перемычках, связывающих блоки.
В главе Ш исследуется ряд свойств квазиблочных матриц. В §1 выводится необходимое условие разбиваемости матрицы на |< слабо связанных блоков.Попутно находятся максимальное и минимальное число элементов внутри блоков. На основе этих оценок находится оценка числа всевозможных булевских |< -квазиблочных матриц.
- 9 -
Минимальное и максимальное число слабо связанных блоков, на которые можно разбить данную матрицу, находятся в §2. Для характеристики разреженности матрицы вводятся такие параметры, как максимальное и минимальное число элементов в столбце, максимальное и минимальное число строк матрицы, связанных с данной строкой. Здесь же найдено достаточное условие разбиваемости матрицы на к слабо связанных блоков. В §3 оценивается число всевозможных разбиений данной матрицы на слабо связанные блоки, причем разбиения матрицы получаются из заданного разбиения матрицы, построенного с помощью алгоритма (69] , описанного в §1 главы I. В §4 дается оценка числа всевозможных разбиений матрицы инциденций задачи оптимального резервирования на слабо связанные блоки, здесь же получены оценки для минимального и максимального числа блоков в разбиении, причем в качестве параметров, характеризующих разреженность матрицы, взяты минимальная и максимальная длина заявки.
В §5 ставится и решается для матрицы инциденций задачи оптимального резервирования задача оптимального разбиения матрицы на слабо связанные блоки, причем в качестве критерия эффективности берется оценка эффективности локального алгоритма при решении полученной квазиблочной задачи. Матрице инциденций задачи оптимального резервирования ставится в соответствие некоторая сеть, причем разбиениям матрицы на слабо связанные блоки соответствуют некоторые пути в сети, так что задача оптимального разбиения на блоки сводится к задаче отыскания кратчайшего пути в эквивалентной сети.
- 10 -
ГЛАВА I. ЛОКАЛЬНЫЕ АЛГОРИТМЫ РЕШЕНИЯ КВАЗИБЛОЧНЫХ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ.
§1. Основные определения.
Рассмотрим локальные алгоритмы решения задач дискретного программирования и связанные с ними понятия. Вначале будет рассмотрена версия алгоритма, предназначенная для решения задач линейного булевского программирования, согласно с*].
Пусть дана задача целочисленного линейного программирования (ЦЛП) с булевскими переменными:
С ОС, -—*■ ех±-ъ (1.1)
ш
при ограничениях
У", оу /г = а-2) (к € {)
^11. С1.3)
Определение 1.1. Множество (ру, 2)—/^ 1 / С1у\ Ф О\ се//<} индексов переменных называется окрестностью первого порядка переменной Ху , где Цу±
Для дальнейшего нам потребуются следующие множества и, о), т
Пусть Оп-} = АГ X& =УЧ.
Определение 1.2.
5 (£) — {к I(%и 1=0; /<=
Окрестность произвольного порядка переменной Ху определим по индукции. Пусть известна окрестность Зр\р^} 2^) /5“го порядка переменной Ху . Окрестность (р + 1) “го порядка пере-
- Київ+380960830922