Диплом - Разработка математической модели и программного обеспечения для задач составления расписания занятий

Подождите немного. Документ загружается.

Алгоритмы решения задачи были протестированы на различных выборках

исходных данных. Тестирование производилось на ЭВМ с процессором Intel

Pentium 1700 Мгц, ОЗУ 0,99 Гб; В качестве тестовых исходных данных были

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

предметах военной школы техников на 2007/2008 учебные годы

2.5. Анализ полученных результатов

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

функциональных возможностях алгоритмов решения и математической

модели, их недостатках и областях применения.

Во-первых, использованная математическая модель содержит в себе

“лишние” ограничения, существование которых обусловлено линейной

целочисленной моделью, кроме этого каждому читаемому на потоке (поток

может состоять и из одной группы) предмету ставится в соответствие 12

переменных, каждая из которых представляет из себя булеву переменную.

Во-вторых, резко возрастает время решения задачи при увеличении входных

данных. Это происходит из-за резкого увеличения количества переменных и

ограничений в модели, в результате чего возрастает размерность массивов

задачи. В-третьих, формализованная математически задача охватывает

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

между занятиями, без учета переходов между корпусами. Учет

дополнительных требований увеличит количество ограничений задачи, что

отрицательно повлияет только лишь на сложность алгоритмов решения.

ВЫВОДЫ

В ходе работы был проведен сравнительный анализ

существующего программного обеспечения по составлению расписания

занятий. Изучены требований, которые предъявляются к программного

обеспечения как к специализированному продукту, ориентированному на

работу в компьютерной сети. Построена математическая модель расписания

в 161 военной школе техников для случая очной формы обучения без

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

и разработана модель хранения исходных данных задачи. Модель хранения

исходных данных, алгоритм математической формализации модели и методы

решения были реализованы в виде программных модулей. Работа

алгоритмов была протестирована на разнородных наборах исходных данных,

в результате чего были определены возможности и области применения

алгоритмов.

На основе результатов тестирования было установлено, что по работе

алгоритмов решения задачи сильно зависят от объема входной информации

и начального допустимого базисного решения, и поэтому значительно

уступают эвристическим и декмпозиционным. Но в случае эвристического

решения его (решения) оптимальность (или достижение глобального

максимума) может быть доказана только полным перебором всех возможных

вариантов (ясно, что в этом случае время работы алгоритма будет очень

большим), поэтому итерации эвристических алгоритмов прекращаются по

достижении некоего максимального (нельзя сказать, локального или

глобального) значения. Решение такого алгоритма может быть близким к

оптимальному, но не оптимальным. В этом случае для достижения

глобального максимума можно использовать рассмотренный в работе способ

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

описанных методов решения.

ЛИТЕРАТУРА

1. Бронфман В. В., Дунин С. М., Шапиро М. А. Колебания. М.: ИНТ, 1997.

63 с.

2. Бояршинов М.“Г.“Математическое моделирование в школьном курсе

Информатики // Информатика и образование. — 1999. — №. — С. 13 —

17.

3. Гречихин А.А., Древс Ю.Г. Вузовская учебная книга: Типология,

стандартизация, компьютеризация. М.: Логос, 2000.

4. Заславский А.А. Использование стратегии расслоения переменных в

общих задачах целочисленного линейного программирования //

Экономика и мат. методы. 1997. Т. 33. Вып. 2.

5. Заславский А.А. Комбинированный метод решения задач о рюкзаке //

Экономика и мат. методы. 1999. Т. 35. Вып. 1.

6. Закон об образовании (в ред. Федерального закона от 13.01.96 № 12-ФЗ)

7. Интернет-обучение: технологии педагогического дизайна / Под ред.

кандидата педагогических наук М.“В.“Моисеевой. — М.: Издательский

дом «Камерон», 2004. — 216 с.

8. Костюка Ю.“Л. — Томск,1989. — 154С.

9. Кошкин Н. И. Ширкевич М. Г. “Справочник по элементарной дискретной

математике”

10. Концепция модернизации российского образования на период до 2010

года (Приложение к приказу Министерства Образования России от

11.02.2002 №93)

11. Лагоша Б.А., Петропавловская А.В. Комплекс моделей и методов

