«Посвящается 60-летию высшего профессионального лесного образования в Республике Коми Л. Э. Еремеева ПОТОКИ В СЕТЯХ Учебное пособие Утверждено учебно-методическим советом Сыктывкарского лесного института в качестве ...»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

СЫКТЫВКАРСКИЙ ЛЕСНОЙ ИНСТИТУТ (ФИЛИАЛ)

ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО

ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

ЛЕСОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ С. М. КИРОВА»

Посвящается 60-летию высшего профессионального лесного образования в Республике Коми Л. Э. Еремеева

ПОТОКИ В СЕТЯХ

Учебное пособие Утверждено учебно-методическим советом Сыктывкарского лесного института в качестве учебного пособия для студентов направлений подготовки 270000 «Архитектура и строительство»

и 190000 «Транспортные средства» всех форм обучения

СЫКТЫВКАР

СЛИ УДК 517.977. ББК 39. Е Печатается по решению редакционно-издательского совета Сыктывкарского лесного института Ответственный редактор:

В. И. Чудов, кандидат технических наук, доцент Рецензенты:

кафедра экономической теории и корпоративного управления (Сыктывкарский государственный университет);

Р. Р. Гарипов, кандидат экономических наук (Министерство развития промышленности и транспорта РК) Еремеева, Л. Э.

Потоки в сетях : учебное пособие / Л. Э. Еремеева ; Сыкт. лесн. ин-т.

Е — Сыктывкар : СЛИ, 2012. — 100 с.

ISBN 978-5-9239-0316- Издание содержит основы организации потоковых процессов и оптимизационного инструментария с использованием методов линейного программирования на основе современных тенденций логистики и принципов эффективности функционирования экономических систем. После каждой главы приведены контрольные вопросы по теме. Приведены тестовые аттестационно-педагогические измерительные материалы для обеспечения возможности проверки остаточных знаний студентов и примерные вопросы к экзамену.

Предназначено для студентов направлений подготовки 270000 «Архитектура и строительство» и 190000 «Транспортные средства» всех форм обучения.

УДК 517.977. ББК 39. Темплан 2010/11 учеб. г. Изд. № 14.

ISBN 978-5-9239-0316-4 © Еремеева Л. Э., © СЛИ,

ОГЛАВЛЕНИЕ

Предисловие

Введение

Глава 1. Задачи сетевого планирования. Сетевая модель комплекса работ............... Глава 2. Применение календарного планирования. Задача о порядке передачи сообщений по каналу связи

Глава 3. Классификация видов моделирования систем

Глава 4. Значение имитационного моделирования для производственных систем и процессов

Глава 5. Основные термины, параметры и система обозначений в потоковых задачах

Глава 6. Сети с нелинейными функциями стоимости дуг

Глава 7. Свободный поток, свободный узел и его параметры

Глава 8. Условие сохранения потока

Глава 9. Алгебраическая модель сети

Глава 10. Основные понятия из теории графов

Глава 11. Стандартная задача о потоке минимальной стоимости

Глава 12. Задача о кратчайшем пути

Глава 13. Оптимизационный алгоритм Дийкстры

Глава 14. Транспортная задача. Задача о назначениях. Задача о максимальном потоке. Сети с выигрышами

Глава 15. Разрез и пропускная способность разреза. Понятие расширенной и предельной сети. Задача о максимальном потоке

Глава 16. Решение задачи о максимальном потоке с помощью алгоритма Форда — Фалкерсона

Глава 17. Основные понятия логистических процессов

Тесты по дисциплине

Примерные вопросы к экзамену

Заключение

Глоссарий

Библиографический список

ПРЕДИСЛОВИЕ

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

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

Для таких взвешенных графов обычно формулируются задачи двух типов:

1) оценить (точно, приближенно или гарантированно) те или иные функционалы, заданные на этих графах;

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

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

Одной из первых книг на русском языке, в которой были подробно рассмотрены задачи исследования потоков на графах, была переведенная с английского языка монография Л. Р. Форда и Д. Р. Фалкерсона «Потоки в сетях» (М.: Мир, 1966). Эта книга изобиловала концептуальными положениями, описанием возможных результатов, а также принципиальными математическими постановками и решениями. Из отечественных хотелось бы отметить книгу Г. М. Адельсона-Вельского, Е. А. Диница и А. В. Карзанова «Потоковые алгоритмы» (М.: Наука, 1975), посвященную описанию наиболее «экономных» потоковых алгоритмов и методов их построения, а из иностранных — переведенную с английского языка книгу П. Йенсена и Д. Барнеса «Потоковое программирование»

(М.: Радио и связь, 1984). Однако до настоящего времени отсутствует книга, имеющая характер учебного пособия, в котором системно излагались бы основы и терминология потоков в сетях, приемы и алгоритмы решения потоковых задач.

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

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

ВВЕДЕНИЕ

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

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

– основные понятия, используемые в сетевом моделировании;

– способы сведения прикладных задач к потоковым задачам;

– взаимосвязь между различными потоковыми задачами и методы их решения;

– способы представления, хранения и преобразования данных;

– основные алгоритмы потокового программирования;

– технологию решения оптимизационных потоковых задач на ЭВМ.

Дополнение к Государственному общеобразовательному стандарту высшего профессионального образования по дисциплине «Потоки в сетях» содержит: определение сети; параметры узлов и дуг; моделирование потоковых процессов; оптимизационные алгоритмы; маршрутизацию;

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

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

1. Как сформулировать интересующую его проблему в виде задачи о потоке в сети?

2. Какой алгоритм выбрать для решения сформулированной задачи?

3. Как создать надежную программную реализацию выбранного алгоритма на ЭВМ и получить численное решение задачи?

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

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

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

ЗАДАЧИ СЕТЕВОГО ПЛАНИРОВАНИЯ.

СЕТЕВАЯ МОДЕЛЬ КОМПЛЕКСА РАБОТ

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

– методы наглядной записи всей информации о планируемом комплексе работ;

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

– методы вычисления других важных характеристик проекта.

Задачи рационального планирования сложного комплекса работ имеют следующие общие черты:

1) весь комплекс работ представляет собой совокупность элементарных работ;

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

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

Термин «работа» может иметь различные значения:

– действительная работа, требующая затрат времени и ресурсов;

– ожидание — процесс, не требующий затрат труда, но занимающий время (например, процессы сушки пиломатериалов, твердения бетона и т. д.);

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

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

Сетевой график ограничен исходным и завершающим событиями.

Исходное событие (источник) не имеет предшествующих работ и событий.

Завершающее событие (сток) не имеет последующих работ и событий.

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

Исходная информация о работах, которые требуется выполнить, должна содержать:

– перечень всех работ;

– последовательность их выполнения;

– оценку каждой работы (продолжительность, стоимость и т. п.).

Так, например, информация о некотором проекте может быть задана в виде структурной таблицы комплекса работ (табл. 1.1).

Таблица 1.1 — Информация о реализуемом проекте Сетевой график строится следующим образом:

– кружками обозначаются события;

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

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

Пусть 0 — исходное событие.

Работы a1 и a2 не имеют предшествующих работ, поэтому они выходят из исходного события.

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

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

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

Работы a9 и a10 опираются на работы a4, a5 и a7, поэтому необходимо объединить концы дуг, соответствующие этим работам, в виде нового события (номер 4), а затем из события 4 изобразить три дуги, соответствующие работам a4, a5 и a7.

