Методические указания
Пусть граф всех возможных маршрутов передвижения между тремя пунктами задан в виде таблицы 4.1.
Таблица 4.1.
Веса рёбер графа |
|||
Вершины |
1 |
2 |
3 |
1 |
|
3 |
5 |
2 |
2 |
|
2 |
3 |
3 |
5 |
|
Взвешенный орграф, соответствующий таблице 4.1, показан на рисунке 1.
Рисунок 1 Взвешенный орграф, соответствующий условиям задачи
Сформируем множество возможных маршрутов по заданному орграфу. Каждый маршрут записывается комбинацией из трёх цифр, каждая из которых лежит в промежутке от 1 до 3 включительно.
Введём в ячейки A2:C2 единицы. Это будет исходная комбинация. В ячейку C3 введём формулу =ЕСЛИ(C2=3;1;C2+1) и скопируем ее во все ячейки этого столбца до ячейки C28 включительно. В ячейку D3 введём формулу =ЕСЛИ(И(C2=3;C3=1);1;0) и скопируем ее во все ячейки этого столбца до ячейки D28 включительно. В ячейку E3 введём формулу =ЕСЛИ(И(B2=3;B3=1);1;0) и скопируем ее во все ячейки этого столбца до ячейки D28 включительно. В ячейку B3 введём формулу =ЕСЛИ(B2+D3=4;1;B2+D3) и скопируем ее во все ячейки этого столбца до ячейки B28 включительно. В ячейку A3 введём формулу =ЕСЛИ(A2+E3=4;1;A2+E3) и скопируем ее во все ячейки этого столбца до ячейки A28 включительно. Таким образом, мы получили полное множество всех возможных маршрутов. Введя необходимые подписи, таблица будет иметь вид, фрагмент которого представлен на рисунке 2.
Рисунок 2 Фрагмент окна MS Excel после получения списка маршрутов
Теперь следует подсчитать стоимость каждого маршрута. Для этого введём данные из таблицы 4.1 в диапазон H10:J12.
Запишем в ячейку F1 слово «Стоимость», а в ячейку F2 введём формулу: =ЕСЛИ(И(A2<>B2;B2<>C2;A2<>C2);ИНДЕКС($H$10:$J$12;A2;B2)+
ИНДЕКС($H$10:$J$12;B2;C2);"").
В виду сложности приведённой формулы поясним её значение. Функция ЕСЛИ используется для проверки допустимости текущего варианта маршрута. Условием допустимости является неравенство номеров вершин, входящих в этот маршрут: И(A2<>B2;B2<>C2;A2<>C2). Если данное условие выполняется, то будет вычислена стоимость маршрута по формуле ИНДЕКС($H$10:$J$12;A2;B2)+ИНДЕКС($H$10:$J$12;B2;C2) которая является суммой цен перемещения между первой и второй а также второй и третьей вершинами маршрута. Функция ИНДЕКС($H$10:$J$12;A2;B2) позволяет получить данные из ячейки, находящейся в диапазоне $H$10:$J$12 (где находятся таблица с условиями задачи), номер строки которой расположен в ячейке A2, а номер столбца – в ячейке B2. аналогично работает функция ИНДЕКС($H$10:$J$12;B2;C2). В случае, если условие И(A2<>B2;B2<>C2;A2<>C2) не выполняется, текущая ячейка останется пустой.
Определим минимальную стоимость маршрута. Для этого введём в ячейку F29 формулу =МИН(F2:F28). Теперь легко определить оптимальный маршрут: он содержится в той строке, значение ячейки из столбца F которой совпадает со значением ячейки F29.
Чтобы повысить наглядность поиска оптимального маршрута применим условное форматирование. Для этого выделим диапазон ячеек F2:F28, выберем пункт меню «Формат»-«Условное форматирование». В появившемся окне укажем условие форматирования «значение равно =$F$29» и стиль форматирования нажав на кнопку «Формат». Например, зададим начертание «полужирный курсив».
После выполнения данной операции в строках с минимальной стоимостью значения стоимости будут выполнены полужирным курсивом. Задача решена.