Изменения
→Сведение к задаче о потоке минимальной стоимости
== Сведение к задаче о потоке минимальной стоимости ==
[[Файл:pic1.PNG|thumb|right|275x250px|Пример построенного графа для матрицы А]]
Построим двудольный ориентированный граф , состоящий из двух частей <tex>G</tex> следующим образом:
* Имеется исток <tex>S</tex> и сток <tex>T</tex>.
* В первой доле части находятся <tex>N</tex> вершин, соответствующие строкам матрицы или заказам.
* Во второй <tex>N</tex> вершин, соответствующие столбцам матрицы или станкам.
* Между каждой вершиной <tex>i</tex> первой доли части и каждой вершиной <tex>j</tex> второй доли части проведём ребро с пропускной способностью 1 и стоимостью <tex>A_{ij}</tex>.* От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой доли части с пропускной способностью 1 и стоимостью 0.* От каждой вершины второй доли части <tex>j</tex> к стоку <tex>T</tex> проведём ребро с пропускной способностью 1 и стоимостью 0.
Найдём в полученном графе <tex>G</tex> максимальный [[Поток минимальной стоимости|поток минимальной стоимости]]. <br />
Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой доли части найдётся только одна вершина <tex>j</tex> из второй доличасти, такая, что поток <tex>f(i, j) = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому это взаимно однозначное соответствие между вершинами первой доли части и вершинами второй доли части является решением задачи.
== Асимптотика ==
Асимптотика этого решения равна асимптотике алгоритма, выбранного для поиска потока.
