5.5. Задача о развозке (о доставке) [7, 47, 24]

В задаче о развозке граф представляет сеть дорог, одна его вершина представляет склад, а все остальные вершины изображают потребителей. Транспорт, покидающий склад, снабжает товаром некоторых потребителей, после чего возвращается на склад. Пусть «стоимость» маршрута равна (например, может быть километражем маршрута или временем, необходимым для его дрохождения). Спрашивается, сколько машин следует использовать на разных маршрутах, чтобы в один и тот же день доставлять всем потребителям товары (каждому потребителю поставляется сразу все необходимое) и чтобы суммарная стоимость проходимых маршрутов была наименьшей. Эту задачу, очевидно, можно рассматривать как ЗНР, в которой столбцы представляют всевозможные осуществимые (с учетом практических ограничений) замкнутые маршруты, начинающиеся и кончающиеся на складе. Строки представляют потребителей.

Почти идентична рассмотренной задаче задача о прокладке электрического кабеля для подачи электроэнергии от подстанции (склада) к потребителям в «кольцевых схемах энергоснабжения» [15]. Другие практические приложения ЗНП и ЗНР связаны с синхронизацией линий сборки [59, 25], государственным районированием [29], с вычислением границ в задачах общего целочисленного программирования [18], с сетевым планированием [20] и с разработкой схем защиты и нападения [8, 10].