ВУЗ:
Составители:
Рубрика:
66
на рис. 5
1
(табл. 25). Действительно, не выгодно (в смысле энергозатрат)
все грузы вести в пункт
3
A , куда должен быть доставлен самый большой
груз (6
3
=a ), а затем снова возвращаться в пункт
1
A для доставки
остальных грузов. Без специальных расчетов видно, что оптимальный
замкнутый маршрут из пункта
1
A проходит по жирной ломаной линии, при
этом попутно доставляются грузы в пункты
2
A ,
5
A ,
4
A а из пункта
3
A
транспорт возвращается в пункт
1
A порожний («везет» пассивный груз
1
1
=a ). Таким образом, оптимальным гамильтоновым циклом,
минимизирующим энергозатраты, будет являться замкнутый маршрут
1,3,4,5,2,1
0
1
=
μ
. (4.24)
Первое необходимое условие оптимальности в (4.24) выполнено, что
следует из сравнения пар элементов в (4.24) с соответствующими
элементами табл. 26. В проверке второго необходимого условия
оптимальности не возникает необходимости, поскольку в (4.24) нет
повторяющихся элементов (кроме начального). Согласно (4.1) для
полученного решения (4.24) и данных, приведенных на графе (рис. 5),
энергозатраты минимальны и равны:
min
0
1
1201619544221,3,4,5,2,1)( ЭЭ ==⋅+⋅+⋅+⋅+⋅== 66
μ
. (4.25)
Найдем решение, используя принцип убывания веса грузов, для чего
граф (рис. 5) запишем в матричной форме (табл. 25) и эстафетным
методом (раздел 2) вычислим полное семейство кратчайших маршрутов
и их длин (табл. 26).
Упорядочим номера пунктов по убыванию веса
грузов
j
a :
(
j
): 3, 4, 5, 2, 1,
(
j
a ): 6, 5, 4, 2, 1.
Наиболее тяжелый груз
6
3
=
a доставляется в пункт
3
A по
кратчайшему маршруту
3;1 (табл. 26); из пункта
3
A
в пункт
4
A
груз
4
5
=a
направляется по маршруту 4;3 (табл. 26) и т.д., что, в конечном
счете, приведет к решению:
1,,5,2,,4,3,11,4,55,2,1,44;33;1
1
41
=
∪∪∪=
μ
. (4.26)
1
Участки дорог, по которым движение возможно только в одном направлении, указаны
направленными (ориентированными) дугами (стрелки).
Страницы
- « первая
- ‹ предыдущая
- …
- 62
- 63
- 64
- 65
- 66
- …
- следующая ›
- последняя »