Работы a11 и a12 опираются на работы a6 и a9, поэтому концы дуг, соответствующие работам a6 и a9, объединяются в виде очередного события (номер 5), и из события 5 изображаются две дуги, соответствующие работам a11 и a12.

Работа a13 опирается на работы a8, a10 и a11, поэтому концы дуг, соответствующие работам a8, a10 и a11, объединяются в виде следующего события (номер 6), из которого изображается дуга, соответствующая работе a13.

На работы a12 и a13 не опирается ни одна работа, поэтому их окончанием служит завершающее событие (номер 7).

Сетевой график изображен на рис. 1.1. Он выражает логическую связь в последовательности событий и работ.

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

События являются упорядоченными, если для каждой работы номер ее начального события меньше номера ее конечного события. Работу в сетевых графиках принято кодировать парой (i, j), где i — номер начального, а j — номер конечного события (рис. 1.2).

В пронумерованной сети для каждой работы (i, j) всегда i < j. Продолжительность работы tij принято проставлять в сетевом графике над соответствующей стрелкой.

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

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

с указанием ранних и поздних сроков свершения событий Продолжительностью пути называется время, необходимое для выполнения всех работ, лежащих на этом пути. Обычно на сети существует несколько полных путей различной продолжительности. Не трудно понять, что критическое время равно продолжительности самого длительного по времени полного пути (Lкр = 3 + 4 + 1 + 5 = 13).

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

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

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

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

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

1. Для решения каких производственных задач используется сетевое планирование?

2. Какой параметр оптимизируется при решении сетевых задач?

3. Что означает термин «действительная работа»?

4. Что означает термин «фиктивная работа»?

5. Что необходимо предпринять для ускорения выполнения комплекса работ?

6. Что означает термин «критический путь»?

7. Как называется в сетевом планировании момент, к которому заканчиваются все входящие в него работы?

8. Какой смысл вкладывается в критическое время при сетевом планировании?

ПРИМЕНЕНИЕ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ.

ЗАДАЧА О ПОРЯДКЕ ПЕРЕДАЧИ СООБЩЕНИЙ

ПО КАНАЛУ СВЯЗИ

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

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

Рассмотрим вначале простую задачу с одним каналом связи. Предположим, что по каналу связи необходимо передать n сообщений длительности t1, t2, …, tn. Каким должен быть наилучший порядок передачи сообщений? Ясно, что общее время передачи всех сообщений (время занятости канала) будет одним и тем же при любой последовательности среднее время ожидания передачи для одного сообщения tож, а также среднее время пребывания одного сообщения в системе tпр. Эти величины разумно принять в качестве критерия оптимальности.

Пример 1. Пусть требуется передать n = 3 сообщения J1, J2, J3, длительности которых равны соответственно 4, 3 и 1 мин.

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

1-е расписание — (J1, J2, J3); 4-е расписание — (J2, J3, J1);

2-е расписание — (J1, J3, J2); 5-е расписание — (J3, J1, J2);

3-е расписание — (J2, J1, J3); 6-е расписание — (J3, J2, J1).

Определим средние времена ожидания tож и пребывания сообщения в системе t пр, присущие 1-му и 6-му расписанию:

– для расписания (J1, J2, J3):

– для расписания (J3, J2, J1):

Таким образом, изменение плана передачи существенно повлияло на среднее время ожидания и среднее время пребывания сообщения в системе (рис. 2.1).

Рисунок 2.1 — Диаграмма передачи сообщений по одному каналу В общем случае оптимальное решение здесь очевидно: передача сообщений должна производиться с того сообщения, для которого длительность передачи минимальна, в порядке возрастания этой величины.

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

Рассмотрим задачу о порядке передачи сообщений по двум каналам связи и график Ганта. Необходимо передать n сообщений различной длительности последовательно сначала по одному, а затем по второму каналу связи. Предполагается заданным время tij передачи i-го сообщения по j-му каналу: i = 1, 2, …, n; j = 1, 2. В этой задаче общее время передачи всех сообщений уже зависит от порядка их запуска. Требуется найти порядок запуска сообщений, при котором общая длительность их передачи по двум каналам была бы минимальной.

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

Пусть имеются два сообщения J1 и J2, которые надо передать по двум каналам. Для первого сообщения время передачи соответственно равно 6 и 3 мин, а для второго сообщения — 2 и 8 мин. Возможны два плана передачи (J1, J2) и (J2, J1). Для первого плана, как видно из рис. 2.2а, суммарное время передачи составит 17 мин, а для второго плана (рис. 2.2б) суммарное время передачи уменьшится до 13 мин.

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

Рисунок 2.2 — Диаграмма передачи сообщений по двум каналам В общем виде для любого числа сообщений поставленная задача решена С. Джонсоном. Им доказана оптимальность следующего порядка передачи сообщений. Все сообщения условно делятся на две группы.

К первой группе относятся все сообщения, для которых ti, 1 ti, 2, т. е. время передачи которых по первому каналу не превосходит времени передачи по второму каналу. Остальные сообщения относятся ко второй группе. Сначала передаются сообщения первой группы в порядке возрастания времени их передачи по первому каналу. Затем передаются сообщения второй группы в порядке убывания времени их передачи по второму каналу.

Пример 3. Определить оптимальный порядок передачи пяти сообщений по двум каналам связи, для которых величины tij (мин) даны в табл. 2.1.

Таблица 2.1 — Исходные данные для решения примера Согласно алгоритму Джонсона, следует включить в первую группу сообщения с номерами 1 и 4, а во вторую — с номерами 2, 3 и 5. Оптимальный порядок передачи сообщений следующий: 4, 1, 3, 5, 2.

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

Здесь каждому каналу соответствует своя ось времени t, на которой отрезками прямых отмечены промежутки, в течение которых данный канал занят передачей того или иного сообщения. Как видно из графика, второй канал будет простаивать по 1 мин перед передачей 4-го, 1-го и 3-го сообщений, а также 3 мин перед передачей 5-го сообщения. Время передачи всех сообщений займет Tmin = 22 мин.

1. Какое название носят задачи календарного планирования?

2. К каким задачам программирования сводятся задачи календарного планирования?

3. Какие критерии принимаются в качестве критерия оптимальности задач календарного планирования?

4. С какого сообщения должна производиться передача сообщений: начиная с максимальной длительности передачи или минимальной?

5. Что описывает график Ганта?

6. Какой оптимальный порядок передачи сообщений при календарном планировании доказан С. Джонсоном?

7. Что можно интерпретировать в качестве каналов связи в лесоперерабатывающем предприятии?

КЛАССИФИКАЦИЯ ВИДОВ МОДЕЛИРОВАНИЯ СИСТЕМ

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

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

В зависимости от формы представления объекта, моделирование можно разделить на два больших класса: материальное и идеальное (рис. 3.1).

МОДЕЛИРОВАНИЕ СИСТЕМ

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

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

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

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

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

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

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

Математическое моделирование можно разделить на аналитическое, имитационное и комбинированное.

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

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

Комбинированное (аналитико-имитационное) моделирование при анализе и синтезе систем позволяет объединить достоинства аналитического и имитационного моделирования.

Математическое моделирование имеет два существенных преимущества перед остальными видами моделирования:

1) дает быстрый ответ на поставленный вопрос, на что в реальной обстановке может потребоваться длительное время, иногда даже годы;

2) дает возможность экспериментирования, осуществить которое на реальном объекте зачастую просто невозможно.

