авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |   ...   | 17 |
-- [ Страница 1 ] --

Институт проблем управления

им. В.А. Трапезникова РАН

УПРАВЛЕНИЕ

БОЛЬШИМИ

СИСТЕМАМИ

Специальный

выпуск 30.1

СБОРНИК

ТРУДОВ

Ноябрь 2010

Сетевые модели в управлении

ISSN 1819-2467

Регистрационный номер Эл №ФС77-27285 от 22.02.2007

Москва – 2010

www.mtas.ru/about/smartman

Проект «Умное управление»

на Интернет-сайте теории управления организационными системами www.mtas.ru Одна из ключевых тенденций XXI века – появление первых примет наступления эпохи «умной» экономики, экономики зна ний. Она заставляет пересмотреть место человека в контуре управления. В современном менеджменте остро ощущается необходимость перехода от несистематизированного и подав ляющего своим объемом набора лучших практик к комплексу инструментов управления.

Целью проекта "Умное управление" является разработ ка научного подхода к конструированию таких инструментов – механизмов управления – учитывающих активность сотрудни ков, на основе теоретического анализа (теории активных систем) и обобщения передового опыта участников проекта.

В планах проекта:

1. Разработка программного комплекса имитационных моделей механизмов управления.

2. Разработка комплексного учебного курса "Механизмы управ ления" для студентов управленческих и экономических специ альностей высших учебных заведений.

3. Проведение комплексных прикладных исследований в облас ти управления в социальных сетях.

Приглашаем к сотрудничеству профессионалов в об ласти организационного управления.

http://www.mtas.ru/about/smartman/mechanism Механизмы управления Мультифункциональное учебное пособие, разработанное в рамках проекта «Умное управление»

Мультифункциональное учебное пособие «Механизмы управле ния», вышедшее в издательстве УРСС, является первым результа том проекта «Умное управление».

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

Редколлегия сборника "Управление большими системами" сотрудничает со многими научными и общественными организациями:

ФГУП НТЦ "Информрегистр" по указанию Правительства РФ осуществляет регистрацию электронных научных изданий, публикация в которых приравнивается ВАКом к опубликованным работам, отражающим основные результаты диссертационной работы. Сборник трудов "Управление большими системами" с 2006 года зарегистрирован НТЦ "Информрегистр".

Научная электронная библиотека eLIBRARY.RU - это круп нейший российский информационный портал в области науки, технологии, медицины и образования, содержащий рефераты и полные тексты более 12 млн научных статей и публикаций. Все выпуски сборника трудов "Управление большими системами" доступны в открытом доступе на платформе eLIBRARY.RU.

Общероссийский математический портал Math-Net - это общероссийский математический портал, предоставляющий российским и зарубежным математикам различные возможности в поиске информации о математической жизни в России. Все выпуски сборника трудов "Управление большими системами" доступны в открытом доступе на платформе MathNet.Ru.

Всероссийский институт научной и технической информа ции РАН – это крупнейший российский и мировой информаци онный и аналитический центр. Все выпуски Сборника трудов "Управление большими системами" обрабатываются ВИНИТИ, включаются им в базу данных и реферативный журнал.

Издательство "МАИК Наука" при поддержке Российской ака демии наук издает более 180 академических журналов на анг лийском языке и совместно с Академиздатцентром Наука – более 200 журналов на русском языке практически по всем направлениям современной науки. С 2010 года Сборник трудов «Управление большими системами» сотрудничает c выпускае мым издательством МАИК Наука журналом «Автоматика и телемеханика», что предполагает опубликование избранных статей Сборника на английском языке в выпускаемом издатель ством МАИК «Наука» журнале «Automation and Remote Control»

(английская версия журнала «Автоматика и телемеханика»).

Подробнее о программах сотрудничества со Сборником УБС – на официальном сайте ubs.mtas.ru РОССИЙСКАЯ АКАДЕМИЯ НАУК Институт проблем управления им. В.А. Трапезникова УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ СБОРНИК ТРУДОВ Специальный выпуск 30. Сетевые модели в управлении Москва – УДК 519 ISSN 1819- ББК 32. У Управление большими системами / Сборник трудов. Специальный выпуск 30. «Сетевые модели в управлении». М.: ИПУ РАН, 2010. – 816 с.

Дата опубликования: 15.11.2010.

КООРДИНАЦИОННЫЙ СОВЕТ Академики РАН: Васильев С.Н., Емельянов С.В., Коровин С.К., Куржанский А.Б., Федо сов Е.А., Черноусько Ф.Л.;

члены-корреспонденты РАН: Желтов С.Ю., Каляев И.А., Пархоменко П.П., Попков Ю.С.;

д-ра техн. наук: Бутковский А.Г., Дорофеюк А.А., Куз нецов О.П., Кульба В.В., Кротов В.Ф., Лотоцкий В.А., Павлов Б.В., Поляк Б.Т., Рутков ский В.Ю.

РЕДАКЦИОННАЯ КОЛЛЕГИЯ Главный редактор: член-корр. РАН Новиков Д.А. Отв. секретарь: к.т.н. Губко М.В.

Д-ра техн. наук: проф. Алескеров Ф.Т. (ГУ ВШЭ), проф. Артамонов Е.И. (ИПУ РАН), д р экон. наук, проф. Архипова М.Ю. (ИПИ РАН), д-ра техн. наук: проф. Афанасьев В.Н.

(МИЭМ), проф. Бахтадзе Н.Н. (ИПУ РАН), проф. Бурков В.Н. (ИПУ РАН), проф.

Вишневский В.М. (ИППИ РАН), д-р экон. наук, проф. Голиченко О.Г. (ЦЭМИ РАН), д-р физ.-мат. наук, проф. Добровидов А.В. (ИПУ РАН), д-ра техн. наук: проф. Заложнев А.Ю. (ИПУ РАН), проф. Ириков В.А. (МФТИ), проф. Калянов Г.Н. (ИПУ РАН), проф.

Касаткин С.И. (ИПУ РАН), проф. Каравай М.Ф. (ИПУ РАН), д-р экон. наук, проф.

Клочков В.В. (ИПУ РАН), д-ра техн. наук: проф. Кононенко А.Ф. (ВЦ РАН), проф.

Курдюков А.П. (ИПУ РАН), проф. Лебедев В.Г. (ИПУ РАН), к-т техн. наук, доцент Лебедев В.Н. (ИПУ РАН), д-р экон. наук, проф. Ловчиновский Э.В. (ИПУ РАН), д-р техн. наук, проф. Мандель А.С. (ИПУ РАН), д-р экон. наук, проф. Нижегородцев Р.М.

(ИПУ РАН), д-ра техн. наук: проф. Новосельцев В.Н. (ИПУ РАН), проф. Орлов А.И.

(МВТУ), канд. техн. наук Петрикевич Я.И. (ИПУ РАН), д-р физ.-мат.наук, проф.

Рапопорт Л.Б. (ИПУ РАН), д-р техн. наук, проф. Рыков А.С. (МИСИС), д-р экон. наук, проф. Секерин В.Д. (ИПУ РАН), д-ра техн. наук: проф. Сидельников Ю.В. (МАИ), проф.

Совлуков А.С. (ИПУ РАН), д-р экон. наук, проф. Сухарев О.С. (Ин-т экономики РАН), д-ра техн. наук: проф. Уткин В.А. (ИПУ РАН), проф. Хоботов Е.Н. (МВТУ), д-ра физ. мат. наук: доцент Чеботарев П.Ю. (ИПУ РАН), проф. Чхартишвили А.Г. (ИПУ РАН), проф. Щербаков П.С. (ИПУ РАН).

РЕГИОНАЛЬНЫЕ РЕДАКЦИОННЫЕ СОВЕТЫ Волгоград – д-ра физ.-мат. наук: проф. Воронин А.А., проф. Лосев А.Г. (ВолГУ);

Воронеж – д-р техн. наук, проф. Баркалов С.А., д-р физ.-мат. наук, проф. Головинский П.А. (ВГАСУ), д-р техн. наук, проф. Подвальный С.Л. (ВГТУ);

Ижевск – д-р физ.-мат.

наук, проф. Непейвода Н.Н., к-т физ.-мат. наук, проф. Родионов В.И. (УдмГУ);

Иркутск – д-ра физ.-мат. наук: проф. Бычков И.В., проф. Лакеев А.В. (ИДСТУ СО РАН);

Казань – д-р физ.-мат. наук, проф. Маликов А.И., д-р техн. наук, проф. Сиразетдинов Р.Т.

(КГТУ-КАИ);

Липецк – д-ра техн. наук: проф. Кузнецов Л.А., проф. Погодаев А.К.

(ЛГТУ);

Самара – д-ра экон. наук: проф. Богатырев В.Д., проф. Гераськин М.И., д-р техн. наук, проф. Засканов В.Г. (СГАУ);

Санкт-Петербург – д-ра физ.-мат. наук: проф.

Петросян Л.А. (СПбГУ), проф. Фрадков А.Л. (ИПМ РАН);

Старый Оскол – д-р техн.

наук, проф. Еременко Ю.И. (СТИ);

Тверь – д-ра техн. наук: проф. Кузнецов В.Н., проф.

Палюх Б.В. (ТГТУ).

Адрес редакции: 117997, г. Москва, ул. Профсоюзная, д. 65.

Адрес в Интернет: ubs.mtas.ru.

Номер гос. регистрации электронного научного издания (ЭНИ): 0420900023.

