Методические указания к выполнению лабораторной работы № 6

На заданной сети указаны пропускные способности ребер. Предполагается, что пропускные способности в обоих направлениях одинаковы. Построить поток максимальной мощности на заданной сети, выделить насыщенные ребра. Найти разрез минимальной пропускной способности и проанализировать возможность получения дополнительной прибыли от увеличения максимального потока.

Пример. На рисунке 1 задана сеть и пропускные способности дуг.

Рис.1

Стрелки показывают, что из вершины 1 (истока) поток только выходит, а в вершину 6 (сток) только входит. Отсутствие стрелки, например, на ребре (2;4) говорит о том, что пропускные способности в обоих направлениях равны.

Представим условия задачи в виде таблицы.

Таб.1

	Узел 1	Узел 2	Узел 3	Узел 4	Узел 5	Узел 6
Узел 1
Узел 2
Узел 3
Узел 4
Узел 5
Узел 6

Ввод данных в Excel состоит из следующих шагов.

1)Введем матрицу пропускных способностей. Так как в первый узел поток не поступает, то все значения пропускных способностей в первом столбце равны нулю. Поэтому первый столбец таблицы 1 вводить не будем. Т.к. из шестого узла поток не выходит, то лучше не вводить последнюю строку таблицы 1. Все ячейки с ненулевыми пропускными способностями желательно выделить одним цветом, это позволит в дальнейшем легко выделить насыщенные дуги. Копируем матрицу два раза, оставляя ниже второй матрицы 2 свободные строки. (Рис.2)

Рис.2

Введем формулу разности матрицы пропускных способностей и матрицы потоков.

· Выделим ячейки B27:F31.

· Вводим знак «=».

· Выделяем ячейки B6:F10.

· Вводим знак «–».

· Выделяем ячейки B15:F19.

· Нажимаем клавиши Ctrl + Shift + Enter.

· Во всех ячейках последней матрицы должны появиться нули.

Математическая модель рассматриваемой задачи имеет вид:

– поток, поступающий в вершину n (сток),

равен потоку, выходящему из вершины 1

(истока).

(1) – поток по каждой дуге не превосходит

пропускной способности этой дуги,

(2) – условие сохранения потока в узлах: для всех узлов кроме истока и стока суммарная величина входящих потоков равна суммарной величине выходящих потоков.

Просуммируем мощности входящих (по столбцам) и выходящих (по строкам) потоков для всех узлов.

· Выделяем ячейки B15:F19.

· Нажимаем знак на верхней панели.

· Если этот способ не проходит, суммируем значения ячеек B15:В19 и используем процедуру Автозаполнения.

· Помещаем курсор в ячейку G15.

· Нажимаем знак на верхней панели.

· Выделяем ячейки В15:F15.

· Нажимаем Enter.

· Остальные строки суммируем с помощью процедуры Автозаполнения.

· Ячейку G15 выделим рамкой или цветом. В ней будет находиться значение целевой функции. (Рис.3)

Рис.3

Выбираем Сервис – Поиск решения. Вводим ограничения (1) и (2) (Рис.4), в окне Параметры отмечаем Линейная модель и Неотрицательные значения, нажимаем Выполнить.