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

• Парфенов, Андрей Павлович
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Парфенов, Андрей Павлович

Оглавление

Введение

1 Динамические оптимизационные задачи на сетях с усилениями

1.1 Управляемые распределенные в пространстве динамические системы

1.1.1 Общая модель сложной детерминированной микроэкономической системы

1.1.2 Управляемые системы с дискретным временем

1.1.3 Обобщенные динамические системы, распределенные в пространстве ,

1.2 Алгоритмы нахождения оптимального потока в сети с нелинейными усилениями

1.2.1 Формализация и оптимизация потоков в логистической системе , , , ,

1.2.2 Общая постановка задачи нахождения оптимального потока в сети с усилениями в вершинах

1.2.3 Сети с нелинейными усилениями в дугах

1.2.4 Сеть с нелинейными усилениями с параллельным соединением дуг , , ,

1.2.5 Агрегированные сети с нелинейными усилениями. Теорема о композиции дуг

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

1.3 Алгоритмы нахождения оптимального динамического потока в сети с нелинейными усилениями

1.3.1 Определение динамического потока в сети с нелинейными усилениями

1.3.2 Частные случаи. Модель Неймана как универсальная динамическая модель

1.3.3 Сведение задачи нахождения оптимального динамического потока к статической задаче

1.3.4 Алгоритм нахождения оптимального динамического потока методом динамического программирования

2 Динамические нестратегические многокритериальные задачи на сетях

2.1 Динамические многокритериальные задачи

2.1.1 Семейство динамических многокритериальных задач и критерии оптимальности

2.1.2 Свойства оптимальных решений

2.1.3 Принципы динамической устойчивости задач многокритериальной оптимизации и их взаимосвязь

2.1.4 Теорема о динамической устойчивости многокритериальных задач для критериев — обобщенных интегральных выигрышей

2.2 Многокритериальные задачи в сетях

2.2.1 Постановка задачи многокритериальной оптимизации потока в сети с усилениями

2.2.2 Нахождение лексикографически оптимального потока в сети с усилепиямибЭ

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

2.3 Многокритериальная оптимизация динамических потоков в сетях

2.3.1 Два алгоритма многокритериальной оптимизации динамических потоков72

2.3.2 Пример 1: модель Леонтьева с разными периодами производства , , , ,

2.3.3 Пример 2: распределение ресурсов между проектами

3 Динамические стратегические многокритериальные задачи на сетях

3.1 Коалиционные принципы оптимальности в динамических играх

3.1.1 Определение динамической игры с одновременными ходами игроков , ,

3.1.2 Принципы оптимальности в динамической игре

3.1.3 Определение подыгры в развернутой форме

3.1.4 Динамическая устойчивость (коалиционных) равновесий в динамической игре и принцип Беллмана

3.1.5 Теорема о рекуррентных соотношениях динамического программирования для нахождения абсолютных равновесий в динамической игре

3.1.6 Теорема о рекуррентных соотношениях для нахождения всех равновесий в динамической игре

3.2 Обобщенные сетевые игры

3.2.1 Логистические сети и их формализация

3.2.2 Игры формирования сетей

3.2.3 Стратегические принципы оптимальности в сетевых играх

3.2.4 Коалиционные принципы оптимальности в сетевых играх

3.2.5 Определение параметрической сетевой игры

3.2.6 Определение групповой сетевой игры

3.3 Динамические сетевые игры

3.3.1 Определение динамической сетевой игры

3.3.2 Теорема о необходимых и достаточных условиях равновесия в динамической сетевой игре

3.4 Заключение

Список литературы

А Приложения

А.1 Непрерывные кусочно-линейные функции

А, 1,1 Общие определения

А, 1,2 Вогнутые кусочно-линейные функции

А, 1,3 НКЛ-функции одной переменной

А,2 Решение задачи распределения ресурсов при строительстве домов

А.З Текст программы для нахождения компромиссного плана в модели Леонтьева

с разными периодами производства

А,4 Примеры статических сетевых игр и принципов оптимальности

А,4,1 Пример 1: стабильные сети в сетевой игре с 3 игроками

А,4,2 Пример 2: сетевая игра на двудольном графе

А,4,3 Пример 3: гибридно-стабильные сети в сетевой игре с 3 игроками , , ,

А,4,4 Пример 4: сильно стабильные сети в сетевой игре с 3 игроками

А,4,5 Пример 5: компромиссное и арбитражное решение в сетевой игре с

игроками

А,4,6 Пример 6: параметрическая сетевая игра с 2 игроками

А,4,7 Пример 7: групповая сетевая игра управления потоками

