Содержание к диссертации
Введение
Глава І. Локальные алгоритмы решения квазиблочных задач дискретного программирования .
1. Основные определения
2. Прикладные квазиблочные задачи 22
3. Локальный алгоритм как частная реализация метода последовательного анализа вариантов 32
4. Связь локального алгоритма с постоптимальным анализом в дискретном программировании 36
5. Эффективная реализация и структурная оптимизация локального алгоритма 41
Глава II. Исследование эффективности локального алгоритма .
1. Сравнение оценок эффективности юи решении задач дискретного программирования с помощью локального алгоритма 49
2. Оценка эффективности локального алгоритма при использовании постоптимального анализа 54
3. Оценки эффективности локального алгоритма 58
4. Исследование эффективности локального алгоритма с помощью машинного эксперимента
Глава III. Исследование свойств квазиблочных матриц .
1. Необходимое условие К -квазиблочности матрицы и оценка числа всевозможных к -квазиблочных матриц ...69
2. Оценка максимального числа слабо связанных блоков для данной матрицы 73
3. Оценки числа всевозможных разбиений данной матрицы на слабо связанные блоки 79
4. Оценка числа всевозможных разбиений матрицы инциденций задачи оптимального оезервирования на блоки 82
5. Задача оптимального разбиения матрицы инциденций задачи оптимального резервирования на слабо связанные блоки 88
3аключение 92
Литература 94
- Локальный алгоритм как частная реализация метода последовательного анализа вариантов
- Оценка эффективности локального алгоритма при использовании постоптимального анализа
- Необходимое условие К -квазиблочности матрицы и оценка числа всевозможных к -квазиблочных матриц
- Оценка числа всевозможных разбиений матрицы инциденций задачи оптимального оезервирования на блоки
Введение к работе
АКТУАЛЬНОСТЬ ПРОБЛЕМЫ. В настоящее время разработано немало перспективных алгоритмов дискретного программирования, однако размеры задач остаются главным ограничением. В связи с этим возникает проблема разработки методов декомпозиции в целочисленном программировании, т.е. сведения решения исходной задачи к решению ряда задач меньших размеров, которые уже могут быть решены известными методами.
Метод декомпозиции впервые был использован для решения задач смешанного целочисленного программирования в [ij .впоследствие этот метод подвергся модификации в работе [2 J Другие алгоритмы декомпозиции для решения задач дискретного программирования специальной структуры были предложены в работах [з - 7J
Среди задач дискретного программирования, возникающих на практике, достаточно много задач с разреженными матрицами условий, которые поддаются разбиению на слабо связанные блоки (или, другими словами, имеют квазиблочную структуру). Для решения -подобных задач может быть использован локальный алгоритм ц8 - I0J имеющий декомпозиционный характер. Первоначально локальные алгоритмы были введены и исследованы в дискретном анализе для построения минимальных нормальных форм алгебры логики [8J Впервые применение локального алгоритма к задачам булевского линейного программирования с целыми коэффициентами дано в \9] Локальный алгоритм для решения квазиблочных задач дискретного программирования с дополнительными ограничениями обобщен в Qo]. Мажорантный локальный алгоритм для решения задач целочисленного программирования специального вида найден в Jll] Алгоритм декомпозиции квазиблочной задачи линейного программирования получен в [і 2 J
Несмотря на то, что среди прикладных задач дискретного программирования достаточно много задач с кваэиблочной структурой, локальный алгоритм с момента его распространения на задачи дискретного программирования до настоящего времени оставался алгоритмом теоретическим, т.к. он не был реализован на ЭВМ, не исследовалась его эффективность (теоретически и экспериментально) при решении различных классов задач дискретного программирования, кроме того, локальный алгоритм ни разу не был использован для решения конкретных прикладных задач. Тесно связанный с локальным алгоритмом класс квазиблочных матриц также совершенно не был исследован.
В диссертации рассматриваются следующие задачи. Исследуется локальный алгоритм в сочетании с алгоритмом дискретного программирования, имеющим оценку эффективности ф(я) l3j для решения к —кваэиблочной задачи 2 дискретного программирования с И- булевскими переменными. Локальный алгоритм
ОС,
сводит решение задачи 2L. к решению к пакетов задач \ J* ± jV-J , \^ К }=< Задачи i2t/ каждого пакета можно упорядочить (структуризовать) и решать их согласно этому упорядочению, используя при решении задач информацию, полученную в процессе решения предшествующих задач. Возникают следующие задачи:
-
Задача структурной оптимизации локального алгоритма
-
Сравнить У(л) и СліАн.,к} - оценку эффективности локального алгоритма ОЪи>
.где А - матрица условий линейной задачи 2
-
Оценить [К.д | , где К д - множество всех разбиений матрицы А на к слабо связанных блоков;
-
Оценить - число слабо связанных блоков, на которые можно разбить А ;
6. Найти к* R*eRCf> тагае, чтоЛд^Л^
(нахождение оптимального разбиения). */t
ЦЕЛЬЮ РАБОТЫ является:
-
Структурная оптимизация локальных алгоритмов решения квазиблочных задач дискретного программирования.
-
Исследование эффективности локальных алгоритмов на классе квазиблочных задач дискретного программирования.
-
Выяснение влияния характеристик квазиблочных задач на эффективность их решения и исследование комбинаторных свойств квазиблочных матриц.
-
Машинная реализация локальных алгоритмов и анализ их реальных вычислительных возможностей.
НАУЧНАЯ НОВИЗНА. В диссертационной работе впервые исследована эффективность локального алгоритма на классе квазиблочных задач дискретного программирования, причем выполнено теоретическое и экспериментальное исследование. В работе получена оценка эффективности постоптимального анализа, ранее неизвестная. Получен ряд новых результатов для квазиблочных матриц. Выявлена связь между локальным алгоритмом и постоптимальным анализом и с учетом этой связи проанализированы возможности структурной оптимизации локального алгоритма. Реализованы на ЭВМ 3 модификации локального алгоритма.
ПРАКТИЧЕСКАЯ ЦЕННОСТЬ. Результаты, полученные в диссертационной работе, могут быть использованы при решении возникавших на практике квазиблочных задач дискретного программирования большой размерности, в частности, для решения задач оптимального резервирования гостиничных номеров, задач оптимального управления системой туризма, задач оптимальной госпитализации больных и т.п.
АПРОБАЦИЯ РАБОТЫ. Основные результаты диссертационной работы докладывались на П Всесоюзной конференции по исследование опера-
- б -
ций (г.Петрозаводск, 1976 г.), на заседании семинара "Теория оптимальных решений" под руководством академика АН УССР В.С.Ми-халевича (г.Киев, 1976 г.), на заседании семинара "Применение математических методов в экономических исследованиях и планировании" под руководством члена-корреспондента АН УССР А.А.Бакаева и доктора физ.-мат. наук Ь.З.Шора (г.Киев, 1977 г.), на ІУ, У, УП научных конференциях профессорско-преподавательского состава Симферопольского гооуииверситета (г.Симферополь, 1975, 1976, 1978 гг.) на заседании УШ цикла семинаров по дискретной математике под руководством профессора А.А.Зыкова (г.Одесса, 1978 г.), на П школе-семинаре "Проблемы автоматизации проектирования и управления качеством продукции" (г.Симферополь, 1978 г.), на семинаре лаборатории проблем распознавания ВЦ АН СССР (г.Москва, 1978 г.), на семинаре по многозначным логикам мехмата МГУ і,г.Москва, 1978 г.), а также на заседаниях семинара кафедры прикладной математики Симферопольского госуниверситета (197і» - 1978 гг.).
ПУБЛИКАЦИИ. По материалам диссертации опубликовано 5 печатных работ [i к - 18]
ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, трех глав, заключения, библиографии (87 наименований), приложения и содержит 127 страниц машинописного текста.
Локальный алгоритм как частная реализация метода последовательного анализа вариантов
Подробно рассмотрим здесь такой важный класс прикладных квазиблочных задач Ш как класс задач оптимального резервирования ресурсов, распределенных во времени (более обще: ресурсов, зависящих от некоторого дискретного параметра). Дадим краткую постановку задачи.
Имеется некоторая система резервирования (СР) ресурсов, распределенных во времени, которая содержит к типов ресурсов = /, к , причем известен запас ЬьС t -го ресурса в о -й период времени для некоторого дискретного интервала планирования l,Tj (т.е. С пробегает значения 1,2,...,Т). Имеется tb± пользователей ресурсов, которые в авоих заявках \Х/у указы-вают, какие типы ресурсов им потребуются, количества ресурсов, на какой срок (начало (іг, и кнец /З/ г. использования) и, возможно, последовательность использования ресурсов различных типов, причем пользователи могут указывать различные варианты использования ресурсов. Задача оптимального резервирования ресурсов, распределенных во времени, состоит в выборе количества ресурсов различных типов, последовательности и продолжительности их эксплуатации пользователями, оптимизирующем некоторую ЦФ, отражающую цели СР, причем должны учитываться ограничения по ресурсам.
Приведем примеры конкретных прикладных задач оптимального резервирования ресурсов, распределенных во времени, решение которых имеет важное практическое значение 1) Примеры из области гостиничного хозяйства. а) Имеется гостиница, число мест в которой на С -й день составляет Vc { о- d,T ). Ґ1± организаций (пользователей) присылают предварительные заявки на резервирование мест в гостинице (скажем, для командированных сотрудников этих организаций). В заявках указывается требуемое число мест, сроки начала и конца эксплуатации этих мест, а также возможные изменения в сроках. Требуется из всего множества заявок выбрать такое подмножество заявок, включаемых в обслуживание гостиницей, которое в наибольшей степени удовлетворяет спрос на места при выполнении ограничений по числу занимаемых мест в каждый день с . б) Имеется несколько гостиниц = к с количеством мест (ЬъС в 6 -и день (с-І, 7" ) в & -й гостинице (здесь ресурс -го - места Ъ- -й гостиницы). Ставится задача, аналогичная предыдущей, но с той разницей, что здесь еще требуется установить, в какую именно гостиницу следует направить пользователя, причем критерий эффективности - максимальный объем обслуживания с учетом приоритетов заявок на обслуживание. 2) Примеры из области туристского хозяйства. Имеется множество пунктов t d-jk рекреационного обслужива ния (туристских гостиниц, турбаз, кемпингов, мотелей, приютов, экскурсионных объектов), для каждого из которых известно коли чество мест в С -й период времени. Туристы в своих за явках указывают требуемое количество мест, пункты рекреационного обслуживания, которые они хотели бы посетить и в какой последо вательности, варианты сроков пребывания в пунктах. Требуется определить, по какому варианту обслужить каждого туриста. Кри терий эффективности - суммарная рекреационная ценность, получае мая туристами (рекреационная ценность - величина, характеризующая оздоровительно-познавательное воздействие на туристов рекреационных объектов: моря, леса, гор, музеев и т.п. [lOJlJ ). 3) Пример из области складского хозяйства. Имеется склад (или несколько складов). Задана вместимость склада vi Б с -й период времени ( С- d,T ). Организации присылают заявки на хранение грузов на складе; в заявке указывается объем груза, желательные сроки начала и окончания хранения, возможные варианты изменения этих сроков. Требуется из всего множества заявок выбрать те, для которых доход (или иным образом заданная эффективность) от эксплуатации склада за интервал ,TJ максимален. 4) Пример из области планирования научно-исследовательских работ. [55J . Организации предложено некоторое множество проектов для выполнения на интервал планирования [ і, Т] (длительный по сравнению со временем выполнения проектов), известны финансовые затраты, предполагающиеся равномерными (равномерность может быть достигнута разбиением проектов на ряд подпроектов, связанных между собой) на каждый период с 7" ДДЯ каждого проекта, известна прибыль от внедрения каждого проекта. Необходимо выбрать подмножество проектов для выполнения организацией, чтобы выполнялись ограничения по финансам на каждый период времени и прибыль от внедрения проектов была максимальной. Заявкам в данном случае соответствуют проекты, ресурсам - финансы. 5) Пример из области планирования грузовых перевозок. Судно вместимости & (ресурс), занятое в речных грузовых перевозках, последовательно заходит в порты . Органи зации / — 4,ґі предварительно подают заявки, в которых указано, из какого порта в какой нужно перевезти груз и какое количество его. Требуется найти, какие заявки нужно удовлетворить, чтобы прибыль от перевозки грузов была максимальна и выполнялись ограничения на вместимость. Здесь периодам времени из интервала планирования соответствует последовательность портов 1,...,Т, для J -й заявки задан о/у - порт отправления и &: - порт назначения.
Оценка эффективности локального алгоритма при использовании постоптимального анализа
Дойдя до и найдя (длина кратчайшего пути) и соответственно Ъпъ , можно переходить к обратному ходу алгоритма. Зная v m. , мы знаем индекс предшествующей вершины, входящей в кратчайший путь, а значит, и jr - индекс вершины, пред-шествующей этой и т.д., таким образом, кратчайший путь будет описываться индексами своих вершин, начиная с конца:
Зная вершины, входящие в кратчайший путь, находим блоки оптимального разбиения. Основные результаты работы сводятся к следующему: 1. Исследована эффективность локального алгоритма на классе квазиблочных задач дискретного программирования; в случае неявного перебора и полного перебора показано, что локальный алгоритм в сочетании с алгоритмом дискретного программирования эффективнее, чем алгоритм дискретного программирования сам по себе. 2. Найдены экстремальные значения оценки эффективности локального алгоритма в сочетании с полным перебором, а так хе средняя величина оценки эффективности при К =2 и асимптотическая формула для средней величины при к х . Этим самым показано, что локальный алгоритм в сочетании с полным перебором при решении квазиблочных задач дискретного программирования существенно эффективнее полного перебора. 3. Выявлена связь локального алгоритма с постоптимальным анализом в дискретном программировании, на основе этого анализируются возможности структурной оптимизации локального алгоритма; получена теоретическая оценка эффективности постоптимального анализа в дискретном программировании. 4. Локальный алгоритм реализован на ЭВМ в 3-х вариантах (I вариант - локальный алгоритм в сочетании с неявным перебором для решения задач оптимального резервирования; П вариант - локальный алгоритм в сочетании с неявным перебором и постоптимальным анализом для решения тех же задач; Ш вариант - локальный алгоритм в сочетании с алгоритмом динамического программирования для решения квазиблочных задач дискретного программирования, у которых каждый блок содержит одно ограничение) и произведен сравнительный машинный эксперимент с целью исследования реальных вычислительных возможностей локального алгоритма. 5. Выявлен ванный класс прикладных квазиблочных задач - класс задач оптимального резервирования ресурса, распределенного во времени. Элементами последнего класса являются задачи оптимального резервирования гостиничных номеров, задачи оптимального использования складских помещений, задачи оптимального планирования грузовых перевозок и т.д. 6. Исследован ряд свойств квазиблочных матриц : получены максимальное и минимальное число элементов внутри блоков к -квазиблочной матрицы, необходимое условие к -квазиблочности матрицы, достаточное условие к -квазиблочности матрицы, оценка числа всех К -квазиблочных матриц с элементами 0-1, оценка максимального числа блоков, на которые можно разбить данную матрицу; оценка числа разбиений на слабо связанные блоки заданной матрицы; решена задача оптимального разбиения матрицы инциденций задачи оптимального резервирования на слабо связанные блоки и реализован соответствующий алгоритм на ЭВМ. 7. На основании результатов работы мочно сделать следующий вывод: при достаточно небольших перемычках между блоками локальный алгоритм в сочетании с некоторым алгоритмом дискретного программирования является весьма эффективным и применение его при решении квазиблочных задач позволяет существенно повысить эффективность вышеупомянутого алгоритма дискретного программирования, в результате чего большие квазиблочные задачи дискретного программирования могут быть достаточно быстро решены.
Необходимое условие К -квазиблочности матрицы и оценка числа всевозможных к -квазиблочных матриц
Сотрудники организации подают заявки на отпуска, в которых указан срок начала отпуска с возможными изменениями. Число сотрудников, находящихся в отпуске, ограничено некоторой величиной (которая определяется необходимым числом сотрудников, обеспечивающим нормальное функционирование организации). Требуется выбрать такие варианты отпусков, чтобы количество удовлетворенных (по какому-либо из указанных вариантов) заявок в период наибольшего спроса было максимальным (здесь можно учесть и приоритеты сотрудников).
В результате аварии часть подстанций выбыла из строя. Имеется ряд объектов (пользователей) электросети, для некоторых из них можно подавать пониженное напряжение, для других же необходимо либо IOO % напряжения, либо ничего (т.к. при пониженном напряжении они работать не будут). Объекты подают заявки с указанием срока начала и окончания питания от электросети с возможными вариантами. Требуется так распределить имеющуюся мощность электросети между объектами во времени, чтобы убытки от нехватки электроэнергии были минимальны.
МТС обладает парком различной техники. Необходимо распределить Технику по участкам и собрать урожай с них при известных вариантах сроков уборки так, чтобы убытки от неполного сбора урожая были минимальны. (Дело в том, что урожайность из года в год меняется и нельзя составить график использования техники на более или менее длительный период). 9) Пример из области здравоохранения. Имеется городской центр госпитализации, в распоряжении которого имеется к больниц с известным числом Ого койко-мест ( Ъ "і, к ) на каждый период времени С из интервала планирования і,ТЦ . Имеется tb± лиц, которых нужно по тем или иным причинам госпитализировать (причины: обследование, болезнь и т.п.). Предложены варианты сроков размещения каждого лица. Требуется госпитализировать этих лиц так, чтобы достигался минимум непредотвращенного ущерба (от резкого ухудшения здоровья, смерти и т.п.). Таким образом, в рамки общей задачи оптимального резервирования ресурсов, распределенных во времени, укладывается ряд практически важных задач, решение которых даст значительный эффект. Рассмотрим математические модели для задачи оптимального резервирования: модель маршрутного резервирования; модель резервирования для нескольких СР, управляемых из единого центра; модель резервирования для одной СР с вариациями сроков использования ресурса и модель резервирования для одной СР без вариаций. Все эти модели представляют собой задачи булевского линейного программирования с квазиблочной структурой. Модель маршрутного резервирования. Имеются k СР, управляемых из единого центра, причем t -я СР ( t = ±{к ) обладает известным количеством ресурса бьі для каждого периода времени С из дискретного интервала планирования /_I,Tj . Имеются П± заявок We. на использование ресурсов каждой из СР (считаем, что все заявки поступают заблаговременно, скажем, в период О). В каждой заявке \х/ указываются запрашиваемое количество ресурса Q , последовательность СР . ресурсы которых будут использоваться заявкой \x/g, именно в заданной последовательности (эта последовательность СР образует маршрут, отсюда и название - модель маршрутного резервирования), задано множество вариантов / — t 4 2 - , j использования ресурса для заявки \Х/, в каждой из запрашиваемых заявкой СР (из множества л- ), причем для каждого варианта предполагается известным доход, получаемый в результате реализации ресурса (доход понимается не обязательно в экономическом смысле, а как некий эффект от реализации ресурса, с помощью количественной оценки которого можно оценивать достижение целей СР). Каждый из вариантов J _Cg заявки v e описывается вектором:
Оценка числа всевозможных разбиений матрицы инциденций задачи оптимального оезервирования на блоки
Были реализованы 3 варианта ЛА на ФОРТРАН ІУ для ЭВМ EC-I022: I) ЛА 6ч в сочетании с НП для решения задач ОР (под программа LOCL ); 2) ЛА Q Lt в сочетании с НП и ПА для реше ния тех ке задач (подпрограмма LOCPM ); 3) ЛА в сочетании с алгоритмом динамического программирования для решения квази блочных задач ДП, у которых каэдый блок содержит одно ограниче ние (подпрограмма LKLKNP ). Был произведен сравнительный машинный эксперимент на ЭВМ BC-I022 для алгоритмов I), 2) и алгоритма НП (подпрограмма НОТЕЬТ ) с целью сравнения эффективности вышеупомянутых алгоритмов на классе задач ОР. Параметры задач OP Cj bQj, & с порождались подпрограм мой эдтшж , использующей генератор случайных чисел (под программа RAV ) причем регулировалось число блоков, их размеры, размеры перемычки между блоками. В настоящем эксперименте с целью уменьшения числа параметров блоки строились одинаковых размеров (кроме, возможно, последнего блока) с одинаковыми перемычками .
В таблице 2.1 приведены результаты эксперимента. Т.к. время счета задач с помощью НП велико (более 30 минут), в таблице оно не приводится. Число реализаций для каждого набора ІП,П,К,П г было взято равным 3, что связано с большим общим временем счета. Отметим, что алгоритмы (%і и C/t работают,согласно данным таблицы 2.1, с переменным успехом, хотя теоретически алгоритм 0tz должен быть эффективнее, чем Otz . Причина этого заключается в способе программной реализации С целью выяснения экстремальных возможностей алгоритмов Utzf ОЬх, был произведен счет для задачи со следующими значениями параметров: /П. =400, К =1000, к =82, / =1. Среднее время счета 3-х задач равно 76,3 сек. (для алгоритма (}Cz ) Таким образом, из таблицы 2.1 видно, что при достаточно большом числе блоков и достаточно небольших перемычках между блоками квазиблочной задачи ЦЛП локальные алгоритмы позволяют эффективно решать такие задачи. В настоящем исследовании в качестве алгоритма ДП, решающего задачи внутри блоков, был взят алгоритм НП, далеко не самый эффективный алгоритм ДП. Использование эффективных алгоритмов ветвей и границ в сочетании с ЛА позволит решать квазиблочные задачи ДП больших размеров. Был произведен такяе небольшой эксперимент с вариантом 3) ЛА в сочетании с алгоритмом динамического программирования. Результаты эксперимента приведены в таблице 2.2. В настоящем параграфе установим минимальное число нулевых элементов в матрице, необходимое для того, чтобы матрица разбивалась на к ССБ, а также установим верхнюю я нижнюю оценки числа всевозможных к -квазиблочных матриц с элементами 0-1 ["84] . Для получения этих результатов нам нужно будет найти минимальное и максимальное возможное число элементов внутри ССБ матрицы hb ки Если Г1 - матрица размерности /?ъ х tv , a J) - число элементов внутри К блоков этой матрицы, то к. при условиях Докажем следующую лемму 3.1, в которой устанавливается максимальное число элементов внутри блоков к -квазиблочной матрицы размерности Нгх hv : Лемма 3.1. Доказательство. Доказательство проведем для более сложного случая к 2 . Итак, среди к -квазиблочных матриц размерности \т -)гъ найти матрицу rl с максимальным общим числом - 70 элементов в блоках. На рис.3.I показана такая матрица /7 Покажем, что эта матрица действительно оптимальна. Заметим, что достаточно рассмотреть квазиблочные матрицы, у которых At =i для любого . Итак, для матрицы параметры блоков имеют следующие значения.
