автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.02, диссертация на тему:Математические модели анализа и синтеза территориально распределенных систем с ограниченными ресурсами

ВВЕДЕНИЕ.

ГЛАВА I. ОБЩАЯ ХАРАКТЕРИСТИКА ЗАДАЧ ИССЛЕДОВАНИЯ ТЕРРИТОРИАЛЬНО РАСПРЕДЕЛЕННЫХ СИСТЕМ С ОГРАНИЧЕННЫМИ РЕСУРСАМИ.

1.1. Предварительные замечания.

1.2. Краткие сведения о системе ПО города. /

1.3. Задача распределения ресурсов в территориально распределенных системах.

1.4. Математическая формализация объекта исследования

Выводы по главе 1.

ГЛАВА 2. МЕТОД ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНЫХ РАЗМЕРОВ ИНДИВИДУАЛЬНЫХ ЗОН ДЕЙСТВИЯ РЕСУРСОВ В ТЕРРИТОРИАЛЬНО РАСПРЕДЕЛЕННЫХ СИСТЕМАХ.

2.1. Общая постановка задачи на примере зон действия ВПЧ.

2.2. Гипотезы о виде функции роста ущерба при пожаре.

2.3. Гипотеза о характере ограничения ущерба при ликвидации пожара.

2.4. Характеристика времени прибытия средств

2.5. Результирующий анализ функции ущерба в зоне действия. зд

2.6. Анализ функции затрат на средства пожаротушения. ¿¿о

2.7. Зависимость капитальных и эксплуатацион

- 3 ных затрат от мощности ВПЧ.

2.8. Функция результирующего приведенного ущерба, отнесенного к одному обслуживаемому объекту. ¿¿б

2.9. Оценка эффективности автоматизации.

Выводы по главе 2.

ГЛАВА 3. ОПРЕДЕЛЕНИЕ ТРЕБУЕМЫХ РЕСУРСОВ В ЗОНЕ (ВЕРОЯТНОСТНЫЙ КРИТЕРИЙ).

3.1. Вероятностный критерий для изолированных зон действия.

3.2. Многомерная производящая функция для зоны.

3.3. Процедура нахождения множества Парето. 5в

3.4. Задача многокритериальной оптимизации ресурса в множестве изолированных зон.

3.5. Приближенная модель для определения необходимых ресурсов для отдельной зоны.

3.6. Случай взаимодействия соседних зон.

3.7. Оценка вероятностных характеристик для случая нескольких пожаров.

3.8. Оценка достаточности ресурсов при взаимодействии зон. 7 л

3.9. Оценка вероятности достаточности ресурса

3.10. Оценка вероятностно-временных характеристик ПО города.

Выводы по главе 3.

ГЛАВА 4. ОПРЕДЕЛЕНИЕ ТРЕБУЕМЫХ РЕСУРСОВ В ЗОНЕ (МИНИМАКСНЫЙ КРИТЕРИЙ).

4.1. Минимаксный критерий для изолированных

- 4 зон. во

4.2. Минимаксный критерий для взаимодействующих зон. 8/

4.3. Эвристические предпосылки для построения алгоритма приближенного решения.

4.4. Обоснование алгоритма приближенного решения специальной задачи целочисленного линейного программирования большой размерности.

§

4.5. Анализ результатов вычислительного эксперимента.

Выводы по главе 4. $

ГЛАВА 5. ЗАДАЧИ ОПЕРАТИВНОГО УПРАВЛЕНИЯ МОБИЛЬНЫМИ РЕСУРСАМИ В ТЕРРИТОРИАЛЬНО РАСПРЕДЕЛЕННЫХ СИСТЕМАХ. дз

5.1. Оптимальный по времени сбор ресурсов из соседних зон.

5.2. Оптимальная дислокация уникальных мобильных обслуживающих устройств. дд

Выводы по главе 5.

Большинство современных крупных народно-хозяйственных систем технического и экономического характера представляет собой территориально распределенные системы. Эти системы включают в свой состав целевые объекты, задача которых заключается в выпол^ нении основных "выходных" функций, т.е. в создании основного выходного эффекта системы, функциональные объекты, задача которых заключается в формировании организационно-управлягощей структуры и сервисном обеспечении основных целевых объектов системы, а также различного рода ресурсов (материальных, информационных, энергетических и т.п.), необходимых для обеспечения нормального функционирования объектов первых двух типов. Все объекты таких систем определенным образом распределены по территории: целевые объекты размещаются, исходя из требований функциональной необходимости выполнения системой своих основных задач, а функциональные объекты и источники ресурсов размещаются по территории в основном в соответствии с наилучшим обеспечением функционирования целевых объектов.