А,5 Примеры динамических сетевых игр и принципов оптимальности

А,5,1 Пример 8: игра 2 игроков "многоножка" с ребрами взаимодействия , ,

А,5,2 Пример 9: игра 3 игроков с ребрами взаимодействия

А,5,3 Пример 10: компромиссное решение в двухшаговой иерархической сетевой игре

Введение диссертации (часть автореферата) на тему «Оптимальные управления в дискретных сетевых многокритериальных системах»

Введение

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

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

• сетевые динамические задачи многокритериальной оптимизации;

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

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

Если система является динамической, ее развитие во времени можно формализовать, используя управляемые динамические системы [4], Задача оптимизации в такой системе чаще всего решается методом динамического программирования [6].

Оптимальное управление в позиционной игре также можно найти методом динамического

программирования [67] или свести ее к комбинаторной игре, которая решается алгебраическими методами [68],

Задачи оптимизации сетей решаются с использованием двух подходов: сведением к задаче целочисленного линейного программирования [34, 63, 30] и комбинаторно-алгебраическими методами, опирающимися на свойства графов и упорядоченных алгебраических структур — эти методы в каждой задаче свои [61, 78, 1, 30], Также возможно сочетание этих двух подходов [84], Наиболее развита теория потоков в сетях, а также потоков в сетях с усилениями и многопродуктовых потоков, к оптимизации которых сводятся многие другие оптимизационные задачи на сетях [78, 84, 86], Чаще всего рассматривались аддитивные потоки, для которых величина потока в вершине складывается из величин потоков в дугах, заканчивающихся в этой вершине. Но многие экономические системы неаддитивны, и их таким образом смоделировать не получится.

Для формализации управления многоагентными сетями используются сетевые игры [79, 73, 72, 70, 17], При этом сетевые игры в каждой работе определяются по-своему: общего определения сетевой игры не построено. Есть два класса сетевых игр: игры формирования сетей и игры на сетях [42], Чаще всего рассматриваются статические сетевые игры, а также отдельные частные случаи динамических сетевых игр. Но многие экономические системы являются динамическими и имеют свойства, для моделирования которых требуются и игры формирования сетей, и игры на сетях.

Многие сложные системы — в частности логистические — являются одновременно и динамическими, и распределенными в пространстве. Очевидно, для моделирования таких систем следует использовать динамические сети. При этом, обычно, ограничиваются описательным подходом: формализацией множества возможных состояний динамической сети без введения критериев качества и постановки оптимизационных задач. Для этого использовались автоматные сети [59], клеточные автоматы [88], функции воздействия "входов" на "выходы" [14], раскрашенные сети Петри [75],

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

• неаддитивных оптимизационных задач в сетях, в том числе динамических — их можно описать обобщенными потоками в сетях;

сетях.

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

1, статические потоки в сетях с нелинейными усилениями;

2, динамические потоки в сетях с нелинейными усилениями;

3, динамические сетевые игры и равновесия в этих играх.

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

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

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

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

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

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

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

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

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

1, Алгоритм нахождения оптимального потока в сетях с непрерывными кусочно-линейными усилениями в дугах,

2, Модель управляемой логистической системы, распределенной в дискретном простран-

стве и развивающейся во времени,

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

4, Формализация динамической сетевой игры и алгоритмы нахождения равновесий в ней.

Структура и объем работы. Работа состоит из введения, 3 глав, заключения, списка цитируемой литературы и 5 приложений, В 1-й главе рассматриваются оптимизационные задачи, в частности, алгоритмы нахождения оптимальных потоков в сети с нелинейными усилениями. Во 2-й главе рассматриваются задачи многокритериальной оптимизации, в частности, для потоков в сетях, В 3-й главе рассматриваются игровые задачи, в частности, динамические сетевые игры, В каждой главе — 3 раздела: в 1-м разделе дается общее определение управляемой динамической системы, во 2-м рассматривается управляемая статическая система, распределенная в дискретном пространстве, в 3-м — управляемая динамическая система, распределенная в дискретном пространстве,

В приложениях приведены вспомогательные сведения о кусочно-линейных функциях, примеры к основным алгоритмам и теоремам, полученным в работе, и исходные коды программ, Список литературы включает 88 наименований. Работа изложена на 136 страницах и 48 страницах приложения, содержит 9 рисунков.

По теме диссертации опубликовано 9 работ [37]-[39], [44] [49], из них 6 статей [44, 45, 46, 47, 49, 39] и тезисы 2 докладов [37, 48],

.....I......I с^Т^с"^1 -в-

