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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сведение к задаче о потоке минимальной стоимости)
Строка 4: Строка 4:
  
 
== Сведение к задаче о потоке минимальной стоимости ==
 
== Сведение к задаче о потоке минимальной стоимости ==
[[Файл:pic1.PNG|thumb|right|300px|Пример построенного графа для матрицы А]]
+
[[Файл:pic1.PNG|thumb|right|300px|Пример построенного графа для матрицы <tex>A = \begin{pmatrix}
 +
1 & 2 \\
 +
3 & 4 \end{pmatrix}</tex>]]
 
Построим ориентированный граф, состоящий из двух частей <tex>G</tex> следующим образом:
 
Построим ориентированный граф, состоящий из двух частей <tex>G</tex> следующим образом:
 
* Имеется исток <tex>S</tex> и сток <tex>T</tex>.
 
* Имеется исток <tex>S</tex> и сток <tex>T</tex>.

Версия 00:34, 5 июня 2012

Постановка задачи

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

Сведение к задаче о потоке минимальной стоимости

Пример построенного графа для матрицы [math]A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}[/math]

Построим ориентированный граф, состоящий из двух частей [math]G[/math] следующим образом:

  • Имеется исток [math]S[/math] и сток [math]T[/math].
  • В первой части находятся [math]N[/math] вершин, соответствующие строкам матрицы или заказам.
  • Во второй [math]N[/math] вершин, соответствующие столбцам матрицы или станкам.
  • Между каждой вершиной [math]i[/math] первой части и каждой вершиной [math]j[/math] второй части проведём ребро с пропускной способностью 1 и стоимостью [math]A_{ij}[/math].
  • От истока [math]S[/math] проведём рёбра ко всем вершинам [math]i[/math] первой части с пропускной способностью 1 и стоимостью 0.
  • От каждой вершины второй части [math]j[/math] к стоку [math]T[/math] проведём ребро с пропускной способностью 1 и стоимостью 0.

Найдём в полученном графе [math]G[/math] максимальный поток минимальной стоимости.
Понятно, что величина потока будет равна [math]N[/math]. Заметим, что для каждой вершины [math]i[/math] из первой части найдётся только одна вершина [math]j[/math] из второй части, такая, что поток [math]f(i, j) = 1[/math]. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому это взаимно однозначное соответствие между вершинами первой части и вершинами второй части является решением задачи.

Асимптотика

Асимптотика этого решения равна асимптотике алгоритма, выбранного для поиска потока.

Источники