Рисунок 3.2 — Спектр применения имитационного моделирования Общую схему математического моделирования можно изобразить в виде, представленном на рис. 3.3.

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

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

В зависимости от характера изучаемых процессов в системе, математические модели бывают:

1) статические — отражают поведение объекта в какой-либо момент времени (например, поперечный разрез объекта);

2) динамические — отражают поведение объекта во времени (временные ряды);

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

4) стохастические — отображают вероятностные процессы и события;

5) дискретные — предназначены для описания дискретных процессов;

6) непрерывные — отражают непрерывный характер процессов, протекающих в системе;

7) дескриптивные — служат лишь для описания процессов функционирования, протекающих в системе;

8) оптимизационные — позволяют управлять характеристиками процессов.

Требования, предъявляемые к математическим моделям: адекватность, непротиворечивость, универсальность, экономичность.

Основные требования к построению математических моделей информационных систем:

1) Математическая модель должна отражать основные свойства исследуемого объекта с точки зрения интересующего параметра или группы параметров.

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

3) Математическая модель должна быть адаптированной под имеющиеся исходные данные.

4) Математическая модель должна быть легко модифицируемой при появлении новых исходных данных или новых сведений о внутренней природе системы.

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

1. Какое практическое значение для менеджмента имеет построение моделей?

2. На какие два больших класса можно разделить моделирование?

3. Какие разновидности натурного эксперимента известны?

4. Что является основным преимуществом имитационного моделирования по сравнению с аналитическим?

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

6. Какие существенные преимущества перед остальными видами моделирования имеет математическое моделирование?

7. В зависимости от характера изучаемых процессов в системе какие математические модели бывают?

8. Каковы основные требования к построению математических моделей информационных систем?

ЗНАЧЕНИЕ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

ДЛЯ ПРОИЗВОДСТВЕННЫХ СИСТЕМ И ПРОЦЕССОВ

Имитационное моделирование есть процесс конструирования модели реальной системы и постановки экспериментов на этой модели.

Оно является экспериментальной и прикладной методологией, имеющей целью описать поведение системы, построить теории и гипотезы, объясняющие наблюдаемое поведение системы, использовать эти теории для предсказания будущего поведения системы.

Имитационное моделирование — это представление динамического поведения системы посредством продвижения ее от одного состояния к другому в соответствии с определенными правилами.

Специальные программы, обслуживающие модель, генерируют различные конкретные реализации входного сигнала x(t) моделируемой системы и строят в соответствии с введенным в ЭВМ описанием системы выходной сигнал y(t). Далее, как и в обычном (натурном) эксперименте, полученные результаты обрабатываются с помощью специальных программ, строящих, например, гистограммы распределений тех или иных величин, характеризующих поведение исследуемой системы. Таким образом решаются задачи анализа кибернетических систем.

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

Имитационные модели применяются в качестве:

– средства осмысления действительности;

– средства общения;

– средства обучения и тренажа;

– средства постановки и проведения экспериментов;

– инструмента прогнозирования.

Имитационные модели могут служить для достижения одной из двух основных целей:

– либо описательной, если модель служит для объяснения или лучшего понимания системы;

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

Имитационная модель должна быть:

1) простой и понятной пользователю;

2) надежной в смысле гарантии от абсурдных ответов;

3) удобной в управлении и обращении;

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

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

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

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

В информационных системах применение имитационного моделирования связано с анализом:

1) процессов получения, хранения и переработки информации;

2) задач выработки решений в условиях неопределенности;

3) процессов передачи информации при ограничениях на материальные, временные, финансовые ресурсы;

4) динамики передачи информации с учетом ненадежности каналов связи;

5) задач проектирования и создания новых информационных систем;

6) прогнозирования развития информационных процессов и систем;

7) задач теории расписаний при передаче информации;

8) задач массового обслуживания, управления запасами.

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

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

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

Недостатки имитационного моделирования следующие:

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

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

Последовательность имитационного моделирования системы:

1. Формулировка проблемы: ясное и четкое изложения целей эксперимента.

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

3. Разработка имитационной модели системы, реализация ее в виде программы на ЭВМ и проверки модели.

4. Реализация имитационной модели в виде программы на ЭВМ связана с двумя задачами:

а) выбором языка программирования (для написания программы на ЭВМ у исследователя имеется две возможности: 1) использовать универсальный язык программирования (типа FORTRAN, PASCAL, BASIC, C и др.) или 2) остановиться на специализированном языке имитационного моделирования (типа ДИНАМО, GPSS, СИМУЛА и т. п.));

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

5. Проведение имитационного эксперимента, включающего планирование, проведение и обработку результатов эксперимента.

1. Что такое имитационное моделирование?

2. Раскройте понятие математической модели.

3. Для достижения каких целей могут служить имитационные модели?

4. Приведите основные требования к имитационной модели.

5. Для решения каких задач лесного хозяйства используются имитационные модели?

6. Для решения каких задач транспортно-дорожного комплекса используются имитационные модели?

7. Перечислите достоинства и недостатки имитационного моделирования.

8. Какова последовательность имитационного моделирования системы?

ОСНОВНЫЕ ТЕРМИНЫ, ПАРАМЕТРЫ И СИСТЕМА

ОБОЗНАЧЕНИЙ В ПОТОКОВЫХ ЗАДАЧАХ

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

При описании указанных ситуаций говорят о «потоках в сетях».

Потоком в сети по дуге к (fk) или по дуге ij (fij) называется неотрицательная вещественная функция, удовлетворяющая следующим условиям:

1. Условие ограниченности: поток по любой дуге сети не превосходит пропускной способности этой дуги: fij cij;

2. Условие сохраняемости: суммарный поток, заходящий в любую вершину сети (кроме истока и стока), равен суммарному потоку, выходящему из этой вершины.

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

Сеть представляет собой совокупность узлов и дуг (рис. 5.1). Данная сеть состоит из шести узлов и восьми дуг. Начальный узел обозначается «s» и называется истоком, а конечный узел обозначается «t» и называется стоком. Допускается обозначение начального и конечного узлов заглавными буквами. Такое представление оказывается полезным при моделировании самых разных ситуаций и физических процессов. На практике сети очень часто используют для описания различных систем:

управления запасами, транспортировки, распределения и т. п.

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

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

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

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

1) значением потока по сети (fk);

2) минимальным значением потока (с k ), который может протекать по дуге (нижняя граница);

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

4) стоимостью передачи единицы потока по данной дуге (hk), которая показывает, во что обойдется передача единицы потока по k-й дуге.

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

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

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

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

В ориентированной сети имеются множество узлов N и множество дуг M. Числовые значения, приписанные дугам и узлам сети, называют параметрами. Для обозначения параметров потока используется fij — поток по дуге из узла i в узел j. При этом узел i называется начальным, а узел j — конечным для дуги ij.

Основными параметрами узлов в сетевых моделях являются:

bi — фиксированный внешний поток в узле i;

сij — верхняя граница (пропускная способность) передачи потока по дуге из узла i в узел j;

hij — стоимость передачи единицы потока по дуге из узла i в узел j.

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

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

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

Исходная сеть из четырех узfk (hk) таким понятием, как расширенная сеть (рис. 5.3). Расширенная сеть Рисунок 5.3 — Расширенная сеть легко получается из исходной сети.

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

