Рис.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 называют мощностью потока сети, будем искать ее максимум.
Запишем математическую формулировку (в виде ЗЛП) задачи для условий, изображенных на графе:
Найти максимум целевой функции:
При ограничениях: