Поток минимальной стоимости — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 20: Строка 20:
 
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
 
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
 
[[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|Решение]] данной задачи легко сводится к поиску потока минимальной стоимости.
 
[[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|Решение]] данной задачи легко сводится к поиску потока минимальной стоимости.
 
== Литература ==
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
  
 
== Ссылки ==
 
== Ссылки ==
Строка 29: Строка 26:
 
*[http://habrahabr.ru/blogs/algorithm/61884/ Хабрахабр - Максимальный поток минимальной стоимости]
 
*[http://habrahabr.ru/blogs/algorithm/61884/ Хабрахабр - Максимальный поток минимальной стоимости]
  
 +
== Литература ==
 +
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
  
 
[[Категория: Задача о потоке минимальной стоимости]]
 
[[Категория: Задача о потоке минимальной стоимости]]

Версия 23:26, 28 декабря 2011

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

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

Определение:
Дано число [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 (рус.)