Поток минимальной стоимости — различия между версиями
Proshev (обсуждение | вклад) |
Proshev (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Определение задачи == | == Определение задачи == | ||
Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества [[Определение сети, потока|потока]] через заданную [[Определение сети, потока|сеть]]. | Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества [[Определение сети, потока|потока]] через заданную [[Определение сети, потока|сеть]]. | ||
| − | |||
{{Определение | {{Определение | ||
|definition=Дано число <tex>f_0</tex> и транспортная сеть <tex>\,G(V,E)</tex> с источником <tex>s \in V</tex> и стоком <tex>t \in V</tex>, где ребра <tex>(u,v) \in E</tex> имеют пропускную способность <tex>\,c(u,v)</tex> и цену <tex>\,p(u,v)</tex>. | |definition=Дано число <tex>f_0</tex> и транспортная сеть <tex>\,G(V,E)</tex> с источником <tex>s \in V</tex> и стоком <tex>t \in V</tex>, где ребра <tex>(u,v) \in E</tex> имеют пропускную способность <tex>\,c(u,v)</tex> и цену <tex>\,p(u,v)</tex>. | ||
| Строка 19: | Строка 18: | ||
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей. | * Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей. | ||
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость. | * Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость. | ||
| − | Решение данной задачи легко сводится к поиску потока минимальной стоимости | + | [[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|Решение]] данной задачи легко сводится к поиску потока минимальной стоимости. |
== Источник == | == Источник == | ||
Версия 07:51, 27 декабря 2011
Определение задачи
Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества потока через заданную сеть.
| Определение: |
| Дано число и транспортная сеть с источником и стоком , где ребра имеют пропускную способность и цену .
Суть задачи — найти поток f(u, v):
|
Алгоритмы решения
- Найти любой поток величины , после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом Форда - Беллмана.
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости.
- Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма).
Задача о назначениях
Условие:
- Дана квадратная матрица . Нужно выбрать в ней элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
- Имеется заказов и станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
Решение данной задачи легко сводится к поиску потока минимальной стоимости.
Источник
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
