|
67 где fy емкость потока в сети TV; s исток и t сток сети N. Для решения необходимо минимизировать функцию mb k=i,...,Kr-, r=i,...,K. Считаем, что имеет место сохранение потока в каждом узле сети; это означает, что поток, втекающий в узел, равен потоку, выходящему из него. Очевидно, что ограничения по потоку не распространяются на исток и сток. Введем следующие обозначения: и с(е^с, (q=\E(N)\). Мы имеем следующую задачу линейного программирования для (12),(13): q 2 = 1 при условиях Bf=(l,0,...,0,-l)'; (vj=s=l; vp=t=-l). Далее, согласно пункту 5 аналитико-оптимизационной процедуры, если мы получаем лучшее решение Т*»,*,, то мы должны повторить выполнение алгоритмов анализа и коррекции для ТЦУ и шаг по оптимизации времени выполнения ТЦУ с выполнением граничных условий, поскольку есть вероятность изменения как ВВР, так и ВР. Повторяя этот шаг, мы можем получить новый критический путь графа ТЦУ и улучшить решение. Если мы получим тот же результат, то работа алгоритма останавливается и процесс оптимизации ТЦУ прекращается. |
fji емкость потока в сети 7V; s исток и t сток сети N. Для решения необходимо минимизировать функцию тгп{ hk-rfji}, к = г = (13) ee£(7V) Считаем, что имеет место сохранение потока в каждом узле сети; это означает, что поток, втекающий в узел, равен потоку, выходящему из него. Очевидно, что ограничения по потоку не распространяются на исток и сток. Введем следующие обозначения: /(ег-) = fiK с(ег) = сг (q = E(N) ). Мы имеем следующую задачу линейного программирования для (12),(13): ч (14) г=1 при условиях Bf = (1,0,.. .,0,-1)'; (v1 = 5 = l; vp = t = -1). Далее, согласно пункту 5 аналитико-оптимизационной процедуры, если мы получаем лучшее решение T*ninl то мы должны повторить выполнение алгоритмов анализа и коррекции для ТЦУ и шаг по оптимизации времени выполнения ТЦУ с выполнением граничных условий, поскольку есть вероятность изменения как ВВР, так и ВР. Повторяя этот шаг, мы можем получить новый критический путь графа ТЦУ и улучшить решение. Если мы получим тот же результат, то работа алгоритма останавливается и процесс оптимизации ТЦУ прекращается. Для реализации же полной схемы необходимо остановиться на одном из важных этапов анализа ТЦУ, который позволяет получить вероятностные характеристики времени реализации как отдельных задач, так и ТЦУ в целом. 74 |