Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Разработка математической модели и ПО для задач составления расписания
Раздел: Рефераты по информатике, программированию
Тип: доклад Добавлен 05:45:00 08 марта 2002 Похожие работы
Просмотров: 420 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Доклад.

Бакалаврская работа на тему “Разработка математической модели и ПО для задач составления расписания”


Уважаемые члены комиссии, вам представляется доклад бакалаврской работы на тему “Разработка математической модели и ПО для задач составления расписания”.

Технологию разработки расписания следует воспринимать не только как трудоемкий технический процесс, объект механизации и автоматизации с использованием ЭВМ, но и как акцию оптимального управления. Таким образом, это - проблема разработки оптимальных расписаний занятий в вузах с очевидным экономическим эффектом. Поскольку интересы участников учебного процесса многообразны, задача составления расписания - многокритериальная.

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

В ходе работы на начальном этапе были проанализированы и протестированы существующие на сегодняшний момент программные продукты. Тестирование осуществлялось на основе данных о ЧГУ за 1999/2000 учебный год. Из проанализированных программ только 3 оказались в состоянии составить расписание, удовлетворяющие почти всем требованиям, причем окончательных результатов работы одной программы дождаться так и не удалось, а 2 остальные работали около 3-4 часов.

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

- расписание составляется из расчета не более двух пар в день (что вполне подходит для случая вечерней формы обучения);

- все пары проводятся в одном корпусе;

- задача ставится в терминах линейного программирования;

- дальнейшая декомпозиция модели не производится;

- все коэффициенты модели и искомые переменные целочисленны;

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

Математическая формализация задачи составления расписания выполнялась исходя из принципов (см. плакат 1.):

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

2. Вводились булевы переменные, соответствующие паре, на которой проводится то или иное занятие. Для сохранения линейной целочисленности полученной модели потребовалось вводить по 12 переменных на каждое проводимое занятие.

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

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

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

В [3] – [8] описаны методы упорядоченной индексации и модифицированных пометок, основанные на лагранжевой декомпозиции исходной модели на ряд однострочных задач, решаемых соответственно методами упорядочивающей индексации или модифицированных пометок. К сожалению количество операций каждого из методов не допускает полиномиальной оценки; кроме того, размерность таблицы наборов (промежуточных значений) методов резко возрастает при увеличении размерности решаемой задачи, что недопустимо в нашем случае. Возможно, изменение алгоритма декомпозиции под конкретную математическую модель позволит уменьшить размерность таблиц, но пока такого алгоритма не существует.

В связи с этим в качестве методов решения были выбраны описанные в [2] модификации симплекс-метода для случая задачи целочисленного линейного программирования. В общем случае количество операций симплекс-метода не допускает полиномиальной оценки (был даже показан класс задач, для которых количество операций составляет O(en )), но для случая нашей задачи среднее число операций допускает полиномиальную оценку: O(n3 m1/( n -1) ) (n – количество переменных; m – количество ограничений). Алгоритм работы методов представлен на плакате 2.

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

Ядро системы и интерфейсная часть были написаны на Delphi 6.0. База данных была реализована на СУБД Oracle 8i, запросы к ней осуществляются на языке PL/SQL.

Алгоритмы решения задачи были протестированы на различных выборках исходных данных. Тестирование производилось на ЭВМ с процессором IntelPentium 350 Мгц, СУБД Oracle 8i был установлен на двухпроцессорном сервере: 2 CPUIntelPentiumII 350 Мгц, ОЗУ 384 Мб; в качестве канала связи использовалась LAN с пропускной способностью до 100 Мбит/с. В качестве тестовых исходных данных были использованы как реальные данные о группах, преподавателях и читаемых предметах вечерней формы обучения ЧГУ на 1999/2000 учебные годы, так и случайно формируемые исходные данные (читаемым предметам случайным образом определяли аудитории для проведения занятий). В среднем производилось от 5 до 10 тестов для каждой тестируемой размерности исходных данных. В результате получили данные, приведенные на плакате 3.

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

Во-первых, использованная математическая модель содержит в себе “лишние” ограничения, существование которых обусловлено линейной целочисленной моделью, кроме этого каждому читаемому на потоке (поток может состоять и из одной группы) предмету ставится в соответствие 12 (для случая вечерников) переменных, каждая из которых представляет из себя булеву переменную. Во-вторых, резко возрастает время решения задачи при увеличении входных данных. Это происходит из-за резкого увеличения количества переменных и ограничений в модели, в результате чего возрастает размерность массивов и соответственно время решения задачи. В-третьих, формализованная математически задача охватывает только задачу составления расписания для студентов вечерней формы обучения без учета переходов между корпусами. Учет дополнительных требований увеличит количество ограничений задачи, что отрицательно повлияет на скорость работы алгоритмов решения.

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

Отметим, что эвристические и декомпозиционные алгоритмы нельзя использовать в “чистом” виде, поскольку в случае эвристического решения его (решения) оптимальность (или достижение глобального максимума) может быть доказана только полным перебором всех возможных вариантов (ясно, что в этом случае время работы алгоритма будет очень большим), поэтому итерации эвристических алгоритмов прекращаются по достижении некоего максимального (нельзя сказать, локального или глобального) значения. Решение такого алгоритма может быть близким к оптимальному, но не оптимальным. В этом случае для достижения глобального максимума можно использовать рассмотренный в работе способ решения, поскольку оптимум может быть достигнут за несколько итераций представленных на плакате 2. методов решения.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:59:42 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:34:49 24 ноября 2015

Работы, похожие на Доклад: Разработка математической модели и ПО для задач составления расписания

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(151207)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru