Cтраница 2
Рассмотрим двойственную задачу к полученной сетевой задаче. [16]
Эти свойства позволяют интерпретировать симплекс-алгоритм решения сетевых задач. Будем последовательно соединять сначала узлы производства со всеми соседними узлами с помощью дуг, исходящих из узлов производства, следя за тем, чтобы добавление новой дуги не привело к образованию контура. Введя новую дугу, пометим узел, соединенный с исходным. Когда все узлы производства будут просмотрены, проделаем то же с узлами потребления, причем будем использовать лишь дуги, входящие в узлы потребления. Если после этого останутся непомеченными некоторые промежуточные узлы, повторим ту же процедуру, начиная от помеченных промежуточных узлов, соединенных с уз-ламп производства. Дерево будет построено, когда все узлы окажутся помеченными. Если в графе остаются изолированные друг от друга множества точек, исходная задача распадается на ряд самостоятельных. [17]
Метод динамического программирования часто используется в сетевых задачах для нахождения кратчайшего пути, соединяющего две вершины. Данный пример является иллюстрацией данного подхода. [18]
Биркгофа и Д.Б. Диаза посвящена аналогичным вопросам для нелинейных сетевых задач. [19]
Данциг показал [56], что симплекс-метод для сетевой задачи линейного программирования ( ЛП) сводится к целенаправленному перебору деревьев этой сети. [20]
Здесь обсуждается, каким образом специфический характер структуры сетевой задачи можно эффективно использовать как на стадии построения и анализа соответствующей модели, так и на стадии нахождения оптимального решения. Причины заинтересованности в ознакомлении со специальными вычислительными методами, применимыми именно к сетевым моделям, очевидны. Вспомним транспортную сетевую модель, рассмотренную в разд. В реальной задаче число заводов вполне может оказаться равным, скажем. [21]
Исходя из этого, разработан ряд алгоритмов решения сетевых задач. [22]
Ясно, что сформулированная задача (14.1) - (14.3), называемая обычно линейной сетевой задачей, является задачей линейного программирования. Часто рассматривается более общая задача, называемая задачей о потоке в сети с ограниченными пропускными способностями. [23]
Анализатор аварийного дампа NDA выполняет форматирование листингов структур данных после аварии какой-либо сетевой задачи или задач. Если целостность этих структур нарушена, NDA выдает диагностическое сообщение. [24]
Транспортную задачу, о которой рассказывалось в первой главе, легко можно интерпретировать как сетевую задачу о потоке минимальной стоимости. Взяв рисунок, приведенный на стр. Пункт отправления содержит F 25 холодильников, из которых 11 следует отправить на первую фабрику, а 14 - на вторую. Пункт назначения должен принять 25 холодильников, причем 10 из первого магазина, 8 из второго и 7 из третьего. Эти условия могут стать частью математической модели, если мы добавим к ней ограничения, требующие, чтобы из пункта отправления на соответствующие фабрики было послано 11 и 14 холодильников, а в пункт назначения прибыло ровно 10, 8 и 7 холодильников из соответствующих магазинов. Условия такого типа внесут небольшие изменения в общий алгоритм и могут быть включены в общую задачу о потоке минимальной стоимости. [25]
Все сказанное выше справедливо и для ГАЭС, причем для насосного режима будет иметь особое значение решение сетевой задачи по балансу токов и напряжений во время пуска насосных агрегатов с учетом ограничений пропускной способности ВЛ и качества напряжения на шинах ГАЭС. [26]
В целом же преимущества матричного метода настолько велики и существенны, что целесообразность его применения для решения сетевых задач не вызывает сомнений. Поэтому в настоящее время практически все исследования сложных электрических цепей выполняются с применением алгебры матриц. [27]
Программа TORA предлагает средства для обращения матриц, решения систем линейных уравнений, задач линейного целочисленного программирования, транспортных и сетевых задач, задач теории массового обслуживания и теории игр. TORA может использоваться в автоматическом режиме или в режиме пошагового выполнения, который можно считать режимом обучения. В автоматическом режиме выводится конечное решение задачи, обычно в стандартном формате, присущем серьезным научным программам. [28]
Во всех случаях, когда задача линейного программирования имеет вид ( 1) - ( 4), она приводится к эквивалентной сетевой задаче. Иногда для приведения задачи к виду ( 1) - ( 4) приходится объединять уравнения, изменять знаки коэффициентов и вводить дополнительное соотношение либо рассматривать двойственную к исходной задачу. [29]
Проведенные в СЭИ С.В. Сумароковым исследования, связанные с применением такого подхода для решения задач, обсуждаемых в данной главе, показали возможность построения подобных вспомогательных сетевых задач и перспективность этого метода. [30]