Содержание к диссертации
Введение
1 Алгоритмы на допустимых пробных точках 22
1.1 Базовый алгоритм безусловной глобальной оптимизации методом усреднения координат 22
1.2 Генераторы последовательностей равномерно распределенных точек .26
1.3 Алгоритм глобальной оптимизации при ограничениях-неравенствах 31
1.4 Примеры 32
1.5 Свойства алгоритма и влияние параметров на качество его работы 39
1.6 Алгоритм поиска главных экстремумов 51
2 Алгоритмы глобальной оптимизации при ограничениях-неравенствах с использованием штрафных функций 64
2.1 Прямая свертка ограничений в штрафную функцию 64
2.2 Формирование штрафной функции с использованием относительных значений оптимизируемой функции и ограничений 65
2.3 Примеры 66
2.4 Свойства алгоритма и влияние параметров на качество его работы 75
3 Прямой алгоритм глобальной оптимизации при ограничениях-неравенствах 80
3.1 Прямой алгоритм учета ограничений 80
3.2 Примеры 81
3.3 Свойства алгоритма и влияние параметров на качество его работы 85
4 Программный пакет глобальной оптимизации «Global Optimizer vl.O» 89
4.1 Общее описание 89
4.2 Требования к ресурсам 91
4.3 Математическое ядро и модуль исследования 92
4.4 Методика проведения интерактивных исследований 97
4.5 Методика проведения пакетных исследований 102
4.6 Методика конструирования специальных программных стендов 108
5 Решение практических задач 111
5.1 Поиск оптимальных параметров эллипсов, аппроксимирующих произвольный контур 1 11
5.2 Поиск оптимального решения задачи распределения штатов 117
Заключение 126
Список использованных источников 128
Приложения 135
- Базовый алгоритм безусловной глобальной оптимизации методом усреднения координат
- Прямая свертка ограничений в штрафную функцию
- Прямой алгоритм учета ограничений
- Общее описание
Введение к работе
Актуальность. Методы оптимизации присутствуют практически на всех этапах системного анализа, а так же в системах поддержки принятия решений. Оптимизация находит широкое применение в науке, технике, бизнесе и во многих других практических областях деятельности человека. Это моїуі бьпь задачи: проекшрования. распределения ограниченных ресурсов, расчета траектории движения объекта, иденгификации параметров и т. д. Словом, такие задачи возникают везде, где необходимо получить наилучший результат целевой функции в допустимой области, задаваемой множеством некоторых ограничений-неравенств. Целевая функция может быть многоэкстремальной, разрывной, не дифференцируемой, искаженной помехами.
В настоящее время наиболее развиты теория и методы локальной оптимизации, которые в основном опираются на использование информации о производных функции качества. Задачи из реальной жизни этими методами зачастую не разрешимы, так как очень часто функция качесіва является многоэкстремальной и (или) информацию о ее производных невозможно получить (для разрывных или не дифференцируемых функций). Имеется острая практическая необходимость в разработке достаточного универсальных алюритмов для решения задач глобальной оптимизации, опираясь лишь на измерение или вычисление функции качества.
В свете всего выше сказанного разработка простых и эффективных алгоритмов глобальной оптимизации представляется достаточно актуальной задачей.
Народно-хозяйственная (техническая) проблема. Во многих современных системах поддержки принятия решений для сложных систем многоэкстре-мальность имеет широкое распространение, например для химико-технологических сие і ем многоэкстремальность является час і о встречающимся на практике моментом. Таким образом, новые, эффективные, универсальные и простые в эксплуатации алгоритмы глобальной оптимизации будут востребованы в индустрии.
Научная проблема порождена тем, что глобальная оптимизация относится к классу сложных и до сих пор полностью не разрешенных проблем. Хотя уже и существуют определенные результаты в этой области, но высокоэффективных, быстро сходящихся, простых по своей структуре, помехоустойчивых, не требующих сложной настройки параметров и понятных конечному пользователю алгоритмов очень мало. Таким образом, научная проблема состоит в синтезе новых и достаточного универсальных алгоритмов для решения задач глобальной оптимизации.
Объектом исследований являются программные алгоритмы глобальной оптимизации при наличии ограничений-неравенств.
Предметом исследований являются характеристики и свойства разработанных программных алгоритмов глобальной оптимизации при наличии ограничений-неравенств.
Цель исследований. Целью данной дтесерт^аішшішй-еабмьі является синтез и анализ новых алгоритмов глобальПой>«пт)іІ^йЩйігфувіций непре-
ЬИЬЛИОТ С.-Петербург ^
рывных переменных при наличии ограничений-неравенсів, на основе метода усреднения координат, позволяющего напрямую использовать инверсные характеристики.
Задачи исследований. Сформулированная выше цель предопределила следующую совокупность решаемых задач:
Разработать проіраммньїе алгоритмы глобальной оптимизации при наличии ограничений-неравенсів.
Разработать программный пакет, который позволит эффекшвно исследовать разработанные алгоритмы, а также решать различные задачи оптимизации.
Провести исследование работоспособности и эффективности этих алгоритмов на представительном множестве тесювых функций.
Выявить параметры, наиболее существенно влияющие на эффективность работы алгоритмов. Определить оптимальные диапазоны эгих параметров.
Получить различные статистические характеристики, описывающие свойства алгоритмов.
Разработать методики подбора параметров алюри шов для эффективного решения раз-гичных задач оптимизации.
Провести апробацию разработанных алгоритмов на реальных иракіиче-ских задачах.
Методы исследований. При решении поставленных идач использовались: теория оптимизации, теория вероятности и математической статисіики, мегодология объектно-ориентированного проіраммирования, а также методы вычислительных экспериментов.
Новые научные результаты диссертации. Разработаны и исследованы новые программные алюритмы глобальной оптимизации (основанные на методе усреднения координат) при наличии ограничений-неравенств:
-
Алгоритм на допустимых пробных точках [1, 2, 4].
-
Алгоритм поиска їлавньгх экстремумов (глобальный экстремум и близкие к нему по функции качества) [10].
-
Алгоритм с использованием двух видов свертки ограничений в штрафную функцию: прямая свертка и свертка в относительных величинах [3, 5].
-
Алгоритм прямого учета ограничений в ядрах процедуры усреднения координат [2, 4].
Значение для теории. Построенные высокоэффективные алгоритмы їло-бальной оптимизации при наличии ограничений-неравенств открывают путь к созданию новых более эффективных модификаций алгоритмов. К последним относятся алгоритмы, более экономно использующие пробные точки, полученные при совершении предыдущих рабочих шагов, а также алгоритмы с другими сочетаниями пробных и рабочих движений, вплоть до их совмещения.
Значение для практики. Разработан исследовательский программный пакет «Global Optimizer vl.O» [12]. Создана методология конструирования программных алгоритмов глобальной оптимизации, разработаны способы исследования влияния параметров алгоритмов на качество их работы. Полученные в
диссертационной работе рекомендации по выбору типа алгоритма и подбору его параметров позволяют конечным пользователям, не владеющим теорией глобальной оптимизации, решать с помощью разработанного программного пакета «Global Optimizer vl .0» различные сложные задачи, возникающие в реальной практике. В рамках диссертационной рабоїьі решено две практические задачи (подбор оптимальных параметров эллипсов аппроксимирующих произвольный контур и поиск оптимального решения задачи распределения штатов), которые подробно описаны в пятом разделе.
Полученные результаты используются в учебном процессе Красноярского государственного технического университета и Сибирского государственного аэрокосмического университета имени академика М.Ф. Решеїнева при изучении курсов: «Методы оптимизации», «Методы анализа данных» и «Компьютерный статистический анализ данных».
Достоверность полученных результатов подтверждается правильным отысканием глобальною условного экстремума для большого количества тестовых функций, и статистическими методами обработки данных, которые подтвердили хорошую воспроизводимость истинных результатов, а также успешным решением двух достаточно сложных практических задач.
Использование результатов диссеріации. Результаты диссертации можно использовать для решения различных теоретических и практических задач, в которых требуется найти условный глобальный экстремум.
Личный вклад автора. Лично автором получены основные результаты диссертации: программные алгоритмы глобальной оптимизации и методы исследования их свойств, которые являются ставной частью разработанного автором программного пакета «Global Optimizer vl .0»; разработана методика конструирования специальных программных стендов для ошимизации задач, у которых целевая функция задается алгоритмически; решено две пракшческие задачи (разработаны специальные программные стенды). Часть результатов, полученных автором в диссертации, вошли в моноірафию А. И. Рубана «Глобальная оптимизация методом усреднения координат» 2004 г., в которой содержатся ссылки на публикации автора.
Апробация результатов диссертации. Основные положения и результаты диссертационных исследований публиковались, докладывались и обсуждались на следующих научно-практических конференциях: The Third Russian-Korean International Symposium on Science and Technology, Новосибирск, 1999; Межвузовская научная конференция «Информатика и информационные технологии», КГТУ, Красноярск, 2003 и 2004; IV Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям, Красноярск, Академгородок, 2003.
Кроме того, отдельные результаты работы и диссеріация в целом обсуждались на научном семинаре кафедры «Информатика» КІ I У.
Публикации. По теме диссертации опубликовано 12 научных работ, из которых: 7 статей в сборниках научных грудов, 2 работы в грудах международных и всероссийских научно-технических конференций, 2 работы размещено в Интернете, получено авторское свидетельство из отраслевого фонда алгоритмов и программ.
Общая характеристика диссертации. Диссертация состоит из введения, пяти глав, заключения, 2 приложений и списка использованных источников из 69 наименования, содержит 150 рисунков и 2 таблицы. Общий объем диссертации (с учетом приложений) составляет 138 страниц.
Базовый алгоритм безусловной глобальной оптимизации методом усреднения координат
Теоретические предпосылки для создания практически реализуемых алгоритмов приведены в [45]. Там же приведена одна из возможных реализаций алгоритма поиска безусловного глобального экстремума методом усреднения координат. В связи с тем, что этот алгоритм, в той или иной мере, лежит в основе всех описанных в данной диссертации алгоритмов, будем называть его базовым алгоритмом, что кроме всего прочего, позволяет упростить описание всех остальных предлагаемых алгоритмов, приводя только необходимые изменения и дополнения к базовому алгоритму. Постановка задачи Необходимо отыскать условный глобальный минимум функции качества 1(х) многих непрерывных переменных x = (xi,---,xm) с учетом ограничений-неравенств фу(х) 0, j = 1, тх. Функция 1{х) может быть многоэкстремальной, разрывной, недифференцируемой, а также может быть искажена помехой. Ограничения сужают область поиска экстремума. Функции ограничений также могут быть невыпуклыми и недифференцируемыми. Поиск глобального минимума осуществляется только на основе измерений или вычислений функции качества 1{х) и функций, определяющих ограничения ф7(х). Описание базового алгоритма безусловной оптимизации 1. Равномерно разместить пробные точки х0), і = \,п в прямоугольной области с центром в точке х и интервалами варьирования Ах : где u - равномерно распределённые (случайные или детерминированные) в интервале [-1; 1] числа. 2. Вычислить значение функции / 0 = 1{х(,)) в этих точках. 3. Вычислить новое значение хм в среднем более близкое к глобальному экстремуму: . =1 5. Проверить условие останова алгоритма, если оно выполняется, то завершить вычисления, иначе перейти к шагу 1. Остановка движения в программной реализации происходит при выполнении одного из критериев останова (задается исследователем перед запуском алгоритма): а) Превышение заранее заданного количества рабочих шагов алгоритма (для предотвращения бесконечных циклов). б) Область варьирования уменьшилась до заданного малого размера. в) Значение функции качества на текущей итерации мало отличается от значения на предыдущей итерации. г) Значение вектора искомых переменных на текущей итерации мало отли чается от предыдущего значения. Примечание: В переменных и , Д для упрощения записи опущен номер итерации / = 0, 1, 2,.... Коэффициент растяжения области варьирования уч О, он определяет скорость сжатия области варьирования. Коэффициент метрики пространства q = 1,2,---. В дальнейшем рх будем называть ядром, а рх - нормированным ядром. Весовые коэффициенты р1 }, i = \,n, всегда нормированы на п системе п пробных точек: Д(,) =1. Коэффициент s О характеризует степень /=i селективности ядра. Для решения различных задач можно использовать следующий набор степенных ядер ps(g) 1. Линейное (г = 1), параболическое (г = 2), кубическое (г = 3) и так далее: Ate) = 0-sT; (1-1-5) 2. Экспоненциальное: py(g) = exp{-5g }, г = 1, 2, 3...; (1.1.6) 3. Регуляризованное гиперболическое: ps(g) = (sgr+ \) l, г = 1,2,3...; (1.1.7) 4. Гиперболическое: ps{g)-g (1.1.8) Приведенного набора ядер вполне достаточно для решения большинства задач глобальной оптимизации. При увеличении коэффициента s растет «селективность» (способность к локализации положения глобального экстремума) ядра. Параметр ядра г 1 определяет «выпуклость» ядра и обычно принимает значения от 1 до 5. Значения больше 5 могут применяться при оптимизации многоэкстремальных функций, сильно искаженных помехами. При конструировании ядер за основу берется убывающая в интервале [0;1] функция p(g), и она возводится в степень s: ps(g)-(p(g)Y Для таких ядер p{g) всегда выполняется условие 1 (p(g)/p{z)) при у z. При работе с алгоритмами оказалось, что для эффективного решения подавляющего большинства задач хватает одного степного ядра с различными значениями степени г и селективности s. На рисунках 1.1.1 - 1.1.4 показаны графики вышеприведенных ядер ps(g) при различных s:
Прямая свертка ограничений в штрафную функцию
Обозначим через 1(х) - исходную оптимизируемую функцию, через фу(х) 0, 7 = 1, тх - исходные ограничения, а через I (х) - штрафную функцию, полученную из 1(х) и ф7(х). Один из распространенных способов решения задач условной минимизации заключается в формировании новой минимизируемой функции (которую обычно называют штрафной функцией) за счет аддитивного присоединения к исходной функции качества 1(х) штрафных компонент, которые сильно нарастают при нарушении ограничений. Таким образом осуществляется переход к эквивалентной, но уже к безусловной задаче минимизации. За счет введения штрафной добавки оптимизируемая функция становится неудобной (овражной) для минимизации существующими традиционными алгоритмами, особенно для алгоритмов использующих градиент или его оценку. При переходе к штрафной функции она становится овражной и часто может содержать точки, и даже целые области не дифференцируемости. Алгоритмы полученные на основе метода усреднения координат глобальной поисковой оптимизации успешно справляются с минимизацией негладких и овражных функций. Штрафная функция часто имеет вид: Недостатком этой функции является необходимость подбора множества коэффициентов aj. Близкая к (2.1.2) штрафная функции имеет вид: І(х) = І(х) + ац)+(х), ф+(х) = тах{0, ф.(х),..., ф (х)}, а 0. (2.1.3) Её ДОСТОИНСТВОМ является наличие только одного штрафного коэффициента а 0. Этот способ формирования штрафной функции (в виду его простоты) и будет использоваться. Он применим, если все функции входящие в (2.1.3) имеют одинаковую размерность. Затем по базовому алгоритму безусловной глобальной оптимизации (см. раздел 1.1) отыскивается безусловный глобальный экстремум для штрафной функции (2.1.3). 2.2 Формирование штрафной функции с использованием относительных значений оптимизируемой функции и ограничений Свертка минимизируемой функции 1{х) со штрафной добавкой в виде (2.1.3) имеет недостаток. Он состоит в том, что в реальных задачах все участвующие в расчетах функции имеют различные размерности. Этот факт проявляется в том, что некоторые функции принимают сравнительно малые значения, а некоторые - сравнительно большие значения. За счет этого свертка (2.1.3) чаще всего становится совсем не эффективной. Целесообразно формировать итоговую минимизируемую функцию на основе использования относительных значений всех компонент. На этапе пробных движений (перед совершением каждого рабочего шага) после выполнения п пробных шагов и вычисления в каждой пробной точке значений всех функций (минимизируемой 1(х{,)) и всех функций Ф,(х(,)), , фп, (х{1)), / = 1, п, входящих в левую часть ограничений-неравенств) при каждом фиксированном значении / в расчетах итоговой штрафной функции 1(хи)) для пробной точки х{1) участвуют только те функции ф7(лг("), которые больше нуля (т. е. те функции, для которых ограничения нарушены): фДх(,)) 0 при jє JU) el m,. Итоговая функция 7(х(") для каждой пробной точки х(,) находится аддитивным наложением на относительную величину основной функции 1(х) штрафной добавки тоже в относительных величинах: Если при некотором j = 1 множество {/: фДх(,)) 0} пустое, то этот номер І не входит во множество J(", присутствующее в формуле {22 А) (для каждого фиксированного / ). Для пробных точек, в которых ни одно неравенство не нарушено (множество J(,) пустое) штрафная добавка берётся равная нулю. Если при некотором j = l множество {/:ф/( (,)) 0} состоит из одного элемента, то соответствующий элемент в (2.2.4) (входящий под оператор тах{}) полагаем равным единице: — = 1. тш Далее каждый рабочий шаг совершается в сторону глобального минимума штрафной функции 1(х) как обычно, по алгоритму глобальной безусловной оптимизации (см. раздел 1.1). 2.3 Примеры Пример 2.3.1 Рассмотрим многоэкстремальную аддитивную двумерную потенциальную функцию: Ее вид показан на рисунках 2.3.1 и 2.3.2. Функция имеет 9 минимумов и изрезана глубокими взаимно пересекающимися (в точках минимума) оврагами. Один из минимумов в точке (2; 2) является глобальным. Ограничения # отсекают два экстремума из девяти (в том числе и глобальный экстремум в точке (2; 2)). Условный глобальный экстремум теперь находится в точке (1.02; 1.99). Отыскиваем условный минимум на основе алгоритмов с использованием прямой и относительной свертки ограничений в штрафную функцию. Тогда оптимизируемая функция будет иметь вид: l(x],x2) = I(xnx2) + атах{0, левые части ограничений (2.3.2)} (2.3.3) Внешний вид функции (2.3.3) при а = 30 представлен на рисунках 2.3.3 и 2.3.4. Проведем минимизацию штрафной функции (2.3.3) с использованием свертки (2.1.3) со следующими настройками: начальная точка (4; 4), размеры области варьирования (Ах, =4; Ах2 = 4), /7 = 50, q = 2, у = 1, а = 30, ядро степенное линейное (г = 1) при л = 300, а также с использованием свертки (2.2.4), при тех же настройках, только при а = 5. Типичные результаты работы в обоих случаях представлены на рисунке 2.3.5. Как видно из графиков, результаты работы примерно одинаковые. Этого и следовало ожидать, так как участвующие в расчетах функции имеют одинаковую размерность, и поэтому особой разницы в результатах нет. Можно даже отметить некоторое преимущество использова-ф ния свертки (2.1.3), так как в этом случае не приходится выполнять лишних
Прямой алгоритм учета ограничений
В работах Якунина 10.10. [62 - 69] одной из рассмотренных задач оптимизации сформулирована следующая.
Работа учебно-методических управлений большинства вузов страны по распределению ресурсов заключается в расчете числа ставок на кафедрах. Причем для высшего руководства очень важно чтобы общее число ставок не превышало заданного значения и стремилось к минимуму. Также, очень важно, чтобы на всех кафедрах и во всех подразделениях средняя нагрузка преподавателя не превышала нормативного значения и примерно была одинаковой на всех кафедрах. И, наконец, нагрузка преподавателя в среднем по вузу не должна превышать нормативного значения.
В качестве варьируемого параметра был выбран нормативный коэффициент приведения по каждой специальности (или в частном случае, по каждому факультету), т.е. число студентов на одного преподавателя.
Поскольку при изменении нормативных коэффициентов приведения у каждого факультета изменяется общее число ставок, выделяемых этим факультетам, то оптимальное решение задачи распределения штатов приведет к тому, что у одних подразделений ресурс будет изыматься, а другим дотироваться с целью выравнивания средней нагрузки преподавателей на кафедрах. В результате факультеты, у которых ресурс был изъят, окажутся спонсорами для других факультетов, у которых соотношение нагрузки и контингента обучающихся не позволяет загрузить кафедры с приемлемой средней нагрузкой. Такая несправедливость может вызвать негативную реакцию со стороны руководителей этих факультетов. Во избежание подобных конфликтов ниже предлагается вариант решения данной задачи, который позволит обойти эти конфликты.
Задача может быть решена путем формирования резервного фонда и его распределения. Нормативным коэффициентом гп регулируется число ставок или количество ресурсов выделяемых подразделению (факультету) по числу студентов. При увеличении нормативного коэффициента уменьшается число ставок и наоборот. Таким образом, для достижения минимума общего числа ставок в вузе, можно было бы увеличить нормативный коэффициент до бесконечности и общее число ставок равнялось бы нулю. Но при снижении числа ставок растет средняя нагрузка преподавателя как в вузе в целом, так и в его подразделениях. А эта величина ограничивается нормативными документами Министерства образования и науки и конституционным законом охраны труда Российской федерации (КЗоТ РФ). Нижняя граница нормативного коэффициента rj ограничивается этими же документами.
Таким образом, изначально вуз располагает числом ставок, полученных от Министерства образования и науки по контингенту обучающихся в соответствии с нормативным коэффициентом, установленным министерством. Далее перед вузом стоит задача определения своего внутреннего нормативного коэффициента таким образом, чтобы минимизировать число ставок на учебный процесс и не превысить максимально возможную среднюю нагрузку преподавателя QZL по ВУ3У- Нужно учесть и тот факт, что нормативный коэффициент может быть одинаковым для всех подразделений по формам обучения (очная, заочная и вечерняя) и типам обучающихся (студент, магистрант, аспирант, слушатель подготовительных курсов и т.д.). А средняя нагрузка преподавателя подразделений и кафедр не должна превышать максимальную нагрузку QZtj и быть примерно одинаковой (различие может состоять в единицах часов нагрузки на преподавателя) по кафедрам. Математическое представление задачи запишется так:
Решение задачи оптимизации (5.2.1) с заданными ограничениями на среднюю нагрузку преподавателя как в вузе в целом, так и на кафедрах, позволяет найти минимальной число ставок необходимых для обеспечения учебного процесса в вузе. Исследования данной модели показали, что ее решение в виде набора значений нормативных коэффициентов позволяет получить такое распределении ресурсов по подразделениям, которое обеспечивает не только минимальное значение общего числа ставок, но и почти одинаковую среднюю нагрузку в подразделениях не превышающую заданного ограничением значения QZ.(см. рисунок 5.2.1).
Из рисунка 5.2.1 видно, что нагрузка ни одного из подразделений не превышает максимально допустимого значения. Но также видно, что отличия средней нагрузки преподавателя в подразделениях все еще присутствует. Это обусловлено заданными г и г (см. ограничения (5.2.2)).
При расширении диапазона г/ в ограничении (5.2.2), возможно достиже Но такое расширение диапазона т. может сопровождаться неизбежным увеличением общего число ставок, выделенных на учебный процесс. Поэтому ответственность за задание значений г" и г ложиться на ЛПР. ЛПР принимает решение о задание г 1 и г в соответствии с текущей политической и
экономической ситуацией в стране и в вузе, а также в соответствии с возможностями вуза обеспечения учебного процесса дополнительными ставками за счет внебюджетных доходов.
Проведение автоматической оптимизации поможет выровнять нагрузку на кафедрах, что в условиях ручного решения недостижимо. Кроме того, автоматизация этой задачи позволяет ЛПР проимитировать различные ситуации, по-средствам изменения исходных данных и параметров задачи оптимизации и тем самым выбрать наилучшее решение.
Для решения этой задачи был разработан специальный программный стенд, который позволяет быстро определять оптимальные значения для нормативных коэффициентов rf . При разработке программного стенда было использовано математическое ядро и элементы пользовательского интерфейса из программного пакета глобальной оптимизации «Global Optimizer vl .0».
Рассматриваемая задача достаточно сложна для оптимизации, так как имеет высокую размерность вектора искомых переменных (от 70 до 100) и большое количество ограничений (порядка 300). По этому было принято решение использовать для оптимизации алгоритмы условной глобальной оптимизации с формированием штрафной функции за счет свертки ограничений в штрафную добавку (эти алгоритмы описаны во втором разделе). Так как эти алгоритмы наиболее просты в настройке и могут работать в ситуации, когда задача оптимизации содержит большое количество ограничений.
Общее описание
В работах Якунина 10.10. [62 - 69] одной из рассмотренных задач оптимизации сформулирована следующая.
Работа учебно-методических управлений большинства вузов страны по распределению ресурсов заключается в расчете числа ставок на кафедрах. Причем для высшего руководства очень важно чтобы общее число ставок не превышало заданного значения и стремилось к минимуму. Также, очень важно, чтобы на всех кафедрах и во всех подразделениях средняя нагрузка преподавателя не превышала нормативного значения и примерно была одинаковой на всех кафедрах. И, наконец, нагрузка преподавателя в среднем по вузу не должна превышать нормативного значения.
В качестве варьируемого параметра был выбран нормативный коэффициент приведения по каждой специальности (или в частном случае, по каждому факультету), т.е. число студентов на одного преподавателя.
Поскольку при изменении нормативных коэффициентов приведения у каждого факультета изменяется общее число ставок, выделяемых этим факультетам, то оптимальное решение задачи распределения штатов приведет к тому, что у одних подразделений ресурс будет изыматься, а другим дотироваться с целью выравнивания средней нагрузки преподавателей на кафедрах. В результате факультеты, у которых ресурс был изъят, окажутся спонсорами для других факультетов, у которых соотношение нагрузки и контингента обучающихся не позволяет загрузить кафедры с приемлемой средней нагрузкой. Такая несправедливость может вызвать негативную реакцию со стороны руководителей этих факультетов. Во избежание подобных конфликтов ниже предлагается вариант решения данной задачи, который позволит обойти эти конфликты.
Задача может быть решена путем формирования резервного фонда и его распределения. Нормативным коэффициентом гп регулируется число ставок или количество ресурсов выделяемых подразделению (факультету) по числу студентов. При увеличении нормативного коэффициента уменьшается число ставок и наоборот. Таким образом, для достижения минимума общего числа ставок в вузе, можно было бы увеличить нормативный коэффициент до бесконечности и общее число ставок равнялось бы нулю. Но при снижении числа ставок растет средняя нагрузка преподавателя как в вузе в целом, так и в его подразделениях. А эта величина ограничивается нормативными документами Министерства образования и науки и конституционным законом охраны труда Российской федерации (КЗоТ РФ). Нижняя граница нормативного коэффициента rj ограничивается этими же документами.
Таким образом, изначально вуз располагает числом ставок, полученных от Министерства образования и науки по контингенту обучающихся в соответствии с нормативным коэффициентом, установленным министерством. Далее перед вузом стоит задача определения своего внутреннего нормативного коэффициента таким образом, чтобы минимизировать число ставок на учебный процесс и не превысить максимально возможную среднюю нагрузку преподавателя QZL по ВУ3У- Нужно учесть и тот факт, что нормативный коэффициент может быть одинаковым для всех подразделений по формам обучения (очная, заочная и вечерняя) и типам обучающихся (студент, магистрант, аспирант, слушатель подготовительных курсов и т.д.). А средняя нагрузка преподавателя подразделений и кафедр не должна превышать максимальную нагрузку QZtj и быть примерно одинаковой (различие может состоять в единицах часов нагрузки на преподавателя) по кафедрам. Математическое представление задачи запишется так: Решение задачи оптимизации (5.2.1) с заданными ограничениями на среднюю нагрузку преподавателя как в вузе в целом, так и на кафедрах, позволяет найти минимальной число ставок необходимых для обеспечения учебного процесса в вузе. Исследования данной модели показали, что ее решение в виде набора значений нормативных коэффициентов позволяет получить такое распределении ресурсов по подразделениям, которое обеспечивает не только минимальное значение общего числа ставок, но и почти одинаковую среднюю нагрузку в подразделениях не превышающую заданного ограничением значения QZ.(см. рисунок 5.2.1).
Из рисунка 5.2.1 видно, что нагрузка ни одного из подразделений не превышает максимально допустимого значения. Но также видно, что отличия средней нагрузки преподавателя в подразделениях все еще присутствует. Это обусловлено заданными г и г (см. ограничения (5.2.2)).
При расширении диапазона г/ в ограничении (5.2.2), возможно достиже Но такое расширение диапазона т. может сопровождаться неизбежным увеличением общего число ставок, выделенных на учебный процесс. Поэтому ответственность за задание значений г" и г ложиться на ЛПР. ЛПР принимает решение о задание г 1 и г в соответствии с текущей политической и экономической ситуацией в стране и в вузе, а также в соответствии с возможностями вуза обеспечения учебного процесса дополнительными ставками за счет внебюджетных доходов.
Проведение автоматической оптимизации поможет выровнять нагрузку на кафедрах, что в условиях ручного решения недостижимо. Кроме того, автоматизация этой задачи позволяет ЛПР проимитировать различные ситуации, по-средствам изменения исходных данных и параметров задачи оптимизации и тем самым выбрать наилучшее решение.
Для решения этой задачи был разработан специальный программный стенд, который позволяет быстро определять оптимальные значения для нормативных коэффициентов rf . При разработке программного стенда было использовано математическое ядро и элементы пользовательского интерфейса из программного пакета глобальной оптимизации «Global Optimizer vl .0».
Рассматриваемая задача достаточно сложна для оптимизации, так как имеет высокую размерность вектора искомых переменных (от 70 до 100) и большое количество ограничений (порядка 300). По этому было принято решение использовать для оптимизации алгоритмы условной глобальной оптимизации с формированием штрафной функции за счет свертки ограничений в штрафную добавку (эти алгоритмы описаны во втором разделе). Так как эти алгоритмы наиболее просты в настройке и могут работать в ситуации, когда задача оптимизации содержит большое количество ограничений.
