Содержание к диссертации
Введение
1. Организация гис, ориентированных на решение оптимизационных задач
1.1. Решение задач в среде ГИС и оптимизация на графовых моделях
1.2. Избыточность и концепция картографического образа
1.3. Комбинирование картографических образов
1.3.1. Принципы комбинирования
1.3.2. Построение рабочей области для комбинирования
1.3.3. Синтез формул комбинирования на основе экспериментальных данных
1.4. Средства снижения риска использования информации ГИС
1.5. Принципы самоактуализации электронных карт ГИС
1.6. Построение нечетких графовых моделей на основе ГИС
1.7. Выводы по разделу 1
2. Размещение объектов с помощью гис с учетом их лингвистических характеристик
2.1. Классификация задач размещения объектов в транспортной сети
2.2. Лингвистические переменные и операции над ними
2.2.1. Определение понятия лингвистической переменной
2.2.2. Операции над значениями лингвистической переменной
2.2.3. Синтаксически независимые лингвистические переменные
2.3. Размещение объектов на карте местности с учетом лингвистических характеристик альтернативных мест размещения
2.3.1. Общее описание постановки задачи
2.3.2. Модель задачи размещения с лингвистическими исходными данными
2.3.3. Подходы к решению задачи
2.4. Размещение объектов на карте с учетом характеристик, учитывающих взаимосвязи мелсду объектами
2.4.1. Минисуммная задача размещения центров обслуживания с исходными данными, представленными в виде лингвистических переменных
2.4.2. Минимаксная задача размещения центров обслуживания с исходными данными, представленными в виде лингвистических переменных
2.4.3. Многокритериальные задачи размещения центров обслуживания и центров скорой помощи
2.5. Выводы по разделу 2
3. Потоки в сетях при нечетком представлении данных
3.1. Основные понятия, используемые в транспортной сети при исследовании потоков
3.2. Неопределенность в транспортной сети
3.3. Использование нечетких данных при решении задач о потоках в сетях
3.4. Определение максимального потока от источника к стоку в графе с нечеткими пропускными способностями
3.4.1. Определение максимального потока в графе с пропускными
способностями, представленными в виде нечетких чисел L-R типа
3.4.2. Определение максимального потока в графе с нечеткими пропускными способностями, представленными в виде интервалов
3.5. Задачи о потоке минимальной стоимости в нечетких условиях
3.5.1. Особенности постановки задачи о потоке минимальной стоимости с нечеткими данными
3.5.2. Модели задачи о потоке минимальной стоимости в нечетких условиях
3.5.3. Задача определения потока минимальной стоимости в графе с нечеткими пропускными способностями
3.5.4. Задача определения потока минимальной стоимости в графе с нечеткими пропускными способностями и нечеткими стоимостями
3.5.5. Задача определения потока минимальной стоимости в графе с нечеткими стоимостями
3.6. Динамические потоки в транспортных сетях с нечеткими исходными данными
3.6.1. Понятия динамического потока и максимального динамического потока в транспортной сети
3.6.2. Постановка задачи определения максимального динамического потока с нечеткими исходными данными
3.6.3. Метод решения задачи о максимальном динамическом потоке в графе с нечеткими пропускными способностями
3.7. Потоки с усилениями
3.7.1. Понятие потока с усилениями
3.7.2. Модель задачи определения потока минимальной стоимости в сети с усилениями
3.7.3. Модификация модели задачи определения потока минимальной стоимости в сети с усилениями для случая использования нечетких данных
3.7.4. Решение задачи определения потока минимальной стоимости в сети с усилениями с нечеткими пропускными способностями
3.7.5. Решение задачи определения потока минимальной стоимости в сети с усилениями при заданных нечетких стоимостях
3.8. Выводы по разделу 3
4. Живучесть нечетких графов
4.1. Анализ живучести нечетких неориентированных графов на основе удаления ребер
4.2. Живучесть нечетких графов на основе сильной связности
4.3. Увеличение степени живучести нечеткого ориентированного графа
4.4. Увеличение степени живучести нечеткого неориентированного графа
4.5. Размещение центров обслуживания с наибольшей степенью живучести
4.5.1. Постановка задачи размещения центров с наибольшей степенью живучести
4.5.2. Метод нахождения центров с наибольшей степенью живучести.
4.5.3. Нахождения центров на основе нечетких баз нечеткого графа
4.6. Использование степени живучести для оценки степени изоморфизма нечетких графов
4.7. Выводы по разделу 4
Заключение
Литература
- Синтез формул комбинирования на основе экспериментальных данных
- Синтаксически независимые лингвистические переменные
- Определение максимального потока от источника к стоку в графе с нечеткими пропускными способностями
- Увеличение степени живучести нечеткого ориентированного графа
Синтез формул комбинирования на основе экспериментальных данных
Анализ позволяет выделить следующие основные сценарии решения оптимизационных задач в среде ГИС: 1) используется некоторая общеприменимая рабочая область карты (не зависящая от задачи), в которой строится графовая модель. Полученный на графовой модели результат считается решением; 2) условия получения решения те же, что и в предыдущем случае, но сам результат подвергается исследованию на качество, исходя из недостатков картографической основы. Результат принимается как решение с оценкой качества и рекомендациями по улучшению; 3) рабочая область задачи строится таким образом, чтобы добиться максимального качества, для чего применяются специальные программные средства и информационные компоненты. Графовая модель использует показатели качества картографической основы, что позволяет использовать полученный результат как окончательное решение.
Сравнивая перечисленные сценарии, необходимо отметить следующее: при использовании первого сценария, поскольку не приняты меры для рационального построения рабочей области (взята «общеупотребимая»), решение задачи трудно интерпретировать из-за неопределенности того, насколько обеспечена актуальность, достоверность и полнота исходного картографического материала для оптимизации. Таким образом, легкость получения решения при работе по первому сценарию компенсируется его неточностью; применение второго сценария является попыткой оценить качество полученного результата. Такой подход рационален в тех случаях, когда пользователь по каким-то причинам не может модифицировать ( улучшить ) рабочую область. Средством оценки может стать использование когнитивных карт [103] - графовых моделей для качественного анализа результата. Можно утверждать, что центр тяжести в таком случае переносится в сторону интерпретации результата, роль оптимизации на графовой модели падает; работа по третьему сценарию компенсирует недостатки, отмеченные выше. Во-первых, строится рабочая область при наличии выбора слоев, объектов, документов и произвольных информационных источников. Аналитик реализует потенциальную возможность построить максимально информативную рабочую область общей карты системы. Во-вторых, растет значимость оптимизации на графовой модели, которая в большей степени становится адекватной реальности. Необходимо отметить, что построение графовой модели - трудноформализуемый процесс из-за многофакторной зависимости от исходных данных, субъективных оценок и предпочтений. Поэтому рациональному построению рабочей области должно предаваться большое значение.
Анализируя процедуры решения задач в среде ГИС, мы приходим к выводу о том, что эффективное решение прикладных задач в значительной степени зависит от того, как построена рабочая область карты. Содержание и выразительность картографического изображения в значительной степени определяют вид и параметры графовой модели, интерпретацию полученного решения. Следовательно, рабочая область должна обладать определенным качеством, достаточным для решения прикладной задачи.
Проблема построения ГИС-аналитиком рабочей области требуемого качества известна [43]. Получить нужную информацию из сложной ГИС все больше становится «попыткой напиться из пожарного шланга» [12], [13]. Как показал анализ, суть проблемы обусловлена следующими факторами: по своей сути электронные карты обладают интегрирующей функцией, объединяя ссылками разнородные информационные ресурсы [57]. Тем самым образуется гипертекстовая структура, скрывающая за графическим изображением обширное информационное пространство. Вследствие подобной «нелинейности» ГИС с картографической основой, включающей более 105 графических примитивов, становятся для пользователя необозримыми и малопонятными; объем информации ГИС растет с течением времени. Состояние объектов и явлений должны фиксироваться с привязкой ко времени, что усложняет поиск объектов и увеличивает неопределенность отображения карт и схем в заданном временном интервале. Заметим, что данный фактор заставляет вводить в состав ГИС подсистему хранилища данных, задачей которой является управление архивной информацией значительного объема; восприятие потока зрительной информации человека ограничено, но условие работы в реальном масштабе времени выдвигает серьезные требования к квалификации пользователя ГИС. Усилия, затрачиваемые на поиск объектов и фрагментов карты, отбор слоев и видовых экранов становятся все более значительными; оценка пользователями информативности и целостности рабочей области общей карты ГИС является субъективной. На отбор объектов влияет ряд НЕ-факторов: неточность, нечеткость, неоднозначность, неопределенность сведений на географических картах [14]. Пользователи, решающие даже одну и туже проблему на основе собственного опыта и знаний, нередко расходятся в оценке качества исходного картографического материала. Поэтому любые детерминированные алгоритмы и средства отбора объектов не дают требуемого эффекта.
Указанные факторы приводят к необходимости создания средств формирования целостных неизбыточных рабочих областей. Именно на этапе построения рабочей области закладывается фундамент решения прикладной задачи. С качеством рабочей области связаны трудоемкость формулировки задачи в терминах графов, параметры графовой модели. В качестве подхода к решению проблемы целесообразно использовать методологию построения картографических образов (КО) [14]. Как показывает анализ, требует дальнейшего развития ряд теоретических вопросов в направлениях: 1) анализа особенностей объектных моделей КО для задач размещения центров обслуживания; 2) исследования принципов синтеза системы КО, начиная с ручного формирования картографических изображений до единой объектной модели; 3) совершенствования методов организации сетевых ГИС, использующих системы КО; 4) анализа качества рабочих областей, строящихся на основе системы КО.
Неформально под избыточностью пользователи понимают те сведения, которые не представляют ценность при решении прикладной задачи. Непосредственное использование подобного определения для разработки средств сокращения избыточности весьма затруднительно, поэтому необходим количественный показатель, который бы отображал как структурную, так и смысловую составляющие избыточности. Под структурной составляющей понимается объем сетевого трафика, под смысловой - субъективно определяемая доля неиспользуемых картографических объектов рабочей области.
Синтаксически независимые лингвистические переменные
Тогда каждая нечеткая ситуация может быть переформирована в нечеткое множество следующего вида [94]: Значения оценок Аї(Л)(л) к = 1,...,Р вычисляются по следующим формулам [94]: - при минимизации критерия, описываемого лингвистической переменной ук; - при максимизации критерия, описываемого лингвистической переменной ук. В формулах (2.17) и (2.18) величина qk определяет число термов для критерия к. Если имеется Р критериев: KVKV...,KP, то лучшей считается альтернатива, удовлетворяющая и критерию К[ и К2, и .... и Кр. Тогда, в соответствии с [28] правило для выбора наилучшей альтернативы может быть записано в виде пересечения соответствующих нечетких множеств:
Операции пересечения нечетких множеств соответствует операция mm, выполняемая над их функциями принадлежности:
Тогда в качестве лучшей альтернативы будет выбираться тот объект /, имеющий наибольшее значение функции принадлежности
Рассмотрим работу этого метода на примере 2.1 из предыдущего раздела. После того, как будут определены нечеткие ситуации и эталонная ситуация, можно определить степени соответствия альтернативы понятию, определяемому критерием Кк, к = 1,...,Р. Для этого для каждой ситуации для каждой лингвистической переменной рассчитаем значения М,{Ук)(ук) , к = 1,...,Р, по формулам (2.17) - (2.18), а также найдем пересечение нечетких множеств по формуле (2.20). Результаты сведем в таблицу 2.2.
Тогда, согласно формуле (2.21), наилучшей будет альтернатива х1, так как значение jUD[x )= maxJuD(xj) = 5/6 . Таблица 2.2.
Критерии различной важности [138]. В случае если критерии Кк, (к = 1,...,Р) имеют различную важность, каждому из них приписывается число ак 0 (чем важнее критерий, тем больше ак), и правило выбора принимает вид: Коэффициенты относительной важности определяются на основе процедуры парного сравнения критериев [28]. Вначале формируется матрица В, элементы которой находятся из таблицы 2.3 и удовлетворяют следующим условиям:
Затем согласно процедуре, описанной в [140], находятся относительные веса рассматриваемых критериев и»,,..., wp . Этот этап состоит из трех шагов: 1) суммирование значений каждого столбца матрицы парных сравнений В; 2) деление каждого элемента матрицы на сумму соответствующего ему столбца. Матрица, получаемая в результате этих действий, называется нормированной матрицей парных сравнений; 3) вычисление средних значений элементов каждой строки нормированной матрицы. Это осуществляется суммированием элементов каждой из строк и делением полученной суммы на число критериев. Такие средние значения и представляют собой относительные веса рассматриваемых критериев w,,..., wp.
Искомые значения коэффициентов ак, к = \,...,Р, получаются умножением элементов w на Р для выполнения условия (2.23): ak=P-wk (2.25) Затем необходимо учесть влияние коэффициентов ак на соответствующие значения лингвистических переменных. Этот учет осуществляется в соответствии с условием (2.22). В связи с этим нечеткая ситуация (2.16) примет следующий вид [138]:
Теперь выбор наилучшего места размещения сервисного центра будет осуществляться по формулам (2.20) и (2.21). Пример 2.3. Снова рассмотрим на примере 2.2 учет критериев различной важности при выборе оптимального места размещения.
Критерии имеют различную важность. Предположим, что первый критерий К] («Стоимость размещения пункта обслуживания») немного важнее критерия К2 («Объем работ станции»), т.е. результат сравнения критериев К{ и К2 -величина 3. Пусть критерий К{ («Стоимость размещения пункта обслуживания») заметно важнее, чем критерий Къ («Важность станции»). Это соответствует значению 7. Наконец, пусть критерий К2 важнее, чем критерий К3. Результат сравнения в этом случае равен 5. Эти значения расположены в правой верхней части матрицы парных сравнений (табл. 2.4).
Если критерий К{ в три раза предпочтительнее, чем критерий К2, то, очевидно, что критерий К2 только в одну треть предпочтительнее, чем критерий К{. Аналогично получаются значения в левой нижней части матрицы парных сравнений. Если критерий сравнивается сам с собой, то в этом случае оценка должна равняться 1.
В результате матрица парных сравнений примет следующий вид: Таблица 2.4. После того, как матрица парных сравнений полностью сформирована, вычисляются веса критериев или собственный вектор матрицы. Для данного примера собственный вектор матрицы В: vv/=0,643; w2=0,283; wj=0,074. Тогда коэффициенты относительной важности критериев равны: а, = 3 0,643 = 1,929 ; а2 = 3 0,283 - 0,849 ; а, = 3 0,074 = 0,222.
Определение максимального потока от источника к стоку в графе с нечеткими пропускными способностями
Для решения рассматриваемых в работе задач оптимизации необходимо задействовать только два слоя: «Станции» и «Дороги».
Слой «Станции» состоит из объектов точечного типа. Каждый такой объект представляет собой одну из станций участка железной дороги. Каждая станция описывается атрибутивными данными: Кодом, Названием и другими.
Слой «Дороги» состоит из объектов линейного типа. Каждый объект «ЖД» представляет собой участок железной дороги между двумя соседними станциями. Каждый такой объект (участок дороги) также описывается атрибутивными данными: Кодами участка, начальной и конечной станций, Протяженностью участка и другими параметрами.
Более подробно описание работы с объектами «Станция» и «ЖД» представлено в [99]. Исходными данными для задач оптимизации являются карты или их фрагменты. После того, как карта, соответствующая определенной теме загружена и определены все необходимые атрибутивные данные, выделяется область на карте, которая охватывает те станции и участки дорог, где необходимо наилучшим образом расположить центры скорой помощи или центры обслуживания. Объекты, попавшие в эту область, называются селектированными объектами [99].
Селекция в системе ObjectLand может осуществляться с помощью режимов «по прямоугольнику», «по кругу», «по полигону». Эти режимы позволяют пользователю селектировать или деселектировать сразу группу объектов, расположенных в определенной области окна, а именно - расположенных в заданном прямоугольнике, круге или полигоне (многоугольнике). При включении одного из этих режимов система позволяет задать на экране соответствующую фигуру [99].
Проводимая в дальнейшем оптимизация будет осуществляться для объектов, попадающих в заданную область.
Рассмотрим пример практического применения алгоритмов решения однокритериальных задач размещения центров обслуживания и центров скорой помощи с учетом исходных данных, представленных в виде лингвистических переменных. Для этого была выполнена программная реализация. Исходная экранная форма, получаемая при запуске программы оптимизации, представлена на
Данная программа позволяет осуществлять ввод исходных данных, решать минисуммные и минимаксные задачи размещения с лингвистическими переменными и с учетом одного критерия, а также сохранять данные.
В качестве исходных данных для оптимизации размещения рассматриваются объекты транспортной сети - станции и участки дорог и данные о станциях и участках дорог, соединяющих эти станции.
В качестве оптимизируемого критерия могут рассматриваться различные критерии, например, критерий «Стоимости», который может представлять собой, например, реальную стоимость проезда по участку дороги, стоимость перевозки грузов на этом участке, длину участка, время проезда и т.п. Значение атрибута рассматриваемого критерия - лингвистическое. В данном случае в качестве критерия оптимизации размещения рассмотрим «Время проезда» между станциями железнодорожной сети.
После того, как необходимые объекты на карте селектированы, из соответствующих таблиц ГБД выбираются записи, соответствующие только выделенным объектам «Станции» и «ЖД». Вся информация об этих объектах заносится в буфер системы ObjectLand, где она обрабатывается. Затем из таблиц выбираются необходимые значения атрибутов: названия станций и стоимости проезда между станциями. Эти данные передаются в модуль реализации алгоритмов размещения. На их основе строится модель, которая представляет собой нечеткий граф.
Нечеткий граф задается матрицей смежности его вершин. Как правило, число вершин графа соответствует числу селектированных объектов «Станции» рассматриваемой области карты. Однако если область оптимизации можно сузить или ограничить определенным типом станций или важностью рассматриваемых станций, то исходный нечеткий граф (и матрица смежности его вершин) будет также ограничена, т.е. в них будут включены не все селектированные станции, а только их часть. При этом ребра графа будут представлять собой цепочку участков, соединяющих выбранные для рассмотрения станции.
Рассмотрим область выделения объектов карты, представленную на рис. 2.26. Ограничим область оптимизации объектами (станциями), представляющими собой наиболее важные. Важность станции определяется экспертом, по оценкам которого формируется модель задачи - нечеткий граф. Пусть в качестве наиболее важных станций будут выбраны: «Валуйки», «Старый Оскол», «Елец», «Мичуринск-Уральский», «Липецк», «Воронеж I», «Лиски». В связи с этим обозначим выбранные станции соответственно XI, Х2, ХЗ, Х4, Х5, Х6, Х7. Тогда ребра графа будут соответствовать цепочке селектированных объектов «ЖД», представляющих участки железной дороги, соединяющие выделенные станции. Так, например, ребро (XI, Х2) соответствует цепочке участков «Валуйки»-«Солоти», «Солоти»-«Рай», «Рай»-«Волоконовка», «Волоконовка»-«Слоновка», «Слоновка»-«Новый Оскол», «Новый Оскол»-«Холки», «Холки»-«Чернянка», «Чернянка»-«Голофеевка», «Голофеевка»-«Котел», «Котел»-«Старый Оскол».
Граф, представленный на рис. 2.27 - неориентированный, т.к. существует путь между станциями в обоих направлениях. Причем часть участка между станциями «Старый Оскол» и «Воронеж I», а также «Елец» и «Мичуринск-Уральский» состоит только из одного пути, что необходимо учитывать при оценке времени проезда между соответствующими станциями.
Ввод лингвистических данных. После того, как определено количество обслуживаемых объектов (в данном случае - 7 станций), а также сформирована модель в виде графа, необходимо определить лингвистические переменные, соответствующие оптимизируемому критерию и их значения. Программа предоставляет возможность ввода лингвистических переменных, а также их лингвистических значений - термов и соответствующих им численных значений.
Сначала необходимо определить лингвистическую переменную, которая будет описывать критерий, приписанный участкам дорог, соединяющим обслуживающие объекты. Это осуществляется при помощи пункта меню «Граф»/«Лингвистические значения». При этом появляется экранная форма (см. рис. 2.28). Теперь можно ввести Имя лингвистической переменной («Время проезда»), значения ее термов (например, «малое», «небольшое», «большое»). Можно также изменить или удалить значения термов лингвистической переменной.
Увеличение степени живучести нечеткого ориентированного графа
Так как каждый динамический поток эквивалентен статическому потоку в развернутом во времени варианте Gp исходного графа, то максимальный динамический поток за р интервалов времени может быть определен с помощью алгоритма поиска максимального потока в развернутом во времени графе, подобному алгоритму Форда-Фалкерсона [128]. Однако если/? велико, то граф Gp станет достаточно большим. Поэтому возрастет и число вычислений необходимых для определения максимального потока в графе.
Для сокращения числа вычислений можно использовать следующий алгоритм [104], предварительно обобщив его на случай нечетких пропускных способностей.
Алгоритм поиска максимального динамического потока. В результате работы алгоритма формируется максимальный динамический поток за р единичных интервалов времени. Этот поток протекает от вершины s к вершине t в графе G = (X,A), в котором q(x,y,T)-q(x,y) для всех моментов времени Г=0, 1, 2, ...,р и всех ребер (х,у)є А.
Считая стоимость ребра (х,у) равной времени z(x,y) прохождения по этому ребру, применить к исходному графу алгоритм поиска потока минимальной стоимости. Выполнение алгоритма продолжать до формирования потока Р. Поток р определяется путями /p,i, fP,2, ..., fp,r„ из s в г, по которым протекает соответственно ьР,і, Ь/,,2, ..., ьР,Гі, единиц потока. Данная декомпозиция потока р является побочным результатом выполнения алгоритма поиска потока минимальной стоимости. Шаг 2. Для j = l,2,...,rp отправлять по каждому пути fpJ pj единиц потока в каждый момент времени 0, 1,2, ..., p-z(fpj). Полученный в результате выполнения шага 2 поток является максимальным динамическим потоком за р единичных интервалов времени.
В данном разделе было показано, каким образом может быть решена задача определения максимального динамического потока в графе с нечеткими пропускными способностями.
В предшествующих рассмотрениях поток, входивший в любую дугу, не изменялся, т.е. количество единиц потока, вошедших в вершину, было равно количеству единиц потока, вышедшего из этой же вершины. При прохождении потока через дугу новые единицы не создавались и старые не исчезали.
Рассмотрим случай, когда потоки, проходящие по дугам, изменяются в процессе их прохождения. Такая ситуация может возникнуть в случаях, когда, например, в ходе перевозки груза между двумя пунктами следования его часть портится и подлежит дальнейшему уничтожению или же происходит прирост груза в пути. Также такие задачи могут рассматриваться при проведении дополнительных погрузочных или разгрузочных работ на станциях в пределах общего маршрута перевозки. В данном случае под дополнительными погрузочными или разгрузочными работами понимается догрузка или отгрузка части перевозимого груза.
При приросте или уменьшении количества груза в пути будем считать, что если в любую дугу (х,у) в вершине хе X входит (х,у) единиц потока, то из этой дуги в вершине у выйдет к-{х,у) единиц потока. Можно считать, что каждая единица потока, проходящая по дуге (х,у), умножается на величину к(х,у). Эта величина называется коэффициентом усиления или просто усилением дуги (х,у) [53].
Если к(х,у) 1, то поток в дуге (х,у) усиливается. Если к{х,у)-\, то поток в дуге (х,у) остается неизменным. Если 0 к(х,у) 1, то поток в дуге (х,у) ослабляется. Если к(х,у) = 0, то поток в дуге теряется, и данная дуга может рассматриваться как сток. В дальнейшем предполагается, что все дуги (х,у), для которых к(х,у) = 0, заменены стоками. Если к(х,у) 0, то для каждой единицы потока, входящей в вершину хе X, в вершину уеХ должно попадать -к{х,у) единиц потока, т.е. в данном случае дуга (х,у) может рассматриваться как порождающая спрос на поток.
При проведении дополнительных погрузочных или разгрузочных работ на станциях в пределах общего маршрута перевозки формулировка задачи поиска потока в сети с усилениями может быть сведена к приведенной выше формулировке. Это достижимо путем представления погрузочно-разгрузочных станций отличными от остальных вершинами графа, описывающего модель транспортной сети. Тогда учет изменения потока за счет этих вершин может производиться путем замены двух инцидентных такой вершине дуг одной дугой в графе [139]. Рассмотрим этот случай на следующем примере (см. рис. 3.20). Граф, представленный на рис. 3.20, включающий вершины и ребра, представленные сплошными линиями, является графом (сетью) с усилениями. Обозначим его G =(X ,A ).
Главной задачей будет являться задача о потоке минимальной стоимости в сети с усилениями. Как можно понять из названия, будет рассматриваться задача поиска оптимального с точки зрения затрат способа пересылки через сеть потока из источника в сток при заданном количестве v единиц потока в источнике и при наличии усиления в дугах сети. При этом необходимо иметь в виду, что если из источника в сеть отправляется v единиц потока, то количество единиц потока, прибывающих в сток из-за усиления в дугах, не обязательно совпадает с величиной потока v.
Для сравнения следует отметить, что во всех потоковых задачах, которые рассматривались в предыдущих разделах, количество единиц потока, выходивших в сеть из источника, всегда равнялось количеству единиц потока, прибывавших в сток.
Пусть в графе с усилениями G -(X ,A ) для дуги (х,у) задается максимальное количество единиц потока q{x,y) (пропускная способность), которое может входить в дугу (х,у), а также стоимость с(х,у) прохождения по дуге каждой вошедшей в нее единицы потока. Как и в предыдущих разделах %{х,у) снова обозначает количество единиц потока, входящих в дугу (х, у).
Тогда задача о потоке минимальной стоимости в сети с усилениями может быть сформулирована следующим образом [53]: с(х,у) - стоимость единицы потока, протекающего по дуге (х,у) є А , ,{х,у) - величина потока, протекающего по дуге (х,у) є А , q(x,y) - значение пропускной способности для дуги (х,у) є А графа С, к(у,х) - коэффициент усиления потока в дуге {у,х) є А , v - заданная величина потока, вытекающего из источника. Выражение (3.68) определяет общую стоимость потока. Уравнение (3.69) показывает, что чистый поток из вершины s должен быть равен v, а чистый поток из любой другой вершины, не считая вершины t, должен быть равен 0. Соотношение (3.70) показывает, что величина потока в каждой дуге должна быть меньше пропускной способности дуги.
Похожие диссертации на Теория и практика решения комплекса оптимизационных задач на сетях при нечетких данных в геоинформатике
