|
| |
|
Слаботочка Книги Приближенное решение можно записать следующим образом: а) решается k задач вида i(=Gj if=G. находятся соответствующие оптимальные значения х\, хт для каждой /-й задачи любым из методов, описанных выше; б) для каждого i-ro элемента находятся наибольшие значения X* - max xi; в) для каждого подмножества элементов Gj находится часть (обозначим ее через Gy*), которая нужна только для выполнения именно /-Й функции. Через С/ обозначим оставшуюся часть подмножества Gj; г) для каждого подмножества G* находится значение Приме ч а ние. Если в подмножество G/ не входит ни один элемент, т. е. если /-я функция выполняется при помощи независимой группы элементов, то положим RJ = I; д) для каждого множества Gj вычисляется значение Ry=Rj/R), которое представляет собой требование к вероятности безотказной работы элементов, принадлежащих подмножеству Gji е) решается дополнительно k задач вида S с,х; П Ri(Xi)Ry,jl,...,k Найденные значения оставшихся х)* принимаются в качестве решения. Таким образом, в качестве решения принимаются значения х*, найденные в п. б), и значения л:**, найденные в п. е). 13.7. ПОЛУЧЕНИЕ ОЦЕНОК СВЕРХУ В ЗАДАЧАХ БОЛЬШОЙ РАЗМЕРНОСТИ 13.7.1. Предварительные замечания. Задачу оптимального резервирования можно рассматривать как задачу математического программирования. В теории математического программирования для получения условий оптимальности решений некоторой исходной задачи и для построения алгоритмов ее решения часто строится некоторая другая задача, которую обычно называют «двойственной к исходной». При построении двойственной задачи- используются множители Лаг-ранжа. Решение двойственной задачи позволяет находить оценки сверху для труднорешаемых задач большой размерности. 13.7.2. Метод множителей Лагранжа. Запишем задачу (13.2) как задачу математического программирования: max 1 У In Rj {х,) - Y Cj д; > О, t = 1, 2,... , ml, (13.12) где X = {x = (Xl, X2, Хз, x„)M > x > 0, / = 1. 2, .... n, Xj - целые) (M - столь большое положительное число, что для любого х, удовлетворяющего «стоимостным» ограничениям задачи (13.12), выполняется условие М > х > Q). Обозначим оптимальное решение задачи (13.12) через л:", и пусть W° = = S In Rj (х/). Здесь и далее будем предполагать, что х ФО. /= 1 Введем фунцию Лагранжа для задачи (13.12): л т / п \ F (x, у) = 2 In Rj (Xj) + 2 С; - S CijXj , (13.13) /=1 i-=i \ /=1 / где у = (Ух, у2, ••> Ут) - т-мерный вектор-строка (множители Лагранжа). Рассмотрим для задачи (13.12) двойственную задачу, которая состоит в нахождении a)* = min max F (х, у). (13.14) уО хех Из теории математического программирования известно, что Г" < ю*. Следовательно, решение задачи (13.14) позволило бы найти оценку сверху для-оптимального значения функционала исходной задачи (13.12). Для решения задачи введем функцию \l3(y)==maxF(x, у). (13.15) Можно показать, что гр (у) - кусочно-линейная, выпуклая вниз функция. 13.7.3. Алгоритм решения. Возьмем некоторый вектор у >0 и обозна»им <;оответствующее ему решение задачи (13.15) через х, т. е. F (х, у) = max F (х, у) = гр (у). Возьмем любой другой вектор у > О и рассмотрим (у)- (у) = шах F (х, у) - max F (х, р) = хех хех = тах F (x, у)-F(x, у)> F(x, у)- F(x, у). Таким образом, гp(y)>F(x,y) (13.16) для любого {х € XF (х, у) = шах F (х, у)). В силу определения (13.13) неравенство (13.16) означает, что гиперплоскость 1=1 i=l \ j=l является опорной к поверхности функции гр (у) в точке у. Неравенство (13.16) было положено в основу следующего алгоритма решения задачи (13.14). 13.7.4. Описание алгоритма. Предположим, что проведено k итераций алгоритма, рассмотрим (k + 1)-ю итерацию. Шаг 1. Решаем задачу линейного программирования L (k): {п т / п \ fi i = i \ /=1 V = 1, 2.....k Здесь x) - точки, полученные на предыдущих k итерациях алгоритма. Обозначим через у*-Ь решение задачи L (k). Следует отметить, что каждая строка - ограничение в задаче L {k) - определяет опорную гиперплоскость к поверхности функции яр (у) (см. (13.16)). Таким образом, алгоритм можно рассматривать как применение метода касательных для поиска экстремума недифференцируемой функции гр (у). Шаг 2. Найдем очередное x*+i как решение задачи: F (х+1, yft+1) = max F (X, у* +1) = max ( У 1п R,• (х.)-f- хех хеХ {/1 т / п + 2 Cj-2 »=1 = 2 + 2 nix In Rj (x+i)- 2 c,,. Xj\ . (13.17) t=l /=1 [ i=l J Введем обозначения A In Rj (xj) = In Rj (Xf + 1) -- In Rj (xj), a..через x*+i будем обозначать решение задачи (13.17), соогветствующее заданному Тогда О, если А In Rj (0) < уЧ cj, 1=1 = \Xj+l, если А In Ri {Xj+l) < v i/+i c <Alni?•(л;) для л;<Л1-U M, если 2 У*+ Cij MnRj (M). Ш a Г 3. При выполнении условия = F (x*+, y*+) в работе алгоритма происходит останов, при этом полагаем cu*: = (a*+i; если же < (х* + , у*+). то добавляем к условиям задачи L (k) новую строку-ограничение, которая соответствует вновь найденному вектору х*+2. После этого начинается (к + 2)-я итерация алгоритма, т. е. происходит возвращение на шаг 1, и т. д. Функция гр (у) - кусочно-линейная, поэтому за конечное число шагов будет решена задача (13.14) и найдена оценка сверху о*. Напомним, что методы, описанные в предыдущих параграфах, позволяют находить допустимые решения, близкие к оптимальному, т. е. позволяют получить оценку снизу для оптимального значения функционала. Пусть для некоторой конкретной задачи (13.12), имеющей неизвестное оптимальное значение функционала 1", получена верхняя оценка о* и найдено некоторое допустимое решение и Г„ = 2 In Rj {Xj„). Тогда имеем о* > Г" > Г„, а величину б = (о* - /=1 - Wj/W можно использовать для оценки погрешности найденного решения х„. При практическом решении задач, содержащих от двух до четырех ограничений и до 3000 переменных, б не превышала 3 • 10-. В ряде задач было получена точное решение. 13.8. ПРИБЛИЖЕННЫЙ АЛГОРИТМ ОПТИМАЛЬНОГО ВВЕДЕНИЯ ИЗБЫТОЧНОСТИ В СИСТЕМЫ С ПРОИЗВОЛЬНОЙ СТРУКТУРОЙ Рассмотрим некоторую систему, состоящую из п элементов. Допустим, что каждый t-й элемент может находиться всего в двух состояниях: в состоянии работоспособности (Sj = 1) и в состоянии отказа (Sj = 0). Тогда в произвольный фиксированный момент времени система может находиться в одном из 2" различ- 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 |