Поток минимальной стоимости

Материал из Викиконспекты
Перейти к: навигация, поиск

Определение задачи

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


Определение:
Дано число [math]f_0[/math] и транспортная сеть [math]\,G(V,E)[/math] с источником [math]s \in V[/math] и стоком [math]t \in V[/math], где ребра [math](u,v) \in E[/math] имеют пропускную способность [math]\,c(u,v)[/math] и цену [math]\,p(u,v)[/math].

Суть задачи — найти поток f(u, v):

[math]p(f) = \sum_{u,v \in V} p(u,v) \cdot f(u,v) - min [/math].
[math]|f| = \sum_{u,v \in V} f(u,v) = f_0[/math]

Алгоритмы решения

Задача о назначениях

Условие:

  • Дана квадратная матрица [math]A_{N\times N}[/math]. Нужно выбрать в ней [math]N[/math] элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
  • Имеется [math]N[/math] заказов и [math]N[/math] станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.

Решение данной задачи легко сводится к поиску потока минимальной стоимости - задача о назначениях.

Источник

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

Ссылки