ИПУ РАН, СОДЕРЖАНИЕ Сетевые модели в управлении: вступительное слово главного редактора........................................................ Математика сетей Батурин В. А., Лемперт А. А.

Метод улучшения для дискретной управляемой системы с сетевой структурой................................... Блюмин С. Л.

Оргиперграфы: матричные представления................. Бурков В. Н., Буркова И. В.

Метод сетевого программирования в задачах управ ления проектами............................................................. Орлов А. И.

Графы при моделировании процессов управления промышленными предприятиями.................................. Петров А. Е.

Двойственные сетевые модели больших систем........ Семенов А. С.

Фрактальные развивающиеся архитектуры............... Сетевые модели в принятии решений Абдулин Е. Р.

Метод построения и проверки гипотез о менталь ных действиях пользователя при реализации челове ко-машинного взаимодействия..................................... Белых А. А., Шайдулин Р. Ф., Гуреев К. А., Хари тонов В. А., Алексеев А. О.

Принцип многомодельности в задачах моделирова ния индивидуальных предпочтений................................ Кононенко А. Ф., Шевченко В. В.

О возможностях конструктивно-логического и се тевого представления операционных игр..................... Кульба В. В., Кононов Д. А., Чернов И. В., Ро щин П. Е., Шулигина О. А.

Сценарное исследование сложных систем: анализ методов группового управления...................................... Мазалов В. В., Печников А. А., Чирков А. В., Чуйко Ю. В.

Задача дележа затрат на создание веб-коммуникатора как кооперативная игра.............. Харитонов В. А., Алексеев А. О.

Сетевые механизмы анализа многофакторных рисков.................................................................................. Технологические сети Ахметзянов А. В., Гребенник О. С.

Выбор допустимых режимов отбора газа из сква жин газовых месторождений....................................... Ахметзянов А. В., Сальников А. М., Спиридо нов С. В.

Многосеточные балансовые модели нестационар ных потоков в сложных газотранспортных системах............................................................................. Бандурин И. И.

Управление структурой оперативного обслужива ния электрических сетей................................................. Гордийчук Т. В., Ицков А. Г.

Некоторые алгоритмы оптимизации и визуального представления транспортных потоков....................... Епифанов С. П., Зоркальцев В. И., Медвежон ков Д. С.

Модель гидравлической сети с регуляторами расхода................................................................................ Зоркальцев В. И., Пержабинский С. М.

Модель оптимизации дефицита мощности элек троэнергетической системы......................................... Корниенко С. А., Угольницкий Г. А.

Оценка качества в производственных системах различной структуры...................................................... Стецюра Г. Г.

Механизмы взаимодействия объектов сетевых цифровых систем.............................................................. Фархадов М. П., Петухова Н. В., Ефросинин Д. В., Семенова О. В.

Моделирование гибридного центра связи с сервиса ми самообслуживания и пороговым управлением размещением заявок......................................................... Когнитивные карты Абрамова Н. А.

Экспертная верификация при использовании фор мальных когнитивных карт. Подходы и практика.... Абрамова Н. А., Воронина Т. А., Порцев Р. Ю.

О методах поддержки построения и верификации когнитивных карт с применением идей когнитивной графики............................................................................ Горелова Г. В., Макарова Е. Л.

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

Верификация когнитивных карт на основе объясне ния прогнозов................................................................... Сетецентрическое управление и многоагентные системы Агаев Р. П., Чеботарев П. Ю.

Сходимость и устойчивость в задачах согласования характеристик (обзор базовых результатов)............. Амбарцумян А. А.

Сетецентрическое управление на сетях Петри в структурированной дискретно-событийной системе Бабак Л. Н., Щербатюк А. Ф.

Об одном алгоритме поиска источника подводного шлейфа, основанном на использовании группы АНПА Граничина Н. О.

Мультиагентная система для распределения заказов.............................................................................. Затуливетер Ю. С., Фищенко Е. А.

Графодинамические системы с сетецентрическим управлением в математически однородном поле компьютерной информации........................................... Каляев И. А., Капустян С. Г., Гайдук А. Р.

Самоорганизующиеся распределенные системы управления группами интеллектуальных роботов, построенные на основе сетевой модели...................... Кузнецов О. П., Жилякова Л. Ю.

Полные двусторонние ресурсные сети с произволь ными пропускными способностями.............................. Петрикевич Я. И.

Линейные алгоритмы управления геометрическим расположением объектов в многоагентной системе Щербаков П. С.

Управление формациями: схема Ван Лоуна и другие алгоритмы....................................................................... Сетевые организации и социальные сети Байбакова Е. Ю., Клочков В. В.

Экономические аспекты формирования сетевых организационных структур в российской наукоем кой промышленности..................................................... Губанов Д. А., Новиков Д. А.

Модели унифицированного информационного управ ления в однородных социальных сетях......................... Просвиркин Н. Ю.

Экономико-математическая многокритериальная модель управления материальными потоками в сетевых интегрированных структурах....................... Райков А. Н.

Сетевая экспертная поддержка решений................... Ратнер С. В.

Сценарии стратификации научно-инновационной сети.................................................................................. Угольницкий Г. А.

Имитационные и оптимизационные модели слож ных систем с учетом их структуры............................ Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

СЕТЕВЫЕ МОДЕЛИ В УПРАВЛЕНИИ:

ВСТУПИТЕЛЬНОЕ СЛОВО ГЛАВНОГО РЕДАКТОРА Настоящий внеочередной специальный выпуск Сборника тру дов «Управление большими системами» носит название «Сетевые модели в управлении». Он посвящен задачам управления, в кото рых объект управления (и/или система управления) имеет сетевую структуру.

Согласно одному из определений, система – это совокупность элементов и связей между ними. Граф, по определению, задается множеством вершин (элементов) и множеством ребер (связей) между ними. Поэтому теория графов является естественным язы ком моделирования структуры систем различной природы. Благо даря своей «графичности» этот язык интуитивен и легко воспри нимается даже людьми, далекими от математики. Возможно, теория графов сделала больше других формальных концепций для популяризации математики и внедрения математических моделей в практику. Более того, многие ученые называют теорию графов универсальным языком науки, позволяющим специалистам из различных областей легко понимать друг друга.

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

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

Крупномасштабные (распределенные и др.) системы управле ния также зачастую имеют сложную структуру, описываемую в терминах теории графов (традиция теории управления противо поставляет сетевые структуры систем и/или объектов управления иерархическим). И именно сетевые структуры в последнее десяти летие стали одним из объектов, привлекающих внимание многих специалистов по теории и практике управления (свидетельством Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

тому является, в том числе, география авторов Спецвыпуска – Вла дивосток, Ижевск, Иркутск, Липецк, Москва, Пермь, Петроза водск, Псков, Ростов-на-Дону, Самара, Санкт-Петербург, Таганрог).

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

В раздел «Математика сетей» сгруппированы статьи, посвя щенные новым инструментам сетевого моделирования, находя щим приложения в различных областях теории управления.

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

Раздел с условным названием «Технологические сети» вклю чает в себя статьи, посвященные управлению сетями различной природы – гидравлическими, электрическими, тепловыми, сетями газо/нефтепроводов, сетями связи (в частности, компьютерными сетями) и др.

Раздел «Когнитивные карты» включает описание инструмен тов для качественного сетевого моделирования динамики сложных экономических, социальных и других систем.

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

Еще два перспективных направления теории управления, свя занных уже с социально-экономическими системами, – это управ ление сетевыми организациями и управление в социальных сетях.

Раздел «Сетевые организации и социальные сети» отражает неко торые новые результаты, полученные в рамках этих подходов.

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

Главный редактор, член-корр. РАН Д. А. Новиков Математика сетей УДК 517.977. ББК 22.161. МЕТОД УЛУЧШЕНИЯ ДЛЯ ДИСКРЕТНОЙ УПРАВЛЯЕМОЙ СИСТЕМЫ C СЕТЕВОЙ СТРУКТУРОЙ Батурин В. А. 2, Лемперт А. А. (Учреждение Российской академии наук Институт динамики систем и теории управления СО РАН, Иркутск) Работа посвящена построению приближенных методов ре шения дискретных задач оптимального управления с сетевой структурой, использующих достаточные условия оптимально сти В. Ф. Кротова.

Ключевые слова: дискретная управляемая система, сетевая струк тура, метод улучшения управления.

Введение Объекты, описываемые математическими моделями в виде дискретной управляемой системы с сетевой структурой встреча ются достаточно часто в прикладных задачах химического или экологического содержания. Для построения алгоритмов улучше ния в таких задачах используется технология достаточных усло вий оптимальности [3]. Методы улучшения для классической за дачи оптимального управления дискретными системами постро ены в [1]. Предлагаемый в работе метод является обобщением одного из алгоритмов данного семейства применительно к задаче оптимального управления с сетевой структурой.

Работа выполнена при финансовой поддержке РФФИ, грант № 08 01-00156.

Владимир Александрович Батурин, доктор физико математических наук, профессор (rozen@icc.ru).

Анна Ананьевна Лемперт, кандидат физико-математических наук (lempert@icc.ru).

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

1. Постановка задачи Пусть задан ориентированный граф (рис. 1) с вершинами i = 0, N + h. Обозначим:

Ai – множество номеров вершин j таких, что в заданном графе существует ребро ij, причем j i, Bi – множество номе ров вершин j таких, что в заданном графе существует ребро ij, причем j i.

Пусть первые k вершин графа являются входными, а послед ние h вершин – выходными, т.е. Ai = при i = 0, k и Bi = при i = N + 1, N + h.

