Метод динамического программирования позволяет определить глобальный экстремум с точностью до шага оптимизации, применяется для многошаговых задач.
Основой динамического программирования является принцип оптимальности
Р. Беллмана. Оптимальное решение обладает тем свойством, что каковы бы не были начальные состояния и начальное решение, последующее решение должно быть оптимальным по отношению к предыдущему. Таким образом, преимуществами данного метода являются:
нахождение глобального экстремума;
независимость от начального решения;
решение на последующих шагах не оказывает влияния на величину функции цели и всегда оптимальнее, чем на предыдущих шагах.
Недостатки динамического метода:
большой объем вычислений, из-за которого вынуждены увеличивать шаг дескеризации, что приводит к уменьшению точности нахождения глобального экстремума.
Для решения задачи методом динамического программирования для каждой опоры определяется набор дискретных высот подвеса правых антенн (в зависимости от выбранного шага дискретности). Берем Dh=30м.
y1’ x1’ y2’ x2’ y3’ x3’ y4’ x4’
0 79 150 83 133 76 119 0
109 113 113 107 106 108
139 77 143 82 136 96
Высоты, неудовлетворяющие системе ограничений, отбрасываются. После этого призводится последовательное комбинирование соседних наборов высот подвеса правых антенн с отбором доминирующих частных решений (точка на графе) по частным значениям критерия оптимальности К.
Граф данной системы представлен на рис.3
| |||
 | |||
В вершинах графа - абсолютные высоты подвеса правых антенн. Весами дуг являются частные значения стоимости опор и фидерных трактов:
соответствующие данным абсолютным высотам подвеса левой и правой антенны (указаны в скобках);
соответствующие суммарной стоимости данной опоры и предыдущих, находящихся на пути минимальной стоимости (представлены справа).
Также отметим на графе последовательность вычислений от 1 до 20 (зеленые цифры).
Стоимость левой опоры (х1). х1=38м
с=с1(х1)‡0,06 х1=с1(38)+0,06 38=35+0,06 38=37,28 тыс.рублей
х1=68м с=с1(68)+0,06 68=66,3+0,06 68=70,38 тыс.рублей
х1=98м с1(98)+0,06 98=97,8+0,06 98=103,68 тыс.рублей
y2=100м, x2=33м, x1=38м
c1(max(y2,x2))+0.06(y2+x2)=100+0.06(100+33)=107.98 тыс. руб.
y2=100м, x2=63м, x1=38м
c1(100/63)+0.06(100+63)=100+0.06(100+63)=109.78 тыс. руб.
y2=100м, x2=93м, x1=38м
c1(100)+0.06(100+93)=100+0.06(100+932)=111.58 тыс. руб.
y2=63м, x2=33м, x1=68м
c1(63)+0.06(63+33)=61+0.06(63+33)=66.76 тыс. руб.
y2=63м, x2=63м c1(63)+0.06(63+63)=68.56 тыс. руб.
y2=63м, x2=93м c1(93)+0.06(63+93)=92.5+0.06(63+93)=101.86 тыс. руб.
10) y2=27м, x2=33м c1(33)+0.06(33+27)=29.8+0.06(33+27)=33.4 тыс. руб.
11) y2=27м, x2=63м c1(63)+0.06(27+63)=61+0.06(27+63)=66.4 тыс.рублей
12) y2=27м, x2=93м c1(93)+0.06(27+93)=92.5+0.06(27+93)=99.7 тыс.рублей
13) y3=71м, x3=34м c1(71)+0.06(71+34)=69.4+0.06(71+34)=75.7 тыс.рублей
14) y3=71м, x3=64м c1(71)+0.06(71+64)=69.4+0.06(71+64)=77.5 тыс.рублей
15) y3=65м, x3=34м c1(65)+0.06(65+34)=63.1+0.06(65+34)=69.04 тыс.рублей
16) y3=65м, x3=64м c1(65)+0.06(65+64)=63.1+0.06(65+64)=70.84 тыс.рублей
17) y3=40м, x3=34м c1(40)+0.06(40+34)=37+0.06(40+34)=41.44тыс.рублей
18) y3=40м, x3=64м c1(64)+0.06(40+64)=62.1+0.06(40+64)=68.34тыс.рублей
19) y4=40м, c1(40)+0.06 40=39.4тыс.рублей
20) y4=29м, c1(29)+0.06 29=27.34тыс.рублей
Таким образом, полученное оптимальное решение К=229,7 тыс.рублей (лучше, чем методом градиентного поиска). х1=38м, у2=100м, х2=93м, у3=40м, х3=34м, у4=40м
Дата: 2019-11-01, просмотров: 248.
