Методические указания для практических работ по дисциплине «Основы моделирования управленческих задач»



Дата26.06.2016
Размер87.4 Kb.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Кафедра «Управление качеством»

АЛГОРИТМ СЛУЧАЙНОГО ПОИСКА РЕШЕНИЙ


Методические указания для практических работ

по дисциплине «Основы моделирования управленческих задач»


Ростов-на-Дону

2013

Составители: Димитров В.П., Катаев В.С.



УДК 004.94

Алгоритм случайного поиска решений. Методические указания к практическим работам по дисциплине "Основы моделирования управленческих задач"/Ростов н/Д: Издательский центр ДГТУ, 2013. - 8 с.


Методические указания предназначены для проведения практических работ со студентами, обучающихся по направлению 221400 «Управление качеством». Приводится методика оптимизации целевой функции при решении трудноформализуемых задач принятия решения. Приводятся индивидуальные задания и методика решения задач.
Печатается по решению методической комиссии факультета «Приборостроение и техническое регулирование»
Научный редактор:

кандидат технических наук профессор Ананченко В.Н.


Редактор


В набор

В печать Офсет. Бумага тип №3.

Формат 6084/16. Объем 0,5 усл. п.л., уч.-изд.л.

Заказ № Тираж. Цена


Издательский центр ДГТУ.

Адрес университета и полиграфического предприятия:

344010, Ростов-на-Дону, пл. Гагарина, 1.



  • Издательский центр ДГТУ, 2013

  • Димитров В.П., Катаев В.С. 2013



ВВЕДЕНИЕ

Целью работы является приобретение навыков использования алгоритма случайного поиска, для решения трудноформализуемых задач принятия решения

Задачи. Приобрести навыки оптимизации целевой функции с использованием алгоритма случайного поиска решений.
1 АЛГОРИТМ СЛУЧАЙНОГО ПОИСКА РЕШЕНИЙ
Алгоритм случайного поиска решений целесообразно использовать при решении трудноформализуемых задач принятия решения, когда построение математической модели зависимости целевой функции от переменных факторов затруднено или невозможно.

Алгоритм включает следующие этапы:

Этап 1. Создать начальное решение.

Начальное решение создаётся различными методами, в зависимости от конкретной задачи принятия решения. Начальное решение является "отправной точкой" исследования области поиска решения.

Этап 2. Оценить результат.

Каждое решение характеризуется некоторым значением целевой функции, т.е. функции, которая определяет привлекательность решения. Целевая функция должна иметь количественное выражение. Определение целевой функции осуществляется либо путём "прямого" её измерения, либо посредством заранее разработанных критериев. Целевая функция может представлять собой различные затраты (труда, времени, финансов), потери и т.д.

Этап 3. Изменить случайным образом решение

Случайное изменение решения – основной инструмент алгоритма случайного поиска.

Результатом начального решения является набор предположительно оптимальных значений параметров управляемой системы , то есть некоторая точка , в которой значение целевой функции . Тогда можно предположить, что искомый минимум (максимум) целевой функции лежит в некоторой области D, ограниченной n-мерным параллелепипедом, границы которого равны . Где – это некоторая константа, определяющая ширину интервала варьирования значений параметра n (рисунок 1).

Рисунок 1 – Область поиска оптимального значения

целевой функции

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

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

Этап 4. Критерий допуска.

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

После оценки нового решения, возможны два варианта:

- новое решение предпочтительное предыдущего;

- новое решение хуже предыдущего.

В первом случае, решение сохраняется и этап 3 повторяется с этим решением в качестве начального.

Если новое решение хуже начального, то его возможно отбросить, или ввести критерий допуска. Если худшее решение отбросить, то выполнение алгоритма займёт меньше времени, однако область поиска решения будет исследована в меньшей степени. Если использовать критерий допуска, то худшее решение может быть принято с вероятностью:



где ΔF – это разность значений целевой функции нового и начального решений, – это значение, определяющее «ширину» области поиска решений:



Затем значение вероятности допуска сравнивается с константой β, заданной на интервале от 0 до 1. Чем данная константа ближе к 1, тем меньше вероятность принятия худшего решения, и, следовательно, область поиска лучшего решения.

Если полученный результат больше β, то решение принимается, если меньше – отбрасывается.

