Содержание к диссертации
Введение
Глава 1. Системный подход к планированию учебного процесса в вузе 15
1.1. Основные виды деятельности и роль принятия управленческих решений в вузе 15
1.2. Анализ учебного процесса как объекта планирования
1.2.1. Элементы и подсистемы учебного процесса 19
1.2.2. Формирование контингента студентов 22
1.2.3. Построение учебных планов образовательных программ 25
1.2.4. Составление расписания занятий 28
1.2.5. Распределение ресурсов в вузе
1.3. Концептуальные основы качества образования в вузе 38
1.4. Обзор литературы, посвященный управлению вузом и планированию учебного процесса в вузе 45
1.5. Постановка задачи исследования 70
Выводыпо главе 75
Глава 2. Концепция оптимального планирования учебного процесса в вузе 77
2.1. Принципы оптимального планирования учебного процесса в вузе 77
2.2. Выбор глобальной целевой функции эффективности учебного Процесса 82
2.2.1. Понятие эффективности учебного процесса 82
2.2.2. Экономические критерии эффективности учебного процесса в вузе 90
2.3. Способы решения задач оптимизации большой размерности 99
2.4.декомпозиция задачи оптимального планирования учебного Процесса в вузе 103
Выводыпо главе 105
Глава 3. Оптимальное планирование Приема студентов в вуз 107
3.1. Постановка задачи нахождения оптимального плана приема студентов в вуз в условиях неопределенности 107
3.2. Метод кусочно-линейной аппроксимации задачи нелинейного Программирования 121
Выводы по главе 128
Глава 4. Модели и алгоритмы формализованного составления учебного плана образовательной программы в вузе 129
4.1. Основные понятия учебного плана 129
4.2. Автоматизированное составление учебного плана
4.2.1. Распределение дисциплин и их объемов по семестрам с учетом выполнения требований фгос и вуза 133
4.2.2. Распределение полученных для каждого семестра объемов дисциплин по видам занятий с учетом ресурсных ограничений 139
4.3. Методы решения задачи оптимизация учебного плана 143
Выводы по главе 158
Глава 5. Оптимальное планирование штата ппс в вузе и его распределение среди образовательных программ 160
5.1. Принципы и методы определения потребностей вуза в штатных единицах ппс 160
5.2. Модели и алгоритмы нахождения оптимальной структуры ппс в вузе 163
5.2.1. Нахождение оптимальной структуры ппс с учетом минимизации затрат на использование ппс 164
5.2.2. Оптимальное планирование штата ппс с учетом максимизации ставок преподавателей с учеными степенями или учеными званиями 171
5.3. Оптимальное распределение учебных поручений между преподавателями кафедры вуза 184
Выводы по главе 194
Глава 6. Автоматизированное составление расписания занятий в в узе 196
6.1. Исходные данные, требования и критерий оценки расписания занятий в вузе 196
6.2. Нахождение оптимальной структуры учебных помещений с учетом минимизации затрат на их использование 199
6.3. Модель и алгоритмы синтеза оптимального расписания для пакета занятий 211
6.3.1. Анализ задачи построения расписаний обслуживания требований между идентичными параллельно работающими приборами 212
6.3.2. Декомпозиция задачи на подмножества оптимизационных задач распределения занятий в одно учебное помещение 217
6.3.3. Модель и алгоритмы синтеза оптимального расписания для одного учебного помещения 221
6.4. Вычислительная схема поэтапного синтеза расписания занятий 229
Выводыпо главе 233
Глава 7. Оптимальное планирование учебного процесса в вузе 235
7.1. Оптимальное планирование учебного процесса 235
7.2. Метод решения задачи координации
7.2.1. Метод целевой координации 251
7.2.2. Метод координации моделей 256
7.2.3. Комбинированный метод
7.3. Сравнение методов координации 261
7.4. Двухуровневое планирование учебного процесса в вузе 263
Выводыпо главе 265
глава 8. Построение системы оптимального планирования учебного процесса в вузе 267
8.1. Развитие системы оптимального планирования учебного процесса агта 267
8.2. Подсистема оптимального планирования приема студентов в вуз 278
Выводыпо главе 284
Заключение 285
Список литературы
- Анализ учебного процесса как объекта планирования
- Выбор глобальной целевой функции эффективности учебного Процесса
- Метод кусочно-линейной аппроксимации задачи нелинейного Программирования
- Распределение полученных для каждого семестра объемов дисциплин по видам занятий с учетом ресурсных ограничений
Введение к работе
Актуальность темы исследования. Высшие учебные заведения стали полноправными субъектами рыночной экономики, получив право самостоятельно определять направления своего развития, цели и методы их достижения. Повысились требования общества к качеству образования, кардинально обновляются технологии обучения, быстро меняются организационные и экономические условия деятельности вузов, обостряется конкурентная борьба на рынке образовательных услуг, постоянно меняется позиция государства по отношению к высшей школе. Возникли разные группы заказчиков и потребителей образовательных услуг со своими финансовыми возможностями, запросами и интересами. Появились и успешно развиваются негосударственные вузы.
Складывающиеся рыночные условия диктуют достаточно жесткие условия для работы вузов. Сложившаяся десятилетиями система управления вузами, не содержащая элементов, даже отдаленно напоминающих экономические, в полном объеме финансируемая государством, оказалась не в состоянии обеспечить надлежащее качество управления современным вузом. В условиях, когда государство отказалось от роли главного и единственного финансиста высшего образования, одной из главных проблем вузов становится проблема экономической выживаемости. Вузы вынуждены не только самостоятельно изыскивать средства для поддержания своего основного вида деятельности, но и эффективно использовать имеющиеся ресурсы. Таким образом, развитие новых организационно-экономических механизмов управления вузом, пригодных для новых экономических условий, становится серьезной проблемой, решение которой невозможно без глубокого научного анализа.
В вузе одновременно протекает большое число процессов, различающихся как по своему назначению, так и по основным показателям. В то же время, характер управленческих решений, принимаемых в вузе, масштаб последствий от принятия решений позволяет выделить в качестве основного учебный процесс. Именно учебный процесс обеспечивает выполнение уставных задач вуза; на учебный процесс направляются основные ресурсы; от организации учебного процесса зависят основные показатели функционирования вуза, его эффективность и качество подготовки обучающихся.
В настоящее время в большинстве вузов планирование учебного процесса, в том числе и распределение ресурсов, осуществляется «вручную», отсутствует возможность многовариантного анализа способов реализации учебного процесса. Результаты планирования учебного процесса значительно ухудшаются по мере укрупнения вуза и увеличения объема информации. Процесс поиска оптимального или просто приемлемого, в каком-либо смысле, управленческого решения в этих условиях носит интуитивный характер и осуществляется методом «проб и ошибок», что часто приводит не только к значительным материальным потерям, но и потере качества подготовки обучающихся. Кроме того, при выработке управленческих решений в расчет по существу не принимаются экономические показатели эффективности учебного процесса.
Широкое внедрение ЭВМ в практику управления вузом позволило значительно улучшить качество планирования учебного процесса, в том числе с помощью решения оптимизационных задач на базе математических моделей. Проблемы оптимизации и информатизации учебного процесса в вузе исследовались в работах Б.А. Аграновича, В.Н. Васильева, Ю.С. Васильева, В.В. Гусева, А.П. Ефремова, Г.И. Лазарева, Д.А. Новикова, А.Я. Савельева, А.Н. Тихонова, В.З. Ямпольского и др. Вместе с тем надо признать, что существующие формализованные методы планирования учебного процесса имеют разрозненный характер, отсутствует общесистемная проработка целей планиро-
вания учебного процесса, не существует системы моделей, взаимоувязанных между собой и описывающих разные аспекты учебного процесса, принятие решений осуществляется без учета экономических факторов.
В современной научной литературе вопросам эффективности планирования отводится значительное место. Как правило, данная проблема освещается преимущественно в экономическом аспекте и по отношению к управлению промышленными или коммерческими предприятиями. Тем не менее, научные основы эффективного планирования, полученные в экономике, могут быть широко использованы и послужить основой для разработки методологических основ управления вузом и в частности планирования учебного процесса. Действительно, учебный процесс в вузе можно рассматривать как некоторую совокупность технологических процессов (набор абитуриентов, обучение и выпуск специалистов), обеспечивающих выполнение соответствующих «производственных» (образовательных) программ. Как и на промышленном предприятии, для осуществления учебного процесса в вузе требуются основные фонды (здания и сооружения), трудовые ресурсы (профессорско-преподавательский состав (ППС), администрация и сотрудники), материалы и инструменты (учебно-методическое обеспечение, технические средства обучения, программы для ЭВМ). Как и на предприятии, в управлении учебным процессом необходимо планирование, контроль, оперативное управление ресурсами, количественная оценка и обоснование принимаемых решений.
Вот почему на нынешнем этапе развития работ по совершенствованию управления в высшей школе особую важность приобретают работы, посвященные формализованному планированию и организации учебного процесса в вузе на основе экономических критериев, современных методов теории управления и оптимизации. Пока теоретические основы такого рода задач в управлении учебным процессом в вузе разработаны недостаточно.
Целью диссертационной работы является совершенствование механизмов планирования учебного процесса в вузе на основе формализации, оптимизации и автоматизации процедур принятия решений при планировании учебного процесса, обеспечивающих его экономическую эффективность.
Соответствующая указанной цели научная проблема может быть сформулирована следующим образом - создание методологии оптимального планирования учебного процесса в вузе пригодной для новых экономических условий.
Основные задачи исследования. Для достижения поставленной цели необходимо решить следующий комплекс задач:
с позиций системного подхода исследовать процедуры принятия решений при планировании и организации учебного процесса в вузе, сформулировать проблему и задачи исследования;
разработать концепцию оптимального планирования учебного процесса в вузе, обеспечивающую его экономическую эффективность;
разработать модели и методы оптимального планирования учебного процесса в вузе, воплощающие эту концепцию;
реализовать модели и методы в виде алгоритмического и программного обеспечения системы оптимального планирования учебного процесса;
провести апробацию разработанных методов и алгоритмов, внедрить разработанные методы и алгоритмы в практику планирования и организации учебного процесса в вузе.
Объект исследования. Объектом исследования является организация и планирование учебного процесса в вузе.
Предмет исследования. Предметом исследования являются методы, модели и алгоритмы формализации, оптимизации и автоматизации процедур принятия решений при планировании учебного процесса в вузе.
Методы исследований. Для исследования проблемы и решения задач формализованного планирования учебного процесса в вузе использовались методы системного анализа, математического программирования, исследования операций, теорий расписаний и иерархических многоуровневых систем.
Научная новизна диссертационной работы заключается в следующем:
-
Предложена новая методология оптимального планирования учебного процесса в вузе с позиций его экономической эффективности, основанная на формализации и оптимизации процедур принятия решений и комплексном решении задач, возникающих при планировании и организации учебного процесса.
-
Разработаны новые математические модели задач, формализующие процедуры принятия решений в задачах планирования учебного процесса в вузе, методы и алгоритмы их решения, которые включают:
математическую модель и точный алгоритм решения задачи нахождения оптимального плана приема студентов в вуз при случайных значениях спроса на образовательные программы;
математическую модель и точный алгоритм решения задачи автоматизированного проектирования учебного плана образовательной программы, учитывающей выполнение логической последовательности изучения дисциплин, требования, задаваемые Федеральным государственным образовательным стандартом (ФГОС) и вузом;
математическую модель и точный алгоритм решения задачи нахождения оптимальной численности ППС и его рационального распределения среди образовательных программ, обеспечивающей минимизацию затрат вуза на использование профессорско-преподавательского состава;
математическую модель и точный алгоритм решения задачи нахождения оптимальной структуры ППС и его рационального распределения среди образовательных программ, обеспечивающей равномерность и максимизацию доли лиц с учеными степенями и учеными званиями среди образовательных программ;
математическую модель и эвристический алгоритм решения задачи нахождения оптимальной структуры учебных помещений, обеспечивающей выполнение всех обязательных требований к расписанию занятий и минимизирующей затраты на использование учебных помещений.
-
Предложена вычислительная схема поэтапного синтеза расписания занятий, заключающаяся в декомпозиции исходной задачи на совокупность оптимизационных задач распределения занятий в одно учебное помещение, решаемых с помощью стандартной задачи линейного программирования о назначении.
-
Разработана комплексная модель задачи оптимизации учебного процесса в вузе и алгоритм ее решения, реализованные в двухуровневой системе принятия решений, позволяющие найти вариант организации учебного процесса с наибольшей экономической эффективностью.
Практическая значимость. Разработанные в диссертации модели и алгоритмы нахождения оптимальных планов приема студентов в вуз, учебных планов образовательных программ, оптимального штатного расписания ППС и фонда учебных помещений, расписания учебных занятий, а также комплексной оптимизации учебного процесса в вузе могут быть рекомендованы к использованию при проектировании, синтезе и эксплуатации автоматизированной системы управления вузом, автоматизированной информационной систе-
мы вуза и т.п. Отдельные результаты работы опубликованы в монографии «Исследование операций в управлении вузом», рекомендованной ФГУ «Федеральный институт развития образования» в качестве учебного пособия для руководителей вузов, преподавателей, аспирантов и студентов.
Достоверность и обоснованность. Достоверность и обоснованность научных результатов диссертационной работы подтверждается использованием известных методов математического программирования, исследования операций, теорий расписаний, непротиворечивых математических моделей задач.
Реализация результатов работы. Результаты диссертационной работы используются в планировании учебного процесса и преподавании ряда дисциплин в Ангарской государственной технической академии (АГТА), Иркутском государственном университете, Иркутском государственном университете путей сообщения, Восточно-Сибирском государственном университете технологий и управления. Ряд разработок зарегистрированы в отраслевом фонде алгоритмов и программ ФГНУ «Государственный координационный центр информационных технологий» Министерства образования и науки РФ.
Апробация работы. Основные результаты и научные положения диссертации обсуждались и докладывались на XIV-XV, XVII-XXI и XXIII Международных научных конференциях «Математические методы в технике и технологиях» (Смоленск, 2001; Тамбов, 2002; Кострома, 2004; Казань, 2005; Воронеж, 2006; Ярославль, 2007; Саратов, 2008; Смоленск, 2010), VII- IX Всероссийских научно-технических конференциях «Теоретические и прикладные вопросы современных информационных технологий» (Улан-Удэ, 2006-2008), V Международной научно-практической конференции «Организационные, экономические и социальные проблемы управления высшим учебным заведением», Пенза, 2007, XV Международной научной конференции «Современные проблемы информатизации» (СПИ-2010), Воронеж, 2010, на ежегодных научно-практических конференциях АГТА.
Публикации. Основные положения диссертации отражены в 50 публикациях, из них 13 статей в журналах, входящих в перечень ВАК и одна монография. Получено 3 свидетельства об отраслевой регистрации разработки.
Структура работы. Диссертация состоит из введения, восьми глав, заключения и 3 приложений, содержит 299 страниц машинописного текста, в том числе 42 рисунка и 33 таблицы, список литературы из 295 наименований.
СТРУКТУРА РАБОТЫ
Анализ учебного процесса как объекта планирования
Контингент студентов является важнейшим показателем эффективности работы вуза. От контингента студентов зависит штатное расписание ІШС и УВП, суммарная учебная нагрузка преподавателей и нагрузка на каждую специальность, направление и форму обучения, количество групп и потоков, число аудиторий, требуемые под учебный процесс площади и количество единиц литературы в фондах библиотеки, объем средств, поступающих от платных студентов и т.д.
Сформировать контингент студентов, значит, решить многоэтапную задачу по определению контингента студентов на каждом курсе, форме обучения, образовательной программе.
Важнейшей задачей в формировании контингента студентов является задача планирования приема студентов на первый курс.
Независимо от организационно-правовой формы, вузы согласно законодательству наделены свободой самостоятельно организовывать свою деятельность в рамках лицензионных нормативов и Федеральных государственных образовательных стандартов, в том числе и планирование приема студентов на первый курс [125].
На рис. 1.2 представлена схема принятия решений при формировании плана приема студентов на первый курс.
В процессе планирования приема можно выделить два основных аспекта. Во-первых, необходимо так осуществить планирование, чтобы правильно и вовремя обеспечить различные секторы экономики страны квалифицированными кадрами, учесть требования, которые предъявляет общество к образованию. Во-вторых, необходимо увязать имеющиеся в вузе ресурсы, не нарушить лицензионные нормативы, обеспечить выполнение Федерального государственного образовательного стандарта.
На уровне федеральных органов управления образованием происходит оценка направлений развития экономики страны, делается прогноз потребности в специалистах, осуществляется финансирование вузов через систему государственного задания на подготовку специалистов.
На уровне общества формируется спрос в получении специальностей исходя из ее общественной престижности, семейных традиций, возможности будущего трудоустройства, условий труда и сложившегося размера оплаты.
Существенными элементами принятия решений при формировании плана приема являются определение бюджетных и коммерческих мест на реализуемые в вузе образовательные программы, решения о сроках и формах обучения, открытие новых направлений и специальностей, установлении цены за обучение на платной основе. Вуз вправе регулировать количество бюджетных мест на той или иной программе, участвуя в конкурсе на разме -23 щения госзаказа на подготовку специалистов. На схеме это отражено обратной связью между планом приема и государственным заданием.
Прием студентов на платной основе сверх плановых цифр зависит от ресурсов вуза, контингента студентов на других курсах и лицензионных нормативов (предельный контингент студентов в лицензии). При этом ресурсы складываются из бюджетных средств на выполнение государственного заказа и средств, получаемых от платных студентов. Ресурсы вуза направляются на организацию учебного процесса (оплата труда преподавателей и сотрудников, приобретение учебной литературы и оборудования и т.д.), капитальное строительство, покрытие прочих затрат вуза. В зависимости от объемов ресурсов вуз, по согласованию с вышестоящими органами, вправе изменять лицензионные нормативы (введение в строй новых учебных площадей позволяет увеличить значение лицензионного норматива в части предельного контингента студентов, привлечение дополнительно преподавателей позволяет вузу открыть новую образовательную программу и т.д.). Устанавливая ту или иную цену за обучение для платных студентов, вуз управляет формированием ресурсов.
Зачастую при формировании плана приема студентов на первый курс вузы используют наиболее простой принцип управления «от достигнутого уровня», когда план приема устанавливается на основе плана предшествующего периода с некоторой корректировкой по всем или отдельным образовательным программам.
Основные недостатки принципа планирования от достигнутого уровня достаточно очевидны: новый план, с одной стороны, повторяет возможно несовершенную структуру прошлого плана, а с другой, может оказаться неосуществимым, как в силу внутренних обстоятельств, например, из-за недостатка ресурсов, так и в силу внешних, например, отсутствие спроса на образовательные услуги на ту или иную образовательную программу.
Поэтому наибольший интерес вызывает подход к планированию приема студентов вуз, основанный на решении математической оптимизацион -24 ной задачи, позволяющей найти план, наилучшим образом согласованный с внутренними возможностями и с внешними условиями.
Для вуза, который осуществляет прием студентов на платной основе, появляются возможности формировать прием студентов и ресурсный потенциал одновременно. Для современного вуза привлечение средств от студентов, обучающихся на платной основе, является одним из основных источников внебюджетного финансирования. Таким образом, планирование от потребностей является ориентацией при формировании плана приема в вуз.
Неправильная оценка состояния вуза и просчеты при организации приема могут существенно повлиять на финансовое положение вуза в будущем. Например, при очень высокой цене за обучение вузу не удастся выполнить план набора студентов на коммерческой основе, при занижении цены вуз может лишиться части возможных поступлений, что отразится на качестве образования.
Выбор глобальной целевой функции эффективности учебного Процесса
Совершенно естественно, что в теории расписаний получили определенное распространение методы математического (линейного, целочисленного, динамического) программирования, особенно для решения задач временного согласования и распределения планируемых работ и ресурсов [34, 234, 259, 269, 271, 287]. В то же время, следует отметить, что представление задач теории расписаний в виде задачи математического программирования не является самым эффективным способом исследования задачи теории расписаний. Так, например, задача о переналадке станка при распределении 10 заданий по 4 станкам, сформулированная в виде задачи целочисленного линейного программирования, содержит 220 переменных и 390 ограничений, а построение расписания в конвейерной системе с 4-мя станками и 10-ю заданиями представляет задачу с 41 непрерывной и 180 двоичными переменными при 400 ограничениях [287]. Также проблематично применение методов динамического программирования [21, 269] к решению практических задач теории расписаний, ибо алгоритмы динамического программирования характеризуются экспоненциальными затратами времени и памяти [283].
Достаточно развитыми методами теории расписаний являются методы, основанные на идеях последовательного конструирования, анализа и отсеивания вариантов расписаний. Предложены многочисленные правила доминирования, позволяющие «отбраковывать» целые группы расписаний по отдельным построенным их фрагментам. Разработаны вычислительные схемы, в которых проводится систематическая оценка перспективности, предпочтительности одних расписаний относительно других конструируемых расписаний.
Одним из методов последовательного конструирования является метод ветвей и границ [60, 286]. Вместе с тем применение метода ветвей и границ к практическим задачам теории расписаний наталкивается на значительные трудности, поскольку характеризуется экспоненциальной вычислительной сложностью. Кроме того, для задач, размерность которых достаточно высока, использование метода ветвей и границ связано с «риском выхода» на прямой перебор. Проводя анализ точных методов в теории расписаний необходимо остановиться и на опыте их применения при составлении расписания занятий.
Одна из первых разработок математической модели расписания занятий принадлежит Готлибу [279]. В этой работе задача составления расписания занятий была сформулирована как задача целочисленного линейного программирования с булевыми переменными. Как уже было сказано выше, эффективные методы решения задачи целочисленного математического программирования разработаны лишь задач малой размерности. В задаче же составления расписания занятий, например, для 10 групп, с 10 преподавателями, с 10 аудиториями и 20 парами имеются 10 -10 10 - 20 = 20000 переменных и 2800 ограничений. Кроме того Готлиб попытался найти необходимые и достаточные условия для существования временного расписания. К сожалению, ему удалось сформулировать только необходимые условия.
В работах [192, 220, 268, 294] в задаче составления расписания занятий использовались графовые модели. Система ограничений задачи представляется в виде графа, вершинами которого являются отдельные занятия, а условия совместимости по времени отражаются с помощью дуг между вершинами. Таким образом, если два занятия несовместимы по времени, то между вершинами, соответствующими этим двум занятиям, в графе ограничений задачи будет присутствовать дуга или ребро. Так в [220] задача составления расписания учебных занятий сводится к задаче определения максимального потока в сети; в [294] к декомпозиции двудольных графов на паросочетания; в [192] к применению методов комбинаторного анализа, основанных на свойствах перестановок; а в [268] задача составления расписания сводится к задаче о раскраске графа.
К сожалению, решить задачу оптимизации расписания занятий с помощью графов точными методами невозможно вследствие большой размерности переменных. Важное значение имеет работа [277], в которой доказано, что задача составления расписания занятий является TVP-полной задачей. Поэтому остается открытым вопрос существования полиномиального алгоритма для решения задачи составления расписания занятий в вузах.
Таким образом, очевидно, что в настоящее время область, применения точных методов ограничивается решением простых задач составления расписаний занятий. Изучение вопросов сложности довольно ясно показывает, что наибольшего прогресса в области теории расписаний следует ожидать от исследования приближенных алгоритмов, которые позволяли бы относительно просто и быстро строить пусть не всегда оптимальные, но в достаточной для практики мере близкие к ним календарные графики.
К приближенным методам относятся статистические и, так называемые, эвристические методы, которые представляют собой набор правил сравнения, анализа и отбора вариантов возможных решений (в литературе они называются правилами предпочтения, приоритета, дисциплинирования очереди), являющихся формализованным обобщением опыта специалистов при составлении календарных планов вручную. Каждый приближенный или эвристический алгоритм строит допустимое, т.е. удовлетворяющее всем требованиям решение рассматриваемой задачи оптимизации.
Надо сказать, что за те несколько десятков лет, в течение которых алгоритмизируются различные задачи календарного планирования, в теории расписаний накоплен весьма значительный арсенал правил предпочтения, которые применяются при решении различных классов задач календарного планирования. Примеры их можно найти в [113, 114, 191,214].
Метод кусочно-линейной аппроксимации задачи нелинейного Программирования
Обзор работ, проведенный в первой главе, показал, что в большинстве вузов при планировании приема студентов на первый курс используется наиболее простой принцип планирования «от достигнутого уровня», когда план приема устанавливается на основе плана предшествующего периода с некоторой корректировкой по всем или отдельным образовательным программам. Причем корректировка осуществляется управленческим персоналом «вручную» без строгих формализованных обоснований. В тех же случаях, когда применяются формализованные методы нахождения плана приема студентов в вуз, математические постановки задач основываются на детерминированных линейных моделях. В то же время, очевидно, что планирование приема студентов в вуз всегда происходит в условиях неопределенности, когда неизвестен спрос на образовательные программы, или спрос представляет собой случайную величину. В этом случае постановка задачи, основанная на де -107 терминированной модели для детерминированных значений параметров и переменных задачи, теряет определенность. Поэтому актуальной является задача нахождения оптимального плана приема студентов в вуз в условиях неопределенности на основании только априорной информации.
В случаях, когда априори план и соответствующая ему эффективность не определены, прибегают к вероятностной оценке эффективности, и уже к моменту действия, апостериори, план и реализуемая эффективность вполне детерминированы. Очевидно, что планирование приема студентов в вуз связано с принятием конкретных обязательств, поэтому план приема не может быть случайным. Следовательно, практический интерес представляет постановка задачи нахождения не случайного, а вполне определенного плана приема, основанного только на располагаемой априорной информации.
Прием, обычно используемый в этом случае, состоит в максимизации или минимизации математического ожидания целевой функции на определенном интервале времени. В ситуациях, в которых одни и те же условия будут повторяться снова и снова, ожидаемое значение целевой функции может быть интерпретировано как среднее значение за долгий срок. Однако этот же самый критерий используется и тогда, когда некоторые обстоятельства имеют место только однажды, так что нет возможности интерпретировать математическое ожидание как долгосрочное среднее.
Перейдем непосредственно к составлению математической модели задачи. План приема студентов в вуз включает весьма большое количество показателей, но всегда является производным от контрольных цифр (бюджетных мест) и «коммерческих» мест для обучающихся на платной основе, формируемых вузом самостоятельно, на всех образовательных программах всех форм обучения.
Поскольку количество бюджетных мест выделяемых вузу формируется с учетом предложений вуза, следовательно, и планирование бюджетных мест также находится в ведении вуза. Пусть Ху- количество бюджетных мест, планируемых вузом на і -ю образовательную программу, г = \,п, где п - количество образовательных программ, (специальность или направление) на у -й форме обучения, j = 1,т, где т — число форм обучения (очная, очно-заочная, заочная); у у— количество мест на платной основе на і -й образовательной программе на у -й форме обучения, Sy- средства, выделяемые государством на одного бюджетного студента і-й образовательной программы на у-й форме обучения, Sy— цена / -й образовательной программы на у -й форме обучения, устанавливаемой вузом для обучающихся на платной основе. Тогда формально можно утверждать, что задача планирования приема студентов в вуз будет решена, если будут установлены значения xtJ и у у, і = 1, п, j = \,т.
Обозначим через Wy спрос абитуриентов на г -ю образовательную программу у-й формы обучения (количество абитуриентов, желающих поступить на і-ю образовательную программу у-й формы обучения). Спрос Wy является случайной величиной, которая подчинена закону нормального распределения с известным математическим ожиданием jUy и стандартным отклонением Gy. Проверка гипотезы о нормальности закона распределения случайной величины wtj приведена в Приложении 1. При решении задачи примем, что все переменные непрерывны.
Известно, что для нормального функционирования вуза необходимо, чтобы все поступившие от государства и коммерческих студентов средства на обучение не только покрывали все текущие издержки вуза по обеспечению образовательного процесса, но и приносили прибыль, которую можно реинвестировать в учебный процесс. Иначе вуз не выполнит обязательства перед участниками образовательного процесса и не обеспечит свое эффективное развитие. Поэтому в модели задачи примем в качестве целевой функции прибыль вуза, связанную с набором студентов в вуз. Поскольку планирование приема проводится в условиях неопределенности, можно говорить лишь о вероятностной оценке прибыли, т.е. ожидаемой прибыли.
Найдем выражение для ожидаемой вузом прибыли. Очевидно, что вуз понесет потери, если в вузе не окажется достаточного количества мест (бюджетных и коммерческих) на желаемую абитуриентом образовательную программу. Эти потери складываются из недополученного государственного финансирования и недополученного дохода от оплаты за обучение, которые можно было бы получить от платных студентов.
Вуз понесет потери и в случае, если количество запланированных мест превысит спрос. Эти потери складываются из постоянных затрат на организацию учебного процесса, а также неполученного финансирования из-за невыполнения плана приема.
Тогда можно считать, что ожидаемая прибыль от приема студентов в вуз равна ожидаемому доходу минус затраты на организацию учебного процесса, минус ожидаемая потеря.
Так как спрос на і-ю образовательную программу поу-й форме обучения равен wy, то доход вуза от приема студентов на і-ю образовательную программу поу-й форме составит SfjWy, ecnuwy xy SyXy+Sy(wy-Xy), ecnuxy wy (xy+yy\ (3.1) Щху + Sgyy, если Wy (xy + уу). При формировании приема на / -ю образовательную программу по у -й форме обучения возможны потери (Щ + Pij )(xij wtj ) + (sij + Pij )Уу если wtj xij» (Sij+PijKXy+yy-Wy), вели Ху М у {Ху+Уу\ (3.2) Sy (Wi, Xy - у у ), если Wy (Xy + у у ), где ру - постоянные затраты на организацию учебного процесса, приведенные на одного обучаемого. -ПО Обозначим через f(wy;jUy, jy) плотность нормального распределения случайной переменной с математическим ожиданием (л и стандартным отклонением ст. Будем предполагать, что нет зависимости между спросом на разные образовательные программы, т.е. абитуриент не станет поступать на другую программу, если мест на интересующей его программе нет. Так же будем считать, что если абитуриент не прошел по конкурсу на бюджетное место выбранной программы, он поступит в вуз на коммерческой основе, но только при наличии коммерческих мест.
Распределение полученных для каждого семестра объемов дисциплин по видам занятий с учетом ресурсных ограничений
Видно, что выполнены все заданные ограничения. Аудиторная нагрузка и самостоятельная работа распределены поровну. Отклонений, как в сторону аудиторной нагрузки, так и в сторону СРС нет.
Следует отметить, что объем вычислений при решении задачи квадратичного программирования в постановке (4.34), (4.35) с т ограничениями и п переменными примерно такой же, как при решении задачи линейного программирования с п + 2т ограничениями к п + т переменными.
Особенностью задачи оптимизации учебного плана является требование целочисленности переменных, т.е. количества часов отводимых на изучение дисциплин не может быть дробным. Кроме того, постановка задачи (4.1) - (4.16) содержит булевы переменные, принимающие только значения 0 или 1. Таким образом, нахождение целочисленного решения задач (4.1) -(4.16) может быть осуществлено одним из методов решения задачи ЦЛП. Схема же решения задачи (4.1) - (4.16) как задачи квадратичного программи -153 рования с целочисленными переменными остается той же, с тем лишь отличием, что после нахождения оптимального решения «обычной» задачи линейного программирования начинает работать метод ЦЛП.
Наиболее распространенными методами поиска решений в целочисленных задачах линейного программирования являются метод ветвей и границ и метод отсечения. Опыт вычислений свидетельствует, что метод ветвей и границ более успешно решает задачу, чем метод отсечения. Практически все коммерческие программы, предназначенные для решения задач целочисленного линейного программирования, используют метод ветвей и границ [233]. Метод отсечения более сложен и менее надежен, кроме того, его реализация порождает серьезные проблемы, связанные с ошибками машинного округления.
Суть метода ветвей и границ заключается в том, что сначала в области допустимых решений системы ограничений обычной задачи линейного программирования находится оптимальное решение задачи симплексным методом без требования целочисленности. Если в полученном решении некоторые переменные имеют дробные значения необходимо изменить пространство допустимых решений. Для этого выбирается любая из переменных, значение которой в исходной задаче линейного программирования не является целочисленной и по ней строятся два ограничения.
Метод ветвей и границ с вычислительной точки зрения обладает существенными достоинствами. Дело в том, что алгоритм, построенный на этом методе, сравнительно легко программируется на ЭВМ и поэтому реализуется на любой итерации без вмешательства человека.
К условиям задачи добавим еще два требования. Первое требование будет определять логическую последовательность изучения дисциплин. Второе требование устанавливает минимально допустимое количество аудиторных часов в неделю для каждой дисциплины, если она изучается в данном -ut семестре. Кроме того, количество часов отводимых на изучение дисциплин не может быть дробным.
Пусть, например, изучение третьей дисциплины возможно лишь после завершения второй дисциплины, а количество аудиторных часов в неделю, отводимых на все дисциплины, если они изучаются, не может быть меньше двух.
В соответствии с (4.4) - (4.6) запишем условия, устанавливающие логическую последовательность изучения дисциплин. Очевидно, что x3j = О, j = 1,3 если нарушено условие акх2к Ь2-е, к=\ Здесь мы имеем условие типа «или-или». Чтобы записать это условие введем булевы переменные S2l и 822 принимающие лишь значения 0 и 1. Очевидно, что третья дисциплина не может быть начата в первом семестре (не изучена вторая дисциплина), следовательно, х31 = 0.
Введем ограничения х32 82ХЪ3 и 12х21 82lb2 -е. Это означает, что если 82х =\, следовательно, вторая дисциплина вычитана в первом семестре. При ЭТОМ Первое уСЛОВИе ЛИШЬ Требует, ЧТО Х32 82ХЪ3 ОДнако если 21 = О (вторая дисциплина не закончена в первом семестре), то х32 0, т.е. х32 = О (третья дисциплина во втором семестре не изучается). Аналогично накладываются ограничения на проведение 3-й дисциплины в 3-м семестре: х33 822Ъ3 и 12х2, + 12;t22 S22b2-e. Так как переменные S2l и 8п не могут быть отрицательными или больше единицы, то достаточно ввести ограничения 82Х 0, 822 0, S2i 1, д22 1 и S2l, S22 - целые.
Поскольку максимальное возможное количество аудиторных часов в неделю не должно превышать шести, а минимальное допустимое количество часов, в случае если дисциплина проводится не меньше двух, то в соответст -155 вий с (4.8) — (4.10) запишем систему ограничений
