Изменения

Перейти к: навигация, поиск

Поток минимальной стоимости

1383 байта убрано, 01:45, 30 декабря 2011
Нет описания правки
== Определение задачи ==
Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества [[Определение сети, потока|потока]] через заданную [[Определение сети, потока|сеть]]данной величины с наименьшей стоимостью.
{{Определение
|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>.
*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].
*[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости|Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма)]].
 
== Задача о назначениях ==
[[Файл:Assignment.jpg|thumb|right|Задача о назначениях]]
Условие:
* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.
* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.
[[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|Решение]] данной задачи легко сводится к поиску потока минимальной стоимости.
== Ссылки ==
Proshev
419
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/15369»

Навигация