Сайт в помощь студенту Грамоте учиться – всегда пригодится


Скачать полностью

ГЛАВА 4. АЛГОРИТМ ДЕФЕКТА

4.1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

В теории сетевого анализа значительное место занимает алгоритм дефекта, который является наиболее общим алгоритмом на детерминированных сетях с ограниченной пропускной способностью и имеет широкую область применения. И, хотя он иногда уступает по эффективности некоторым специальным алгоритмам, алгоритм дефекта позволяет решать широкий класс потоковых задач.
Перед описанием алгоритма сформулируем основные понятия и определения.
Множество дуг сети обозначим через S, множество узлов сети обозначим через N.
Если поток по дуге может принимать только определенные значения, например, если заданы верхняя и (или) нижняя границы потока, то дуга имеет ограниченную пропускную способность.
Если направление потока по дуге совпадает с ее ориентацией, то дуга называется прямой, если направление потока по дуге противоположно ее ориентации, то дуга называется обратной.
Сеть, содержащая дуги с ограниченной пропускной способностью, называется сетью с ограниченной пропускной способностью.
Циркуляцией называется поток по дугам сети, для которого в каждом узле выполняется условие сохранения потока. Для работы алгоритма дефекта требуется существование циркуляции, поэтому исходная сеть модифицируется – вводится дополнительная дуга, соединяющая источник со стоком, которая называется возвратной. Способы построения возвратной дуги зависят от вида исходной сети.
Алгоритм дефекта является итеративной процедурой, выполняющей для заданной сети с ограниченной пропускной способностью поиск циркуляции, минимизирующей суммарную стоимость потоков по всем дугам.
Алгоритм дефекта основан на теории двойственности линейного программирования и условиях дополняющей нежесткости.
Введем обозначения: fij – поток по дуге (i, j) (fij = 0, если поток по дуге отсутствует, fij > 0, если поток протекает из i в j), Lij – нижняя пропускная способность дуги (i, j), Uij – верхняя пропускная способность дуги (i, j), сij – стоимость потока из узла i в узел j.
Рассматриваемая потоковая задача может быть сформулирована в виде специальной задачи линейного программирования, формулируемой следующим образом: максимизировать
                                                        (4.1)
при условии, что
  для всех iIN (условие сохранения потока),       (4.2)
fij ? Uij (ограничения на потоки сверху),                                             (4.3)
-fij ? - Lij (ограничения на потоки снизу),                                   (4.4)
fij ? 0 (условие неотрицательности потока).                               (4.5)
Это прямая задача линейного программирования. Для любой прямой задачи существует соответствующая ей двойственная задача. В рассматриваемом случае двойственная задача формулируется следующим образом: минимизировать
                                                       (4.6)
при условии, что
pi - pj + aij - dij ? - cij   для всех (i, j)IS,                                      (4.7)
pi не имеют ограничений по знаку для всех (i, j)IS,
aij ? 0 для всех (i, j)IS,                                                               (4.8)
dij ? 0 для всех (i, j)IS.                                                               (4.9)

В данной формулировке переменные p соответствуют ограничениям, описывающим условие сохранения потока для прямой задачи, и могут принимать произвольные значения, так как эти ограничения имеют вид равенств. Переменные a в двойственной задаче соответствуют ограничениям сверху на потоки по дугам в прямой задаче, а переменные  d - ограничениям снизу.

Решения прямой и двойственной задач являются оптимальными, если:

  • оба решения допустимы;
  • для любой положительной двойственной переменной соответствующее ограничение прямой задачи является жестким;
  • для любого ограничения в двойственной задаче, не являющегося жестким, значение соответствующей переменной в прямой задаче равны 0.

Последние два условия называются условиями дополняющей нежесткости и вместе с условиями допустимости составляют необходимые и достаточные условия оптимальности решения задачи о циркуляции минимальной стоимости.
Условия допустимости для прямой задачи