Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dfc/2009/xtra/skorohodov/Skorokhodov_research_statement.pdf Дата изменения: Sun Oct 25 20:24:40 2009 Дата индексирования: Tue Nov 24 17:38:22 2009 Кодировка: Windows-1251

План исследования
Ориентированные графы (взвешенные и обыкновенные) стали мощным средством анализа и моделирования различных прикладных задач. Неоспорим тот факт, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электроника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика и многих других. При этом, обычно на графе решаются задачи о достижимости (т.е. существует ли путь из вершины в вершину? и если существует несколько путей, то какой из них кратчайший), задача о случайном блуждании частицы на орграфе с заданными на дугах вероятностями (Марковский процесс), а так же потоковая задача. Перечисленные задачи (в классической постановке, т.е. когда все дуги являются равноправными, а все пути допустимыми) хорошо изучены и являются широко применимыми в различных областях. В классической постановке все дуги орграфа являются равноправными для прохождения по ним. В проекте предполагается рассмотреть новые типов ограничений на прохождение по дугам выделенных подмножеств и разработать методы и алгоритмы для решения классических задач при таких неклассических видах достижимости. В качестве примера рассмотрим так называемую смешанную достижимость. На множестве дуг графа выделено подмножество так называемых запретных дуг. Допустимыми путями на графе считаются пути, не проходящие более одного раза подряд по запретным дугам. Ясно, что при этом для путей на графе пропадает транзитивное свойство, перестает быть справедливым и утверждение о том, что любой отрезок кратчайшего пути является кратчайшим путем между соответствующими вершинами. Из-за этого перестает работать алгоритм нахождения кратчайших путей. Если рассматривать задачу о случайном блуждании частицы по графу с такой достижимостью, то она не является марковской, так как возможные переходы частицы из вершины в вершину определяются не только заданными на дугах вероятностями, но зависят от предыстории частицы (по дуге какого типа она пришла в вершину). Для задачи о максимальном потоке в сети наблюдается такое-же явление не все определяется только пропускными способностями дуг, но существенным становится взаимное расположение запретных и обычных дуг. В процессе выполнения работ по проекту предполагается получить следующие результаты: 1. изучить новые классы ограничений на достижимость;


2. изучить новые классы условий, аналогичных ограничениям на достижимость (например, зависимость веса дуги от времени); 3. разработать общий подход к решению задач о достижимости и о случайном блуждании, а так же потоковой задачи на ориентированных графах с условиями, аналогичными нестандартной достижимости; 4. исследовать вопрос о двойственности для классических задач на графах с нестандартной достижимостью; 5. разработать общее правило построения математических моделей для такого класса задач логистики, как перераспределение ресурсов в сети элементов среднего или крупного предприятия. Эти результаты позволят получить обобщение классического понятия ?ориентированный граф?, что расширит область применения графовых моделей и методов, в том числе к задачам логистики, маршрутизации в сетях с участками затухания и участками усиления сигнала, к нахождению кратчайших путей выполнения технологических процессов, в которых имеются ограничения на порядок (последовательность) выполнения некоторых операций или их совместимость, к нахождению вероятностей в задачах случайного блуждания частицы, когда имеются переходы, влияющие на ее свойства ся:

На первом этапе

(первый год) выполнения работы предполагает-

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

На втором этапе

(второй год) выполнения работы предполагает-

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

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

На третьем этапе