задачи выбора кратчайшего пути

Как и в примере 5.4, считаем, что каждой ориентированной дуге сети соответствует переменное модели х^, представляю]щее собой количество товара, которое должно быть отправлено с г-го склада на Для ка

Рассмотрим транспортную задачу с промежуточными пунктами, сеть которой представлена на рис. 5.3. При этом предположим, что: а) в узле с номером 1 имеется избыточ]ная единица товара; б) в узле с номером 8 имеется недостаток единицы товара; в) узлы с номерами 2-7 являются промежуточ]ными пунктами с нулевыми чистыми запасами (потребность в дополнительных поставках товара равна нулю см. пример 5.4). Необходимо разработать план перевозок товара между узлами сети (складами), который при минимальных транс]портных затратах позволит на каждом складе поддерживать нулевой чистый запас товара.

Предположим, что для сети, представленной на рис. 5.3, необходимо найти кратчайший путь от узла с номером 1 (ис]точник) до узла с номером 8 (сток). Установим связь этой задачи с классической транспортной задачей.

Существуют сети, содержащие циклы, каждый из которых представляет собой замкнутый путь (путь, исходящий из неко]торого узла сети и возвращающийся в него же). Так, в сети, представленной на рис. 5.3, много циклов, один из них содержит узлы с номерами 2, 3, 5, 6 и 7. Как правило, в задачах иссле]дования операций значения с,^ положительны и общая длина" цикла является положительной. Следовательно, решение зада]чи выбора кратчайшего пути не может содержать циклов.

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

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

Как правило, в сети выделяют один узел, который является конечным (пункт или станция назначения, сток). Задача заключается в отыскании кратчайшего пути в этот конечный узел (на рис. 5.3 конечным является узел с номером 8) из некоторого другого узла сети (например, из первого узла сети на рис. 5.3). Величина с,^ определяет расстояние от г-го узла сети до ее го узла.

Заданный 3-й узел. К этой задаче, известной в исследовании операций как задача выбора кратчайшего пути, сводятся такие практически важные задачи, как задача о замене обору]дования, задача о календарном планировании комплекса работ И т. д.

Пусть задана некоторая сеть (рис. 5.3), каждой ориентиро]ванной дуге которой соответствует определенное расстояние. Необходимо найти кратчайший путь из г-го узла сети в ее

Опубликовано в рубрике | Май 17th, 2012

Вы находитесь здесь: > > 5.4. Задача выбора кратчайшего пути

Свежие комментарииАрхивы

Финансы нужно уметь считать

5.4. Задача выбора кратчайшего пути » Экономическая математика