54
правки
Изменения
Новая страница: «== Постановка задачи == * Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> э…»
== Постановка задачи ==
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
== Сведение к задаче о потоке минимальной стоимости ==
Построим двудольный граф <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_{ij} = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому, это взаимно однозначное соответствие между вершинами первой доли и вершинами второй доли является решением задачи.
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
== Сведение к задаче о потоке минимальной стоимости ==
Построим двудольный граф <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_{ij} = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому, это взаимно однозначное соответствие между вершинами первой доли и вершинами второй доли является решением задачи.
