Оптимизация на графах: потоки минимальной стоимости в транспортных сетях
Задача о потоке минимальной стоимости (Minimum Cost Flow Problem, MCFP) является объединяющей и фундаментальной проблемой сетевой оптимизации. Она обобщает несколько классических задач теории графов: задачу о кратчайшем пути, задачу о максимальном потоке, транспортную задачу и задачу о назначениях. Цель MCFP заключается в поиске наиболее дешевого способа пересылки заданного объема ресурса через транспортную сеть от источников к стокам, учитывая пропускные способности ребер графа и удельные стоимости транспортировки.