Задание к контрольной работе. Цель контрольной работы: научиться на практике применять знания и навыки решения оптимизационных задач

Цель контрольной работы: научиться на практике применять знания и навыки решения оптимизационных задач, полученные при прохождении курса дисциплины «Логистика», на примере «Travelling salesman problem» («Задача коммивояжера»).

Структура контрольной работы:

1. Титульный лист (1 стр.).

2. Бланк рецензии (1 стр.).

3. Введение (1 стр.).

4. Исходные данные – матрица цен и скриншоты (2-3 стр.).

5. Произвольный вариант маршрута – описание, граф, расчет стоимости (1 стр.).

6. Вычисленный вариант маршрута – ход решения, граф, общая стоимость (2-3 стр.).

7. Вывод (1 стр.).

Содержание контрольной работы: следуйте приведенным ниже рекомендациям при решении контрольной работы:

1. Напишите к контрольной работе введение, в котором кратко обозначьте ее цель, задачи, актуальность.

2. В таблице с исходными данными найдите те, что соответствуют Вашему варианту. Это будут названия семи городов мира, один из них (начальная и конечная точка пути) одинаков для всех – Москва. Моделируемая ситуация – туристическое путешествие по этим городам.

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

Перелеты из города в этот же город, обозначим символом «M», как нецелесообразные.

Обратите внимание, что цены на билеты одного направления, но разных авиакомпаний будут отличаться. Поэтому в матрицу цен вносите либо средние значения, либо стоимость самого дешевого билета (рассматриваем эконом-класс).

Сделайте выборочные скриншоты веб-страниц с ценой на билеты любых 5-7 направлений (например: Москва - Париж, Пекин – Дели, и т.д.). Добавьте эти скриншоты в контрольную работу.

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

Опишите последовательность перелетов, рассчитайте стоимость всего маршрута.

5. Решите задачу коммивояжера о нахождении (в данном случае) самого дешевого маршрута на основе данных Вашей матрицы цен. Отразите основные этапы решения в контрольной работе. Постройте граф найденного маршрута, рассчитайте его общую стоимость.

6. Сделайте вывод. Сравните первый маршрут, составленный по наитию, и второй – найденный в рамках решения задачи коммивояжера. Оказался ли второй маршрут дешевле? Если да, то какую сумму позволило сэкономить применение данной оптимизационной задачи логистики?

Также подумайте, какие могут быть недостатки у второго оптимального маршрута? Какие факторы не были учтены при решении задачи о нахождении самого дешевого маршрута?

Изложите Ваши выводы, наблюдения и предложения в контрольной работе.

ВАРИАНТЫ ИСХОДНЫХ ДАННЫХ

* Сидней (Австралия)