Решение - сетевая задача
Cтраница 1
Решение сетевых задач может потребовать таких орудий, как теория графов ( ветвь топологии), теория графов сигналов ( ветвь теории графов), теория массового обслуживания ( или очередей) и линейное программирование. [1]
 |
Схема взаимодействия прикладных программ вычислительной сети. [2] |
Решение разнообразных сетевых задач обеспечивается специализацией систем, реализуемых абонентскими и коммуникационными машинами. [3]
Алгоритм решения сетевой задачи с ограниченными сверху переменными дает оптимальные значения xtj, являющиеся также целочисленными. Следует учитывать, что значения иц могут быть такими, что допустимое решение не будет существовать даже тогда, когда общие поставки равны общему спросу. Кроме того, необходимо достаточно осторожно выбирать исходное пробное решение, а именно оно должно содержать базисное множество маршрутов с потоками, не превышающими заданные ограничения по пропускной способности. Добиться выполнения этого условия не столь сложно, однако подробное изложение этого вопроса выходит за рамки данной книги. [4]
Эти свойства позволяют интерпретировать симплекс-алгоритм решения сетевых задач. Будем последовательно соединять сначала узлы производства со всеми соседними узлами с помощью дуг, исходящих из узлов производства, следя за тем, чтобы добавление новой дуги не привело к образованию контура. Введя новую дугу, пометим узел, соединенный с исходным. Когда все узлы производства будут просмотрены, проделаем то же с узлами потребления, причем будем использовать лишь дуги, входящие в узлы потребления. Если после этого останутся непомеченными некоторые промежуточные узлы, повторим ту же процедуру, начиная от помеченных промежуточных узлов, соединенных с уз-ламп производства. Дерево будет построено, когда все узлы окажутся помеченными. Если в графе остаются изолированные друг от друга множества точек, исходная задача распадается на ряд самостоятельных. [5]
Исходя из этого, разработан ряд алгоритмов решения сетевых задач. [6]
Все сказанное выше справедливо и для ГАЭС, причем для насосного режима будет иметь особое значение решение сетевой задачи по балансу токов и напряжений во время пуска насосных агрегатов с учетом ограничений пропускной способности ВЛ и качества напряжения на шинах ГАЭС. [7]
В целом же преимущества матричного метода настолько велики и существенны, что целесообразность его применения для решения сетевых задач не вызывает сомнений. Поэтому в настоящее время практически все исследования сложных электрических цепей выполняются с применением алгебры матриц. [8]
Для каждой висячей вершины Ыг определяется решением транспортной задачи с промежуточными перевозками для полного графа, соответствующего данному подмножеству. Для обязательных ветвей потоки входят в базисные решения Таким образом можно определить со для каждой висячей вершины. Pfj-новидность метода Y решения сетевой задачи предусчгтриваст ветвление, начг. Ветвление закапчивается в точке D, соответствующей дереву минимальной длины. [9]
Если выполнить это условие, то оказывается, что последовательность получаемых решений содержит минимальную стоимость по сравнению со всеми остальными значениями при одной и той же величине потока в сети. Ото обстоятельство позволяет изменить структуру алгоритма, что в свою очередь обеспечивает возможность обобщения потокового метода для решения более сложных сетевых задач. Смысл алгоритма заключается в том, чтобы увеличивать общую величину потока таким образом, чтобы это увеличение происходило при минимальных приращениях затрат. F единиц потока распределяются по сети, с помощью излагаемого метода отыскивается путь минимальной стоимости, увеличивающий поток, причем увеличение потока производится именно на этом пути. Метод отыскания пути минимальной стоимости основан на алгоритме выбора кратчайшего лтршрута. [10]
Обеспечение практической реализуемости столь крупных по масштабам систем обусловливает необходимость разработки эффективных методов решения операционных задач. Следовательно, читателю необходимо составить ясное представление о развитии методов ( алгоритмов) решения задач и понять, что имеется в виду, когда речь идет об использовании особых структурных свойств модели. Чтобы достигнуть этой цели, нужно рассмотреть конкретные примеры. Приведенные в этой главе алгоритмы решения сетевых задач служат именно такой иллюстрацией. [11]
Для построения вычислительной сети в качестве коммуникационных устройств в СМ ЭВМ используются синхронный адаптер АДС-С и мультиплексор МПД-ПСА. Мультиплексор применяется преимущественно в коммуникационных ЭВМ, выполняющих функции узлов коммутации пакетов, а адаптер - для подключения абонентских ЭВМ. Оба устройства имеют выход на стык С2 и ориентированы на использование каналов телефонного типа. Здесь следует отметить, что принятый в СМ ЭВМ протокол канального уровня ( типа ДДСМР) допускает использование асинхронных методов передачи по каналу. Поэтому при построении вычислительной сети СМ ЭВМ возможно применение асинхронных устройств. Практически могут использоваться все коммуникационные устройства, за исключением асинхронного терминального мультиплексора. Однако при этом необходимо учитывать, что применение асинхронных методов для передачи массивов информации снижает эффективность использования канала связи. Кроме того, асинхронные устройства не имеют аппаратных средств выполнения протокольных функций, в результате чего увеличивается загрузка центрального процессора при решении сетевых задач. Необходимые для построения вычислительной сети последовательные каналы связи, в зависимости от расположения сопрягаемых ЭВМ, могут иметь длину от нескольких сотен метров до тысяч километров. [12]
Страницы: 1