419
правок
Изменения
→Задача о назначениях
== Задача о назначениях ==
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
Популярная задача, которая легко сводится к потоку минимальной стоимости - [[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|задача о назначениях]].
