Примеры экономических задач, сводимых к задаче о кратчайшей цепи

Среди экономических задач, сводимых к рассмотренным выше, можно отметить задачу о плане замены оборудования, задачу составления расписания, задачу выбора некольцевого маршрута перевозок, планирование работ по осуществлению проекта в методе критического пути. Первые три сводятся к задаче о кратчайшей цепи. В задаче о замене оборудования при этом делается допущение о дискретности срока службы оборудования. Обычно замена может быть произведена в начале очередного года эксплуатации, но не позже истечения срока службы. Узлами являются решения о замене, дугами - периоды эксплуатации от момента приобретения до ликвидации конкретного набора оборудования с обобщенной стоимостью, равной общим затратам, состоящим из начальной стоимости оборудования + эксплуатационные расходы за годы эксплуатации - ликвидационная стоимость + затраты на ликвидацию. В задачах составления расписаний узлами являются моменты окончания предыдущих и начала последующих процессов (прибытия и убытия транспортных средств, начала и окончания работ), дугами - продолжительности процессов. Данная модель справедлива в случае наличия единственного исполнителя равноправных независимых процессов. В задачах выбора маршрута узлы - транзитные пункты (пункты перегрузки и переформирования в задачах о перевозках, насосные станции для трубопроводов и т. д.), дуги - части маршрута между узлами, характеризуемые расстоянием, временем, либо стоимостью доставки.

При планировании работ по осуществлению проекта в методе критического пути узлами являются события - решения о начале выполнения некоторой (или некоторых) работы; дугами - сами работы. В зависимости от характеристик работы могут быть трех видов: реальные с ненулевыми стоимостью выполнения и временем выполнения; пассивные с нулевыми стоимостью выполнения и ненулевым временем выполнения; фиктивные с нулевыми стоимостью выполнения и временем выполнения, вводимые для выполнения условий упорядоченности совершения событий. В такой постановке продолжительность всего проекта определяется в задаче о максимальной по продолжительности цепи.