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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 15: Строка 15:
  
 
== Задача о назначениях ==
 
== Задача о назначениях ==
[[Файл:Assignment.jpg|thumb|left|Задача о назначениях]]
+
[[Файл:Assignment.jpg|thumb|right|Задача о назначениях]]
 
Условие:
 
Условие:
 
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
 
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.

Версия 08:03, 27 декабря 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 (рус.)

Ссылки