В расширенной сети каждой дуге k соответствует противоположно ориентированная дуга (–k), которая связывает ту же пару вершин, но ориентированных противоположно. Дугу (–k) называют обратной дугой. При этом если дуга k имеет стоимость hk, то дуга (–k) имеет стоимость (–hk).

Множество узлов в расширенной сети DE совпадает с множеством узлов в исходной сети D:

а множество дуг в два раза больше:

Множество узлов предельной сети D* совпадает с множеством узлов исходной сети D:

а множество дуг M* является подмножеством дуг расширенной сети ME:

M* образует допустимые дуги. Следует учесть, что дуга может быть прямой или обратной.

Существуют условия допустимости дуг:

– прямая дуга считается допустимой, если поток по ней можно увеличить, т. е. fk < сk, f. Допустимость прямой дуги помечается знаком «+»;

– обратная дуга считается допустимой, если поток по ней можно уменьшить, т. е. fk < сk, f. Допустимость обратной дуги помечается знаком «–». Поток можно уменьшить до 0. Если поток fk = 0, то дуга перестает существовать.

1. Что представляет собой сеть в потоковых задачах?

2. Сформулируйте понятие потока в сети.

3. В чем заключается сущность задач потокового программирования?

4. Что называется истоком и стоком в сети?

5. Какими основными параметрами характеризуется дуга в сети?

6. Что называется прямой дугой и обратной дугой?

7. Каковы условия допустимости дуг (прямой и обратной)?

8. Какими основными параметрами характеризуется узел в сети?

СЕТИ С НЕЛИНЕЙНЫМИ ФУНКЦИЯМИ СТОИМОСТИ ДУГ

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

Распознать нелинейную функцию можно, проведя пунктирный отрезок (рис. 6.1): если пунктирная линия окажется выше нелинейного отрезка функции стоимости дуги, то функция относится к выпуклой, а если прямой пунктирный отрезок лежит ниже, то функция относится к вогнутой.

Рисунок 6.1 — Линейные (а) и нелинейные (б) функции стоимости дуг Один из часто применяемых методов решения потоковых задач стоимости нелинейных функций — это кусочно-линейная аппроксимация (приближение). В этом случае выпуклый участок можно составить из отдельных линейных участков (рис. 6.2).

Рисунок 6.2 — Решение нелинейной выпуклой функции При этом стоимость на каждом предыдущем участке меньше, чем на последующем за ним участке: h1 < h2 < h3, а тангенсы углов наклона участков кривой tg 1, tg 2, tg 3 можно представить следующим образом:

В рассматриваемом случае нелинейную дугу вместо тривиальной схемы (рис. 6.3) можно представить в виде трех дуг (рис. 6.4).

для кусочно-линейной аппроксимации выпуклой функции Так как h1 < h2 < h3, то поток вначале пойдет по дуге 1, пока его значение не достигнет U1, потом по дуге 2, пока не достигнет U2, затем по дуге 3. Второй участок вогнутой функции стоимости (рис. 6.1б) на практике встречается чаще, чем выпуклая, т. к. отражает экономический закон относительного уменьшения стоимости при увеличении объема производства продукции (экономии от масштаба). К сожалению, такую функцию нельзя свести к линейной задаче: т. к. h1 > h2 > h3, поток приходится отправлять сначала по дуге с большей стоимостью, и далее со снижающейся стоимостью.

Для решения задач вогнутой функции используются различные процедуры целочисленного исчисления.

Проиллюстрируем решение нелинейной функции (табл. 6.1).

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

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

Коэффициент наклона первого линейного участка:

Коэффициент наклона второго линейного участка:

Коэффициент наклона третьего линейного участка:

Полученный график участков линейных функций приближен к заданной нелинейной функции (рис. 6.5). Погрешность равна = 54. Для уменьшения погрешности можно взять другие граничные точки, т. е.

увеличить количество дуг с линейными функциями стоимости.

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

Интерфейс решения задачи с нелинейными функциями стоимости описан в методическом пособии «Решение потоковых задач в MS Excel»

[2, с. 32—35].

1. Какой метод решения потоковых задач нелинейной функции стоимости вам известен?

2. Какая функция относится к выпуклой?

3. Какая функция относится к вогнутой?

4. Какая нелинейная функция отражает экономический закон относительного уменьшения стоимости при увеличении объема производства продукции?

5. В чем заключается кусочно-линейная аппроксимация?

6. Как определяется коэффициент наклона линейного участка?

7. Каким образом определить достаточность участков линейных функций при решении нелинейной функции?

СВОБОДНЫЙ ПОТОК, СВОБОДНЫЙ УЗЕЛ И ЕГО ПАРАМЕТРЫ

Сетевая модель потоков любой бизнес-единицы включает в себя «вход» (поставщики) и «выход» (потребители). Поэтому для постановки и решения потоковых задач вводятся, кроме фиксированного внешнего потока (ФВП) bi, два дополнительных параметра — это свободный внешний поток (СВП) bsi и стоимость свободного внешнего потока (ССВП) hsi.

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

Рассмотрим сеть со свободbi, bsi, hsi] ным потоком [bi, bsi, hsi] (рис. 7.1).

рис. 7.1.

внешний поток 2, свободный внешний поток 2, стоимость потока 1.

внешний поток 1, свободный Рисунок 7.1 — Сеть со свободным потоком внешний поток 2, стоимость потока –2.

Узел 3: фиксированный внешний поток 0, свободный внешний поток –2, стоимость потока 1.

Узел 4: фиксированный внешний поток –1, свободный внешний поток –2, стоимость свободного внешнего потока 1.

Рассмотрим порядок решения задачи о сети со свободным потоком.

Структура сети определяется множеством узлов и множеством дуг: N — множество узлов. Узел i является элементом множества узлов N = 1, 2, 3, …, i, …, n или i = 1, n, где n — количество узлов в сети; М — множество дуг. Дугу можно задать по-разному: как упорядоченную пару узлов (i, j) или как элемент k списка дуг М = 1, 2, 3, …, k, …, m. Таким образом, дугу можно называть дуга k (i, j) или просто (i, j). Узел i называется начальным узлом, а узел j называется конечным узлом дуги.

Для сети составляют список начальных и конечных узлов:

О — список начальных узлов: О = [o1, o2, …, om].

Т — список конечных узлов: T = [t1, t2, …, tm].

Иногда вводят дополнительные списки дуг:

МОi — список дуг, которые выходят из узла i;

МTi — список дуг, которые входят в узел i.

Пример описания сети показан на рис. 7.2.

Список узлов рассматриваемой сети:

- начальных узлов: О = [1, 1, 2, 2, 3];

- конечных узлов: T = [2, 3, 3, 4, 4].

Список дуг рассматриваемой сети:

- выходят из узла 1: МО1 = [1, 2];

- входят в узел 1: МТ1 = [] (пустое множество);

- выходят из узла 2: МО2 = [3, 4];

- выходят из узла 3: МО3 = [5];

- выходят из узла 4: МО4 = [] (пустое множество);

Итак, потоком в сети называется множество чисел fk, определенных на дугах k, удовлетворяющих условиям ограниченности и сохраняемости. Условие ограниченности отображается как fk ck, где ck — пропускная способность.

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

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

Вектор потока определяется как f = [f1, f2, f3, …, fm], где штрих в верхнем индексе означает операцию транспортирования данной векторстроки, т. е. f является вектор-столбцом. Его значения и необходимо найти в задачах.

