Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Поток с потерями минимальной стоимости

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

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

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

В любом случае будем считать, что если в связь (х, у) в узле х входит f(x, у) единиц потока, то из этой связи в узле у выйдет к(х, у) /(х, у) единиц потока, т.е. каждая единица потока, проходящая по связи (х, у), умножается на к(х, у). Если к(х, у) > 1, то поток по связи увеличивается (усиливается) и данную величину называют коэффициентом усиления. Если к(х, у) < 1, то поток по связи уменьшается или ослабляется (теряется), и данную величину называют коэффициентом ослабления {потерь).

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

для всех (х, у).

Сформулируем задачу о потоке минимальной стоимости.

Найти

при условии

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

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

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

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>