http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=SvyatoslavВикиконспекты - Вклад участника [ru]2026-05-04T11:39:11ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85_%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B5_%D0%BE_%D0%BF%D0%BE%D1%82%D0%BE%D0%BA%D0%B5_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%BE%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8&diff=17175Сведение задачи о назначениях к задаче о потоке минимальной стоимости2012-01-17T19:29:55Z<p>Svyatoslav: </p>
<hr />
<div>== Постановка задачи ==<br />
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.<br />
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.<br />
<br />
== Сведение к задаче о потоке минимальной стоимости ==<br />
[[Файл:pic1.PNG|thumb|right|275x250px|Пример построенного графа для матрицы А]]<br />
Построим двудольный граф <tex>G</tex> следующим образом:<br />
* Имеется исток <tex>S</tex> и сток <tex>T</tex>.<br />
* В первой доле находятся <tex>N</tex> вершин, соответствующие строкам матрицы или заказам. <br />
* Во второй <tex>N</tex> вершин, соответствующие столбцам матрицы или станкам.<br />
* Между каждой вершиной <tex>i</tex> первой доли и каждой вершиной <tex>j</tex> второй доли проведём ребро с пропускной способностью 1 и стоимостью <tex>A_{ij}</tex>.<br />
* От истока <tex>S</tex> проведём рёбра ко всем вершинам <tex>i</tex> первой доли с пропускной способностью 1 и стоимостью 0.<br />
* От каждой вершины второй доли <tex>j</tex> к стоку <tex>T</tex> проведём ребро с пропускной способностью 1 и стоимостью 0.<br />
<br />
Найдём в полученном графе <tex>G</tex> максимальный [[Поток минимальной стоимости|поток минимальной стоимости]]. <br /><br />
Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой доли найдётся только одна вершина <tex>j</tex> из второй доли, такая, что поток <tex>f(i, j) = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому это взаимно однозначное соответствие между вершинами первой доли и вершинами второй доли является решением задачи.<br />
== Асимптотика == <br />
Асимптотика этого решения равна асимптотике алгоритма, выбранного для поиска потока.<br />
<br />
== Источники ==<br />
[http://e-maxx.ru/algo/assignment_mincostflow Задача о назначениях. Решение с помощью min-cost-flow]<br />
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)<br />
<br />
[[Категория: Задача о потоке минимальной стоимости]]</div>Svyatoslavhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Pic1.PNG&diff=17174Файл:Pic1.PNG2012-01-17T19:29:20Z<p>Svyatoslav: Пример построенного графа для данной матрицы А</p>
<hr />
<div>Пример построенного графа для данной матрицы А</div>Svyatoslav