ЛР № 1. Решение оптимизационной задачи с использованием эвристического алгоритма
 Скачать 295.83 Kb.
|
|
Министерство транспорта Российской Федерации Федеральное агентство железнодорожного транспорта Федеральное государственное бюджетное образовательное учреждение высшего образования «Дальневосточный государственный университет путей сообщения» Кафедра: «Информационные технологии и системы» Лабораторная работа №1 (7) «Решение оптимизационной задачи с использованием эвристического алгоритма» Выполнил: Пильщикова А.П., СО251КОБ Проверил: Прохорец О.В., Ешенко Р.А. Хабаровск, 2022 Цель работы: освоение точного и эвристического методов решения оптимизационной задачи. Между станциями А и Б имеется железнодорожный путь сообщения. На нем действует ряд ограничений скорости движения поездов. Каждое дополнительное ограничение скорости приводит к тому, что на проход поезда по участку затрачиваются дополнительное время, топливо (электроэнергия) и эксплуатационные расходы. Соответственно, если устранить эти ограничения, то дорога будет получать доход, равный сумме затрачиваемых расходов. Для получения максимального дохода (сведения дополнительных затрат к нулю) требуется устранить все ограничения скорости. Но так как дорога обладает ограниченными финансовыми возможностями (выделяемым объемом капитальных вложений), одновременное устранение всех ограничений невозможно. Кроме этого, могут быть определены другие требования на выбор мероприятий, направленных на устранение ограничений скорости. Например: срок окупаемости плана мероприятий должен быть не менее заданного; подразделения, выполняющие мероприятия, должны освоить определенный минимальный объем капвложений и т. д. По железнодорожному пути выполняется ежесуточный пропуск 10 однотипных грузовых поездов (Nгр.п = 10 шт.). На пути действует 6 дополнительных ограничений скорости. Варианты заданий на выполнение лабораторной работы
Набор требований к параметрам плана: суммарные капвложения не должны превышать 12 000 000 руб.; ПМС-219 должна освоить не менее 3 000 000 руб.; МСО-9 должен освоить не менее 4 500 000 руб.
 Описание используемых цветов: розовый: в данных узлах нарушено ограничение О1 (сумма капвложений не более 12 млн), рассмотрение дальнейших решений из данных узлов нецелесообразно, так как будет происходить увеличение суммы капвложений; фиолетовый: в данных узлах период окупаемости Ток больше, чем период, определённый у узла, удовлетворяющего всем трём ограничениям; зелёный: оптимальное решение – данный узел удовлетворяет всем трём ограничениям и имеет наименьший период окупаемости Ток; синий: узел с решением, не являющимся оптимальным, – удовлетворяет всем трём ограничениям, но период окупаемости Ток не минимальный.  Вывод об эффективности и корректности поиска решения двумя способами Характеристика найденного оптимального решения (плана) включает: мероприятия 5,2 и 1,6; потребные капвложения менее максимально выделяемого объема 11 698 250 ≤ 12 000 000; объем капвложений, осваиваемых ПМС-219, не менее минимально потребного 5 931 250 ≥ 3 000 000; объем капвложений, осваиваемых МСО-9, не менее минимально потребного 5 767 000 ≥ 4 500 000; срок окупаемости плана мероприятий Tок = 2,9 лет. Оба метода выявили одинаковые решения поставленной задачи – мероприятия 5,2 и 1,6, при этом решение эвристическим методом А* занимает значительно меньше вычислительных и временных ресурсов, чем метод частичного перебора. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||