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

Приложение к уроку по теме "Задачи теории расписаний"

Скачать:

ВложениеРазмер
Файл kommivoyazher.docx382.24 КБ

Предварительный просмотр:

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

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

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

7

2

9

7

5

3

9

1

4

8

5

3

5

6

4

7

7

6

3

7

Разместите исходные данные на рабочем листе. Замените знак ∞ числом 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  будет виден порядок его перемещений. Если в ячейке, которая отнесена к организации «В» стоит единица, значит, сотрудник посетил эту организацию следующей за пунктом «А». Если в ячейке ноль – сотрудник организацию не посещал.


По теме: методические разработки, презентации и конспекты

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

Лабораторно-практическая работа по калькуляции и учёту пищевых продуктов и математике. Технологические карты и таблицы  в помощь преподавателю. Исторические сведения о процентах.Методы решения за...

Исследование геометрических моделей. Задача о склеивании коробки. Практическая работа (11 класс)

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

Практические работы по учебной дисциплине МАТЕМАТИКА по теме «Решение текстовых задач с помощью таблицы»

Решение тестовых задач для многих учащихся является трудной практически невозможной работой, т.к. много условий,  непонятно что брать за «Х, У, Z», и уж совсем непонятно как ус...

Практическая работа 11 класс Решение экспериментальных задач по теме "Гидролиз солей"

Практическая работа для учащитхся 11 класса, изучающих химию на профильном уровне...

Практическая работа по теме "Решение экспериментальных задач по теме "Электролитическая диссоциация""

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

Практическая работа «РЕШЕНИЕ ЭКСПЕРИМЕНТАЛЬНЫХ ЗАДАЧ ПО ТЕМЕ «Металлы».

Значительное место в содержании курса отводится химическому эксперименту. Он открывает возможность формировать у учащихся специальные предметные умения работать с веществами, учит школьников безопасно...

Практическая работа Задача «Какие технологии позволяют современным учёным отделять нуклеиновые кислоты от компонентов клетки»10-11 класс

Интересная работа для старшеклассников..Ознакомление с материалом по теме и небольшие задания по этому же тексту.Очень современно.Выполняла эту работу как заключительную на курсах ....