Содержание к диссертации
Введение
ГЛАВА I. Общая характеристика задач исследования территориально распределенных систем с ограниченными ресурсами 15
1.1. Предварительные замечания 15
1.2. Краткие сведения о системе города ... 18
1.3. Задача распределения ресурсов в территориально распределенных системах 22
1.4. Математическая формализация объекта исследования
Выводы по главе 1 28
ГЛАВА 2. Метод определения оптимальных размеров индивидуальных зон действия ресурсов в территориально распределенных системах 29
2.1. Общая постановка задачи на примере зон действия ВПЧ 29
2.2. Гипотезы о виде функции роста ущерба при пожаре 31
2.3. Гипотеза о характере ограничения ущерба при ликвидации пожара
2.4. Характеристика времени прибытия средств 37
2.5. Результирующий анализ функции ущерба в зоне действия 39
2.6. Анализ функции затрат на средства пожаротушения
2.7. Зависимость капитальных и эксплуатационных затрат от мощности ВПЧ 4-ї
2.8. Функция результирующего приведенного ущерба, отнесенного к одному обслуживаемому Объекту
2.9. Оценка эффективности автоматизации 48
Выводы по главе 2 52
ГЛАВА 3. Определение требуемых ресурсов в зоне (вероятностный критерий) 53
3.1. Вероятностный критерий для изолированных зон действия 53
3.2. Многомерная производящая функция для зоны 55
3.3. Процедура нахождения множества Парето... 56
3.4. Задача многокритериальной оптимизации ресурса в множестве изолированных зон ... 59
3.5. Приближенная модель для определения необходимых ресурсов для отдельной зоны... 63
3.6. Случай взаимодействия соседних зон 67
3.7. Оценка вероятностных характеристик для случая нескольких пожаров 68
3.8. Оценка достаточности ресурсов при взаимодействии зон Y1
3.9. Оценка вероятности достаточности ресурса 73
3.10. Оценка вероятностно-временных характеристик города у6
Выводы по главе 3 7д
ГЛАВА 4. Определение требуемых ресурсов в зоне (минимаксный критерий) 80
4.1. Минимаксный критерий для изолированных зон 80
4.2. Минимаксный критерий для взаимодействующих зон
4.3. Эвристические предпосылки для построения алгоритма приближенного решения... 83
4.4. Обоснование алгоритма приближенного решения специальной задачи целочисленного линейного программирования большой размерности 85
4.5. Анализ результатов вычислительного эксперимента 92
Выводы по главе 4
ГЛАВА 5. Задачи оперативного управления мобильными ресурсами в территориально распределенных системах
5.1. Оптимальный по времени сбор ресурсов из соседних зон 93
5.2. Оптимальная дислокация уникальных мобильных обслуживающих устройств дд
Выводы по главе 5 107
Общее заключение по работе 108
Литература
Приложение
- Краткие сведения о системе города
- Гипотезы о виде функции роста ущерба при пожаре
- Задача многокритериальной оптимизации ресурса в множестве изолированных зон
- Обоснование алгоритма приближенного решения специальной задачи целочисленного линейного программирования большой размерности
Введение к работе
Большинство современных крупных народно-хозяйственных систем технического и экономического характера представляет собой территориально распределенные системы. Эти системы включают в свой состав целевые объекты, задача которых заключается в выпол^ нении основных "выходных" функций, т.е. в создании основного выходного эффекта системы, функциональные объекты, задача которых заключается в формировании организационно-управлягощей структуры и сервисном обеспечении основных целевых объектов системы, а также различного рода ресурсов (материальных, информационных, энергетических и т.п.), необходимых для обеспечения нормального функционирования объектов первых двух типов. Все объекты таких систем определенным образом распределены по территории: целевые объекты размещаются, исходя из требований функциональной необходимости выполнения системой своих основных задач, а функциональные объекты и источники ресурсов размещаются по территории в основном в соответствии с наилучшим обеспечением функционирования целевых объектов.
На практике размещение целевых объектов является заданным или же не подлежит выбору со стороны исследователей или проектировщиков остальной части системы, являющейся "обеспечивающей". На содержательном уровне задача ставится так: требуется оптимальным образом спроектировать обеспечивающую часть территориально распределенной системы, чтобы она с заданными показателями качества выполняла бы свои функции при минимально возможном расходе ресурсов. (Возможно, естественно и обратная постановка задачи: спроектировать обеспечивающую часть системы, чтобы она функционировала бы с наилучшими показателями качества при существующих ог-
раничениях на ресурсы.) И прямая и обратная задачи являются задачами на условную оптимизацию, возможность их конструктивного решения определяется видом целевого функционала и структурой системы ограничений.
Актуальность практического решения указанных задач определяется тем, что упомянутые территориально распределенные системы, как правило, выполняют важные народно-хозяйственные задачи. К рассматриваемым системам относятся, например, системы связи, вычислительные системы коллективного пользования, некоторые системы энергетики, транспортные системы, системы централизованного технического обслуживания различных технических средств (вычислительной техники, сельско-хозяйственной техники, транспортных средств и т.п.), системы материально-технического снабжения.
Ряд из указанных систем обладает к тому же еще и весьма характерной особенностью: целевые объекты взаимодействуют с функциональными объектами и необходимыми ресурсами на локальном уровне. Иными словами, потребление ресурсов некоторым целевым объектом может сказаться на обеспеченности тем же ресурсом лишь для целевых объектов, расположенных в некотором смысле близко от рассматриваемого объекта.
Эти особенности больших территориально распределенных систем (структура, большая размерность, локальность взаимодействия) определяют и специфику соответствующих математических моделей.
Цель данной работы состоит в формулировке и математической формализации различных задач, возникающих при исследовании территориально распределенных систем с ограниченными ресурсами, разработке методов математического исследования этих систем (решение задач анализа и синтеза для математических моделей,адекватных большим территориально распределенным системам с локальным взаи-
_ 7 -
модействием входящих в их состав объектов). Кроме того, прикладной целью данной работы является разработка таких математических моделей, которые имели бы не только чисто математический интерес, но и смогли бы найти применение при решении практических задач. Наконец, к целям данной работы можно отнести и разработку алгоритмов решения задач целочисленного программирования большой размерности, получающихся в результате формулирования оптимизационных задач.
Виды сформулированных математических задач предопределили и методы исследования. Эти методы исследования относятся к традиционным методам теории исследования операций: это вероятностно-статистические методы и методы оптимизации.
К вероятностно-статистическим методам относятся, прежде всего, комбинаторные методы, связанные с построением многомерных производящих функций, и методы теории случайных потоков, использующие приемы разрежения случайных потоков, а также методы теории массового обслуживания, применительно к задачам обслуживания территориально распределенных объектов.
Методы оптимизации, используемые в работе, относятся к решению многокритериальных задач оптимизации, т.е. к построению множеств неулучшаемых решений (множеств Парето), а также к разработке эффективных вычислительных алгоритмов решения задач целочисленного линейного программирования большой размерности.
Научная новизна в основном заключается в построении комплекса взаимосвязанных математических моделей, описывающих функционирование большой территориально распределенной системы и позволяющих находить оптимальные значения различных параметров с учетом ресурсных ограничений. Впервые сформулированы совокупности вероятностных и минимаксных критериев достаточности ресурсов
для обеспечения требуемых показателей качества функционирования рассматриваемых систем.
Найден класс математических задач, описывающих территориально распределенные системы с локальным характером взаимодействия объектов и локальным характером использования ресурсов, обеспечивающих нормальное функционирование. Для этих задач определен и круг практических приложений.
Практическая ценность полученных результатов определяется тем, что разработанные математические модели и алгоритмы решения оптимизационных задач большой размерности (метод многомерных производящих функций и метод решения задач целочисленного линейного программирования большой размерности) нашли практическое применение при исследовании реальных объектов (систем пожарной охраны городов) на этапе проектирования.
Достоверность полученных результатов обеспечивается корректностью используемого математического аппарата при решении аналитических задач, обоснованностью сделанных допущений и соответствием их практическим постановкам задачи, а предлагаемые алгоритмы приближенного решения задач целочисленного линейного программирования апробированы на достаточно большом вычислительном эксперименте.
Практическое внедрение результатов работы: предложенные в работе математические модели и алгоритмы их исследования использованы при анализе проектных решений отдельных задач, касающихся вопросов пожарной охраны городов, и использованы в учебном процессе в Высшей инженерно-пожарной технической школе МВД СССР.
Апробация работы заключалась в изложении основных научных результатов на научных семинарах в Вычислительном центре АН СССР
- 9 -(Москва, І982-84гг.), на кафедре "Большие системы" Московского физико-технического института (Москва, 1981г., 1983г.), в Институте кибернетики АН Азерб.ССР, а также на Всесоюзном семинаре "Инженерные методы надежности", проводимом в Кабинете надежности и качества Политехнического музея г.Москвы в рамках Всесоюзного семинара по надежности и прогрессивным методам контроля качества промышленной продукции.
Основное содержание диссертации отражено в 4 печатных работах.
Краткое изложение содержания диссертационной работы. Работа состоит из пяти глав и приложения.
Краткие сведения о системе города
Современная система пожарной охраны (ПО) города является сложной многофункциональной системой. Сложность самого охраняемого объекта - современного города с многомиллионным населением, развитой промышленностью, большим числом общественных организаций, разветвленной службой быта и огромными жилыми массивами - предопределяет и сложность системы ПО. (Основные задачи, решаемые в ПО, схематически представлены на рис.1.1.)
Структура управления гарнизоном ПО представляет собой сложную пространственно-функциональную структуру. Ориентировочный перечень основных задач, решаемых в системе управления ПО, приводится ниже: - прием и регистрация сообщений о пожарах и других бедствиях, сведения о которых поступают по служебным линиям, линии "01", от автоматических пожарных извещателей, а также от других источников информации, - сведение к минимуму ложных тревог, поступающих от всех источников информации, - определение дислокации объекта пожара, - определение номеров военизированных пожарных частей (ВПЧ) и наряда средств для ликвидации пожара, - определение оптимальных маршрутов следования боевых подразделений к месту пожара в зависимости от внешней обстановки (состояния дорог, уровня трафика на улицах, удобных направлений подъезда к объекту и пр.), - выработка тактики тушения пожара в зависимости от характера объекта, номера пожара, наличия определенных средств, характера протекания процесса пожара (непредвиденные изменения процесса развития пожара, оперативное уточнение характеристик объекта пожара и т.п.)» - определение технико-экономических и оперативных характеристик эффективности системы ПО города, - проведение текущего технического обслуживания средств ПО и поддержание его высокой готовности. Для эффективного решения большинства перечисленных задач необходима разработка соответствующих математических моделей, которые должны лечь в основу обоснованных решений как для проектных работ (определение структуры системы ПО, определение нарядов средств, приписанных различным ВПЧ и т.п.), так и для успешного проведения боевых операций (определение маршрутов следования техники, определение наряда средств и его распределение между различными ВПЧ при тушении пожара, изменение тактики тушения пожара и т.п.).
Во многих странах мира, в том числе и в Советском Союзе, создаются и уже существуют АСУ ПО городов. Как правило, это уникальные АСУ, создаваемые для условий каждого конкретного города. В качестве наиболее ярких систем подобного типа можно назвать АСУ, созданные на базе мощных ЭВМ, в Москве [ Н і] и Лос-Анжелесе [52] . Применение в этих городах АСУ ПО оказалось весьма эффективным, несмотря на большие капитальные вложения на создания этих систем и высокие эксплуатационные затраты. Следует заметить, что в. СССР начата разработка унифицированной АСУ ПО города, которая будет в последствии внедряться во всех миллионных городах нашей страны.
Внедрение автоматизированных систем управления пожарной охраной города естественным образом приводит к необходимости разработки соответствующих математических моделей и программного обеспечения для получения оперативных решений. Кроме того, разработка математических моделей функционирования пространственно распределенных систем обслуживания с пространственно распределенными ресурсами может быть широко использована не только для принятия оперативных решений, но и для задач проектирования, включая задачи модернизации существующих систем пожарной охраны города и задачи перспективного их развития с учетом социального и экономического развития города.
При формальной постановке задач город рассматривается как совокупность распределенных по плоскости объектов, каждый из которых может служить источником пожарной ситуации. Объекты могут подразделяться по важности, по возможной специфике пожарной ситуации (склады легковоспламеняющихся материалов, высотные здания, химические предприятия и пр.). Кроме того, каждый объект характеризуется еще и максимальным номером пожара. Номер пожара зависит уже не только от вида объекта, но и от того, в какой фазе началась локализация пожара.
Гипотезы о виде функции роста ущерба при пожаре
Сгорание ограниченного количества достаточно компактно сосредоточенного в пространстве обычного горючего материала является физико-химическим процессом, протекающим, как правило, по определенному "сценарию": сначала сравнительно продолжительное время происходит относительно медленное возгорание объекта вокруг источника пожара, затем процесс пожара переходит в фазу весьма активного горения, имеющего пока еще достаточно локализованный характер. Обычно этот момент является моментом обнаружения пожара, т.е. после небольшой задержки сигнал о пожаре поступает в систему пожарной охраны. Затем начинается практически лавинообразное развитие пожара: увеличивается теппература в эпицентре пожара, происходит экстенсивное развитие процесса горения, причем увеличение температуры приводит к началу горения плохо горящих горючих материалов, что в результате приводит к серьезным нарушениям силовых конструкций. Затем происходит экспансия пожара по территории объекта пожара. Наконец, если объект пространственно изолирован начинается "догорание" его и постепенное стихание пожара по причине полного сгорания всего горючего материала. (Понятно, что такой сценарий соответствует пожару различного рода зданий, но не относится к объектам, содержащим легковоспламеняющиеся или взрывчатые вещества: там пожар носит характер серии последовательных взрывов, приводящих к быстрому переносу огня и к сильным разрушениям в зоне самого взрыва. Этот сценарий горения не правомерен также для крупномасштабных пожаров, которые имели, например, место в ряде городов Германии в 1945 году в результате варварских бомбардировок американской авиацией, когда возникал эффект, получивший название "огненного торнадо".)
Исходя из сценария пожара обычного горючего материала можно считать, что хорошей математической моделью развития ущерба от пожара во времени может служить 5 -образная функция, т.е. такая функция W , которая до некоторого значения аргумента выпукла вниз, будучи возрастающей, а после этого момента она продолжает возрастать, но является уже выпуклой вниз. Другими словами,
Для этого распределения точка перегиба Г может быть названа моментом наступления половинного ущерба. Величина в характе-ризует интенсивность пожара, а величина и - абсолютное значение ущерба при условии полного сгорания объекта.
Величина W рассчитывается на основании информации о стоимостях входящих в объект элементов или оценивается эксперт-ным путем. Величины 6 и / могут быть оценены только на основании данных о реальных пожарах или по результатам расчетов на математических моделях пожаров идеализированных объектов. Аппроксимация функции ущерба от длительности процесса его рания объекта в виде функции (2.1) удобна не только тем, что она имеет достаточно простой аналитический вид и имеет хорошую интер претацию для различных вероятностных приложений, но еще и тем, что имеются весьма подробные таблицы численных значений. Кроме того, если диапазон изменения аргумента для функции Лапласа, приведенный в таблице, недостаточен, то можно использовать верх нюю и нижнюю оценки для интеграла /2 Теперь мы рассмотрим одну из возможных математических моделей процесса протекания тушения пожара. Будем считать, что с момента прибытия fj первой группы из ближайших ВПЧ, в зоне действия которых находится объект пожара, процесс роста ущерба W(t) качественно меняется. Если tf / , то в момент ff у функции W(f) будет наблюдаться точка перегиба, т.е. на интервале \J I , ) функция WM становится выпуклой вверх. Размер ущерба после момента до полной ликвидации пожара зависит от уже достигнутого ущерба к моменту , т.е. от )Xf(t) и от соотношения наличных средств тушения и потребных средств тушения для данного номера пожара. Для описания характера ограничения ущерба от пожара в процессе его тушения примем следующую гипотезу: с момента начала тушения пожара функция ущерба экспоненциально стремится к некоторому финальному значению.
Задача многокритериальной оптимизации ресурса в множестве изолированных зон
Вычислительный эксперимент проводился для задачи целочисленного линейного программирования с размерностью матрицы 169 х 169. (Размерность этой матрицы определялась тем, что по числу зон этот случай близок к размерности реальной задачи ПО города в условиях Баку. Численные значения были взяты условными, позволяющими провести вычислительный эксперимент на тестовом примере.) Размерность решаемой задачи была выбрана таким образом, чтобы можно было бы проиллюстрировать достоинства и технологию решения указанной задачи предлагаемым приближенным методом, но в то же время можно было бы провести решение этой задачи прямыми методами. (Для прямого решения использовалась программа решения задач линейного программирования, разработанная в ВЦ ІШ СССР, с добавлением блока целочисленного решения, использующего метод ветвей и границ.)
Вся территория Г была представлена в виде плотного покрытия правильными идентичными б-угольниками. Вся область представлялась в виде квазиквадрата размера ІЗ х 13. Матрица исходных потребностей для тестового примера приведена на рисунке в приложении. Кроме того, эксперимент проводился для случаев, когда в данную матрицу вводились возмущения: в задаче № 2 вместо числа, стоящего в I столбце I строки, записывалось число 9, в задаче № 3 вместо числа, стоящего в I столбце 2 строки, записывалось число 9, в задаче № 4 вместо числа, записанного в 7 столбце 7 строки, записывалось число 9 и, наконец, в задаче № 5 вместо числа, стоящего в 13 столбце 13 строки, записывалось также число 9.
Возмущения в исходную матрицу вводились для того, чтобы проверить, влияет ли локальное возмущение на точность решения по аргументам целевого функционала. Эксперимент показал сильное влияние этих возмущений, если возмущенные элементы попадали в области Q , с которых начиналось действие алгоритма (что совершенно естественно). Во время эксперимента варьировались размеры областей Р и Q . (В эксперименте эти области назывались соответственно: О - "ядро", G\$ - "кайма".) Результаты решения, полученного с использованием приближенного метода, приведены в таблицах 4.1 - 4.5. В заголовках таблиц приводятся также значения решений, полученных строгим методом. Эксперимент подтвердил хорошее совпадение полученных приближенных значений со строгим решением. (В ряде случаев получены даже точные совпадения.) В целом лучшие решения для рассмотренных задач не давали погрешности решения, превышающей 5$. В таблице 4.6 приведены сравнения времени счета (в условных единицах) задач Ш 1-5 строгим методом и приближенным методом (при приближенном методе бралось время счета для наилучшего решения). Очевидно, что с ростом размерности задачи преимущество приближенного метода по быстродействию будет увеличиваться. В то же время точность решения принципиально не должна изменяться. Комментарий. Решение задал нелинейного и целочисленного нелинейного программирования с использованием изложенной идеи должно дать в принципе еще больший выигрыш при исследовании математических моделей, описывающих территориально распределенные системы с локальным взаимодействием объектов и ресурсов, поскольку в этом случае трудоемкость решения возрастает с ростом размерности еще сильнее, чем в задачах линейного программирования.
Обоснование алгоритма приближенного решения специальной задачи целочисленного линейного программирования большой размерности
В данном контексте под обслуживающим устройством понимается некоторое уникальное техническое средство пожаротушения, численность которого во всем гарнизоне ПО города невелика, а нагрузка этого средства ощутима, т.е. в принципе не исключена необходимость в нем одновременно в нескольких точках, т.е. возможно возникновение таких ситуаций, когда заявки могут образовывать очередь. Как и ранее, под заявкой будет пониматься возникновение пожарной ситуации, а под источником заявок - объект возникновения пожара.
Предполагается, что обслуживающее устройство базируется в некотором центре (базе), откуда совершает выезды для обслуживания заявок, возникающих на объектах обслуживания. Произведя обслуживание заявки (в данном случае - участие в ликвидации пожара вместе с другими техническими средствами пожаротушения), оно возвращается на базу, где либо ждет поступления заявки, либо получает распоряжение относительно выезда на объект, уже ожидающий своей очереди обслуживания.
Предполагается, что распоряжение о выезде на очередное обслуживание обслуживающее устройство получает, только прибыв на базу. Это является упрощяющим исследование допущением, поскольку на практике существует оперативная связь, позволяющая техническим средствам пожаротушения следовать к месту очередного пожара. Это допущение оказывается приемлемым для решения практических задач, если справедливо допущение о том, что пожары, требующие данный тип средств пожаротушения для своей ликвидации, одновременно в нескольких местах возникают очень редко, а область действия этих средств достаточно велика.
Рассматривается множество территориально распределенных объектов, генерирующих пуассоновские потоки заявок с интенсивностями \ Заявки обслуживаются в порядке поступления одним обслуживающим устройством, передвигающимся от объекта к базе и от базы к объекту с постоянной единичной скоростью. Обслуживание заявки заключается в том, что обслуживающее устройство выезжает из базы к объекту, проводит там некоторое время и возвращается обратно. Очевидно, такая система есть система массового обслуживания (СМО) типа Л//G/ J . Стационарное время ожидания для рассматриваемых систем равно стационарному времени ожидания выезда к объекту. (Эту величину будем называть стационарным временем отклика). Более важна другая характеристика - стационарное время ожидания приезда обслуживающего устройства. Задача состоит в определении координат базы ос , минимизирующих эту величину.
Рассмотрим сначала случай расположения объектов на прямой. Это в практических задачах соответствует размещению объектов вдоль некоторой основной транспортной магистрали города.
Пусть ас - координата базы; ос. - координата объекта. " интенсивность поступления заявок, G (f) - функция распределения времени задержки на объекте. Рассматриваемая система есть СМО А// /Ї с входящим пуассоновским потоком интенсивности Л и функцией распределения времени обслуживания
Трудности численного решения задачи с размещением объектов на плоскости определяются тем, что оптимизируемая функция в этом случае не является унимодальной. Дополнительные трудности возникают при практических постановках задач, поскольку приходится рассматривать, вообще говоря, уже не расстояния до объектов, а время прибытия обслуживающего устройства к объекту, у которого возникла заявка, что приводит, как уже отмечалось, к необходимости учета множества своеобразных факторов: времени суток, погоды и т.п.
