Описание Области
подробнее…
Постановка задачи
Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества потока через транспортную сеть.
Дано:
• 1 источник – завод (склад), с которого начинается передача потока (перевозка товара).
• 1 сток – магазин (склад), которым заканчивается передача потока (перевозка товара).
• Набор промежуточных вершин (складов), через которые проходит поток (перевозятся товары).
• Набор дуг (дорог), соединяющих вершины графа. Каждой дуге сопоставляется 2 характеристики: пропускная способность дуги и стоимость дуги.
• Величина потока (объем товара) который требуется передать от источника к стоку.
Требуется:
Найти поток минимальной стоимости заданной величины от источника к стоку. Т.е. самый дешевый способ перевозки заданного объема товара от завода до магазина.
кратко