Рис. 1. Ориентированный граф В каждой вершине графа состояние процесса описывается своей математической моделью в форме дискретной управляемой Математика сетей системы:

xi (ti + 1) = f i ti, xi (ti ), ui (ti ), (1) где ti {ti, ti + 1,..., ti }, i = 0, N, j Bi.

00 Далее индекс i у t будем опускать.

Начальные условия в каждой вершине определяются из сле дующих соотношений:

xi (ti ) = xi, i = 0, k, 0 l xi (ti ) = i xl1 (tl1 ),..., xlp (t1p ), (2) 0 l1,..., lp Ai, i = k + 1, N.

Функции xi (t) принимают значения в евклидовом простран стве Rn(i) ;

ui (t) Ui Rm(i) ;

i – заданные функции.

Обозначим x = x1 (t), x2 (t),..., xN +h (t), u = u1 (t), u2 (t),..., uN +h (t).

Множество троек (x, u, a), удовлетворяющих перечислен ным условиям, а также связям (1) и начальным условиям (2), будем называть множеством допустимых и обозначать D, пред полагается, что D =.

Определим функционал I(x, u) = F xN +1 (tN +1 ),..., xN +h (tN +h ) min.

(3) 1 2. Метод улучшения Пусть i (t, xi ) – функции, непрерывно дифференцируемые по xi, t ti, ti + 1,..., ti, i = 1, N + h. Обозначим xi = 00 1 xi (ti ), xi = xi (ti ) и введем следующие конструкции.

0 1 Ri (t, xi, ui ) = i t + 1, f i (t, xi, ui ) i (t, xi ) + ui 2, Gi (xi, xi ) = i (ti, xi ) i (ti, xi ) + xi 2.

01 11 00 Обозначим N +h (x0, x1 ) = F xN +1,..., xN +h + Gi xi, xi, 1 i= Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

i N +h t1 Ri t, xi (t), ui (t) dt.

L(x, u) = (x0, x1 ) i=1 ti Относительно постановки задачи сделаем следующие пред положения: Ui = Rm(i).

Пусть заданы управления ui (t) и соответствующие состоя I ния xi (t). Требуется найти ui (t), xi (t), i = 1, N + h, такие, I II II что I (xII, uII ) I (xI, uI ).

Пусть функции f i (t, xi, ui ), дважды непрерывно дифферен цируемы по xi, ui, функции F, i, дважды непрерывно дифферен цируемы по своим аргументам, i = 1, N + h.

Функции Кротова будем искать в классе линейно квадратичных функций:

i (t, xi ) = i (t)xi + x i i (t)xi, где i (t) – n(i) – векторы;

i (t) (n(i)n(i)) – симметрические матрицы;

xi = xi xi (t), ui = ui ui (t).

I I Рассмотрим приращение функционала L.

i N +h t1 Ri t, xi (t), ui (t) dt.

L(x, u) = (x0, x1 ) i=1 ti Приращение функций и Ri разложим в ряд Тейлора до слагаемых 2-го порядка включительно.

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

При i = 1, N :

xi (ti ) = i (ti ) z (tz ) · z i, 1 0 x 1 zBi z (tz ) · z i + xzi · z (tz ) · z i + xi (ti ) xi (ti ) = 0 x x xi 1 1 1 1 zBi + i (ti ) + (1 )E n(i).

Математика сетей При i = N + 1, N + h:

xi (ti ) = Fxi + i (ti ), 1 + i (ti ) + (1 )E n(i).

xi (ti ) xi (ti ) = Fxi xi 1 1 1 Тогда N i (ti ) z (tz ) · z i xi + = 1 0 x i=1 zBi z (tz ) · z i + xzi · z (tz ) · z i + + 1 xi i (ti ) 0 1 2 x x xi 1 1 zBi N +h Fxi + i (ti ) xi + )E n(i) xi +(1 + 1 1 i=N + + i (ti ) + (1 )E n(i) xi + o( x1 2 ), + 2 xi Fxi xi 1 1 1 Ri = Rxi xi + Rui ui + i i x i Rxi xi xi + i +u i Rui ui ui + x i Rxi ui i i ui + u i Rui xi xi + i 2 xi (t), ui (t) +o.

Найдем max dRi + 2 d2 Ri, приравнивая к нулю производ ui ные по ui, получим (4) ui = Rui uii Rui + Rui xi xi, i = 1, N + h.

i i Здесь производные функций Ri подсчитываются вдоль на чального приближения.

Подставим (4) в приращение функций Ri, получим:

i i i Rui xi xi + i R xi R u i R u i u i + 1 x i Rxi xi Rxi ui Rui ui i i i Rui xi xi i 1 2 1 R ui R ui ui i i i xi (t), ui (t) R ui + o.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Коэффициенты функций i (t, xi ) зададим так, чтобы выпол нялись следующие соотношения:

max dRi + d2 Ri = c(t), ui d + d2 = 0.

Для выполнения данных соотношений при любых xi до статочно, чтобы i i i i R xi R u i R u i u i Rui xi = 0;

i i i i R xi xi R xi u i R u i u i Rui xi = 0;

при i = 1, N :

i (ti ) = z (tz ) · z i ;

(5) 1 0 x zBi i (ti ) = z (tz ) · z i + xzi · z (tz ) · z i + 1 0 x x (6) xi 1 1 zBi )E n(i) ;

