Содержание к диссертации
Введение
ГЛАВА 1. Системологический подход к разработке крупномасштабных предметных областей управления (на примере ж.д. транспорта) 18
1.1. Состояние проблемы в условиях информатизации ж.д. транспорта 18
1.2. Концептуальные требования к системологическому подходу 23
1.3. Архитектурная концепция системологического подхода 25
1.4: Формирование метамодельного уровня 30
1.5. Классификация образующих ММ по группам родственных абстракций (комплексам и категориям) 37
1.6. Формирование категорий методологических решений (моделей и методов) 41
1.7. Выводы 47
ГЛАВА 2. Категория моделей и методов выбора оптимальной структуры управления 50
2.1. Постановка проблемной задачи 50
2.2.Разработка математической модели выбора оптимальной структуры управления 51
2.3.Анализ существующих методов выбора оптимальной структуры управления 54
2.4. Разработка алгоритма автоматической классификации 56
2.5. Разработка алгоритма выбора оптимальной структуры управления, основанного на потоковых построениях 65
2.6. Разработка алгоритмов потоковой оптимизации, основанных на агрегации информации 71
2.7. Выводы 87
ГЛАВА 3. Категория регулярных макромоделей и методов управления 90
3; 1. Постановка проблемной задачи 90
3.2. Разработка регулярных макромоделей управления вагонопотокамиt 92
3.3. Потоковые построения и преобразования регулярной модели 103
3.4. Методы анализа системы организации вагонопотоков, основанные на регулярных макромоделях 110
3.5. Выводы 116
ГЛАВА 4: Категория моделей и методов выбора маршрутов следования транспортных потоков 119
4.1. Постановка проблемной задачи 119
4.2. Системный анализ задачи выбора маршрутов 121
4.3. Разработка математических моделей выбора маршрутов следования 131
4.4. Разработка алгоритмов выбора маршрутов следования 141
4.5. Выводы 151
ГЛАВА 5. Категория моделей и методов распределения ресурсов в иерархических транспортных системах 154
5.1. Постановка проблемной задачи 154
5.2. Декомпозиционная модель и алгоритм распределения погрузочных ресурсов 158
5.3. Полиоптимизационная модель и алгоритм распределения погрузочных ресурсов 17 Г 5.4. Модели и методы перераспределения погрузочных ресурсов в условиях елабоформализованных целей и критериев 181
5.5. Выводы 188
ГЛАВА 6. Категория моделей и методов выбора оптимального плана формирования 191
6.1. Постановка проблемной задачи 191
6.2. Разработка математической модели выбора оптимального плана формирования 195
6.3. Разработка алгоритма выбора оптимального плана формирования, основанного на методе ветвей и границ 199
6.4. Модели и методы выбора оптимального плана формирования в условиях нечетких исходных данных 212
6.5. Выводы 225
ГЛАВА 7. Категория моделейи методов оптимизации структуры сортировочной работы на транспортной сети 231
7.1 .Постановка проблемной задачи 231
7.2. Разработка математической модели оперативной корректировки 243
7.3. Разработка алгоритмов оперативной корректировки 251
7.4. Распознавание ситуаций затруднений, требующих оперативной корректировки 258
7.5. Выводы: 263
ГЛАВА 8. Категория динамических моделей и методов управления транспортными потоками 270
8.1. Постановка проблемной задачи 270
8.2. Разработка обобщенной динамической модели управления транспортными потоками 274
8.3. Разработка методов векторной оптимизации динамических транспортных потоков 280
8.4. Анализ эффекта от учёта динамики при управлении транспортными потоками 294
8.5. Выводы 298
ГЛАВА 9. Категория моделей и методов поддержки принятия решений при управлении транспортными системами 302
9.1. Постановка проблемной задачи 302
9.2. Разработка имитационной модели поддержки принятия решений по управлению транспортными системами 309
9.3. Разработка алгоритма распознавания ситуаций при управлении транспортными системами 318
9.4. Функционирование имитационной модели в режиме «совета» 325
9.5. Построение имитационной модели задачи контроля погрузки по дорогам назначения и в затрудненные пункты выгрузки 330
9.6. Синтез модели и алгоритмов распознавания ситуаций при ортогональной структуре решающих правил 336
9.7. Выводы 350
Заключение 354
Литература 364
- Классификация образующих ММ по группам родственных абстракций (комплексам и категориям)
- Разработка алгоритма выбора оптимальной структуры управления, основанного на потоковых построениях
- Методы анализа системы организации вагонопотоков, основанные на регулярных макромоделях
- Модели и методы перераспределения погрузочных ресурсов в условиях елабоформализованных целей и критериев
Введение к работе
Актуальность темы: Решающая роль в стратегии развития ж.д. транспорта России в условиях проводимых радикальных экономических реформ; принадлежит процессу информатизации, обеспечивающему необходимой и достоверной информацией; все сферы управления транспортными; системами и производством.. Для решения принципиальных: научных, технических: и организационных проблем, возникающих в ходе этого процесса, разработаны Концепция и программа информатизации, которые утверждены, решением расширенной коллегииf МПС №5 от 28; февраля: 1996 года. Данными основополагающими документами установлено, что реализация процесса: информатизации в новых условиях должна осуществляться с помощью информационных технологий, центральными и действительно сложными элементами которых являются модели, методы и алгоритмы, Hat основе которых принимаются управляющие решения. Поэтому успешную информатизацию, а следовательно и решение проблемы реформирования ж.д. транспорта, невозможно осуществить без создания; и совершенствования развитого наукоемкого комплекса формальных моделей; прикладных методов и эффективных алгоритмов управления; транспортными системами, ілі производством:
В настоящее время в области - моделирования ь и і алгоритмизации систем; управления на ж.д. транспорте имеются фундаментальные теоретические исследования, выполненные АЛ. Петровым, К.А.Бернгардом,. Б.А.Левиным, Л.А.Барановым, Е.М.Тишкиным, Л:П.Тулуповым, В.А.Шаровым; В.Г.Шубко, А.Я;Калиниченко, Е.А.Сотниковым, ВіА.Буяновьім, П.А.Козловым, Т.А.Тибиловым, Ю.В.Дьяковым,. В.В.Виноградовым, А.А.Воробьевым, В.Ю.Гореликом, Е.В; Архангельским, А.ВіГорским, В.И.Галаховым, А.Ф.Бородиным, Н.Д.Иловайским, В.П.Феоктистовым, В.И.Некрашевичем, М:М.Болотиным,С.В.Дуваляном; И.К.Лакиным, В.К.Буяновой; В.И.Ковалевым, А.Т.Осьмининым, А.А.Аветикяном, В.М. Акулиничевым,, А.М:Макарочкиным; Ф.П.Кочневым, Ф.С.Гоманковым; В.А.Кудрявцевым и многими другими.
Вместе с тем, анализ современных условий функционирования» ж.д. транспорта показывает, что возникает ряд новых проблем, для которых, разработанный ранее методологический инструментарий оказался плохо приспособленным, и требуется і создание нового поколения моделей: и методов управления транспортными системами и производством. Очевидно, что реализация управляющих решений; принятых на основе неадекватных моделей и методов, может привести к тяжелым последствиям, а; возникшую проблему управления нельзя решить, даже за счет большого количества информации, пока не будут разработаны- адекватная- модель ш метод. Сегодня на ж.д. транспорте наблюдается! значительный разрыв между громадными: возможностями имеющихся; компьютеров и применяемыми машинными, алгоритмами решения? прикладных задач управления. Поэтому Концепция информатизация ж.д. транспорта требует не только обеспечения информацией существующих функциональных, задач управления, но и постоянную разработку принципиально новых более адекватных и эффективных моделей, методов и алгоритмов, позволяющих повысить обоснованность, качество и своевременность принимаемых управляющих решений. При разработке моделей и методов нового поколения возникает ряд проблем, требующих первоочередного решения.
Центральной проблемой являются трудности: построения глобальной модели управления для такой крупномасштабной системы, какой является ж.д. транспорт. Эти трудности вызваны огромным размером такого моделирования, наличием І большого числа противоречивых или плохо совместимых целей- и ограничений, отсутствием лаконичных и выразительных моделей и не могут быть разрешены на базе старых: подходов и методов, которые разобщенно рассматривают вопросы моделирования в устоявшихся? предметных областях управления с помощью традиционных видов математических моделей. Поэтому в условиях коренных, реформ необходимо создание развитой методологии формирования; органически целостного комплекса» взаимосвязанных и взаимодополняющих категорий моделей и методов управления нового поколения, обеспечивающих адаптацию управляющей системы» к изменившимся целямі функционирования ж.д. транспорта. Разнородность, формируемых категорий; требует созданияf единого универсального языка описания знаний о различных моделях и методах управления.
Особой проблемой, связанной с адаптацией управляющей системы к изменившимся условиям І и І требующей і обязательного решения при. разработке нового поколения моделей и методов; управления, являются вопросы совершенствования структуры этой системы. Выбор оптимальных структур управления транспортными системами и производством является сложной научной, задачей, для которой в настоящее время отсутствуют адекватные модели и методы решения. Эффективным подходом? к ее решению, позволяющим лучше адаптироваться к конъюнктуре перевозок, является разработка многоуровневых иерархических структур управления, путем оптимальной; декомпозиции транспортной сети на полигоны. С проблемой совершенствования структур управления? тесно связана проблема; создания, структурно-ориентированных методов оптимизации управляющих решений.
Принципиально новой проблемой при- формировании более адекватного поколения моделей и методов является отсутствие методологического инструментария компактного и наглядного макроуровневого моделирования, позволяющего давать единое описание и представление интегральных характеристик всей- системы управления потоками? на транспортной или производственной сети: Особую значимость разработка такой макромодели имеет для целей аналитического исследования системы организации вагонопотоков, обладающей слабыми: возможностями по анализу, из-за сложного комбинаторного характера и огромной размерности решаемых задач, которая оценивается « 2 допустимых вариантов решения.
Исключительно важной проблемой; возникающей в условиях экономических реформ, является резкое повышение роли субъективного фактора в процессе принятия управляющих решений. В этих условиях многие актуальные задачи • управления возникают в сложных контекстах социальных, экономических иг технических явлений, относятся к слабо - формализуемым И-могут быть реализованы только с помощью интеллектуального вмешательства человека. Необходимость учета; человеческого фактора с его уникальными возможностями классифицировать ситуации, вырабатывать цели, стратегии и: методы их достижения в условиях неопределенности, оперировать неполной: и неоднозначной информацией существенно усложняет математическое описание задач управления транспортными: системами; и производством; Поэтому в ситуациях; носящих субъективный і характер иг трудно; поддающихся формализации с помощью традиционных методов исследования операций, на передний план выдвигается разработка моделей и методов поддержки принятия управляющих решений. Такие ситуации; возникают при выборе маршрутов следования в условиях, когда только учет слабоформализуемых факторові позволяет выбрать маршруты следования; транспортных потоков, удовлетворяющие всем требованиям лица, принимающего решения (ЛПР). Роль» человеческого фактора особенно велика: в системах оперативного диспетчерского управления, задачах распределения: и; перераспределения погрузочных ресурсов и многих др. задачах управления. Разработанные в, данной работе модели и алгоритмы поддержки принятия решений основаны на методах теории полезности, штрафных и барьерных функций, распознавания и прогнозирования ситуаций- и сцен и др. теориях; их отличает большая интеллектуальная составляющая; предполагающая непосредственное участие ЛПР в процессе выработки управляющих решений.
Значительной; проблемой является; разработка адекватных моделей m методов дискретной комбинаторнойs оптимизации, поскольку в; условиях экономических реформ повышается роль именно дискретных задач управления транспортными системами ш производством. Важность данной? проблемы объясняется усилением требований к качеству и оперативности решения тех многочисленных задач управления, которым; в наибольшей степени» соответствует математика дискретных множеств или множеств, изменяющихся:
в дискретные моменты времени. Среди дискретных задач управления, рассматриваемых в. данной работе, следует отметить задачи; выбора и оперативной корректировки плана формирования,, концентрации и перераспределения сортировочной работы, динамического управления вагонопотоками, выбора маршрутов следования вагоно-и поездопотоков и др.. Сложность решения указанных задач: связана с тем, что многие из них относятся к «универсальным переборным задачам», для которых в настоящее время: отсутствуют эффективные методы и алгоритмы решения. Основная проблема\ решения; дискретных задач управления усугубляется четырьмя: дополнительными проблемами. Во-первых, многие рассматриваемые задачи являются многокритериальными, что существенно? усложняет поиск оптимального решения, т.к. требуется определить некоторый компромиссный результат, который в общем случае не является оптимальным ни по; одному критерию. Во-вторых, необходимо принимать во внимание существенно нелинейный характер ряда параметров решаемых задач управления, что позволит построить адекватные модели и методы, учитывающие, реальные возможности различных элементов транспортной сети по пропуску и і переработке вагоно- из поездопотоков. В-третьих, переменные условия функционирования ж.д. сети потребовали разработки адекватных динамических моделей; учитывающих нестационарный; характер решаемых дискретных задач управления. В-четвертых, сложность настоящего этапа реформирования ж.д; транспорта, трудность идентификации основных параметров новых задач управления и др. причины приводят к необходимости выработки управляющих решений на основе неточных, приблизительных и так называемых «нечетких» исходных данных,, для которых достаточно лишь указать их возможные значения5 относительно некоторого интервала достоверности.
Большая практическая значимость изложенных выше проблем обусловливает высокую актуальность выбранной темы и позволяет сформировать цель исследования..
Цель исследования: Основной целью настоящего исследования является создание и реализация • методологии и І соответствующего методологического инструментария разработки; нового поколения моделей и методов, которым предназначено обеспечить решение проблем управления, возникающих в условиях коренного реформирования и широкой информатизации ж.д. транспорта: Для достижения основной щели в диссертации также установлены подцели исследования; связанные с определением функциональных требований к управлению, выбором наиболее актуальных и принципиально новых функциональных задач управления, формированием и разработкой сложных и наукоемких категорий моделей и методов решения выбранных задач, а также их алгоритмической и программной реализацией на і единой интегрированной информационной основе.
Методика исследования:: Общий методический подход к достижению цели исследования заключается в использовании структурного анализа больших систем. В зависимости от конкретных подцелей и задач исследования также использовался следующий методологический инструментарий: моделирование и алгоритмизация транспортных систем и производств; математическое моделирование с помощью графов и І сетей; дискретная комбинаторная оптимизация; методы представления и обработки знаний; теория вероятностей; теория нечетких множеств; методы адаптации, обучения; распознавания и прогнозирования ситуаций; многокритериальная оптимизация; теория; многоуровневых иерархических систем І управления; методы регуляризации; линейное и нелинейное программирование; автоматическая» классификация; методы распределения ресурсов;: теория баз данных; методы поддержки принятия решений и др.
Научная новизна: В диссертации? исследован теоретический! подход к разработке нового поколения моделей,, методов и алгоритмов решения функциональных задач управления гранспортными системами и производством, содержащий следующие впервые полученные научные результаты:
I. Двухуровневую архитектуру Концепции информатизации ж.д. транспорта России, которая включает в; рассмотрение обеспечивающий і уровень, состоящий» из информационной, среды и инфраструктуры информатизации, и прикладной уровень информационных технологий. Центральными и действительно сложными элементами этих технологий являются модели, методы и алгоритмы решения функциональных задач управления.
П Системологический подход к разработке функциональных задач управления для- крупномасштабных транспортных систем; и производству базирующийся; на архитектурной концепции, двухмерной параллельной системе классификации используемого методологического инструментария; формировании категорий моделей и методов и универсальной фреймовой структуре для описания и использования знаний о модельных представлениях и методах работы с ними. Принципиальная новизна данного подхода заключается в том, что в качестве объекта исследования выступают не отдельные конкретные модели, а соответствующие классы — категории, которые могут интегрировать большое количество моделей с противоречивыми; нечеткими или плохо совместимыми требованиями и ограничениями, а также учитывать современные тенденции в развитии; «традиционных моделей».
III. Нижеперечисленные сложные и наукоемкие категории! моделей, методов и алгоритмов (с детализацией их научной новизны):
1. Выбора оптимальной структуры управления (модель, основанная на декомпозиции, исходной транспортной сети на непересекающиеся; подсети меньшей размерности; приближенный алгоритм декомпозиции, требующий для своей реализации построения минимального остовного дерева; теоретически обоснованный» эффективный алгоритм декомпозиции, использующий) понятие окрестности вершины графа и потоковые преобразования; теоремы агрегирования, носящие конструктивный характер и позволяющие существенно понизить размерность исходной задачи выбора оптимальной- структуры, а также построить эффективный алгоритм поиска максимального потока в сети).
2. Регулярных макромоделей и методов управления (способ компактного и наглядного представления комбинаторных транспортных задач большой размерности с помощью методов; регуляризации решетками исходной транспортной или производственной сети; «алгоритм половинной нумерации», обеспечивающий свойство строгого упорядочения=номеров опорных элементов в определенных направлениях сети; макромодель системы организации вагонопотоков; приближенное выражение целевой функции, задачи выбора оптимального плана формирования, в котором отсутствуют трудности комбинаторного характера, что обеспечивает проведение: ряда аналитических исследований).
3. Выбора маршрутов следования корреспонденции транспортных потоков (необходимое условие локализации различных частей корреспонденции на одном маршруте; модели и алгоритмы, учитывающие с помощью инструмента штрафных и барьерных функций дополнительные субъективные ограничения ЛПР, а также технологические ограничения на загрузку элементов сети; как при условии обязательного сосредоточения одной корреспонденции на одном маршруте, так и без него).
4. Распределения ресурсов в иерархических транспортных системах (двухуровневая иерархическая модель задачи? распределения погрузочных ресурсов и декомпозиционный! алгоритм ее решения; многокритериальная модель задачи комплексного регулирования погрузочными ресурсами и эффективный алгоритм ее оптимизации, который представляет собой некоторую?комбинацию «метода ограничений» и «метода свертки»; модели и алгоритмы перераспределения погрузочного ресурса в условиях его дефицита и при множестве слабоформализованных целей и критериев).
5. Выбора оптимального? плана формирования; (модель выбора оптимального плана формирования с учетом ограничений на число путей и перерабатывающие способности: станций, которая представляет собой двойственную к классическим подходам: задачу оптимизации нелинейной целевой функции на дискретном множестве решений комбинаторного типа;
общий алгоритм оптимизации, основанный на методе ветвей и границ и построении верхних Иг нижних границ целевой функции и ограничений, который обеспечивает плану «устойчивость в малом»; частные алгоритмы, позволяющие улучшить временную ш емкостную сложность вычислений;
У обобщение разработанных моделей и алгоритмов на случай нечеткой информации).
6. Оптимизации структуры сортировочной работы, (многокритериальная модель и универсальный алгоритм оперативной t корректировки плана формирования, основанные на выделении потокозависимых станций и эквивалентных потоковых преобразованиях; алгоритм распознавания ситуаций, требующих оперативной корректировки; модели и алгоритмы; оперативной корректировки специального вида, предназначенные для выделения сверхдальних магистральных назначений и снижения уровня «угловых потоков»; модель концентрации и перераспределения сортировочной работы, представленная как трехэтапная задача оптимизации, и алгоритм ее решения)..
\УУ 7. Динамических моделей:и методов управления транспортными потоками
(динамическая модель, управления с лексикографически упорядоченными критериями оптимизации и весами, заданными с помощью вектор-функций; эффективные алгоритмы оптимизации, основанные на топологическом свойстве ацикличности «расширенной во времени» исходной сети; понятие «эффекта от учета динамики», определяемого с помощью двухкомпонентного вектора; и его анализ; частные модели и алгоритмы для перспективных областей применения динамического потока на ж.д. транспорте).
8. Поддержки принятия решений при управлении транспортными системами (методологический подход к «интеллектуализации» информационных технологий на ж.д. транспорте; имитационная модель ( • поддержки принятия і решений, основанная на методах адаптации и = обучения, распознавания ситуаций и выборе информативных признаков; анализ влияния и способы компенсации «неидеальности» реального учителя на процесс обучения имитационной модели; алгоритм распознавания ситуаций, основанный на ортогональной структуре решающих правил и понятии «информационной точки»; подход к выбору наиболее информативных признаков для распознавания ситуаций; использующий понятие «ценности информации»).
Практическая ценность исследования состоит в создании научно обоснованного подхода к разработке нового поколения моделей и методов управления транспортными системами в современных условиях реформирования и широкой«информатизации ж.д. транспорта. Его реализация позволяет построить более адекватные и принципиально новые модели и; высокоэффективные: методы и алгоритмы, являющиеся органической, составной частью перспективных информационных технологий управления. Практическое использование предложенного подхода обеспечивает: создание новых информационных технологий, удовлетворяющих условиям открытости, гибкости и адаптируемости к изменяющимся условиям функционирования транспортных, систем; высокую скорость разработки и развития комплекса моделей и методов; интеграцию существующих и вновь разрабатываемых моделей и методов управления в соответствующих категориях, что позволяет осуществить важнейший принцип проектирования информационных технологий, заключающийся в однократности любой разработки: и многократности и многоаспектное™ ее использования. Внедрение исследования позволяет: существенно улучшить эффективность использования ресурсов, участвующих в транспортном процессе,, путем повышения транзитности вагонопотоков и уменьшения числа нерациональных их переработок, сокращения; порожнего пробега и ускорения доставки грузов, усиления ритмичности, снабжения грузами получателей и погрузочными! ресурсами грузоотправителей»и, как следствие такого улучшения, высвободить, часть ресурсов для дополнительных перевозок; повысить качество управления транспортными системами за счет детальности, точности? и оперативности выработки управляющих решений; обеспечить принятие мер упреждающего управления для ликвидации прогнозируемых затруднений в работе транспортных систем. Практическую значимость выполненного исследования •,
усиливает универсальность ряда разработанных категорий моделей и методов, позволяющая их использовать при создании систем управления производством.
Реализация работы: Результаты исследования использовались при разработке ряда документов государственного и отраслевого значения, важнейшими из которых являются следующие: «Общегосударственная Концепция и программа: информатизации общества (раздел ж.д. транспорт)»; «Программа создания новых интеллектуальных информационных технологий на: ж.д. транспорте», выполненная: по заданию ГКВТИ (№ ЦША-2/176 от 20.08.90 г.); «Концепция и программа информатизации ж.д. транспорта России», утвержденные решением расширенной Коллегии МПС 28.02.96 г. Указанные документы явились основой- для реализации процесса информатизации на ж.д. транспорте, а годовой экономический эффект от их внедрения оценивается в 1.93-2.25 млрд. руб. Разработанные в диссертации методические положения и; архитектурные решения вошли также в утвержденные МПС методики, ТЗ и ТП, в числе которых следует отметить: «Системный проект информационной системы ж.д. транспорта» (10.00.76/95.00.00. № 29 от 29.01.96 г.); ТЗ и ТП «Автоматизированная система для управлениям грузовыми перевозками с распределенным банком данных о поездах, вагонах и грузах»; ТЗ и ТП «Информационная среда для обеспечения функционирования новых информационных технологий» (04704353.19300.001 ТЗ и П6); «Технические требования к ГИС ж.д. транспорта» и др.
Диссертационное исследование также реализовано в многочисленных прикладных разработках и приложениях, из которых перечислим только наиболее значимые. Во-первых,, модели и методы поддержки принятия решений, выбора структуры: управления и распределения ресурсов получили применение при создании управляющего режима диалоговой системы контроля и управления работой сети ж.д. (ДИСКОР), внедренной в промышленную эксплуатацию (приказ МПС № А-20528, годовой экономический: эффект от внедрения составляет около 13.9 млн. руб.). Во-вторых, результаты исследования, связанные с выбором маршрутов следования, оптимизацией структуры сортировочной работы и выбором плана формирования использовались при реализации комплексной программы перспективного развития и размещения сети сортировочных станций (целевая программа № П-23302); проведении по заданию МПС и- ряда дорог расчетов, связанных с оперативной корректировкой плана формирования и маршрутов следования вагонопотоков; выборе сверхдальних магистральных назначений; снижению уровня «угловых потоков», концентрации и перераспределению сортировочной работы в условиях сильного спада объема перевозок (годовой экономический эффект от реализации только одного локального варианта концентрации и перераспределения составляет несколько і сотен тысяч рублей). В-третьих, разработанные модели и алгоритмы; интегрированы в рамках геоинформационной системы «Электронная карта», которая отражает состояние сети ж.д. России, стран СНГ и Балтии (свыше 9 тыс. раздельных пунктов) и в настоящее время используется в нескольких департаментах и диспетчерском; центре МПС, установлена у руководства МПС (всего 37 рабочих мест), эксплуатируется в рамках КИВС МПС и ПКБ ГПУ МПС, а в сфере производства нашла применение в ERP-проекте МПС для управления материальными, финансовыми, трудовыми и, др.. видами ресурсов; (годовой экономический эффект оценивается в 27 млн: руб.)..
Апробация; работы: Материалы исследования и результаты работы докладывались, рассматривались и; получили одобрение на следующих конференциях, заседаниях и совещаниях: Всесоюзной научно-технической конференции «Опыт создания и внедрения і О АСУ,. АСУП и АСУТП на видах транспорта и перспективы развития АСУ для обеспечения \ координированной работы транспорта» (Ленинград, 1976 г.); Всесоюзном научно-техническом семинаре «Пути» повышения надежности АСУ» (МДНТП, 1980 г.); V-OM совместном; цикле расширенных заседаний научно-исследовательских семинаров по дискретной математике (ЮНЦ АН УССР) и по графам и гиперграфам (АН МССР КГУ) под преде. проф.А.А. Зыкова (Одесса, 1981 г.); Всесоюзной научно-технической конференции «Проблемы автоматизации управления перевозочным процессом» (Харьков, 1982 г.); Всесоюзной научно-технической конференции «Пути совершенствования перевозочного процесса и управления транспортом» (Гомель, 1985г.); П-ой международной научно-технической конференции «Актуальные проблемы развития ж.д. транспорта» !? (Москва, 1996 г.); заседаниях Коллегии МПС РФ (№6 от 22.03.95 г. и расширенном заседании 28.02.1996 г., посвященном проблеме информатизации ж.д. транспорта); совместном заседании комиссий по вычислительной технике и автоматизации: и эксплуатации НТС МПС под преде, проф. К.А. Бернгарда (протокол от 20.10.81г.); совместном заседании секций «Управление перевозочным процессом» и «Автоматика, связь и вычислительная техника» НТС МПС (протокол от 29.04.86 г.); сетевом совещании по организации вагонопотоков (Москва, 1983 г.); научно-технических советах отделений «Вычислительной техники», «Управления перевозочным процессом», «Общесетевых вопросов» (ВНИИЖТ, 1980-1987 г.г.) и «Автоматизированных систем управления» (ВНИИЖА, 1988-1995 г.г.); заседаниях кафедры АСУ v{ МИИТа (1974 г. — н. вр.); сетевых научно-технических совещаниях начальников и главных инженеров служб перевозок (Голицино, 1996-1999 г.г.). Интегрированная система «Электронная карта» представлялась на выставках «ЭкспоТранс 99», «ЭкспоЖд», «Корпоративные сети и системы связи 2000», «Международная транспортная 2000» и была удостоена золотой медали Всероссийского выставочного центра (ВВЦ), а диссертант — присвоения звания «Лауреат ВВЦ».
Работа квалифицируется как теоретическое обобщение и решение крупной научно-технической проблемы создания і нового поколения моделей и алгоритмов функциональных задач управления транспортными системами и производством, имеющей важное хозяйственное значение для развития ж.д.
Ц транспорта страны.
Классификация образующих ММ по группам родственных абстракций (комплексам и категориям)
Формирование метамодельного уровня основано на создании метамодели, представляющей логическую структуру всей предметной- области и: являющейся промежуточным этапом на пути к модельному уровню (рис.1.3).
Создание метамодели; отвечает требованиям парадигмы целостности и органического единства рассматриваемой сложной; системы проблем и задач; Метамодель позволяет охватить рассматриваемую систему целиком и играет роль необходимого «структурно-логического каркаса» или «контактной поверхности», определяющей границы между конкретными явлениями и абстрактными конструкциями уровня математических моделей. В метамодели (ММ) представляются основные сущностные модели рассматриваемой предметной области, детали- которых скрыты (инкапсулированы). В; процессе построения ММ создается, трактуемая с единых логических позиций, система? частных локальных моделей, с низким уровнем описания; и отношений между этими моделями, отражающая в единой сжатой» и компактной форме разные аспекты функционирования сложной системы. ММ действует в качестве формальной памяти сложной системы иt обеспечивает полезный базис для извлечения требований; к системе. В ММ предусматривается определение входных и выходных значений, функциональных зависимостей, производится описание того, что делает каждая функция, осуществляется выработка критериев оптимизации. Основными требованиями к ММ; являются полнота и адекватность. ММ создается:как средство достижения основных целей управления сложной системы и позволяет осуществить плавный переход от анализа системы, к разработке локальных математических моделей. При построении ММ осуществляется последовательный переход от вербального, без должной формализации, уровня декларативного описания цели функционирования всей системы до спецификаций; логически взаимосвязанных локальных математических моделей функциональных задач и данных; с помощью которых реализуется эта цель.
В основу разрабатываемого методологического инструментария построения ММ положены: методы структурного и объектно-ориентированного анализа (рис. 1.3).
Начальная или, исходная цель управления; сложной; системой является категорией максимальной степени абстракции, обычно представленной в качественном виде. Поэтому рассмотрение сложных предметных областей требует привлечения иерархических принципов декомпозиции цели управления по методу «сверху-вниз», с последующим синтезом общего модельного решения.
Разработка функциональной и информационной составляющей ММ является итеративным; многоуровневым процессом (рис. 1.6). На»основе цели; функционирования системы формируются исходные функциональные задачи, а также структура? их взаимодействия. Исходные функциональные задачи идентифицируют ключевые функции, которые должна реализовать система управления для достижения поставленной начальной цели. Требование выполнения; функциональной задачи і-го уровня представляет цель для следующего (і+1 )-го уровня декомпозиции. Уровни описания целей и подцелей образуют иерархию в соответствии с уменьшением сложности: описания элементов: цели і-го уровня делят на; подцели, которые могут быть в дальнейшем декомпозированы до нужного уровня детализации. На самом: нижнем уровне вложенности, представляющем непосредственно содержание ММ; находятся атомарные (неделимые) г функциональные задачи. Эти терминальные задачи имеют самостоятельные значения и представляют собой логически целые части, для которых нет необходимости декомпозиции. При перемещении центра внимания по иерархической древовидной структуре, изображенной на рис. 1.6, рассмотренные ранее цели и функциональные задачи переходят во внешнюю среду, представляя внешние сущности І (терминаторы), расположенные вне контекста системы.
Процесс построения ММ представляет собой единый подход как для обследования и анализа предметной области, так и для описания результатов проектирования информационной системы управления. Разработанный подход позволяет существенно снизить сложность построения ММ путем введения соответствующих: уровней абстракции и дает наглядное представление таких существующих базовых понятий АСУ, как функциональная система, суперсистема, подсистема, задача и подзадача.
При формировании образующих элементов ММ за основу выбраны конструктивные блоки методологий SADT [8] и DFD [9], которые, с целью дальнейших методологических использований, подвергаются модификациям; Также вводятся дополнительные правила; устанавливающие способы соединения и представления этих элементов.
Для. идентификации классово методов или методологических инструментальных средств, которые требуются І для реализации элементов ММ, отражающих состав функциональных задач и данных, вводится дополнительная пространственная координата методов или методологических инструментов (рис. 1.7). На рис. 1.7 представлены две разные методологические иерархии, ортогональные друг к другу и принадлежащие одному процессу разработки ММ. Каждая иерархия и ее проекция относятся к определенному аспекту разработки ММ, а все вместе они определяют ММ с должной степенью полноты, правильности и адекватности.
Разработка алгоритма выбора оптимальной структуры управления, основанного на потоковых построениях
Разработка и совершенствование методов управления транспортными системами (оперативная; корректировка плана формирования, распределение погрузочного ресурса и др.) связаны с применением структурно-ориентированного подхода. Применение структурно-ориентированного подхода первоначально предполагает выбор оптимальной; структуры управления; на? транспортной І сети и предусматривает рациональное распределение; функций между отдельными органами управления. Для; эффективного управления сложной, системой1 необходима иерархическая; например двухуровневая структура управления; подразумевающая декомпозицию, системы на определенное число подсистем І нижнего уровня, координируемых более высоким уровнем. Задача координации управления подсистемами нижнего уровня является тем проще, чем проще получающаяся в результате декомпозиции агрегированная система управления, то есть,. чем более автономны, независимы друг от друга подсистемы і нижнего уровня, иначе, чем меньше совокупные связи между подсистемами нижнего уровня.
Таким образом, задача; выбора оптимальной структуры является задачей декомпозиции графа транспортной сети; по какому-либо критерию. Необходимость, такой декомпозиции следует из большой размерности и сложности решаемых задач управления и, как правило, экспоненциально растущей трудоемкости алгоритма управления при увеличении размерности. Практическое использование декомпозиционного подхода позволит резко сократить объемы информации, передаваемой на верхний уровень, а также уменьшить нерациональные перевозки. От качества решения задачи деления; системы управления на слабосвязанные между собой подсистемы во многом, зависит эффективность решения, задач управления на транспортной сети. Разработке эффективных методов решения задачи структуризации системы управления и посвящается данная глава.
Следует отметить, что представленная проблемная задача имеет более широкую сферу приложений, чем только управление на сети железных дорог. На этапе разработки и проектирования любой информационно-управляющей системы обычно приходится рассматривать систему объектов, между которыми существуют некоторые отношения «близости» или взаимосвязи. Например, это может быть система предприятий, взаимосвязи между которыми характеризуются, объемами поставок продукции предприятия і предприятию j. Это может быть также совокупность станций на сети железных дорог, с заданными величинами вагонопотоков между ними; Другие примеры: система понятий при построении словарей и тезаурусов информационно-поисковых языков; информационно-логические схемы алгоритмов и программ; сети связи; пункты, обслуживания клиентов и т.д. Математические модели указанных систем объектов формулируются в терминах теории графов. Значения меры близости, как правило, распределены между объектами неравномерно. Поэтому, в системе объектов можно выделить структуру слабосвязанных между собой групп объектов, т.е. разбить систему на подсистемы относительно близких друг к другу объектов.
В настоящей работе предлагаются достаточно простые в вычислительном отношении алгоритмы решения задачи структуризации систем, представленных графами. Тогда проблема выбора оптимальной структуры ставится как задача разбиения множества {Я}на агрегаты {Rj} ({RJ}G{R}), j = 1Д, где к — фиксированное число агрегатов, обладающих заданными характеристиками связей. Ввиду того, что отношения взаимосвязи распределены между первичными объектами неравномерно, задача выбора рациональной структуры может быть поставлена как задача нахождения такого разбиения (декомпозиции) на к агрегатов, которое обращает в экстремум некоторый выбранный критерий С. Структуризация графа транспортной сети Г на агрегаты является многокритериальной проблемой ввиду того, что граф Г отражает структуру сети железных дорог, а на этой сети могут решаться самые различные задачи управления. Выделим следующие критерии и ограничения решения задачи декомпозиции графа транспортной сети Г: 1. Критерий минимума суммарного веса связей между агрегатами. Выполнение этого условия обеспечивает известную независимость агрегатов, необходимую для структурно-ориентированного решения поставленной задачи управления. Вес связей между первичными объектами / и/ можно задать следующими соотношениями: Минимизация первого и второго критериев при соответствующих ограничениях является сложной задачей дискретного программирования. В настоящее время не существует эффективного алгоритма ее решения. Одним из подходов к решению задачи структуризации является выбор только одного критерия, приемлемого для широкого класса задач управления на" графе.77. В [51] показано, что при достаточно; широких предположениях задача выбора рациональной структуры сводится к минимизации суммарного числа внешних связей между агрегатами. Все связи между объектами задаются в виде квадратной симметрической матрицы соединений W = \\WyW, где i,j = \;m. Естественной математической постановкой задачи оптимальной декомпозиции исходной транспортной системы является задача разбиения (разреза) множества вершин графа Г, моделирующего железнодорожную сеть, на совокупность из к подмножеств (регионов разреза), каждое из которых содержит одну из выделенных -вершин. При этом разбиение должно минимизировать сумму весов ребер, концы которых принадлежат разным регионам разреза, или, что то же самое (двойственная задача), максимизировать сумму весов внутренних ребер разреза. Отметим, что возникшая задача нахождения минимального разреза графа между выделенными & вершинами, в случае k=2 соответствует классической задаче, рассматриваемой в теории Форда-Фалкерсона [159] и эффективно решаемых с помощью алгоритма пометок (алгоритм Форда-Фалкерсона).
Методы анализа системы организации вагонопотоков, основанные на регулярных макромоделях
Различные задачи управления вагоно- ш поездопотоками вызывают необходимость создания компактной и наглядной математической модели, которая давала бы» единое описание и представление интегральных характеристик всей системы управления потоками, на транспортной сети.. Рассмотрим проблему разработки такой макромодели на примере основной задачи управления вагонопотоками - выборе плана формирования одногруппных поездов. Необходимость ее разработки вызвана сложным комбинаторным характером задачи выбора плана формирования и ее слабой обозримостью, возникающей из-за огромной размерности, которая оценивается « 2 допустимых вариантов решения. В пользу построения макромодели говорит и опыт человеческой деятельности, когда; в процессе выбора и анализа плана формирования лицо, принимающее решения (ЛПР), осуществляет многократные взаимные переходы между макроуровнем исследования: системы: (полигоны, экономические зоны, направления) и микроуровнем.работы с отдельными струями вагонопотоков.
Разрабатываемая макромодель должна удовлетворять следующим, достаточно жестким; требованиям, выполнение которых необходимое как для анализа, так и синтеза системы организации вагонопотоков: 1. Отражать качественную картину процедуры выбора плана формирования, т.е. наглядно и обозримо, описывать различные; массовые построения и преобразования, связанные как со структурой исходного графа опорных станций, так и со структурой синтезируемого графа назначений Н; 2. Позволять удобно физически интерпретировать процесс расчета, т.е. устанавливать взаимнооднозначное соответствие между физическими характеристиками системы, организации вагонопотоков и различными результатами операций, связанных с вычислениями как на глобальном, интегральном уровне, так и на локальном, дифференциальном уровне работы с отдельными струями вагонопотоков; 3. Удобно осуществлять процесс выбора плана формирования, т.е. при выборе плана формирования легко производить необходимую трансформацию потоковой схемы, определяемой фиксацией заданных назначений и способом прикрепления струй вагонопотоков к этим назначениям; 4. Иметь такие топологические свойства элементов модели, которые позволяли бы использовать самые эффективные алгоритмы, оптимизации, включая и алгоритмы параллельных вычислений; 5. Давать как графотеоретическую, на локальном уровне, так и регулярную, на глобальном уровне, интерпретацию хода расчета и легко переходить от одной к другой, используя графовые методы устранения «локальных дефектов», возникающих в регулярной постановке; 6. Производить агрегацию информации и естественную декомпозицию; задачи по полигонам, необходимую как для целей расчета, так и для-организации оперативной корректировки сетевого плана формирования; 7. Позволять расширять модель за счет учета дополнительных влияющих факторов и ограничений; 8. Давать удобный инструмент для описания общесистемных показателей и проведения аналитических исследований системы организации вагонопотоков, включая следующие исследования: а) оценка средней длины назначения и влияние на неё различных факторов; б) анализ изменения основных показателей системы организации вагонопотоков при; развитии системы, в том числе при концентрации сортировочной работы на ряде станций; в) исследование плана формирования на чувствительность к изменениям вагонопотоков и выбор оптимальной периодичности его расчета; г) анализ надежности плана формирования и его устойчивости к случайным возмущениям и др. Основные подходы к разработке такой макромодели рассматриваются, ниже. Главной проблемой при её создании является выбор способа компактного описания системы организации вагонопотоков, так как работа с графовым описанием комбинаторных систем большой размерности становится сложной и труднообозримой, что существенно затрудняет их качественное исследование. Поэтому требуются новые методы представления таких систем, которые обладали бы достаточной наглядностью и сочетались бы с уже применяемыми методами теории графов и матриц. Разработка регулярных макромоделей управления вагонопотоками Известно, что для решения; и качественного анализа» непрерывных задач хорошо развиты и успешно применяются; различные методы регуляризации [168-169]. Более того, системный подход к изучению сложной ПО всегда должен базироваться на том или ином методе регуляризации В противном случае не будет ничего стабильного, что поддавалось бы изучению, никакой! структуры, к раскрытию которой можно было бы стремиться [151]. Представляется перспективным использовать этш методы ив комбинаторных задачах, к которым относится рассматриваемая задача расчета плана формирования. В настоящей работе выбран метод регуляризации, основанный на построении регулярной сети, которая представляет собой достаточно общую математическую конструкцию. Поэтому выбор конфигурации регулярной сети і представляет самостоятельную задачу.
Модели и методы перераспределения погрузочных ресурсов в условиях елабоформализованных целей и критериев
При выборе назначения: (г,s), а, следовательно, и выращенном дереве, все вагонопотоки, «стекающие» по ветвям дерева в. корень (г,s), жестко прикрепляются к назначению (r,s); Этот факт может быть использован для; последовательной, декомпозиции задачи на подзадачи меньший размерности. Декомпозиция І осуществляется! путем і следующей? перестройки матрицы; вагонопотоков: Пусть [r,s) - фиксированное назначение, Щ- одна из цепей выращенного дерева, которая ведет в. корень (r,s), а Щ -произвольный вагонопоток, принадлежащий цепи Щ (рис.3.10). Тогда декомпозиция задачи і осуществляется путем перехода от матрицы Nij к редуцированной; матрице Nyr, представленной на рис. 3.10, в которой новый; элемент элементы Nir и Nffr образуются путем простой суперпозиции старых элементов Nir и Nsfr с вагонопотоком Щ: При такой декомпозиции осуществляется резкое уменьшение размерности задачи, так как обнуляется значительная часть вагонопотоков, связанных с деревом, выращенным на (r,s). При выполнении» процедуры параллельной? диагонализации матрицы вагонопотоков, в процессе которой осуществляется проекцияJ элемента (г,У) одновременно на два соседних (i,j — l) и (/ + 1 ")» необходимо обеспечить условие сохранения мощности матрицы вагонопотоков. Данное: условие; обеспечивается, путем проекции отрицательного значения элемента (i,j) на элемент (/ + 1,/-1). При; этом исходная матрица как бы упаковывается в другую, имеющую большее число нулевых элементов. Рассмотренная выше математическая модель и потоковые построения, осуществляемые с ее помощью, положены в основу различных высокоэффективных алгоритмов анализа и синтеза системы организации вагонопотоков. Построенные ранее регулярные макромодели и методы позволяют достаточно просто аналитически, без использования компьютера; исследовать поведение системы организации вагонопотоков на качественном уровне. Рассмотрим пример использования этих методов для-случая, когда регулярная г модель представлена в виде упорядоченной матрицы вагонопотоков Ny. Примем во внимание, что существует несколько стратегий организации вагонопотоков относительно опорных станций, участвующих в сортировочной; работе. Наиболее простой, однако нерациональной, является стратегия, когда не существует сквозных назначений; а все вагонопотоки перерабатываются в; участковых назначениях, т.е.. в назначениях, сформированных между соседними станциями. Более рациональной является стратегия, когда; вагонопотоки могут перерабатываться как в длинных - сквозных, так ив участковых назначениях. В этом случае можно предположить, что каждая /-я опорная станция «обслуживает поездами» определенную зону, граница которой лежит на расстоянии / от этой станции и. выделена на упорядоченной І матрице нумераций / (рис.3.11). На границу зоны вагонопотоки «выносятся» в магистральных (сквозных) назначениях. В процессе переработки вагонопотоков Щ , длина которых больше / (рис.3.11), они сначала прикрепляются к магистральным назначениям, а затем к назначениям, выделенным внутри зоны. При выборе стратегии прикрепления вагонопотоков к назначениям, лежащим внутри зоны, можно исходить из! предположения, что внутри зоны вагонопотоки перерабатываются Стратегия организации вагонопотоков только в участковых назначениях (см. верхнюю половину вьщеленных на рис. 3.11 зон). Более общим, однако, является случай, когда внутри выделенной; зоны вагонопотоки могут перерабатываться как в участковых, так и в сквозных назначениях (см. нижнюю половину выделенных на рис.3.11 зон). Известно [176]; что целевая функция задачи выбора оптимального плана формирования имеет следующий вид: Выполним качественный анализ этой функции при общей стратегии, когда внутри выделенной зоны A,B,C,D вагонопотоки могут перерабатываться и в сквозных назначениях. С целью упрощения структуры целевой функции введем следующие обозначения: cm- среднее значение вагоно-часов накопления на одно назначение; Н - суммарное число назначений, выделенных относительно графа G; N - среднее значение корреспонденции вагонопотока между і -йи j-u станциями, где ij=l;n2. Тогда целевую функцию (3.1), имеющую составляющую накопления FHaK и переработки F„ep, можно приближенно записать в следующем виде: Число назначений Н можнолибо оценить приближенно, либо взять из действующего плана формирования. При оценке Л" существенное значение имеет выбор стратегии прикрепления вагонопотоков к назначениям, лежащим внутри зоны. Обозначим /(/) число назначений, формируемых і-й станцией, которое является функцией размера зоны /, где /=1; п 2.