Динамические оптимизационные задачи на сетях с усилениями

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

1.1 Управляемые распределенные в пространстве динамические системы

1.1.1 Общая модель сложной детерминированной микроэкономической системы

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

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

и

матичеекой модели. Аспекты социальных и экономических систем, делающие их сложными для моделирования:

• это динамические системы — их состояние х(Ь) меняется с течением времени;

тельно, они неавтономны: параметры описывающих их уравнений и неравенств меняются с течением времени: х(Ь + 1) € F(я(£),£) (в случае дискретного времени);

• они распределены в пространстве, то есть состоят из множеетва подсистем а\,... находящихся в разных местах и взаимодействующих друг с другом;

•

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

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

Дискретное пространство, в котором между элементами возможно только парные взаимодействия — то есть взаимодействия между парами элементов — можно смоделировать ориентированным графом или мультиграфом.

Определение 1. Граф — это набор (Ь,М), где Ь — произвольное множество, называемое множеством вершин, аМ С Ь х Ь — множество пар вершин, называемых дугами.

Определение 2. Мультиграф — это набор (Ь, М, в, в), где Ь — произвольное множество (множество вершин), М — произвольное множество (множество дуг), а в, в: М ^ Ь — функции, сопоставляющие каждой дуге соответственно начальную и конечную вершину дуги,

В мультиграфе возможны параллельные дуги. Граф — это мультиграф, у которого в(а,Ь) = а, в(а,Ь) = Ь. Дискретное пространство моделируется графом, вершины которого I € Ь — это элементы, а дуги (1\,12) € М — взаимодействия между ними. Поскольку, в

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

Определение 3. Сеть — это граф ((Ь, М), /, д) или мультиграф ((Ь, М, в, е), /, д) для которого заданы функции /: Ь — А (нагруженные вершины), д: М — В (нагруженные дуги), принимающие значения из произвольных множеств А, В,

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

(Ь, М)

стему, не меняется со временем, а меняются только параметры вершин /¡(¿), I € Ь и дуг дт(г), т € М.

1.1.2 Управляемые системы с дискретным временем

Пусть X — метрическое пространство (пространство состояний системы). Пусть Т — шкала времени, т.е. упорядоченное множество моментов времени. Траекторией системы называют функцию х: Т — X, которая каждому моменту времени сопоставляет состояние системы в этот момент времени. Возможны разные способы введения пучка траекторий Р(х,£) — то

х

Например, с помощью обобщенной динамической системы (ОДС) [4]:

Определение 4. Обобщенная динамическая си,стем,а, на X с временем Т — это функция О: X х Т х Т — 2х, обладающая следующими свойствами:

1, О(х, ¿1, ¿2) = 0 — непустое компактное множество при ¿1 < ¿2- ОДС определяет будущее по прошлому, т.е. выводит следствия из причин,

2, О(х, ¿) = {х} (рефлексивность — при переходе от момента времени £ к тому же самому моменту, множество возможных состояний не меняется)

3, £ < ¿1 < ¿2 ^ О(х,£,£2) = Уу&ш(х,г,г1) О(у, ¿1, ¿2) (транзитивность).

4, Функция 0(х, ¿1, ¿2) непрерывна по совокупности переменных (х, ¿1) и по перемен ной ¿2 в метрике Хауедорфа,

Траектория ОДС — это функция х: Т ^ X, которая для любых двух моментов времени ¿1,12 € Т удовлетворяет соотношению

В работе рассматривается только дискретное упорядоченное множество моментов времени Т. Из дискретности следует, что его можно пронумеровать: Т = {¿1,12,... ,13]. Условия компактности и непрерывности функций достижимости — слишком ограничивающие и в работе не используются.

Определение 5. Пусть Т — дискретное время. Тогда функция О — ОДС с дискретным временем, если для нее выполняются свойства непустоты, рефлексивности и транзитивности.

Замечание 1.1.1. При этом могут не выполняться свойства непрерывности и компактности множеств достижимости.

Определение 6. Управляемая (автономная) динамическая система с дискретным, временем с множеством состояний X — это набор (О, и, п), где О — функция достижимости в ОДС с дискретным временем, и — множество управлений, а п: X х и ^ X — функция перехода такая, что Щ^е^ п(х(Ь),и(Ь)) = Щх^)^^ + 1),

Управляемая, неавтономная динамическая систем,а, с дискретным временем с множеством состояний X и временем Т — это набор (О, и,п), где О — функция достижимости в ОДС с дискретным временем, и — множество управлений, ап: X х Т х и ^ X — функция перехода такая, что

(т.е. функция п сюръективна по и для каждого (х,1)).

