|
2) |
3) |
||||
|
4) |
5) |
Обратите внимание на то, что для нахождения наикратчайшего расстояния от очередного пункта до конечного достаточно среди всех соседних пунктов (в направлении конечного) найти такой, что бы сумма расстояний от очередного пункта до соседнего и от соседнего до конечного (она отмечается в вершине) была наименьшей.
2. Двигаясь от начального пункта A до конечного L по отмеченным дорогам,
находим наикратчайший маршрут ADFKL, длина которого равна 10.
Пример 2. Для производства некоторой продукции предприятие закупило новое оборудование. Зависимости производительности оборудования и затрат на его содержание и ремонт приведены в таблице:
|
Время эксплуатации оборудования (лет) |
||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
|
|
Годовой выпуск продукции (тыс. руб) |
80 |
75 |
65 |
60 |
60 |
55 |
|
Затраты на содержание и ремонт оборудования (тыс. руб) |
20 |
25 |
30 |
35 |
45 |
55 |
Таблица 1.
Зная, что затраты на покупку нового оборудования составляют 40 тыс. рублей, а заменяемое оборудование списывается, составить план замены оборудования в течение 5 лет, при котором общая прибыль за данный период времени максимальна.
Решение. Вычитая из стоимости готовой продукции затраты на содержание и ремонт оборудования, получим зависимость прибыли предприятия от времени эксплуатации оборудования:
|
Время эксплуатации оборудования (лет) |
||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
|
|
Прибыль (тыс. руб) |
20 |
50 |
35 |
20 |
15 |
0 |
Таблица 2.
Примечание. Закупив в начале года новое оборудование, предприятие в этот год получает прибыль 80 – 40 – 20 = 20 (тыс. руб.).
В конце каждого года у предприятия есть выбор: оставить прежнее оборудование либо приобрести новое и получить прибыль согласно таблицы 2.
Отмечая вершинами графа концы финансовых лет, а весами рёбер прибыль от эксплуатации оборудования, получим:
что следует понимать следующим образом:
Аналогично, понимаются веса рёбер в столбцах IV и V.