оптимизации расписания занятий в вузе // Экономика и мат. методы.

1993. Т. 29. Вып. 4.

12. Лебедев С.С. Модификация метода Бендерса частично целочисленного

линейного программирования // Экономика и мат. методы. 1994. Т. 30.

Вып. 2.

13. Лебедев С.С., Заславский А.А. Использование специального метода

ветвей и границ для решения целочисленной обобщенной транспортной

задачи // Экономика и мат. методы. 1995. Т. 31. Вып. 2.

14. Лебедев С.С. О методе упорядочивающей индексации целочисленного

линейного программирования // Экономика и мат. методы. 1997. Т. 33.

Вып. 2.

15. Лебедев С.С., Заславский А.А. Модифицированный метод пометок для

задач булева программирования // Экономика и мат. методы. 1998. Т.

34. Вып. 4.

16. Мильчин А.Э. Издательский словарь–справочник. М.: Юристъ, 1998.

17. Мелихов А.Н., Берштейн Л.С. четкие и расплывчатые множества, ч.1,2 -

Таганрог: ТРТУ, 1980, 1981.

18. Intel® «Обучение для будущего» при поддержке Microsoft ®:

официальный Web-сайт программы.

19. decsupport@gmail.com. Поздняк Евгений Сергеевич, Попов Вадим

Витальевич создатели программы «ДЕКАНАТ»

20. rapidshare.com/files/169086374/Dekanat_Free_Version.zip

21. http://www.rector.spb.ru

22. support@rector.spb.ru

ПРИЛОЖЕНИЕ 1. ВОЗМОЖНОСТИ ПРОГРАММНЫХ

ПРОДУКТОВ СИСТЕМ СОСТАВЛЕНИЯ РАСПИСАНИЙ.

«ДЕКАНАТ»

Возможности системы

 Подготовка и выполнение““контроля учебного процесса студентов

(формирование учебных планов, подготовка рабочих программ);

 Организация процедуры приема студентов (от приема документов,

через проведение вступительных испытаний с конкурсным отбором по

их итогам, до формирования представления к зачислению);

 Сопровождение процессов обучения студента в ВУЗ-е (переводы,

отчисления, оценки, задолженности и т.д.);

 Обеспечение процесса выпуска студентов (проведение

государственных аттестаций, защиты дипломных проектов, подготовку

и печать дипломов, академических справок и т.д.);

 Формирование различных документов с поименным составом

входящих в них преподавателей (заседаний комиссий, ведомостей и

т.д.);

 Анализ различных аспектов учебного процесса (сверка выполнения

учебных планов, движение, успеваемость и т.д.)

« РЕКТОР »

Ректор 3 - программа для составления расписания в средних школах.

Ректор-Школа - программа для составления расписания в средних школах с

профильным обучением.

Программы позволяют быстро и удобно вводить все дисциплины,

классы, нагрузки учителей, взаимосвязи уроков, кабинеты. Она позволяет

создать группы, объединить несколько классов в один урок и иметь уроки,

обучаемые через две недели. Возможно определить и большее количество

учителей для одного урока.

Мы можем выбрать точный интервал времени для каждой дисциплины,

класса, кабинета и учителя. Например можно определить, что Математика не

может быть 6-ым уроком, учительница Иванова не может обучать 6-ой урок

во вторник и 3-ий в среду, и спортзал должен быть свободен в течение 4-ых и

5-ых уроков, так как в эти дни приходят тренироваться ученики спорт-

школы. [ 21,22]

Программа соблюдает все заданные условия:

 Число окон для учителей, ограничение максимального числа окон,

ограничение дней, когда преподаватель может обучать.

 Равномерное распределение дисциплин в течений недели

 Проверка последовательности уроков полных и разделенных классов

 Размещение уроков в кабинеты

 И много больше ...

Ректор-Колледж - программа для составления расписания в средних

специальных учебных заведениях.

Ректор-ВУЗ - программа для составления расписания в ВУЗах.

Программа позволяет составить расписание занятий студентов исходя из

имеющихся данных о наличии свободных аудиторий, наличие свободных

преподавателей, а также учебного планы группы.