Потоки являются изменяемыми переменными, при этом их стоимость h(fk) — функция потока по дуге k — не зависит от других потоков по дугам.

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

Уравнение означает, что сумма стоимостей по всем дугам минимальна.

В случае линейной зависимости функция стоимости отражается как Вектор-столбец дуговых стоимостей отражается как Пропускная способность ck является ограничением потока по дуге:

Вектор-столбец пропускной способности отражается как Ограничение на поток снизу записывается следующим образом:

Нижняя граница пропускной способности отражается как Внешние потоки попадают в сеть с определенными характеристиками, где bi — фиксированный внешний поток в узле i; bsi — свободный внешний поток в узле i; his — стоимость свободного внешнего потока.

В результате стоимость потока в сети можно отразить в виде следующего уравнения:

Свободные потоки можно представить, используя параметры дуг, а не узлов. Для этого вводится свободный узел. Начертим сеть (рис. 7.3) и найдем свободный узел (рис. 7.4). Этот узел обозначим 5. В свободном узле не требуется выполнение условия сохранения потока (УСП).

Рисунок 7.3 — Исходная сеть со свободным потоком Рисунок 7.4 — Преобразование сети с введенным свободным узлом В узлах 1, 2, 3 свободный внешний поток не равен нулю (bsi 0).

Если bsi > 0, то вводится дуга из свободного узла в данный узел 5.

В узлы 1, 2, 3 вводятся дуги со свободным узлом, при этом направление вводимых дуг определяется исходя из положительности или отрицательности свободного внешнего потока:

– Если узел, в котором bsi < 0, то дуга от него вводится в свободный узел. Из узла 3 вводится дуга в свободный узел 5 (рис. 7.4).

– Если узел, в котором bsi > 0, то дуга из свободного узла вводится в него. Во 2-й узел вводится дуга из свободного узла 5, также из свободного узла 5 вводится дуга в узел 1. При этом значение свободного потока узла переходит в пропускную способность дуги bsi ck:

При этом знак «–» перешел в направление стрелки (из параметра свободного внешнего потока узла 3 в значение пропускной способности дуги 8, имеющей направление выходящей из узла 3).

На рис. 7.5 знак «–» около значения стоимости передачи единицы потока по дуге 6 говорит о том, что при передаче потока по этой дуге получен доход.

В ходе преобразования убираем bsi.

Стоимость передачи единицы потока по дуге переходит в стоимость вводимой дуги hsi hk:

В ходе преобразования убираем hsi.

В рассмотренной сети можно предположить, что узел 1 — это магазин, на его складе в наличии имеется 3 ед. товара. Узел 4 — это потребитель, которому нужно 5 ед. товара. Встает вопрос, где взять недостающие 2 ед. товара. Для этого необходим свободный узел 5, в котором берем недостающие 2 ед. товара.

1. Сформулируйте понятие свободного потока.

2. Каковы правила установления знаков свободного потока?

3. Как составляется список начальных узлов?

4. Как составляется список конечных узлов?

5. Для чего в сети вводится свободный узел?

6. От какого параметра и как зависит, вводится дуга в свободный узел или выводится из него?

7. В какой параметр переходит значение свободного потока узла?

УСЛОВИЕ СОХРАНЕНИЯ ПОТОКА

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

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

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

Опишем дуги входящие (–) и выходящие (+) из узлов:

Примечание. fi — переменная, которую необходимо найти для минимальной стоимости потока в сети.

Дуги, которые связаны со свободными узлами, называются свободными. А дуги, которые не связаны со свободными узлами, называются несвободными. В некоторых столбцах элементы парные: один f со знаком «+», другой со знаком «–». Необходимо провести суммирование по столбцам. Если в результате в столбце суммирование даст результат 0, то УСП соблюдается. Если результат в другой, то УСП не соблюдается.

Таким образом, условие сохранения потока соблюдается в 1—4 узлах, за исключением 5-го узла.

Другой метод проверки УСП основан на составлении матрицы коэффициентов (А-матрица).

Решение матрицы подтверждает предыдущее решение: условие сохранения потока соблюдается в 1—4 узлах, за исключением 5-го узла, т. к. по дугам 6, 7 и 8, связанным с узлом 5, УСП не соблюдается.

Приведем векторную запись условия сохранения потока. Вектор потоков f записывается в следующем виде:

Вектор-столбец фиксированного внешнего потока:

Векторная запись условия сохранения потока:

Объединим алгоритм введения свободного узла и условия сохранения потока. Исходная сеть приведена на рис. 8.2.

Рассмотрим узлы: в узлах 1, 3 свободный внешний поток bsi 0, bs1 = 2, bs3 = 1, т. е. узлы 1, 3 не свободны. Введем свободный узел (рис. 8.3). В свободном узле должно соблюдаться УСП. При этом направления дуг 6 и 7, связывающих свободный узел 5 с узлами 1 и 3 исходной сети, определяются вышеизложенными в главе 7 правилами.

Поскольку bs1 > 0 и bs3 > 0, то дуги 6 и 7 входят в узлы 1 и 3.

Затем произведем передачу значений свободных потоков узлов 1 и 3 в пропускную способность свободных дуг. Значение свободного потока узла 1 переходит в пропускную способность дуги 7:

Значение свободного потока узла 3 переходит в пропускную способность дуги 6:

Стоимость передачи единицы потока из узла 1 переходит в стоимость дуги 7:

Стоимость передачи единицы потока из узла 3 переходит в стоимость дуги 6:

Убираем из параметров узлов 1 и 3 bsi и hsi как переданные свободным дугам. После данных преобразований сеть представлена на рис. 8.4.

Запишем УСП для преобразованной сети. Так как в узле 5 не показан внешний поток, то строки уравнений по нему нет, а элементы и связи по нему включаются в соответствующие строки узлов 1 и 3.

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

Запишем УСП с помощью матрицы коэффициентов, подтвердив при этом, что дуги 6 и 7 являются свободными, т. к. сумма коэффициентов по ним не равна нулю:

Коэффициенты всегда записываются в значении «1», при этом со знаком «+» для выходящих дуг и со знаком «–» для входящих дуг.

Суммарный коэффициент, отличный от нуля, свидетельствует о том, что условие сохранения потока не соблюдается по дуге 6 и дуге 7.

1. Сформулируйте условие сохранения потока.

2. Какие дуги называются свободными?

3. Какие дуги называются несвободными?

4. На чем основан метод проверки УСП?

5. В какой форме записывается система ограничений условий сохранения потока в узлах?

6. В значение какого параметра дуги переходит значение свободного потока при введении свободного узла?

8. В значение какого параметра дуги переходит значение стоимости передачи единицы потока из узла при введении свободного узла?

АЛГЕБРАИЧЕСКАЯ МОДЕЛЬ СЕТИ

Алгебраическая модель сети представляет собой комбинацию следующих составляющих:

1) компонентов (узлы i = 1, n ; дуги k = 1, m );

2) переменных (fk — потоки по дугам и i — потенциал узлов);

3) параметров (нижняя граница ck ; пропускная способность сk;

стоимость передачи единицы потока по дуге hk);

4) функциональных зависимостей (линейные и нелинейные);

5) целевых функций;

6) ограничений (условие сохранения потока; ограничения по пропускной способности).

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

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

2) при ограниченной пропускной способности дуг:

3) при условии неотрицательности дуговых потоков:

где i — номер начального узла дуги ij; j — номер конечного узла дуги ij;

