Введение
В рамках этого исследования была поднята цель определения каждой из сетевых моделей, начиная с самых основных понятий, таких как определение того, каким будет узел, какие вершины используются в сетевой модели, дуги, которые могут быть стрелка или соединитель каждого узла в сети, а также соображения, которые необходимо принять, чтобы понять структуру сети, например, направления, по которым проходят дуги, они могут быть прямыми или косвенными.
После того, как терминология частей, составляющих сети, понятна, мы продолжим с каждой из моделей, первой может быть матрица инцидентности узел-дуга, которая будет таблицей, представляющей модель в сети, метод дерева минимального расширения, шаги, которые необходимо выполнить для его выполнения, метод максимального потока, технические шаги, метод кратчайшего маршрута и другие модели сети, которые могут быть, проблемы транспортировки, проблемы кратчайшего пути, критический путь в планировании сетевого проекта, проблема потока с наименьшими затратами, анализ чувствительности для сетевых моделей, проблема перемещения поставщика, а также с использованием некоторых примеров, чтобы проблемы могли быть более ясными.
Все эти темы объясняются более подробно и для лучшего понимания в документе.
Сетевые модели
Сетевая модель - это модель перевалки с пропускной способностью, которая может принимать различные формы, такие как модель кратчайшего маршрута и модель максимального и минимального потока, задача дерева минимального досягаемости, метод критического пути и т. Д. другие приложения финансового и производственного планирования.
Основная характеристика модели перевалки с мощностями заключается в том, что это сеть, в которой предложения находятся в конкретных точках отправления, потребности в конкретных точках назначения и альтернативы доставки предлагаются через промежуточные узлы, поэтому которые следуют по маршрутам с определенными возможностями от исходной точки до пункта назначения.
Сетевая терминология
Сеть состоит из набора узлов, соединенных дугами (или ветвями). Обозначение для описания сети - (N, A), где N - это набор узлов, а A - набор дуг.
N = {1, 2, 3, 4, 5}
А = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5) }
Ниже представлена схема сети и ее основных компонентов.
Технологические модели сети
Что такое узел?
Обычно его называют вершиной или точкой. Обычно его изображают кружком. В транспортных сетях это должны быть города на карте.
Что такое арка?
Обычно ее называют рамкой или стрелкой. Это могло быть прямым или косвенным. Голова - это пункт назначения, а хвост - начало. Голова и хвост - это узлы, которые могут быть как в начале, так и в конце. В транспортных сетях дуги могут быть дорогами, навигационными каналами в реке или схемами полета самолета. Дуги обеспечивают связь между узлами. Улица с односторонним движением может быть представлена дугой, а улица с двусторонним движением может быть представлена дугой без направления или двумя дугами, указывающими в противоположных направлениях. В сети с n узлами может быть столько дуг, сколько n! / = п (п-1) / 2. При нацеливании это число может удвоиться.Это огромное количество возможных дуг - одна из причин, по которой существуют специальные алгоритмы решения конкретных сетевых проблем.
В сетевом узле вы обычно найдете число с положительным или отрицательным знаком, которое обозначает предложение (+) и спрос или требования (-) узла.
Путь - это набор дуг, которые соединяют два разных узла и проходят через другие узлы в сети. Например, на рисунке 1 дуги (1,2), (2,3), (3,4) и (4,5) образуют путь между узлами 1 и 5. Путь образует цикл или цикл, если вы соединяете узел с собой через другие узлы. На рисунке 6.1 дуги (2,3), (3,4) и (4,2) образуют цикл.
Важные соображения:
- Односторонние стрелки / линии являются прямыми дугами. Линии с потоком в обоих направлениях являются косвенными дугами. Сеть, в которой есть только прямые дуги, является прямой сетью. Сеть, имеющая дуги в обоих направлениях, является косвенной сетью. Прямой путь от узла i до j - это последовательность соединенных дуг, поэтому поток, который проходит через этот путь, возможен Непрямый путь от узла i к j - это последовательность соединенных дуг, направление которых равно i, и наоборот. Путь, который начинается и заканчивается в одном и том же узле, является петлей.Если сеть содержит хотя бы один прямой путь между двумя узлами, они называются связанными. Чтобы определить, какой из сетевых маршрутов будет выбран, мы должны учитывать стоимость и пропускную способность по маршруту маршрутов.
Сетевые модели, версия 1
Узел - матрица инцидентности дуги
Это таблица для представления данных ограничений сетевой модели. Каждая дуга сети соответствует столбцу таблицы. Каждому узлу в сети соответствует строка в таблице. В столбцах есть только две ненулевые записи: +1 и -1.
Технологические модели сети
После того, как мы подняли модель линейного программирования, мы должны найти решение этого линейного программирования, мы должны найти решение, которое оптимизирует целевую функцию.
- Мы можем использовать некоторые программы линейного программирования, такие как SOLVER или LINDO, чтобы найти оптимальное решение.
закрытие
- Терминология и процедура построения сети помогут вам применить модели оптимизации, поскольку, глядя на иллюстрацию 3, намного легче определить кратчайший или самый длинный путь и т. Д.
Версия сетевой модели 2
Метод минимального остовного дерева
Это дерево связывает узлы сети, используя минимальную общую длину соединяющих ветвей. Обычное применение происходит при мощении дорог, которые соединяют города или напрямую, или которые проходят через другие города. Решение с минимальным остовным деревом обеспечивает проектирование системы шоссе.
Шаги Минимальный метод связующего дерева
- Выберите любой узел в сети. Подключите этот узел к ближайшему узлу, чтобы минимизировать общее расстояние. Учитывая все узлы, которые теперь подключены, найдите и подключите ближайший узел, который не подключен. Если есть связь для ближайшего узла, выберите произвольно. Связь предполагает, что может быть более одного оптимального решения. Повторяйте третий шаг, пока не будут подключены все узлы.
пример
Рокси Ламот, владеющая большой коневодческой фермой недалеко от Орландо, планирует установить систему водоснабжения, которая соединит все конюшни и сараи. Расположение объектов и расстояния между ними показаны на следующем рисунке. Рокси должна определить самый дешевый способ подачи воды в каждый объект.
Технологические модели сети
Техника пикового потока
- Метод пикового потока определяет максимальный поток, который может проходить через сеть.
4 шага техники пикового потока
- Выберите любой путь от начала (исходный) до конца (назначения) с некоторым потоком. Если нет пути потока, то оптимальное решение было достигнуто. Найдите дугу пути с наименьшей доступной пропускной способностью. Назовите эту пропускную способность C. Это представляет собой максимальную дополнительную пропускную способность, которая может быть выделена для этого пути. Для каждого узла на этом пути уменьшите пропускную способность в направлении потока на величину C. Для каждого узла на этом пути увеличьте пропускную способность. поток в обратном направлении на величину C.
Повторяйте эти шаги до тех пор, пока больше не станет возможным увеличивать поток.
пример
PetroChem, нефтеперерабатывающий завод, расположенный на реке Миссисипи к югу от Батон-Руж, штат Луизиана, проектирует новый завод по производству дизельного топлива. На рисунке 5 показана сеть основных центров обработки вместе с существующим расходом. Руководство хотело бы определить максимальное количество топлива, которое может течь через установку от узла 1 до узла 7.
Технологические модели сети
Техника кратчайшего пути
Эта проблема определяет кратчайший маршрут между источником и пунктом назначения в транспортной сети.
Шаги техники кратчайшего пути
- Найдите узел, ближайший к началу координат. Поместите расстояние в поле рядом с узлом. Найдите следующий ближайший узел к источнику (растению) и укажите расстояние в поле рядом с узлом. В некоторых случаях необходимо будет просмотреть несколько путей, чтобы найти ближайший узел - повторяйте процесс, пока не пройдете всю сеть. Последнее расстояние в конечном узле будет расстоянием кратчайшего пути. Обратите внимание, что расстояние, указанное в поле рядом с каждым узлом, является кратчайшим путем к этому узлу. Эти расстояния используются в качестве промежуточных результатов для поиска следующего ближайшего узла.
Пример:
RentCar разрабатывает политику замены своего парка автомобилей на 4-летний горизонт планирования. В начале каждого года автомобиль заменяют или оставляют в эксплуатации еще на один год. Автомобиль должен находиться в эксплуатации от 1 до 3 лет. В следующей таблице представлена стоимость замены в зависимости от года приобретения автомобиля и количества лет эксплуатации.
Технологические модели сети
Задачу можно сформулировать как сеть, в которой узлы с 1 по 5 представляют начало лет с 1 по 5. Дуги от узла 1 (год 1) могут достигать узлов 2, 3 и 4, потому что автомобиль может быть в эксплуатации от 1 до 3 лет. Таким же образом можно интерпретировать дуги от других узлов. Длина каждой арки равна стоимости замены. Решение проблемы эквивалентно определению кратчайшего пути между узлами 1 и 5.
На рисунке 6 показана получившаяся сеть. Используя TORA, 2 кратчайший путь - 1 S3 S5.
Решение указывает, что автомобиль, купленный в начале года 1 (узел 1), необходимо заменить через 2 года в начале года 3 (узел 3). Автомобиль на замену будет оставаться в эксплуатации до конца года 4. Общая стоимость этой политики замены составляет 12 500 долларов США.
(= 5400 долларов США + 7100 долларов США).
Технологические модели сети
Сетевая модель версии 3
Типы сетевых моделей
Семейство задач оптимизации сети включает следующие прототипы моделей: задачи назначения, критический путь, максимальный поток, кратчайший путь, транспорт и минимальная стоимость потоков. Проблемы легко устанавливаются за счет использования сетевых дуг и узлов.
Проблемы с транспортировкой
Транспортные модели играют важную роль в управлении логистикой и в цепочке поставок для снижения затрат и улучшения услуг. Поэтому цель - найти наиболее экономичный способ перевозки грузов. Дистрибьютор, у которого есть «m» складов с поставкой продукции в них, должен отправлять упомянутые продукты в географически удаленные торговые центры, каждый из которых имеет определенный потребительский спрос, например, который должен быть удовлетворен. Цель состоит в том, чтобы определить минимально возможную стоимость перевозки с учетом затрат на транспортировку между i-м складом и j-м торговым центром, то есть Cij.
Проблемы кратчайшего пути
Проблема состоит в том, чтобы определить лучший способ пересечь сеть, чтобы найти самый дешевый путь из одного источника в заданный пункт назначения. Предположим, что в данной сети есть m узлов и n дуг (ребер) и стоимость Cij, связанная с каждой дугой (iaj) в сети. Формально задача кратчайшего пути (CC) состоит в том, чтобы найти самый короткий путь (наименьшую стоимость) от начального узла 1 до конечного узла m. Стоимость дороги - это сумма затрат на каждую пройденную дугу. Определите двоичные переменные Xij, где Xij = 1, если дуга (iaj) находится на CC, и Xij = 0 в противном случае. Есть два специальных узла, называемых источником и местом назначения. Цель состоит в том, чтобы найти кратчайший путь от пункта отправления до пункта назначения.
Критический путь в планировании сетевого проекта
Успешное управление амбициозным проектом, будь то строительство, транспорт или финансы, зависит от тщательной координации и планирования различных задач. Метод критического пути (или пути) (CCM) пытается проанализировать планирование проекта. Это позволяет лучше контролировать и оценивать проект. Например, мы хотим знать, как долго продлится проект? Когда конкретная задача будет готова к запуску? Если задача не выполнена вовремя, Будет ли отложена остальная часть проекта?
Какие задачи необходимо ускорить (эффективно), чтобы проект закончился раньше?
Задача минимальной стоимости потока
Все вышеперечисленные сетевые проблемы являются частными случаями проблемы потоков с минимальной стоимостью. Как и проблема пикового потока, он рассматривает потоки в сетях с возможностями. Как и в случае задачи о кратчайшем пути, здесь учитывается стоимость потока в дугу. Как и в случае с транспортной проблемой, она допускает несколько пунктов отправления и назначения. Следовательно, все эти проблемы можно рассматривать как частные случаи задачи минимальной стоимости потока. Проблема состоит в том, чтобы минимизировать общую стоимость в зависимости от доступности и спроса некоторых узлов, а также верхнего соединения потока через каждую дугу.
Анализ чувствительности для сетевых моделей
Семейство классических задач оптимизации сети включает следующие прототипы моделей: выделение, критический путь, максимальный поток, кратчайший путь и транспорт. Хотя хорошо известно, что проблемы такого типа можно моделировать как линейное программирование, они обычно никогда не выполняются. Из-за неэффективности и относительной сложности симплекс-метода (прямого, двойного и других вариантов) для сетевых моделей эта проблема решается одним из более чем 400 специальных алгоритмов. Это приводит к множеству трудностей. Решения алгоритмов не унифицированы, и каждый алгоритм использует свою стратегию для исследования особой структуры конкретной проблемы. Кроме того, небольшие изменения в проблеме, такие как добавление отдельного ограничения или нескольких индексов,разрушает специальную структуру и заставляет алгоритм перезапускаться. Более того, эти алгоритмы позволяют получать эффективные решения за счет управленческой хитрости, поскольку они являются окончательным решением этих алгоритмов, не имеющих достаточной информации для проведения анализа чувствительности.
Проблема с поездкой продавца
Торговец должен посетить города 1, 2,.. N, и его путешествие начинается и заканчивается в Родном городе. Пусть Cij будет стоимостью проезда по городу и указанному городу j. Задача состоит в том, чтобы определить оптимальный порядок проезда по городам с минимальными затратами. Максимизация потоков - типичная проблема в исследовании операций, у которого есть много приложений, например, дорожный поток в городе, канализационная сеть, компьютерная сеть и т. Д.
вывод
В заключение мы можем сказать, что дуги являются соединителями узлов в каждой сети, эти модели могут иметь прямой или косвенный адрес, что в каждой сети может быть несколько соединителей, которые служат для соединения нескольких узлов и, таким образом, создания маршрутов внутри каждого. В сети есть циклы, которые соединяют узлы за пределами исходного пути.
Модели могут быть представлены сетевыми программами, модели второй версии, такие как метод минимального связующего дерева, используется для случаев, связанных с короткими расстояниями или небольшими маршрутами, метод максимального потока определяет, какой максимальный поток может протекать В сети метод кратчайшего пути помогает нам определить кратчайший путь от нашего исходного узла и нашего транспортного пути.
Сетевые модели обычно используются в определенных рабочих аспектах, и благодаря им мы можем решать проблемы, и их можно разрабатывать в различных областях, облегчая маршруты, которые им лучше всего подходят.
Надеюсь, эта статья будет очень полезной и что содержащиеся в ней концепции четко объяснены.
Ссылки
- Хиллер, Ф., Либерман, Г. (2006). Введение в исследование операций. (8-е изд.) Мексика. Макгроу Хилл. ISBN 970-10-5621-3Oc, F, (2010), Модели сетей - Исследование операций, получено с http://www.slideshare.net/FreddOc/modelos-de-redes-investigacin-de-operacionesTaha, HA (2012), Исследование операций, (9-е изд.), Мексика, Pearson Education. ISBN: 978-607-32-0796-6 Раффо, Э. (1990), Исследование операций, Лима, Раффо Лекка Editores, код библиотеки: 658.4034 / T16
