419
правок
Изменения
Нет описания правки
== Определение задачи ==
Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества [[Определение сети, потока|потока]] через заданную [[Определение сети, потока|сеть]].
{{Определение
|definition=Дано число <tex>f_0</tex> и транспортная сеть <tex>\,G(V,E)</tex> с источником <tex>s \in V</tex> и стоком <tex>t \in V</tex>, где ребра <tex>(u,v) \in E</tex> имеют пропускную способность <tex>\,c(u,v)</tex> и цену <tex>\,p(u,v)</tex>.
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
[[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|Решение ]] данной задачи легко сводится к поиску потока минимальной стоимости - [[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|задача о назначениях]].
== Источник ==
