III Международная студенческая научная конференция Студенческий научный форум - 2011

Данная задача состоит в определении в транспортной сети кратчайшего пути между заданными исходным пунктом и пунктом назначения. Такая модель может быть использована для описания различных экономических ситуаций. В качестве примера рассмотрена следующая задача.

Фирма по прокату DVD-дисков планирует их замену на очередные 6 лет. Партия дисков должна эксплуатироваться на менее одного года, прежде чем её заменяют. На рис. 1 приведены стоимости замены партии дисков в тыс. ден. ед., зависящие от времени замены и числа лет, в течение которых диски находятся в эксплуатации.

Для определения плана замены дисков, обеспечивающего фирме минимальные расходы, применяется метод нахождения кратчайшего пути.

Вычисления производятся по формулам:

где  - кратчайшее расстояние до предыдущего узла ;  - расстояние между текущим узлом  и предыдущим узлом .

Кратчайший маршрут от исходного узла до узла назначения определяется, начиная с узла назначения путём прохождения узлов в обратном направлении по дугам, на которых реализовались минимальные значения расстояний на каждом шаге.

В соответствии с приведённой методикой, проведены вычисления и найден кратчайший путь в данной схеме: . При этом стоимость проекта составит  тыс. ден. ед. Это означает, что каждый диск заменяется через три года, а через шесть лет списываются.

Код для цитирования: Скопировать