Пр.11 «Нахождение Максимального потока сети»

Рис.1

Найти максимальный поток по сети с использованием надстройки MS Excel «Поиск решения» из истока I – вершины 1 в сток S – вершину 6.

Решение:

Для использования надстройки MS Excel «Поиск решения» необходимо сформулировать данную задачу как ЗЛП, т.е. необходимо определить неотрицательные переменные задачи, ограничения, накладываемые на них и целевую функцию.

Переменные задачи

Для получения математической модели задачи введем неотрицательные целочисленные переменные  соответствующие дугам графа, где i – индекс вершины, являющейся началом дуги, j – индекс вершины, являющейся концом дуги, которые интерпретируются как величина потока по дуге (i, j). Количество переменных определяется количеством дуг в графе.

Согласно графу из условия задачи, у нас будут 18 переменных, соответствующих дугам графа, обозначим их следующим образом:

 

Ограничения

На переменные задачи накладываются условия не отрицательности и цело численности потока  по дуге (i, j).

Математически это ограничение в общем виде можно записать следующим образом:

Для графа из условия задачи, данные ограничения будут:

Условия наличия истока I в вершине 1 и стока S в вершине 10 накладывают на задачу соответствующие ограничения.

Величина потока из истока I в вершине 1 должна быть равна величине потока, пришедшего в сток S – вершину 10. В общем виде математически данное ограничение можно записать следующим образом:

По условию задачи из вершины 1 выходят дуги (1, 2), (1, 3) и (1, 4), следовательно, величина потока из истока равна сумме потоков по этим ребрам:

В вершину 6 поток приходит по ребрам (8, 10) и (9, 10), следовательно, величина потока из истока равна сумме потоков по этим ребрам:

Из условия (1) получаем ограничение:

Величина потока по ребру не может быть больше пропускной способности ребра. Обозначив через  пропускную способность по ребру (i, j) в направлении от вершины i к вершине j, это ограничение в общем можно записать следующим образом:

Для графа из условия задачи, данные ограничения будут:

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

Математически это условие можно записать так:

где I – индекс вершины-истока, S – индекс вершины-стока

Для графа из условия задачи имеем 8 вершин, не являющихся истоком или стоком, для каждой из них получим следующие ограничения:

Для вершины 2:

Для вершины 3:

Для вершины 4:

Для вершины 5:

Для вершины 6:

Для вершины 7:

Для вершины 8:

 

Целевая функция

По условию задачи необходимо найти максимальный поток по сети, который равен количеству вещества, вытекающего из истока I.

Где: j – конечные вершины ребер, исходящих из I;

Линейную функцию f называют мощностью потока сети, будем искать ее максимум.

Запишем математическую формулировку (в виде ЗЛП) задачи для условий, изображенных на графе:

Найти максимум целевой функции:

При ограничениях: