Расчет максимального потока в сети

Расчет максимального потока в сети в MathCad

Поток — это некая информация, передаваемая по дугам в сети.

Предположим, что эта информация имеет количественное измерение, тогда вес дугиэто максимальное количество информации, которое можно передать по дуге (пропускная способность), если ввести обозначение для рисунка 1:

Хi — величина потока по i-ой дуге.

Получим ограничения пропускной способности:

Будем считать, что весь поток, входящий в узел, равен потоку, исходящему из узла.

Получим ограничения на отсутствие задержек потока в узлах:

Величину в стоке сети можно вычислить:

где Х — вектор потока по каждой дуге.

Отсюда задача линейной оптимизации:

Вектор решения R определяет, что по дуге х1 необходимо пропустить поток величиной «3», по дуге x9 — «1», по x3 — «1» и так далее. При этом величина максимального потока = 18. Точка «А» является источником, «C» — стоком сети.

Графическая интерпретация решения (выделены дуги, переносящие максимальный поток):

Расчет максимального потока в сети в Excel

Подготовка бланка решения:

Подготовка бланка решения (в режиме формул):

СУММПРОИЗВ:

Перемножает соответствующие элементы заданных массивов и возвращает сумму произведений.

СУММПРОИЗВ (массив1;массив2;массив3; …).

Массив1, массив2, массив3,… — от 2 до 255 массивов, компоненты которых нужно перемножить, а затем сложить результаты.

Замечания:

Аргументы, которые являются массивами, должны иметь одинаковые размерности. В противном случае функция СУММПРОИЗВ возвращает значение ошибки #ЗНАЧ!

Функция СУММПРОИЗВ трактует нечисловые элементы массивов как нулевые.

Использование массивов дает более общее средство для выполнения действий, подобных функции СУММПРОИЗВ.

Заполнение параметров поиска решений:

Устанавливаем соответствующие параметры:

Нажимаем OK > Выполнить > Сохранить найденное решение > OK.

Результат: