3. Расчет максимального потока в сети.
3.1 Расчет максимального потока в сети в MathCad.
Поток – это некая информация, передаваемая по дугам в сети.
Предположим, что эта информация имеет количественное измерение, тогда вес дуги– это пропускная способность дуги (то есть максимальное количество информации, которое можно передать по дуге), если ввести обозначение для рисунка 1:
Хi – величина потока по i-й дуге
Рис. 1
Получим ограничения пропускной способности:
Считаем, что весь поток, входящий в узел, равен потоку, исходящему из узла.
Получим ограничения на отсутствие задержек потока в узлах:
Величину в стоке сети можно вычислить как:
, где Х – вектор потока по каждой
дуге.
Получаем задачу линейной оптимизации:
Вектор решения R определяет, что по дуге х1 необходимо пропустить поток величиной «1», по дуге x2 – «3», по x3 – «3» и так далее. При этом величина максимального потока = 9. Точка «А» является источником, «F» - стоком сети.
Графическая интерпретация решения (выделены дуги, переносящие максимальный поток):
3.2. Расчет максимального потока в сети в Excel.
Подготовка бланка решения:
Подготовка бланка решения (в режиме формул):
СУММПРОИЗВ:
Перемножает соответствующие элементы заданных массивов и возвращает сумму произведений.
СУММПРОИЗВ (массив1;массив2;массив3; ...)
Массив1, массив2, массив3,... — от 2 до 255 массивов, компоненты которых нужно перемножить, а затем сложить результаты.
Замечания:
Аргументы, которые являются массивами, должны иметь одинаковые размерности. В противном случае функция СУММПРОИЗВ возвращает значение ошибки #ЗНАЧ!.
Функция СУММПРОИЗВ трактует нечисловые элементы массивов как нулевые.
Использование массивов дает более общее средство для выполнения действий, подобных функции СУММПРОИЗВ.
Заполнение параметров поиска решений:
Устанавливаем соответствующие параметры:
Нажимаем OK → Выполнить → Сохранить найденное решение → OK
Результат:
4. Поиск минимального пути от источника к стоку сети.
4.1 Поиск минимального пути от источника к стоку сети в MatCad.
Если вес дуги трактовать, как стоимость перевозки по этой дуге, то можно поставить задачу по нахождению пути, который обеспечит минимальную стоимость перевозки по сети.
Вес, данный каждой дуге, будем трактовать, как длину дуги.
Будем считать, что весь поток, входящий в узел, равен потоку, исходящий из узла. Получим ограничение на отсутствие задержки потока в узлах:
Длину можно вычислить как:
Получим задачу линейной оптимизации:
Вектор решения R определяет, какие дуги задействованы в минимальном пути. 1 – задействована, 0 – не задействована. При этом величина минимального пути = 5.
На приведенной ниже графической интерпретации видно, что найденный минимальный путь является единственным равным длине 5:
