* Данный текст распознан в автоматическом режиме, поэтому может содержать ошибки

Оптимизация и линейное программирование в системе Mathcad 685 8.12.8. Задача о распределении потоков в сетях В задачах подобного типа требуется найти оптимальный вариант транспортиров ки продукта по сети определенной конфигурации. В этом случае элементы сети имеют следующие характеристики: сij – стоимость транспортировки единицы продукции для ребра сети между вершинами i и j, Dij – пропускная способность этого ребра, в общем случае ограниченная в пределах 0 ? Dij ? ? (если ребро между данными вершинами i и j графа отсутствует, то пропускная способность равна нулю, если поток ничем не ограничен – то бесконечности). Очевидно, что в этом случае должно выполняться требование сохранения потока – суммарного потока, то есть входящий и выходящий из узла потоки должны быть равны. Пусть xij – поток в ребре графа, тогда для промежуточной вершины сети где k – перечисление всех входящих, j – всех исходящих ребер для вершины i. Для потока в любом ребре требуется, чтобы Для начальной и конечной вершин очевидно необходимо выполнение условия где A1 – максимальный выходной поток, создаваемый исходной вершиной сети, необходимо, чтобы он был меньше, чем суммарная пропускная способность всех исходящих из вершины ребер: где Bn – максимальный поток, потребляемый конечной вершиной сети, он также не должен превышать пропускной способности входящих ребер. Возможны различные постановки задачи оптимизации – минимизации стои мости транспортировки и максимизации потока. Получаем соответственно две формулировки математической модели задачи. 1. Минимизация стоимости: – минимизируемая целевая функция – общая стоимость транспортировки. Ограничения: A1 = Bn – поток не может накапливаться в промежуточных вершинах, то есть 0 ? xij ? Dij – по пропускной способности; – сохранение непрерывности потока.