На практике размещение целевых объектов является заданным или же не подлежит выбору со стороны исследователей или проектировщиков остальной части системы, являющейся "обеспечивающей". На содержательном уровне задача ставится так: требуется оптимальным образом спроектировать обеспечивающую часть территориально распределенной системы, чтобы она с заданными показателями качества выполняла бы свои функции при минимально возможном расходе ресурсов. (Возможно, естественно и обратная постановка задачи: спроектировать обеспечивающую часть системы, чтобы она функционировала бы с наилучшими показателями качества при существующих ограничениях на ресурсы.) И прямая и обратная задачи являются задачами на условную оптимизацию, возможность их конструктивного решения определяется видом целевого функционала и структурой системы ограничений.

Актуальность практического решения указанных задач определяется тем, что упомянутые территориально распределенные системы, как правило, выполняют важные народно-хозяйственные задачи. К рассматриваемым системам относятся, например, системы связи, вычислительные системы коллективного пользования, некоторые системы энергетики, транспортные системы, системы централизованного технического обслуживания различных технических средств (вычислительной техники, сельско-хозяйственной техники, транспортных средств и т.п.), системы материально-технического снабжения.

Ряд из указанных систем обладает к тому же еще и весьма характерной особенностью: целевые объекты взаимодействуют с функциональными объектами и необходимыми ресурсами на локальном уровне. Иными словами, потребление ресурсов некоторым целевым объектом может сказаться на обеспеченности тем же ресурсом лишь для целевых объектов, расположенных в некотором смысле близко от рассматриваемого объекта.

Эти особенности больших территориально распределенных систем (структура, большая размерность, локальность взаимодействия) определяют и специфику соответствующих математических моделей.

Цель данной работы состоит в формулировке и математической формализации различных задач, возникающих при исследовании территориально распределенных систем с ограниченными ресурсами, разработке методов математического исследования этих систем (решение задач анализа и синтеза для математических моделей,адекватных большим территориально распределенным системам с локальным взаимодействием входящих в их состав объектов). Кроме того, прикладной целью данной работы является разработка таких математических моделей, которые имели бы не только чисто математический интерес, но и смогли бы найти применение при решении практических задач. Наконец, к целям данной работы можно отнести и разработку алгоритмов решения задач целочисленного программирования большой размерности, получающихся в результате формулирования оптимизационных задач.

Виды сформулированных математических задач предопределили и методы исследования. Эти методы исследования относятся к традиционным методам теории исследования операций: это вероятностно-статистические методы и методы оптимизации.

К вероятностно-статистическим методам относятся, прежде всего, комбинаторные методы, связанные с построением многомерных производящих функций, и методы теории случайных потоков, использующие приемы разрежения случайных потоков, а также методы теории массового обслуживания, применительно к задачам обслуживания территориально распределенных объектов.

Методы оптимизации, используемые в работе, относятся к решению многокритериальных задач оптимизации, т.е. к построению множеств неулучшаемых решений (множеств Парето), а также к разработке эффективных вычислительных алгоритмов решения задач целочисленного линейного программирования большой размерности.

Научная новизна в основном заключается в построении комплекса взаимосвязанных математических моделей, описывающих функционирование большой территориально распределенной системы и позволяющих находить оптимальные значения различных параметров с учетом ресурсных ограничений. Впервые сформулированы совокупности вероятностных и минимаксных критериев достаточности ресурсов для обеспечения требуемых показателей качества функционирования рассматриваемых систем.

Найден класс математических задач, описывающих территориально распределенные системы с локальным характером взаимодействия объектов и локальным характером использования ресурсов, обеспечивающих нормальное функционирование. Для этих задач определен и круг практических приложений.

Практическая ценность полученных результатов определяется тем, что разработанные математические модели и алгоритмы решения оптимизационных задач большой размерности (метод многомерных производящих функций и метод решения задач целочисленного линейного программирования большой размерности) нашли практическое применение при исследовании реальных объектов (систем пожарной охраны городов) на этапе проектирования.

Достоверность полученных результатов обеспечивается корректностью используемого математического аппарата при решении аналитических задач, обоснованностью сделанных допущений и соответствием их практическим постановкам задачи, а предлагаемые алгоритмы приближенного решения задач целочисленного линейного программирования апробированы на достаточно большом вычислительном эксперименте.

Практическое внедрение результатов работы: предложенные в работе математические модели и алгоритмы их исследования использованы при анализе проектных решений отдельных задач, касающихся вопросов пожарной охраны городов, и использованы в учебном процессе в Высшей инженерно-пожарной технической школе МВД СССР.

Апробация работы заключалась в изложении основных научных результатов на научных семинарах в Вычислительном центре АН СССР

Москва, 1982-84гг.), на кафедре "Большие системы" Московского физико-технического института (Москва, 1981г., 1983г.), в Институте кибернетики АН Азерб.ССР, а также на Всесоюзном семинаре "Инженерные методы надежности", проводимом в Кабинете надежности и качества Политехнического музея г.Москвы в рамках Всесоюзного семинара по надежности и прогрессивным методам контроля качества промышленной продукции.

Основное содержание диссертации отражено в 4 печатных работах.

Краткое изложение содержания диссертационной работы. Работа состоит из пяти глав и приложения.

6. Основные результаты диссертационной работы опубликованы в следующих печатных работах:

1) Гусейнов Б.А. Использование вероятностных критериев для определения наряда противопожарных средств. Известия АН СССР. Техн.кибернетика. № 3, 1983.

2) Гусейнов Б.А., Перлов Ю.М. Одна задача технического обслуживания территориально распределенных объектов. Известия АН СССР. Техн.кибернетика. № б, 1983.

3) Гусейнов Б.А. Определение комплекса средств для выполне

- 109 ния потока заявок с заданным уровнем надежности. Надежность и контроль качества. № 3, 1984.

4) Гусейнов Б.А. Об одной задаче резервирования в территориально распределенных системах. Надежность и контроль качества. № 7, 1984.

- но

- 108 -ОБЩЕЕ ЗАКЛЮЧЕНИЕ ПО РАБОТЕ

1. Сформулированы основные задачи минимизации ресурсов в территориально распределенной системе применительно к одному классу специфических систем.

2. Сформулирована и решена задача определения оптимального размера зоны действия ресурса в индивидуальной зоне его действия с учетом ущербов и затрат.

3. Разработан метод построения базиса множества Парето с помощью многомерных производящих функций для решения многокритериальной задачи определения векторного ресурса для территориально распределенной системы при вероятностном критерии достаточности ресурса.

Разработан алгоритм приближенного решения задачи целочисленного линейного программирования большой размерности с линейной трудоемкостью по размерности задачи; метод использован для определения оптимального ресурса для территориально распределенной системы при минимаксном критерии достаточности ресурса.

5. Сформулирована и решена задача дислокации мобильного обслуживающего устройства, предназначенного для удовлетворения заявок от территориально распределенных объектов.

1. Айгнер М. Комбинаторная теория. Москва, "Мир", 1982, с.558.

2. Акоф Р., Сасиени М. Основы исследования операций. Пер. с англ. под ред. И.А.Ушакова. Москва, "Мир", 1971.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. Москва, "Мир", 1979, с.536.

4. Барлоу Р., Прошан Ф. Математическая теория надежности. Пер. с англ. под ред. Б.В.Гнеденко. Москва, "Советское радио", 1969.

5. Барра Ж.-Р. Основные понятия математической статистики. Москва, "Мир", 1974, с.280.

6. Басакер Р., Саати Т. Конечные графы и сети. Пер. с англ. под ред. А.И.Теймана. Москва, "Наука", 1974.

7. Большаков И.А., В.С.Ракошиц. Прикладная теория случайных потоков. Москва, "Советское радио", 1978, с.248.

8. Булавский В.А., Звягина Р.А., Яковлева М.А. Численные методы линейного программирования. Москва, "Наука", 1977, с.368.

9. Виленкин Н.Я. Комбинаторика. Москва, "Наука", 1969, с.328.

10. Вильсон А.Дж. Энтропийные методы моделирования сложных систем. Москва, "Наука", 1978, с.248.

11. Гаврилей В.М. и др. Применение методов математического моделирования при оценке пожарной опасности. В сб.: Вопросы экономики в пожарной охране, вып.4, ВНИИПО, 1975.

12. Гнеденко Б.В., Беляев Ю.К., Соловьев А.Д. Математические методы в теории надежности. Москва, "Наука", 1965.

13. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. Москва, "Наука", 1969, с.382.

14. Гончарова Л.И., Станевиюч А.-И.А. Автоматизация решения опти- III мизационных задач. В сб.: Согласование и анализ решений оптимизационных задач. Под ред. Некрасова A.C. Москва, "Наука", 1976.

15. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. Москва, "Мир", 1981, с.368.

16. Гусейнов Б.А. Использование вероятностных критериев для оп-ребеления наряда противопожарных средств. Известия АН СССР. Техн.кибернетика, № 3, 1983, с.200-203.

17. Гусейнов Б.А., Перлов Ю.М. Одна задача технического обслуживания территориально распределенных объектов. Известия АН СССР. Техн.кибернетика, № 6, 1983, с.98-102.

18. Гусейнов Б.А. Определение комплекса средств для выполнения потока заявок с заданным уровнем надежности. Надежность и контроль качества, № 3, 1984, с.10-12.

19. Гусейнов Б.А. Об одной задаче резервирования в территориально распределенных системах. Надежность и контроль качества, № 7, 1984, с.11-14.

20. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизации. Москва, "Наука", 1981.

21. Емеличев В.А. Дискретная оптимизация. Последовательные схемы решения. I, II. Кибернетика, № 6, 1971$ № 2, 1972, с.92-103.

22. Емеличев В.А., Комлик В.Н. Метод построения последовательности планов для решения задач дискретной оптимизации. Москва, "Наука", 1981, с.208.

23. Карманов В.Г. Математическое программирование. Москва, "Наука", 1975, с.272.

24. Кёнинг Д., Штоян Д. Методы теории массового обслуживания. Москва, "Радио и связь", 1981.

25. Клейнрок Л. Теория массового обслуживания. Москва, "Машиностроение", 1979.- 112

26. Климов Г.П. Стохастические системы обслуживания. Москва, "Наука", 1966, с.243.

27. Козлов Б.А., Ушаков И.А. Справочник по расчету надежности аппаратуры радиоэлектроники и автоматики. Москва, "Сов.Радио", 1975.

28. Корбут A.A., Финкелыитейн ЮЛ). Дискретное программирование. Москва, "Наука", 1969, с.368.

29. Кофман А. Введение в прикладную комбинаторику. Пер. с фран. под ред. Б.А.Севастьянова. Москва, "Наука", 1975.

30. Криницкий H.A., Фролов Г.Д., Миронов Г.А. Программирование и алгоритмические языки. Москва, "Наука", 1975, с.496.

31. Минаев С.Н., Семиков В.Л. и др. Совершенствование управления в пожарной охране. В сб.: Вопросы экономики в пожарной охране, вып.6, ВНИИПО, 1977.

32. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации. Москва, "Наука", 1983, с.208.

33. Михалевич B.C., Сергиенко И.В., Шор Н.Э. Исследование методов решения оптимизационных задач и их приложения. Кибернетика, 1981, № 4, с.89-113.

34. Моисеев H.H. Элементы теории оптимальных систем. Москва, "Наука", 1975, с.528.

35. Моисеев H.H. Математические задачи системного анализа. Москва, "Наука", 1981, с.488.

36. Моисеев H.H., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. Москва, "Наука", 1978.

37. Прохоров Ю.В., Розанов Ю.А. Теория вероятностей. Москва, "Наука", 1973, с.496.

38. Разумихин Б.С. Задача об оптимальном распределении ресурсов. Автоматика и телемеханика. 1967, № I, с.62-74.- из

39. Риордан Дж. Комбинаторный анализ. ИЛ, 1963.

40. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. Москва, "Мир", 1973, с.302.

41. Семиков В.П. Проблемы создания АСУ в пожарной охране. В сб.: Вопросы экономики в пожарной охране, вып.З, ВНИЙПО, 1974.

42. Станевичюс А.-И.А. Особенности вычислительной схемы мультипликативного симплекс-метода на ЭЦВМ. Труды ВНИИ механизации сельского хозяйства, т.45, 1968, с.128-136.

43. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. Москва, "Наука", 1978.

44. Трубин В.А. О методе решения задач целочисленного линейного программирования специального вида. Доклады АН СССР, 1969, 189, № 5, с.952-954.

45. Туркин Б.Ф., Денисов Г.В. Автоматизированная система управления пожарной охраной крупного административного центра. В сб.: Пожарная профилактика, Москва, 1980, № 16, с.144-153.

46. Фаянс О.Г. Математические методы в управлении городскими транспортными средствами. Ленинград, 1979, с.152.

47. Федоренко Р.П. Приближенное решение задач оптимального управления. Москва, "Наука", 1978, с.488.

48. Федоров В.В. Численные методы максимина. Москва, "Наука", 1979, с.280.

49. Френк Г., Фриш И. Сети, связь и потоки. Москва, "Связь", 1978, с.488.

50. Юдин Д.Б., Голыптейн Е.Г. Линейное программирование. Теория и приложения. Москва, "Наука", 1969, с.424.- IB

51. P. Mesar w S.M Blum. Square toot ¿avsfor f/re £„gine /eespo„se nísta/7Ces /sanyement Science. Vol. /9, /to. /2, August ,g7¿

52. Carter, c. W fyaii, 6., "A Simulation MoM oj hre Jeparfment tPpera forts: Jkston W frtlumnary Pesults \ Itff rrantacftons tn

53. Systems Saense W Cuder/tetics Vot SSC-6 r/o.4, (tS?o), PP?8¿.M3

54. A ll oca t<y Man fmerpency (/nits A Suri/eu"

55. Vot. 19, /to. 4, Part II, (/ec, p.130. Management Science

56. Siting of fire Statins';Operational Research Quarterly /9, pp.

57. Seras. '-Simulation Cost effectiveness