Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 30

Работы будем обозначать сплошными дугами, а отношения предшествования (фиктивные дуги) – прерывистыми. Составим из работ слоистую сеть. На слой 1 поместим работы, которым ничего не предшествует. Работам следующих слоев предшествуют работы слоев с меньшими номерами, причем хотя бы одна работа с непосредственно предшествующего слоя.

Правила редукции графа. 1. Если концы фиктивной дуги связывает путь, то дугу можно удалить (из r₁ в r₆ и из r₃ в r₇).

2. Если в  вершину втекает, или из нее вытекает единственная дуга, и она фиктивна, то начало и конец дуги можно склеить (r₃ поглощает 2 дуги, r₅ и r₆ по 1).

3. Две работы, следующих одна за другой, объединим в одну с суммарной длительностью, если степень вершины на стыке равна 2 ( в примере - r₆ и r₇).

Объединим все вершины слоя 1 в вершину s, последнего слоя – в вершину t.

Пусть a_i – самый ранний срок начала работ, выходящих из вершины j, а w_i – самый поздний срок окончания работ, входящих в вершину j при условии, что весь комплекс работ будет завершен в минимальное время. Тогда

a₁ = 0,   a_i = max _j{a_i + t_ij }               w_t = a_t ,   w_i = min _j{w_j - t_ij }

D_ij = w_j - t_ij - a_i  - максимальная задержка работы, выполняющейся на отрезке (i,j).

Работу назовем критической, если D_ij = 0. Путь критический, если все дуги в нем критические. Он – самый длинный в сети.

Двойственность в сетевом планировании.

Задача нахождения α_i= max{α_i+ d_ij} ~ задаче α_t- α_s→ min при α_i– α_j≥ d_ij

Она двойственна прямой задаче c’x → max, Ax = b, x ≥ 0 с параметрами: A - матрица инциденций, c ={d_ij} – длительности работ (реальных и фиктивных), x – единичный поток. Ограничения прямой задачи = уравнения баланса для потока. Матрица инциденций вполне унимодулярна Þ ЛП = ЦЛП Þ c’x = длина пути. Цель – найти максимальный путь. Граф ацикличен Þ задача полиномиальна.

Выделение критических работ и путей непосредственно следует из ТДН ???

Обратим внимание на то, что y=α в двойственной задаче y’b → min, y’A ≥ c’ может быть любым Þ ограничения прямой задачи имеют форму равенств. b=(-1,0   0,1).

Связь с NP ‑полной задачей МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ.

3.5. ПОТОКОВЫЕ ЗАДАЧИ

Задача о максимальном потоке (ЗМП).

Пусть S – сеть, т.е. граф (V,E) с выделенными стартовой и терминальной вершинами s, t ÎV; A ={a _ij ³ 0} – матрица пропускных способностей ребер,
a _ij = 0 Û ребра нет; поток X ={x _ij}– матрица, удовлетворяющая ограничениям:

0 £ x _ij £ a _ij ,              S_j x _ij = S_k x _ki , " i ¹ s,t – уравнение баланса.

Максимизируем величину потока, вытекающего из вершины s:   F( X ) = S_j x _sj .

Предположение А. r=min{x_ij, x_ji} = 0. Иначе проводим операцию ГАШЕНИЕ:
x_ij= x_ij– r, x_ji = x_ji– r. Поток при этом остается допустимым. В том числе x_ii = 0. Предположение Б. x _js = x _tj = 0 (в s ничего не втекает, из t ничего не вытекает).

На диагонали матрицы X стоят нули. Суммы элементов первой строки и последнего столбца равны. Для остальных строк: сумма элементов строки i равна сумме элементов i-го столбца.

Все ограничения и целевая функция линейны Þ это задача ЛП.

Как и задача о кратчайшем пути, она может решаться волновым алгоритмом.

Пусть W – множество включенных вершин: WÌV, sÎW, tÏW. Обозначим через R(W) ={(v₁,v₂)ÎE | v₁ÎW, v₂ÏW}  -разрез,`R(W) ={(v₁,v₂)ÎE | v₁ÏW, v₂ÎW} -антиразрез,
a (R (W )) =  - пропускную способность разреза. 

Теорема 1: Для любого потока X и для любого W .

Доказательство. Имеем  .

Следствие 1. S_j x _sj = S_k x _kt . Для этого достаточно взять W = V \ {t}.

Следствие 2. Для любого потока X и для любого W имеем F (X) ≤ a (R (W )) .

Доказательство:      .

Неравенство верно для любых Xи W Þ .

Теорема 2 (Форда-Фалкерсона):