fij — поток по дуге ij; hij — стоимость передачи единицы потока по дуге ij;

bi — фиксированный внешний поток в узле i; n — число узлов сети; m — число дуг.

Задачу линейного программирования можно записать в матричных обозначениях: найти минимальное значение Н = hf, где h — вектор стоимостей; f — вектор дуговых потоков.

Векторная запись условия сохранения потока:

где А — матрица коэффициентов; b — вектор фиксированных потоков, при этом f с; f 0.

Разделим матрицу А на две — В и R: А = [В, R].

Матрица В называется базисной и сформирована из (n – 1) линейно-независимых столбцов матрицы А. Переменные, соответствующие столбцам матрицы В, называются базисными переменными.

Матрица R соответствует небазисным переменным, fВ — вектор базисных переменных, fR — набор небазисных переменных:

B–1 — это матрица, обратная матрице B, т. е. В · B–1 = Е (единичная матрица).

Чтобы определить базисное решение fВ, каждую небазисную переменную полагают равной нулю или сk (0, сk). Поскольку ранг матрицы А r = n – 1, то fВ — единственное решение и, по крайней мере, одно оптимальное решение задачи линейного программирования является базисным, его необходимо найти.

Прямой задаче линейного программирования соответствует двойственная задача, которая формулируется следующим образом. Найти при ограничениях i – j + k –hk, k = 1, m.

Условия оптимальности решения выполняются при следующих допущениях.

1. Решение прямой задачи допустимо, если:

а) условие сохранения потока выполняется в каждом узле;

2. Приведенное двойственное решение допустимо при k = max [0, –k], где k = i – j + hk.

3. Выполняются условия, дополняющие жесткости:

1. Какие составляющие включает алгебраическая модель сети?

2. В виде нахождения минимума какой целевой функции для прямой задачи линейного программирования отражается алгебраическая модель сети?

3. В виде нахождения минимума какой целевой функции для двойственной задачи линейного программирования отражается алгебраическая модель сети?

4. Какая матрица называется базисной?

5. Какая матрица называется небазисной?

6. Каковы условия, дополняющие жесткости решения двойственной задачи?

7. Привести условия допустимости прямой и двойственной задачи.

ОСНОВНЫЕ ПОНЯТИЯ ИЗ ТЕОРИИ ГРАФОВ

Основоположником теории графов явился Леонард Эйлер, который в 1736 г. решал задачу Кенигсбергских мостов с помощью графов. Исходные понятия сетевого моделирования связаны с ориентированными и неориентированными графами. Граф — это объединение множеств вершин (узлов) N и ребер Х: пара множеств G = [N, Х], где каждое ребро соединяет две вершины.

Ориентированный граф G = [N, M] определяется как пара (N, M), где N — конечное множество вершин, а M — множество дуг, представляющих собой упорядоченные ребра (бинарное отношение на N, т. е.

подмножество множества NхN). Ориентированный граф для краткости называют орграфом.

Множество N называют множеством вершин графа. Вершина графа, не имеющая ни одного прообраза, называется истоком (источником). Вершина, не имеющая ни одного образа, называется стоком.

Множество M называют множеством ребер графа. На рис. 10.1а показан ориентированный граф с множеством вершин (1, 2, 3, 4). Вершины изображены кружками, а ребра в ориентированном графе — стрелками. Граф может содержать ребра-петли, соединяющие вершину саму с собой.

В неориентированном графе G = (N, M) множество ребер M состоит из неупорядоченных пар вершин. Парами являются множества {n, m}, где n, m N и m М, а n m. Неориентированное ребро обозначается как (n, m); при этом для неориентированного графа (n, m) и (m, n) обозначают одно и то же ребро. Неориентированный граф не может содержать ребер-петель, и каждое ребро состоит из двух различных вершин («соединяя» их). На рис. 10.1б изображен неориентированный граф с множеством вершин (1, 2, 3, 4).

Рисунок 10.1 — Ориентированный (а) и неориентированный (б) графы Многие понятия параллельно определяются для ориентированных и неориентированных графов (с соответствующими изменениями). Про ребро (n, m) ориентированного графа говорят, что оно выходит из вершины u и входит в вершину v. Например, на рис. 10.1а имеются три ребра, выходящие из вершины 2 (ребра (2, 2), (2, 3) и (2, 4)), и два ребра, в нее входящих (ребра (1, 2) и (2, 2)). Про ребро (n, m) неориентированного графа говорят, что оно инцидентно вершинам n и m. Например, на рис. 10.1б есть три ребра, инцидентные вершине 2: ребра (1, 2), (2, 3), (2, 4).

Если в графе G имеется ребро (n, m), говорят, что вершина n смежна с вершиной m. Для неориентированных графов отношение смежности является симметричным, но для ориентированных графов это не обязательно. Если вершина n смежна с вершиной m в ориентированном графе, то пишут m n. На обоих рисунках (рис. 10.1) вершина 2 является смежной с вершиной 1, но лишь во втором из них на (рис. 10.1б) вершина 1 смежна с вершиной 2 (в первом случае ребро (2, 1) отсутствует в графе).

Степенью вершины в неориентированном графе называется число инцидентных ей ребер. Например, для графа на рис. 10.1б степень вершины 2 равна 3. Для ориентированного графа различают исходящую степень, определяемую как число выходящих из нее ребер, и входящую степень, определяемую как число входящих в нее ребер. Сумма исходящей и входящей степеней называется степенью вершины. Например, вершина 2 в графе на рис. 10.1б имеет входящую степень 2, исходящую степень 3 и, следовательно, степень вершины 5.

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

Замкнутый маршрут называется циклом, если в нем все вершины, кроме начальной, различны, т. е. начальная вершина является конечной и совпадает сама с собой (рис. 10.2). Длина маршрута равна числу ребер в нем. Маршрут можно задать либо в виде списка вершин 1—2—5— 2—3, либо в виде списка ребер 1, 5, 5, 4.

Маршрут замкнутый: 1—2—4—5—2—1 (1, 6, 8, 5, 1).

Цепь: 1—2—5—4—2—3.

Путь: 1—2—4—5—3.

Цикл: 1—2—4—1.

Циклом в ориентированном графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Цикл называется простым, если в нем нет одинаковых вершин (кроме первой и последней), т. е. если все вершины различны. Ребро-петля является циклом длины 1. На рис. 10.1а ни один из путей циклов не образует. Ориентированный граф, не содержащий реберпетель, называется простым.

В неориентированном графе путь называется простым циклом, если в нем при числе вершин 3 все вершины различны. Например, нарис. 10.1б имеется простой цикл (1, 2, 3, 1).

Граф, в котором нет циклов, называется ациклическим.

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

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

Иерархическая структура в графе называется деревом. Дерево — это связный ациклический граф. Множество деревьев называется лесом.

Характерные особенности деревьев:

1) Число дуг в дереве на единицу меньше числа узлов.

2) В ориентированном связывающем дереве в каждый узел входит одна дуга, за исключением корневого узла.

3) Из каждого узла может выходить любое количество дуг.

4) Любые две вершины в дереве связаны единственным путем.

Как Эйлер решил задачу Кенигсбергских мостов? Он ввел понятие степени вершины. Число ребер, выходящих из вершины i, называют положительной степенью вершины (+i ), а число входящих ребер — отрицательной степенью вершины (i ).

Таким образом, степень вершины i равна Для ориентированного графа сумма положительных вершин равна сумме отрицательных степеней:

