Материал: Оптимизация и моделирование в автоматизированных системах

Таблица 1

Исходные данные

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

Полученная матрица представлена в табл. 2. Далее произведем редукцию столбцов - найдем минимальный элемент в каждом столбце, и из каждого элемента столбца вычтем соответствующий минимальный элемент. В итоге в каждом столбце будет хотя бы одна нулевая клетка. Полученная матрица представлена в табл. 3. После чего найдем "оценки" для всех нулевых ячеек матрицы.

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

Выбираем нулевую клетку с наибольшей оценкой (в нашем случае она равна 9,5 и находится в ячейке 1-6). Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какой аптеки к какой движемся, в нашем случае из первой аптеки в шестую). Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно). В итоге получим матрицу, представленную в табл. 4.

240

Таблица 2

Редукция столбцов

Таблица 3

Редукция столбцов

241

Таблица 4

Матрица после нахождения одного из маршрутов

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

На следующем шаге была выбрана нулевая клетка с наибольшей оценкой (в нашем случае она равна 2,6 и находится в ячейке 4-8). Так был найден второй участок маршрута.

В дальнейшем при повторении алгоритма найдена нулевая ячейка - ячейку 5-1. Таким образом, мы нашли третий маршрут. После вычеркивания соответствующих строки и столбца, редукции строк и столбцов, а также поиска оценок нулевых клеток нашли максимальную оценка, находящуюся в ячейке 6- 5. Но путь 6-5 выбирать нельзя, тогда у нас зациклится весь маршрут (5-1-6-5), поэтому в ячейке 6-5 поставим М. Выбираем следующий участок маршрута - ячейка 7-15 с оценкой 1,2. Мы нашли четвертый отрезок (из седьмой аптеки в пятнадцатую). При повторе алгоритма максимальная оценка (1,5) находится в ячейке 15-9. Выбираем следующий отрезок маршрута (из пятнадцатой аптеки в девятую). В дальнейшем был найден маршрут 11-5. Затем определена максимальная оценка (1,6) в ячейке 16-12. Выбираем следующий отрезок маршрута (из шестнадцатой аптеки в двенадцатую). Повторяем алгоритм.

Мы получили две клетки с максимальной оценкой (0,9). Выбираем из них любую - ячейку 6-10. Таким образом, мы нашли еще один участок маршрута (из шестой аптеки в десятую). После вычеркивания соответствующих строки и столбца, редукции строк и столбцов, а также поиска оценок нулевых клеток получили матрицу и рассчитали оценки: максимальная оценка (1,9) находится в ячейке 9-7. Но путь 9-7 выбирать нельзя, тогда у нас зациклится весь маршрут

242

(9-7-15-9), поэтому в ячейке 9-7 поставим М. Выберем следующий участок маршрута с максимальной оценкой - ячейка 10-2 с оценкой 0,9. Мы нашли следующий отрезок (из десятой аптеки во вторую). Повторяем алгоритм.

Максимальная оценка (6,7) находится в ячейке 2-16. Выбираем следующий отрезок маршрута (из второй аптеки в шестнадцатую). На следующем шаге по максимальной оценке (11,6) мы нашли очередной отрезок маршрута - 12-11. Но, к сожалению, он тоже приводит к зацикливанию маршрута (12-11-5-1-6-10- 2-16-12), поэтому выбираем следующую после 11,6 максимальную оценку- 3,8, соответствующую ячейке 9-4 (из девятой аптеки в четвертую). Ячейке 12-11 присваиваем значение М. Аналогично повторяем процедуры алгоритма.

Максимальная оценка (1,6) находится в ячейке 8-11. Выбираем следующий отрезок маршрута (из восьмой аптеки в одиннадцатую). Вычеркиваем соответствующие строку и столбец, редуцируем строки и столбцы и найдем оценки для нулевых клеток. Максимальная оценка (4,7) находится в ячейке 12-7, но при ее выборе произойдет зацикливание маршрута без прохождения 3, 13 и 14 аптеки, поэтому выберем следующую за ней максимальную оценку (0,4), соответствующую ячейке 13-3 (из тринадцатой аптеки в третью). Ячейкам 12-7 и 3 - 13присваиваем значение М. Повторяем алгоритм. По максимальной оценке (0,8) был произведен выбор следующего отрезка маршрута - 14-13. Повторим алгоритм и найдем два заключительных участка маршрута 3-7 и 12-14. Выпи-

шем все отрезки найденные ранее: 1-6, 4-8, 5-1, 7-15, 15-9, 11-5, 16-12, 6-10, 10- 2, 2-16, 9-4, 8-11, 13-3,14-13, 3-7, 12-14. В зависимости от выбора начального пункта объезда аптек, мы получаем следующие варианты маршрутов:

1-6-10-2-16-12-14-13-3-7-15-9-4-8-11-5-1 6-10-2-16-12-14-13-3-7-15-9-4-8-11-5-1-6 10-2-16-12-14-13-3-7-15-9-4-8-11-5-1-6-10

......................................................................

11-5-1-6-10-2-16-12-14-13-3-7-15-9-4-8-11 5-1-6-10-2-16-12-14-13-3-7-15-9-4-8-11-5

Естественно, расстояния этих маршрутов равны и составляют 61 км (исходя из таблицы с исходными данными). Если в зависимости от задач аптечной сети не нужно возвращаться в исходный пункт, то в решении задачи необходимо отбросить последнюю аптеку и выбрать маршрут в зависимости от требований к начальному пункту.

Построим маршрут 1-6-10-2-16-12-14-13-3-7-15-9-4-8-11-5 (Минская,

д.1→пр-т. Ленинский, д.131→пр-т. Московский, д.114→ ул. Невского, д.49→ б-р Победы д.24 →ул. Лизюкова, д.56→ул. Южно-Моравская, д.26→ул. Комарова, д.2→ул. Южно-Моравская, д.54→ ул. Моисеева, д.1 → ул. 20 лет Октя б- ря, д.40 →ул. Моисеева, д.82 →б-р. Пионеров, д.27 →ул. Героев Сибиряков, д.69→ ул. Генерала Лизюкова д.16→ пр-т. Московский, д.24) на карте. Сервис Яндекс.Карты позволяет строить маршрут максимум с десятью пунктами. Поэтому итоговый путь целесообразно отобразить на двух картах (рис. 3 и 4), тем

243

более карты не будут громоздкими, как было бы в случае с построением маршрута с шестнадцатью пунктами.

Рис. 3. Итоговый маршрут

Рис. 4. Итоговый маршрут

Итоговое расстояние (32+22=54км) отличается от 61 километра в связи с тем, что мы в конце маршрут не зациклили, то есть не вернулись назад в исхо д- ный пункт (первая аптека - Минская, д.1). Отличие как раз и составляет расстояние между пятой и первой аптекой.

244