Замечание 1,1,2. Таким образом, управляемая динамическая с дискретным временем эквивалентна автомату без выхода (переходной системе) (X,U,п) [59], где X и и - множество

п

Управляемая неавтономная динамическая система (О, и, п) с множеством состояний X и Т

— это пространство-время X х Т, а функция перехода — п'((х,Ь),и) = (п(х,Ь,и),Ь + 1),

х(12) € О(х(*1), ¿1, ¿2)•

(1.1)

(1.2)

Утверждение 1.1.1. У ОДС с дискретным временем для любой начальной точки х0 и любого программного управления и: Т — и существует единственная совместимая с ним траектория х: Т — X, т.е. такая, что п(х(^),¿,и(^)) = х(^ + 1), выходящая из точки, х0.

Верно и обратное: для, каждой траектории системы, существует совместимое с ней программное управление.

Доказательство. Индукцией по числу моментов времени. База индукции: х(0) = х0. Индукционный переход: если построено начало траектории х^) до момента к, берем х(^ + 1) = п(х(^),¿,и(^). Соотношение (1.1) следует из транзитивности.

Обратное утверждение также доказывается по индукции. Существование управления и(^) на каждом шаге следует из еуюръективноети функции тт. □

Замечание 1,1,3. Таким образом, ОДС с дискретным временем однозначно определяется функцией О(х, ¿) = 0(х,£,£ + 1), Управляемая динамическая система с дискретным временем однозначно определяется множествами и(х, ¿) и функцией п — отображение О можно определить по формуле (1.2).

Верно и обратное: если ОДС на множестве X с дискретным временем Т задана функцией О то ей соответствует управляемая динамическая система, для которой и(х,^) = О(х, ¿) и п(х,^,и) = и. Таким образом, обычные ОДС с дискретным временем и управляемые эквивалентны, Далее управление в некоторых случаях определяется явно, а в некоторых — нет, из соображений удобства.

Как известно [25], каждую ОДС с дискретным временем можно наглядно изобразить графом (XМ), множество вершин которого — X' = X х Т (пространство-время системы), а дуги т € М имеют вид т = ((х1,¿), (х2,^ + 1)), где х2 € ©(х^,^ + 1), Этот граф — диаграмма переходов соответствующего автомата без выхода. Путь в графе — это движение ОДС, а множество путей, выходящих из точки — пучок траекторий.

Замечание 1,1,4. Граф ОДС является "выровненным" — для каждой его вершины х € X'

х

"выровненный" граф (X',М) также можно считать графом ОДС, в котором для каждой вершины х ее целочисленное время Ь — длина путей, ведущих из произвольной корневой вершины графа в х. В "обобщенной ОДС", которой соответствует граф (XМ), возможна произвольная продолжительность времени от начального состояния до конечного. Но ее можно привести к "обобщенной ОДС" с постоянной продолжительностью времени, добавив к каждой терминальной вершине у графа достаточное количество фиктивных вершин уьу2,.. . ук так, чтобы длины всех непродолжаемых путей стали одинаковы.

Кроме того, в произвольном "выровненном" графе пространство X (¿) состояний системы

— это множество достижимости в момент £ из всех корневых вершин графа, В общем случае, оно непостоянное (меняющееся со временем). Но можно считать, что множество всех состояний системы — X = и4еТ X (¿).

В бесконечном графе длины путей могут быть неограничены. Но в настоящей работе мы рассматриваем системы на конечных (среднесрочных) интервалах времени и поэтому предполагаем, что длины всех путей в ОДС ограничены, В частности, если в каждой позиции ОДС с конечным временем существует только конечное число вариантов выбора, то граф конечен и, следовательно, длины всех путей ограничены [7]. Но мы будем рассматривать и возможность бесконечного числа вариантов выбора и ограниченного множества длин путей. Бесконечный граф с ограниченным множеством длин путей, как и конечный, можно свести к графу ОДС, добавив в конец фиктивные вершины и определив множество состояний системы как X = У4еТ X(¿).

Наконец, произвольный ("невыровненный") бесконтурный граф (X',М) с ограниченным множеством длин путей можно свести к "выровненному" следующим образом:

1, Присвоить каждой вершине х € X такую временную метку ¿(х) € Т, что если существует дуга (х1,х2) € М, то ¿(х1) < ¿(х2). Существование таких меток для бесконтурного графа следует из существования его топологической сортировки [30],

2, Расположить па каждой дуге ((х,Ь(х)), (у,¿(у))) фиктивные вершины (х,Ь(х) + 1), (х,г(х) + 2,..., (х,1(у) - 1)).

В разделе 2,3,2 приведен пример сведения произвольного "невыровненного" графа к графу ОДС.

В работе рассматриваются оптимизационные задачи, в которых множество альтернатив

— это пучок траекторий Р(х,Ь). Простейший случай критерия оптимальности на пучке траекторий — интегральный выигрыш Н,... ,хт) = д-ъ(х-ъ) + дг+1(хг+1) + ■ ■ ■ + дт(хт). Для ОДС (О, х0) с заданным начальным состоянием хо задача максимизации интегрального выигрыша сводится к поиску оптимального пути в бесконтурном графе [1]. Его можно найти алгоритмом Беллмана-Форда [1] или более простым алгоритмом для бесконтурных графов [30].

1.1.3 Обобщенные динамические системы, распределенные в пространстве

В данном разделе определены управляемые динамические системы, распределенные в пространстве, Они моделируют распределенные меняющиеся во времени управляемые системы (например, социальные или экономические). Возможны 2 различных сетевых представления пространства-времени системы:

1, Представление в виде графа ОДС с дискретным временем, рассмотренное в предыдущем разделе;

2, Представление в виде графа системы, развернутого во времени.

Второе представление нужно, например, для уменьшения количества возможных состояний системы. Пусть управляемая динамическая система состоит из |Ь| = п узлов, распределенных в пространстве, каждый из которых может находиться в одном из IX | = х

| М| = т

ют взаимодействия между узлами. Пусть каждое соединение может находиться в одном из | и| = и

множеств состояний узлов и множеств состояний соединений. Тогда эта система имеет очень много возможных состояний: хпит, а следовательно, для |Т| = в моментов времени ее граф имеет вхпит вершин и 0(вх2пи2т) дуг. Граф же, развернутый во времени, имеет вп вершин и О(вт) дуг, что гораздо меньше.

Определение 7. Статическая распределенная система в дискретном, пространстве — это набор (Ь, М, {¿?г}геь, {^(и)}^, {Щв))}^ где

• (Ь, М) — граф, описывающий дискретное пространство, в котором расположена система;

• $г — множество возможных состояний вг € Бг вершины I € Ь (произвольное непустое множество);

• и^) — множество возможных с остояннй и^-) дуг и (г, € М (произвольное непустое множество);

• Поч)ем ~~^ ~~ множественное отображение;