При больших значениях T, плохие решения принимаются чаще, чем отбрасываются. При уменьшении T, вероятность принятия худшего решения также снижается.

При использовании критерия допуска, осуществляется сужение поиска области решения после выполнения m числа итераций. Сужение осуществляется путём уменьшения значения Т

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

Этап 5. Завершение алгоритма, выбор лучшего решения.

Прекращение алгоритма осуществляется либо после выполнения m итераций, либо после того как k раз не удаётся обнаружить лучшее решение.

После завершения алгоритма, в качестве окончательного решения выбирается то, при котором значение целевой функции минимально (максимально).
2 МОДЕЛЬНЫЙ ПРИМЕР
Рассмотрим возможность использования алгоритма случайного поиска решения для выбора значений параметров молотильно-сепарирующего устройства (МСУ) зерноуборочного комбайна, обеспечивающих наименьший процент потерь.

Показателем качества работы данной системы является процент потерь зерна. Целевая функция (процент потерь зерна) складывается из потерь свободным зерном в полове , свободным зерном в соломе , потерь недомолотом в соломе и полове и дроблением зерна .





, в свою очередь, складываются из потерь щуплым зерном и полновесным зерном

Тогда целевая функция определяется выражением:



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

Влияние на целевую функцию возможно за счёт изменения следующих регулируемых параметров МСУ:

- частоты вращения молотильного барабана х1,

- зазора барабан-дека (на выходе) х2;

- раствор жалюзи верхнего решета х3;

- раствор жалюзи нижнего решета х4;

- раствор жалюзи удлинителя верхнего решета х5;

- частота вращения вентилятора очистки х6;

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

ставляющих целевой функций определяется уравнениями (все значения и зависимости служат для иллюстрации примера и не описывают реальную работу МСУ):



Пусть в результате предварительной настройки МСУ были установлены следующие значения параметров х1 = 800 мин-1; х2 = 8 мм; х3 = 10 мм; х4 = 6 мм; х5 = 10 мм; х6 = 750 мин-1

Минимальный шаг изменения значений параметров МСУ, при котором можно фиксировать изменение целевой функции примем: для х1, х6 = 10 мин-1; для х2 – х5 = 2 мм.

За примем 100 мин-1, а за – 6 мм. Тогда Границы интервалов варьирования факторов будут иметь вид: для х1 (700;900) мин-1, а для х2 (2;14) мм, х3 (4;16) мм, х4 (0;12) мм, х5 (4;16) мм, х6 (650;850) мин-1.

Оценим начальное решение . Для начального решения .

Изменим случайным образом начальное решение. Для этого сгенерируем случайные числа в интервале варьирования каждого из факторов (генерировать случайные числа будем в Microsoft Excel). Результаты генерации случайных чисел представлены на рисунке 2.



Рисунок 2 – Генерация случайных чисел

Присваиваем параметрам МСУ случайно сгенерированные значения, предварительно округлив их для соответствия размеру минимального шага регулировки:

х1 = 760 мин-1; х2 = 8 мм; х3 = 10 мм; х4 = 13 мм; х5 = 8 мм; х6 = 820 мин-1

Оценим новое решение:

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

х1 = 890 мин-1; х2 = 14 мм; х3 = 4 мм; х4 = 3 мм; х5 = 11 мм; х6 = 750 мин-1.

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

Следующие 7 итераций алгоритма дали такие результаты:

В нашем случае алгоритм будет остановлен после 10 итераций. Лучшим решением, т.е. решением с наименьшим значением целевой функции является решение Х3 со значением целевой функции 4,808 %.


ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
По заданию преподавателя выбрать техническую систему, определить целевую функцию и регулируемые параметры. Используя алгоритм случайного поиска оптимизировать целевую функцию.

Рекомендуемая литература

1. Численные методы оптимизации: учебное пособие / Рейзлин В.И. – Томский политехнический университет. Томск: Изд-во Томского политехнического университета, 2011. 105 с.

2. Теоретические и прикладные аспекты разработки экспертных систем для технического обслуживания машин./ В. П. Димитров, Л. В. Борисова - Ростов н/Д: Издательский центр ДГТУ, 2007. - 202 с.





База данных защищена авторским правом ©refedu.ru 2016
обратиться к администрации

    Главная страница