страница - 0
Решение модельных оптимизационных задач на графах средствами Excel
Скороход С.В. (sss64@mail.ru) Таганрогский институт управления и экономики
Постановка задачи
Графовые методы часто используются при решении разнообразных задач как
технического, так и экономического характера [1-3]. При этом граф выступает в роли
модели исследуемого объекта, а решение конкретной задачи сводится к поиску некоторого оптимального подмножества, пути, цикла, подграфа в этом графе.
В теории графов известно большое количество алгоритмов для самых разнообразных задач. Однако для их использования требуется специальное программное обеспечение, разработка которого доступна далеко не каждому пользователю. Возникает вопрос, возможно ли применение для некоторых из них какой-либо широко распространённой системы, не требующей навыков программирования?
В качестве таковой можно использовать Microsoft Excel, имеющий надстройку Поиск решения, которая позволяет находить решение задачи линейного программирования [4, 5]. В этом случае оптимизационная задача на графе должна быть сведена к последней.
В данной работе рассматриваются задачи поиска кратчайшего пути, гамильтонова цикла и наименьшего доминирующего множества графа [1-3], для каждой из них предлагается линейная оптимизационная модель и алгоритм её реализации в Excel.
Поиск кратчайшего пути
задан множеством вершин V={v1,...,vn} и матрицей смежности S=[sij] порядка n, где
Даны две произвольные вершины vHa4 и vKOH из множества V. Необходимо найти кратчайший путь из vHa4 в vKOH, который бы проходил через минимальное количество рёбер графа. Пример кратчайшего пути между вершинами 1 и 6 изображён на рисунке 1 пунктиром.
Введём целочисленные переменные Xj, i = 1, n, j = 1, n ,где
Пусть граф
G=(V, S)
(1)
[1, vi и vj соединены ребром;
в противном случае.
[ 1, кратчайший путь содержит переход из вершины vi в v j ;
0,в противном случае.
1 ,
7
Рисунок 1. Кратчайший путь
Целевая функция имеет следующий вид:
n n
IIsijxij min. i=1 j=1
В ней вычисляется количество переходов между вершинами в кратчайшем пути. Минимизация означает, что решением является путь, содержащий минимальное количество переходов.
Первая пара ограничений задаёт условия для начальной вершины пути \нач. В искомом пути в эту вершину не должно быть входа, но должен быть один выход:
i=1
нач xi нач
j=1
8нач jxнач j = 1-
Вторая пара ограничений задаёт условия для конечной вершины пути хкон. В неё должен быть один вход, но не должно быть выхода:
I si кон xi кон
1. I sкон jxкон j = °-
i=1j=1
Для всех остальных вершин (кроме \нач и укон) устанавливаются ограничения, задающие
равенство количества входов и выходов в каждую из них в искомом кратчайшем пути:
nn
I sikxik - I skjxkj = °, k = 1, n, k * нач, к * кон.
i=1j=1
Для каждой вершины количество входов не должно быть более одного:
n
n
n
Е sikxik < 1, k = 1 n. i=1
Для каждой вершины количество выходов не должно превышать одного:
n
Е skjxkj <1 k =l, n. j=1
Граничные условия устанавливают в качестве области допустимых значений переменных значения 0 или 1:
0 < < 1, i = 1, n, j = 1, n.
Подготовим данные для решения задачи на рабочем листе Excel в соответствии с рисунком 2.
Ячейки B3:I10 содержат матрицу смежности вершин графа, а ячейки B14:I21 -искомые переменные Xj. В ячейки J14:J21 вписываются формулы для вычисления суммы произведений соответствующих строк матрицы смежности и матрицы переменных: СУММПРОИЗВ(В3:13;В14:114) ... СУММПРОИЗВ(В10:110;В21:121). В ячейки B21:I21 вписываются формулы для вычисления суммы произведений соответствующих столбцов этих же матриц: СУММПРОИЗВ(В3:В10;В14:В21) ... СУММПРОИЗВ(13:110;114:121). В ячейку J22 (на рисунке выделена штриховкой) введём формулу для вычисления целевой функции: СУММПРОИЗВ(В3:110;В14:121).
Откроем окно Поиск решения (пункт меню Сервис/Поиск решения) и установим следующие значения.
•Целевая ячейка - J22.
•Равной - минимальному значению.
•Изменяемые ячейки - В14:121.
•Ограничения:
В22 = 0; J14 = 1; G22 = 1; J19 = 0; J15:J18 = C22:F22; J20:J21 = H22:I22; J14:J21 < 1; J14:J21 > 0; В22:Г22 < 1; В22:Г22 > 0; B14:I21 = целое; В14:Г21 > 0; B14:I21 < 1.
•Параметры - линейная модель.
После ввода всех параметров нажатием кнопки Выполнить находим решение. Возможны 2 результата:
•Кратчайший путь существует и найден. Нижняя часть таблицы преобразуется в соответствии с найденным решением. Её вид изображён на рисунке 3. Мы видим, что
содержание:
[стр.Введение] [стр.1] [стр.2] [стр.3]