Программа позволяет ввести учебный план группы на семестр и далее

предоставляет интерактивные интерфейс для ввода расписания занятий, при

этом контролируя следующие параметры:

· Соответствие вновь вводимого (редактируемого) занятия учебному плану

группы;

· Свободность аудитории;

· Свободность преподавателя.

СИСТЕМНЫЕ ТРЕБОВАНИЯ

Операционная система - MS Windows XP или MS Vista.

Объем оперативной памяти - 512 Мб или выше.

Свободное место на жестком диске - не менее 100 Мб.

Рекомендуемая глубина цвета, поддерживаемая видеокартой и монитором

- 16 разрядов (бит) или больше.

Минимальное разрешение монитора - 1024 x 768.

Мышь - не менее двух кнопок.

Система АВТОР-2+

Система АВТОР-2+ предназначена для быстpого и удобного составления

расписаний занятий и сопровождения их в течение всего учебного года.

АВТОР-2+ - универсальная система. Есть несколько версий программы,

рассчитанные на любые учебные заведения:

 сpедние и специализиpованные (математические, языковые и т.п.)

школы, лицеи, гимназии;

 техникумы, училища и колледжи;

 ВУЗы с одним учебным корпусом;

 ВУЗы с несколькими учебными корпусами (с учетом переездов между

корпусами).

АВТОР-2+ позволяет максимально облегчить и автоматизиpовать

сложный тpуд составителей расписания. Система помогает легко стpоить,

коppектиpовать и pаспечатывать в виде удобных и наглядных документов:

 pасписания занятий классов (учебных групп);

 расписания пpеподавателей;

 расписание аудиторий (кабинетов);

 учебные планы;

 тарификацию.

АВТОР-2+ имеет пpиятный дизайн и дpужеcтвенный сеpвис. Программа

достаточно проста в освоении. Имеется подробное руководство, в котором

описаны все возможности и способы работы с программой.

Программа работает на любых IBM-совместимых компьютерах, начиная с

486DX с оперативной памятью 516Mb (и выше), занимает около 75 Mb на

жестком диске. Операционная система: WINDOWS XP.

Время работы зависит от размерности учебного заведения и мощности

компьютера. Полный расчет и оптимизация расписания школы среднего

размера (30 классов, 60 преподавателей, две смены) идет около 5 минут на

компьютере типа Celeron-1700.

Программа отличается уникальным и очень мощным алгоритмом

построения и оптимизации расписания. Полученное автоматическое

расписание практически не требует ручной доработки, то есть даже при

очень сложных и жестких ограничениях автоматически размещаются все

возможные занятия. Если в исходных данных имеются неразрешимые

противоречия, то их можно обнаружить и устранить, используя специальный

блок анализа.

АВТОР-2+ позволяет:

 оптимизировать "окна" в расписании;

 учитывать требуемый диапазон дней/часов как для классов, так и для

преподавателей;

 оптимально pазмещать занятия по кабинетам (аудиториям) с учетом

особенностей классов, предметов, пpеподавателей и вместимости

кабинетов;

 учитывать хаpактеp pаботы и пожелания как штатных сотpудников, так

и совместителей-почасовиков;

 легко соединять ("спаpивать") несколько классов (учебных групп) в

потоки пpи пpоведении любых занятий;

 pазделять классы пpи пpоведении занятий по иностранному языку,

физической культуре, тpуду, информатике (и любым другим

предметам) на любое количество подгрупп (до десяти!);

 вводить (помимо основных пpедметов) спецкуpсы и факультативы;

 оптимизировать равномерность и трудоемкость расписания.

По желанию заказчика АВТОР-2+ модифициpуется под условия

конкретного учебного заведения.

Система “Расписание” ver 4.0 Москва – ЛинТех

Необходимо сразу же отметить, что программа “Расписание”

ориентирована на составление школьного расписания, использование в

ВУЗ`ах и колледжах возможно лишь с некоторыми оговорками. Составление

расписания производится в рамках комплекса условий, которые

определяются на шагах ввода исходных данных. Полный перечень

возможных условий приведен ниже:

- Ограничен максимальный номер урока – т.е. количество уроков,

максимально допустимое в день;