а для неориентированного графа:

где m — количество вершин.

Эйлер доказал, что поскольку все вершины имеют нечетную степень, то задача Кенигсбергских мостов (граф) неразрешима:

Например, нельзя нарисовать, не отрывая карандаша от бумаги, квадрат с двумя диагоналями, а если «открыть конвертик» (добавить ребра), то задача решается.

2. Каково определение ориентированного графа?

3. Каково определение неориентированного графа?

4. Что представляет для ориентированного графа исходящую степень?

5. Что представляет для ориентированного графа входящую степень?

6. Что такое маршрут в графе?

7. Что такое путь в графе?

СТАНДАРТНАЯ ЗАДАЧА

О ПОТОКЕ МИНИМАЛЬНОЙ СТОИМОСТИ

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

Стандартная задача о потоке минимальной стоимости (СЗПМС) в сети является одной из основных потоковых задач и формулируется следующим образом. Задана ориентированная сеть D = [N, M], где N — множество вершин, M — множество дуг, по которым могут протекать потоки fij продукта одного вида. В прямой задаче линейного программирования (ЗЛП) для решения СЗПМС требуется найти минимум целевой функции 1) при ограничениях условия сохранения потока по дугам сети:

2) при ограничениях пропускной способности дуг:

3) при условии неотрицательности дуговых потоков:

где n — число узлов сети; i — номер начального узла дуги ij; j — номер конечного узла дуги ij; — номер узла, предшествующего узлу i; hij — стоимость передачи единицы потока по дуге ij; fi — поток, входящий в узел i по дуге i; bi — фиксированный внешний поток в узле i.

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

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

Существует двойственная задача линейного программирования для решения СЗПМС, которая формулируется следующим образом: найти минимум целевой функции при ограничениях i – j + k –hk, k = 1, m; i — не ограничены, i = 1, n 1; k 0, где n — число узлов; m — число дуг; i — потенциал узла i;

j — потенциал узла j; ck — пропускная способность дуги k; k — переменная-индикатор, показывающая на принадлежность дуги к минимальному разрезу при максимальном потоке в сети.

Математические модели позвоbi] пользователю.

H = 2f1 + 20f2 + 1f3 + 12f4 + 2f5 min.

Ограничения записываются следующим образом:

Полученные значения «0» учитывают условие сохранения потока.

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

Двойственная задача СЗПМС формулируется в виде целевой функции:

Далее записываются ограничения по дугам:

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

k 0; i — не ограничены.

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

Рассмотрим решение, обработав математическую модель в MS Excel.

Алгоритм ввода данных сети в электронную таблицу:

1. Номера дуг сети читаем как вертикальные порядковые (слева).

2. Начальные узлы заводятся последовательно в столбец «А». Начальным считается узел данной дуги, из которого выходит дуга.

3. Конечные узлы заводятся последовательно в столбец «B». Конечным считается узел данной дуги, в который входит дуга.

4. Параметры пропускной способности дуг (ck) заносятся в столбец «С».

5. Стоимость передачи единицы потока по дугам (hk) заносятся в столбец «D».

6. Для решения (определения потоков по дугам) резервируются ячейки в столбце «F» (в данной сети с 1-й по 5-ю). Зарезервированным ячейкам дается заливка (например, голубого цвета). Устанавливается формат ячеек: числовые; один знак после запятой (для данной сети, т. к.

имеется значение 1,5).

7. Целевая ячейка устанавливается в столбце «F» сразу же после зарезервированных ячеек (в данной сети целевой ячейкой будет F6 — в данной ячейке задается формула целевой функции: СУММПРОИЗВ (F1:F5;D1;D5)).

8. В столбце «I» заводятся номера узлов (в данной сети с 1 по 4).

9. В столбце «J» записывается сумма потоков: в данной сети из 1-го узла выходят дуга 1 и дуга 2, поэтому заводится запись =+F1+F2; во второй узел входит дуга 1 и выходят дуги 3 и 4, поэтому заводится запись =–F1+F3+F4; по 3-му узлу записывается =–F2–F3+F5; по 4-му узлу записывается =–F4–F5.

10. В столбце «K» заносятся значения фиксированного внешнего потока (bi): по 1-му узлу «2», по 2-му и 3-му «0», по 4-му узлу «–2».

11. Из меню «Сервис» выбираем «Поиск решения». В открывшемся окне выполнить следующие действия:

– в строке «Установить целевую ячейку» ввести F6;

– в строке «Равной» поставить маркер «минимальному значению»;

– в строке «Изменяя ячейки» ввести F1:F5;

– в строке «Ограничения» ввести следующее:

- F1:F50, т. е. неотрицательность потока;

- F1:F5С1:С5, т. е. ограниченность;

- J1:J4=K1:K4, т. е. сохраняемость;

– далее необходимо курсором отметить команду «Выполнить».

12. В столбце «F» дается готовое решение, по каким дугам оптимальна передача потока и количество передаваемых единиц потока.

В данной сети по дуге 1—4 передается 1 ед. потока; по дугам 1—3— передается 1 ед. потока.

13. В целевой ячейке (F6) в результате решения указано значение стоимости передачи оптимального потока: в данной сети минимальная стоимость передачи 2 ед. потока составит 19 стоимостных единиц.

Стоимостные единицы могут быть как денежными, так и временными.

В этом проявляются возможности решения двух необходимых для оптимизации параметров.

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

Интерфейс решения стандартной задачи о потоке минимальной стоимости описан в методическом пособии «Решение потоковых задач в MS Excel» [2, с. 24—27].

1. Как формулируется прямая задача СЗПМС?

2. Как формулируется двойственная задача СЗПМС?

3. Каково назначение целевой ячейки в решении СЗПМС в MS Excel?

4. Какая функция отражается в целевой ячейке решения СЗПМС в MS Excel?

5. Какие ограничения необходимо ввести для дуговых потоков в СЗПМС?

6. Какие правила установки знаков потоков?

7. Приведите примеры применения СЗПМС в отраслях промышленности.

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ

Задача о кратчайшем пути (ЗКП) решается как на графе, так и в сети. В задаче о кратчайшем пути выделяются два узла, один из которых называют источником, другой стоком. Стоимость дуги обычно трактуют как длину дуги (отсюда и название задачи).

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

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

Пусть сеть D = [N, M] — ориентированный граф, заданный на множестве узлов N, из которых s — исток, t — сток, и множестве дуг M.

В реальной жизни возникают ситуации, когда:

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

– некоторые дуги имеют отрицательную длину (где стоимость отрицательная, то по этой дуге получен доход), однако в сети нет циклов с отрицательной суммарной длиной;

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

Задача решается:

1) либо нахождением кратчайшего пути из источника в сток (s t);

2) либо нахождением кратчайшего пути из источника во все остальные узлы сети (s n – 1).

Прямая задача линейного программирования по ЗКП записывается обычным образом. Требуется найти минимум целевой функции:

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

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

Для истока ограничение будет выглядеть так:

Для стока ограничение будет выглядеть так:

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

Двойственная задача линейного программирования по ЗКП записывается обычным образом:

при ограничениях j – i hk;

s = 0, i — неограничены, i s.

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

Пусть сеть D = [N, M] — ориентированный граф, заданный на множестве узлов N, из которых s — исток, t — сток, и множестве дуг М. Требуется найти путь из s в t, имеющий наименьшую стоимость.