• [/¿: вг —> — множественное отображение.

Состояние статической распределенной системы — это набор параметров вершин и дуг ({■■г}г&ь, {и(^)}(^)€м) такой, что

Щ = {Щг,])}{г,])&М ^ и¿(в»)

Можно рассматривать аналогичные определения управляемой сетевой системы на муль-тиграфе — то есть графе с кратными дугами. Но состояние набора дуг можно рассматривать как вектор состояний дуг, и тогда мультиграф сводится к простому графу.

Рассмотрим теперь динамические системы, распределенные в пространстве, в которых воздействие передается от одной вершины к другой по дуге за конечное время. Состояние системы — это набор состояний ее вершин и дуг: Б = Л 1&ь Бг х ПтеМ ит. Дуга — переносчик воздействия. Поскольку время мы считаем дискретным, можно свести воздействие элемента а на элемент Ь за время п к п-кратному воздействию за единичное время, введя фиктивные состояния, как описано в предыдущем разделе. Тогда состояние системы в последующий момент времени в(1 + 1) зависит только от состояния системы в предыдущий момент времени в(1). Отсюда получаем определение (в данном определении из соображений удобства управления не заданы явно):

Список литературы диссертационного исследования кандидат наук Парфенов, Андрей Павлович, 2016 год

Литература

[1] Авдошин С.М., Белов В.В. Обобщенный метод "волны" для решения экстремальных задач на графах // ЖВМ и МФ, АН СССР. 1979. Т. 19, №3. С. 739-755.

[2] Авдошин С.М., Белов В.В., Маслов В.П., Питеркин В.М. Оптимизация гибких производственных систем. М,: ин-т электрон, машиностроения, 1987. - 91 с.

[3] Ашманов С.А. Математические модели и методы в экономике. М,: изд.-во Моск. ун.-та, 1980. - 199 с.

[4] Барбашин E.A.K теории обобщенных динамических систем // Учебные записки МГУ. 1949. №135. С. 110-133.

[5] Белтадзе Г.Н. Множества равновесных ситуаций в лексикографических бескоалиционных играх. // Бюллетень Академии Наук Грузинской ССР. 1980. Т. 98, JVS1. С. 41-44.

