|
| |
|
Слаботочка Книги Окончательная доминирующая последовательность
Таблица 13.15 Значения функции я]),- Таблица 13.16 Значения функции Беллмана
Аналогичньш образом по табл. 13.14 определяем, что решением для второй задачи (вероятность безотказной работы должна быть не ниже 0,45) является 1/4 = = 17. Также последовательно находим, что = 17 соответствуют значения = 4, = 3, Хд = I, Xi = 1 и Xg = 4. При этом стоимость системы составляет 62 ед. 13.3.4. Методика отыскания решения с заданной относительной точностью. Для задач (13.1), (13.2) большой размерности (т 1000), решение которых требуется получить с заданной относительной точностью, можно воспользоваться следующим алгоритмом, основанным на схеме динамического программирования. (Алгоритм излагается для задачи (13.1).) 1. Вычисляем Д = bLJm, М = fm/б], где б - заданная требуемая относительная точность. 2. Определяем F, Z - границы возможного изменения количества резервных элементов на всех участках системы (см. п. 13.3.1). 3. Заполняем табл. 13.15 значениями целочисленной функции: гр (Xj) = = [Li {Xi)IM, i = 1, m, Xi = Y, Y +- 1, z 1, Z (знак [ ] означает, как всегда, целую часть числа). 4. Заполняем однострочную табл. 13.16 значениями функции Беллмана при 1 = 1: G (k) = Cj rain {xil%(xi) <k}, k= 1, .... M, одновременно заполняем первую строку табл. 13.17: X* {k) = rain {Xiij5i (Xj) < } = G {k)lci. 5. Последовательно при / = 2, .... m выполняем действия п. 4. 6. Последовательно при k = М, М - 1, 1 изменяем значения функции G {k) в табл. 3.16: G{k)= min \G{k-i{Xi)) + CiXi\i{Xi)<k], (13.8) - Y, Z одновременно заполняем /-ю строку табл. 13.17 теми значениями х* (k), на которых достигается минимум в (13.8). 7. По табл. 13.17 определяем Хт = Хт (т, М), затем последовательно от / = m - 1 до I = 1 вычисляем Таблица 13.17 Значения xi, минимизирующие G()
А: = - iJjj+j (x? + i), k"= М и по табл. 13.17 находим х° = х? {Щ. Найденный наборxJ, .... х представляет собой приближенное решение задачи (13.1) с заданной относительной точностью б. Алгоритм можно использовать только для решения задач с помощью ЭВМ, причем при решении задачи размерности т потребуется 2т обращений к внешним носителям памяти. Промежуточные вычисления для алгоритма наискорейшего спуска
13.3.5. Метод наискорейшего покоординатного спуска. Этот метод значительно меньшей трудоемкости, чем метод динамического программирования. Он позволяет построить подпоследовательность окончательной доминирующей последовательности, полученной в п. 13.3.3, причем разница в значениях С (х) для соседних членов этой подпоследовательности не превышает шах Cj, т. е. в большин- стве практических задач метод наискорейшего покоординатного спуска позволяет получить решение с достаточной точностью. 1. Заполняется табл. 13.18 (т строк 6 столбцов): 1-й столбец i - номер участка системы; 2-й = уй 3-й Li W); 4-й (4» + 1); 5-й Д!" = = L. (xj") L. (xl" + 1); 6-й gP = lЧci. (В процессе работы алгоритма числа в табл. 13.18 изменяются, поэтому при использовании алгоритма вручную все столбцы, кроме 1-го, нужно заполнять карандашом.) 2. Вычисляются: L) = 2=1 Li (л;}") - сумма чисел, стоящих в 3-м столбце, и С(«) = 2Г=1г4». Далее переходим к последовательному выполнению шагов алгоритма. Описывается k-й шаг. 3. В 6-м столбце табл. 13-18 отыскивается максимальное число и фиксируется / - номер строки, в которой оно стоит. 4. Вычисляются: L(« = L(fi-i) - Д}*"-; CW = Ck-i) + Q - и проверяются выполнения неравенств: для задачи (13.1) L) < Lp, для задачи (1.3.2) C(fe) > Со. Если соответствующее неравенство выполнено, то работа алгоритма заканчивается, а решение задачи выдается в виде: для задачи (13.1) .... xf~i\ + 1, xf+l\ x*->; для задачи (13.2) хГ, х-\ В противном случае числа в /-й строке табл. 12.18 изменяются по следующему правилу: 2-й столбец х} = xf~ + 1 - число увеличивается на 1; 3-й столбец Lj (xf) - переносится число из четвертого столбца; 4-й столбец Lj {xf + 1); 5-й столбец Д = Lj [xf) - Lj (xf + 1); 6-й столбец gf = AflCj. После этого переходим к следующему шагу алгоритма. Пример 13.3. Рассмотрим ту же систему, что и в примере 13.2. Требуется определить оптимальный резерв на каж- дом участке для двух случаев: 1) общая стоимость резерва не более 28 ед.; 2) вероятность безотказной работы не менее 0,45 (Lo = 0,8). Решение. Выполняя 0-й шаг алгоритма для задачи (13.1), заполняем табл. 13.19; суммируя числа в 3-м столбце, получаем LC) = 2,3256; вычисляем С(в) = 2 CixJ«> = 18 ед. 1=1 Таблица Промежуточные вычисления для примера 13.3 13.19
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [70] 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||