3. Условная вероятность того, что операция выполняется, если известно, что начальное событие i появилось благодаря выбору случайной акции я p,y(^):= PK( выполняется j i имело место), где ру (я) = gij (#)/ qt (я) для ,(я)>0, иначе pj =0. Очевидно, что все эти вероятности могут быть выражены в терминах узловых и дуговых переменных и вероятностей ftw. Как было условлено ранее, при задании некоторой реализации процесса дуговые переменные w(y Е) и узловые переменные и((ie V) определены. Итак, рассмотрим ожидаемую стоимость с(я), как результат, соответствующий случайной акции л. Пусть через Ех обозначено ожидаемое значение этой переменной с учетом вероятности Рт и пусть cw соответствует затратам на W-e исполнение процесса. Тогда, согласно (2.2.4) и (2.2.6), для ожидаемой стоимости имеем с(л-) = (сж) = £ с/, = z Wu (4 И€«* (/,/б£) которая конечна для каждого ЯеП. Необходимо найти случайную акцию (и, следовательно, соответствующую реализацию процесса), которая минимизирует ожидаемую стоимость исполнения. Предполагается, что для каждой операции существует наименьшая и наибольшая вероятности (границы), соответствующие исполнению при условии, что / произошло. Определим 0<^.<^W (2.2.7) Кроме того, рассматриваются только случайные акции п, для которых вероятность 4(#=<7/я) (2.2.8) соответствует активации стока .у, т.е. вероятности успешного завершения процесса и не меньше, чем заранее заданная нижняя граница э, где 0 <э<1. 79 |
Ру(я):= Рп ( выполняется i имело место), где ру (л-) = gy (я)! (я) для qt (я)>0, иначе ру =0. Очевидно, что все эти вероятности могут быть выражены в терминах узловых и дуговых переменных и вероятностей xw. Как было условлено ранее, при задании некоторой реализации алгоритма дуговые переменные Wy (G Е) и узловые переменные (i& V) определены (см. Опр.2). Итак, рассмотрим ожидаемую стоимость с(я), как результат, соответствующий случайной акции я. Пусть через Ет обозначено ожидаемое значение этой переменной с учетом вероятности Р„, и пусть cw соответствует затратам на W-Q исполнение алгоритма. Тогда, согласно (1.21) и (1.23), для ожидаемой стоимости имеем с(я-) = E„(clv)='£ c^w = YcijSij(А wee (i,jeE) которая конечна для каждого я еП. Необходимо найти случайную акцию (и, следовательно, соответствующую реализацию алгоритма), которая минимизирует ожидаемую стоимость исполнения. Предполагается, что для каждой задачи существует наименьшая и наибольшая вероятности (границы), соответствующие исполнению при условии, что i произошло. Определим 0<Л^. <ру(я)<ку <1 (g/(^)>0; &E). (1.24) Кроме того, рассматриваются только случайные акции я, для которых вероятность q(n):=qs(n) (1.25) соответствует активации стока s, т.е. вероятности успешного завершения процесса и не меньше, чем заранее заданная нижняя граница э, где 0 <э 1. 102 |