Составители:
Рубрика:
255
х
4
=412,9; y
4
=456,4.
Полный результат решения представлен в табл. 7.3'.
Табл. 7.3'
Год Доход Отчисления Чистый
П
1
П
2
от дохода доход
1
2
3
4
437,1
435,4
434,9
412,9
562,9
520,9
477,9
456,4
1738,1
1697,6
1653,8
1602,2
243,7
234,8
226,1
нет
1494,4
1462,8
1427,7
1602,2
Суммарный чистый доход 5987,1
Расхождение в величине чистого дохода с ранее рассчитанным максимальным
доходом 5992,8 на 0,1% объясняется накоплением ошибок округлений при расчетах.
7.3. Задача о составлении оптимального маршрута
Эта задача может иметь разное экономическое приложение. Например, при определении
кратчайшего пути следования деталей по станкам, нахождения критического пути в сетевом графике, при
проектировании лесовозных дорог и т.д.
Однако прежде чем рассматривать числовой пример, сформулируем задачу в
общем виде.
Предположим, имеется некоторое множество, состоящее из намеченных пунктов.
Эти пункты могут быть занумерованы произвольно числами натурального ряда от 1 до N
включительно.
Предполагается, что каждые два пункта, входящие во множество, непосредственно
соединены между собой (дорогой и пр.).
Время, необходимое для проезда (или продвижения деталей) из любого пункта i
множества N (в дальнейшем принадлежность к множеству будем обозначать через ∈) в
пункт j∈N, непропорционально расстоянию между пунктами i иj.
В этой связи задана квадратная несимметричная матрица
T=
,
ij
t
где
t
ij
– время проезда (продвижения) из пункта
i
в пункт
j
, взятых из множества
N
.
В
задаче требуется определить оптимальный маршрут
следования через все
пункты множества
N
, при котором время переезда (продвижения) из начального пункта 1
в конечный пункт
N
было бы минимальным.
Сформулированная задача может быть отнесена к типу задач динамического
программирования, ибо нетрудно убедиться в том, что она удовлетворяет основным
свойствам задач динамического программирования.
Весь процесс переезда (продвижения) из пункта 1 в пункт
N
является
многоэтапным. На каждом этапе выбирается пункт с таким расчетом, чтобы время на
переезд было минимальным. Отсюда следует, что рассматриваемая задача является
многоэтапной (многошаговой).
Свойство
аддитивности
для этой задачи вытекает из того, что общее время на
переезд (продвижение деталей и т.п.) равно сумме времен переезда на каждом отрезке
между двумя пунктами.
И, наконец, нетрудно представить, что наименьшее время на переезд из любого
пункта
i
в пункт
N
зависит не от того, каким образом мы достигли пункта
i
, а только от
Страницы
- « первая
- ‹ предыдущая
- …
- 253
- 254
- 255
- 256
- 257
- …
- следующая ›
- последняя »
