Экономико-математические методы в логистике: теория графов

Экономико-математические методы в логистике К.Э.Н., ДОЦЕНТ БОРИСОВА ВИКТОРИЯ ВЛАДИМИРОВНА Т Е ОРИЯ Г РА Ф ОВ СЕТЕВЫЕ И ПОТОКОВЫ Е МОДЕЛИ Типовые постановки, которые моделируютс я сетевыми моделями Расположение населенных соединяющих их дорог пунктов и Любые трубопроводные системы , по которым прокачиваются потоки различной физической природы (нефть, газ, масло, вода и пр.) Транспортная сеть Потоковы е схемы Перемещаются по сети потоки различной физической природы ◦потоки машин на дорогах; ◦потоки сырья и полуфабрикатов в логистичеcкой системе; ◦Потоки нефти, газа в трубопроводах; ◦грузовые потоки; ◦потоки товаров в каналах распределения и др. Основны е определения сетевы х и потоковы х моделей  - узел  Ребро – неориентированная линия  Дуга - однонаправленная линия – из в  Ребро может быть представлено двумя дугами  Сеть – множество узлов и дуг, соединенных в определенном порядке Основны е определения сетевы х и потоковы х моделей  Путь - последовательность дуг, в котором начало каждой последующей дуги совпадает с концом предыдущей независимо от направления дуги  Контур – путь, у которого начальный и конечный узлы совпадают  Гамильтоновый путь – проходящий через все узлы только по одному разу  Гамильтоновый контур – гамильтоновый путь, у которого начальный и конечный узлы совпадают Основны е определения сетевы х и потоковы х моделей  Связный путь - любые два узла связаны путем  У дуги есть характеристика - вес дуги (расстояние между пунктами, пропускная способность дороги, время перемещения между пунктами, стоимость поставки грузов из одного пункта к другому и т.д.) Основны е определения сетевы х и потоковы х моделей  Потоком физической величины (сырье, товары, полуфабрикаты, деньги, информация) называется количество физической величины (объем, вес, число, ден.ед., единиц информации), протекающей через некоторую поверхность в течение определённого промежутка времени (сек, минуту, неделю и т.д.)  Размерность потока - {количество физической величины/ временной интервал} Основны е определения сетевы х и потоковы х моделей  Плотность потока – величина потока / площадь сечения, через который он проходит  Пропускная способность объекта – максимальный поток, который может быть пропущен через данный объект  Непрерывность потока – равенство суммарного потока, входящего в объект и суммарного потока, выходящего из объекта  Понятие потока предназначено для отражения перемещения физической величины в пространстве  Интенсивность потока – скорость изменения потока при неизменности пространственного положения ТИПОВЫ Е ЗАДАЧИ ( задача о максималь ном потоке в сети ) Поток произвольной физической природы втекает в сеть, проходит через промежуточные пункты сети и вытекает из нее. Каждая дуга сети характеризуется величиной пропускной способности, причем дуга может пропускать поток в одном или двух направлениях. Необходимо определить величину максимального потока, который может быть пропущен через данную сеть. потоке в сети: математическая формализация Целевая функция: F = {полный поток; исходящий из общего источника} либо Целевая функция: F = {полный поток; входящий в общий сток} потоке в сети: математическая формализация Первый вид ограничений. {Суммарный поток, исходящий из источника} = {Суммарный поток, входящий в сток} Второй вид ограничений. {Суммарный поток, входящий в узел } = {Суммарный поток, выходящий из узла } потоке в сети: математическая формализация Третий вид ограничений. Поток , протекающий по дуге не может превышать максимальной пропускной способности дуги , т.е. 0 ≤ { Поток в дуге } ≤ {Пропускная способность дуги } Задача о максимальном потоке в сети 4 2 4 4 6 7 6 5 1 2 2 8 6 3 9 5 7 8 1 1 7 4 ТИПОВЫ Е ЗАДАЧИ ( определен ие кратчайше го маршрута в сети ) Индивидууму необходимо доехать из одного города в другой по имеющейся сети автодорог, выбрав для этого кратчайший путь. маршруте в сети: математическая формализация Целевая функция: F = {Суммарная длина пути} - величина потока, протекающего по дуге в направлении из в Ограничения: {Суммарный поток, входящий в узел } = {Суммарный поток, выходящий из узла } Задача о кратчайшем пути в сети 1 1 2 1 5 8 1 6 1 2 4 1 3 3 3 7 5 5 7 6 6 8 1 6 8 1 5 9 1 2 9 ТИПОВЫ Е ЗАДАЧИ ( сетевой график ) Планирование работ и управление проектами, моделирование бизнеспроцессов, составление расписания и планирование работ. Задача нахож дения критического пути в сетевом графике •Вариант задачи максимального пути в сети. •База – сетевая модель (сетевой график) в виде логической и технологической последовательности работ. •Основные понятия сетевой модели: •Событие (узел) •Дуга (работа) •Путь. Основны е категория сетевого графика •Работа связывает два события •Каждая работа имеет продолжительность. •Работы бывают текущие и фиктивные (длительность =0) •События - результаты выполнения одной или нескольких работ. •Начальное событие – источник •Завершающее событие – сток •Понятие пути •Продолжительность пути •Максимальный по длительности путь = критический путь. Требование сетевой модели Нумерация сети (i < j) Отсутствие тупиковых событий (кроме стока) Отсутствие висячих вершин (кроме источника) Отсутствие циклов (замкнутых контуров) Введение фиктивных работ 1. Параллельные работы A В Б 2. Разные последующие работы для одной предшествующей A B Б A C Введение фиктивных работ 3. Дано: А, Б, В, Г, Д Условие: В начинается после А Г начинается после А и Б Д начинается после Б 4. Дано: А, Б, В, Г, Д, Е, Ж Условие: А, Б, В, Г начинаются одновременно Д начинается после А и Б Е начинается после Б и В Ж начинается после В и Г Числовы е характеристики сети Ранние сроки (раннее начало (РО) и раннее окончание (РО)) величина наиболее длительного отрезка пути от источника до рассматриваемого события Поздние сроки (позднее начало (ПО) и позднее окончание (ПО)) – самый поздний допустимый срок, в который может начаться и к которому должно совершится событие Длительност ь крит ического пут и – максимальная оценка пути от источника до стока Резерв - оценка предельно допустимого срока задержки наступления события без увеличения срока выполнения всего комплекса работ Виды резервов Полны й резерв (Rпо) – на сколько можно увеличить время выполнения конкретной работы при условии, что срок выполнения всего комплекса работ не изменится ◦Работы критического пути имеют Rпо=0. Част ны й резерв первого рода (r1) - оценка возможности переноса ПО на более ранние сроки без изменения окончания предшествующих работ Част ны й резерв второго рода (r2) - оценка возможности переноса РО на более поздние сроки без изменения ранних сроков начала следующих работ Свободны й резерв (Rсв) - дополнительное время (сверх продолжительности выполнения работы), которое находится в пределах ранних сроков начала непосредственно следующих и поздних сроков окончания непосредственно предшествующих работ Временны е параметры сети i-j Tij 1-2 7 2-3 1 3-8 4 1-4 8 4-6 8 4-7 9 6-7 5 7-8 3 1-5 4 5-8 12 2-4 5-6 РН РО ПН ПО r1 r2 Rпо Rсв