[6] Беллман Р. Динамическое программирование. / Пер. с англ. U.M. Андреева, A.A. Кор-бут, И. В. Романовский, И. Н. Соколова, под ред. Н. Н. Воробьева. М,: издательство Иностранная литература, 1960. - 340 с.

[7] Берж К. Теория графов и ее применения. М,: издательство иностранной литературы, 1958. - 320 с.

[8] Введение в математическое моделирование транспортных потоков (под ред. A.B. Гаени-кова). М.: МФТИ, 2010. - 362 с.

[9] Воробьев H.H. Коалиционные игры // Теория вероятностей и ее применения. 1967. Т. 12, №2. С. 289-306.

[10] Высокое М.И., Жуковский В.И. Модель управляемой дуополии Курно // Спектральные и эволюционные задачи. 2010. Т. 20. С. 109-114.

[11] Гапаго А. Б. К задаче о максимальном потоке на специальной сети с обобщенными дугами: автореферат диссертации на соискание ученой степени канд. физ.-мат, наук, Минск, 1987.

[12] Гермеиер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971. - 383 с.

[13] Гермеиер Ю.Б. Игры с непротивоположными интересами. М.: Наука, 1976. - 327 с.

[14] Глушков В.М. Кибернетика. // Математическая энциклопедия (под ред. И.М. Виноградова). Т.2. М,: издательство "Советская энциклопедия", 1979. - с. 850-855.

[15] Гороховик В. В. Геометрические и аналитические характеристики кусочно-аффинных отображений // Национальная академия наук Беларуси. Труды Института математики. 2007. Т. 15, №1. С. 22-32.

[16] Губко М.В. Теоретико-игровая модель формирования торговой сети // Управление большими системами. 2004. №6. С. 56-83.

[17] Губко М.В. Управление организационными системами с сетевым взаимодействием агентов // Автоматика и телемеханика. 2004. №8. С. 115-123. №9. С. 131-148.

[18] Давыдов Э.Г. Исследование операций: Учеб. пособие для студентов вузов. М,: Высшая школа, 1990. - 383 с.

[19] Данилов В.И., Сотсков А.И. Механизмы группового выбора. М,: Наука, 1991. - 172 с.

[20] Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр. М,: Наука, 1981. - 336 с.

[21] Еремин И.И. Линейная оптимизация и системы линейных неравенств: учеб. пособие для вузов. М,: издательский центр "Академия", 2007. - 256 с.

[22] Исследования по общей теории систем (под ред. В. И. Садовского и Э.Г . Юдина) М.: Прогресс, 1969. - 520 с.

[23] Иенсен П., Барнес Д. Потоковое программирование. М,: Радио и связь, 1984. - 392 с.

[24] Карманов В.Г. Математическое программирование: учеб. пособие. М,: Физматлит, 2000. - 264 с.

[25] Коган Д. И. Динамическое программирование и дискретная многокритериальная оптимизация. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2005. - 260 с.

[26] Кокорин А.И., Копытов В.М. Линейно упорядоченные группы. М,: Наука, 1972. - 199 с.

[27] Колоколъцов В.Н., Малафеев O.A. Теория игр для всех (моделирование процессов конкуренции и кооперации), СПб: Лань, 2010, - 624 с,

[28] Колоколъцов В.Н., Маслов В. П. Дифференциальное уравнение Беллмана и принцип максимума Понтрягина для задач многокритериальной оптимизации // Докл. Акад. Наук СССР. 1992. №324:1. С. 29-34.

[29] Кравцов М.К. Полиэдральные аспекты транспортных задач и сложность многокритериальных задач дискретной оптимизации: автореф. дис. на сонск. учен. степ, д.ф.-м.н. Минск, 1994. - 29 с.

[30] Кристофидес П. Теория графов. Алгоритмический подход. М,: Мир, 1978. - 432 с.

[31] Кун Г. У. Позиционные игры и проблема информации // Позиционные игры (под ред. H.H. Воробьева и П.Н. Врублевской). М,: Наука, 1967. - С. 13-40.

[32] Лъюс Р. Игры и решения: введение и критический обзор. / Р .Д. Льюс, X. Райфа. М,: издательство иностранной литературы, 1961. - 642 с.

[33] Ляпунов А.Н. Согласованность и равновесие в многокритериальных задачах // Экономико-математические исследования. Математические модели и информационные технологии, IV, ч,1, СПб, 2005. - С.92-110.

[34] Майника Э. Алгоритмы оптимизации на сетях и графах. М,: Мир, 1981. - 323 с.

[35] Малафеев O.A. Управляемые конфликтные системы. СПб: издательство СПбГУ, 2000. - 275 с.

