Решение задачи о максимальном потоке в среде MS Excel

Рассмотрим задачу нахождения максимального поток в сети, которая представляет модель системы магистральных трубопроводов, связывающих источник добычи некоторого жидкого продукта (нефти, сжиженного газа) с предприятием по его промышленной переработке. Данная модель может быть представлена в виде схемы, формально представляющая собой ориентированный граф без циклов, состоящий из 6 вершин и 10 дуг (рис. 15.2). Предельные значения пропускной способности каждого участка рассматриваемой системы между двумя соседними компрессорными станциями, выраженные например в т/час, равны значению весовой функции для каждой дуги, которые указаны рядом с изображением этой дуги в графе.

В предположении, что источник, которому соответствует вершина v₁=v_s, обладает достаточными запасами продукта, требуется определить количество транспортируемого продукта по каждому из участков трубопроводной системы до стока, которому соответствует вершина v₆=v_t, так чтобы количество доставленного на сток продукта было максимальным.

Рис.15.2. Исходный ориентированный граф индивидуальной задачи о

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

Переменными математической модели данной индивидуальной задачи о максимальном потоке в сети являются 10 переменных: x₁₂, x₁₃, x₂₃, x₂₄, x₂₅, x₃₄, x₃₅, x₄₅, x₄₆, x₅₆. Каждая из этих переменных x_ij может принимать неотрицательные целочисленное значение, не превышающее пропускной способности дуги c_ij и соответствующее величине потока продукта, транспортируемого по отдельному трубопроводу, связывающему компрессорные станции – вершины сети. Тогда математическая постановка рассматриваемой индивидуальной задачи о максимальном потоке в сети может быть записана в следующем виде:

(15.5)

где множество допустимых альтернатив формируется следующей системой ограничений типа равенств и неравенств:

(15.6)

Заметим, что те переменные x_ij, для которых весовая функция дуг h не определена или равна 0, не входят в математическую постановку рассматриваемой задачи (15.5) - (15.6).

Для решения поставленной задачи воспользуемся программой электронных таблиц MS Excel – компонентом офисного пакета MS System Office. MS Excel позволяет выполнять быстрые расчеты и содержит встроенные средства для решения задач оптимизации. Также имеющиеся возможности MS Excel могут быть расширены за счет использования встроенного языка программирования VBA или вызова внешних функций из библиотек динамической компоновки, разработанных самим пользователем на таких языках программирования как Borland Delphi^® и MS Visual C++^®.

Для решения поставленной индивидуальной задачи нахождения максимального потока в сети с помощью программы MS Excel необходимо выполнить следующие действия.

1. Создать в книге «Оптимизация на графах» новый рабочий лист с именем «Максимальный поток».

2. Ввести необходимые надписи в ячейки A1:F1 (рис. 15.3). Конкретное содержание этих надписей не оказывает влияния на решение рассматриваемой задачи.

3. В ячейки A2:A11 ввести индексы начальных вершин, а в ячейки B2:B11 – индексы конечных вершин всех имеющихся дуг исходного графа.

4. В ячейки C2:C11 ввести значения пропускных способностей дуг исходного графа.

5. В ячейку F2 ввести формулу: =СУММ(D2:D3), которая представляет целевую функцию (15.5).

6. В ячейку E2 ввести формулу: =СУММ(D2:D3)-СУММ(D10:D11), которая представляет собой левую часть первого ограничения (15.6).

7. В ячейку E3 ввести значение левой части второго ограничения: D2-СУММ(D4: D6).

8. В ячейку E4 ввести значение левой части третьего ограничения: D3-СУММ(D7: D8).

9. В ячейку E5 ввести значение левой части четвертого ограничения: СУММ(D5; D7)-СУММ(D9: D10).

10. В ячейку E6 ввести значение левой части пятого ограничения: СУММ(D6; D8:D9)-D11.

Внешний вид рабочего листа с исходными данными для решения задачи о минимальном пути в графе имеет следующий вид (рис 15. 3).

Рис. 15.3. Исходные данные для решения задачи о максимальном потоке в сети

Для дальнейшего решения задачи следует вызвать мастер поиска решений для чего необходимо выполнить операцию главного меню: Сервис | Поиск решения.

После появления диалогового окна Поиск решения следует выполнить следующие действия:

1. В поле с именем Установить целевую ячейку: ввести абсолютный адрес ячейки $F$2.

2. Для группы Равной: выбрать вариант поиска решения – максимальному значению.

3. В поле с именем Изменяя ячейки: ввести абсолютный адрес ячеек $D$2:$D$11.

4. Задать первых 5 ограничений для рассматриваемой задачи. С этой целью выполнить следующие действия:

· для задания этих ограничений в исходном диалоговом окне Поиск решения нажать кнопку с надписью Добавить;

· в появившемся дополнительном окне выбрать диапазон ячеек $E$2:$E$11, который должен отобразиться в поле с именем Ссылка на ячейку;

· в качестве знака ограничения из выпадающего списка выбрать равенство «=»;

