Ограничениями задачи ЛП будут уравнения баланса входного и выходного потоков для каждого узла. Целевая функция максимизирует или величину общего потока, "выходящего" из начального узла, или величину общего потока, "входящего" в конечный узел.
Пример 6.4.3
В задаче вычисления максимального потока в сети, показанной на рис. 6.29 (пример 6.4.2), s=l и f=5. В следующей таблице приведена соответствующая задача ЛП с двумя различными целевыми функциями, одна из которых максимизирует поток, выходящий из узла 1 (функция zt), вторая максимизирует поток, входящий в узел 5 (функция гг).
| | | | | | | | |
Максимизировать Z\ 1 Максимизировать z2 | | | | | | | | |
Узел 2 1 УзелЗ Узел 4 | | | -1 1 | | -1 1 | | | ii ii ii |
Пропускная способность 20 | | | | | | | | |
Оптимальное решение этой задачи ЛП с использованием любой целевой функции составляют х12 = 20, хп = 30, х14=10, х25 = 20, х34=10, хзъ = 20, х45 = 20. Максимальный поток равен гх - г2 = 60. |
УПРАЖНЕНИЯ 6.4.3
1. Решите задачу из упражнения 6.4.2.2 как задачу линейного программирования.
2. Решите задачу из упражнения 6.4.2.5 как задачу линейного программирования.
6.4.4. Решение задачи определения максимального потока в Excel
Шаблон Excel, предназначенный для решения общей транспортной задачи (см. раздел 5.3.3), можно немного модифицировать, чтобы найти максимальный поток. Максимальный размер сети - 10 узлов. На рис. 6.35 показан рабочий лист, на котором решается задача из примера 6.4.2 (файл ch6SolverMaxFlow.xls). Матрица пропускных способностей записана в диапазоне В6:К15.4 Незаполненные ячейки матрицы пропускных способностей показывают, что соответствующие дуги имеют бесконечную пропускную способность. Нулевое значение пропускных способностей вводится для несуществующих дуг.
После того как будут введены значения пропускных способностей, рабочий лист пе-ресчитывается автоматически. Выделенные столбцы В, С, F и G содержат исходные данные задачи, необходимые для использования средства Поиск решения. Диапазон В20:В39 (изменяемые ячейки для средства Поиск решения) содержит величины потоков, проходящие по каждой дуге. Столбец С содержит значение пропускных способ-
4 На рис. 6.35 строки от 11 до 16 скрыты для экономии места.
ностей дуг (диапазон С20:С39). Все эти вычисления выполняются автоматически. Все, что необходимо сделать вам для решения задачи, - это указать диапазон изменяемых ячеек и задать ограничения в диалоговом окне средства Поиск решения. На рис. 6.35 видно, что изменяемые ячейки составляют диапазон В20:В39, а ограничения задаются как F20:F22=G20:G22 (баланс потоков для узлов 2, 3 и 4) и В20:В39<=С20:С39 (ограничения пропускных способностей дуг). Отметим, что целевая ячейка устанавливается автоматически и ее не надо изменять. Следует установить переключатель Равной максимальному значению, поскольку решается задача максимизации.
Задача нахождения максимального йотой»
Входные данные
| Матрица пропускных способностей , стые ячейки=Сесконечность |
| | | | Ш N5 | | | | |
| | | | 10 0 | | | | |
| | | | 0~~\ 30 | | | | |
| | | | Г10 j 20 | | | | |
| | | | ° -4 20 | | | | |
| 0 " | "о : о~" | 0 0 | | | | |
17 Оптимальное решение
i Общая стоимость : 60
От-в
N1 -N2 N1 -N3 N1-N4 N1 -N5 N2-N1 N2-N3 N2-N4 N2-N5 N3-N1 N3-N2 N3-N4 N3-N5 N"-N1
Поток
20 30 10 0 0 0 0 20 0 0 10 20 0
П: сп0с
20 30 10
40 0 30
10 20 0
Промежуточные ычиелонии
Имя Узел Поток Спрос От В Единичный поток
N1 К
N2 Я
N3 Т а
N4 1 4
N5 1 Sl -60
о о о
1 1 1 1
2 2 2 2 3
3 2 3 4
4 1 4 2
2 1
3! 1
3 4 5 1
Поиск решении
Установить целевую ячейку: Равной: <? детальному значению
г медиальному значению Имняя ячейки
Значению: (Г
Вьполнить ) Закрыть
ftB$20-$8$39 Ограничения:
$8$20,$В$39 <= $С$20:$С$Э9 tF$20:tFt22 = $GJ20:$G$22
Гзедполщкить
Добавить Изменить {
Параметры
Удалить
Восстановить Слравка
Рис. 6.35. Определение максимального потока в Excel
Решение N1-N2 = 20, Nl-N3 = 30, N1-N4 = 10, N2-N5 = 20, N3-N4=10, N3-N5 = 20 и N4-N5 = 20, показанное на рис. 6.35, дает максимальный поток, равный 60 единицам.
УПРАЖНЕНИЯ 6.4.4
1. Решите задачу из упражнения 6.4.2.2 с помощью средства Поиск решения.
2. Решите задачу из упражнения 6.4.2.5 с помощью средства Поиск решения.
Задача нахождения потока наименьшей стоимости в сети с ограниченной пропускной способностью обобщает задачу определения максимального потока по следующим направлениям.
1. Каждой дуге поставлена в соответствие (неотрицательная) стоимость прохождения единицы потока по данной дуге.
2. Дуги могут иметь положительную нижнюю границу пропускной способности.
3. Любой узел сети может выступать в качестве как источника, так и стока.
В рассматриваемой задаче необходимо найти потоки по дугам, минимизирующие общую стоимость прохождения потока по сети; при этом должны удовлетворяться ограничения на пропускные способности дуг и на величины предложений и спроса отдельных (или всех) узлов. Сначала опишем сетевую модель с заданными стоимостями прохождения потока по дугам и сформулируем соответствующую задачу линейного программирования. Эта задача далее будет использована как основа для построения специального симплексного алгоритма, предназначенного для решения данной сетевой задачи.
6.5.1. Сетевая модель
Рассмотрим сеть G = (N, А) с ограниченной пропускной способностью, где N - множество узлов, А - множество дуг. Обозначим
xtj - величина потока, протекающего от узла i к узлу у,
ц,. (?,.) - верхняя (нижняя) граница пропускной способности дуги (i, j),
ctj - стоимость прохождения единицы потока по дуге (t, j),
f. - величина "чистого" результирующего потока, протекающего через узел i.
На рис. 6.36 показано, как на схемах сетей будем отображать определенные параметры дуг. Метка [/,] указывает положительное (отрицательное) значение предложения (спроса), соответствующего узлу i.
6.5. ЗАДАЧА НАХОЖДЕНИЯ ПОТОКА НАИМЕНЬШЕЙ СТОИМОСТИ
if -IJ-
Рис. 6.36. Обозначение параметров дуг