+( при i = N + 1, N + h:

i (ti ) = Fxi ;

(7) 1 (ti ) = Fxi xi i (1 )E n(i).

(8) 1 i (t, xi, i, ui ) = i (t + 1)f i (t, xi, ui ), i = Обозначим H 1, N + h.

Выпишем производные от функций Ri через производные от функций H i, f i, получим Rxi = Hxi i (t), i i i i R ui = H ui, Rxi xi = Hxi xi + fxii i (t + 1)fxi i (t), i i i Rui ui = Hui ui + fuii i (t + 1)fui (1 )E m(i), i i i Rxi ui = Hxi ui + fxii i (t + 1)fui.

i i i Математика сетей Производные функций H i (t, xi, i, ui ) подсчитываются вдоль (t, xi (t), i (t + 1), ui (t)).

I I Окончательно получим следующие соотношения i = 1, N + h :

i (t) = Hxi Hxi ui + fxii i (t + 1)fui i i i i H ui ui + (9) +fuii i (t + 1)fui (1 )E m(i) i i H ui ;

i (t) = fxii i (t + 1)fxi fxii i (t + 1)fui + Hxi ui i i i Hui ui + fuii i (t + 1)fui (1 )E m(i) i i (10) fxii i (t + 1)fui + Hxi ui i i i + H xi xi ;

ui = Hui ui + fuii i (t + 1)fui (1 )E m(i) i i (11) Hui + Hxi ui + fxii i (t + 1)fui xi.

i i i Полученные соотношения определяют алгоритм улучшения 2-го порядка:

1. В каждой вершине графа задаются начальные управления ui (t), из уравнений (1) и начальных условий (2) определя I ются xi (t).

I 2. Задается параметр (0, 1] так, чтобы выполнялись нера венства:

Hui ui + fuii i (t + 1)fui (1 )E m(i) 0, i i и из уравнений (9), (10) с учетом (5) – (8) находятся i (t), i (t), i = 1, N + h.

3. Решаются системы xi (ti + 1) = f i t, xi, ui + ui, где ui I задаются формулой (11), тем самым получается ui и xi.

II II 4. Сравниваются значения функционалов I(xI, uI ) и I(xII, uII ). Если улучшения не произошло, то пара метр уменьшается и процесс повторяется начиная с шага 2.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

3. Модельный пример На рисунке 2 представлена структурная схема задачи.

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

x1 (t + 1) = x1 (t) + u1 (t), x1 (0) = 1, t {0, 1, 2};

x2 (t + 1) = 2x2 (t) + u2 (t), x2 (0) = x1 (2) + 1, t {0, 1};

x3 (t + 1) = x3 (t), x2 (0) = x1 (2), t {0, 1};

I = x2 (1) + x3 (1) min.

Проведем одну итерацию метода улучшения.

1. Зададим начальные управления u1 (t) = 1 и u2 (t) = 1, I I тогда в силу системы x1 (0) = 1, x1 (1) = 2, x1 (2) = 3;

I I I x2 (0) = 4, x2 (1) = 9;

I I x3 (0) = 3, x3 (1) = 9.

I I 2. Выпишем основные конструкции алгоритма:

H 1 (t, x1, 1, u1 ) = 1 (t + 1) x1 (t) + u1 (t) ;

H 2 (t, x2, 2, u2 ) = 2 (t + 1) 2x2 (t) + u2 (t) ;

H 3 (t, x3, 3, u3 ) = 3 (t + 1) x3 (t).

1 (t) = 1 (t + 1) 1 1 (t + 1) 1 (t + 1) (1 ) ;

1 (t) = 1 (t + 1) 1 1 (t + 1) 1 (t + 1) (1 ) ;

1 (2) 2 (0) 3 (0);

= + 1 (2) = 2 (0) + 3 (0) + 2(1 ).

Математика сетей Аналогично, 2 (t) = 2 2 (t + 1) 1 2 (t + 1) 2 (t + 1) (1 ) ;

2 (t) = 2 2 (t + 1) 1 2 2 (t + 1) 2 (t + 1) (1 ) ;

2 (1) = ;

2 (1) = 1 +.

3 (t) = 2 2 (t + 1)x3 (t);

3 (t) = 2 2 (t + 1) + 4 3 (t + 1) x3 (t) ;

3 (1) = ;

3 (1) = 1 +.

Зададим параметр = 0.5. Тогда 3 (1) = 0.5;

3 (1) = 0.5;

3 (0) = 3;

3 (0) = 19;

2 (1) = 0.5;

2 (1) = 0.5;

2 (0) = 0.5;

2 (0) = 0;

1 (2) = 3.5;

1 (2) = 18;

1 (1) 0.014;

1 (1) 0.49.

3. Определим u1 (0) 0.4 0.49x1 (0);

u1 (1) 1.76 0.97x1 (1);

u2 (0) 3.5 x2 (0).

Отсюда получим u1 (0) 0.9;

x1 (0) = 1;

II II u1 (1) 0.9;

x1 (1) 1.9;

II II x1 (2) 2.8;

II u2 (0) 0.7;

x2 (0) 3.8;

II II x2 (1) 8.3;

II x3 (0) 2.8;

x3 (1) 7.84.

II II 4. Подсчитаем значение функционала I(xI, uI ) = 18, I(xII, uII ) 16.14. Новое значение меньше предыдущего, таким образом, итерация закончена.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

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

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

Приведен модельный пример, иллюстрирующий работу дан ного алгоритма.

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

Литература БАТУРИН В.А., УРБАНОВИЧ Д.Е. Приближенные ме 1.

тоды оптимального управления, основанные на принципе расширения. — Новосибирск: Наука, 1997. – 175 с.

БАТУРИН В.А., ЛЕМПЕРТ А.А. Методы слабого улучше 2.

ния в задаче оптимального управления на сети операто ров // Тр. междунар. конф. «Вычислительные и информа ционные технологии в науке и образовании». Павлодар, 2006. — Т. 2. – C. 76-87.

Математика сетей КРОТОВ В.Ф., ГУРМАН В.И. Методы и задачи опти 3.

мального управления. — М.: Наука, 1973. – 446 c.

IMPROVING METHOD FOR DISCRETE PLANT WITH NETWORK STRUCTURE Vladimir Baturin, Institute for System Dynamics and Control Theory of SB RAS, Irkutsk, Doctor of Science, professor (rozen@icc.ru).

Anna Lempert, Institute for System Dynamics and Control Theory of SB RAS, Irkutsk, Cand.Sc. (lempert@icc.ru).

Abstract: The paper is devoted to design of approximate methods of the optimal control problem solution for the network-structured discrete plant. The methods developed are based on Krotov sufficient conditions of optimality.

Keywords: discrete control system, network structure, improving method.

Статья представлена к публикации членом редакционной коллегии Д. А. Новиковым Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

УДК 519.179. ББК 22. ОРГИПЕРГРАФЫ:

МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ Блюмин С. Л. (Липецкий государственный технический университет, Липецк) Предложено формирование матриц инцидентности оргипер графов с использованием корней из единицы подходящих сте пеней для ориентации гиперточек и гипердуг. Сформированы также матрицы валентности и смежности и лапласианы для оргиперграфов и их дуальных.

Ключевые слова: оргиперграфы, корни из единицы, матрица инцидентности, матрица валентности, матрица смежности, лапласиан.

1. Введение Графы широко применяются в математическом моделиро вании для описания и исследования реальных объектов и систем самой разнообразной природы. Хорошо известны применения теоретико-графовых моделей для решения задач управления большими системами. Так, в [1] проиллюстрировано многооб разие применений теории графов при решении широкого класса прикладных задач управления организационными системами. В их числе – задачи о цепях и путях как упорядоченных последо вательностях ребер и дуг или, что то же, вершин в неориентиро ванных и ориентированных графах.

Работа поддержана РФФИ, проект №09-07-00220-а.

Семен Львович Блюмин, доктор физико-математических наук, профессор (slb@stu.lipetsk.ru).

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

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

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

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

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

2. Гиперграфы Гиперграф H определяется заданием множеств V и E и ото бражения R: V E ® {0, 1} [2, 3, 5]. В соответствии с термино логией теории графов элементы v V называются вершинами, а элементы е Е – ребрами гиперграфа;

отображение R называ ется его инцидентором. Вершина v V и ребро е Е инцидент ны в Н, если инцидентор R(v, e) = 1, и не инцидентны, если R(v, e) = 0. С учетом этого гиперграф может быть определен как пара H = (HV, HE), где HV @ {hv = E(v) = {e E: R(v, e) = 1}}, HE @ {he = V(e) = {v V: R(v, e) = 1}} – множества его гипервершин и гиперребер (символ @ здесь и далее означает «по определению»). В дальнейшем символы hv и he, в зависимости от контекста или удобства интерпретации, трактуются как v или E(v), e или V(e). Из определений следует, что e hv v he.

Дуальный гиперграф определяется как пара H* = (H*V, H*E) @ (HE, HV);

при этом (H*)* = H.

Определяются:

– степени пар «вершина-гиперребро»

d(v, he) = R(v, e);

– степени пар гипервершин (их смежности;

символ |S| означа ет мощность множества S) d(hv’, hv”) = d(hv”, hv’) = |hv’ hv”|, в частности, степени гипервершин (их валентности) d(hv) = d(hv, hv) = |hv|;

– степени пар гиперребер (их смежности) d(he’, he”) = d(he”, he’) = |he’ he”|, в частности, степени гиперребер (их валентности) d(he) = d(he, he) = |he|;

– степени пар «ребро-гипервершина»

d(e, hv) = R(v, e).

Математика сетей Для дуального гиперграфа эти понятия определяются ду альным образом.

Далее предполагается, что множества V, E вершин и ребер, а значит и множества HV, HE гипервершин и гиперребер, ко нечны: |HV| = m, |HE| = n;

в этом случае говорят о (m, n) гиперграфе Н и его дуальном (n, m)-гиперграфе Н*. Предпола гается, что элементы этих конечных множеств некоторым обра зом (фиксированным на протяжении всего рассмотрения) пере нумерованы: V = {vi, i = 1, …, m}, E = {ej, j = 1, …, n}.

(m, n)-гиперграф однозначно определяется матрицей (вер шинно-гиперреберной) инцидентности I(H) = I(V, HE) – (0, 1)-матрицей размера m n, строки которой помечены его вершинами, столбцы – гиперребрами, а на месте (v, he) находит ся число d(v, he). При этом для дуального гиперграфа Н* I(H*) = I(E, HV) = (I(V, HE))* = (I(H))*;

здесь применение операции «*» к матрице означает транспони рование.

Матрица I(HV) гипервершинной инцидентности определя ется как квадратная матрица порядка m, строки и столбцы кото рой помечены гипервершинами, а на месте (hv’, hv”) находится число d(hv’, hv”). Эта матрица допускает представление d ( he )-1 (1) I ( HV ) = I ( HV ;

he) = P( he) k ( he ) = heHE k ( he ) = 0 heHE d ( he ) -1 = P (he) 0 + P (he) k ( he ) = D( HV ) + A( HV ).

heHE k ( he ) =1 heHE Здесь D(HV) – диагональная матрица валентности (степеней) гипервершин;

A(HV) – симметричная (с нулевой диагональю) матрица смежности гипервершин, а вспомогательные матрицы I(HV;

he) и P(he) строятся так: матрица I(HV;

he) содержит единицы на местах, отвечающих вершинам v he, а остальные элементы – нули. Вычеркивание в ней нулевых строк и столб цов приводит к квадратной матрице J порядка d(he), состоящей из единиц. Эта матрица допускает представление в виде суммы J = P0 + P1 + … + Pd(he) – 1, Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

где Р0 – единичная матрица;

P1 = P – матрица циклической перестановки набора из d(he) элементов. Возвращение в нее вычеркнутых строк и столбцов приводит к матрице P(he).

Матрица I(HЕ) гиперреберной инцидентности определяется как квадратная матрица порядка n, строки и столбцы которой помечены гиперребрами, а на месте (he’, he”) находится число d(he’, he”). Эта матрица допускает представление d ( hv ) - (2) I ( HE ) = I ( HE;

hv ) = P (hv) k ( hv ) = hvHV k ( hv ) = hvHV d ( hv ) - = P (hv) 0 + P( hv) k ( hv ) = D ( HE ) + A( HE ).

hvHV k ( hv ) =1 hvHV Здесь D(HЕ) – диагональная матрица валентности (степе ней) гиперребер;

A(HЕ) – симметричная (с нулевой диагональю) матрица смежности гиперребер, а вспомогательные матрицы I(HЕ;

hv) и P(hv) строятся дуально матрицам I(HV;

he) и P(he), так как для дуального гиперграфа I(H*V) = I(HE), I(H*E) = I(HV).

Лапласовские матрицы L(H), L(H*) (лапласианы) гипергра фа и его дуального определяются по формулам L(H) @ I(H)(I(H))*, L(H*) @ I(H*)(I(H*))* = (I(H))*I(H), они симметричны и удовлетворяют соотношениям L(H) = I(HV), L(H*) = I(HE).

Указанные выше матричные представления (неориентиро ванных) гиперграфов служат основой для матричных представ лений оргиперграфов.

3. Оргиперграфы Обыкновенные графы G = (V, E) без петель являются част ным случаем рассматриваемых гиперграфов, для всех гиперре бер которых, т. е. ребер е, d(e) = 2, так как ребра являются двух элементными подмножествами e = {v’, v”} множества V вершин (следует отметить, что для обыкновенных графов имеет смысл понятие гипервершины, так как, вообще говоря, вершине графа Математика сетей инцидентно множество ребер, |E(v)| 0 может быть любым натуральным числом, как и в гиперграфе).

В случае орграфа OG = (V, A) вершины дуг (arcs – ориенти рованных ребер) а А упорядочены, пронумерованы, а = (v’, v”) = (v(а)1, v(а)2) или (в соответствии с последующими обозначениями) а = (v(а)0, v(а)1). В столбце матрицы I(OG) инци дентности орграфа, отвечающем дуге а, на местах, отвечающих этим вершинам, находятся числа +1 и –1, являющиеся корнями степени 2 из единицы и имеющие нулевую сумму. Это подска зывает следующее определение матрицы инцидентности орги перграфа.

Пусть элементы гипервершин и гиперребер гиперграфа не которым образом (вообще говоря, не связанным с указанной ранее «сквозной» нумерацией его вершин и ребер) упорядоче ны, пронумерованы, в результате чего гипервершины и гипер ребра становятся гиперточками hp HP (hyperpoints) и гипер дугами ha HA (hyperarcs):

hp = (e0hp ), e1( hp ),..., edhp ) ) -1 ) = (ekhp ) ), k (hp) = 0,1,..., d (hp) - 1), ( ( ( ( hp ( hp ha = (v0ha ), v1( ha ),..., vdha ) )-1 ) = (vk ha ) ), k (ha) = 0,1,..., d (ha) - 1), ( ( ( ( ha ( ha (именно такой способ «внутренней» нумерации удобен в даль нейшем).

Оргиперграф теперь может быть определен как пара OH = (OHV, OHE) = (HP, HA). Дуальный оргиперграф (ОН)* = (НА, НР).

В столбец матрицы I(OH) инцидентности оргиперграфа, от вечающий его гипердуге ha, на места, отвечающие инцидент ным ей вершинам в установленном их порядке, помещаются, вообще говоря, комплексные корни степени d(ha) из единицы, имеющие нулевую сумму:

e d ((ha )) (ha), k (ha) = 0,1,..., d (ha) - 1, k ha где e d ( ha ) (ha) = e d ( ha ) (ha) = exp 2pi d (ha) Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

(указание метки гипердуги ha обязательно, так как для разных гипердуг ha’, ha” возможно d(ha’) = d(ha”)).

Лапласиан L(ОH) оргиперграфа определяется по формуле L(ОH) @ I(ОH)(I(ОH))*;

здесь применение операции «*» к матрице с комплексными элементами означает эрмитово сопряжение, т. е. транспониро вание и замену каждого элемента комплексно сопряженным.

Как следствие, лапласиан оргиперграфа является эрмитовой матрицей. Справедливо соотношение L(OH) = I(HP), где матрица I(HP) гиперточечной инцидентности допускает представление, основанное на представлении (1) матрицы I(HV) гипервершинной инцидентности:

d ( ha )-1 k ( ha ) (3) I ( HP ) = I ( HP;

ha ) = ( e d ( ha ) ( ha) P( ha) ) = haHA k ( ha ) = 0 haHA d ( ha ) -1 k ( ha ) = P( ha )0 + ( e d ( ha ) ( ha ) P (ha ) ) = D( HP) + A( HP).

haHA k ( ha ) =1 haHA Здесь D(HР) – диагональная матрица валентности гиперточек, совпадающая с матрицей D(HV) валентности гипервершин, а A(HР) – эрмитова (с нулевой диагональю) матрица смежности гиперточек, отличающаяся указанным в (3) образом от матрицы A(HV) смежности гипервершин.

Для матрицы инцидентности и лапласиана дуального орги перграфа (ОН)* = (НА, НР) справедливы соотношения I((OH)*) = (I(OH))*, L((OH)*) @ I((OH)*)(I((OH)*))* = (I(OH))*I(OH) = I(HA).

Для получения на основе (2) дуального к (3) представления матрицы гипердуговой индцидентности исходного гиперграфа, т. е. матрицы гиперточечной инцидентности и лапласиана ду ального гиперграфа, целесообразно переопределить непосред ственно матрицу инцидентности дуального гиперграфа спосо бом, дуальным к способу определения матрицы инцидентности исходного графа, а именно: в столбец матрицы I^((OH)*) инци дентности дуального оргиперграфа, отвечающий его гипердуге Математика сетей hр (гиперточке исходного оргиперграфа), на места, отвечающие ее элементам (инцидентным ей ребрам исходного гиперграфа) в установленном их порядке, помещаются корни степени d(hр) из единицы, имеющие нулевую сумму:

d dk((hp )) (hp), k (hp) = 0, 1,..., d ( hp) - 1.

hp Теперь лапласиан L^((ОH)*) дуального оргиперграфа опре деляется по формуле L^((ОH)*) @ I^((ОH)*)(I^((ОH)*))*.

Справедливо соотношение L^((OH)*) = I^(HA), где матрица I^(HA) гипердуговой инцидентности исходного оргиперграфа допускает представление, основанное на пред ставлении (2) матрицы I(HЕ) его гиперреберной инцидентности:

d ( hp )-1 k ( hp ) (4) I ( HA) = I ( HA;

hp ) = (d d ( hp ) (hp ) P (hp ) ) = hpHP k ( hp ) =0 hpHP d ( hp ) -1 (d (hp) P( hp) ) k ( hp ) = D ( HA) + A ( HA).

= P (hp)0 + d ( hp ) k ( hp ) =1 hpHP hpHP Здесь D^(HА) – диагональная матрица валентности гипердуг, совпадающая с матрицей D(HЕ) валентности гиперребер, а A^(HА) – эрмитова (с нулевой диагональю) матрица смежности гипердуг, отличающаяся указанным в (4) образом от матрицы A(НЕ) смежности гиперребер.

4. Примеры 4.1. ГРАФЫ В случае обыкновенных графов представления (1) и (3) сво дятся к известным соотношениям I(G)(I(G))* = L(G) = D(G) + A(G), I(OG)(I(OG))* = L(OG) = D(OG) + (–1)A(OG), где I(G) и L(G), I(OG) и L(OG) – матрица инцидентности и лапласиан графа и орграфа, D(G) = D(OG) и A(G) = A(OG) – матрицы валентности и смежности, совпадающие для графа и соответствующего ему орграфа. Множитель –1 соответствует Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

Представление (2) сводится к сравнимому с известным со отношением для реберного графа (I(G))*I(G) = 2E + A(R(G)), где в данном случае Е – единичная матрица;

A(R(G)) – матрица смежности реберного графа. Множитель 2 соответствует общей для всех ребер графа их степени. На матрицу 2Е можно смот реть как на матрицу валентности, а на матрицу A(R(G)) – как на матрицу смежности дуального (в смысле гиперграфов) графа.

4.2. ОРГИПЕРГРАФ В [2] приведен пример гиперграфа H = (HV, HE), для кото рого V = {v1, …, v9}, E = {e1,…, e6}, HV = {hv1 = {e1}, hv2 = {e1, e2}, hv3 = {e1, e4}, hv4 = {e2}, hv5 = {e2}, hv6 = {e2, e3, e6}, hv7 = {e3}, hv8 = {e3, e4}, hv9 = {e5}}, HE = {he1 = {v1, v2, v3}, he2 = {v2, v4, v5, v6}, he3 = {v6, v7, v8}, he4 = {v3, v8}, he5 = {v9}, he6 = {v6}}.

Матрицы инцидентности I(H), валентности D(HV) и смеж ности A(HV) гипервершин, валентности D(HE) и смежности А(НЕ) гиперребер этого гиперграфа имеют вид:

1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 I (H ) = 0 1 0 0 0 0, D( HV ) = diag (1,2,2,1,1,3,1,2,1), 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 Математика сетей 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 A(HV ) = 0 0, 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 D( HE ) = diag (3,4,3,2,1,1), A(HE ) =.

1 0 1 0 0 0 0 0 0 0 1 1 0 Непосредственно проверяются соотношения I(H)(I(H))* @ L(H) = I(HV) = D(HV) + A(HV), (I(H))*I(H) @ L(H*) = I(HЕ) = D(HЕ) + A(HЕ).

Представления (1), (2) матриц I(HV), I(HE) проиллюстрированы ниже в рамках представлений (3), (4) матриц I(HP), I^(HA).

Пусть элементы гиперточек и гипердуг оргиперграфа ОН упорядочены именно так, как указано выше. Его матрица инци дентности формируется в виде Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

e 3 (1) 0 0 0 1 e 3 (1) e 4 (2) 0 0 0 e 3 (1) 2 e 2 (4) 0 0 e 4 (2) 0 0 0 0, I (OH ) = 0 e 4 (2) 0 0 3 e10 (6) e 4 (2) e 3 (3) 0 0 0 e 3 (3) 0 0 0 e 3 (3) e 2 (4) 2 0 e10 (5) 0 0 0 0 а ее сопряженная (I(OH))* = e 3 (1) e 32 (1) e 3 (1) 0 0 0 0 0 e 4 (2) e 4 (2) e 4 (2) e 4 (2) 0 3 2 0 0 0 0 0 0 2 e 3 (3) e 3 (3) e 3 (3) 0 0 0 = e 2 (4) e 2 (4) 0 0 0 0 0 0 0 0 e10 (5) 0 0 0 0 0 0 e10 (6) 0 0 0 0 0 0 Их произведение I(OH)(I(OH))* @ L(OH) = I(HP) (с учетом свойств произведений корней из единицы и того, что ej0(i) = 1) записывается в виде Математика сетей 1 e 3 (1) e 3 (1) 2 0 0 0 0 1 e 3 (1) e 3 (1) e 4 (2) e 4 (2) e 4 (2) 2 3 2 2 0 0 e 3 (1) e 3 (1) e 1 (4) 2 2 0 0 0 0 e 4 (2) e 4 (2) e 4 (2) 1 3 0 0 1 0 0 0 e 4 (2) e 4 (2) e 4 (2) 2 1 0 1 0 e 4 (2) e 4 (2) e 4 (2) e 3 (3) e 3 (3) 3 2 1 2 0 0 0 e 3 (3) e 3 (3) 1 0 0 0 0 0 e 2 (4) e 3 (3) e 3 (3) 1 2 0 0 0 0 0 0 0 0 0 0 Его представление (3) расписывается следующим образом:

L(OH) = I(HP) = D(HP) + A(HP), где D(HP)= = D ( HV ) = diag (1, 2, 2, 1, 1, 3, 1, 2, 1) = P ( ha1 )0 +... + P ( ha6 ) 0 = = diag (1,1,1,0,0,0,0,0,0) + diag (0,1,0,1,1,1,0,0,0) + + diag (0, 0, 0, 0, 0, 1, 1, 1, 0) + diag (0, 0, 1, 0, 0, 0, 0, 1, 0) + + diag (0, 0, 0, 0, 0, 0, 0, 0, 1) + diag (0, 0, 0, 0, 0, 1, 0, 0, 0), A(HP) = 1 1 1 2 = e 3 (1) + e 3 (1) + Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

1 1 2 1 +e 4 (2) + e 4 (2) + 1 1 +e 4 (2) + e 3 (3) + 1 1 +e 3 (3) + e 2 (4).

1 1 1 Замена корней из единицы единицами дает представление (1) матрицы A(HV).

Матрица инцидентности I^((OH)*) дуального оргиперграфа формируется в виде (целесообразно сравнить ее с матрицей I((OH)*) = (I(OH))*, а ее сопряженную (I^((OH)*))* – с матри Математика сетей цей (I((OH)*))* = I(OH);

далее указано их произведение и, для сравнения, произведение (I(OH))*I(OH)) I^((OH)*) = d10 (1) d 20 (2) d 20 (3) 0 0 0 0 d 2 (2) d1 (4) d1 (5) d 3 (6) 1 0 0 0 0 0 0 0 d 3 (6) d10 (7) d 20 (8) 0 0 0 =, d 2 (3) d 2 (8) 1 0 0 0 0 0 0 0 d10 (9) 0 0 0 0 0 0 d 32 (6) 0 0 0 0 0 0 I^((ОH)*)(I^((ОH)*))* @ L^((ОH)*) = I^ (HA) = 3 d 2 (2) d 2 (3) 1 1 2 d 2 (2) d 3 (6) 0 d 3 (6) 4 0 d 2 (8) 0 d 32 (6), d 3 (6) 1 = 1 d 2 (3) d 2 (8) 0 2 0 0 0 0 0 d 3 (6) d 3 (6) 2 0 0 (I(OH))*I(OH) = I((OH)*)(I((OH)*))* @ L((OH)*) = I(HA) = 3 e 3 (1) e 3 (1) 2 0 1 e 3 (1) e 4 (2) 0 e 4 (2) 1 4 0 1.

e 4 (2) e 3 (3) e 1 (4) 3 = 2 e 3 (1) e 2 (4) e 3 (3) 1 0 2 0 0 0 0 0 e 4 (2) 0 1 0 0 Представление (4) расписывается следующим образом:

I^(HA) = D^(HA) + A^(HA), где D^(HA) = D ( HE ) = diag (3, 4, 3, 2, 1, 1) = P ( hp1 )0 +... + P ( hp9 ) 0 = = diag (1, 0, 0, 0, 0, 0) + diag (1, 1, 0, 0, 0, 0) + diag (1, 0, 0, 1, 0, 0) + Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»


+ diag (0, 1, 0, 0, 0, 0) + diag (0, 1, 0, 0, 0, 0) + diag (0, 1, 1, 0, 0, 1) + + diag (0, 0, 1, 0, 0, 0) + diag (0, 0, 1, 1, 0, 0) + diag (0, 0, 0, 0, 1, 0), 1 1 A ^ ( H) = d 2 (2) + 1 1 + +d 2 (3) + d 3 (6) 1 1 + d 2 (8) +d 3 (6) 2.

1 Замена корней из единицы единицами дает представление (2) матрицы А(НЕ).

5. Заключение В литературе имеются указания на то, что принятая за ос нову в данной работе трактовка гипердуги в оргиперграфе как кортежа, т. е. упорядоченного, нумерованного множества вер Математика сетей шин, использовалась, например, в [7] (без использования ком плексных корней из единицы для формирования матричных представлений оргиперграфов) как основа для обобщения тео рии формальных языков, грамматик и автоматов в соответст вующем направлении.

Из других известных определений оргиперграфа, отличных от принятого за основу в данной работе, можно указать сле дующие [3, 9]: гипердугами являются пары подмножеств мно жества вершин, одно из которых принимается за «начальное», а другое – за «конечное» подмножество гипердуги;

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

В определении инцидентора нечеткого гиперграфа [10] двухэлементное множество {0, 1} заменяется промежутком [0, 1]. Так как в практических приложениях нечетких гипергра фов обычно оказываются достаточными некоторые конечные подмножества промежутка [0, 1], то предложенный в данной работе подход, при надлежащей его модификации, может быть распространен на нечеткие гиперграфы.

Лапласианы и их спектры играют важную роль в теории и приложениях графов и орграфов (см., например, [4, 6, 8]). Так, в работе [4] исследовано применение спектров лапласианов взве шенных орграфов в задачах согласования характеристик при децентрализованном управлении многоагентными системами;

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

одним из свойств его лапласиана, определяю щих свойства его спектра, является то, что он имеет нулевые строчные суммы;

это, в конечном счете, является следствием Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

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

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

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

Литература 1. БУРКОВ В. Н., ЗАЛОЖНЕВ А. Ю., НОВИКОВ Д. А. Тео рия графов в управлении организационными системами. – М.: СИНТЕГ, 2001. – 124 с.

2. ЕМЕЛИЧЕВ В. А., МЕЛЬНИКОВ О. И., САРВАНОВ В. И., ТЫШКЕВИЧ Р. И. Лекции по теории графов. – М.: Наука, 1990. – 384 с.

3. ЗЫКОВ А. А. Гиперграфы // Успехи математических наук.

– 1974. – Т. 29, №6. – С. 89–154.

4. ЧЕБОТАРЕВ П. Ю., АГАЕВ Р. П. Согласование характери стик в многоагентных системах и спектры лапласовских матриц орграфов // Автоматика и телемеханика. – 2009. – №3. – С. 136–151.

Математика сетей 5. BERGE C. Hypergraphs: Combinatorics of Finite Sets. – Am sterdam: North-Holland, 1989. – 321 p.

6. BIYIKOGLU T., LEYDOLD J., STADLER P. Laplacian Ei genvectors of Graphs. – Berlin: Springer, 2007. – 115 p.

7. COURCELLE B. Graph Rewriting. Handbook of Theoretical Computer Science. Part 2: Formal Models and Semantics. – NY: North Holland, 1990. – P. 193–242.

8. CVETKOVIC D., DOOB M., SACHS H. Spectra of Graphs:

Theory and Applications. – Leipzig: Verlag, 1995. – 368 p.

9. GALLO G., LONGO G., NGUYEN S., PALLOTTINO S.

Directed Hypergraphs and Applications // Discrete Applied Mathematics. – 1993. – №42. – Р. 177–201.

10. MORDESON J., NAIR P. Fuzzy Graphs and Fuzzy Hyper graphs. – Heidelberg, New York: Physica-Verlag, 2000.

– 248 p.

DIHYPERGRAPHS: MATRIX REPRESENTATIONS Sam L. Blyumin, Lipetsk State Technical University, Lipetsk, Dr.

Sc. in Math. & Phys., professor (slb@stu.lipetsk.ru).

Abstract: Incidence matrices construction routine is proposed for dihypergraphs. It uses relevant degrees of unity root to describe hyperpoints and hyperarcs orientation. Valence and adjacency matrices along with Laplacians are also constructed for dihyper graphs and their duals.

Keywords: dihypergraphs, unity root, incidence matrix, valence matrix, adjacency matrix, Laplacian.

Статья представлена к публикации членом редакционной коллегии А. Г. Чхартишвили Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

УДК 002.53+004.65+004.62/.63+338. ББК 32.816, 65.05.0. МЕТОД СЕТЕВОГО ПРОГРАММИРОВАНИЯ В ЗАДАЧАХ УПРАВЛЕНИЯ ПРОЕКТАМИ Бурков В. Н.1, Буркова И. В. (Учреждение Российской академии наук Институт проблем управления РАН, Москва) Метод сетевого программирования разработан для получения точных решений или верхних (нижних) оценок задач многоэкс тремальной (в частном случае – дискретной) оптимизации.

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

В каждой вершине решаются простые задачи оптимизации.

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

Ключевые слова: сетевое программирование, управление проектами, дискретная оптимизация.

1. Введение Задачи оптимизации в управлении проектами в основном связаны с определением предметной области проекта (т. е.

состава работ проекта) и с построением календарного плана при ограниченных ресурсах. Как правило, это задачи многоэкстре Владимир Николаевич Бурков, д.т.н., профессор (vlab17@bk.ru) Ирина Владимировна Буркова, к.т.н. (irbur27@mail.ru) Математика сетей мальной (в частном случае – дискретной) оптимизации. В об щем случае для их решения применяются эвристические алго ритмы. Из точных методов следует отметить метод ветвей и границ и метод динамического программирования. Эффектив ность метода ветвей и границ в большой степени зависит от качества верхних или нижних оценок (границ). Для получения таких оценок достаточно универсальным является метод мно жителей Лагранжа.

В 2004 году авторами был предложен метод дихотомиче ского программирования [3], а несколько позднее его обобще ние – метод сетевого программирования (МСП) [4]. Как метод точного решения задач, МСП обобщает метод динамического программирования, а как метод получения верхних (нижних) оценок – метод множителей Лагранжа.

В статье дается обзор применения МСП к задачам управле ния проектами. Дадим краткое описание МСП.

2. Метод сетевого программирования Рассмотрим следующую задачу дискретной оптимизации:

определить вектор x X, обеспечивающий (1) max f ( x) x X при ограничении (2) j ( x) b.

Далее будем предполагать, что X = X i,где Xi – дискрет i ное множество чисел.

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

Пример 1. Рассмотрим функцию четырех переменных (3) f(x) = (x1x2 + x12)x3 + x3x4 + x1x4.

Ее сетевое представление приведено на рис. 1, где y1 = x1x2 + x12, y2 =y1x3, y3 =x1x4, y4 =x3x4, y5 = y2 + y3 + y4.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

y y2 y3 y y x1 x2 x3 x Рис. 1. Пример сетевого представления функции Определение 1. Функции f(x) и j(x) называются структур но-подобными (с-подобными) в заданном классе сетевых пред ставлений, если существуют сетевые представления этих функ ций такие, что соответствующие сетевые структуры совпадают.

Пример 2. Рассмотрим функцию (4) j(x) = (x1 + x2)x3(x1 + x4) + x3x4.

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

Пусть функции f(x) и j(x) в задаче (1), (2) являются с-подобными. Построим их общее сетевое представление. Пусть далее целевая функция f является монотонной функцией обоб щенных переменных y (без ограничения общности можно при нять, что f – возрастающая функция y). Аналогично примем, что функция j также является возрастающей функцией y. В сетевом представлении выделим вершины нулевого уровня, которым соответствуют переменным xi. Вершинам первого уровня соот ветствуют задачи оптимизации следующего вида: максимизиро вать (5) yi = fi(x) при ограничении zi = ji(x) p, где p принимает все допустимые значения.


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

Последней решается задача, соответствующая выходу сети.

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

Теорема 1. Величина yk(b) является верхней оценкой для исходной задачи (1), (2).

3. Задача выбора портфеля проектов Имеется n проектов, каждый из которых характеризуется затратами ai на реализацию и эффектом ci от реализации проек та. Задача заключается в выборе портфеля проектов с макси мальным суммарным эффектом при заданной величине R инве стиционного фонда. Формально задача сводится к классической задаче о ранце [6].

Математическая постановка задачи имеет вид:

(6) f ( x) = c j x j ® max, j (7) j ( x) = a j x j R, j (8) x j {0, 1}, j = 1, n.

Структура сетевого представления является деревом, по этому метод сетевого или дихотомического программирования дает оптимальное решение.

Различные обобщения этой задачи связаны с учетом огра ничений на совместимость проектов, с учетом риска или огра ничений на число проектов в тех или иных областях рассмотре ны в [1, 2].

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

4. Задача календарного планирования Рассмотрим задачу формирования календарного плана реа лизации проекта, состоящего из n работ.

Примем, что плановый период разбит на Т интервалов оп ределенной длины D (недели, месяцы, кварталы и т. д.) Обозначим Ri – множество интервалов, в которых может выполняться работа i;

Psj – множество работ j-го вида которые могут выполняться в s-ом интервале. Заданы ограничения Qtj на объем проектных работ каждого вида в каждом интервале. Для каждой проектной работы, в свою очередь, задан объем работ, выполняемый ресурсами каждого вида. Более того, примем, что каждая работа выполняется только одним видом ресурсов.

Таким образом, все работы разбиты на m подмножеств так, что работы j-го подмножества выполняются ресурсами j-го вида.

Обозначим через xis объем i-ой работы, выполняемый в s-ом интервале;

cis – максимальный объем i-ой работы, который можно выполнить в s-ом интервале. Задача заключается в опре делении {xis }, i = 1, n, s = 1, T, так, чтобы (9) xis C is, i Ps, s = 1, T, xis Wi, i = 1, n, sR где Wi – объем i-ой работы, (10) xis Qsj, j = 1, m, iPsj а суммарный объем выполненных работ j-го вида T xis (11) s =1 iPsj был максимален.

Ограничимся случаем независимых работ. Для решения за дачи определим двудольный граф G(X, Y). Вершины i X соот ветствуют работам, а вершины s Y соответствуют интервалам.

Пропускные способности вершин i X равны объектам Wi соответствующих работ, а пропускные способности вершины Математика сетей s Y равны объему работ, который можно будет выполнить в соответствующем интервале, т. е. Qs.

Пропускные способности дуг (i, s), i = 1, n, s Ri, равны Cis.

Задача свелась к определению максимального потока в полу ченной сети, что соответствует минимальному объему работ, отдаваемых на субподряд. Опишем алгоритм определения потока максимальной величины, основанный на методе сетевого программирования.

3АДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ Рассмотрим произвольную сеть без контуров на дугах (i, j), которой заданы пропускные способности Сij 0. Как известно, потоком в сети называется совокупность чисел 0 хij сij, (i, j) U (U – множество дуг сети), таких что (12) xij = xki j k для всех i 0, n, где 0 – вход сети, a n – выход сети. Величиной потока называется (13) j 0 = x0i = x jn.

i j Задача заключается в определении потока максимальной величины. Для решения этой задачи, как правило, применяется алгоритм Форда-Фалкерсона. Мы рассмотрим другой подход, в основе которого лежит метод сетевого программирования.

Сначала дадим определение агрегируемой сети.

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

1 2 n-1 n Рис. 2. К определению последовательного множества Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

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

Определение 3. Параллельным множеством дуг называется подмножество дуг сети, у которых начальная и конечная вер шины совпадают.

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

Определение 4. Сеть называется агрегируемой, если путем агрегирования последовательных и (или) параллельных мно жеств дуг ее можно свести к одной дуге.

Задача о максимальном потоке для агрегируемой сети эф фективно решается. Как известно, задача о максимальном пото ке для агрегируемой сети может быть представлена сетевой структурой типа дерева. На рис. 3. приведен пример агрегируе мой сети (числа у дуг равны пропускным способностям), а на рис. 4. сетевое представление задачи о максимальном потоке.

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

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

4 (4) (3) (2) 1 (6) (5) (1) 0 (3) (2) Рис. 3. Пример агрегируемой сети Математика сетей + min min 5 + + (0,1) (3,5) 5 6 min min 3 (0,3) (1,4) (4,5) (1,5) (0,2) (2,3) 3 4 2 3 Рис. 4. Сетевое представление задачи о максимальном потоке Числа в нижних половинах вершин равны пропускным спо собностям соответствующих дуг, а в верхних половинах указа ны операции, которые проводятся над числами вершин нижних уровней для определения величины максимального потока.

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

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

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Рассмотрим произвольную сеть. Произвольную сеть всегда можно преобразовать в агрегируемую сеть путем разделения ряда вершин на несколько вершин. Так, если в сети (рис. 5) вершину 4 разделить на две вершины 4 и 4, то получим агреги руемую сеть, приведенную на рис. 6.

Поскольку вместо одной дуги (4,5) мы получили две дуги (4,5) и (4,5), то разделим пропускную способность С45 = 5 на две части произвольным образом. Возьмем, например, С45 = 4, С4’5 = 1. Определим поток максимальной величины и соответст венно разрез минимальной пропускной способности в получен ной сети, применяя описанный выше алгоритм для агрегируе мых сетей.

(5) 1 (6) (8) (7) 0 (6) (5) (7) 2 Рис. 5. Исходная сеть (5) 1 (6) (8) (7) (4) 0 (6) (1) (7) 2 Рис. 6. Преобразованная агрегируемая сеть Нетрудно видеть, что величина потока равна 7, а в разрез заходят дуги (0,1) и (4,5). Имеет место Математика сетей Теорема 2. Величина максимального потока в агрегируе мой сети меньше или равна величине максимального потока в исходной сети.

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

Теорема 3 (двойственности). Существует разбиение пропу скных способностей дуг, исходящих из разделенных вершин, такое, что величина максимального потока в агрегируемой сети равна величине максимального потока в исходной сети.

Следствие. Если (i, j) – дуга, заходящая в разрез минималь ной пропускной способности в исходной сети, то все дуги (is j) также заходят в разрез минимальной пропускной способности в агрегируемой сети.

Из теоремы и следствия мы получаем необходимые и дос таточные условия оптимальности потока в агрегируемой сети:

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

Рассмотрим пример сети (рис. 6). В разрез минимальной пропускной способности заходит дуга (4,5), но не заходит дуга (4,5). Поэтому поток можно увеличить, если «перекинуть» часть пропускной способности дуги (4,5) на дугу (4,5). Увеличим C4 ',5 на 3 единицы, уменьшив C4,5 на 3 единицы (рис. 7).

(5) 1 (8) (6) (7) (1) 0 (6) (4) (7) 2 4’ Рис. 7. Увеличение потока за счет переброски части пропускной способности дуги Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

Получаем разрез минимальной пропускной способности с дугами (1,3), (4,5) и (4’,5), заходящими в разрез.

Поскольку обе дуги (4,5) и (4,5) заходят в разрез, то усло вия оптимальности выполнены. Следовательно, поток макси мальной величины j0 = 10 получен.

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

Wi – объем i-й работы, i = 1, n. Требуется распределить работы меж ду подразделениями так, чтобы загрузка подразделений (или их перегрузка) была максимально равномерной. Обозначим xij = если i-ая работа выполняется подразделением j, xij = 0 в против ном случае. Тогда уровень загрузки (перегрузки) подразделения i можно оценить величиной (14) Fi = wi xij - Qi.

j Задача заключается в распределении работ по подразделе ниям так, чтобы минимизировать (15) max wi xij - Qi.

j i Рассмотрим сначала частный случай, когда Qi = Q для всех i. В этом случае задача сводится к классической «задаче о кам нях».

Дадим постановку «задачи о камнях». Имеется n «камней»

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

Математика сетей Задача 1. Обозначим через ai вес 1-го камня, xij = 1, если камень i попал в j-ую кучку (группу), xij = 0 в противном случае.

Суммарный вес камней в j-ой группе равен (16) T j = ai xij.

i Максимальный вес группы (17) T = max ai xij ® min.

j i Поскольку каждый камень должен быть помещен только в одну группу, имеем ограничения:

(18) xij = 1, i = 1, n.

j Задача заключается в минимизации (17) при ограничениях (18). Мы будем рассматривать вспомогательную задачу сле дующего вида:

Задача 2. Фиксируем допустимый вес каждой группы Т и сформулируем следующую задачу: максимизировать сумму весов размещенных в ящики вместимостью Т камней:

(19) F = ai xij ® max.

i, j при ограничениях (18) и (19):

(20) ai xij T, j = 1, m.

i Связь между задачами (17)–(18) и (18)–(20) очевидна. Ми нимальное Т, при котором в оптимальном решении задачи размещены все камни, дает оптимальное решение задачи 1.

Сначала получим сетевое представление задачи 2. Оно представлено на рис. 8 для случая n = 3, m = 2.

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

Все ai также делим на 2 части uij и vij для каждой вершины нижнего уровня так, что (21) uij + vij = ai, для всех i, j.

Рассмотрим следующие две задачи.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

j j j j j x x11 x21 x22 x31 x Рис. 8. Пример сетевого представления задачи j j j j j x1 x x1 x x2 x2 x3 x3 x2 x2 x3 x Рис. 9. Преобразованная структура Задача 3. Определить xij так, чтобы максимизировать u ij xij (22) i, j при ограничениях (18).

Задача 4. Максимизировать (23) vij xij i, j при ограничениях (20).

Обозначим Sm(u) и Lm(v) оптимальные решения первой и второй задач при заданных u и v. Оценочная задача заключается в определении {uij} и {vij}, минимизирующих Математика сетей (24) F(u, v) = Sm(u) + Lm(v) при ограничении (21). Заметим, во-первых, что в оптимальных решениях первой и второй задач можно принять uij = yi, vij = ai – yi, j = 1, m.

Во-вторых, решение первой задачи очевидно:

(25) S m (u ) = yi i В третьих, решение m вторых задач при заданных {уi} сво дится к решению одной задачи о ранце: определить xi = 0,1, максимизирующие (26) xi (ai - yi ) i при ограничении (27) xi ai T.

i Решим задачу (26) и (27) при yi = 0, i = 1, n. Обозначим че рез Q = {Qj} множество векторов х, удовлетворяющих (27) и упорядоченных по убыванию M j= ai, Y j= y i, а iQ j iQ j Z = max ( M j-Y j ).

j Заметим, что при заданных {yi} Z определяет оптимальное решение каждой из m вторых задач. Оценка (24) при этом равна (28) F ( y ) = mZ + yi.

i где yi 0 удовлетворяют неравенствам (29) y i + Z M j, j = 1, N.

iQ j где N – число различных решений неравенства (27). Таким образом, оценочная задача свелась к определению 0 yi ai, i = 1, n и 0 Z Mj, максимизирующих (28) при ограничениях (29). Это обычная задача линейного программирования. Фикси руем величину Z и определяем максимальный номер k такой, что Z Mk.Рассматриваем следующую задачу линейного программи рования: определить 0 yi ai, i = 1, n, минимизирующие Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

(30) Y ( Z ) = y i.

i при ограничениях (29), где j = 1, k. Двойственная задача имеет вид: определить uj 0, j = 1, k, максимизирующие k ( M j - Z )u j, j = при ограничениях u j 1, i = 1, n jRi где Ri - множество номеров Qj, содержащих камень i.

Обозначим через Y0(Z) минимальное значение Y(Z). Оце ночная задача сводится к минимизации функции одного пере менного (31) Y0(Z) + mZ min.

Берем T0 = A/m, где A = ai, и решаем задачу 2. Если i Фmax(T0) A, то увеличиваем Т0 до T1 так, чтобы появился хотя бы один новый вектор Qj. Если Фmax(T1) A, то продолжаем увеличение T до тех пор, пока не получим величину Tk такую, что Фmax(Tk) A. Величина Tk является нижней оценкой для задачи 1. Далее можно применить метод ветвей и границ на основе полученной оценки.

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

Рассмотрим, например, задачу ремонта мостов или участков дорог. Ремонт производится одной бригадой. Необходимо определить очередность ремонта мостов (участков дорог) так, чтобы продолжительность ремонта была минимальной. Задача Математика сетей сводится к задаче коммивояжера. Дадим ее постановку и решим на основе метода сетевого программирования [5].

Задан (n + 1)-вершинный граф с длинами дуг lij, которые интерпретируются как расстояние между городами i и j. Требу ется найти кратчайший гамильтонов контур (маршрут комми вояжера). Обозначим xij = 1, если дуга (i, j) входит в маршрут, xij = 0 в обратном случае. Тогда задача сводится к минимизации (32) L(x ) = lij xij i, j при ограничениях (33) xij = 1 "j i xij = 1 "i (34) j (35) ui - u j + nxij n - 1, где ui 0;

i, j = 1, 2, …, n;

i j. Условие (35) гарантирует полу чение гамильтонова контура [4].

Рассмотрим симметричную задачу коммивояжера, т. е.

lij = lji " i, j.

Разобьем ограничения задачи на две группы. В одну группу включим ограничения (33) и (35), а во вторую – (34) и (35) Соответственно разделим на две части коэффициенты lij, т. е.

представим lij в виде (36) lij = pij + qij, "i, j.

Рассмотрим две оценочные задачи.

Задача 5. Определить {xij}, удовлетворяющие ограничени ям (33) и (35) и минимизирующие (37) P (x ) = pij xij.

ij Задача 6. Определить {xij}, удовлетворяющие ограничени ям (34) и (35) и минимизирующие (38) Q(x ) = qij xij.

ij Обозначим L1(p) (L2(q)) значение целевой функции в оптималь ном решении первой (второй) задачи.

Управление большими системами Специальный выпуск 30.1 «Сетевые модели в управлении»

В соответствии с основной теоремой [3], сумма (39) L1 (P) + L2 (Q) = L (P, Q) дает оценку снизу для исходной задачи коммивояжера. Таким образом, двойственная задача заключается в определении p и q, удовлетворяющих (36) и максимизирующих (39).

Теорема 4. Двойственная задача является задачей выпукло го программирования.

РЕШЕНИЕ ОЦЕНОЧНЫХ ЗАДАЧ ДЛЯ СИММЕТРИЧНОЙ ЗАДАЧИ КОММИВОЯЖЕРА Метод решения оценочных задач для симметричных мат риц основан на понятии i-дерева [6].

Выбираем некоторую вершину i. Для подграфа без верши ны i строим кратчайшее i-дерево Ti, т. е. дерево кратчайшей длины l(Ti). Для построения кратчайшего i-дерева Ti построим кратчайшее дерево на вершинах графа без вершины i и добавим к нему два кратчайших ребра, инцидентных вершине i [6].

Оценка снизу для каждой задачи определяется i-деревом, для которого l(Ti) максимальна.

Пример 3. Рассмотрим граф, рис. 10.

Оценка снизу определяется любым i-деревом и равна l(Ti) = 9, i = 1, 6. Разобьем граф на 2 (рис. 11). Имеем для первого графа l(T3) = 9, а для второго l(T2) = 9. Оценка снизу равна l(T3) + l(T2) = 18, т. е. в два раза лучше. Более того, она является достижимой. Оптимальный маршрут – (1, 2, 6, 5, 4, 3, 1).

9 0 4 0 3 Рис. 10. Граф для примера Математика сетей 1 0 5 9 0 0 0 0 0 0 4 6 4 0 0 0 3 2 3 9 Рис. 11. Разбиение на два графа 7. Оптимизация программ по стоимости Рассмотрим задачу формирования программы развития ре гиона (либо предприятия, холдинга, корпорации), обеспечи вающей требуемое значение комплексной оценки с минималь ными затратами. Примем, что задана процедура формирования комплексной оценки программы. Программа оценивается по m критериям. Обозначим j минимальное (граничное) значение i го критерия, которому соответствует оценка j (j = 1, 2, 3, 4).

Таким образом, если значение критерия yj лежит в полуинтервале d ij y i d ij +1, то оценка по соответствующему направлению равна j.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 17 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.