[36] Малафеев O.A., Муравьев А.И. Математические модели конфликтных ситуаций и их разрешение. Т.1: общая теория и вспомогательные сведения. СПб, 2000. - 283 с.

[37] Малафеев O.A., Парфенов А.П Конкурентные решения в сетевых моделях многоагент-ного взаимодействия // Современные методы теории функций и смежные проблемы: материалы конференции. Воронеж, 2007. С. 150-151.

[38] Малафеев O.A., Парфенов А.П. Многокритериальные задачи в сети с линейными усилениями // Малафеев O.A., Зубова А.Ф. Математическое и компьютерное моделирование социально-экономических систем на уровне многоагентного взаимодействия (введение в проблемы равновесия, устойчивости и надежности). СПб., 2006. - С. 648-658.

[39] Малафеев O.A., Парфенов А.П. Решение сетевых игр, // Малафеев O.A., Зубова А.Ф. Математическое и компьютерное моделирование социально-экономических систем на уровне многоагентного взаимодействия (введение в проблемы равновесия, устойчивости и надежности), СПб., 2006, С, 697-710,

[40] Малафеев O.A., Соснина В.В., Мутлу О.В. Модель управления процессом кооперативного трехагентного взаимодействия // Проблемы механики и управления: нелинейные динамические системы. 2007. Вып. 39. С. 131-144.

[41] Матвеенко В.Д. Применение модели Неймана для исследования схемы динамического программирования // Автомат, и телемех. 1988. №12. С. 62-70.

[42] Новиков Д.А. Игры и сети // Математическая теория игр и ее приложения. 2010. T.2, вып.1. С. 107-124.

[43] Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход. М.: Физматлит, 2002. 2005. - 176 с.

[44] Парфенов А.П. Алгоритм нахождения равновесий в динамической сетевой игре // Математическая теория игр и её приложения. 2013. Т. 5. Вып. 1. С. 45-60.

[45] Парфенов А.П. Многошаговые сетевые игры управления потоками // Вести. Санкт-Петерб. унив.-та, Сер. 10: Прикладная математика. Информатика. Процессы управления. 2009. Вып. 4. С. 200-212.

[46] Парфенов А. П. Нахождение Парето-лексикографически оптимальных траекторий в дискретных динамических системах // Московское научное обозрение. 2012. Д'"9. С. 65-69

[47] Парфенов А.П. Оптимизация потока в сетях с кусочно-линейными функциями усиления и стоимости // Процессы управления и устойчивость: Труды 38 научной конференции аспирантов и студентов (под ред. Платонова А. В., Смирнова Н.В.) СПб., 2007. С. 592598.

[48] Парфенов А.П. Оптимизация потока в сети с нелинейными усилениями // Современные методы теории краевых задач: материалы Воронежской весенней математической школы "Понтрягинекие чтения - XVIII". Воронеж, 2007. С. 125-126.

[49] Парфенов А.П., Малафеев O.A. Равновесное и компромиссное управление в сетевых моделях многоагентного взаимодействия / / 39-й выпуск межвузовского сборника научных

трудов "Проблемы механики и управления: Нелинейные динамические системы", Пермь, 2007. С. 154-167.

[50] Петросян Л.А., Зенкевич, H.A., Сёмина, Е.А. Теория игр: Учебное пособие для университетов. М,: Высшая школа, 1998. - 304 с.

[51] Петросян Л.А, Кузютин Д.В. Игры в развернутой форме: оптимальность и устойчивость. СПб.: издательство СПбГУ, 2002. - 292 с.

[52] Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах // Автоматика и телемеханика. 1996. №2. С. 24-29.

[53] Розен В.В. Стратегические игры с упорядоченными исходами: автореферат диссертации на соискание ученой степени докт. физ.-мат. наук. М,, 1989.

[54] Романовский В.И. Алгоритмы решения экстремальных задач. М,: Наука, 1977. - 352 с.

[55] Седа,ков A.A. Многошаговые игры с коалиционной структурой: автореферат диссертации на соискание ученой степени канд. физ.-мат. наук. СПб., 2009.

[56] Семененко А.П., Сергеев В.И. Логистика. Основы теории. С-Пб: издательство "Союз", 2001. - 544 с.

[57] Слобожанин Н.М. Информация и управление в динамических играх. СПб.: издательство СПбГУ, 2002. - 308 с.

[58] Смолин Е.А. Принцип позиционной динамической устойчивости и его применение в системах со многими управлениями: автореферат диссертации на соискание ученой степени канд. физ.-мат. наук. Красноярск, 2007.