Для решения двойственной задачи о КП используется алгоритм Дийкстры (рассматривается в следующей главе).

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

Кратчайший путь на графе определяется по следующему алгоритму:

1. Вершина-источник s получает метку Ms = 0.

2. Все вершины, связанные с источником одним ребром, получают метку Mi = 1.

3. Проверяется, не достигнут ли узел-сток t (получает ли вершинасток метку Mt). Если сток не достигнут — Mi = Mi + 1, то повторяется шаг 2. Если сток достигнут — переход к шагу 4.

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

Предпримем попытку решения задачи о КП, перебирая все возможные варианты по исходной сети (рис. 12.1).

Рисунок 12.1 — Пример задачи о кратчайшем пути:

Узлы 2, 3, 4 не являются источником или стоком, поэтому для них внешний поток всегда равен 0.

Вариантов решений несколько:

– нахождение кратчайшего пути из источника в сток: s' t;

– нахождение кратчайшего пути из источника во все остальные узлы сети: s' (n – 1).

Проанализируем все возможные пути из источника в сток:

(1, 3), (3, 2), (2, 5) стоимость этого пути: 2 + 3 + 5 = 10.

(1, 3), (3, 4), (4, 5) стоимость этого пути: 2 + 1 + 4 = 7.

Из анализа сети следует, что минимальная стоимость равна 7:

(1, 3), (3, 2), (2, 5) стоимость этого пути: 2 + 3 + 5 = 10 > 7.

(1, 3), (3, 4), (4, 5) стоимость этого пути: 2 + 1 + 4 = 7.

Таким образом, кратчайший путь состоит из дуг (1, 3), (3, 4), (4, 5), т. к. стоимость этого пути 2 + 1 + 4 = 7. Однако только в простейшей сети с малым количеством узлов и дуг возможно такое примитивное решение. Рациональным оптимизационным инструментарием является решение потоковых задач линейного программирования.

Проведем интерпретацию прямой и двойственной задачи линейного программирования для решения ЗКП (рис. 12.2). Исходная сеть состоит из пяти узлов, т. е. n = 5. При решении прямой задачи по ЗКП требуется минимизировать общее расстояние, пройденное потоком величины (n – 1) единиц до всех узлов сети, причем в каждом из узлов требуется 1 ед. потока.

Записывается прямая задача линейного программирования для ЗКП следующим образом в виде уравнения при ограничениях (ранг матрицы 5):

при fk 0.

Записывается двойственная задача линейного программирования для ЗКП следующим образом при ограничениях:

Значения потенциалов 2, 3, 4, 5 не ограничены.

Правильное решение (рис.12.3) прямой и двойственной задачи проверяется одинаковыми значениями Н и Р (Н = Р).

Интерфейс решения задачи о кратчайшем пути описан в методическом пособии «Решение потоковых задач в MS Excel» [2, с. 13—19].

1. Приведите примеры использования задачи о КП в реальной жизни.

2. Какой параметр трактуется в задаче о КП в качестве кратчайшего пути?

3. Что является основным параметром в задаче о кратчайшем пути?

4. Применима ли в решении задачи о КП прямая задача линейного программирования?

5. Применима ли в решении задачи о КП двойственная задача линейного программирования?

ОПТИМИЗАЦИОННЫЙ АЛГОРИТМ ДИЙКСТРЫ

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

Решение двойственной задачи по алгоритму Дийкстры (рис. 13.1) проводится последовательно по циклам, называемым итерациями, до тех пор, пока все узлы сети будут включены в список начальных узлов (СНУ). Это будет условием окончания алгоритма. Число итераций не превышает количества узлов, уменьшенное на 1, т. е. n – 1. R обозначает неизвестное значение потенциалов узлов, пока не рассчитанных. Так как значение потенциала пока неизвестно, то оно стремится к бесконечности.

Проведем решение алгоритма Дийкстры для сети (рис. 13.2).

1. Потенциал истока всегда равен нулю i = 0, на рисунке около узла 1 указываем в квадратных скобках потенциал [0]. Около всех остальных узлов указываем неизвестное значение потенциала [R]. Формируем список начальных узлов в виде таблицы СНУ. Так как в исходной сети 5 узлов, то число итераций должно быть не более 4 ( n – 1 5 – 1 4). Заполнение второй строки в таблице, а именно выбор нового начального узла производится последовательно в процессе решения алгоритма Дийкстры:

2.1. Первая итерация включает пересчет потенциалов узлов, соседних с узлом-истоком 1:

поэтому на сети следует поменять потенциал узла 2 со значения [R] на [2];

поэтому на сети следует поменять потенциал узла 3 со значения [R] на [2];

поэтому на сети следует поменять потенциал узла 4 со значения [R] на [3].

Рисунок 13.2 — Исходная сеть для решения алгоритма Дийкстры 3.1. Так как не все узлы включены в СНУ, то выбираем следующий начальный узел для второй итерации. Для этого необходимо выписать все рассчитанные в первой итерации потенциалы узлов и сравнить их значения:

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

2.2. Вторая итерация включает пересчет потенциала узла 5, т. к. из узла 2 выходит только одна дуга, входящая в узел 5:

поэтому на сети следует поменять потенциал узла 5 со значения [R] на [7].

3.2. Не все узлы включены в СНУ, выбираем начальный узел для третьей итерации.

Выписываем все рассчитанные в первой итерации потенциалы узлов, не вошедших в СНУ. Из рассчитанных потенциалов узлов не вошли в СНУ узлы 3, 4, 5. Узел 5 является стоком и в СНУ не входит, т. к. количество начальных узлов n – 1 = 5 – 1 = 4:

т. к. 3 < 4, то выбираем в качестве начального узла 3 и заносим его в СНУ.

2.3. Третья итерация. Из узла 3 выходят две дуги, которые входят в узел 2 и 5. Но из них узел 2 уже вошел в СНУ, поэтому потенциал узла 2 не пересчитывается, а пересчитывается потенциал узла 5:

поэтому меняем потенциал узла 5 со значения [7] на [5].

3.3. Выбираем начальный узел для четвертой итерации. Поскольку остался не включенным в СНУ только один узел 4, то он включается начальным узлом для четвертой итерации.

2.4. Четвертая итерация. Из узла 4 выходят две дуги 7 и 8, но дуга 7 входит в узел 3, который уже вошел в СНУ, то для него потенциал не пересчитывается. Дуга 8 входит в узел 5, его потенциал пересчитываем:

Меняем потенциал узла 5 с [5] на [3].

3.4. Все узлы вошли в СНУ, решение алгоритма Дийкстры окончено.

Получили конечные значения потенциалов всех узлов сети (рис. 13.3).

Рисунок 13.3 — Исходная сеть с пересчитанными потенциалами узлов Построим дерево кратчайших путей (ДКП), оно наглядно продемонстрирует решение задачи нахождения кратчайшего пути, причем не только от источника в сток, но и от источника во все узлы сети (рис. 13.4). Таким образом, появится оптимальный маршрут транспортировки.

Построение ДКП производится по определенным правилам:

1. Вырисовываем все узлы сети и около каждого узла записываем конечные потенциалы.

2. В ДКП включаем дуги, начиная от стока. При этом дуга существует, если она обеспечивает совпадение окончательного значения потенциала предыдущего узла с учетом стоимости передачи единицы потока по дуге:

3. Все узлы в ДКП должны быть связаны с истоком.