· в качестве значения правой части ограничения ввести с клавиатуры значение 0;

· для добавления первого ограничения в дополнительном окне нажать кнопку с надписью Добавить.

5. Задать первое из 10 ограничений на пропускные способности дуг (15.6). С этой целью выполнить следующие действия:

· Для задания ограничения в исходном диалоговом окне Поиск решения нажать кнопку с надписью Добавить;

· В появившемся дополнительном окне выбрать ячейку $D$2, которая должна отобразиться в поле с именем Ссылка на ячейку;

· В качестве знака ограничения из выпадающего спуска выбрать нестрогое неравенство «<=».

· В качестве значения правой части ограничения в появившемся дополнительном окне выбрать ячейку $C$2, которая должна отобразиться в поле с именем Ссылка на ячейку;

· Для добавления первого ограничения в дополнительном окне нажать кнопку с надписью Добавить.

6. Аналогичным образом добавить остальные 9 ограничений (15.6), используя в качестве исходных ячеек $D$3: $D$11 и $C$3:$C$11.

7. Задать ограничение на целочисленные значения переменных. С этой целью выполнить следующие действия:

· В исходном диалоговом окне Поиск решения нажать кнопку с надписью Добавить;

· В появившемся дополнительном окне выбрать диапазон ячеек $D$2:$D$11, который должен отобразиться в поле с именем Ссылка на ячейку;

· В качестве знака ограничения из выпадающего списка выбрать строку «цел»;

· В качестве значения правой части ограничения в поле с именем Ограничение: оставить без изменения вставленное программой значение «целочисленные»;

· Для добавления первого ограничения в дополнительном окне нажать кнопку с надписью Добавить.

8. В окне дополнительных параметров поиска решения выбрать отметки Линейная модель и Неотрицательные значения.

Общий вид диалогового окна спецификации параметров мастера поиска решения показан на рис. 15.4.

Рис. 15.4. Ограничения значений переменных и параметры мастера поиска решения для задачи о максимальном потоке в сети

Рис. 15.5. Результат количественного решения задачи о максимальном

потоке в сети

После задания ограничений и целевой функции можно приступить к поиску численного решения, для чего следует нажать кнопку Выполнить. После выполнения расчетов программой MS Excel будет получено количественное решение, которое имеет следующий вид (рис. 15.5).

Результатом решения задачи о максимальном потоке в сети являются найденные оптимальные значения переменных: , , , , , , , , остальные переменные равны 0. найденному оптимальному решению соответствует значение целевой функции: .

Анализ найденного решения показывает, что максимальный поток в сети (рис. 15.2), проходящий из вершины 1 в вершину 6, протекает по следующим дугам: по дуге (1, 2) в количестве 2 т/час, по дуге (1, 3) в количестве 4 т/час, по дуге (2, 4) в количестве 2 т/час, по дуге (3, 4) в количестве 3 т/час, по дуге (3, 5) в количестве 1 т/час, по дуге (4, 5) в количестве 2 т/час, по дуге (4, 6) в количестве 3 т/час, по дуге (5, 6) в количестве 3 т/час.

Тем самым найден оптимальный план транспортировки продукта от пункта добычи до пункта переработки (рис. 15.6). При этом общая величина потока транспортируемого продукта для рассматриваемой сети будет максимальна и равна 6 т/час.

Рис. 15.6. Минимальный поток в исходной сети между вершинами 1 и 6.

Простейшая проверка найденного решения может быть связана с рассмотрением так называемых разрезов графа сети (рис. 15.6). Разрезом сети называется множество, которому принадлежит исток, и не принадлежит сток. Т.е. разрез - это минимальное (в смысле отношения включения) множество дуг, удаление которых “ разрывает” все пути, соединяющие исток и сток.

Пропускной способностью разреза называется число, равное сумме пропускных способностей дуг этого разреза. Разрез называется минимальным, если имеет наименьшую пропускную способность.

Например, применительно к найденному решению задачи о максимальном потоке в сети (рис. 15.6) множество дуг удовлетворяет определению минимального разреза и его пропускная способность равна 6, что в точности равно величине найденного максимального потока. Для дополнительной проверки получаемых с помощью программы MS Excel решений данной типовой задачи оптимизации на графах можно воспользоваться специальным алгоритмом пометок Форда - Фалкерсона.

Контрольные вопросы

1. В чем состоит особенность задач оптимизации на графах?

2. Приведите типовые примеры задач оптимизации на графах.

3. Приведите содержательную постановку задачи о максимальном потоке в сети.

4. Дать общую постановку задач оптимизации на графах.

5. Приведите математическую постановку задачи о максимальном потоке.

6. К какой из задач математического программирования сводится задача о максимальном потоке.

7. Приведите порядок действий при решении задачи о максимальном потоке в среде MS Office.

8. Опишите понятие разреза сети и его свойства.

9. Дайте определение понятию минимального разреза.

10. Использование какого метода решения задачи о максимальном потоке позволяет проверить решение данной задачи с помощью встроенных средств MS Excel.