[59] Трахтенброт Б.А., Вардзинь Я.М. Конечные автоматы (поведение и синтез). М,: Наука, 1970. - 400 с.

[60] Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М,: Мир, 1984. - 496 с.

[61] Форд Л., Фалкерсон Д. Потоки в сетях. М,: Мир, 1966. - 277 с.

[62] Хачиян Л. Г. Сложность задач линейного программирования. М,: Знание, 1987. - 32 с.

[63] Ху Т. Целочисленное программирование и потоки в сетях. М,: Мир, 1973. - 520 с.

[64] van (lev Aalst W.M.P., van Hee K.M., Houben G.J. Modelling and analizing workflow using a Petri net base approach // Proceedings of Second Workshop on Computer-supported Cooperative Work, Petri nets related formalisms, 1994, P. 31-50,

[65] Aumann, R. and Myerson, R. Endogenous Formation of Links Between Players and Coalitions: An Application of the Shaplev Value // Roth, A. (ed.) The Shaplev Value, Cambridge University Press, 1988, P. 175-191,

[66] Bacelli Fr., Cohen G., Olsder J.G., Quadrat J.-P. Synchronization and linearity. Algebra for discrete event systems. New-York: John Wiley & Sons, 1992, - 501 p.

[67] Bashar T., Olsder G.J. Dynamic noneooperative game theory, London: Academic press inc., 1982. - 430 p.

[68] Conway J.H. On Numbers and Games, London Math, Soc, Monograph, №6, Academic Press, London-New-San Francisco, 1976,

[69] Dobkin D., Guibas L., Hershberger J., Snoeyink J.. An efficient algorithm for finding the CSG representation of a simple polygon // Algorithmica, №10, 1993, P. 1-23,

[70] Flam S.D., Horvath C. Network games; adaptations to Nash-Cournot equilibrium // Annals of Operation Research. 1996. №64. P. 179-195.

[71] Flischer L., Scutella M. Minimum cost flows over time without intermediate storage // Proceedings of the 14th annual ACM-SIAM simposium on discrete algorithms. 2003. P. 66-75.

[72] Jackson M. O. Social and Economic Networks. Princeton University Press. 2008. - 647 p.

[73] Jackson M.O., Wolinsky A. A Strategic Model of Social and Economics Networks // J. Econom. Theory. 1996. №71. P. 44-74.

[74] Jarilo C. On strategic network // Strategic Maneg. J. 1988. Vol. 9. P. 31-41.

[75] Jensen K. An introduction to the theoretical aspects of coloured Petri nets //A decade of concurrency, Lecture notes in computer science. 1994. Vol. 803. P. 230-272.

[76] P.J. Hammond Consequentialist foundations for expected utility // Theory and Decision, 25. 1988. P. 25-78.

[77] P.J. Hammond, H. Zank Rationality and Dynamic Consistency under Risk and Uncertainty. The Warwick Economics Research Paper Series (TWERPS) 1033. 2013. - 74 p.

[78] Minieka E. Parametric network flows // Discussion paper of International Center for Management Science affiliated with the Center for Operation Research and Econometrics, 1971.

[79] Myerson R. Graphs and Cooperation in Games // Math. Operations Research. 1977. №2. P. 225-229.

[80] Oldham J.D. Combinatorial Approximation Algorithms for Generalized Flow Problems. Department of Computer Science, Stanford University, Stanford. 1998.

[81] S. Ovchinnikov. Max-Min Representation of Piecewise Linear Functions // Contributions to Algebra and Geometry. Vol. 43. №1. 2002. P. 297-302.

[82] Radzik T. Faster algorithms for the generalized network flow problem // Mathematics of Operations Research. 1998. №23. P. 69-100.

[83] Shen G., Gaines P.E. Hierarchically accelerated dynamic programming for finite-state machines // IEEE Trans. Automatic Control. 2002. Vol. 47. №2. P. 271-283.

[84] Truemper K. On max flows with gains and pure min-cost flows // SIAM J. Appl. Math. 1977. №32. P. 450-456.

[85] Venkatesh B., Sanjeev G. A Noncooperative Model of Network Formation // Econometrica, Vol. 68, №5. 2000. P. 1181-1229.

[86] Wayne K.D. Generalized Maximum Flow Algorithms: A Dissertation Presented to the Faculty of the Graduate School of Cornell University. 1999.

[87] Wayne K.D. A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow // Mathematics of Operations Research, Vol. 27, №3. 2002. P. 445-459.

[88] Wolfram S. A New Kind of Science. Champaign, IL, Wolfram Media, 2002.