Лабораторная работа. Лабораторная работа №2 нечеткие знания. Лабораторная работа 2 Сравнение метода частичного перебора и алгоритма А при поиске решения
 Скачать 167.42 Kb.
|
|
Лабораторная работа №2 Сравнение метода частичного перебора и алгоритма А* при поиске решения (на примере решения задачи эффективного вложения капитальных вложений (инвестиций) для переустройства участка железной дороги) 1. Описание задачи 2. Постановка задачи. 3. Исходные данные к примеру. 4. Решение задачи методом частичного перебора. 5. Решение задачи с использованием алгоритма А*. 6. Задание на выполнение лабораторной работы. 1. Описание задачи На участке дороги действует ряд ограничений скорости движения поездов. Каждое ограничение скорости приводит к тому, что на проход поезда по участку затрачиваются дополнительное время, топливо (электроэнергия) и эксплуатационные расходы. Соответственно, если устранить эти ограничения, то дорога избавившись от этих дополнительных затрат будет получать доход, равный сумме устраненных расходов. Т.о., чтобы получить максимальный доход (свести дополнительные затраты к нулю) требуется устранить все ограничения скорости. Но так как дорога обладает ограниченными финансовыми возможностями (выделяемым объемом капитальных вложений) одновременное устранение всех ограничений невозможно. Кроме этого, могут быть определены другие требования на выбор мероприятий, направленных на устранение ограничений скорости. Например, срок окупаемости1 плана мероприятий должен быть не менее заданного, подразделения, выполняющие мероприятия, должны освоить определенный минимальный объем капвложений и т.д. 1 Ток = K / C, где Ток - срок окупаемости; K - сумма капвложений по реализуемым мероприятиям; C - сумма дополнительных расходов на передвижение поездов от действия ограничений скорости. 2. Постановка задачи Выбрать мероприятия, направленные на устранение ограничений скорости, чтобы выполнение их набора (плана мероприятий) окупилось в минимально короткий срок (принесло максимальный доход) при безусловном выполнении заданных требований на характеристики плана (решение задачи). 3. Исходные данные к примеру Имеется путь участка между станциями А и Б. В качестве упрощения задачи примем, что по заданному пути участка выполняется ежесуточный пропуск 10 однотипных грузовых поездов (Nпзд = 10 шт.). На пути действует 6 дополнительных ограничений скорости. Скорости движения поезда с учетом и без учета ограничений скорости показаны на следующем рисунке.  Рис.1. Допускаемые скорости и скорости движения поезда Условные обозначения:  - эпюра допускаемой скорости движения поезда без учета дополнительных ограничений; - дополнительные ограничения скорости; - скорость движения поезда без учета дополнительных ограничений; - скорость движения поезда с учетом дополнительных ограничений.Характеристика дополнительных ограничений скорости и соответствующих мероприятий по их устранению приведена в табл.1. Мероприятия отсортированы по сроку окупаемости, т.е. в начале таблицы мероприятия, дающие максимальные эффект (максимальную отдачу от капвложений). Таблица 1 Характеристика дополнительных ограничений скорости и мероприятий
*) Срок окупаемости рассчитывается по формуле Токi = Ki / (365 * Nпзд * Ci) В качестве требований на характеристики плана выступают следующие: - суммарные капвложения не должны превышать 12 000 000 руб.; - ПМС-219 (путевая машинная станция) должна освоить не менее 3 000 000 руб.; - МСО-9 (мостостроительный отряд) должен освоить не менее 4 500 000 руб. Требуется найти такой набор выполняемых мероприятий, чтобы их суммарный срок окупаемости  был минимальным и соблюдались требования (О):O1 - Ki ≤ 12 000 000, i соответствует мероприятиям, включенным в план; O2 - Kpms ≥ 3 000 000, pms соответствует мероприятиям, включенным в план и выполняемыми ПМС-219; O3 - Kmso ≥ 4 500 000, mso соответствует мероприятиям, включенным в план и выполняемыми МСО-9. 4. Решение задачи методом частичного перебора Дерево при поиске решения методом частичного перебора показано на следующем рисунке.  Рис.2. Дерево при поиске решения методом частичного перебора Обход дерева выполняется сверху-вниз слева-направо (поиск в глубину). Каждый узел дерева (за исключение корневого) соответствует набору мероприятий. Mi=1 означает включение i-го мероприятия в план, Mi=0 – невключение. Соответственно план мероприятий для каждого узла включает в себя все мероприятия, для которых Mi=1, начиная с корневого узла и до текущего узла при спуске по стрелкам. Надпись Oj означает несоблюдение j-ого требования. Узлы с зеленым и фиолетовым фоном соответствуют допустимым планам, остальные - недопустимым. Для узлов с красным фоном дальнейшее рассмотрение вариантов плана по ветвям, исходящим из них, не требуется по следующим причинам: - для красных узлов с двойной рамкой - нарушено требование на суммарные капвложения (O1). Добавление мероприятий в такой план приведет к еще большему нарушению этого требования. Несоблюдение требований O2 и O3 (на минимальные суммарные капвложения, осваиваемые конкретными подразделениями) в отличие от требования O1 не означает прекращение поиска решения из конкретного узла; - для красных узлов с одинарной рамкой - значение критерия (срока окупаемости Ток) хуже, чем у уже найденного до него допустимого варианта плана. При дальнейшем поиске решения из этого узла, даже если будет найден новый допустимый вариант плана, значение критерия по нему будет заведомо хуже найденного. Оптимальный план капвложений соответствует узлу с зеленым фоном. Его характеристика: - включает мероприятия 1, 5 и 6; - потребные капвложения менее максимально выделяемого объема 9 000 ≤ 12 000 000; - объем капвложений, осваиваемый ПМС-219 не менее минимально потребного 4 500 000 ≥ 3 000 000; - объем капвложений, осваиваемый МСО-9 не менее минимально потребного 4 500 000 ≥ 4 500 000; - срок окупаемости плана мероприятий Tок = 3,5 года. 5. Решение задачи с использованием алгоритма А* Одним из вариантов решения задачи с использованием алгоритма А* является перебор возможных планов, когда на каждом уровне дерева рассматриваются сочетания мероприятий, выполняемые одним подразделением.  Рис.3. Дерево при поиске решения с использованием алгоритма А* Надписи, цвет фона и тип рамки узлов приняты, как и при решении задачи методом частичного перебора. На 1-ом уровне вариант плана должен обязательно отвечать требованиям O1 и O2, а на 2-ом уровне – всем требованиям. В связи с этим, в узлах, несоответствующих этим требованиям, расчет критерия (срока окупаемости Ток) не выполняется. Зеленым фоном выделен узел, соответствующий оптимальному плану. Как видно результат (план) идентичен полученному с помощью метода частичного перебора и состоит из мероприятий 1, 5 и 6. Если бы из узла 1-ого уровня с мероприятиями 1 и 6 все продолжения вели бы к узлам 2-ого уровня, для каждого из которых не соблюдалось хотя бы одно требование, тогда при поиске решения следовало бы рассмотреть продолжения из следующий по оптимальности узла 1-ого уровня (на рис.3 узел с мероприятиями 1, 3 и 6) и т.д. Следует отметить, что в данном конкретном случае алгоритм А* оказался эффективнее метода частичного перебора (при одинаковом результате потребовалось меньше вычислений). В тоже время, если бы количество мероприятий, выполняемых ПМС-219, было бы не три, а десять, то уже на 1-ом уровне пришлось бы рассматривать 1023 варианта вместо 7. 6. Задание на выполнение лабораторной работы 1) Варианты заданий выбрать согласно таблице 2. Остальные исходные данные принять такими же, как и в рассмотренном выше примере. Таблица 2 Варианты заданий на выполнение лабораторной работы
2) Набор требований на параметры плана принять такой же, как и в рассмотренном выше примере: - суммарные капвложения не должны превышать 12 000 000 руб.; - ПМС-219 (путевая машинная станция) должна освоить не менее 3 000 000 руб.; - МСО-9 (мостостроительный отряд) должен освоить не менее 4 500 000 руб. 3) Определить оптимальный план (набор мероприятий) с помощью метода частичного перебора и алгоритма А*. 4) В отчете должен содержаться следующий материал: - номер варианта; - краткое описание постановки задачи, включая перечень ограничений; - таблица с мероприятиями, отсортированная по сроку окупаемости, аналогичная табл. 1; - полное дерево решений при поиске оптимального плана с помощью метода частичного перебора, аналогичное рис. 2; - полное дерево решений при поиске эффективного плана с использованием алгоритма А*, аналогичное рис. 3; - вывод об эффективности и корректности поиска решения двумя способами. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||