Практическая работа «Задача коммивояжера»
методическая разработка по информатике и икт (11 класс) на тему

Практическая работа «Задача коммивояжера»

«Сотруднику компании ООО «Новые технологии» Петрову Н.И. необходимо обновить

программный продукт автоматизированного учета в пяти организациях: А, Б, В, Г и Д. Он решил начать свой обход с организации «А», так как она находится на первом этаже дома, в котором проживает Петров. Сотруднику необходимо, спланировать свой маршрут таким образом, чтобы к концу рабочего дня обойти все организации в определенном порядке и выполнив свою работу, вернутся домой (в пункт «А»). В каком порядке Петрову следует обходить организации, чтобы его замкнутый тур был кратчайшим?  Расстояния между каждой парой организаций заданы следующей квадратной матрицей (5x5):

Разместите исходные данные на рабочем листе. Замените знак ∞ числом 10000 (на результат решения исключение пути не оказывает влияния).

Введите формулы:

1. Запустите надстройку MS Excel «Поиск решения» и заполните таблицу.

2. Для того чтобы выполнялись условия однократного посещения сотрудником организаций и в то же время запланированный Петровым маршрут был пройден полностью, введите ограничения: в ячейки B9, G4 заводим формулы из таблицы и распространите их на соответствующие диапазоны B9:F9 и G4:G8. Задайте следующие данные $B$9:$F$9=1 и $G$4:$G$8=1 в Ограничения окна «Поиск решения». Таким образом можно отследить порядок обхода организаций сотрудником, оценить правильность выбора и оптимальность его маршрута.

3. Выберите ячейку B19 и устанавливаем ее адрес в Целевую ячейку окна «Поиск решения», чтобы определить длину наикратчайшего маршрута. Для этого в ячейку B19 предварительно заносим соответствующую формулу из таблицы 1. Когда программа «Поиск решения» вычислит оптимальный маршрут Петрова и станет известен порядок обхода организаций (из раздела переменных), будут известны и расстояния между конкретными парами организаций. Затем при помощи простых математических подсчетов программа рассчитает протяженность оптимального маршрута.

4. Установите еще одно ограничение в окно «Поиск решения»: $E$19=0. В указанную ячейку введите формулу из таблицы 1 и исключите, таким образом, заведомо ложный порядок движения Петрова в порядке обхода организаций.

5. В связи с тем, что ячейки диапазона B4:F8 – изменяемые, в Ограничение окна «Поиск

решения» необходимо добавить строку $B$4:$F$8=двоичное.

6. Введите  в ячейки B23; B24; B25; B26 соответствующие формулы из таблицы  и

распространите их на следующие диапазоны: B23:E23; B24:E24; B25:E25; B26:E26 для учета всех возможных вариантов обхода организаций сотрудником и выбора из них оптимального. Формулы задаются таким образом для обеспечения исключения  ложного пути, соблюдая условие задачи об обходе всех организаций по одному разу.

7. Добавьте в Ограничения окна «Поиск решения» $B$23:$E$26 ≤ 3.

Так как это линейная модель, то необходимо фиксировать в окне Параметры поиска решений позицию Линейная модель и Неотрицательные значения. После того, как все поля и ячейки заполнены, нажмите кнопку «Выполнить» и появляется окно диалога с описанием результатов процесса оптимизации. Чтобы отобразить найденное решение в ячейках листа, установите переключатель «Сохранить найденное решение» и нажмите кнопку ОК. Найденная минимальная величина помещается в целевую ячейку, а переменные ячейки заполняются оптимальными значениями переменных, которые удовлетворяют установленным ограничениям.

Таким образом, получите следующий результат. Если Петров переходит из организации в организацию, то в диапазоне B4:F8  будет виден порядок его перемещений. Если в ячейке, которая отнесена к организации «В» стоит единица, значит, сотрудник посетил эту организацию следующей за пунктом «А». Если в ячейке ноль – сотрудник организацию не посещал.